Exponential compile times for chained RPITIT

[Artemis21]

I tried this code:

#![feature(return_position_impl_trait_in_trait)]

trait Nest: FnOnce() -> () {
    fn nest(self) -> impl Nest;
}

impl<P: FnOnce() -> ()> Nest for P {
    fn nest(self) -> impl Nest {
        || self()
    }
}

fn inner(val: &'static str) -> impl Nest {
    move || {
        val;
    }
}

fn main() {
    inner("")
        .nest().nest().nest().nest().nest()
        .nest().nest().nest().nest().nest()
        .nest().nest().nest().nest().nest()
        .nest().nest().nest().nest().nest()
        .nest().nest().nest().nest().nest();
}

I expected this to compile reasonably quickly.

Instead the above example took about a minute and a half. With 20 .nest()s in sequence, it takes between two and three seconds. For each subsequent .nest(), it takes about twice the time.

When I replace || self() with just self, it compiles almost instantly. The same happens when I remove the apparently inconsequential val; statement, or when I use an owned type instead of a &'static str.

Meta

rustc --version --verbose:

rustc 1.66.0-nightly (3f83906b3 2022-09-24)
binary: rustc
commit-hash: 3f83906b30798bf61513fa340524cebf6676f9db
commit-date: 2022-09-24
host: x86_64-unknown-linux-gnu
release: 1.66.0-nightly
LLVM version: 15.0.0

[Artemis21]

The version of this without using RPITIT also compiles quickly:

fn nest<F: FnOnce() -> ()>(f: F) -> impl FnOnce() -> () {
    || f()
}

fn inner(val: &'static str) -> impl FnOnce() -> () {
    move || {
        val;
    }
}

fn main() {
    nest(nest(nest(nest(nest(
        nest(nest(nest(nest(nest(
            nest(nest(nest(nest(nest(
                nest(nest(nest(nest(nest(
                    inner("")
                )))))
            )))))
        )))))
    )))));
}

[compiler-errors]

how interesting, I'll look into this :)

[Mark-Simulacrum]

Feels like the desugaring might end up similar to #100886, so maybe worth trying any fix on that too.

[compiler-errors]

This doesn't exactly have to do with RPITIT -- can be replicated with regular opaques via impl_trait_in_assoc_type

#![feature(impl_trait_in_assoc_type)]

trait Nest: FnOnce() -> () {
    type Nest: Nest;
    fn nest(self) -> Self::Nest;
}

impl<P: FnOnce() -> ()> Nest for P {
    type Nest = impl Nest;
    fn nest(self) -> Self::Nest {
        || self()
    }
}

fn inner(val: &'static str) -> impl Nest {
    move || {
        val;
    }
}

fn main() {
    inner("")
        .nest().nest().nest().nest().nest()
        .nest().nest().nest().nest().nest()
        .nest().nest().nest().nest().nest()
        .nest().nest().nest().nest().nest()
        .nest().nest().nest().nest().nest();
}