Coherence with object types with overlapping supertrait projections is incomplete

[compiler-errors]

I tried this code:

trait Sup<T> {
    type Assoc;
}

impl<T> Sup<T> for () {
    type Assoc = T;
}
impl<T, U> Dyn<T, U> for () {}

trait Dyn<A, B>: Sup<A, Assoc = A> + Sup<B, Assoc = B> {}

trait Trait {
    type Assoc;
}
impl Trait for dyn Dyn<(), ()> {
    type Assoc = &'static str;
}
impl<A, B> Trait for dyn Dyn<A, B> {
    type Assoc = usize;
}

fn call<A, B>(x: usize) -> <dyn Dyn<A, B> as Trait>::Assoc {
    x
}

fn main() {
    let x: &'static str = call::<(), ()>(0xDEADBEEF);
    println!("{x}");
}

I expected to see this happen: It does not work.

Instead, this happened: Segfault

Meta

rustc --version --verbose:

rustc 1.85.0-nightly (a47555110 2024-11-22)

[compiler-errors]

The reason this fails is because we store object types as fully elaborated lists of projections, but deduplicate them after substitution when they come identical.

Think of dyn Dyn<(), ()> as [Sup<(), Assoc = ()>, Sup<(), Assoc = ()>] which gets deduplicated as [Sup<(), Assoc = ()>]
and dyn Dyn<A, B> which in coherence gets replaced with inference vars to [Sup<?A, Assoc = ?A>, Sup<?B, Assoc = ?B>].

We then check that these lists are the same length, and if they're not, we return a "type mismatch". In effect, we consider the types to be not equal, which also means that we consider two impls to not overlap.

[compiler-errors]

I'm actually somewhat afraid that a general solution to matching up the projections in various states of substitution and deduplication is impossible to solve; however, I think I have in mind a set of restrictions that we may be able to impose that is both not too restrictive but prevents this issue in general.

I'll noodle a bit on this... @rustbot claim

[lcnr]

marked as P-high for now https://rust-lang.zulipchat.com/#narrow/channel/245100-t-compiler.2Fwg-prioritization.2Falerts/topic/.23133361.20Coherence.20with.20object.20types.20with.20overlapping.20supert.E2.80.A6