Circular trait bounds causes stack overflow in rustc

[mikejsavage]

overflow.rs:

pub struct Deg { d : f64 }
pub trait Angle : Equiv< Self > { }

impl Angle for Deg { }

impl< T : Angle > Equiv< T > for T {
        fn equiv( &self, other : &T ) -> bool {
                return true;
        }
}

pub fn main() { }

compiling:

$ rustc -v
rustc 0.9
host: x86_64-unknown-linux-gnu
$ rustc overflow.rs 
overflow.rs:9:1: 13:2 error: cannot provide an extension implementation where both trait and type are not defined in this crate
overflow.rs:9 impl< T : Angle > Equiv< T > for T {
overflow.rs:10  fn equiv( &self, other : &T ) -> bool {
overflow.rs:11          return self.normalize() == other.normalize();
overflow.rs:12  }
overflow.rs:13 }
task 'rustc' has overflowed its stack
Illegal instruction (core dumped)

[Aatch]

Definitely a bug. Causes an infinte loop while trying to create the vtables it seems, the loop I got was

middle::typeck::check::vtable::search_for_vtable
middle::typeck::check::vtable::lookup_vtables_for_param::closure
middle::ty::each_bound_trait_and_supertraits
middle::typeck::check::vtable::lookup_vtables_for_param
middle::typeck::check::vtable::lookup_vtables
...

Looking at the RUST_LOG output, theres something odd about the way it's substituting, each loop creates a new generic type to substitute into Equiv.

[Aatch]

Upon further inspection (including reading the gdb backtrace properly), it isn't actually an infinite loop, instead is just a very, very long one. since it breaks out of that loop eventually and then overflows.

[Aatch]

Aha! There are other generic implementations of Equiv in std which mean you cannot make your own generic implementations of Equiv (see #3429).

As for why the loop happens... I don't know.

[Aatch]

Related to #12511

[doy]

This is enough to cause the stack overflow, if it helps any:

trait Foo : Bar<Self> { }
trait Bar<T: Foo> { }

[steveklabnik]

Triage: @doy's sample still overflows on

rustc 1.0.0-dev (9ade482b3 2015-01-15 17:12:55 +0000)

[reem]

Just to add another case, using associated types doesn't work either:

trait One { type Foo: Two; }
trait Two { type Foo: One; }

also overflows.

[grissiom]

On rustc 1.0.0-dev (593db00 2015-03-25) (built 2015-03-25),

trait One { type Foo: Two; }
trait Two { type Foo: One; }

does not overflow.

trait Foo : Bar<Self> { }
trait Bar<T: Foo> { }

and the original code does not compile.

[tamird]

@steveklabnik this should have been closed by #23013. Would you do the honours?

[alexcrichton]

Steal!