rustc overflows its stack when type checking ~~a simple program~~ polymorphmic recursion

[jhjourdan]

The following program triggers a stack overflow in rustc:

struct S<T> {
    t : T,
    s : Box<S<fn(u : T)>>
}

fn f(x : S<u32>) { }

fn main () { }

My version of rustc:

$ rustc --version
rustc 1.15.0-nightly (71c06a56a 2016-12-18)

The problem also appears when replacing fn(u : T) with fn() -> T.

[achanda]

Interestingly, I don't see a stack trace with RUST_BACKTRACE

:~/src$ RUST_BACKTRACE=1 rustc test.rs

thread 'rustc' has overflowed its stack
fatal runtime error: stack overflow

Same version of rustc

[AraHaan]

Well oddly than not it does look to see if there is about half a GB left on disk and if there is not updating would not work. Which is bad because there actually is enough space if I have an older version of it.

[AraHaan]

This also happens that sometimes it actually uses over than 1 GB of RAM as well for some insanely small code for some unknown reason.

[jhjourdan]

The struct is obviously infinitely recursive.

I don't know what you mean by this, but I do no think this is the problem here. The following program also reveals the problem:
rust

struct S<T> {
    t : T,
    s : Box<S<Option<fn(u : T)>>>
}

But the following is accepted:

struct S<T> {
    t : T,
    s : Box<S<T>>
}

fn f(x : S<u32>) { }

fn main () { }

Recursive structs are a well-known and important feature of Rust.

[sfackler]

@jhjourdan S<()> contains an S<fn(u: ())>, which contains an S<fn(u: fn(u: ()))>, which contains an S<fn(u: fn(u: fn(u: ())))>, which contains...

[jhjourdan]

@sfackler : it does not /contain/ it. It /refers/ to it.

Again, recursive structs are a well-known, important feature of Rust. For example, you cannot define linked lists without them.

[sfackler]

The issue is not the storage of the struct. The issue is that you are asking the compiler to generate code for an infinite number of instantiations of S.

struct List<T>(Option<Box<List<T>>>)

Is a very different thing than

struct Foo<T>(Option<Box<List<fn(T)>>>);

[jhjourdan]

Well, but I am not asking the compiler to generate any code here... Or at least, the code that is generated is not used anywhere.

[sfackler]

I'm confused then - why is it valuable for it to be possible to define but never use this type?

[jhjourdan]

Btw, now I understand better why my code provokes a stack overflow.

But still, there is no reason this code is generated if the code is never used, and even then, this is not an excuse for rustc to do a stack overflow.

[brson]

Yes there should be some reasonable recursion limit here.

[insaneinside]

More importantly, rustc should issue a diagnostic instead of overflowing its stack. 😮

[istankovic]

This is no longer reproducible with rustc 1.26.0-nightly (2789b06 2018-03-06).

[pnkfelix]

The phenomenon that @sfackler is describing above is technically known as "polymorphic recursion."

cc #4287

But, as noted by @istankovic above, this particular instance of the diagnostic issue with polymorphic recursion (that I believe persists to this day) no longer seems to replicate.

Marking as E-needstest.