Borrow checker overly conservative when assigning to a parent reference

[silene]

Consider the following simplified testcase. This is some Rust translation of the C idiom while ((p = p->next)).

struct List { next: Option<Box<List>> }

fn bar(p: &mut List) {
  let n =
    match (*p).next {
      Some (ref mut q) => &mut **q,
      None => p
    };
  bar(n);
}

The code compiles fine. Unfortunately, it relies on a recursive call. Since Rust does not perform any tail call optimization, let us transform the code by hand. So, instead of calling the function recursively, we just update its argument inside a loop:

fn baz(mut p: &mut List) {
  loop {
    let n =
      match (*p).next {
        Some (ref mut q) => &mut **q,
        None => p
      };
    p = n;
  }
}

The code no longer compiles, since Rust detects 3 errors with it. Actually, only one matters (as can be seen by removing the loop), "cannot assign to p because it is borrowed". Given the borrowing rules as I understand them, the compiler is right to complain. Indeed, we have live references to values accessible by paths going through p, so accessing p is forbidden.

The rules seem overly conservative though, since no alias is being created when assigning a parent reference. Indeed, the only path to access the content pointed by p goes through p (since p is &mut); modifying p cannot break that invariant by adding a new path. At worst, modifying p could remove the only known path to the content previously pointed to. (Note that p is just a reference, so the assignment is atomic and without any side-effect.)

[silene]

For the sake of completeness, I should mention that adding a trivial let statement is sufficient for the loop to compile, but that should not be needed in a ideal world.

[arielb1]

@silene

This is well-known. If p had a destructor, it would be unsafe too.

[alexcrichton]

This can be worked around by doing something like let tmp = p at the top of the loop and then re-assigning to p later on through tmp. Otherwise this should be covered by rust-lang/rfcs#811, so closing in favor of that.

[silene]

Yes, let tmp = p is what I meant by "adding a trivial let statement".

However, I somehow doubt rust-lang/rfcs#811 will be of any help here. Even if borrows were dataflow-sensitive, the example above would still not pass. Indeed, the issue is not with the None branch (the RFC would be helpful there), it is with the Some branch. The example really involves two &mut borrows on p at the same time.

Below is a less simplified example: insertion in a sorted list. Hopefully, one day, the five extra lines (and their associated runtime cost) will no longer be needed to make the borrow checker happy.

fn insert<T:Ord>(v: T, mut l: &mut List<T>) {
  loop {
    match *l {
      None => break,
      Some(ref mut m) => {
        let m = &mut **m;
        match v.cmp(&m.elem) {
          std::cmp::Ordering::Less => break,
          _ => {} // should have been: l = &mut m.next
        }
      }
    };
    // the 5 next lines are needed only to make the borrow checker happy
    let m = l;
    match *m {
      None => panic!(),
      Some(ref mut m) => l = &mut m.next
    }
  }
  // do the insertion
}