alias-relate is theoretically incomplete

[lcnr]

the following test nearly triggers an incompleteness of alias-relate, which would result in overlapping impls getting accepted:

struct W<T: ?Sized>(*const T);
trait Bound<T: ?Sized> {}
impl Bound<W<u8>> for u8 {}
impl Bound<W<u16>> for u16 {} 

trait Constrain<T: ?Sized> {
    type Assoc: ?Sized;
}

impl<T: ?Sized> Constrain<W<T>> for u8
where
    u8: Bound<W<T>>,
{
    type Assoc = u8;
}

trait ToId {
    type Assoc: ?Sized;
}
impl<T: ?Sized> ToId for T {
    type Assoc = <T as Id>::This;
}
trait Id {
    type This: ?Sized;
}
impl<T: ?Sized> Id for T {
    type This = T;
}

trait Overlap<T> {}

impl<T: ?Sized> Overlap<<T as ToId>::Assoc> for T {}
impl<T: ?Sized> Overlap<<u8 as Constrain<W<T>>>::Assoc> for T {}

The idea is as follows: we prove AliasRelate(<?t as ToId>::Assoc, <u8 as Constrain<W<?t>>>::Assoc) during coherence. This does the following:

• structurally normalize lhs to ?lhs with NormalizesTo(<?t as ToId>::Assoc, ?lhs)
• structurally normalize rhs to u8, constraining ?t to u8.

At this point, evaluating the goals added by trying to structurally normalize <?t as ToId>::Assoc constrains ?lhs to <u8 as Id>::This, which is not a rigid alias. If we were to first evaluate added goals here and then structurally equate, this would result in an error, allowing these two impls to coexist even though they clearly overlap. Alternatively, changing commit_if_ok to inherit the nested goals of the parent would also enable this unsoundness. The underlying issue is that after structurally normalizing the lhs, we do not check whether it results in a normalizeable alias when considering the constraints from structurally normalizing the rhs.

We currently instead reach the following branch, first constraining ?lhs to u8 and then proving NormalizesTo(<u8 as ToId>::Assoc, u8). This uses semantic equality when relating u8 with <u8 as Id>::This, which succeeds. https://github.com/rust-lang/rust/blob/a0569fa8f91b5271e92d2f73fd252de7d3d05b9c/compiler/rustc_trait_selection/src/solve/alias_relate.rs#L56-L57

I feel like it is likely this issue can be theoretically exploited. I am also confident that this cannot be hit by accident and is fairly straightforward to fix by changing NormalizesTo to recursively normalize the projected term. It currently only normalizes by one-step and requires AliasRelate to recursively normalize. This would change NormalizesTo from normalizing exactly one-step to normalizingh at least one step. It would therefore require using commit_if_ok in both AliasRelate and at the end of NormalizesTo.

[lcnr]

we should add this as a regression test 😅

[lcnr]

nm, move this to dev-guide or sth 🤔 🤷