GAT-related lifetime conflicts with mutex temporary lifetime

Question

I'm experimenting with GATs to enhance the API to an in-memory data store. The data is organized in values, where each value contains, among other things, a lookup key. You can think of it like a row in a database table, where the whole row is a "value", but it also contains a primary-key column or columns.

The idea is to describe this by a trait, so you can look for a particular value by providing the key. The key must be able to refer into the value, so that if the key-part of the value is String, you can look it up using just &str. This is where GATs enter the picture:

pub trait Value {
    type Key<'a>: PartialEq where Self: 'a;

    fn as_key<'a>(&'a self) -> Self::Key<'a>;
}

The Key<'a> GAT provides a lifetime that as_key() can use to return a value that refers to inner data. Note that as_key() can't just return a reference to the key because the returned key can be something that doesn't exist verbatim inside Self, such as a composite key. For example, these are all possible:

struct Data {
    s: String,
    n: u64,
    // ... more fields ...
}

// example 1: expose key as self.s as a &str key
impl Value for Data {
    type Key<'a> = &'a str;
    fn as_key(&self) -> &str { &self.s }
}

// example 2: expose key as a pair of (self.s.as_str(), self.n)
impl Value for Data {
    type Key<'a> = (&'a str, u64);
    fn as_key(&self) -> (&str, u64) { (&self.s, self.n) }
}

An example of generic code that makes use of this trait could look like this:

pub struct Table<T> {
    data: Vec<T>,
}

impl<T: Value> Table<T> {
    fn find<'a: 'k, 'k>(&'a self, k: T::Key<'k>) -> Option<usize> {
        self.data.iter().position(|v| v.as_key() == k)
    }
}

This works beautifully and you can play around with it in the playground. (A more realistic example would require Ord or Hash from Value::Key and build a more sophisticated storage, but this is enough to show the idea.)

Now, let's make a simple change and store the table data in a Mutex. The code looks almost the same, and since it only returns the position, the mutex manipulation should remain internal to the implementation:

struct Table<T> {
    data: Mutex<Vec<T>>,
}

impl<T: Value> Table<T> {
    pub fn find<'a: 'k, 'k>(&'a self, k: T::Key<'k>) -> Option<usize> {
        let data = self.data.lock().unwrap();
        data.iter().position(|v| v.as_key() == k)
    }
}

However, the above code doesn't compile - it complains that "data doesn't live long enough":

error[E0597]: `data` does not live long enough
  --> src/main.rs:18:9
   |
16 |     pub fn find<'a: 'k, 'k>(&'a self, k: T::Key<'k>) -> Option<usize> {
   |                         -- lifetime `'k` defined here
17 |         let data = self.data.lock().unwrap();
18 |         data.iter().position(|v| v.as_key() == k)
   |         ^^^^^^^^^^^              ---------- argument requires that `data` is borrowed for `'k`
   |         |
   |         borrowed value does not live long enough
19 |     }
   |     - `data` dropped here while still borrowed

Playground

I don't quite understand this error - why would data need to live for the lifetime of the key we're comparing it to? I tried:

• changing lifetimes so that lifetimes of 'k and 'a are fully decoupled
• extracting the comparison to a simple function that receives &'a T and &T::Key<'b>, and returns a bool after comparing them (and which compiles on its own)
• replacing Iterator::position() with an explicit for loop

But nothing helped, the error always remained in some form. Note that it's perfectly legal to place both v.as_key() and k in the same closure (e.g. like this), it's only when you attempt to compare them that the error arises.

My intuitive understanding of the problem is that the Eq bound associated with Value::Key<'a> only applies to another Key<'a>.

Is it possible to rework the lifetimes or the as_key() interface to work around this issue? Is this a variant of the issue described here?

---

EDIT: relaxing the PartialEq bound to HRTB for<'b> PartialEq<Self::Key<'b>> as suggested by kmdreko fixes the above examples, but breaks with generics. For example, this implementation of Value fails to compile:

struct NoKey<T>(T);

impl<T> Value for NoKey<T> {
    type Key<'a> = () where T: 'a;
    fn as_key(&self) -> () {
        ()
    }
}

with the error:

error[E0311]: the parameter type `T` may not live long enough
  --> src/lib.rs:38:20
   |
38 |     type Key<'a> = () where T: 'a;
   |                    ^^ ...so that the type `NoKey<T>` will meet its required lifetime bounds

Playground

Answer 1

My intuitive understanding of the problem is that the Eq bound associated with Value::Key<'a> only applies to another Key<'a>.

This is correct. You can relax this constraint by using a higher-ranked trait bound to require Key<'a> to be comparable to all Key<'b>:

pub trait Value {
    type Key<'a>: for<'b> PartialEq<Self::Key<'b>> // <-----
    where
        Self: 'a;

    fn as_key<'a>(&'a self) -> Self::Key<'a>;
}

I don't think there's any other way, because most types are covariant with respect to their associated lifetime, but with T::Key<'k> I don't think you can constrain that 'k can be shortened.

The issue with generics pointed out in the edited question can be worked around by requiring the generic to be 'static (playground). Note that the 'static bound only applies to the value as a whole, the key may still refer to parts of the value.