rustc does not terminate after 1.57.0

[dingelish]

I tried this code:

#![recursion_limit="256"]
use futures_util::{Future, future, TryFutureExt};
use std::path::Path;

struct Foo;

fn orz<T>(path: T) -> impl Future<Output = Result<String, ()>>
where
    T: AsRef<Path> + Send + 'static,
{
    std::future::ready(Ok("".into()))
}

fn zoo<T>(arg: T) -> impl Future<Output = Result<Foo, ()>>
where T: AsRef<Path> + Send + 'static
{
    orz(arg).map_err(|_| ()).and_then(|line| {
        let result = Ok(Foo{});
        std::future::ready(result)
    })
}

fn root() ->  impl Future<Output = Result<Foo, ()>> {
    future::err(())
        // more zoo more time
        .or_else(|_| zoo(""))
        .or_else(|_| zoo(""))
        .or_else(|_| zoo(""))
        .or_else(|_| zoo(""))
        .or_else(|_| zoo(""))
        .or_else(|_| zoo(""))
        .or_else(|_| zoo(""))
        .or_else(|_| zoo(""))
        .or_else(|_| zoo(""))
        .or_else(|_| zoo(""))
        .or_else(|_| zoo(""))
        .or_else(|_| zoo(""))
        .or_else(|_| zoo(""))
        .or_else(|_| zoo(""))
        .or_else(|_| zoo(""))
}

fn main() {
    println!("Hello, world!");
    root();
}

I expected to see this happen: it compiles successfully

Instead, this happened: rustc takes long time to compile as the number of or_else(|_| zoo("")) increases. looks like exponential time. 1.56.1 successfully compiles it.

Meta

rustc --version --verbose:

rustc 1.58.0 (02072b482 2022-01-11)
binary: rustc
commit-hash: 02072b482a8b5357f7fb5e5637444ae30e423c40
commit-date: 2022-01-11
host: x86_64-unknown-linux-gnu
release: 1.58.0
LLVM version: 13.0.0

Backtrace

<backtrace>

no backtrace

[Aaron1011]

This should compile in a reasonable amount of time on the latest nightly.

[dingelish]

This should compile in a reasonable amount of time on the latest nightly.

thanks @Aaron1011 ! confirmed latest nightly fixed this. could i have some background? how's the fix looks like? thanks!

[Aaron1011]

@dingelish: In the past, we used to aggressively cache the results of trait evaluation and projection. However, this turned out to interact badly with incremental compilation, and could lead to ICEs. As a result, some of this caching logic was removed in PRs like #88945

While our performance benchmarks showed only small to moderate performance regressions, it turned out that the caching was needed to prevent exponential blowup in some cases that were not covered by our benchmark. I re-added some of the caching logic in PRs like #89831 (in a modified and potentially less effective form, to be compatible with incremental compilation). This appears to have fixed the exponential blowup.

See #89195 and rust-lang/rustc-perf#1124 for more context

[dingelish]

thanks for the explaination! it's pretty clear. thanks again!