Compiler hang with recursive trait requirement and `default impl`

[jruderman]

Found by mutating tests/ui/traits/issue-18400.rs with my variant of fuzz-rustc

Code

#![allow(incomplete_features)]
#![feature(specialization)]

trait Set<T> {
    fn contains(&self, bit: T);
}

default impl<T, S> Set<&T> for S where
    S: Set<T>,
{
    fn contains(&self, _: &T) {}
}

fn main() {
    0.contains(());
}

Error output

With the default recursion limit (128), rustc effectively hangs without showing any output.

With #![recursion_limit = "8"], it exits with E0275:

error[E0275]: overflow evaluating the requirement `{integer}: Set<&&&&&&&&&_>`
  --> d2.rs:16:7
   |
16 |     0.contains(());
   |       ^^^^^^^^
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "16"]` attribute to your crate (`d2`)
note: required for `{integer}` to implement `Set<&&&&&&&&&_>`
  --> d2.rs:9:20
   |
9  | default impl<T, S> Set<&T> for S where
   |                    ^^^^^^^     ^
   = note: 8 redundant requirements hidden
   = note: required for `{integer}` to implement `Set<&&&&&&&&&_>`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0275`.

Where it's slow

-Z time-passes: type_check_crate

Sample head: trait selection and obligations

Not a recent regression

It's slow to the point of hanging at least as far back as nightly 2021-01-01

Version

rustc 1.76.0-nightly (ba7c7a301 2023-11-13)
binary: rustc
commit-hash: ba7c7a301984967c8c13adb580ef9b86ba706a83
commit-date: 2023-11-13
host: x86_64-apple-darwin
release: 1.76.0-nightly
LLVM version: 17.0.4

@rustbot label +I-compiletime +A-specialization +F-specialization +T-compiler

[lqd]

(Note that if it's an actual hang and not just rustc being slow, there's I-hang instead of I-compiletime.)

[clubby789]

Some measurements of the time until recursion limit reached:

recursion_limit	Time
16	0.047
32	0.114
64	2.143
80	6.945
100	24.130
128	1:40.51

Additionally, if we specify 0i32, we still always hit the recursion limit but almost immediately, with a very small linear increase as the limit increases