Why don't I need to explicitly provide the borrowed variable?

Question

I just wrote a small Rust program that calculates Fibonacci numbers and remembers the calculations. It works, but I'm a little confused why, especially a recursive call. (This is also probably not idiomatic.)

Here is the program:

use std::collections::HashMap; fn main() { let n = 42; // hardcoded for simplicity let mut cache = HashMap::new(); let answer = fib(n, &mut cache); println!("fib of {} is {}", n, answer); } fn fib(n: i32, cache: &mut HashMap<i32,i32>) -> i32 { if cache.contains_key(&n) { return cache[&n]; } else { if n < 1 { panic!("must be >= 1") } let answer = if n == 1 { 0 } else if n == 2 { 1 } else { fib(n - 1, cache) + fib(n - 2, cache) }; cache.insert(n, answer); answer } } 

Here is how I understand what is happening:

• In main , let mut cache means "I want to be able to mutate this hash (or reset the variable)."
• When main calls fib , it passes &mut cache to say, "I give you this, and you are allowed to mutate it."
• In the signature fib , cache: &mut Hashmap means "I expect a volatile HashMap to be provided - borrow it with mutation permission"

(Please correct me if I am wrong.)

But when fib recurses, calling fib(n -1, cache) , I do not need to use fib(n -1, &mut cache) , and I get the error message: "I can not borrow the immutable local cache variable as mutable." BUT? This is not an immutable local variable, this is mutable borrowing - right?

If I try fib(n - 1, &cache) , I get a slightly different error:

 error: mismatched types: expected `&mut std::collections::hash::map::HashMap<i32, i32>`, found `&&mut std::collections::hash::map::HashMap<i32, i32>` 

Which looks like this: "I was expecting a mutable link and got a link to a mutable link."

I know that fib lending is in a recursive call, because if he renounced ownership, he would not be able to call cache.insert afterwards. And I know this is not a special case for recursion, because if I define fib2 to be almost identical to fib , I can rewrite them with each other, and it works great.

Why don't I need to explicitly provide a borrowed mutable variable ?

Answer 1

Your three points are pretty much spot-on. When the compiler does not allow you to pass &mut cache , this is because the value is actually already borrowed. The cache type is &mut HashMap<i32, i32> , so passing &mut cache yields a value of &mut &mut HashMap<i32, i32> . Just passing cache leads to the expected type.

The specific error message cannot borrow immutable local variable cache as mutable triggered because the cache variable itself has not been changed, although the memory it points to ( HashMap ). This is because declaring the cache: &mut HashMap<i32, i32> argument cache: &mut HashMap<i32, i32> does not declare the mut variable. This is similar to how a let differs in variability from a let mut . Rust supports mutable arguments, which in this case look like mut cache: &mut HashMap<i32, i32> .