Ordering of bounds matters with GAT/HRTB

[aliemjay]

I tried this code:

(playground)

#![feature(generic_associated_types)]
use std::marker::PhantomData as PhD;

pub trait Universe: 'static {
    type Ty<'a>;
}

impl Universe for &'static u8 {
    type Ty<'a> = &'a u8;
}

trait Service<Req> {}

struct BadCombinator<ReqU, S>(PhD<ReqU>, S);

impl<'c, ReqU, S> Service<ReqU::Ty<'c>> for BadCombinator<ReqU, S>
where
    ReqU: Universe,
    S: for<'a> Service<ReqU::Ty<'a>>,
    S: Service<ReqU>, // swapping the last two bounds works!
{
}

fn test(svc: impl for<'a> Service<&'a u8>) {
    fn assert_good(_: impl for<'a> Service<&'a u8>) {}

   // assert_good(BadCombinator(PhD::<&u8>, svc)); //<- works
    assert_good(BadCombinator(PhD, svc));
}

I expected to see this happen: program either compiles or requires type annotation for ReqU.

Instead, this happened: The program fails with a message unrelated to type inference. While reording the bounds as noted or annotating for ReqU makes it compile.

The error message looks pretty confusing as it seems that the compiler was able to infer ReqU!

Error Output

error[[E0277]](https://doc.rust-lang.org/nightly/error-index.html#E0277): the trait bound `for<'a> impl for<'a> Service<&'a u8>: Service<<&u8 as Universe>::Ty<'a>>` is not satisfied
  [--> src/lib.rs:28:17
](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=7d6db0f5036d46fc55706aed2d6eb64c#)   |
28 |     assert_good(BadCombinator(PhD, svc));
   |     ----------- ^^^^^^^^^^^^^^^^^^^^^^^ the trait `for<'a> Service<<&u8 as Universe>::Ty<'a>>` is not implemented for `impl for<'a> Service<&'a u8>`
   |     |
   |     required by a bound introduced by this call
   |
note: required because of the requirements on the impl of `for<'a> Service<&'a u8>` for `BadCombinator<&u8, impl for<'a> Service<&'a u8>>`
  [--> src/lib.rs:16:19
](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=7d6db0f5036d46fc55706aed2d6eb64c#)   |
16 | impl<'c, ReqU, S> Service<ReqU::Ty<'c>> for BadCombinator<ReqU, S>
   |                   ^^^^^^^^^^^^^^^^^^^^^     ^^^^^^^^^^^^^^^^^^^^^^
note: required by a bound in `assert_good`
  [--> src/lib.rs:25:28
](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=7d6db0f5036d46fc55706aed2d6eb64c#)   |
25 |     fn assert_good(_: impl for<'a> Service<&'a u8>) {}
   |                            ^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `assert_good`
help: consider further restricting this bound
   |
24 | pub fn test(svc: impl for<'a> Service<&'a u8> + for<'a> Service<<&u8 as Universe>::Ty<'a>>) {
   |                                               ++++++++++++++++++++++++++++++++++++++++++++

For more information about this error, try `rustc --explain E0277`.
error: could not compile `playground` due to previous error

Meta

Reproduced on nightly versions back to 2020-05-01

Current nightly:

1.62.0-nightly (2022-04-21 de1bc0008be096cf7ed6)

@rustbot label F-generic_associated_types A-inference T-compiler

[aliemjay]

It looks similar to #90875. I noticed while working on the same problem domain. Error messages are similar and both are fixed by type annotation. However for the latter, ordering of bounds doesn't fix the problem.

[aliemjay]

Can be produced without GAT by changing Universe to :

pub trait Universe<'a>: 'static {
    type Ty;
}

(playground)

@rustbot label -F-generic_associated_types +A-lifetimes +A-traits

[aliemjay]

Prior to #90887, It always fails regardless of the the ordering.

cc PR author @jackh726 and reviewer @compiler-errors. Is this an expected behaviour?