Splitting Borrows

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

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

    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:

    1. # use std::slice::from_raw_parts_mut;
    2. # struct FakeSlice<T>(T);
    3. # impl<T> FakeSlice<T> {
    4. # fn len(&self) -> usize { unimplemented!() }
    5. # fn as_mut_ptr(&mut self) -> *mut T { unimplemented!() }
    6. fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
    7.     let len = self.len();
    8.     let ptr = self.as_mut_ptr();
    9.     assert!(mid <= len);
    10.     unsafe {
    11.         (from_raw_parts_mut(ptr, mid),
    12.          from_raw_parts_mut(ptr.offset(mid as isize), len - mid))
    13.     }
    14. }
    15. # }

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

    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!

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

    For instance here’s a singly linked list:

    1. # fn main() {}
    2. type Link<T> = Option<Box<Node<T>>>;
    4. struct Node<T> {
    5.     elem: T,
    6.     next: Link<T>,
    7. }
    9. pub struct LinkedList<T> {
    10.     head: Link<T>,
    11. }
    13. pub struct IterMut<'a, T: 'a>(Option<&'a mut Node<T>>);
    15. impl<T> LinkedList<T> {
    16.     fn iter_mut(&mut self) -> IterMut<T> {
    17.         IterMut(self.head.as_mut().map(|node| &mut **node))
    18.     }
    19. }
    21. impl<'a, T> Iterator for IterMut<'a, T> {
    22.     type Item = &'a mut T;
    24.     fn next(&mut self) -> Option<Self::Item> {
    25.         self.0.take().map(|node| {
    26.             self.0 = node.next.as_mut().map(|node| &mut **node);
    27.             &mut node.elem
    28.         })
    29.     }

    Here’s a mutable slice:

    1. # fn main() {}
    3. type Link<T> = Option<Box<Node<T>>>;
    5. struct Node<T> {
    6.     elem: T,
    7.     left: Link<T>,
    8.     right: Link<T>,
    9. }
    11. pub struct Tree<T> {
    12.     root: Link<T>,
    13. }
    15. struct NodeIterMut<'a, T: 'a> {
    16.     elem: Option<&'a mut T>,
    17.     left: Option<&'a mut Node<T>>,
    18.     right: Option<&'a mut Node<T>>,
    19. }
    21. enum State<'a, T: 'a> {
    22.     Elem(&'a mut T),
    23.     Node(&'a mut Node<T>),
    24. }
    26. pub struct IterMut<'a, T: 'a>(VecDeque<NodeIterMut<'a, T>>);
    28. impl<T> Tree<T> {
    29.     pub fn iter_mut(&mut self) -> IterMut<T> {
    30.         let mut deque = VecDeque::new();
    31.         self.root.as_mut().map(|root| deque.push_front(root.iter_mut()));
    32.         IterMut(deque)
    33.     }
    34. }
    36. impl<T> Node<T> {
    37.     pub fn iter_mut(&mut self) -> NodeIterMut<T> {
    38.         NodeIterMut {
    39.             elem: Some(&mut self.elem),
    40.             left: self.left.as_mut().map(|node| &mut **node),
    41.             right: self.right.as_mut().map(|node| &mut **node),
    42.         }
    43.     }
    44. }
    47. impl<'a, T> Iterator for NodeIterMut<'a, T> {
    48.     type Item = State<'a, T>;
    50.     fn next(&mut self) -> Option<Self::Item> {
    52.             None => match self.elem.take() {
    53.                 Some(elem) => Some(State::Elem(elem)),
    54.                 None => match self.right.take() {
    55.                     Some(node) => Some(State::Node(node)),
    56.                     None => None,
    57.                 }
    58.             }
    59.         }
    60.     }
    61. }
    63. impl<'a, T> DoubleEndedIterator for NodeIterMut<'a, T> {
    64.     fn next_back(&mut self) -> Option<Self::Item> {
    65.         match self.right.take() {
    66.             Some(node) => Some(State::Node(node)),
    67.             None => match self.elem.take() {
    68.                 Some(elem) => Some(State::Elem(elem)),
    69.                 None => match self.left.take() {
    70.                     Some(node) => Some(State::Node(node)),
    71.                     None => None,
    72.                 }
    73.             }
    74.         }
    75.     }
    76. }
    78. impl<'a, T> Iterator for IterMut<'a, T> {
    79.     type Item = &'a mut T;
    80.     fn next(&mut self) -> Option<Self::Item> {
    81.         loop {
    82.             match self.0.front_mut().and_then(|node_it| node_it.next()) {
    83.                 Some(State::Elem(elem)) => return Some(elem),
    84.                 Some(State::Node(node)) => self.0.push_front(node.iter_mut()),
    85.                 None => if let None = self.0.pop_front() { return None },
    86.             }
    87.         }
    88.     }
    89. }
    91. impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
    92.     fn next_back(&mut self) -> Option<Self::Item> {
    93.         loop {
    94.             match self.0.back_mut().and_then(|node_it| node_it.next_back()) {
    95.                 Some(State::Elem(elem)) => return Some(elem),
    96.                 Some(State::Node(node)) => self.0.push_back(node.iter_mut()),
    97.                 None => if let None = self.0.pop_back() { return None },
    98.             }
    99.         }
    100.     }
    101. }

    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).