nightly: Trait resolution picks the wrong trait impl with higher ranked bounds

[konnorandrews]

Code

I tried this code:

fn main() {
    
}

type Bound<'lt, 'ctx> = &'lt &'ctx ();

trait Raise{
    type Higher<'lt, 'ctx, B>: for<'a, 'b> Lower<'a, 'b, Bound<'a, 'b>> + Lower<'lt, 'ctx, B, T = Self>;
}

trait Lower<'lt, 'ctx, B> {
    type T: Raise<Higher<'lt, 'ctx, B> = Self>;
}

fn use_lower<'a, 'ctx: 'a, T: Raise>(x: T) {
    use_higher::<<T as Raise>::Higher::<'a, 'ctx, Bound<'a, 'ctx>>>(x);
}

fn use_higher<'a, 'ctx, H: for<'b, 'c> Lower<'b, 'c, Bound<'b, 'c>>>(x: <H as Lower<'a, 'ctx, Bound<'a, 'ctx>>>::T) {
    use_lower(x)
}

type T<'lt, 'ctx, __> = <__ as Lower<'lt, 'ctx, Bound<'lt, 'ctx>>>::T;
type HigherRanked<'lt, 'ctx, __> = <__ as Raise>::Higher::<'lt, 'ctx, Bound<'lt, 'ctx>>;

fn is_bijective_raise<'a, 'ctx: 'a, U>(
    x: &T<'a, 'ctx, HigherRanked<'a, 'ctx, U>>,
) where
    U: Raise,
{
    let _y: &U = x;
}

fn is_bijective_lower<'a, 'ctx: 'a, U>(
    x: &HigherRanked<'a, 'ctx, T<'a, 'ctx, U>>,
) where
    U: Lower<'a, 'ctx, Bound<'a, 'ctx>>,
{
    let _y: &U = x;
}

I expected to see this happen: For it to compile (based on rustc previously accepting this code)
I am not 100% sure this code is supposed to be allowed.

Instead, this happened: A compiler error

error: lifetime may not live long enough
  --> src/main.rs:16:5
   |
15 | fn use_lower<'a, 'ctx: 'a, T: Raise>(x: T) {
   |              -- lifetime `'a` defined here
16 |     use_higher::<<T as Raise>::Higher::<'a, 'ctx, Bound<'a, 'ctx>>>(x);
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ requires that `'a` must outlive `'static`
   |
note: due to current limitations in the borrow checker, this implies a `'static` lifetime
  --> src/main.rs:19:28
   |
19 | fn use_higher<'a, 'ctx, H: for<'b, 'c> Lower<'b, 'c, Bound<'b, 'c>>>(x: <H as Lower<'a, 'ctx, Bound<'a, 'ctx>>>:...
   |                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error: lifetime may not live long enough
  --> src/main.rs:16:5
   |
15 | fn use_lower<'a, 'ctx: 'a, T: Raise>(x: T) {
   |                  ---- lifetime `'ctx` defined here
16 |     use_higher::<<T as Raise>::Higher::<'a, 'ctx, Bound<'a, 'ctx>>>(x);
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ requires that `'ctx` must outlive `'static`
   |
note: due to current limitations in the borrow checker, this implies a `'static` lifetime
  --> src/main.rs:19:28
   |
19 | fn use_higher<'a, 'ctx, H: for<'b, 'c> Lower<'b, 'c, Bound<'b, 'c>>>(x: <H as Lower<'a, 'ctx, Bound<'a, 'ctx>>>:...
   |                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error: implementation of `Lower` is not general enough
  --> src/main.rs:16:5
   |
16 |     use_higher::<<T as Raise>::Higher::<'a, 'ctx, Bound<'a, 'ctx>>>(x);
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ implementation of `Lower` is not general enough
   |
   = note: `<T as Raise>::Higher<'2, '_, &'2 &()>` must implement `Lower<'1, 'c, &'1 &'c ()>`, for any lifetime `'1`...
   = note: ...but it actually implements `Lower<'2, '_, &'2 &()>`, for some specific lifetime `'2`

error: implementation of `Lower` is not general enough
  --> src/main.rs:16:5
   |
16 |     use_higher::<<T as Raise>::Higher::<'a, 'ctx, Bound<'a, 'ctx>>>(x);
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ implementation of `Lower` is not general enough
   |
   = note: `<T as Raise>::Higher<'_, '2, &&'2 ()>` must implement `Lower<'b, '1, &'b &'1 ()>`, for any lifetime `'1`...
   = note: ...but it actually implements `Lower<'_, '2, &&'2 ()>`, for some specific lifetime `'2`

help: the following changes may resolve your lifetime errors
  |
  = help: replace `'a` with `'static`
  = help: replace `'ctx` with `'static`

error: could not compile `rustc_bisect_sandbox` (bin "rustc_bisect_sandbox") due to 4 previous errors

Version it worked on

It most recently worked on: Rust 1.78.0

Version with regression

Rust 1.79.0 and later. Bisected to commit 43f4f2a

@rustbot modify labels: +regression-from-stable-to-beta -regression-untriaged

[konnorandrews]

I just discovered that swapping the bounds on the Raise::Higher causes it to work again on 1.79.0 and later.

(not working)

trait Raise{
    type Higher<'lt, 'ctx, B>: for<'a, 'b> Lower<'a, 'b, Bound<'a, 'b>> + Lower<'lt, 'ctx, B, T = Self>;
}

(working)

trait Raise{
    type Higher<'lt, 'ctx, B>: Lower<'lt, 'ctx, B, T = Self> + for<'a, 'b> Lower<'a, 'b, Bound<'a, 'b>>;
}

[konnorandrews]

I have simplified the code to this

fn main() {}

trait Raise{
    type Higher<'lt>: for<'a> Lower<'a> + Lower<'lt, T = Self>;
}

trait Lower<'lt> {
    type T: Raise<Higher<'lt> = Self>;
}

fn use_lower<'a, T: Raise>(x: T) {
    use_higher::<<T as Raise>::Higher::<'a>>(x);
}

