Mutable borrow issue while looping with reference pivot

Question

struct A {
    next: Option<Box<A>>,
}

impl A {
    fn grow(&mut self) {
        self.next = Some(Box::new(A { next: None }));
    }
}

fn main() {
    let mut a = A{ next: Some(Box::new(A { next: None }))};
    let mut p = &mut a;
    // attempt to append to the list
    loop {
        match &mut p.next {
            Some(n) => p = n,
            None => {
                p.grow();
                break;
            }
        }
    }
}

The code above is the simplified logic from a more complex data structure that is able to reproduce the borrow checker complaint:

error[E0499]: cannot borrow `*p` as mutable more than once at a time
  --> t.rs:19:17
   |
16 |         match &mut p.next {
   |               ----------- first mutable borrow occurs here
...
19 |                 p.grow();
   |                 ^
   |                 |
   |                 second mutable borrow occurs here
   |                 first borrow later used here

error: aborting due to previous error

Why is p still thought to be mutably borrowed in the match case? And, trying to move p.update() out of the loop doesn't help:

fn main() {
    let mut a = A{ next: Some(Box::new(A { next: None }))};
    let mut p = &mut a;
    // attempt to append to the list
    loop {
        match &mut p.next {
            Some(n) => p = n,
            None => {
                break;
            }
        }
    }
    p.grow();
}

I got the same error in this case. I know p = n is causing the problem because it compiles through without it, but why?

Answer 1

Here is my take on what's going on. To explain it, I simplified your code a little, without changing the idea:

fn main() {
    let mut a = A{ next: Some(Box::new(A { next: None }))};
    let mut p = &mut a;
    let next = &mut p.next;
    if let Some(n) = next {
        p = n;
    }

    p.grow();
}

This code produces the same error as yours. What's more interesting, you cannot use p in any way at the end of main. Even println!("{:?}", p) produces the same error.

The compiler checks all the ways the code can execute and sees that at the point when p.grow() is called, p can either point to a, or to a.next.as_mut() (I mean inner value of a.next option struct). But p.grow() requires using one of this references.

If p == &mut a, and we call p.grow(), then the reference to a.next.as_mut() becomes invalid, thus error. If p == a.next.as_mut(), and we call p.grow(), we reference &mut a two times, as the first borrow cannot be dropped still.

If you don't assign p = n, there is no such issue, because there is only one valid reference, which the compiler can use when p.grow() is called.

In this example actually there 3 ways to prevent compiler error:

1. Remove p = n assignment.
2. Move p.grow() inside if let block, thus making sure that at the moment of the call p references the inner value.
3. Exiting main in case next is Some:

if let Some(n) = next {
  p = n;
} else {
  return;
}

p.grow();

The later works because compiler knows for sure that at the point of p.grow() call first borrow is not needed and can be dropped, and p can point only to the inner value.

The problem in the original question is same. Compiler must know for sure what p references at the point of the p.grow() call.

In the solution, provided by Lagerbaer, p can reference only one certain value when p.grow() is called (there is no reference to p.next at this time), thus it works:

    let mut p = &mut a;
    // attempt to append to the list
    loop {
        match p.next {
            Some(ref mut n) => p = n,
            None => {
                p.grow();
                break;
            }
        }
    }