Type expansion does not terminate when faced with erroneous recursive associated types

[knz]

rustc does not terminate (or will perhaps terminate with a stack overflow given sufficient time and insufficient memory) when provided the following code as input:

use std::marker::PhantomFn;
trait TypeTrans<X> : PhantomFn<(Self,X)> { type Y; }
trait Circular  : PhantomFn<Self> { 
  type T : Circular;  
}
impl<X, U : Circular> TypeTrans<X> for U {
  type Y = < <U as Circular>::T as TypeTrans<X> >::Y;
}
fn main()  {}

I expected an error message stating that the expansion recursion depth limit was exceeded (like when one makes such a mistake with C++ templates).

Instead, rustc does not terminate, and attaching gdb reveals an ever growing call stack (see backtrace below).

Meta

rustc --version --verbose:

rustc 1.0.0-dev (2b01a37ec 2015-02-21) (built 2015-02-21)
binary: rustc
commit-hash: 2b01a37ec38db9301239f0c0abcf3c695055b0ff
commit-date: 2015-02-21
build-date: 2015-02-21
host: x86_64-unknown-linux-gnu
release: 1.0.0-dev

Backtrace:

#0  0x00007ffff5431340 in middle::subst::EnumeratedItems$LT$$u27$a$C$$u20$T$GT$.Iterator::next::h1346200232120614734 ()   from /scratch/opt/lib/librustc-4e7c5e5c.so
#1  0x00007ffff5430c18 in middle::ty_fold::TypeFolder::fold_substs::h2872510736836719091 () from /scratch/opt/lib/librustc-4e7c5e5c.so
#2  0x00007ffff5431468 in middle::ty_fold::super_fold_trait_ref::h8139351459621092501 () from /scratch/opt/lib/librustc-4e7c5e5c.so
#3  0x00007ffff5430655 in middle::ty_fold::TypeFolder::fold_ty::h6033027339639275593 () from /scratch/opt/lib/librustc-4e7c5e5c.so
#4  0x00007ffff5430c5a in middle::ty_fold::TypeFolder::fold_substs::h2872510736836719091 () from /scratch/opt/lib/librustc-4e7c5e5c.so
#5  0x00007ffff5431468 in middle::ty_fold::super_fold_trait_ref::h8139351459621092501 () from /scratch/opt/lib/librustc-4e7c5e5c.so
#6  0x00007ffff5430655 in middle::ty_fold::TypeFolder::fold_ty::h6033027339639275593 () from /scratch/opt/lib/librustc-4e7c5e5c.so
#7  0x00007ffff5430c5a in middle::ty_fold::TypeFolder::fold_substs::h2872510736836719091 () from /scratch/opt/lib/librustc-4e7c5e5c.so
#8  0x00007ffff5431468 in middle::ty_fold::super_fold_trait_ref::h8139351459621092501 () from /scratch/opt/lib/librustc-4e7c5e5c.so
#9  0x00007ffff5430655 in middle::ty_fold::TypeFolder::fold_ty::h6033027339639275593 () from /scratch/opt/lib/librustc-4e7c5e5c.so
#10 0x00007ffff5430c5a in middle::ty_fold::TypeFolder::fold_substs::h2872510736836719091 () from /scratch/opt/lib/librustc-4e7c5e5c.so
....

[apasel422]

This is still an issue after removing the outdated PhantomFn bounds.

[UserAB1236872]

Yup, still an issue, I just spent a while debugging a cryptic "rustc overflowed its stack" bug, it would be useful if, when this can be detected, we could print a more specific error message on accidental circular type references.

[brson]

Old type checking bug. P-tag?

[steveklabnik]

This is still an issue after removing the outdated PhantomFn bounds.

Not any more:

C:\Users\steve\tmp> rustc .\foo.rs
error[E0275]: overflow evaluating the requirement `<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<U as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T as Circular>::T`
 --> .\foo.rs:5:23
  |
5 | impl<X, U : Circular> TypeTrans<X> for U {
  |                       ^^^^^^^^^^^^
  |
  = help: consider adding a `#![recursion_limit="128"]` attribute to your crate

given

I expected an error message stating that the expansion recursion depth limit was exceeded (like when one makes such a mistake with C++ templates).

I agree, and this is fixed.

[knz]

Thanks!