Mutability in a recursive function

fn helper(left_to_dominoes: &mut BTreeMap<u8, VecDeque<Domino>>, left: u8, dominoes: &mut Vec<Domino>) -> bool {
    if left_to_dominoes[&left].is_empty() {
        return true;
    }
    if !left_to_dominoes.contains_key(&left) {
        return false;
    }

    let mut choices = left_to_dominoes.get_mut(&left).unwrap();
    for _ in 0..choices.len() {
        let (left, right) = choices.pop_front().unwrap();
        if helper(left_to_dominoes, right, dominoes) {
            return true;
        }
        choices.push_back((left, right));
    }
    return false;
}

Fails with:

error[E0499]: cannot borrow `*left_to_dominoes` as mutable more than once at a time
  --> src/lib.rs:37:19
   |
33 |     let mut choices = left_to_dominoes.get_mut(&left).unwrap();
   |                       ------------------------------- first mutable borrow occurs here
...
37 |         if helper(left_to_dominoes, right, dominoes) {
   |                   ^^^^^^^^^^^^^^^^ second mutable borrow occurs here
...
41 |         choices.push_back((left, right));
   |         -------------------------------- first borrow later used here

I read this thread, which is a very similar problem, but the accepted solution uses nightly and experimental API that I can't.

I also tried using RefCell, but it failed at runtime with the following error:

panicked at 'already borrowed: BorrowMutError

You could look up the key again after the recursive call, e.g.

fn helper(left_to_dominoes: &mut BTreeMap<u8, VecDeque<Domino>>, original_left: u8, dominoes: &mut Vec<Domino>) -> bool {
    if left_to_dominoes[&original_left].is_empty() {
        return true;
    }
    if !left_to_dominoes.contains_key(&original_left) {
        return false;
    }

    let mut choices = left_to_dominoes.get_mut(&original_left).unwrap();
    for _ in 0..choices.len() {
        let (left, right) = choices.pop_front().unwrap();
        if helper(left_to_dominoes, right, dominoes) {
            return true;
        }
        choices = left_to_dominoes.get_mut(&original_left).unwrap();  // <- this line is new
        choices.push_back((left, right));
    }
    return false;
}

Note that the code probably contains bugs. For example, the !left_to_dominoes.contains_key(&left) condition can never be true since left_to_dominoes[&left].is_empty() would have already panicked. And dominoes seems to be unused. And the fact that you get a panic when trying to use RefCell indicates that you might be modifying the same VecDeque at different recursion levels, which might be indicating a problem, depending on what this function is actually supposed to be doing, and in any case it’s fairly hard to reason about behavior.

1 Like

I get the exact same error with the new code. As for bugs, it's possible, I'll get to the point of actually solving the problem at hand once the compiler stops fighting me.

The code compiles if let mut choices = ... is moved into the loop.

Interesting. I don't get any compilation error:

Rust Playground

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.