Covariance-related GAT lifetime mismatch

[QuineDot]

I tried this code:

#![feature(generic_associated_types)]

use core::marker::PhantomData;

pub trait GenAssoc<T> {
    type Iter<'a>;
    fn iter(&self) -> Self::Iter<'_>;
    fn reborrow<'long: 'short, 'short>(iter: Self::Iter<'long>) -> Self::Iter<'short>;
}

pub struct Wrapper<'a, T: 'a, A: GenAssoc<T>> {
    a: A::Iter<'a>,
    _p: PhantomData<T>,
}

impl<'a, T: 'a, A: GenAssoc<T>> GenAssoc<T> for Wrapper<'a, T, A>
where
    A::Iter<'a>: Clone,
{
    type Iter<'b> = ();
    fn iter<'s>(&'s self) -> Self::Iter<'s> {
        let a = A::reborrow::<'a, 's>(self.a.clone());
    }

    fn reborrow<'long: 'short, 'short>(iter: Self::Iter<'long>) -> Self::Iter<'short> {
        ()
    }
}

I expected to see this happen: Successful compilation.

Instead, this happened: Errors as follows.

error[E0308]: mismatched types
  --> src/lib.rs:23:13
   |
23 |         let a = A::reborrow::<'a, 's>(self.a.clone());
   |             ^ lifetime mismatch
   |
   = note: expected type `Sized`
              found type `Sized`
note: the lifetime `'s` as defined on the method body at 22:13...
  --> src/lib.rs:22:13
   |
22 |     fn iter<'s>(&'s self) -> Self::Iter<'s> {
   |             ^^
note: ...does not necessarily outlive the lifetime `'a` as defined on the impl at 16:6
  --> src/lib.rs:16:6
   |
16 | impl<'a, T: 'a, A: GenAssoc<T>> GenAssoc<T> for Wrapper<'a, T, A>
   |      ^^

For more information about this error, try `rustc --explain E0308`.

Note that it expected and found "type Sized", which doesn't make sense. Additionally, I don't see what is restricting 's to outlive 'a; and indeed, the error can be worked around.

Meta

Playground:

Nightly channel
Build using the Nightly version: 1.57.0-nightly
(2021-09-28 8f8092cc32ec171becef)

The original use-case tied the lifetime parameter of the GAT to the type in typical fashion. Discovered in this URLO thread.

@rustbot label +F-generic_associated_types +A-lifetimes +requires-nightly +A-diagnostics

[jackh726]

So, surprisingly, changing A::Iter<'a>: Clone to for<'b> A::Iter<'b>: Clone makes everything compile file.

Details

Somehow, a <<A as GenAssoc<T>>::Iter<'a> as std::marker::Sized> is ending up in the param_env. Later, we try to prove <<A as GenAssoc<T>>::Iter<'b> as std::marker::Sized>, use that predicate, and get that 'a == 'b.

Edit: <<A as GenAssoc<T>>::Iter<'a> as std::marker::Sized> ends up in the param_env because Clone: Sized

[jackh726]

Okay, so I've dug into this a little bit. And I thought I would share where I'm at.

First, let's look at the root cause of this problem: the A::Iter<'a>: Clone bound. This leads to a A::Iter<'a>: Sized bound in the environment. There is also an implicit for<'x, Y> <X as GenAssoc<Y>>::Iter<'x>: Sized bound. At some point, we need to prove that Self::Iter<'s>: Sized. Because of the current rules for what candidates take preference during trait candidate selection. we pick the predicate in the param_env (which, importantly has the specific lifetime 'a). Note, the implicit bound is more generally applicable, but the way the trait selection code works right now means that we select one candidate to confirm. So, we eventually unify 'a with 's, and that's a problem.

One potentially solution I had was to just always prefer the projection candidate. Unfortunately, this ran into a problem with the following case:

fn discr<T, U>(v: T, value: U)
where
    <T as DiscriminantKind>::Discriminant: PartialEq<U>,
{
    assert!(discriminant_value(&v) == value);
}

Basically, the param_env gets a <T as DiscriminantKind>::Discriminant: PartialEq<U> predicate and the projection candidate is <T as DiscriminantKind>::Discriminant: PartialEq<<T as DiscriminantKind>::Discriminant>. We need the former for type checking to succeed. Again though, both candidates are "compatible", and it would just mean that we end up with the constraint that <T as DiscriminantKind>::Discriminant == U.

One thing I'm exploring right now is to make candidate preference depend on if it's a ?X: Sized predicate or not; if so, then we should use the projection candidate (since this will always have the same or more generality and doesn't have any parameters) - otherwise, use the param_env candidate. This is a total hack, but might be okay.