`project` for trait object bound candidates is incomplete

[lcnr]

https://github.com/rust-lang/rust/blob/9b8dbd558c1c4b25c55d987e22baba312ae980ad/compiler/rustc_trait_selection/src/traits/project.rs#L1255-L1262

This ignores impl candidates even if the builtin object candidate guides inference, which is incomplete. Incompleteness during coherence is unsound, outside of coherence it can merely result in bad and confusing errors.

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

impl Trait<u32> for u32 {
    type Assoc = u32;
}

// This would trigger the check for overlap between automatic and custom impl.
// They actually don't overlap so an impl like this should remain possible
// forever.
//
// impl Trait<u64> for dyn Trait<u32, Assoc = u32> {
//     type Assoc =  dyn Trait<u32, Assoc = u32>;
// }
trait Indirect<T: ?Sized> {}
impl Indirect<dyn Trait<u32, Assoc = u32>> for () {}
impl<T: ?Sized> Trait<u64> for T
where
    (): Indirect<T>,
{
    type Assoc = u32;
}

trait Overlap<U> {}

impl<U> Overlap<U> for <dyn Trait<u32, Assoc = u32> as Trait<U>>::Assoc where
    dyn Trait<u32, Assoc = u32>: Trait<U>
{
}

impl Overlap<u64> for u32 {}

fn main() {}

currently results in

error[E0277]: the trait bound `<(dyn Trait<u32, Assoc = u32> + 'static) as Trait<U>>::Assoc: Overlap<U>` is not satisfied
  --> src/main.rs:26:24
   |
26 | impl<U> Overlap<U> for <dyn Trait<u32, Assoc = u32> as Trait<U>>::Assoc
   |                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `Overlap<U>` is not implemented for `<(dyn Trait<u32, Assoc = u32> + 'static) as Trait<U>>::Assoc`
   |
help: consider further restricting the associated type
   |
28 | dyn Trait<u32, Assoc = u32>: Trait<U>, <(dyn Trait<u32, Assoc = u32> + 'static) as Trait<U>>::Assoc: Overlap<U>
   |                                      ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

which is also buggy :grin: adding that bound to the impl makes it compile but now they actually don't overlap because using the first impl would result in an inductive cycle. In the future all traits will be coinductive at which point this would be unsound. But as that will only happen in the new solver, we're safe.

It does however guide inference in incorrect ways, causing an additional - hopefully merely theoretical - breaking change with the new solver:

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

impl Trait<u32> for u32 {
    type Assoc = u16;
}

// This would trigger the check for overlap between automatic and custom impl
// They actually don't overlap so an impl like this should remain possible
// forever.
//
// impl Trait<u64> for dyn Trait<u32, Assoc = u32> {
//     type Assoc =  dyn Trait<u32, Assoc = u32>;
// }
trait Indirect<T: ?Sized> {}
impl Indirect<dyn Trait<u32, Assoc = u32>> for () {}
impl<T: ?Sized> Trait<u64> for T
where
    (): Indirect<T>,
{
    type Assoc = dyn Trait<u32, Assoc = u32>;
}

fn yay<T: Trait<U> + ?Sized, U>(x: &'static T) -> &'static <T as Trait<U>>::Assoc {
    todo!();
}

fn unconstrained<T>() -> T {
    todo!()
}

fn should_be_ambig() {
    let y: &'static dyn Trait<u32, Assoc = u32> = unconstrained();
    let _ = yay::<dyn Trait<u32, Assoc = u32>, _>(y);
    // The current solver incorrectly constrains `_` to `u32` here.
}

fn main() {
    let y: &'static dyn Trait<u32, Assoc = u32> = unconstrained();
    // let mut x = yay::<_, u64>(y); // compiles
    let mut x = yay::<_, _>(y); // errors
    x = y;
}

incorrect inference results in the following error in main:

error[E0308]: mismatched types
  --> src/main.rs:43:9
   |
42 |     let mut x = yay::<_, _>(y); // errors
   |                 -------------- expected due to this value
43 |     x = y;
   |         ^ expected `&u32`, found `&dyn Trait<u32, Assoc = u32>`
   |
   = note: expected reference `&u32`
              found reference `&'static (dyn Trait<u32, Assoc = u32> + 'static)`

[lcnr]

Tracked in https://github.com/rust-lang/trait-system-refactor-initiative/issues/101 instead

[lcnr]

it actually is possible to get overlapping impls from this. The following results in an ICE:

struct W<T: ?Sized>(*const T);

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

// This would trigger the check for overlap between automatic and custom impl.
// They actually don't overlap so an impl like this should remain possible
// forever.
//
// impl Trait<u64> for dyn Trait<u32> {}
trait Indirect {}
impl Indirect for dyn Trait<u32, Assoc = ()> {}
impl<T: Indirect + ?Sized> Trait<u64> for T {
    type Assoc = ();
}

trait Overlap<U: ?Sized> {
    type Assoc: Default;
}
impl<T: ?Sized + EvaluateHack<W<U>>, U: ?Sized> Overlap<U> for T {
    type Assoc = Box<u32>;
}
impl<U: ?Sized> Overlap<U> for dyn Trait<u32, Assoc = ()> {
    type Assoc = usize;
}

// Incomplete impl where `dyn Trait<u32>: Trait<_>` does not hold, but
// `dyn Trait<u32>: Trait<u64>` does.
trait EvaluateHack<U: ?Sized> {}
impl<T: ?Sized, U: ?Sized> EvaluateHack<W<U>> for T
where
    T: Trait<U, Assoc = ()>, // incompletely constrains `_` to `u32`
    U: IsU64,
    T: Trait<U, Assoc = ()>, // incompletely constrains `_` to `u32`
{
}

trait IsU64 {}
impl IsU64 for u64 {}

fn overlap<T: Overlap<U> + ?Sized, U>() -> T::Assoc {
    Default::default()
}

fn generic_first<T: ?Sized + EvaluateHack<W<U>>, U>() {
    overlap::<T, U>();
}
fn main() {
    generic_first::<dyn Trait<u32, Assoc = ()>, u64>();
}

[lcnr]

marked as P-medium https://rust-lang.zulipchat.com/#narrow/stream/245100-t-compiler.2Fwg-prioritization.2Falerts/topic/.23107887.20.60project.60.20for.20trait.20object.20bound.20candidates.20is.20inco.E2.80.A6