fn use_higher<'a, H: for<'b> Lower<'b>>(x: <H as Lower<'a>>::T) {}

As before switching it with

 type Higher<'lt>: Lower<'lt, T = Self> + for<'a> Lower<'a>;

works

[fmease]

cc @lcnr

[lcnr]

has already been reverted on beta in #125629.

[lcnr]

the unstable result depending on whether the associated type bounds are swapped is caused by

rust/compiler/rustc_trait_selection/src/traits/select/mod.rs

Lines 1965 to 1970 in a330e49

	(ProjectionCandidate(i), ProjectionCandidate(j))
	| (ObjectCandidate(i), ObjectCandidate(j)) => {
	// Arbitrarily pick the lower numbered candidate for backwards
	// compatibility reasons. Don't let this affect inference.
	DropVictim::drop_if(i < j && !has_non_region_infer)
	}

before #119820 we already discarded the non-hr item bounds - ProjectionCandidate - before using fn candidate_should_be_dropped_in_favor_of, causing us to always use the hr one, regardless of order.

[konnorandrews]

Here is a smaller example that doesn't use GATs.

pub trait ForLt<'a> {
    type T;
}

pub trait Hrt: for<'a> ForLt<'a> {}

pub trait Other<'a> {
    type Higher: Hrt + ForLt<'a>;
}

error: implementation of `ForLt` is not general enough
  --> src/main.rs:10:18
   |
7  | pub trait Hrt: for<'a> ForLt<'a> {}
   | --------------------------------
   | |              |
   | |              doesn't satisfy where-clause
   | due to a where-clause on `Hrt`...
...
10 |     type Higher: Hrt + ForLt<'a>;
   |                  ^^^
   |
   = note: ...`<Self as Other<'a>>::Higher` must implement `ForLt<'0>`, for any lifetime `'0`...
   = note: ...but it actually implements `ForLt<'a>`

(A more meaningful example is to use type Higher: Hrt + ForLt<'a, T = i32>;. As this actually adds a extra bound instead of it being a duplicate bound.)

Is the type Higher: ForLt<'a> + Hrt; supposed to be allowed? I do use the stable behavior in some code and am wondering if I need to change to some other method to achieve this.

[apiraino]

Same as #125194 . Changes in #119820 were reverted so in theory this regression should be neutralized in the current nightly. Can you check @konnorandrews ? thanks

[lcnr]

I only reverted it on beta, it still affects nightly (and the new beta)

[lcnr]

THis has since been fully reverted, closing as fixed. We already have added tests for this.