old solver incompletely prefers projection and object candidates

[lcnr]

the following example compiles in the old solver and errors in the new solver. This happens because the old solver makes an arbitrary choice here https://github.com/rust-lang/rust/blob/617d3d6d722c432cdcbf210e6db55c3bdeafe381/compiler/rustc_trait_selection/src/traits/select/mod.rs#L1967-L1972

trait Trait<'t> {}
impl<'t> Trait<'t> for () {}

fn foo<'x, 'y>() -> impl Trait<'x> + Trait<'y> {}

fn impls_trait<'x, T: Trait<'x>>(_: T) {}

fn bar<'x, 'y>() {
    impls_trait::<'y, _>(foo::<'_, '_>());
}

fn main() {}

changing this example a bit we get a MIR typeck ICE with the new solver

trait Trait<'t> {}
impl<'t> Trait<'t> for () {}

fn foo<'x, 'y>() -> impl Trait<'x> + Trait<'y> {}

fn impls_trait<'x, T: Trait<'x>>(_: T) {}

fn bar<'x, 'y>() {
    impls_trait::<'y, _>(foo::<'x, 'y>());
}

fn main() {}

error: internal compiler error: errors selecting obligation during MIR typeck: [FulfillmentError(Obligation(predicate=Binder(TraitPredicate(<Opaque(DefId(0:17 ~ main[db48]::foo::{opaque#0}), ['?16, '?17, '?18, '?19]) as Trait<ReFree(DefId(0:13 ~ main[db48]::bar), BrNamed(DefId(0:15 ~ main[db48]::bar::'y), 'y))>>, polarity:Positive), []), cause=ObligationCause { span: src/main.rs:6:23: 6:32 (#0), body_id: DefId(0:0 ~ main[db48]), code: AscribeUserTypeProvePredicate(src/main.rs:6:23: 6:32 (#0)) }, param_env=ParamEnv { caller_bounds: [], reveal: UserFacing, constness: NotConst }, depth=0),Ambiguity), FulfillmentError(Obligation(predicate=Binder(WellFormed(fn(?0t) {impls_trait::<ReFree(DefId(0:13 ~ main[db48]::bar), BrNamed(DefId(0:15 ~ main[db48]::bar::'y), 'y)), ?0t>}), []), cause=ObligationCause { span: no-location (#0), body_id: DefId(0:0 ~ main[db48]), code: MiscObligation }, param_env=ParamEnv { caller_bounds: [], reveal: UserFacing, constness: NotConst }, depth=0),Ambiguity)]

This feels like it may be caused by the theoretical issue discussed in https://rust-lang.zulipchat.com/#narrow/stream/364551-t-types.2Ftrait-system-refactor/topic/mir.20typeck.20and.20relying.20on.20region.20equality

[lcnr]

the same using projection candidates
ambig in new solver:

trait Trait<'t> {}
impl<'t> Trait<'t> for () {}

trait Proj<'x, 'y> {
    type Assoc: Trait<'x> + Trait<'y>;
}

fn foo<'x, 'y, T: Proj<'x, 'y>>() -> T::Assoc { todo!() }

fn impls_trait<'x, T: Trait<'x>>(_: T) {}

fn bar<'x, 'y, T: Proj<'x, 'y>>() {
    impls_trait::<'y, _>(foo::<'_, '_, T>());
}

fn main() {}

ICE in new solver

trait Trait<'t> {}
impl<'t> Trait<'t> for () {}

trait Proj<'x, 'y> {
    type Assoc: Trait<'x> + Trait<'y>;
}

fn foo<'x, 'y, T: Proj<'x, 'y>>() -> T::Assoc { todo!() }

fn impls_trait<'x, T: Trait<'x>>(_: T) {}

fn bar<'x, 'y, T: Proj<'x, 'y>>() {
    impls_trait::<'y, _>(foo::<'x, 'y, T>());
}

fn main() {}

[lcnr]

and using object bounds

ambig

trait Trait<'t> {}
impl<'t> Trait<'t> for () {}

trait Object<'x, 'y>: Trait<'x> + Trait<'y> {}

fn foo<'x, 'y>() -> Box<dyn Object<'x, 'y>> { todo!() }

fn impls_trait<'x, T: Trait<'x> + ?Sized>(_: Box<T>) {}

fn bar<'x, 'y>() {
    impls_trait::<'y, _>(foo::<'_, '_>());
}

fn main() {}

mir ICE:

trait Trait<'t> {}
impl<'t> Trait<'t> for () {}

trait Object<'x, 'y>: Trait<'x> + Trait<'y> {}

fn foo<'x, 'y>() -> Box<dyn Object<'x, 'y>> { todo!() }

fn impls_trait<'x, T: Trait<'x> + ?Sized>(_: Box<T>) {}

fn bar<'x, 'y>() {
    impls_trait::<'y, _>(foo::<'x, 'y>());
}

fn main() {}

[lcnr]

this issue may be fixed by supporting OR bounds in query outputs instead. This means we'd rely on no region based incompleteness existing