Nested closures result in exponential compilation time increase

[VFLashM]

Closures include captured types twice in a type tree.

Wrapping one closure with another leads to doubling the amount of types in the type tree.

With nested closures compile time increases exponentially and it's extremely easy to break the compiler. Obviously it's even easier if each level captures more than one closure.

I think I have a fix for this one ready, about to push it.

I tried this code:

fn dup<F: Fn(i32) -> i32>(f: F) -> impl Fn(i32) -> i32 {
    move |a| f(2*a)
}

fn main() {
    let f = |a| a;

    let f = dup(f);
    let f = dup(f);
    let f = dup(f);
    let f = dup(f);
    let f = dup(f);

    let f = dup(f);
    let f = dup(f);
    let f = dup(f);
    let f = dup(f);
    let f = dup(f);

    let f = dup(f);
    let f = dup(f);
    let f = dup(f);
    let f = dup(f);
    let f = dup(f);

    let f = dup(f);
    let f = dup(f);
    let f = dup(f);
    let f = dup(f);
    let f = dup(f);

    // Compiler dies around here if it tries
    // to walk the tree exhaustively.

    let f = dup(f);
    let f = dup(f);
    let f = dup(f);
    let f = dup(f);
    let f = dup(f);

    let f = dup(f);
    let f = dup(f);
    let f = dup(f);
    let f = dup(f);
    let f = dup(f);

    println!("Hello {}", f(1));
}

I expected to see this happen: no error.

Instead, this happened:

error: reached the type-length limit while instantiating `dup::<[closure@src/main.rs:2:5: ...rs:6:13: 6:18]]]]]]]]]]]]]]]]]]>`
 --> src/main.rs:1:1
  |
1 | / fn dup<F: Fn(i32) -> i32>(f: F) -> impl Fn(i32) -> i32 {
2 | |     move |a| f(2*a)
3 | | }
  | |_^
  |
  = note: consider adding a `#![type_length_limit="1835001"]` attribute to your crate

Meta

I tried it both on stable and nightly rust:

$ rustc --version --verbose
rustc 1.45.0-nightly (7ebd87a7a 2020-05-08)
binary: rustc
commit-hash: 7ebd87a7a1e0e21767422e115c9455ef6e6d4bee
commit-date: 2020-05-08
host: x86_64-pc-windows-msvc
release: 1.45.0-nightly
LLVM version: 9.0

$ rustc --version --verbose
rustc 1.43.0 (4fb7144ed 2020-04-20)
binary: rustc
commit-hash: 4fb7144ed159f94491249e86d5bbd033b5d60550
commit-date: 2020-04-20
host: x86_64-pc-windows-msvc
release: 1.43.0
LLVM version: 9.0

[panstromek]

Just for the record, similar issue has been fixed recently #68061

It's similar but without any captures.

[VFLashM]

There is already a src/test/ui/closures/deeply-nested_closures.rs, so I think it's a separate issue.