How to Normalize Types in Rust: Entry Points and Solver Transition

- Normalizing `<?x as Iterator>::Item` results in some new inference variable `?y`, as `<?x as Iterator>::Item` is an ambiguous alias - The final result is that normalizing `Foo<?x>` results in `?y` ## How to normalize When interfacing with the type system it will often be the case that it's necessary to request a type be normalized. There are a number of different entry points to the underlying normalization logic and each entry point should only be used in specific parts of the compiler.  An additional complication is that the compiler is currently undergoing a transition from the old trait solver to the new trait solver. As part of this transition our approach to normalization in the compiler has changed somewhat significantly, resulting in some normalization entry points being "old solver only" slated for removal in the long-term once the new solver has stabilized. The transition can be tracked via the [WG-trait-system-refactor](https://github.com/rust-lang/rust/labels/WG-trait-system-refactor) label in Github. Here is a rough overview of the different entry points to normalization in the compiler: - `infcx.at.structurally_normalize` - `infcx.at.(deeply_)?normalize` - `infcx.query_normalize` - `tcx.normalize_erasing_regions` - `traits::normalize_with_depth(_to)` - `EvalCtxt::structurally_normalize` ### Outside of the trait solver The [`InferCtxt`][infcx] type exposes the "main" ways to normalize during analysis: [`normalize`][normalize], [`deeply_normalize`][deeply_normalize] and [`structurally_normalize`][structurally_normalize]. These functions are often wrapped and re-exposed on various `InferCtxt` wrapper types, such as [`FnCtxt`][fcx] or [`ObligationCtxt`][ocx] with minor API tweaks to handle some arguments or parts of the return type automatically. #### Structural `InferCtxt` normalization [`infcx.at.structurally_normalize`][structurally_normalize] exposes structural normalization that is able to handle inference variables and regions. It should generally be used whenever inspecting the kind of a type. Inside of HIR Typeck there is a related method of normalization- [`fcx.structurally_resolve`][structurally_resolve], which will error if the type being resolved is an unresolved inference variable. When the new solver is enabled it will also attempt to structurally normalize the type. Due to this there is a pattern in HIR typeck where a type is first normalized via `normalize` (only normalizing in the old solver), and then `structurally_resolve`'d (only normalizing in the new solver). This pattern should be preferred over calling `structurally_normalize` during HIR typeck as `structurally_resolve` will attempt to make inference progress by evaluating goals whereas `structurally_normalize` does not. #### Deep `InferCtxt` normalization ##### `infcx.at.(deeply_)?normalize` There are two ways to deeply normalize with an `InferCtxt`, `normalize` and `deeply_normalize`. The reason for this is that `normalize` is a "legacy" normalization entry point used only by the old solver, whereas `deeply_normalize` is intended to be the long term way to deeply normalize. Both of these methods can handle regions. When the new solver is stabilized the `infcx.at.normalize` function will be removed and everything will have been migrated to the new deep or structural normalization methods. For this reason the `normalize` function is a no-op under the new solver, making it suitable only when the old solver needs normalization but the new solver does not. Using `deeply_normalize` will result in errors being emitted when encountering ambiguous aliases[^2] as it is not possible to support normalizing *all* ambiguous aliases to inference variables[^3]. `deeply_normalize` should generally only be used in cases where we do not expect to encounter ambiguous aliases, for example when working with types from item signatures. ##### `infcx.query_normalize` [`infcx.query_normalize`][query_norm] is very rarely used, it has almost all the same restrictions as `normalize_erasing_regions` (cannot handle inference variables, no diagnostics support) with the main difference being that it retains lifetime information. For this reason `normalize_erasing_regions` is the better choice in almost all circumstances as it is more efficient due to caching lifetime-erased queries.

This section outlines the process of normalizing types in Rust, highlighting various entry points to the underlying normalization logic and their specific use cases. It mentions the ongoing transition from the old to the new trait solver, which has led to changes in normalization approaches and the presence of 'old solver only' entry points. The entry points discussed include `infcx.at.structurally_normalize`, `infcx.at.(deeply_)?normalize`, `infcx.query_normalize`, `tcx.normalize_erasing_regions`, `traits::normalize_with_depth(_to)`, and `EvalCtxt::structurally_normalize`. The section emphasizes the use of `structurally_normalize` for inspecting type kinds and the distinction between `normalize` and `deeply_normalize` for deep normalization, with `normalize` being phased out in favor of `deeply_normalize` as the new solver stabilizes. It also covers the use of `infcx.query_normalize`, which retains lifetime information but is rarely used compared to `normalize_erasing_regions`.