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?