Exponential compile time with nested &dyn Fn type and lifetime

[jruderman]

Found with a modified fuzz-rustc (variant of #104583 that is still slow)

Code

fn main() {}

fn q<'b>(_a: &'b 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(&dyn Fn(&'b u16)))))))))))))
{
    3_u8
}

Time complexity

Seems exponential:

Nesting level	Time
9	0.4 sec
10	1.6 sec
11	6.7 sec
12	33 sec

Where it's slow

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

Version

rustc 1.75.0-nightly (a2f5f9691 2023-11-02)
binary: rustc
commit-hash: a2f5f9691b6ce64c1703feaf9363710dfd7a56cf
commit-date: 2023-11-02
host: x86_64-apple-darwin
release: 1.75.0-nightly
LLVM version: 17.0.4

@rustbot label +I-compiletime

[saethlin]

Can you try with -Ztrait-solver=next? The new solver is definitely not done, but it has (I'm told accidentally) fixed a handful of other bugs that have been reported recently.

[jruderman]

Using -Z trait-solver=next does not help, but instead makes it moderately slower. Tested with rustc 1.76.0-nightly (2f8d81f9d 2023-11-21).