Immutable borrow when using .get on hashmap

I'm a beginner, and I'm on Chapter 13.1 of the book. The following appears as a suggested exercise:

Try modifying Cacher to hold a hash map rather than a single value. The keys of the hash map will be the arg values that are passed in, and the values of the hash map will be the result of calling the closure on that key. Instead of looking at whether self.value directly has a Some or a None value, the value function will look up the arg in the hash map and return the value if it’s present. If it’s not present, the Cacher will call the closure and save the resulting value in the hash map associated with its arg value.

Here is my attempt (what I think is the relevant part):

struct Cacher<T,K,V> where T: Fn(K) -> V,
K: std::cmp::Eq + std::hash::Hash,
{
        calculation: T,
        values: HashMap<K,V>,
    }

impl<T,K,V> Cacher<T,K,V> where T: Fn(K) -> V,
K: std::cmp::Eq + std::hash::Hash,
{

    fn new(calculation: T) -> Cacher<T,K,V> {
        Cacher {
            calculation,
            values: HashMap::new(),
        }
    }

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

}

However I get the following errors:

error[E0502]: cannot borrow `self.values` as mutable because it is also borrowed as immutable
  --> src/main.rs:37:17
   |
32 |     fn value(&mut self, arg: K) -> &V {
   |              - let's call the lifetime of this reference `'1`
33 |        match self.values.get(&arg) {
   |              ----------- immutable borrow occurs here
34 |             Some(v) => v,
   |                        - returning this value requires that `self.values` is borrowed for `'1`
...
37 |                 self.values.insert(arg,result);
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

error[E0382]: use of moved value: `arg`
  --> src/main.rs:37:36
   |
32 |     fn value(&mut self, arg: K) -> &V {
   |                         --- move occurs because `arg` has type `K`, which does not implement the `Copy` trait
...
36 |                 let result = (self.calculation)(arg);
   |                                                 --- value moved here
37 |                 self.values.insert(arg,result);
   |                                    ^^^ value used here after move

error[E0515]: cannot return reference to local variable `result`
  --> src/main.rs:38:17
   |
38 |                 &result
   |                 ^^^^^^^ returns a reference to data owned by the current function

error[E0382]: borrow of moved value: `result`
  --> src/main.rs:38:17
   |
36 |                 let result = (self.calculation)(arg);
   |                     ------ move occurs because `result` has type `V`, which does not implement the `Copy` trait
37 |                 self.values.insert(arg,result);
   |                                        ------ value moved here
38 |                 &result
   |                 ^^^^^^^ value borrowed here after move

error: aborting due to 4 previous errors

Why is self.values borrowed immutably when I do self.values.get()? Isn't self passed as a mutable reference to the value function? How would I go about fixing this? I am a beginner. I will greatly appreciate it if someone can help me understand the concept better thanks.

Please check out our post on formatting here.

Thanks I've edited it.

The value v in the Some branch contains a borrowed reference into the hash map. Inserting into the map would invalidate this reference, so it is not allowed while the reference is alive.

The compiler should see that the reference is not in scope in the None branch, and allow you to mutate the HashMap there. In a future version it will, but the current borrow checker is not smart enough. The standard library has some special APIs to work around this, which we'll see below.

The other error happens because the calculation function consumes its argument. You could fix that by passing it a reference (&K instead of K), or by adding a K: Clone bound and cloning the argument as necessary.

With K: Clone, you can solve both errors by using the HashMap::entry API (Playground):

impl<T,K,V> Cacher<T,K,V> where
    T: Fn(K) -> V,
    K: Eq + Hash + Clone, // changed bounds on `K`
{
    fn value(&mut self, arg: K) -> &V {
        let arg2 = arg.clone();
        let calculation = &self.calculation;
        
        self.values.entry(arg)
            .or_insert_with(|| calculation(arg2))
    }
}

Unfortunately, that requires cloning the key unconditionally, which could be expensive (depending on its type). If you want to avoid cloning the key unnecessarily, you'll need Entry::or_insert_with_key, which is available in nightly Rust with a feature gate, or by using the hashbrown crate directly (Playground):

    fn value(&mut self, arg: K) -> &V {
        let calculation = &self.calculation;
        self.values.entry(arg)
            .or_insert_with_key(|k| calculation(k.clone()))
    }

And if you want to avoid cloning the key entirely, you'll also need to make calculation take an &K reference (Playground):

impl<T,K,V> Cacher<T,K,V> where
    T: Fn(&K) -> V, // changed bound on `T`
    K: Eq + Hash,
{
    fn value(&mut self, arg: K) -> &V {
        self.values.entry(arg)
            .or_insert_with_key(&self.calculation)
    }
}
2 Likes

Thank you very much for the explanation.