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