Splitting Borrows

The mutual exclusion property of mutable references can be very limiting whenworking with a composite structure. The borrow checker understands some basicstuff, but will fall over pretty easily. It does understand structssufficiently to know that it’s possible to borrow disjoint fields of a structsimultaneously. So this works today:

struct Foo {
    a: i32,
    b: i32,
    c: i32,
}
let mut x = Foo {a: 0, b: 0, c: 0};
let a = &mut x.a;
let b = &mut x.b;
let c = &x.c;
*b += 1;
let c2 = &x.c;
*a += 10;
println!("{} {} {} {}", a, b, c, c2);

However borrowck doesn’t understand arrays or slices in any way, so this doesn’twork:

let mut x = [1, 2, 3];
let a = &mut x[0];
let b = &mut x[1];
println!("{} {}", a, b);

error[E0499]: cannot borrow `x[..]` as mutable more than once at a time
 --> src/lib.rs:4:18
  |
3 |     let a = &mut x[0];
  |                  ---- first mutable borrow occurs here
4 |     let b = &mut x[1];
  |                  ^^^^ second mutable borrow occurs here
5 |     println!("{} {}", a, b);
6 | }
  | - first borrow ends here
error: aborting due to previous error

While it was plausible that borrowck could understand this simple case, it’spretty clearly hopeless for borrowck to understand disjointness in generalcontainer types like a tree, especially if distinct keys actually do mapto the same value.

In order to “teach” borrowck that what we’re doing is ok, we need to drop downto unsafe code. For instance, mutable slices expose a split_at_mut functionthat consumes the slice and returns two mutable slices. One for everything tothe left of the index, and one for everything to the right. Intuitively we knowthis is safe because the slices don’t overlap, and therefore alias. Howeverthe implementation requires some unsafety:

# use std::slice::from_raw_parts_mut;
# struct FakeSlice<T>(T);
# impl<T> FakeSlice<T> {
# fn len(&self) -> usize { unimplemented!() }
# fn as_mut_ptr(&mut self) -> *mut T { unimplemented!() }
fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
    let len = self.len();
    let ptr = self.as_mut_ptr();
    assert!(mid <= len);
    unsafe {
        (from_raw_parts_mut(ptr, mid),
         from_raw_parts_mut(ptr.offset(mid as isize), len - mid))
    }
}
# }

This is actually a bit subtle. So as to avoid ever making two &mut‘s to thesame value, we explicitly construct brand-new slices through raw pointers.

However more subtle is how iterators that yield mutable references work.The iterator trait is defined as follows:

trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}

Given this definition, Self::Item has no connection to self. This means thatwe can call next several times in a row, and hold onto all the resultsconcurrently. This is perfectly fine for by-value iterators, which haveexactly these semantics. It’s also actually fine for shared references, as theyadmit arbitrarily many references to the same thing (although the iterator needsto be a separate object from the thing being shared).

But mutable references make this a mess. At first glance, they might seemcompletely incompatible with this API, as it would produce multiple mutablereferences to the same object!

However it actually does work, exactly because iterators are one-shot objects.Everything an IterMut yields will be yielded at most once, so we don’tactually ever yield multiple mutable references to the same piece of data.

Perhaps surprisingly, mutable iterators don’t require unsafe code to beimplemented for many types!

For instance here’s a singly linked list:

# fn main() {}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
    elem: T,
    next: Link<T>,
}
pub struct LinkedList<T> {
    head: Link<T>,
}
pub struct IterMut<'a, T: 'a>(Option<&'a mut Node<T>>);
impl<T> LinkedList<T> {
    fn iter_mut(&mut self) -> IterMut<T> {
        IterMut(self.head.as_mut().map(|node| &mut **node))
    }
}
impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.take().map(|node| {
            self.0 = node.next.as_mut().map(|node| &mut **node);
            &mut node.elem
        })
    }
}

Here’s a mutable slice:

# fn main() {}
use std::mem;
pub struct IterMut<'a, T: 'a>(&'a mut[T]);
impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        let slice = mem::replace(&mut self.0, &mut []);
        if slice.is_empty() { return None; }
        let (l, r) = slice.split_at_mut(1);
        self.0 = r;
        l.get_mut(0)
    }
}
impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        let slice = mem::replace(&mut self.0, &mut []);
        if slice.is_empty() { return None; }
        let new_len = slice.len() - 1;
        let (l, r) = slice.split_at_mut(new_len);
        self.0 = l;
        r.get_mut(0)
    }
}

And here’s a binary tree:

# fn main() {}
use std::collections::VecDeque;
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
    elem: T,
    left: Link<T>,
    right: Link<T>,
}
pub struct Tree<T> {
    root: Link<T>,
}
struct NodeIterMut<'a, T: 'a> {
    elem: Option<&'a mut T>,
    left: Option<&'a mut Node<T>>,
    right: Option<&'a mut Node<T>>,
}
enum State<'a, T: 'a> {
    Elem(&'a mut T),
    Node(&'a mut Node<T>),
}
pub struct IterMut<'a, T: 'a>(VecDeque<NodeIterMut<'a, T>>);
impl<T> Tree<T> {
    pub fn iter_mut(&mut self) -> IterMut<T> {
        let mut deque = VecDeque::new();
        self.root.as_mut().map(|root| deque.push_front(root.iter_mut()));
        IterMut(deque)
    }
}
impl<T> Node<T> {
    pub fn iter_mut(&mut self) -> NodeIterMut<T> {
        NodeIterMut {
            elem: Some(&mut self.elem),
            left: self.left.as_mut().map(|node| &mut **node),
            right: self.right.as_mut().map(|node| &mut **node),
        }
    }
}
impl<'a, T> Iterator for NodeIterMut<'a, T> {
    type Item = State<'a, T>;
    fn next(&mut self) -> Option<Self::Item> {
        match self.left.take() {
            Some(node) => Some(State::Node(node)),
            None => match self.elem.take() {
                Some(elem) => Some(State::Elem(elem)),
                None => match self.right.take() {
                    Some(node) => Some(State::Node(node)),
                    None => None,
                }
            }
        }
    }
}
impl<'a, T> DoubleEndedIterator for NodeIterMut<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        match self.right.take() {
            Some(node) => Some(State::Node(node)),
            None => match self.elem.take() {
                Some(elem) => Some(State::Elem(elem)),
                None => match self.left.take() {
                    Some(node) => Some(State::Node(node)),
                    None => None,
                }
            }
        }
    }
}
impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match self.0.front_mut().and_then(|node_it| node_it.next()) {
                Some(State::Elem(elem)) => return Some(elem),
                Some(State::Node(node)) => self.0.push_front(node.iter_mut()),
                None => if let None = self.0.pop_front() { return None },
            }
        }
    }
}
impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        loop {
            match self.0.back_mut().and_then(|node_it| node_it.next_back()) {
                Some(State::Elem(elem)) => return Some(elem),
                Some(State::Node(node)) => self.0.push_back(node.iter_mut()),
                None => if let None = self.0.pop_back() { return None },
            }
        }
    }
}

All of these are completely safe and work on stable Rust! This ultimatelyfalls out of the simple struct case we saw before: Rust understands that youcan safely split a mutable reference into subfields. We can then encodepermanently consuming a reference via Options (or in the case of slices,replacing with an empty slice).