Exponential compile time with nested &dyn Fn type

[jruderman]

Found with a modified fuzz-rustc

Code

fn id(
    f: &dyn Fn(u32)
) -> &dyn Fn(
    &dyn Fn(
        &dyn Fn(
            &dyn Fn(&dyn Fn(&dyn Fn(&dyn Fn(&dyn Fn(&dyn Fn(&dyn Fn(&dyn Fn(&dyn Fn(u32)))))))))
        )
    )
) {
    f
}

fn main() {}

Time complexity

Seems exponential:

Nesting level	Time
9	0.9 sec
10	4.2 sec
11	17 sec
12	80 sec

Where it's slow

• From -Z time-passes: item_bodies_checking (full output)
• From sampling: seems like recursion involving type inference (head of sample tree)

Not a recent regression

It's slow at least as far back as nightly-2018-01-01

Version

rustc 1.67.0-nightly (a00f8ba7f 2022-11-15)
binary: rustc
commit-hash: a00f8ba7fcac1b27341679c51bf5a3271fa82df3
commit-date: 2022-11-15
host: x86_64-apple-darwin
release: 1.67.0-nightly
LLVM version: 15.0.4

@rustbot label +I-compiletime