Compiler hangs at ObligationForest

[RustyYato]

I tried something like the code below:

playground

struct Wrapper<T>(T);

struct Test;

pub unsafe trait Foo: Sized {
    type Bar: Bar<Self>;
}

pub unsafe trait Bar<B: Foo>: Sized {}

unsafe impl<S: Bar<Self>> Foo for Wrapper<&mut S> {
    type Bar = S;
}

unsafe impl<B: Foo<Bar = Self>> Bar<B> for Test {}

fn assert<B: Foo>(b: B) {}

fn test() {
    assert(Wrapper(&mut Test))
}

I thought this should compile, because everything checks out, but instead I got the compiler to go into an infinite loop! It never stops (I had one instance run for over 10 minutes, with no end in sight)

[matthiaskrgr]

perf top says
55,03% librustc_driver-17b8b01089c6566b.so [.] rustc_data_structures::obligation_forest::ObligationForest<O>::register_obligation_at
I wonder if that's related to #75860

[estebank]

By changing the cache key used in register_obligation_at to be the debug output instead of a ParamEnvAnd<Binder<Predicate>>, the output is the following:

error[E0275]: overflow evaluating the requirement `Test: Bar<Wrapper<&mut Test>>`
  --> f20.rs:20:5
   |
17 | fn assert<B: Foo>(b: B) {}
   |              --- required by this bound in `assert`
...
20 |     assert(Wrapper(&mut Test))
   |     ^^^^^^
   |
   = help: consider adding a `#![recursion_limit="256"]` attribute to your crate (`f20`)
note: required because of the requirements on the impl of `Foo` for `Wrapper<&mut Test>`
  --> f20.rs:11:27
   |
11 | unsafe impl<S: Bar<Self>> Foo for Wrapper<&mut S> {
   |                           ^^^     ^^^^^^^^^^^^^^^
note: required because of the requirements on the impl of `Bar<Wrapper<&mut Test>>` for `Test`
  --> f20.rs:15:33
   |
15 | unsafe impl<B: Foo<Bar = Self>> Bar<B> for Test {}
   |                                 ^^^^^^     ^^^^
   = note: 127 redundant requirements hidden
   = note: required because of the requirements on the impl of `Foo` for `Wrapper<&mut Test>`

I believe that we need to tweak the hashing algorithm for the cache key to consider some inferred lifetimes to be the same.

To clarify, the hack of using debug output for the cache key causes a lot of regressions, is not an adequate fix, but it was good enough to verify my assumptions.

[estebank]

The plot thickens:

rust/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs

Lines 51 to 54 in 696b239

	// FIXME(nikomatsakis) -- this cache is not taking into
	// account cycles that may have occurred in forming the
	// candidate. I don't know of any specific problems that
	// result but it seems awfully suspicious.

I can't tell for sure that this is what is causing the type's obligations to be expanded with fresh lifetimes, growing indefinitely, but that @nikomatsakis comment stopped me on my tracks and is making me suspicious.