Normalization Challenges with the Old Solver and the Motivation for Change

As a concrete example: equality of aliases is implemented by assuming they're rigid and recursively equating the generic arguments of the alias. ### New solver It's expected that all types potentially contain ambiguous or unnormalized aliases. Whenever an operation is performed that requires aliases to be normalized, it's the responsibility of that logic to normalize the alias (this means that matching on `ty.kind()` pretty much always has to structurally normalize first). As a concrete example: equality of aliases is implemented by a custom goal kind ([`PredicateKind::AliasRelate`][aliasrelate]) so that it can handle normalization of the aliases itself instead of assuming all alias types being equated are rigid. Despite this approach we still deeply normalize during [writeback][writeback] for performance/simplicity, so that types in the MIR can still be assumed to have been deeply normalized. --- There were a few main issues with the old solver's approach to normalization that motivated changing things in the new solver: ### Missing normalization calls It was a frequent occurrence that normalization calls would be missing, resulting in passing unnormalized types to APIs expecting everything to already be normalized. Treating ambiguous or unnormalized aliases as rigid would result in all sorts of weird errors from aliases not being considered equal to one another, or surprising inference guidance from equating unnormalized aliases' generic arguments. ### Normalizing parameter environments Another problem was that it was not possible to normalize `ParamEnv`s correctly in the old solver as normalization itself would expect a normalized `ParamEnv` in order to give correct results. See the chapter on `ParamEnv`s for more information: [`Typing/ParamEnv`s: Normalizing all bounds](./typing_parameter_envs.md#normalizing-all-bounds) ### Unnormalizable non-rigid aliases in higher ranked types Given a type such as `for<'a> fn(<?x as Trait<'a>::Assoc>)`, it is not possible to correctly handle this with the old solver's approach to normalization. If we were to normalize it to `for<'a> fn(?y)` and register a goal to normalize `for<'a> <?x as Trait<'a>>::Assoc -> ?y`, this would result in errors in cases where `<?x as Trait<'a>>::Assoc` normalized to `&'a u32`. The inference variable `?y` would be in a lower [universe] than the placeholders made when instantiating the `for<'a>` binder.

The old solver expected immediate normalization, leading to issues like missing calls (resulting in incorrect type comparisons and inference) and problems normalizing `ParamEnv`s (as normalization required a normalized `ParamEnv`). It also struggled with unnormalizable, non-rigid aliases in higher-ranked types. The new solver addresses these by allowing unnormalized aliases, normalizing them only when necessary.