infinite recursion Trait that provides impl of its own super trait

[pnkfelix]

Test case:

trait A     { fn a(&self); }
trait B : A { fn b(&self); }

impl<T:B> A for T { fn a(&self) { self.b(); } }

impl B for int {
    fn b(&self) {
        println(fmt!("b(%?)", *self));
    }
}

fn main() {
}

Now here's the scary thing: the transcript of compiling it:

% rustc --version
/Users/pnkfelix/opt/rust-dbg/bin/rustc 0.8-pre (fd49f6d 2013-09-09 02:36:06 -0700)
host: x86_64-apple-darwin
% rustc /tmp/bus.rs
Bus error: 10
% 

From my attempts to acquire a stack trace in gdb, I am currently assuming that we're hitting an infinite loop, but we are not catching the stack overflow properly. At least, that seems to be happening some of the time; sometimes the stack seems to have been corrupted (at least from the viewpoint of gdb) so I am not certain.

Here are some stack traces (some partial) of interest:

Presumably corrupted:

(gdb) r
The program being debugged has been started already.
Start it from the beginning? (y or n) y
error while killing target (killing anyway): assertion failure on line 219 of "/SourceCache/gdb/gdb-1824/src/gdb/macosx/macosx-nat-inferior-util.c" in function "kern_return_t macosx_inferior_suspend_mach(macosx_inferior_status *)": macosx_task_valid (s->task)

warning: error on line 2184 of "/SourceCache/gdb/gdb-1824/src/gdb/macosx/macosx-nat-inferior.c" in function "void macosx_kill_inferior_safe()": (os/kern) invalid argument (0x4x)
Starting program: /Users/pnkfelix/Dev/Mozilla/rust.git/objdir-dbgopt/x86_64-apple-darwin/stage2/bin/rustc /tmp/bus.rs

Program received signal EXC_BAD_ACCESS, Could not access memory.
Reason: KERN_INVALID_ADDRESS at address: 0x00000001057ffee8
[Switching to process 11090 thread 0x1c03]
0x00000001010d6aa1 in middle::typeck::infer::lattice::CombineFieldsLatticeMethods$CombineFields::set_var_to_merged_bounds::h71b79b6e6fe3cd10Gva8::v0.8$x2dpre ()
(gdb) bt 30
#0  0x00000001010d6aa1 in middle::typeck::infer::lattice::CombineFieldsLatticeMethods$CombineFields::set_var_to_merged_bounds::h71b79b6e6fe3cd10Gva8::v0.8$x2dpre ()
(gdb) 

Presumably stack overflowed:

(gdb) r 
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /Users/pnkfelix/Dev/Mozilla/rust.git/objdir-dbgopt/x86_64-apple-darwin/stage2/bin/rustc /tmp/bus.rs

