src/doc/tarpl/borrow-splitting.md

   1 % Splitting Borrows
   2
   3 The mutual exclusion property of mutable references can be very limiting when
   4 working with a composite structure. The borrow checker understands some basic
   5 stuff, but will fall over pretty easily. It *does* understand structs
   6 sufficiently to know that it's possible to borrow disjoint fields of a struct
   7 simultaneously. So this works today:
   8
   9 ```rust
  10 struct Foo {
  11     a: i32,
  12     b: i32,
  13     c: i32,
  14 }
  15
  16 let mut x = Foo {a: 0, b: 0, c: 0};
  17 let a = &mut x.a;
  18 let b = &mut x.b;
  19 let c = &x.c;
  20 *b += 1;
  21 let c2 = &x.c;
  22 *a += 10;
  23 println!("{} {} {} {}", a, b, c, c2);
  24 ```
  25
  26 However borrowck doesn't understand arrays or slices in any way, so this doesn't
  27 work:
  28
  29 ```rust,ignore
  30 let x = [1, 2, 3];
  31 let a = &mut x[0];
  32 let b = &mut x[1];
  33 println!("{} {}", a, b);
  34 ```
  35
  36 ```text
  37 <anon>:3:18: 3:22 error: cannot borrow immutable indexed content `x[..]` as mutable
  38 <anon>:3     let a = &mut x[0];
  39                           ^~~~
  40 <anon>:4:18: 4:22 error: cannot borrow immutable indexed content `x[..]` as mutable
  41 <anon>:4     let b = &mut x[1];
  42                           ^~~~
  43 error: aborting due to 2 previous errors
  44 ```
  45
  46 While it was plausible that borrowck could understand this simple case, it's
  47 pretty clearly hopeless for borrowck to understand disjointness in general
  48 container types like a tree, especially if distinct keys actually *do* map
  49 to the same value.
  50
  51 In order to "teach" borrowck that what we're doing is ok, we need to drop down
  52 to unsafe code. For instance, mutable slices expose a `split_at_mut` function
  53 that consumes the slice and returns *two* mutable slices. One for everything to
  54 the left of the index, and one for everything to the right. Intuitively we know
  55 this is safe because the slices don't overlap, and therefore alias. However
  56 the implementation requires some unsafety:
  57
  58 ```rust,ignore
  59 fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
  60     let len = self.len();
  61     let ptr = self.as_mut_ptr();
  62     assert!(mid <= len);
  63     unsafe {
  64         (from_raw_parts_mut(ptr, mid),
  65          from_raw_parts_mut(ptr.offset(mid as isize), len - mid))
  66     }
  67 }
  68 ```
  69
  70 This is actually a bit subtle. So as to avoid ever making two `&mut`'s to the
  71 same value, we explicitly construct brand-new slices through raw pointers.
  72
  73 However more subtle is how iterators that yield mutable references work.
  74 The iterator trait is defined as follows:
  75
  76 ```rust
  77 trait Iterator {
  78     type Item;
  79
  80     fn next(&mut self) -> Option<Self::Item>;
  81 }
  82 ```
  83
  84 Given this definition, Self::Item has *no* connection to `self`. This means that
  85 we can call `next` several times in a row, and hold onto all the results
  86 *concurrently*. This is perfectly fine for by-value iterators, which have
  87 exactly these semantics. It's also actually fine for shared references, as they
  88 admit arbitrarily many references to the same thing (although the iterator needs
  89 to be a separate object from the thing being shared).
  90
  91 But mutable references make this a mess. At first glance, they might seem
  92 completely incompatible with this API, as it would produce multiple mutable
  93 references to the same object!
  94
  95 However it actually *does* work, exactly because iterators are one-shot objects.
  96 Everything an IterMut yields will be yielded *at most* once, so we don't
  97 *actually* ever yield multiple mutable references to the same piece of data.
  98
  99 Perhaps surprisingly, mutable iterators *don't* require unsafe code to be
 100 implemented for many types!
 101
 102 For instance here's a singly linked list:
 103
 104 ```rust
 105 # fn main() {}
 106 type Link<T> = Option<Box<Node<T>>>;
 107
 108 struct Node<T> {
 109     elem: T,
 110     next: Link<T>,
 111 }
 112
 113 pub struct LinkedList<T> {
 114     head: Link<T>,
 115 }
 116
 117 pub struct IterMut<'a, T: 'a>(Option<&'a mut Node<T>>);
 118
 119 impl<T> LinkedList<T> {
 120     fn iter_mut(&mut self) -> IterMut<T> {
 121         IterMut(self.head.as_mut().map(|node| &mut **node))
 122     }
 123 }
 124
 125 impl<'a, T> Iterator for IterMut<'a, T> {
 126     type Item = &'a mut T;
 127
 128     fn next(&mut self) -> Option<Self::Item> {
 129         self.0.take().map(|node| {
 130             self.0 = node.next.as_mut().map(|node| &mut **node);
 131             &mut node.elem
 132         })
 133     }
 134 }
 135 ```
 136
 137 Here's a mutable slice:
 138
 139 ```rust
 140 # fn main() {}
 141 use std::mem;
 142
 143 pub struct IterMut<'a, T: 'a>(&'a mut[T]);
 144
 145 impl<'a, T> Iterator for IterMut<'a, T> {
 146     type Item = &'a mut T;
 147
 148     fn next(&mut self) -> Option<Self::Item> {
 149         let slice = mem::replace(&mut self.0, &mut []);
 150         if slice.is_empty() { return None; }
 151
 152         let (l, r) = slice.split_at_mut(1);
 153         self.0 = r;
 154         l.get_mut(0)
 155     }
 156 }
 157
 158 impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
 159     fn next_back(&mut self) -> Option<Self::Item> {
 160         let slice = mem::replace(&mut self.0, &mut []);
 161         if slice.is_empty() { return None; }
 162
 163         let new_len = slice.len() - 1;
 164         let (l, r) = slice.split_at_mut(new_len);
 165         self.0 = l;
 166         r.get_mut(0)
 167     }
 168 }
 169 ```
 170
 171 And here's a binary tree:
 172
 173 ```rust
 174 # fn main() {}
 175 use std::collections::VecDeque;
 176
 177 type Link<T> = Option<Box<Node<T>>>;
 178
 179 struct Node<T> {
 180     elem: T,
 181     left: Link<T>,
 182     right: Link<T>,
 183 }
 184
 185 pub struct Tree<T> {
 186     root: Link<T>,
 187 }
 188
 189 struct NodeIterMut<'a, T: 'a> {
 190     elem: Option<&'a mut T>,
 191     left: Option<&'a mut Node<T>>,
 192     right: Option<&'a mut Node<T>>,
 193 }
 194
 195 enum State<'a, T: 'a> {
 196     Elem(&'a mut T),
 197     Node(&'a mut Node<T>),
 198 }
 199
 200 pub struct IterMut<'a, T: 'a>(VecDeque<NodeIterMut<'a, T>>);
 201
 202 impl<T> Tree<T> {
 203     pub fn iter_mut(&mut self) -> IterMut<T> {
 204         let mut deque = VecDeque::new();
 205         self.root.as_mut().map(|root| deque.push_front(root.iter_mut()));
 206         IterMut(deque)
 207     }
 208 }
 209
 210 impl<T> Node<T> {
 211     pub fn iter_mut(&mut self) -> NodeIterMut<T> {
 212         NodeIterMut {
 213             elem: Some(&mut self.elem),
 214             left: self.left.as_mut().map(|node| &mut **node),
 215             right: self.right.as_mut().map(|node| &mut **node),
 216         }
 217     }
 218 }
 219
 220
 221 impl<'a, T> Iterator for NodeIterMut<'a, T> {
 222     type Item = State<'a, T>;
 223
 224     fn next(&mut self) -> Option<Self::Item> {
 225         match self.left.take() {
 226             Some(node) => Some(State::Node(node)),
 227             None => match self.elem.take() {
 228                 Some(elem) => Some(State::Elem(elem)),
 229                 None => match self.right.take() {
 230                     Some(node) => Some(State::Node(node)),
 231                     None => None,
 232                 }
 233             }
 234         }
 235     }
 236 }
 237
 238 impl<'a, T> DoubleEndedIterator for NodeIterMut<'a, T> {
 239     fn next_back(&mut self) -> Option<Self::Item> {
 240         match self.right.take() {
 241             Some(node) => Some(State::Node(node)),
 242             None => match self.elem.take() {
 243                 Some(elem) => Some(State::Elem(elem)),
 244                 None => match self.left.take() {
 245                     Some(node) => Some(State::Node(node)),
 246                     None => None,
 247                 }
 248             }
 249         }
 250     }
 251 }
 252
 253 impl<'a, T> Iterator for IterMut<'a, T> {
 254     type Item = &'a mut T;
 255     fn next(&mut self) -> Option<Self::Item> {
 256         loop {
 257             match self.0.front_mut().and_then(|node_it| node_it.next()) {
 258                 Some(State::Elem(elem)) => return Some(elem),
 259                 Some(State::Node(node)) => self.0.push_front(node.iter_mut()),
 260                 None => if let None = self.0.pop_front() { return None },
 261             }
 262         }
 263     }
 264 }
 265
 266 impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
 267     fn next_back(&mut self) -> Option<Self::Item> {
 268         loop {
 269             match self.0.back_mut().and_then(|node_it| node_it.next_back()) {
 270                 Some(State::Elem(elem)) => return Some(elem),
 271                 Some(State::Node(node)) => self.0.push_back(node.iter_mut()),
 272                 None => if let None = self.0.pop_back() { return None },
 273             }
 274         }
 275     }
 276 }
 277 ```
 278
 279 All of these are completely safe and work on stable Rust! This ultimately
 280 falls out of the simple struct case we saw before: Rust understands that you
 281 can safely split a mutable reference into subfields. We can then encode
 282 permanently consuming a reference via Options (or in the case of slices,
 283 replacing with an empty slice).