Skip to content

Exponential compile times for chained RPITIT #102527

@Artemis21

Description

@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

Activity

Artemis21

Artemis21 commented on Sep 30, 2022

@Artemis21
Author

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("")
                )))))
            )))))
        )))))
    )))));
}
added
I-slowIssue: Problems and improvements with respect to performance of generated code.
requires-nightlyThis issue requires a nightly compiler in some way.
on Sep 30, 2022
compiler-errors

compiler-errors commented on Sep 30, 2022

@compiler-errors
Member

how interesting, I'll look into this :)

Mark-Simulacrum

Mark-Simulacrum commented on Sep 30, 2022

@Mark-Simulacrum
Member

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

added
I-compiletimeIssue: Problems and improvements with respect to compile times.
and removed
I-slowIssue: Problems and improvements with respect to performance of generated code.
on Sep 30, 2022
compiler-errors

compiler-errors commented on Jun 12, 2023

@compiler-errors
Member

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();
}
added
A-impl-traitArea: `impl Trait`. Universally / existentially quantified anonymous types with static dispatch.
and removed on Jun 12, 2023
compiler-errors

compiler-errors commented on Jun 29, 2023

@compiler-errors
Member

Triage: still hangs

added a commit that references this issue on Oct 14, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Labels

A-impl-traitArea: `impl Trait`. Universally / existentially quantified anonymous types with static dispatch.C-bugCategory: This is a bug.F-impl_trait_in_assoc_type`#![feature(impl_trait_in_assoc_type)]`I-compiletimeIssue: Problems and improvements with respect to compile times.requires-nightlyThis issue requires a nightly compiler in some way.

Type

No type

Projects

Status

Non-blocking

Milestone

No milestone

Relationships

None yet

    Development

    No branches or pull requests

      Participants

      @compiler-errors@Mark-Simulacrum@saethlin@Artemis21

      Issue actions

        Exponential compile times for chained RPITIT · Issue #102527 · rust-lang/rust