How can I mutate other elements of a HashMap when

Question

I'd like to use a HashMap to cache an expensive computation that's dependent on other entries in the map. The entry pattern only provides a mutable reference to the matched value, but not to the rest of the HashMap. I'd really appreciate feedback on a better way to solve this (incorrect) toy example:

use std::collections::HashMap;
use std::collections::hash_map::Entry::{Occupied, Vacant};

fn compute(cache: &mut HashMap<u32, u32>, input: u32) -> u32 {
    match cache.entry(input) {
        Vacant(entry) => if input > 2 {
            // Trivial placeholder for an expensive computation.
            *entry.insert(compute(&mut cache, input - 1) +
                          compute(&mut cache, input - 2))
        } else {
            0
        },
        Occupied(entry) => *entry.get(),
    }
}

fn main() {
    let mut cache = HashMap::<u32, u32>::new();
    let foo = compute(&mut cache, 12);
    println!("{}", foo);
}

(playground)

The issue with the above snippet is that cache.entry borrows cache immutably, but I would like to update cache as well.

Answer 1

First things first: your example can be simplified with the .or_insert_with() method that takes a closure which returns the value to insert at that key.

It is not possible with the entry pattern to solve your problem, because you mutably borrow the cache first in your entry, and afterwards in your match (or closure). You can try it, if you use a RefCell (which just moves the borrowing from compiletime to runtime) it will throw a panic.

To actually solve your problem, you have to split getting and inserting the value, like this:

fn compute(cache: &mut HashMap<u32, u32>, input: u32) -> u32 {
    if let Some(entry) = cache.get(&input) {
        return *entry;
    }

    let res = if input > 2 {
        // Trivial placeholder for an expensive computation.
        compute(cache, input - 1) + compute(cache, input - 2)
    } else {
        0
    };
    cache.insert(input, res);
    res
}

(if you are on nightly and using ![feature(nll)] you can omit the return and use else on the if let branch to make it a little bit cleaner.

Answer 2

hellow has shown how to get working code, but I want to dive a bit more into why your code does not compile.

The code you have proposed cannot be statically verified to be memory safe. It's entirely possible that your recursive calls attempt to access the same index. Check out this simplified code for one possibility:

use std::collections::{hash_map::Entry, HashMap};

fn compute(cache: &mut HashMap<u32, u32>) {
    if let Entry::Vacant(_entry) = cache.entry(42) {
        let _aliased_mutable_reference = cache.get_mut(&42).unwrap();
    }
}

This now has two mutable references pointing to the same value, violating the rules of references.

Additionally, what if the inner call used entry and it didn't exist?

use std::collections::{hash_map::Entry, HashMap};

fn compute(cache: &mut HashMap<u32, u32>) {
    if let Entry::Vacant(entry1) = cache.entry(42) {
        if let Entry::Vacant(entry2) = cache.entry(41) {
            entry2.insert(2);
            entry1.insert(1);
        }
    }
}

Now, when you insert the value into the map via entry2, the map may reallocate the underlying memory, invalidating the reference held by entry1, violating the other rule of references.

Rust has prevented you from introducing two possible types of memory unsafety into your program; just like it was designed to do.