I'm trying to write a function that can both read and write from a cache, but I'm running into a problem where the compiler says I can't both mutably and immutably borrow the cache.
I've read through https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html , https://naftuli.wtf/2019/03/20/rust-the-hard-parts/ and random stack overflow/Reddit posts, but I can't see how to apply what they say to this code.
use std::collections::HashMap;
struct CacheForMoves {
set_of_moves: Vec<usize>,
cache: HashMap<usize, Vec<Vec<usize>>>,
}
impl CacheForMoves {
fn new(set_of_moves: Vec<usize>) -> CacheForMoves {
CacheForMoves {
set_of_moves: set_of_moves,
cache: HashMap::new(),
}
}
fn get_for_n(&self, n: usize) -> Option<&Vec<Vec<usize>>> {
self.cache.get(&n)
}
fn insert_for_n(&mut self, n: usize, value: Vec<Vec<usize>>) {
self.cache.insert(n, value);
}
}
fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
return match cache.get_for_n(n) {
Some(result) => result,
None => stairs(cache, n - 1),
};
}
fn main() {
let mut cache = CacheForMoves::new(vec![1, 2]);
cache.insert_for_n(1, vec![]);
let result = stairs(&mut cache, 4);
println!("Found {} possible solutions: ", result.len());
for solution in result {
println!("{:?}", solution);
}
}
This produces the following compile error:
error[E0502]: cannot borrow `*cache` as mutable because it is also borrowed as immutable
--> stairs2.rs:28:18
|
26 | return match cache.get_for_n(n) {
| ----- immutable borrow occurs here
27 | Some(result) => result,
28 | None => stairs(cache, n - 1)
| ^^^^^ mutable borrow occurs here
29 | }
30 | }
| - immutable borrow ends here
error: aborting due to previous error
For more information about this error, try `rustc --explain E0502`.
I don't understand why it thinks I'm immutably borrowing cache on line 26. My understanding is main creates an instance of CacheForMove and owns that value. It's mutably-lending the value to the stairs function, and so now stairs has mutably borrowed the value. I expected to be able to invoke both get_for_n and insert_for_n on that mutably-borrowed reference.
In this SO question, the OP wants to have their update for one key in the cache depend on the value of a different key in the cache. I do eventually want to do that to, but I'm running into a problem before I get to that point. I'm not looking at other entries in the cache in order to compute "this" entry. The answers in that question says that they would need to split getting from the cache from inserting into the cache like so:
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
}
However, I believe my code already splits getting from inserting, and yet I still get a compile error.
Even if I adapt the above example to match my API:
fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
if let Some(entry) = cache.get_for_n(n) {
return entry;
}
let res = stairs(cache, n - 1);
cache.insert_for_n(n, res.clone());
res
}
I still get the same error:
error[E0502]: cannot borrow `*cache` as mutable because it is also borrowed as immutable
--> src/main.rs:29:15
|
25 | fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
| - let's call the lifetime of this reference `'1`
26 | if let Some(entry) = cache.get_for_n(n) {
| ----- immutable borrow occurs here
27 | return entry;
| ----- returning this value requires that `*cache` is borrowed for `'1`
28 | }
29 | let res = stairs(cache, n - 1);
| ^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
error[E0499]: cannot borrow `*cache` as mutable more than once at a time
--> src/main.rs:30:5
|
25 | fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
| - let's call the lifetime of this reference `'1`
...
29 | let res = stairs(cache, n - 1);
| ----- first mutable borrow occurs here
30 | cache.insert_for_n(n, res.clone());
| ^^^^^ second mutable borrow occurs here
31 | res
| --- returning this value requires that `*cache` is borrowed for `'1`
error: aborting due to 2 previous errors
Some errors occurred: E0499, E0502.
For more information about an error, try `rustc --explain E0499`.
In that SO question, the OP states they are unwilling to use a struct, and the answers provided use some combination of unsafe, mutex, lazy_static!, RefCell, and so on.
I have the opposite issue. I am perfectly willing to use a struct (and in fact, I am using one in my original problem statement), but using unsafe, mutex, lazy_static!, and so on sound much more dangerous or complex to me.
The OP of that question implies that if we could use a struct, the solution would be obvious. I would like to learn that obvious solution.
The matched value is not used by whatever the stairs function does. In the implementation shown in the original problem statement:
fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
return match cache.get_for_n(n) {
Some(result) => result,
None => stairs(cache, n - 1),
};
}
I immutably borrow cache to get a cached value out of it. If there is a value available, I return it (without recursively calling stairs again). If there is no value, I expect None to be copyable (i.e. I can have my own copy of None on my stack; I no longer need to reference any data in cache at all). At this point, I expect to be able to safely mutably borrow cache to invoke stairs(cache, n-1), because there are no other borrows (mutable or immutable) to cache.
To really drive this point home, consider this alternative implementation of the stairs function:
fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
{
let maybe_result = cache.get_for_n(n);
if maybe_result.is_some() {
return maybe_result.unwrap();
}
}
return stairs(cache, n - 1);
}
Here I've used a pair of curly braces to limit the scope of the immutable borrow. I perform an immutable borrow to populate maybe_result, and check whether it is a Some. If it is, I unwrap the internal value and return it. If not, I end my scope, and thus all borrows have gone out of scope and are now invalid. There are no borrows happening anymore.
Then, I try to mutably borrow cache to recursively invoke stairs. This should be the only borrow happening at this point, and so I expect this borrow to succeed, but the compiler tells me:
error[E0502]: cannot borrow `*cache` as mutable because it is also borrowed as immutable
--> src/main.rs:32:12
|
25 | fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
| - let's call the lifetime of this reference `'1`
26 | {
27 | let maybe_result = cache.get_for_n(n);
| ----- immutable borrow occurs here
28 | if maybe_result.is_some() {
29 | return maybe_result.unwrap();
| --------------------- returning this value requires that `*cache` is borrowed for `'1`
...
32 | return stairs(cache, n - 1);
| ^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
error: aborting due to previous error
For more information about this error, try `rustc --explain E0502`.
I think I've got this figured out, so recording my answer in case someone else gets stuck with the same problem. This compiles and runs:
use std::collections::HashMap;
struct CacheForMoves {
set_of_moves: Vec<usize>,
cache: HashMap<usize, Vec<Vec<usize>>>
}
impl CacheForMoves {
fn new(set_of_moves: Vec<usize>) -> CacheForMoves {
CacheForMoves {
set_of_moves: set_of_moves,
cache: HashMap::new()
}
}
fn get_for_n(&self, n: usize) -> Option<&Vec<Vec<usize>>> {
self.cache.get(&n)
}
fn insert_for_n(&mut self, n: usize, value: Vec<Vec<usize>>) {
self.cache.insert(n, value);
}
}
fn stairs(cache: &mut CacheForMoves, n: usize) -> Vec<Vec<usize>> {
return match cache.get_for_n(n) {
Some(result) => result.clone(),
None => stairs(cache, n - 1)
}
}
fn main() {
let mut cache = CacheForMoves::new(vec![1, 2]);
cache.insert_for_n(1, vec![]);
let result = stairs(&mut cache, 4);
println!("Found {} possible solutions: ", result.len());
for solution in result {
println!("{:?}", solution);
}
}
There are 2 main changes:
stairs no longer returns &Vec<Vec<usize>> and instead returns Vec<Vec<usize>>Some(result) case, we return result.clone() instead of result.2 is a consequence of 1, so let's focus on why 1 is necessary and why it fixes the problem. The HashMap owns the Vec<Vec<usize>>, and so when the original implementation returned a &Vec<Vec<usize>>, it was returning a reference to a memory location owned by the HashMap. If someone were to mutate the HashMap, say by deleting an entry, since the HashMap owns the Vec<Vec<usize>>, the HashMap would conclude that it's safe to deallocate the memory being used by the Vec<Vec<usize>>, and I'd end up with a dangling reference.
I can only return a &Vec<Vec<usize>> as long as I can guarantee no one will mutate the HashMap for as long as the &Vec<Vec<usize>> reference exists, and since I'm returning the &Vec<Vec<usize>> reference to my caller, that essentially means I need to guarantee that the HashMap is immutable forever (since I have no idea what the caller might do).