Description
This code is not expected to compile successfully:
fn main() {
recurse(std::iter::empty());
}
struct Wrapped<T>(T);
struct IteratorOfWrapped<T, I: Iterator<Item = T>>(I);
impl<T, I: Iterator<Item = T>> Iterator for IteratorOfWrapped<T, I> {
type Item = Wrapped<T>;
fn next(&mut self) -> Option<Wrapped<T>> {
self.0.next().map(Wrapped)
}
}
fn recurse<T>(elements: T) -> Vec<char>
where
T: Iterator<Item = ()>,
{
recurse(IteratorOfWrapped(elements).map(|t| t.0))
}This can't compile successfully because recurse<T> calls recurse<Map<IteratorOfWrapped<(), T>, [closure@<source>:22:51: 22:58]>> recursively, which then calls recurse<Map<IteratorOfWrapped<(), Map<IteratorOfWrapped<(), T>, [closure@<source>:22:51: 22:58]>>, [closure@<source>:22:51: 22:58]>>, and so on...
However up to stable 1.55, the code failed to compile quickly with the default recursion limit. On the compiler explorer, you can see it even handling #![recursion_limit = "800"] without timeout. However, go to 1.56 and it no longer reaches a compilation error in time with #![recursion_limit = "30"]. Still just as slow on nightly (rustc 1.59.0-nightly (6bda5b331 2021-12-12)).
@rustbot label: regression-from-stable-to-stable, perf-regression, I-compiletime, T-compiler, E-needs-bisection
Comes from: https://users.rust-lang.org/t/compiler-hanging/68804
Rough estimate on my machine: In the area of recursion_limit being 20-30, the time more-than doubles for each increase of the recursion limit by 2 or 3, so it really is exponential AFAICT.