Help with tricky lifetimes for creating in memory cache

So here is what I have so far:

pub struct Cache<'a, K, V> {
    map: NeptuneMap<K, V>,
    storage: Map<'a, &'a K, V>,
}

impl<'a, K, V> Cache<'a, K, V>
where
    &'a K: Debug + PartialEq + Eq + PrimaryKey<'a>,
    K: Clone + Debug + PartialEq + Eq,
    V: Clone + Serialize + DeserializeOwned,
{
    pub fn new(storage: Map<'a, &'a K, V>) -> Self {
        Self { map: NeptuneMap::new(), storage }
    }

    // The problem is in here.
    pub fn get_mut(&'a mut self, deps: Deps, key: &'a K) -> CommonResult<&'a mut V> {
        match self.map.iter().position(|x| &x.0 == key) {
            Some(index) => Ok(&mut self.map.0[index].1), // problem is here, cannot borrow self.map.0 as mutable
            None => {
                let value = self.storage.load(deps.storage, &key)?;
                self.map.insert(key.clone(), value);
                Ok(&mut self.map.last_mut().unwrap().1)
            }
        }
    }
    pub fn save(&'a self, deps: DepsMut) -> CommonResult<()> {
        for (key, value) in self.map.iter() {
            self.storage.save(deps.storage, key, value)?;
        }
        Ok(())
    }

Full error message:

error[E0502]: cannot borrow `self.map.0` as mutable because it is also borrowed as immutable
  --> packages/neptune-common/src/storage.rs:68:36
   |
57 | impl<'a, K, V> Cache<'a, K, V>
   |      -- lifetime `'a` defined here
...
67 |         match self.map.iter().position(|x| &x.0 == key) {
   |               -----------------------------------------
   |               |
   |               immutable borrow occurs here
   |               argument requires that `self.map` is borrowed for `'a`
68 |             Some(index) => Ok(&mut self.map.0[index].1),
   |                                    ^^^^^^^^^^ mutable borrow occurs here

I'm can't quite figure out why it's complaining. Shouldn't the compiler figure out that the immutable borrow is dropped before the mutable borrow takes over? I'm not sure how to play with the lifetimes here to get it to stop complaining. Any help appreciated.

Your bound &'a K: Eq means that evaluating == on &K will require borrowing the whole 'a lifetime. This explains the concrete error at hand.


The most important issue with the code at hand that I’m noticing, and the thing you should probably address first, is that &'a mut self is of type &'a mut Cache<'a, K, V>. You are conflating lifetimes here! Making the lifetime of the borrow equal to the lifetime parameter 'a means that the get_mut function will be (almost entirely) unusable. A call to get_mut would need to borrow the Cache for its entire lifetime.


Glancing back at

pub struct Cache<'a, K, V> {
    map: NeptuneMap<K, V>,
    storage: Map<'a, &'a K, V>,
}

I’m getting a suspicion that you might be intending to put references of values in map into the storage field. If that’s the case (otherwise, ignore the following, I guess?[1]): Not going to work! At least not like this, and neither in any other way that wouldn’t require some fancy macro-magic of tailor-made crates for so-called “self-referential” data structures. Or you could consider splitting up the struct into multiple parts that are handled separately by the user – often the more sane approach. Or… well… you could always work with some owned data. E.g. cloning the K. Or maybe using Rc/Arc if cloning is considered too expensive.


  1. although, judging by the implementation of save, it kinda looks like that’s exactly what’s going on here :innocent: ↩︎

4 Likes

The most important issue with the code at hand that I’m noticing, and the thing you should probably address first, is that &'a mut self is of type &'a mut Cache<'a, K, V> . You are conflating lifetimes here! Making the lifetime of the borrow equal to the lifetime parameter 'a means that the get_mut function will be (almost entirely) unusable. A call to get_mut would need to borrow the Cache for its entire lifetime.

Yep definitely correct. That was a result of me randomly playing around trying to get lucky haha. Did not work. Appreciate the explanation.

If that’s the case

Yes that is definitely the case. I think My first attempt at fixing this will be to use Owned values for the map keys. That shouldn't be too expensive here. That would mean that Cache would now be defined like this