Program received signal EXC_BAD_ACCESS, Could not access memory.
Reason: KERN_INVALID_ADDRESS at address: 0x0000001fdcadea08
[Switching to process 11076 thread 0x1c03]
0x00007fff88a86018 in szone_size ()
(gdb) bt 30
#0  0x00007fff88a86018 in szone_size ()
#1  0x00007fff88ac470e in free ()
#2  0x00000001000a02a9 in rt::local_heap::local_free::hbf6638d34c91b178::v0.8$x2dpre ()
#3  0x0000000100f2bfe7 in hashmap::HashMap::with_capacity::h3db7efd01b1a5f57OUaP::v0.8$x2dpre ()
#4  0x000000010100cddc in middle::typeck::check::vtable::search_for_vtable::h3391b622fc9a29f5::v0.8$x2dpre ()
#5  0x000000010100a923 in middle::typeck::check::vtable::lookup_vtable::h3391b622fc9a29f5::v0.8$x2dpre ()
#6  0x0000000101009ccb in middle::typeck::check::vtable::lookup_vtables_for_param::anon::expr_fn::ax ()
#7  0x0000000100f3cc31 in middle::ty::each_bound_trait_and_supertraits::h5b76ffabfac448::v0.8$x2dpre ()
#8  0x0000000101009281 in middle::typeck::check::vtable::lookup_vtables_for_param::hcd3c44457f263be7::v0.8$x2dpre ()
#9  0x000000010100784f in middle::typeck::check::vtable::lookup_vtables::haf29d221bd418de8::v0.8$x2dpre ()
#10 0x000000010100d95d in middle::typeck::check::vtable::search_for_vtable::h3391b622fc9a29f5::v0.8$x2dpre ()
#11 0x000000010100a923 in middle::typeck::check::vtable::lookup_vtable::h3391b622fc9a29f5::v0.8$x2dpre ()
#12 0x0000000101009ccb in middle::typeck::check::vtable::lookup_vtables_for_param::anon::expr_fn::ax ()
#13 0x0000000100f3cc31 in middle::ty::each_bound_trait_and_supertraits::h5b76ffabfac448::v0.8$x2dpre ()
#14 0x0000000101009281 in middle::typeck::check::vtable::lookup_vtables_for_param::hcd3c44457f263be7::v0.8$x2dpre ()
#15 0x000000010100784f in middle::typeck::check::vtable::lookup_vtables::haf29d221bd418de8::v0.8$x2dpre ()
#16 0x000000010100d95d in middle::typeck::check::vtable::search_for_vtable::h3391b622fc9a29f5::v0.8$x2dpre ()
#17 0x000000010100a923 in middle::typeck::check::vtable::lookup_vtable::h3391b622fc9a29f5::v0.8$x2dpre ()
#18 0x0000000101009ccb in middle::typeck::check::vtable::lookup_vtables_for_param::anon::expr_fn::ax ()
#19 0x0000000100f3cc31 in middle::ty::each_bound_trait_and_supertraits::h5b76ffabfac448::v0.8$x2dpre ()
#20 0x0000000101009281 in middle::typeck::check::vtable::lookup_vtables_for_param::hcd3c44457f263be7::v0.8$x2dpre ()
#21 0x000000010100784f in middle::typeck::check::vtable::lookup_vtables::haf29d221bd418de8::v0.8$x2dpre ()
#22 0x000000010100d95d in middle::typeck::check::vtable::search_for_vtable::h3391b622fc9a29f5::v0.8$x2dpre ()
#23 0x000000010100a923 in middle::typeck::check::vtable::lookup_vtable::h3391b622fc9a29f5::v0.8$x2dpre ()
#24 0x0000000101009ccb in middle::typeck::check::vtable::lookup_vtables_for_param::anon::expr_fn::ax ()
#25 0x0000000100f3cc31 in middle::ty::each_bound_trait_and_supertraits::h5b76ffabfac448::v0.8$x2dpre ()
#26 0x0000000101009281 in middle::typeck::check::vtable::lookup_vtables_for_param::hcd3c44457f263be7::v0.8$x2dpre ()
#27 0x000000010100784f in middle::typeck::check::vtable::lookup_vtables::haf29d221bd418de8::v0.8$x2dpre ()
#28 0x000000010100d95d in middle::typeck::check::vtable::search_for_vtable::h3391b622fc9a29f5::v0.8$x2dpre ()
#29 0x000000010100a923 in middle::typeck::check::vtable::lookup_vtable::h3391b622fc9a29f5::v0.8$x2dpre ()
(More stack frames follow...)
(gdb) 

[pnkfelix]

@huonw clued me in that we don't have stack-overflow checks yet in the new runtime.

This is still a bug in rustc, of course. :)

[glaebhoerl]

Twisted, cool idea. GHC accepts it, given the appropriate pragmas:

{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}

class A self where foo :: self
class A self => B self where bar :: self
instance B self => A self where foo = bar

instance B Int where bar = 666

main = print (foo :: Int)

Compiles and prints 666. (The methods are slightly different, but that's not the important part.)

[thestinger]

edited the title to infinite recursion, since restoring stack safety is a separate issue

[steveklabnik]

So, uh, this compiles now?

trait A     { fn a(&self); }
trait B : A { fn b(&self); }

impl<T:B> A for T { fn a(&self) { self.b(); } }

impl B for int {
        fn b(&self) {
                    std::io::println(&*format!("b({:?})", *self));
                        }
}

fn main() {
}