GATs: adding a seemingly unrelated bound makes an Index blanket impl compile

Why does adding a Key: 'static bound to the impl make this compile? Does Index<Key> create an implicit lifetime bound? Key: 'a is insufficient.

// Copyright 2022 Google LLC.
// SPDX-License-Identifier: Apache-2.0

use core::ops::Index;

trait MyIndex<Key> {
    type Output<'a>
    where
        Self: 'a;
    fn my_index(&self, n: Key) -> Self::Output<'_>;
}

impl<'a, T, Key> MyIndex<Key> for T
where
// Required to compile: why?
//    Key: 'static,
    T: Index<Key>,
    <T as Index<Key>>::Output: 'a,
{
    //  the associated type `<T as Index<Key>>::Output` may not live long enough
    type Output<'b> = &'b T::Output where T: 'b;

    fn my_index<'c>(&'c self, n: Key) -> Self::Output<'c> {
        todo!()
    }
}

If I just look at the code and think through what might go wrong, I see:

If T::Output lives for 'a, and T satisfies some lifetime 'x longer than 'a, then the GAT is defined for lifetimes 'b which live longer than T::Output, and &'b T::Output is not well-formed.

You have 'a there as a bound for <T as Index<Key>>::Output only. If Output isn't 'static, it must be bound by one the input parameters to the implementation -- that is, it's picking up a lifetime from T or Key (or both). The GAT has a built-in bound (where Self: 'a / where T: 'b) to ensure well-formedness if the lifetime comes from T, but you also need something in the case where the lifetime comes from Key.

That's my interpretation of the problem, and tying the Key into the GAT does let it compile. I haven't attempted to actually utilize the trait though.

[I just quickly edited the playground link -- you no longer need a lifetime on the impl.]

3 Likes

Great, thank you! I sort of understand, though I'm confused where the implicit lifetime really comes in, since the actual output type shouldn't necessarily care about the lifetime of the Key. So should this apply generally, where if you have a GAT that references a trait's type parameter at all, it should probably bound on it?

That 'a in there with the bound was actually left over from a test with an specific struct impl where we did need the 'a. There, we had to specify where 'a: 'b on the impl's GAT bound. For some reason, this is not detected as a more strict bound than the trait declaration. Any thoughts there, or WAI?

Example where it cares about the lifetime of the Key. Is this ever a sensible pattern? :man_shrugging: Sensible or not, should or should not, it's allowed by the Index trait which you're relying on, so you have to account for the possibility.

We're all still getting our GAT legs, but it does feel like one should consider all inputs to their trait (here, that includes Key) and not just Self when thinking about what GAT clauses make sense. If the intention is to rely on an associated type where your inputs are the other trait's inputs too, like this example, you probably have to.

It works with the suggested changes anyway.

The lifetime relationships of types is largely syntactical. Given 'a: 'b, and the rules as they apply to MyIndexType<'a> (aliased by Self), we can conclude that Self: 'a. Presumably that's what's going on and why it wasn't flagged as a stricter bound.

It's a little more surprsing that it seems to be fine with changing 'a: 'b to Self: 'b, as it must somehow "going backwards" (from the POV of the RFC) and concluding 'a: 'b... or at least that's the only way it seems to me it could be okay with the bound proving that Foo<'a>: 'b.

The logic still makes sense to me, but I have seen errors where the compiler didn't seem to be able to make this leap between struct bounds and lifetime bounds. I'm afraid I don't have a citation or complete understanding of when this may or may not occur though.