alias-relate results in exponential blowup

[lcnr]

alias-relate currently assembles three candidates and then decides which candidate should be used:

• lhs-normalizes-to-rhs: checks normalize(lhs) == rhs
• rhs-normalizes-to-lhs: checks lhs = normalize(rhs)
• outside of coherence bidirectional-normalizes-to: normalize(lhs) == normalize(rhs)
• args-relate: if both aliases have the same DefId, relates their generic arguments

This results in a hang in the following example:

trait Identity {
    type Assoc: ?Sized;
}

impl<T: ?Sized> Identity for T {
    type Assoc = T;
}

type Id<T> = <T as Identity>::Assoc;

type Five<T> = Id<Id<Id<Id<Id<T>>>>>;
// hangs
type Ty<T> = Five<Five<Five<Five<Five<T>>>>>;
// ok
// type Ty<T> = Five<T>;

trait Trait<T> {}

impl<T> Trait<T> for Ty<T> {}
impl Trait<u32> for Ty<i32> {}

To see what's going on, consider Id<Id<?x>> == Id<Id<u32>>:

• alias-relate(Id<Id<?x>>, Id<Id<u32>>)
  • lhs-normalizes-to-rhs ~> alias-relate(Id<?x>, Id<Id<u32>>)
    • lhs-normalizes-to-rhs ~> ?x constrained to Id<Id<u32>>
    • rhs-normalizes-to-lhs ~> alias-relate(Id<?x>, Id<u32>)
      • lhs-normalizes-to-rhs ~> ?x constrained to Id<u32>
      • rhs-normalizes-to-lhs ~> alias-relate(Id<?x>, u32)
        • lhs-normalizes-to-rhs ~> ?x constrained to u32
      • args-relate ~> ?x constrained to u32
      • candidites with different results ~> AMBIGUITY
    • args-relate ~> ?x constrained to Id<u32>
    • candidates with different results ~> AMBIGUITY
  • rhs-normalizes-to-lhs ~> alias-relate(Id<Id<?x>>, Id<u32>)
    • ...
  • args-relate ~> alias-relate(Id<?x>, Id<u32>)
    • ...

Even when ignoring cache hits, the blowup is still depth^2 while normalizing <alias as Identity>::Assoc also normalizes the self type when searching for candidates.

I would like to avoid this issue somehow, something like try_normalize_ty(lhs) == try_normalize_ty(rhs) would avoid this blowup but has other issues and is non-trivial.