Save mutable reference for later even when aliased

Question

I'm trying to implement something like a zipper but taking advantage of mutable references to avoid having to deconstruct and reconstruct the data structure as I move through it. I've got example code for an attempt with a linked list, although I'd ideally like to apply it to other structures, like trees.

pub enum List<T> {
    Empty,
    Cons { head: T, tail: Box<List<T>> },
}

pub struct Zipper<'a, T: 'a> {
    trail: Option<Box<Zipper<'a, T>>>,
    focus: &'a mut List<T>,
}

impl<'a, T: 'a> Zipper<'a, T> {
    pub fn down(&'a mut self) {
        match self.focus {
            &mut List::Empty => (),
            &mut List::Cons {
                tail: ref mut xs, ..
            } => {
                //We need a way to convince rust that we won't use oldZipper
                //until xs goes out of scope
                let oldZipper = std::mem::replace(
                    self,
                    Zipper {
                        trail: None,
                        focus: xs,
                    },
                );
                self.trail = Some(Box::new(oldZipper));
            }
        }
    }
}

The borrow checker is not happy with this:

error[E0499]: cannot borrow `*self` as mutable more than once at a time
  --> src/main.rs:21:21
   |
16 |                 tail: ref mut xs, ..
   |                       ---------- first mutable borrow occurs here
...
21 |                     self,
   |                     ^^^^ second mutable borrow occurs here
...
30 |     }
   |     - first borrow ends here

This isn't surprising: if we have a zipper focused on a list and call down on it, we get zipper with a mutable reference to the tail of that list, so we have mutable aliasing.

However, if we never use the Zipper's trail before focus goes out of scope, we'll never be able to "see" the mutable aliasing. This seems analogous to normal mutable borrowing: you can't use the variable you borrowed from until the borrow goes out of scope.

Is there some way to explain this to the borrow checker? If you want to "explain" to the borrow checker that borrowing two non-overlapping slices from an array is okay, you can use split_at: is there some corresponding function that will enforce that trail is never used before focus goes out of scope, and in doing so, satisfies the borrow checker?

Answer 1

In order to achieve your goal, we need to get rid of the mutable reference in the Zipper struct. We can use mutable raw pointers instead: they let us mutate their referent, and we can more than one such pointer pointing at a particular object, but dereferencing them is unsafe.

Here's the code:

use std::mem;
use std::marker::PhantomData;

pub enum List<T> {
    Empty,
    Cons { head: T, tail: Box<List<T>> },
}

pub struct Zipper<'a, T: 'a> {
    trail: Option<Box<Zipper<'a, T>>>,
    focus: *mut List<T>,
    _list: PhantomData<&'a mut List<T>>,
}

impl<'a, T: 'a> Zipper<'a, T> {
    pub fn new(list: &'a mut List<T>) -> Zipper<'a, T> {
        Zipper {
            trail: None,
            focus: list as *mut List<T>,
            _list: PhantomData,
        }
    }

    pub fn down(&mut self) {
        unsafe {
            match *self.focus {
                List::Empty => (),
                List::Cons {
                    tail: ref mut xs, ..
                } => {
                    let old_zipper = mem::replace(
                        self,
                        Zipper::new(xs),
                    );
                    self.trail = Some(Box::new(old_zipper));
                }
            }
        }
    }
}

fn main() {
    let mut list = List::Cons { head: 1, tail: Box::new(List::Empty) };
    let mut zipper = Zipper::new(&mut list);
    zipper.down();
    zipper.down();
}

The focus field in the Zipper struct is now a *mut List<T>. Because this is a raw pointer, we can copy it around freely. This resolves the compiler error you had in Zipper::down. There's also a new field, _list, of type PhantomData<&'a mut List<T>>. PhantomData is a special type that is meant to tell the compiler "pretend I'm storing/owning a T, even though I'm not". Without this field, the compiler would complain that the lifetime parameter 'a is unused.

Notice that Zipper::new still expects a &'a mut List<T> as a parameter: this allows Zipper to provide a safe interface by requiring the caller to have a unique mutable reference to the List<T>, a fact we can use to declare that the other unsafe operations in the struct are indeed safe since we have full knowledge of the available mutable references. As far as the compiler is concerned, a Zipper is mutably borrowing the List; if you try to mutate a List while a Zipper on the List is in scope, you'll get an error that the List is already mutably borrowed.

---

You haven't shown any code that would let the user get a reference to the Zipper's focus. I've been thinking of a possible implementation that would be unsafe, and it's tempting to go that route, but the compiler won't tell you it's wrong. Let me show you:

impl<'a, T: 'a> Zipper<'a, T> {
    pub fn focus(&mut self) -> &'a mut List<T> {
        unsafe { &mut *self.focus }
    }
}

It's tempting to return a &'a mut List<T> because that's what we were given. However, it's wrong because the return value's lifetime is not bound to self in any way, which means that we could call focus twice to obtain two mutable references to the same List<T>. If we still had a &'a mut List<T> in Zipper, the compiler would tell us if we tried to return a &'a mut List<T> (unless we used unsafe code to work around it). A correct implementation would be:

impl<'a, T: 'a> Zipper<'a, T> {
    pub fn focus(&mut self) -> &mut List<T> {
        unsafe { &mut *self.focus }
    }
}

In this implementation, the Zipper will be mutably borrowed as long as the returned &mut List<T> is around, which means we can't call focus (or down) until the &mut List<T> goes out of scope.