-Ztrait-solver=next-coherence: issue-90662-projection-caching.rs breaks

[lcnr]

minimized https://rust.godbolt.org/z/MK6hWKhdb

trait HasProvider<T: ?Sized> {}
trait Provider<M: ?Sized> {
    type Interface: ?Sized;
}

struct Service;
struct ServiceImpl;
impl<M: HasProvider<&'static ()> + ?Sized> Provider<M> for ServiceImpl {
    type Interface = Service;
}

struct TestModule;
impl HasProvider<&'static ()> for TestModule {}
impl HasProvider<<ServiceImpl as Provider<TestModule>>::Interface> for TestModule {}

for whatever reason dyn Repository breaks, () does not.

why this compiles in the old solver:

• before equating impl headers, normalize both impls
• Projection(<ServiceImpl as Provider<TestModule>>::Interface)
• single candidate with nested goal TestModule: HasProvider<&'static ()> is simply emitted as a nested goal, successfully normalize to Service
• equating impl HasProvider<&'static ()> for TestModule {} with impl HasProvider<Service> for TestModule {} fails

what's happening in the new solver:

• coherence equates the two impls, resulting in a nested alias-relate(<ServiceImpl as Provider<TestModule>>::Interface, &'static ())
• uniquification results in exists<'0> alias-relate(<ServiceImpl as Provider<TestModule>>::Interface, &'0 ())
• normalizes-to candidat with single impl, normalizing to Service with nested goal TestModule: HasProvider<&'static ()>, again, canonicalized to '0
• two candidates:
  • impl HasProvider<&'static ()> for TestModule {}, YES '0 == 'static
  • impl HasProvider<<ServiceImpl as Provider<TestModule>>::Interface> for TestModule {}
    • unify <ServiceImpl as Provider<TestModule>>::Interface with &'static (), resulting in an inductive cycle
  • AMBIG
• WHY DOES ALIAS-RELATE NOT FAIL?

[BoxyUwU]

I suspect alias relate doesnt fail because the normalizes-to candidate in the alias-relate goal is going to have a response of Ok(Ambig(Overflow)) with no constraints. In evaluate_added_goals_and_make_canonical_response we call make_ambiguous_response_no_constraints if try_evaluate_added_goals is Certainty::OVERFLOW.
So in this specific caseI would assume:

• infer var hack the normalizes-to(/* alias */, &'0 ()) to normalizes-to(/* alias */, ?0)
• assemble normalizes-to candidates. Inferring ?0=Service and adding TestModule: HasProvider<&'static ()>
• we call evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
• proving TestModule: HasProvider<&'static ()> results in Ok(Ambig(Overflow)) because unifying certainties always prefers overflow to other causes of ambiguity.
• return a no constraint overflow result from evaluate_added_goals_and_make_response because the added goals had a response of Certainty::OVERFLOW instead of returning an ambiguous response with the ?0=Service
• the normalizes-to goals with a rhs of &'0 () only sees a Ok(Ambig(Overflow)) response and has no knowledge that ?0 = Service should be the case as it was not in the response

This is commented on a little in the function already:

        if let Certainty::OVERFLOW = certainty {
            // If we have overflow, it's probable that we're substituting a type
            // into itself infinitely and any partial substitutions in the query
            // response are probably not useful anyways, so just return an empty
            // query response.
            //
            // This may prevent us from potentially useful inference, e.g.
            // 2 candidates, one ambiguous and one overflow, which both
            // have the same inference constraints.
            //
            // Changing this to retain some constraints in the future
            // won't be a breaking change, so this is good enough for now.
            return Ok(self.make_ambiguous_response_no_constraints(MaybeCause::Overflow));
        }

---

I have not actually looked at any debug logs for this though and am mostly just going off reading the provided code snippet and explanation of what's happening in new solver.

[compiler-errors]

For the record, these tests hang if that hack is removed.

test [ui] tests/ui/traits/new-solver/cycles/coinduction/fixpoint-exponential-growth.rs has been running for a long time
test [ui] tests/ui/traits/new-solver/overflow/exponential-trait-goals.rs has been running for a long time

[lcnr]

similar example: unlike a "true" inductive cycle this avoids fatal overflow in the new solver and an endlessly growing fixpoint cycle in the new one

trait Trait {
    type Assoc;
}

struct W<T: ?Sized>(*mut T);
impl<T: ?Sized> Trait for W<W<T>>
where
    W<T>: Trait,
{
    type Assoc = ();
}

trait NoOverlap {}
impl<T: Trait<Assoc = u32>> NoOverlap for T {}
impl<T: ?Sized> NoOverlap for W<T> {}

fn main() {}