Need help with complex relative lifetimes

[mankinskin]

I am stumped by an error that occurs in this example:

full playground

I have a set of types that should provide synchronized access to some type of collection, in the example its a HashMap, and I interface with them with a trait called Traversable which has a lock function returning a guard to access the collection through. So this guard will represent the lifetime of a lock being held.

trait Traversable {
    type Guard<'g>: Deref<Target=HashMap<usize, String>> where Self: 'g;
    fn lock<'g>(&'g self) -> Self::Guard<'g>;
}

Then there are types which are able to get values out of this collection, and the interface here is GetValue which has a function get_value expecting one of these guards, so the signature looks like this:

fn get_value<
    'g,
    Trav: Traversable,
>(&self, guard: &'g Trav::Guard<'g>) -> &'g String;

where guard is the guard to the locked collection of a generic Traversable. Now the lifetimes here are supposed to enforce that the provided guard outlives the return value &'g String, because that is supposed to be a reference into the guarded collection.

However if I try to use this like this:

fn example<
    Trav: Traversable,
>(&self, trav: &Trav) {
    let guard = trav.lock();
    {
        let value = self.get_value::<Trav>(&guard);
        
        // do some stuff with value
        println!("{}", value);
        // drop value
    }
    // drop guard
}

It says guard does not live long enough.

error[E0597]: `guard` does not live long enough
  --> src/main.rs:54:44
   |
54 |         let value = self.get_value::<Trav>(&guard);
   |                                            ^^^^^^ borrowed value does not live long enough
...
58 |     }
   |     -
   |     |
   |     `guard` dropped here while still borrowed
   |     borrow might be used here, when `guard` is dropped and runs the destructor for type `<Trav as Traversable>::Guard<'_>`

But shouldn't 'g be the lifetime of the guard variable?
No, because the lock function asserts that fn lock<'g>(&'g self) -> Self::Guard<'g>, so 'g is in fact the lifetime on trav: &Trav, which may be much larger than the lifetime of the guard variable.

I can't remove the lifetime from &'g self in lock, because then an implementation of lock could not return a matching lifetime. The error I get is:

21 |     fn lock<'g>(&self) -> Self::Guard<'g> {
   |             --  - let's call the lifetime of this reference `'1`
   |             |
   |             lifetime `'g` defined here
22 |         self.entries.lock().unwrap()
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ associated function was supposed to return data with lifetime `'g` but it is returning data with lifetime `'1`

So I tried to introduce a second lifetime for representing the lifetime of the Traversable &Trav (or &self):

example with second lifetime

trait Traversable {
    type Guard<'a: 'g, 'g>: Deref<Target=HashMap<usize, String>> + 'g where Self: 'a;
    fn lock<'a: 'g, 'g>(&'a self) -> Self::Guard<'a, 'g>;
}

So here 'a must include 'g but can still be different from 'g. Now when I use it like this:

trait GetValue {
    fn get_value<
        'a: 'g,
        'g,
        Trav: Traversable,
    >(&self, guard: &'g Trav::Guard<'a, 'g>) -> &'g String;
}

fn example<
    'a: 'g,
    'g,
    Trav: Traversable,
>(&self, trav: &'a Trav) {
    let guard = trav.lock();
    {
        let value = self.get_value::<Trav>(&guard);
        
        // do some stuff with value
        println!("{}", value);
        // drop value
    }
    // drop guard
}

I would think 'g must be the lifetime of the variable guard, because that is asserted by &'g Trav::Guard<'a, 'g> in get_value. But for some reason I get the exact same error. For some reason value: &'g String still outlives guard, even though I would expect it to have the same lifetime at most. Actually value is dropped before guard, so it should have a shorter lifetime inside of 'g. But even if I introduce a third lifetime for the return value &'x String, with 'g: 'x ('g containing 'x), I get the exact same error.

trait GetValue {
    fn get_value<
        'a: 'g,
        'g: 'x,
        'x
        Trav: Traversable,
    >(&self, guard: &'g Trav::Guard<'a, 'g>) -> &'x String;
}

third lifetime

So what exactly is going on here? I feel like I am completely on the wrong track, but it is extremely hard to google this at this point.

This is even a simplified version of what I actually need. In my actual use case I need the lifetime of the value: &String to be either in &self or &Trav::Guard<'g>, but both should be allowed. So I really need to understand this even simpler problem.

If someone could point me in a direction or has encountered this before, I would be very thankful.

[semicoleon]

Your intuition to introduce another lifetime was on the right track, but you didn't put the new lifetime where it was needed.

This version of GetValue works^[1]

trait GetValue {
    fn get_value<
        'a, 
        'g: 'a,
        Trav: Traversable,
    >(&self, guard: &'a Trav::Guard<'g>) -> &'a String;
}

Playground

I believe the issue you're running into is lifetime variance. GAT lifetimes are assumed to be invariant similar to lifetime parameters on traits ^[2]. That means guard: &'g Trav::Guard<'g> was saying that the borrow of guard had to live exactly as long as the lifetime inside the Guard GAT, which is why you got the weird dropcheck borrow error message.

By adding another lifetime we clarify that we only need the borrow to last as long as the return value, and that the borrow can't be shorter than 'g. There's more about variance in Rust here

Subtyping and Variance - The Rustonomicon

---

1. once the rest of the code is updated to compensate of course ↩︎

2. like in Trait<'a> ↩︎

[quinedot]

Same change @semicoleon suggested, different spelling. And yes, it's problematic because GATs are invariant in their parameters.

