Mutable borrow from HashMap and lifetime elision

Question

Chapter 13 of the Rust book (2nd edition) contains an example of a simple calculation cache. Cacher takes the calculation function as a constructor param, and will cache the result - after the first call, it will not invoke the function again, but simply return the cached result:

struct Cacher<T>
where
    T: Fn(u32) -> u32,
{
    calculation: T,
    value: Option<u32>,
}

impl<T> Cacher<T>
where
    T: Fn(u32) -> u32,
{
    fn new(calculation: T) -> Cacher<T> {
        Cacher {
            calculation,
            value: None,
        }
    }

    fn value(&mut self, arg: u32) -> u32 {
        match self.value {
            Some(v) => v,
            None => {
                let v = (self.calculation)(arg);
                self.value = Some(v);
                v
            }
        }
    }
}

It is very limited, and there are a couple of improvement suggestions in the book, left as an exercise for the reader.

So I'm trying to make it cache multiple values. The Cacher holds a HashMap with result values, instead of just one value. When asked for a value, if it has in the map (cache), return it. Otherwise, calculate it, store it the cache, and then return it.

The cacher takes references, because it doesn't want to own the inputs. When using it (see unit test), I'm borrowing, because the cacher owns the results.

Here's my attempt:

use std::collections::HashMap;

struct Cacher<T>
where
    T: Fn(&u32) -> u32,
{
    calculation: T,
    values: HashMap<u32, u32>,
}

impl<T> Cacher<T>
where
    T: Fn(&u32) -> u32,
{
    fn new(calculation: T) -> Cacher<T> {
        Cacher {
            calculation,
            values: HashMap::new(),
        }
    }

    fn value(&mut self, arg: u32) -> &u32 {
        let values = &mut self.values;
        match values.get(&arg) {
            Some(v) => &v,
            None => {
                let v = (self.calculation)(&arg);
                values.insert(arg, v);
                &values.get(&arg).unwrap()
            }
        }
    }
}

#[test]
fn call_with_different_values() {
    let mut c = Cacher::new(|a| a + 1);
    let v1 = c.value(1);
    assert_eq!(*v1, 2);
    let v2 = c.value(2);
    assert_eq!(*v2, 3);
}

Compiler output:

22 |     fn value(&mut self, arg: u32) -> &u32 {
   |              - let's call the lifetime of this reference `'1`
23 |         let values = &mut self.values;
24 |         match values.get(&arg) {
   |               ------ immutable borrow occurs here
25 |             Some(v) => &v,
   |                        -- returning this value requires that `*values` is borrowed for `'1`
...
28 |                 values.insert(arg, v);
   |                 ^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

I'm borrowing self.values as mutable on line 23. However, when I try to use it on the following line, I get the "immutable borrow" error. How is match values.get(arg) an immutable borrow of values ? Didn't the borrowing already happen ?

There is also the error for line 25. From my understanding of lifetime elision rules, the 3rd one should apply here - we have &mut self as a method parameter, so it's lifetime should be automatically assigned to the return value ?

Your case could be even simpler, by not returning a &u32 but u32 instead. — hellow
value function can be replaced with one-liner: self.values.entry(arg).or_insert((self.calculation)(&arg)) — Laney

Markus Klein Markus Klein · Accepted Answer · 2019-05-17T15:47:53

I do not think that you are going to be happy with that signature:

fn value(&mut self, arg: u32) -> &u32

Without lifetime elision this is read as:

fn value(&'a mut self, arg: u32) -> &'a u32

Even if you implement it correctly this has huge implications. For example you can not call value again as long as old results are still in use. And rightly so, after all nothing is preventing the function body to delete old values from the cache.

Better to follow @hellow advice and make the return type u32.

Another misunderstanding: Just because you borrowed values already, does not mean you cannot borrow from it again.

Now to answer your original question: The compiler is not lying to you values.get(arg) is indeed an immutable borrow of values. The technical explanation is that the signature of that method call is (simplified) get(&self, k: &Q) -> Option<&V>. So the borrow of self (aka values) is valid as long as &V can still be referenced. &V however needs to be valid for the entire function body at least (so it can be returned). Now you tried to mutably borrow in the None case which means &V never existed in the first place. So if the compiler gets smarter it may allow your code to run, but for now (1.34.0) it isn't.

Mutable borrow from HashMap and lifetime elision

1 Answers