Lifetime issue with GATs

[clark]

I'm not sure this is really related specifically to GATs, but I need GATs to represent what I am trying to do.

For context, I am writing a game networking library which takes a world, say a hecs::World, and can add/remove objects from the world, inspect objects, and mutate objects. But to inspect/mutate objects it requires borrowing a "view", which allows one to inspect/mutate exactly one object at a time (and as long as the view is held, no objects can be added or removed).

I can do this naturally by directly borrowing a hecs::World, but my intention is to make this more general so as to not be tied down to hecs.

Below is a very pared down attempt at this using GATs.

#![feature(generic_associated_types)]

struct Object {}

trait Viewer<'a> {
    // the same function without the 'b doesn't work either and as I understand
    // should be no different. I.e., borrow checker already looks for a 'b
    // that is no longer than 'a
    fn get_object<'b>(&'a self, world_object_id: u32) -> &'b Object where 'a:'b;
}

trait World {
    type WorldViewer<'a>: Viewer<'a> where Self: 'a;
    

    fn get_view(&self) -> Self::WorldViewer<'_>;

    // This doesn't work either:
    //   fn get_view<'a>(&'a self) -> Self::WorldViewer<'a>;
}

fn _test(world: &impl World) {
    let view = world.get_view();
    // add an extra scope to help borrow checker as much as possible
    {
        let _o = view.get_object(1);
    }
}

fn main() {
    
}

   Compiling playground v0.0.1 (/playground)
error[E0597]: `view` does not live long enough
  --> src/main.rs:26:18
   |
26 |         let _o = view.get_object(1);
   |                  ^^^^^^^^^^^^^^^^^^ borrowed value does not live long enough
27 |     }
28 | }
   | -
   | |
   | `view` dropped here while still borrowed
   | borrow might be used here, when `view` is dropped and runs the destructor for type `<impl World as World>::WorldViewer<'_>`

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

I understand that the impl is forcing a drop check, and that is why I get this specific error. But if I create a struct that implements the World trait and pass a reference to that instead I still get an error if I try to call get_object a second time. So somehow the get_object call is permanently borrowing the lifetime of view and I don't get why.

[steffahn]

Note that the &'a self in Viewer<'a>::get_object method, together with the fact that WorldViewer<'a> only implements Viewer<'a> relates the lifetime parameter of the WorldViewer with the lifetime of how long it's going to be borrowed. Hence calling get_object here requires a &'a T::WorldViewer<'a>, note the two matching lifetimes. This creates problems with drop check in a generic setting, and even in a concrete setting may still force two a priory unrelated lifetimes to be the same (depending on how generic the actual Viewer implementation of the type involved is.

---

I don't know what changes to the API to suggest here, as I don't quite understand the actual constraints here. This isn't helped by the fact that you don't actually provide any trait implementation for demonstration here.

One guess is that it may be reasonable to change &'a self in get_object to &'b self. Can't know if that's possible for the reasons explained above, but if that works for your implementations, it at least makes your example code compile. In that case however, the whole 'a parameter of the Viewer trait might be unnecessary to begin with, because you'll also get an implicit 'a: 'b bound anyways when some type Foo<'a> implementing Viewer gets passed to get_object as a &'b Foo<'a> reference (such a reference type implies 'a: 'b). Without the trait parameter, the code looks like

trait Viewer {
    fn get_object<'b>(&'b self, world_object_id: u32) -> &'b Object;
}

trait World {
    type WorldViewer<'a>: Viewer where Self: 'a;

    fn get_view(&self) -> Self::WorldViewer<'_>;
}

[clark]

Thank you for that reply. I get now what is causing the issue. I think I need to think about it more to figure out why, if that makes sense (specifically why the rules work that way).

In an effort to demonstrate why I needed all the complication I added a simplified version along the lines you were suggesting and also added a sample implementation.

Much to my surprise it worked (sometimes going from A to C we skip B I guess).

To be honest I was surprised that trait Viewer<'a> compiled without using the 'a. I guess that restriction only exists on structs.

#![feature(generic_associated_types)]

struct Object { val: u32 }

trait Viewer<'a> {
    fn get_object(&self, world_object_id: u32) -> &Object;
    fn get_object_mut(&mut self, world_object_id: u32) -> &mut Object;
}

trait World {
    type WorldViewer<'a>: Viewer<'a> where Self: 'a;
    
    fn add(&mut self, obj: Object) -> u32;
    fn del(&mut self, idx: u32);
    

    fn get_view(&mut self) -> Self::WorldViewer<'_>;
}

struct SimpleWorld {
    objs: Vec<Object>
}

impl SimpleWorld {
    fn new() -> Self {
        Self {  objs: Vec::default() }
    }
}

impl World for SimpleWorld {
    type WorldViewer<'a> where Self: 'a = SimpleWorldViewer<'a>;
    
    fn add(&mut self, obj: Object) -> u32 {
        self.objs.push(obj);
        self.objs.len() as u32 - 1
    }
    
    fn del(&mut self, idx: u32) {
        self.objs.remove(idx as usize);
    }

    fn get_view(&mut self) -> Self::WorldViewer<'_> {
        Self::WorldViewer { world: self }
    }
}

struct SimpleWorldViewer<'a> {
    world: &'a mut SimpleWorld,
}

impl<'a> Viewer<'a> for SimpleWorldViewer<'a> {
    fn get_object(&self, world_object_id: u32) -> &Object {
        &self.world.objs[world_object_id as usize]
    }
    
    fn get_object_mut(&mut self, world_object_id: u32) -> &mut Object {
        &mut self.world.objs[world_object_id as usize]
    }
}


fn test(world: &mut impl World) {
    world.add(Object { val: 101 });

    {
        let mut view = world.get_view();

        // this is meant to fail because we are holding a view:
        //    world.add(Object { val: 201 });

        let mut o1 = view.get_object_mut(1);
        o1.val = 1;
        let _o2 = view.get_object(2);
        let mut o3 = view.get_object_mut(0);
        o3.val = 99;
    }

    // The following works without the braces above if
    // "world: &mut SimpleWorld" but not if
    // "world: &mut impl World" due to drop check.  
    // With the braces it works either way.
    world.add(Object { val: 121 });
}

fn main() {
    let mut world = SimpleWorld::new();
    world.add(Object { val: 32 });
    world.add(Object { val: 17 });
    world.add(Object { val: 11 });

    test(&mut world);
    
    // make sure our changes actually happened
    assert_eq!(world.objs[0].val, 99);
    assert_eq!(world.objs[1].val, 1);
    assert_eq!(world.objs.len(),5);
}

I played a little with trying to remove the GAT but didn't see how.

I will move this back to my code base and see if there was some other reason I needed to complicate the interface as much as I did. The main implementation will be a wrapper around a hecs world and there may be a reason that led me to complicate things. In the simple example, e.g., there is no reason for the viewer at all (just move those methods onto the world), but with hecs you need it to hold a PreparedView object to access the world.

Thanks again for your response, I do really appreciate it.

[quinedot]

I wrote up the below comment, saw you typing, waited for your post, and now think you probably don't need the lifetime on the trait... so most of the comment won't be necessary. I'm only leaving it in case it is instructional in why the rules work how they do. I'll reply to your latest comment soon.

A possible alternative if the trait truly must have a lifetime

A trait with a lifetime has a bit of code smell. Sometimes it's necessary, but other times, it can be the result of following a chain of compiler errors until you reach a point that the compiler can follow along, but you can no longer due anything ergonomically or at all, due to all the lifetime constraints. If you think you do need the lifetime on the trait, you should probably provide more context, as there may be an alternative. (Perhaps especially when using GATs, since those should alleviate some valid use-cases of lifetime-carrying traits.)

With that being said, if you want covariant behavior, you can work it into the GAT bounds:

    type WorldViewer<'a>: for<'b> Viewer<'b> where Self: 'a;

And then your implementations will have to be covariant to meet that bound:

/*
// Won't work, each `&'a str` only implements `Viewer<'a>`
impl<'a> Viewer<'a> for &'a str {
    fn get_object(&'a self, world_object_id: u32) -> &'a Object {
        let obj: &'a _ = &OBJ;
        obj
    }
}
*/

