Skip to content

project for trait object bound candidates is incomplete #107887

@lcnr

Description

@lcnr

if let ProjectionCandidateSet::Single(ProjectionCandidate::Object(_)) = candidates {
// Avoid normalization cycle from selection (see
// `assemble_candidates_from_object_ty`).
// FIXME(lazy_normalization): Lazy normalization should save us from
// having to special case this.
} else {
assemble_candidates_from_impls(selcx, obligation, &mut candidates);
};

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 😁 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)`

Metadata

Metadata

Assignees

No one assigned

    Labels

    A-trait-systemArea: Trait systemC-bugCategory: This is a bug.I-unsoundIssue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/SoundnessP-mediumMedium priorityT-compilerRelevant to the compiler team, which will review and decide on the PR/issue.T-typesRelevant to the types team, which will review and decide on the PR/issue.WG-trait-system-refactorThe Rustc Trait System Refactor Initiative (-Znext-solver)fixed-by-next-solverFixed by the next-generation trait solver, `-Znext-solver`.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions