Closed mglagla closed 7 years ago
parse_expr(&mut sub_iter, 0)
This is wrong because it results in wrapping It
in an iterator, and when recursing back to the same line, it wraps that type again, etc. ad infinitum. I believe this is usually called "polymorphic recursion".
The simplest fix would be to cast the iterator (at the cost of dynamic dispatch):
parse_expr(&mut sub_iter as &mut Peekable<Iterator<Item=&'a Token>>, 0)
A better solution would involve rewriting all of this code, but I'm not sure exactly how that can be done.
However, the compiler is supposed to error here, so the bug is that it goes into a loop instead.
Discussed in the compiler team meeting. This is likely a cycle in trans (possibly the collector?), quite likely triggered by a fn recursively calling itself with a derived closure, or otherwise growing infinitely. Perhaps we are missing a recursion detector in the cycle collector or elsewhere to detect infinite monomorphization problems?
Ah, @eddyb wrote that. =)
triage: P-high
This looks like another case of "slow exponential recursion", except instead of a function calling 2 different functions, it creates a type of double the size:
parse_prefix::<τ> requires
parse_prefix::<Fuse<FilterMap<&mut Peekable<τ>, [parse_prefix closure]::<τ>>>>
This type, when interned, has O(n) size, but trait operations fold it, which requires O(2^n) time. That... actually looks like it could be a part of some realistic example. Not sure what to do.
Minified:
trait Mirror {
type Image;
}
impl<T> Mirror for T { type Image = T; }
#[allow(unconditional_recursion)]
fn recurse<T>() {
recurse::<<(T, T) as Mirror>::Image>();
}
fn main() {
recurse::<()>();
}
This is a regression from 1.8.0 to 1.9.0.
On nightly, this was introduced between nightly-2016-03-18
and nightly-2016-03-20
(Changes).
What did 1.8.0 do then?
Reported a recursion limit:
hang.rs:8:1: 10:2 error: reached the recursion limit during monomorphization
hang.rs: 8 fn recurse<T>() {
hang.rs: 9 recurse::<<(T, T) as Mirror>::Image>();
hang.rs:10 }
A variant using traits hangs on all versions:
trait Mirror {
type Image;
}
impl<T> Mirror for T { type Image = T; }
trait Foo {
fn recurse(&self);
}
impl<T> Foo for T {
#[allow(unconditional_recursion)]
fn recurse(&self) {
(self, self).recurse();
}
}
fn main() {
().recurse();
}
@eddyb
A better solution would involve rewriting all of this code, but I'm not sure exactly how that can be done.
Yeah, it was my first attempt at refactoring that part, so i expected the compiler to give me some errors. Instead it hung.
@TimNN
This is a regression from 1.8.0 to 1.9.0.
Did you mean @arielb1 first minified example? I just tried to build my project on 1.8.0 and it still hung (i.e. compiled for half an hour without finishing).
@mglagla: Yes, that was @arielb1's first example.
Sure enough. All of these examples create an exponentially-long type, and if we do anything to it before the recursion limit is reached, we hang (in fact, my "reduced" example hangs while printing the overflow error message).
I wonder if we need another kind of limit -- something that caps the maximum size a type is allowed to be (measured...somehow). Then we can abort when we hit that limit instead?
Retagging as a regression. I don't see a reason it's not. This specific symptom did not used to occur. Now it does.
@nikomatsakis We can easily track "total number of children" for each Ty
, that's one option.
This can be fixed by adding a limit to type sizes at the entry to monomorphization. Will do that.
Just waiting on https://github.com/rust-lang/rust/pull/37789. Thanks @arielb1 !
Hello everyone,
while trying to refactor a small toy project (Link), I've hit a bug where the compiler never finishes compiling:
I had to stop because even after a minute it did not finish.
This is the offending commit on branch "no-alloc", the previous commit on branch master finished very quickly.
The only difference to master is this code in parse.rs, starting on line 97:
has been replaced with this code:
rustc version is 1.12.0 (3191fbae9 2016-09-23)