Polynomial slowdown in `impl Trait` composition

[SnowyCoder]

I tried this code:

pub trait A<'a> {
    fn or(&self, other: impl A<'a>) -> impl A<'a> {
        ()
    }
}

impl<'a> A<'a> for () {
}

pub fn main() {
    let x = ().or(()).or(());
    let x = x.or(x).or(x).or(x);
    let x = x.or(x).or(x).or(x);
    let x = x.or(x).or(x).or(x);
    let x = x.or(x).or(x).or(x);
    let x = x.or(x).or(x).or(x);
    let x = x.or(x).or(x).or(x);
    let x = x.or(x).or(x).or(x);
    let x = x.or(x).or(x).or(x);
    let x = x.or(x).or(x).or(x);
    let x = x.or(x).or(x).or(x);
}

Playground link

I expected to see this happen: Give me lots of errors

Instead, this happened: Hang for a lot of time, then give me lots of errors

Meta

The issue persists both in stable and nightly.

I distilled this code from a real slowdown I encountered in a large code-base.

rustc --version --verbose:

rustc 1.87.0-nightly (617aad8c2 2025-02-24)
binary: rustc
commit-hash: 617aad8c2e8783f6df8e5d1f8bb1e4bcdc70aa7b
commit-date: 2025-02-24
host: x86_64-unknown-linux-gnu
release: 1.87.0-nightly
LLVM version: 20.1.0