5

I'm attempting to implement a dynamic programming problem in Rust to gain familiarity with the language. Like many dynamic programming problems, this uses memoization to reduce the running time. Unfortunately, my first-pass solution yields errors. I've pared the code down to the following. Warning - it's now a bit nonsensical:

use std::collections::HashMap;

fn repro<'m>(memo: &'m mut HashMap<i32, Vec<i32>>) -> Option<&'m Vec<i32>> {
    {
        let script_a = repro(memo);
        let script_b = repro(memo);
    }

    memo.get(&0)
}

fn main() {}

The compilation error is:

error[E0499]: cannot borrow `*memo` as mutable more than once at a time
 --> src/main.rs:6:30
  |
5 |         let script_a = repro(memo);
  |                              ---- first mutable borrow occurs here
6 |         let script_b = repro(memo);
  |                              ^^^^ second mutable borrow occurs here
7 |     }
  |     - first borrow ends here

Why is the variable memo borrowed multiple times? In my view, it should be borrowed once when I compute script_a, then that borrow ends, then it gets borrowed again for script_b.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366

2 Answers2

4

Currently borrows last for the block they are defined in (#9113 might change this if implemented)

The problem is that script_a (that holds an immutable reference to a map) is valid for the whole block and you try to use a mutable reference to the same map:

let script_a = repro(memo);
let script_b = repro(memo);
// script_a is still alive
Arjan
  • 19,957
  • 2
  • 55
  • 48
  • If it's the fact that `script_a` is holding an immutable reference, any idea why the error message would say that it wants to have multiple mutable references? I'd expect a variant of the cannot get mutable ref while an immutable ref lives error message. – Shepmaster Jul 07 '14 at 20:55
  • @Shepmaster the lifetime is on an `&mut` input parameter, that is, the `repro` call is taking a mutable borrow of `memo`. – huon Jul 07 '14 at 22:40
  • @dbaupp As I understand it, `repro` gets a mutable reference, but that reference is no longer alive after the first call to `repro`. However, `repro` returns an *immutable* reference from the HashMap, which is held by `script_a`. At the time of the second call, a *mutable* reference is needed, but there's an outstanding *immutable* reference (`script_a`). Thus I would expect the error to indicate I cannot get a mutable reference while an immutable reference is alive. – Shepmaster Jul 08 '14 at 16:01
  • 1
    @Shepmaster, yes, but the `&` was constructed "by magic" (through the black box of `repro`) out of a mutable one, that is, the compiler is connecting borrows via lifetimes, not via types, i.e. if you have a `'a` that came out of a `&mut`, then it's a "mutable lifetime". [This example](http://is.gd/EN7USM) demonstrates that it is handled as a `&mut` borrow, because the second `&` borrow is illegal. Maybe the error message could be tweaked and the behaviour relaxed, but I'm not sure it's valid & it would have to be a special case for `&'a`, a `Foo<'a>` would need to assume mutable borrowing. – huon Jul 09 '14 at 04:58
  • (Even if `Foo` was just a wrapper around `&`, `struct Foo<'a> { x: &'a ... }`.) – huon Jul 09 '14 at 04:59
-1

The bigger problem is the infinite loop. Anyway let script_a is a reference to data inside the hash map, so it's still borrowed by the time you call let script_b = repro(memo);.

A.B.
  • 15,364
  • 3
  • 61
  • 64
  • 1
    Yes, the infinite loop is why I said "Warning - it's now a bit nonsensical" :-). If I understand you correctly, you agree with @arjan's assesment that `script_a` holds a reference to data from the HashMap; any idea why it complains about multiple *mutable* references as opposed to one mutable and one immutable? – Shepmaster Jul 07 '14 at 20:59
  • Well I can't give you an exact answer without some guessing, but it doesn't make a difference either way, you can't mutably borrow something that's already borrowed (mutably or not). What are you trying to do in your real code? – A.B. Jul 07 '14 at 21:12