src/doc/rustc-dev-guide/src/solve/normalization.md

   1 # Normalization in the new solver
   2
   3 With the new solver we've made some fairly significant changes to normalization when compared
   4 to the existing implementation.
   5
   6 We now differentiate between "shallow normalization" and "deep normalization".
   7 "Shallow normalization" normalizes a type until it is no-longer a potentially normalizeable alias;
   8 it does not recurse into the type. "deep normalization" replaces all normalizeable aliases in a
   9 type with its underlying type.
  10
  11 The old trait solver currently always deeply normalizes via `Projection` obligations.
  12 This is the only way to normalize in the old solver. By replacing projections with a new
  13 inference variable and then emitting `Projection(<T as Trait>::Assoc, ?new_infer)` the old
  14 solver successfully deeply normalizes even in the case of ambiguity. This approach does not
  15 work for projections referencing bound variables.
  16
  17 ## Inside of the trait solver
  18
  19 Normalization in the new solver exclusively happens via `Projection`[^0] goals.
  20 This only succeeds by first normalizing the alias by one level and then equating
  21 it with the expected type. This differs from [the behavior of projection clauses]
  22 which can also be proven by successfully equating the projection without normalizating.
  23 This means that `Projection`[^0] goals must only be used in places where we
  24 *have to normalize* to make progress. To normalize `<T as Trait>::Assoc`, we first create
  25 a fresh inference variable `?normalized` and then prove
  26 `Projection(<T as Trait>::Assoc, ?normalized)`[^0]. `?normalized` is then constrained to
  27 the underlying type.
  28
  29 Inside of the trait solver we never deeply normalize. we only apply shallow normalization
  30 in [`assemble_candidates_after_normalizing_self_ty`] and inside for [`AliasRelate`]
  31 goals for the [`normalizes-to` candidates].
  32
  33 ## Outside of the trait solver
  34
  35 The core type system - relating types and trait solving - will not need deep
  36 normalization with the new solver. There are still some areas which depend on it.
  37 For these areas there is the function `At::deeply_normalize`. Without additional
  38 trait solver support deep normalization does not always work in case of ambiguity.
  39 Luckily deep normalization is currently only necessary in places where there is no ambiguity.
  40 `At::deeply_normalize` immediately fails if there's ambiguity.
  41
  42 If we only care about the outermost layer of types, we instead use
  43 `At::structurally_normalize` or `FnCtxt::(try_)structurally_resolve_type`.
  44 Unlike `At::deeply_normalize`, shallow normalization is also used in cases where we
  45 have to handle ambiguity. `At::structurally_normalize` normalizes until the self type
  46 is either rigid or an inference variable and we're stuck with ambiguity. This means
  47 that the self type may not be fully normalized after `At::structurally_normalize` was called.
  48
  49 Because this may result in behavior changes depending on how the trait solver handles
  50 ambiguity, it is safer to also require full normalization there. This happens in
  51 `FnCtxt::structurally_resolve_type` which always emits a hard error if the self type ends
  52 up as an inference variable. There are some existing places which have a fallback for
  53 inference variables instead. These places use `try_structurally_resolve_type` instead.
  54
  55 ## Why deep normalization with ambiguity is hard
  56
  57 Fully correct deep normalization is very challenging, especially with the new solver
  58 given that we do not want to deeply normalize inside of the solver. Mostly deeply normalizing
  59 but sometimes failing to do so is bound to cause very hard to minimize and understand bugs.
  60 If possible, avoiding any reliance on deep normalization entirely therefore feels preferable.
  61
  62 If the solver itself does not deeply normalize, any inference constraints returned by the
  63 solver would require normalization. Handling this correctly is ugly. This also means that
  64 we change goals we provide to the trait solver by "normalizing away" some projections.
  65
  66 The way we (mostly) guarantee deep normalization with the old solver is by eagerly replacing
  67 the projection with an inference variable and emitting a nested `Projection` goal. This works
  68 as `Projection` goals in the old solver deeply normalize. Unless we add another `PredicateKind`
  69 for deep normalization to the new solver we cannot emulate this behavior. This does not work
  70 for projections with bound variables, sometimes leaving them unnormalized. An approach which
  71 also supports projections with bound variables will be even more involved.
  72
  73
  74 [`assemble_candidates_after_normalizing_self_ty`]: https://github.com/rust-lang/rust/blob/1b6d4cdc4d923c148198ad4df230af48cdaca59e/compiler/rustc_trait_selection/src/solve/assembly/mod.rs#L330-L378
  75 [`AliasRelate`]: https://github.com/rust-lang/rust/blob/1b6d4cdc4d923c148198ad4df230af48cdaca59e/compiler/rustc_trait_selection/src/solve/alias_relate.rs#L16-L102
  76 [`normalizes-to` candidates]: https://github.com/rust-lang/rust/blob/1b6d4cdc4d923c148198ad4df230af48cdaca59e/compiler/rustc_trait_selection/src/solve/alias_relate.rs#L105-L151
  77 [the behavior of projection clauses]: https://github.com/rust-lang/trait-system-refactor-initiative/issues/1
  78 [normalize-via-infer]: https://github.com/rust-lang/rust/blob/1b6d4cdc4d923c148198ad4df230af48cdaca59e/compiler/rustc_trait_selection/src/solve/assembly/mod.rs#L350-L358
  79
  80 [^0]: TODO: currently refactoring this to use `NormalizesTo` predicates instead.