Exponential slowdown in catching an `overflow` error.

[steffahn]

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.

[parasyte]

Possibly related to #89195?

[hkratz]

Bisected to #85868, cc @Aaron1011

bisected with cargo-bisect-rustc v0.6.1

searched nightlies: from nightly-2021-06-01 to nightly-2021-12-08 regressed nightly: nightly-2021-09-03 searched commit range: https://github.com/rust-lang/rust/compare/50171c310cd15e1b2d3723766ce64e2e4d6696fc...371f3cd regressed commit: https://github.com/rust-lang/rust/commit/371f3cd3fe523d0b398ed1db1620667c53ba7d02

Host triple: x86_64-unknown-linux-gnu
Reproduce with:

cargo-bisect-rustc -t 3 --start 2021-06-01 --script ./test.sh

test.sh:

#!/bin/bash
cargo build
exit 0

@rustbot label -E-needs-bisection

[steffahn]

That PR seems incremental-compilation related. This leaves the question of whether the regression also happens without incremental compilation turned on, and whether or not it happens at the same point.

[wesleywiser]

This is almost certainly the same issue as #89195 then.

[steffahn]

Hard to know for certain until #89195 has a mvce. Also note that, as far as I understand, #89195 is observable with cargo check whereas this bug only appears with cargo build. (I somehow forgot to mention that...)

[apiraino]

Assigning priority as discussed in the Zulip thread of the Prioritization Working Group.

@rustbot label -I-prioritize +P-high