 /// interface to get a value from a locked traversable
 trait GetValue {
     fn get_value<
         'g,
         Trav: Traversable,
-    >(&self, guard: &'g Trav::Guard<'g>) -> &'g String;
+    >(&self, guard: &'g Trav::Guard<'_>) -> &'g String;
 }
 impl GetValue for Example {
     fn get_value<
         'g,
         Trav: Traversable,
-    >(&self, guard: &'g Trav::Guard<'g>) -> &'g String {
+    >(&self, guard: &'g Trav::Guard<'_>) -> &'g String {
         guard.get(&self.key).unwrap()
     }
 }

[mankinskin]

Thank you, this sounds promising, I will try to make the changes..

I think my misunderstanding was that the lifetime on MutexGuard<'a, T> is not the lifetime of the guard, but of the locked mutex, is that correct? So basically the longer lifetime should go into Trav::Guard<'a>, and that itself has a lifetime &'g Trav::Guard<'a> where 'a: 'g ('a contains 'g)

[mankinskin]

Insane. It works, just like that

Thank you soo much

[quinedot]

I'm not sure if you had a misunderstanding, or just a lack of understanding with regards to the hazards of invariant inner lifetimes. Drop played a role too, but invariance was really at the heart of the matter in my opinion.

Let me see if I can summarize.

---

Something similar to this comes up more often with concrete, lifetime-carrying structs where people do something like:

struct Ref<'a> { /* ...something covariant... */ }
impl<'a> Ref<'a> {
    fn method(&'a mut self) { /* ... */ }
}

&'a mut T is covariant in 'a but invariant in T, and this method takes a &'a mut Ref<'a>. The result is that once you call the method ^[1], you can never directly use the underlying Ref again, because it is exclusively borrowed for the rest of it's validity (due to the lifetime). You can't move it, you can't borrow it again, you can't even have a non-trivial destructor -- because that destructor needs to take a &mut self too. ^[2]

For this reason, &'a mut Thing<'a> is a red flag. Any use it has is very niche.

However, we have something closer to...

// This one is invariant in `'a` because `Cell<T>` is invariant in `T`
struct Invar<'a>(Cell<Ref<'a>>);
impl<'a> Invar<'a> {
    fn method(&'a self) { /* ... */ }
}

This is almost as restricting, but not quite -- you could still immutably borrow self after you called method this time. But you still can't move it, you can't mutably borrow it, and you still can't have a non-trivial destructor either -- there's still no way to get a &mut self.

The usual solution in both cases is to not require the outer reference lifetime to match the inner struct lifetime.

impl<'a> Thing<'a> {
    fn foo(&mut self) {} // No &'a mut self
    fn bar(&self) {} // No &'a self
}

Or they're trying to make a self-referential struct or similar, in which case there probably is no safe solution the programmer will be happy with.

---

Why does the invariance matter so much? Well, let's look at what happens here:

// Reminder: Ref<'a> is covariant in 'a
impl<'a> Ref<'a> {
    // unnecessarily_strict_but_okay
    fn usbok(&'a self) {}
}

fn example<'a>(r: Ref<'a>) { // 'a ----+
    let slo_mo = &r;    // 'x ------+  |
    Ref::usbok(slo_mo); //          |  |
    drop(slo_mo);       // ---------+  |
    let _moved_ref = r; //             |
} //                                   | (longer than the fn body)        

The r in the example gets borrowed for some shorter &'x... even though we said it takes a &'a Ref<'a>. This is possible because of the covariance of Ref. Because Ref<'a> is covariant in 'a, we coerced a &'x Ref<'a> into a &'x Ref<'x> in order to be able to call the method.

That's how covariance lets this work despite the anti-pattern. ^[3]

If 'a is invariant, the move will cause an error for the reasons explained above. You can't coerce a &'x Invar<'a> to a &'x Invar<'x>, so instead you have to start with a &'a Invar<'a> to make the lifetimes match in order to make the method call.

You can call Ref::<'a>::usbok specifically to see that actually creating a &'a Ref<'a> is still problematic.

---

With that background, I think the only other pieces you need to understand your OP are that:

• GATs are invariant in their parameters -- because your definition may be too!
• GATs are assumed to have non-trivial destructors in generic context -- because they could!
  • (MutexGuard in particular does have one)

And the fix is the typical one: Don't use the &'a Thing<'a> antipattern, keep the lifetimes distinct (usually by eliding one or both of them).

---

What if you need a covariant GAT? There's no covariant bound, so you have to instead work around it with methods if you need to.

(But you don't need to.)

---

1. once you create the &mut really ↩︎

2. If method returns some reborrow of the &mut self, you can still use that. ↩︎

3. So you may have used this pattern before in a less generic setting and not had it bite you! ↩︎

[H2CO3]

@mankinskin

I think my misunderstanding was that the lifetime on MutexGuard<'a, T> is not the lifetime of the guard, but of the locked mutex, is that correct?

Yeah, kind of. It wouldn't make sense for the lifetime annotation of the guard to refer to the guard itself. A lifetime annotation ultimately always gets used as the parameter of a reference type, either directly or transitively. Thus, Guard<'guard> would either mean a self-referential struct (impossible and/or useless in safe Rust), or else it would be redundant/useless at best or wrong at worst: when you have a value of a type, the compiler knows perfectly well how long you are allowed to reference it – lifetime annotations cannot shrink or extend the true liveness region of a value.

Hence, lifetime annotations are required when your value references some other value. So in your case, the annotated type should indeed be Guard<'lock> instead.

Furthermore, what also probably confused you is that the following API makes no sense:

impl<'lock, T> Guard<'lock, T> {
    fn get(&self) -> &'lock T {
        ...
    }
}

The whole point of a lock guard is to restrict access to the value to the duration for which the lock is held. If you could access the locked value through a reference with lfietime longer than that of the guard, then your lock and guard would be useless and/or unsound. (The aforementioned signature is also impossible to implement when the returned reference is mutable, again due to invariance.)