impl<'a, 'b> Viewer<'b> for &'a str {
    fn get_object(&'b self, _world_object_id: u32) -> &'b Object {
        // Implied by signature: 'a: 'b
        let obj: &'a _ = &OBJ;
        obj
    }
}

And with that in place, you can call get_objecton a Viewer<'a> implementer with a &'b self where 'b is shorter than 'a. (This could also be arranged as a CovariantViewer<'a> subtrait with a bound of for<'b> Viewer<'b>.)

What I'm not sure about is if this is too restrictive in another way or not; more context required.

In case it helps your understanding, traits and GATs are invariant over their lifetime parameters -- having a 'a doesn't imply you can get a 'b, without specifying further bounds.

[clark]

In case it helps your understanding, traits and GATs are invariant over their lifetime parameters -- having a 'a doesn't imply you can get a 'b , without specifying further bounds.

Yes, that helps tremendously. I should probably think a bit more about why the compiler needs that, but I guess it's just that the compiler has no idea what some trait implementation will do with the lifetime, so it has to assume invariance.

The sample code is in your response is also helpful because I wasn't sure how to specify both for<> on the trait and then supply the right 'b implementation on the actual implementation of the trait.

Thanks.

[quinedot]

@clark

To be honest I was surprised that trait Viewer<'a> compiled without using the 'a. I guess that restriction only exists on structs.

I think it's still a sign there's something off or at least weird going on (I'm not thinking of how it could be useful, and again, you normally don't want lifetimes on traits). In your playground, you can just remove the lifetime parameter. Probably you don't need it.

You may be wondering why this still works then:

impl<'a> Viewer for SimpleWorldViewer<'a> {
    fn get_object(&self, world_object_id: u32) -> &Object {
    // Doesn't this mean I have to take a `&'b self` for
    // any `'b` at all?

And the reason is that the

• &'b self has the type
• &'b Self which is an alias for
• &'b SimpleWorldViewer<'a>

And this introduces an implicit "well-formed (WF)" bound that 'a: 'b. It's ok if you can't implement something for &'static SimpleWorldViewer<'short>, because that even existing in the first place is instant UB.

for<'a> SimpleWorldViewer<'a>: Viewer still holds; that's basically what the implementation signature, which has no further where clauses or other bounds, says.

@clark

I played a little with trying to remove the GAT but didn't see how.

Emulating lifetime GATs on stable is one of the valid use-cases for traits-with-lifetimes; here it is for your playground. See also this great step-by-step by @steffahn.

GATs look nicer, hopefully play as nice or nicer once stabilized, and can support more exotic things, so you may or may not want to go with that depending on the larger situation (including how much you care about being on nightly / being stable).

[clark]

Just a quick follow-up:

I was able to apply the CanBorrow trait trick to my code base. I had to declare it like @steffahn did in his example:

trait CanBorrowViewer<'a, _Outlives = &'a Self> { {
    type WorldViewer: 'a + Viewer;
}

Rather than simply as:

trait CanBorrowViewer<'a,> : 'a {
    type WorldViewer: 'a + Viewer;
}

The reason is that my more complex world had a lifetime of it's own, and the later method doesn't work in that case, at least as far as I could manage it.

I'm still not great at reasoning about lifetimes, so I won't give my take on why this fails, but this doesn't compile because 'a and 'w are unrelated:

impl<'a,'w> CanBorrowViewer<'a> for SimpleWorld<'w> {
    type WorldViewer = SimpleWorldViewer<'a,'w>;
}

But if declare it like below then you can't implement World for SimpleWorld<'w> because CanBorrow is not general enough:

impl<'a,'w:'a> CanBorrowViewer<'a> for SimpleWorld<'w> {
    type WorldViewer = SimpleWorldViewer<'a,'w>;
}

In any case, it is all working in my code base so thank you both for the help.

[steffahn]

@clark

The reason is that my more complex world had a lifetime of it's own, and the later method doesn't work in that case, at least as far as I could manage it.

The point of the workaround using the _Outlives parameter with a default type is to limit the range of the for<'a> CanBorrowViewer<'a> supertrait bound. You really only want to say “for those 'a such that Self: 'a, define an associated type WorldViewer”, similar to what the Self: 'a does in a GAT “type WorldViewer<'a>: Viewer<'a> where Self: 'a;”.

The reason why this works is because HRTBs like for<'a> CanBorrowViewer<'a> implicitly only range over those lifetimes such that the types involved are valid. E.g. a bound Fn(&T) or equivalently for<'a> Fn(&'a T) will also only range over the lifetimes where 'a: T. The default parameter is a neat trick that abbreviates a longer expression involving a type that implies this restriction: With the _Outlives = &'a Self parameter, the HRTB

for<'a> CanBorrowViewer<'a>

is just an abbreviation for the longer equivalent

for<'a> CanBorrowViewer<'a, &'a Self>

and this has the effect that the HRTB only ranges over lifetimes such that Self: 'a.

Rustc is still not particularly smart about these implied bounds. For example, you can see that using

struct SimpleWorldViewer<'a, 'w> {
    world: &'a mut SimpleWorld<'w>,
}

impl<'a, 'w> CanBorrowViewer<'a> for SimpleWorld<'w> {
    type WorldViewer = SimpleWorldViewer<'a, 'w>;
}

works and rustc doesn’t complain about the fact that SimpleWorldViewer<'a, 'w>; needs 'w: 'a, because that’s implied by the implicit &'a SimpleWorld<'w>; the above is equivalent to

impl<'a, 'w> CanBorrowViewer<'a, &'a SimpleWorld<'w>> for SimpleWorld<'w> {
    type WorldViewer = SimpleWorldViewer<'a, 'w>;
}

after all, if you add in the defaulted type argument. However while rustc can understand the fact that &'a SimpleWorld<'w> implies 'w: 'a in this case, if you tried adding such a bound yourself and writing a – in theory – ought-to-be equivalent

impl<'a, 'w: 'a> CanBorrowViewer<'a> for SimpleWorld<'w> {
    type WorldViewer = SimpleWorldViewer<'a, 'w>;
}

then rustc suddenly complains about the implementation being “not general enough”, anyways. It sees “there’s a bound on the impl” and seems to conclude “it’s not fully general, yet the HRTB requires it to be fully general”, so there’s an error message.

It’s a subtle ride along the border of what you can make rustc understand and what you cannot, and the last word isn’t spoken on HRTBs yet anyways; there’s still multiple open soundness issues where riding the border of what you can make rustc understand, you go further and can make rustc “understand” (i.e. accept) code that’s actually wrong. See e.g. #84591 or #84533 (comment) for some issues I came across while trying to understand the details of rustc behavior around lifetimes and things like HRTBs myself almost 1 year ago. ^[1]

---

1. Note that AFAICT neither of these issues should require any restrictions to the usage of HRTBs that _Outlives = &'a Self trick for emulating GATs relies on. My main point her is just to bring across that “these things are inherently hard to understand” and “even rustc doesn’t really fully understand this (in a sound way)” ↩︎