`uncertain`: local projection cache strenghens inference

[lcnr]

https://crater-reports.s3.amazonaws.com/pr-133502-13/try%233cddd79d4be3c8f1e937d09ca618d192abc69373/reg/uncertain-0.3.1/log.txt

trait Trait {
    type Assoc;
}

struct W<T>(T);
impl<T: Trait> Trait for W<T> {
    type Assoc = T::Assoc;
}

impl Trait for () {
    type Assoc = f32;
}


fn foo<T: Trait>(arg: T, x: T::Assoc) -> T::Assoc {
    x
}

fn main() {
    let w = W(Default::default());
    foo(w, 1f32).abs();
    let _: W<()> = w;
}

we store <W<_> as Trait>::Assoc => ?unconstrained in the projection cache and reuse ?unconstrained for both the input and output. We only do so as normalizing <W<_> as Trait>::Assoc actually made some progress

[compiler-errors]

probably unsound according to lcnr (edit: lcnr) as the evaluation cache can rely on this, e.g. a candidate W<<W<_> as Trait>::Assoc>: Bound<?unconstrained> can differ from W<<W<_> as Trait>::Assoc>: Bound<?unrelated> without this getting tracked by the cache

[lcnr]

A more in-depth explanation:

We don't add anything to the projection cache if normalization itself is ambiguous: https://github.com/rust-lang/rust/blob/95a2212587f1b8500af1ac630322b0cb2e030c61/compiler/rustc_trait_selection/src/traits/project.rs#L421

However, if we're able to project to an impl item, we do add the resulting type to the cache, even if its normalization is still ambiguous: https://github.com/rust-lang/rust/blob/95a2212587f1b8500af1ac630322b0cb2e030c61/compiler/rustc_trait_selection/src/traits/project.rs#L389-L407

---

Proving Projection(<?x as Trait>::Assoc, ?y) fails with TooManyCandidates/ambiguous, so it results in ProjectionCacheEntry::Ambiguous. This cache entry does not refer to ?y. If we then later prove Projection(<?x as Trait>::Assoc, ?z), we use the cache entry and ?y and ?z remain unconstrained.

Proving Projection(<W<?x> as Trait>::Assoc, ?y) normalizes to <?x as Trait>::Assoc. We then project that to <?x as Trait>::Assoc. This resulting type then gets normalized and we write Normalized { value: Ty(?y), obligations: [Projection(<?x as Trait>::Assoc, ?y)] } into the cache. Accessing this cache entry when proving Projection(<W<?x> as Trait>::Assoc, ?z) then equates ?y and ?z.

---

Caching in the new solver uses canonicalization, so reusing that entry for ?z does not reuse ?y. I think that supporting this is generally desirable but difficult to do properly. Given that this pattern is very rare (for now [uncertain] is the only known regression), I would simply break this instead of trying to add/keep some sort of local normalization cache around.

[lcnr]

The new solver still has something like this due to the cache in generalization. If we encounter an alias twice during the same generalization, we may also end up normalizing it to the same inference variable:

trait Trait {
    type Assoc;
}

struct W<T>(T);
impl<T: Trait> Trait for W<T> {
    type Assoc = T::Assoc;
}

impl Trait for () {
    type Assoc = f32;
}


fn foo<T: Trait>(arg: T) -> (T::Assoc, T::Assoc) {
    todo!();
}

fn main() {
    let w = W(Default::default());
    let mut x = foo(w);
    x.1 = 1f32;
    x.0.abs();
    let _: W<()> = w;
}