Borrow checker prohibits two mutually exclusive mutable borrows

Hi. I hit a wall today with borrow checker in the current Rust stable (v1.50).

I was trying to implement a tree-like structure and I needed a method that would return mutable reference to a leaf corresponding to a given path. The details are not important though. I managed to create a minimal code example that can simulate the compilation error I got.

Consider a structure like this:

struct LinkedList {
    next: Option<Box<Self>>,
}

Now let's say that we'd like to implement a method that will return the last element in our linked list. Probably the most straight-forward way would be something like this:

impl LinkedList {
    fn last(&mut self) -> &mut Self {
        if let Some(next) = self.next.as_mut() {
            return next.last();
        }

        self
    }
}

If we try to compile it, we'll end up with an error like this:

error[E0499]: cannot borrow `*self` as mutable more than once at a time
  --> mod.rs:88:9
   |
83 |     fn last(&mut self) -> &mut Self {
   |              - let's call the lifetime of this reference `'1`
84 |         if let Some(next) = self.next.as_mut() {
   |                             --------- first mutable borrow occurs here
85 |             return next.last();
   |                    ------------ returning this value requires that `self.next` is borrowed for `'1`
...
88 |         self
   |         ^^^^ second mutable borrow occurs here

The thing is that the two mutable borrows the borrow checker is complaining about cannot happen at the same time. Obviously, the first mutable borrow created by self.next.as_mut() can outlive the scope of the method but if it does, the second mutable borrow won't happen. On the other hand, if self.next is None, then the first mutable borrow should end right before the second mutable borrow. Or at least that's how I understand non-lexical lifetimes.

This simple method can be rewritten like this:

impl LinkedList {
    fn last(&mut self) -> &mut Self {
        if self.next.is_some() {
            self.next.as_mut().unwrap().last()
        } else {
            self
        }
    }
}

which will compile without any issues. But creating more complex methods can be quite challenging.

My question is: Am I missing something? Is it a bug? Or is it simply something that the current borrow checker cannot handle?

It is a bug / known limitation of the current version of the borrow checked (NLL), which is planned to be superseded by Polonius, which ought to fix this kind of things (feel free to try and run cargo +nightly rustc -- -Z polonius to see if your first snippet compiles there).

6 Likes

An alternate workaround is to use a ref mut pattern. This compiles with the latest stable compiler:

fn last(&mut self) -> &mut Self {
    if let Some(ref mut next) = self.next {
        return next.last();
    }
    self
}

(See also this recent topic.)

1 Like

Good to know. Polonius seems to be able to handle it correctly. Thank you both.