Failed to unify types when using GATs and HRTBs

[reinerp]

I believe the following code should typecheck under nightly (https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=f3d45f199cadea62341a727f66c52d86):

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

struct Id<'id>(PhantomData<fn(&'id ()) -> &'id ()>);

fn new_id() -> Id<'static> {
    Id(PhantomData)
}

pub trait HasLifetime where {
    type AtLifetime<'a>;
}

pub struct ExistentialLifetime<S: HasLifetime>(S::AtLifetime<'static>);

impl<S: HasLifetime> ExistentialLifetime<S> {
    pub fn new<F>(f: F) -> ExistentialLifetime<S>
        where for<'id> F: FnOnce(Id<'id>) -> S::AtLifetime<'id> {
        ExistentialLifetime(f(new_id()))
    }
}


struct ExampleS<'id>(Id<'id>);

struct ExampleMarker;

impl HasLifetime for ExampleMarker {
    type AtLifetime<'id> = ExampleS<'id>;
}


fn broken0() -> ExistentialLifetime<ExampleMarker> {
    fn new_helper<'id>(id: Id<'id>) -> ExampleS<'id> {
        ExampleS(id)
    }

    ExistentialLifetime::<ExampleMarker>::new(new_helper)
}

fn broken1() -> ExistentialLifetime<ExampleMarker> {
    fn new_helper<'id>(id: Id<'id>) -> <ExampleMarker as HasLifetime>::AtLifetime<'id> {
        ExampleS(id)
    }

    ExistentialLifetime::<ExampleMarker>::new(new_helper)
}

fn broken2() -> ExistentialLifetime<ExampleMarker> {
    ExistentialLifetime::<ExampleMarker>::new(|id| ExampleS(id))
}

Note that this uses generic associated types (AtLifetime<'a>) and it also uses a higher-rank trait bound in fn new.

However, rustc nightly rejects this program with the following error:

 Compiling playground v0.0.1 (/playground)
error[E0271]: type mismatch resolving `for<'id> <for<'id> fn(Id<'id>) -> ExampleS<'id> {broken0::new_helper} as FnOnce<(Id<'id>,)>>::Output == <ExampleMarker as HasLifetime>::AtLifetime<'id>`
  --> src/lib.rs:38:5
   |
38 |     ExistentialLifetime::<ExampleMarker>::new(new_helper)
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected associated type, found struct `ExampleS`
   |
   = note: expected associated type `<ExampleMarker as HasLifetime>::AtLifetime<'_>`
                       found struct `ExampleS<'_>`
   = help: consider constraining the associated type `<ExampleMarker as HasLifetime>::AtLifetime<'_>` to `ExampleS<'_>` or calling a method that returns `<ExampleMarker as HasLifetime>::AtLifetime<'_>`
   = note: for more information, visit https://doc.rust-lang.org/book/ch19-03-advanced-traits.html
note: required by a bound in `ExistentialLifetime::<S>::new`
  --> src/lib.rs:18:46
   |
17 |     pub fn new<F>(f: F) -> ExistentialLifetime<S>
   |            --- required by a bound in this
18 |         where for<'id> F: FnOnce(Id<'id>) -> S::AtLifetime<'id> {
   |                                              ^^^^^^^^^^^^^^^^^^ required by this bound in `ExistentialLifetime::<S>::new`

error[E0271]: type mismatch resolving `for<'id> <for<'id> fn(Id<'id>) -> <ExampleMarker as HasLifetime>::AtLifetime<'id> {broken1::new_helper} as FnOnce<(Id<'id>,)>>::Output == <ExampleMarker as HasLifetime>::AtLifetime<'id>`
  --> src/lib.rs:46:5
   |
46 |     ExistentialLifetime::<ExampleMarker>::new(new_helper)
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected associated type, found struct `ExampleS`
   |
   = note: expected associated type `<ExampleMarker as HasLifetime>::AtLifetime<'_>`
                       found struct `ExampleS<'_>`
   = help: consider constraining the associated type `<ExampleMarker as HasLifetime>::AtLifetime<'_>` to `ExampleS<'_>` or calling a method that returns `<ExampleMarker as HasLifetime>::AtLifetime<'_>`
   = note: for more information, visit https://doc.rust-lang.org/book/ch19-03-advanced-traits.html
note: required by a bound in `ExistentialLifetime::<S>::new`
  --> src/lib.rs:18:46
   |
17 |     pub fn new<F>(f: F) -> ExistentialLifetime<S>
   |            --- required by a bound in this
18 |         where for<'id> F: FnOnce(Id<'id>) -> S::AtLifetime<'id> {
   |                                              ^^^^^^^^^^^^^^^^^^ required by this bound in `ExistentialLifetime::<S>::new`

error[E0271]: type mismatch resolving `for<'id> <[closure@src/lib.rs:50:47: 50:64] as FnOnce<(Id<'id>,)>>::Output == <ExampleMarker as HasLifetime>::AtLifetime<'id>`
  --> src/lib.rs:50:5
   |
50 |     ExistentialLifetime::<ExampleMarker>::new(|id| ExampleS(id))
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected associated type, found struct `ExampleS`
   |
   = note: expected associated type `<ExampleMarker as HasLifetime>::AtLifetime<'_>`
                       found struct `ExampleS<'_>`
   = help: consider constraining the associated type `<ExampleMarker as HasLifetime>::AtLifetime<'_>` to `ExampleS<'_>` or calling a method that returns `<ExampleMarker as HasLifetime>::AtLifetime<'_>`
   = note: for more information, visit https://doc.rust-lang.org/book/ch19-03-advanced-traits.html
note: required by a bound in `ExistentialLifetime::<S>::new`
  --> src/lib.rs:18:46
   |
17 |     pub fn new<F>(f: F) -> ExistentialLifetime<S>
   |            --- required by a bound in this
18 |         where for<'id> F: FnOnce(Id<'id>) -> S::AtLifetime<'id> {
   |                                              ^^^^^^^^^^^^^^^^^^ required by this bound in `ExistentialLifetime::<S>::new`

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

I think rustc is wrong to reject this code. As you can see, it fails to unify type <ExampleMarker as HasLifetime>::AtLifetime<'_> with type ExampleS<'_>. But these types should unify!

Version of rustc: 1.60.0-nightly 2022-01-25 8cdb3cd94efece1e17cb.

[compiler-errors]

This seems related to #93342, and I'm looking at that right now..

[compiler-errors]

@rustbot claim
just for good measure, haha

[skyzh]

Hi @reinerp, if you need a quick fix, you may refer to my issue #93342, where you may implement a "bridge trait" to help the compiler infer the correct lifetime for where for<'id> F: FnOnce(Id<'id>) -> S::AtLifetime<'id>.

[jackh726]

I think this was fixed in #90887, but needs to be confirmed.

[compiler-errors]

@jackh726, confirmed fixed.

[crlf0710]

Closing according to the comment above.