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.

[BoxyUwU]

I think this isnt solely a gats issue you can reproduce it on stable playground This technically makes reverting the fix a breaking change since the fix hit stable, if you look at the playground you'll see that it compiles on stable but not on latest nightly

[jackh726]

uh oh

[jackh726]

Okay, so this "only" hit stable on Rust 1.60. So it "only" needs a stable backport if we want to keep this revert for now. I'm going to label for lang team to discuss.

Brief summary:
This issue was fixed by a "hack" in #92191. At the time, this hack was deemed acceptable because it wasn't clear that it could break code. It did break #93262 though (uses GATs, but nobody to my knowledge has tried to make a non-GAT repro). That hit stable in 1.60 and also seems to fix this non-GAT example.

#96593 just hit nightly, which is a revert of the above hack. Unfortunately this now changes stable behavior (as opposed to only GATs behavior, which was expected). I'm going to try to schedule a crater run later today to get some data on if this actually effects anyone.

To make things more interesting, the code in this example compiles with feature(nll), which is likely on track to be stabilized. I don't think it fixes #93262.

We have three options:

1. Revert the revert and wait until NLL stabilization to revert the revert revert. This means that GAT: lifetime is inconsistently required with Higher-Rank Trait Bounds #93262 will not work in the meantime. (Unstable, but GATs which has stabilization PR open)
2. Stable and beta backport the revert. This means that the linked playground will return to being an error on stable.
3. Do nothing and just wait for NLL.

Between the 3, I would prefer 2.

[jackh726]

@craterbot run name=92191_revert mode=check-only start=master#4c60a0ea5b2385d7400df9db1ad04e96f2a4c154 end=master#bdcb6a99e853732f8ec050ae4986aa3af51d44c5

[craterbot]

👌 Experiment 92191_revert created and queued.
🔍 You can check out the queue and this experiment's details.

ℹ️ Crater is a tool to run experiments across parts of the Rust ecosystem. Learn more

[craterbot]

🚧 Experiment 92191_revert is now running

ℹ️ Crater is a tool to run experiments across parts of the Rust ecosystem. Learn more

[craterbot]

🎉 Experiment 92191_revert is completed!
📊 15 regressed and 11 fixed (231778 total)
📰 Open the full report.

⚠️ If you notice any spurious failure please add them to the blacklist!
ℹ️ Crater is a tool to run experiments across parts of the Rust ecosystem. Learn more

[danielhenrymantilla]

It did break #93262 though (uses GATs, but nobody to my knowledge has tried to make a non-GAT repro)

@jackh726 FWIW, neither of the two canonical stable-GAT-workarounds for that snippet regresses:

• https://rust.godbolt.org/z/1Y7denM7Y
• https://rust.godbolt.org/z/EjxPjcM3K

so I strongly suspect it's only a GAT-specific regression 🙂

[jackh726]

Yes, that makes sense: the issue there really comes down to the where clause.

Crater results look clean though. As discussed on Zulip (https://rust-lang.zulipchat.com/#narrow/stream/213817-t-lang/topic/Covariance-related.20GAT.20lifetime.20mismatch.20.2389352/near/281881315), accepting that for beta backport.

[jackh726]

The nominated portion of this got resolved when #96593 got beta-backported. Technically, the non-GATs reproduction that #96593 broke got "stabilized" in 1.60 - but this falls under accidental stabilization and is reverted in 1.61 (it was too close to release train to stable-backport).

Removing I-lang-nominated.

[jackh726]

This now compiles, since NLL stabilization.

[jackh726]

Actually, there was a bug test that got properly moved during stabilization. Closing.