pub struct Cache<'a, K, V> {
    map: NeptuneMap<K, V>,
    storage: Map<'a, K, V>,
}

I'll let you know how it goes! Really appreciate the assistance.

Alright so I've actually found a solution! Here is the final result, working well!

pub struct Cache<'s, 'k, K, V>
where
    for<'a> &'a K: Debug + PartialEq + Eq + PrimaryKey<'a>,
    K: Clone + Debug + PartialEq + Eq,
    V: Clone + Serialize + DeserializeOwned,
{
    map: NeptuneMap<K, V>,
    storage: Map<'s, &'k K, V>,
}

impl<'s, 'k, K, V> Cache<'s, 'k, K, V>
where
    for<'a> &'a K: Debug + PartialEq + Eq + PrimaryKey<'a>,
    K: Clone + Debug + PartialEq + Eq,
    V: Clone + Serialize + DeserializeOwned,
{
    pub fn new(storage: Map<'s, &'k K, V>) -> Self {
        Self { map: NeptuneMap::new(), storage }
    }
    pub fn must_get_mut(&mut self, deps: Deps<'_>, key: &K) -> CommonResult<&mut V> {
        match self.map.iter().position(|x| &x.0 == key) {
            Some(index) => Ok(&mut self.map.0[index].1),
            None => {
                let value = self.storage.load(deps.storage, key)?;
                self.map.insert(key.clone(), value);
                Ok(&mut self.map.last_mut().unwrap().1)
            }
        }
    }

    pub fn must_get(&mut self, deps: Deps<'_>, key: &K) -> CommonResult<V> {
        match self.map.iter().position(|x| &x.0 == key) {
            Some(index) => Ok(self.map.0[index].1.clone()),
            None => {
                let value = self.storage.load(deps.storage, key)?;
                self.map.insert(key.clone(), value);
                Ok(self.map.last_mut().unwrap().1.clone())
            }
        }
    }

    pub fn save(&mut self, deps: DepsMut<'_>) -> CommonResult<()> {
        for (key, value) in self.map.iter() {
            self.storage.save(deps.storage, key, value)?;
        }
        Ok(())
    }
}

The little bit of guidance you offered was just enough for me to figure it out. Thanks so much for your time!

As a rule of thumb, the only lifetime annotation you should use when "playing around with the code, trying to get lucky with lifetimes" is '_ - the anonymous lifetime. Sometimes, the lifetime elision rules do the wrong thing, and telling Rust explicitly "no, don't deduce a relationship between two things" can be helpful (e.g. if you're not borrowing from self, but from another argument, to form the return value, or if you've got a trait object whose default lifetime is being deduced as 'static, but you need it to be shorter).

2 Likes

I would say, as a rule of thumb: Never follow compiler suggestions for adding explicit lifetimes completely blindly. And, when adding explicit lifetimes, always make sure that

  • you know the meaning of each explicit lifetime
  • multiple places use the same lifetime parameter only if that restriction actually makes sense

Which means, in a "playing around with lifetimes setting" without understanding their meaning, that explicit lifetimes should either be avoided or at least take note of which lifetimes are restricted to be the same, and look back at those to check the sensibility of those restrictions later, especially once confusing compilation errors come up.


It's also important to just be aware in the first place, that “incorrect” lifetime annotations of a function can lead not only to immediate compilation failure in the function. Instead, while you're developing code, it can lead to errors much later, e. g. only once you try to use the function as intended. The arg: &'a mut SomeType<'a> pattern is a typical pattern where compilation errors often only really show up once you try to use the functions with such argument types.

4 Likes

On that note, if you're adding explicit lifetimes at all, you will benefit from reading and understanding this list of Rust lifetime misconceptions.

A key error I see far more than I'd like, including in my older code from before I got a good understanding of how lifetimes work, is naming too many lifetimes: you should only need to name lifetimes if you need to tell the compiler about the relationship between lifetimes (either "lives at least as long as" or "outlives", expressed as <'long, 'long: 'short>, or that an output borrows from an input (expressed by giving the output the same lifetime as the input it borrows from).

Edit: @quinedot pointed out that I'd swapped the two sides in the "outlives" relationship (which shows how often I actually need to express this). Fixed

1 Like

It's 'long: 'short (read "outlives" or "is valid for").

3 Likes