Exponential compile times for chained RPITIT

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

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("")
                )))))
            )))))
        )))))
    )))));
}

how interesting, I'll look into this :)

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

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();
}

Triage: still hangs

Auto merge of rust-lang#115822 - compiler-errors:stabilize-rpitit, r=…

This no longer hangs with the next solver. The code compiles quickly even if I double the number of nest calls.
Still hangs with the old solver.

Navigation Menu

Repository navigation

Exponential compile times for chained RPITIT #102527

Meta

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Exponential compile times for chained RPITIT #102527

Description

Meta

Activity

Artemis21 commented on Sep 30, 2022

compiler-errors commented on Sep 30, 2022

Mark-Simulacrum commented on Sep 30, 2022

compiler-errors commented on Jun 12, 2023

compiler-errors commented on Jun 29, 2023

adwinwhite commented on Jan 13, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions