relating projection substs is unsound during coherence

[lcnr]

// This must fail coherence.
//
// Getting this to pass was fairly difficult, so here's an explanation
// of what's happening:
//
// Normalizing projections currently tries to replace them with inference variables
// while emitting a nested `Projection` obligation. This cannot be done if the projection
// has bound variables which is the case here.
//
// So the projections stay until after normalization. When unifying two projections we
// currently treat them as if they are injective, so we **incorrectly** unify their
// substs. This means that coherence for the two impls ends up unifying `?T` and `?U`
// as it tries to unify `<?T as WithAssoc1<'a>>::Assoc` with `<?U as WithAssoc1<'a>>::Assoc`.
//
// `impl1` therefore has the projection `<?T as WithAssoc2<'a>>::Assoc` and we have the
// assumption `?T: for<'a> WithAssoc2<'a, Assoc = i32>` in the `param_env`, so we normalize
// that to `i32`. We then try to unify `i32` from `impl1` with `u32` from `impl2` which fails,
// causing coherence to consider these two impls distinct.
pub trait Trait<T> {}

pub trait WithAssoc1<'a> {
    type Assoc;
}
pub trait WithAssoc2<'a> {
    type Assoc;
}

// impl 1
impl<T, U> Trait<for<'a> fn(<T as WithAssoc1<'a>>::Assoc, <U as WithAssoc2<'a>>::Assoc)> for (T, U)
where
    T: for<'a> WithAssoc1<'a> + for<'a> WithAssoc2<'a, Assoc = i32>,
    U: for<'a> WithAssoc2<'a>,
{
}

// impl 2
impl<T, U> Trait<for<'a> fn(<U as WithAssoc1<'a>>::Assoc, u32)> for (T, U) where
    U: for<'a> WithAssoc1<'a>
{
}

this currently compiles even though the following crate would mean that both impls overlap:

extern crate test1;
use test1::*;

struct Ty1;
struct Ty2;

impl WithAssoc1<'_> for Ty1 {
    type Assoc = ();
}
impl WithAssoc2<'_> for Ty1 {
    type Assoc = i32;
}
impl WithAssoc1<'_> for Ty2 {
    type Assoc = ();
}
impl WithAssoc2<'_> for Ty2 {
    type Assoc = u32;
}

fn foo<T, U>()
where
    (T, U): Trait<for<'a> fn((), u32)>,
{
}

fn main() {
    foo::<Ty1, Ty2>();
}

however, it seems like rustc generally has issues with both of these impls, so it actually believes that none of these impls apply 😁 see also #102047 where the first impl results in an ICE.

[lcnr]

cc @rust-lang/types

[BoxyUwU]

#96912 fixes this but it'll be a while before it can be merged

[apiraino]

WG-prioritization assigning priority (Zulip discussion).

@rustbot label -I-prioritize +P-medium

[lcnr]

This is also wrong if only region arguments differ:

trait Trait<T> {}

trait WithAssoc<'a> {
    type Assoc;
}

impl<T: for<'a> WithAssoc<'a>> Trait<T> for for<'a> fn(<T as WithAssoc<'a>>::Assoc) {}

impl<'a, T: WithAssoc<'a>> Trait<T> for fn(<T as WithAssoc<'a>>::Assoc) {}