Seemingly equivalent GAT trait implementations behave differently

[petrosagg]

The following code fails to compile:

#![feature(generic_associated_types)]

use std::ops::Deref;

trait GetOutput {
    type Output<'a>
    where
        Self: 'a;

    fn output<'a>(&'a self) -> Self::Output<'a>;
}

impl<T, D> GetOutput for T
where
    T: Deref<Target = D>,
    D: GetOutput,
{
    type Output<'a>
    where
        Self: 'a,
        D: 'a,
    = D::Output<'a>;

    fn output<'a>(&'a self) -> Self::Output<'a> {
        self.deref().output()
    }
}

But this equivalent (I think) code compiles just fine:

#![feature(generic_associated_types)]

use std::ops::Deref;

trait GetOutput {
    type Output<'a>
    where
        Self: 'a;

    fn output<'a>(&'a self) -> Self::Output<'a>;
}

impl<T> GetOutput for T
where
    T: Deref,
    T::Target: GetOutput,
{
    type Output<'a>
    where
        Self: 'a,
        <Self as Deref>::Target: 'a,
    = <<Self as Deref>::Target as GetOutput>::Output<'a>;

    fn output<'a>(&'a self) -> Self::Output<'a> {
        self.deref().output()
    }
}

There might be a subtle difference between the two implementation but I can't see any. This is a simplified example from this question in the Rust subreddit: https://www.reddit.com/r/rust/comments/qp8dwl/hey_rustaceans_got_an_easy_question_ask_here/hjsfjgs/

[jackh726]

This is pretty gnarly. Has some relevance around implied bounds, as well as constrained type params and their inferred outlives relationships, specifically when they don't appear in the Self type, but do appear as the associated type in a projection.

See https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=4a9562b4e3074b1630fae2994a3d7471 for a different repro, where I split out the GAT from the trait, so we don't have to write the required Self: 'a bound (the expected workaround).

We get this error

error[E0309]: the parameter type `D` may not live long enough
  --> src/lib.rs:26:9
   |
20 | impl<T, D> GetOutput for T
   |         - help: consider adding an explicit lifetime bound...: `D: 'a`
...
26 |         self.deref().output()
   |         ^^^^^^^^^^^^ ...so that the type `D` is not borrowed for too long

error[E0309]: the parameter type `D` may not live long enough
  --> src/lib.rs:26:14
   |
20 | impl<T, D> GetOutput for T
   |         - help: consider adding an explicit lifetime bound...: `D: 'a`
...
26 |         self.deref().output()
   |              ^^^^^ ...so that the reference type `&D` does not outlive the data it points at

error[E0309]: the parameter type `D` may not live long enough
  --> src/lib.rs:26:22
   |
20 | impl<T, D> GetOutput for T
   |         - help: consider adding an explicit lifetime bound...: `D: 'a`
...
26 |         self.deref().output()
   |                      ^^^^^^ ...so that the reference type `&D` does not outlive the data it points at

This is probably the error that was seen originally, too.

So, in the "compiling" example, we're able to infer that <<Self as Deref>::Target as GetOutput>::Output: 'a, even without a Self: 'a bound. Don't know, maybe because of variance. Have to think about it more.

[nikomatsakis]

@jackh726 and I talked about this issue today. Here is what is going on:

• The reason that the second example works is because the where clause Self: 'a on its own implies that <Self as Target>::Deref: 'a. This is because we have a rule that says "if all the inputs to a trait outlive 'a, then the values of its associated types outlive 'a", or, put another way, "the value of an associated type must outlive all the inputs".
• The problem with the first example is, in part but not entirely, that we lose sight of that rule when an associated type is successfully normalized. So in this case we have Self: Deref<Target = D>, that implies that "D outlives Self", but that's not something the compiler knows or knows how to reason about. If it did, it could conclude that D: 'a because D: Self and Self: 'a.

The proper fix is probably extending the compiler to understand the idea of T1: T2 and, in cases where you have T1: Trait<Type = T2>, elaborating that to include the implication that T2: T1.

[jackh726]

GATs issue triage: not blocking. This is a bit of a more general problem than GATs. I'm not sure if this can be hit outside of GATs (I imagine there might be a way). However, given that fixing this will be backwards-compatible and there is a workaround (just use the projection form), I don't think this needs to block stabilization.