Lazy normalization experimentation notes

notes.md

Lazy normalization in rustc

This is a collection of various things encountered when experminenting with lazy normalization in https://github.com/matthewjasper/rust/commits/lazy-normalization.

Ambiguity in where clauses

On master the two bounds on T are normalized and deduplicated. With lazy normalization the bounds are distinct, don't get deduplicated and cause ambiguity errors.

fn f<T>()
where
    T: FnOnce(()) + FnOnce(<Vec<()> as IntoIterator>::Item)
{}

Type outlives bounds and normalization

Given a where clause like: <<X as Y>::Z as A>::B: 'a we need to normalize this eagerly. Region checking runs too late to compare types with relate, and instead has to use "syntatic equality" (==). This means that we have to normalize this before region checking.

Coherence

Coherence currently checks for overlap by:

• Normalizing the impl headers
• Checking if relate returns OK
• Evaluating the obligations of both impls, and the obligations from relate one at a time

For lazy normalization this is problematic because we want at least the bounds from relate to be resolved to inform inference.

can_eq and can_sub

These are used a fair amount in error code. With lazy normalization there are two sensible ways to handle these:

• Only return true if relate has an empty list of obligations
  • This is a bit stricter than we might want, but there are some cases in diagnostics where we compare against (for example) every trait method in the currently loaded set of crates. This can result in us having to prove arbitrary predicates that from the user's point of view, come out of nowhere. This is problematic because proving auto traits on opaque types can cause query cycle errors.
• Evaluate/select all of the obligations.
  • This appears to work well enough in most cases.

Unnormalizing

Lazy normalization needs to be able to distinguish an associated type where we haven't tried to normalize, with one where we have, but could not find any bounds/impls to use.

Monomorphization wants to be able to try normalizing those types again, this gives us 2 options:

• "unnormalize" when setting types in MIR
• Make codegen try to normalize the "tried to normalize and failed" types (i.e. make normalize_erasing_regions somehow force such types to be normalized).

Opportunisticly resolving variables

On master resolve_vars_if_possible will leave type/const variables alone if they haven't been resolved to something other than a variable. To avoid hitting the recursion limit we need to have it resolve type/const variable to a minimal variable ID so that cycles can be detected.

Strange errors

The following code currently returns a rather strange (to a user) error:

trait A {}

impl A for <Vec<()> as IntoIterator>::Item {}

fn g<T: A>(t: T) {}

fn f() {
    g(1i32);
}

error[E0271]: type mismatch resolving `<std::vec::Vec<()> as std::iter::IntoIterator>::Item == i32`
  --> <source>:32:5
   |
29 | fn g<T: A>(t: T) {}
   |         - required by this bound in `g`
...
32 |     g(1i32);
   |     ^ expected `i32`, found `()`

We should maybe consider rejecting the impl as a candidate earlier so that the predicate in the error is i32: A, rather than the bound that we have.

Normalization in trait objects

We can sometimes get types like dyn Iterator<Item = (), Item = <Vec<()> as IntoIterator>::Item>, these need to be handled carefully when relating types.

Regressions

Normalizing more means that we sometimes report errors that we didn't previously.

Further investigations

• How does fn(()) == for<'a> fn(<&'a () as std::ops::Deref>::Target) affect name mangling?
• Lazy normalization for opaque types.
• How to make this something that can be landed in rustc?
• How does this affect the "const lazy norm" feature enabled by const_generics?