src/borrow-splitting.md - rust-lang/nomicon - Git at Google

 # Splitting Borrows

 The mutual exclusion property of mutable references can be very limiting when
 working with a composite structure. The borrow checker (a.k.a. borrowck)
 understands some basic stuff, but will fall over pretty easily. It does
 understand structs sufficiently to know that it's possible to borrow disjoint
 fields of a struct simultaneously. So this works today:

 ```rust
 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't
 work:

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

 ```text
 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's
 pretty clearly hopeless for borrowck to understand disjointness in general
 container types like a tree, especially if distinct keys actually *do* map
 to the same value.

 In order to "teach" borrowck that what we're doing is ok, we need to drop down
 to unsafe code. For instance, mutable slices expose a `split_at_mut` function
 that consumes the slice and returns two mutable slices. One for everything to
 the left of the index, and one for everything to the right. Intuitively we know
 this is safe because the slices don't overlap, and therefore alias. However
 the implementation requires some unsafety:

 ```rust
 # 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!() }
 pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
     let len = self.len();
     let ptr = self.as_mut_ptr();

     unsafe {
         assert!(mid <= len);

         (from_raw_parts_mut(ptr, mid),
          from_raw_parts_mut(ptr.add(mid), len - mid))
     }
 }
 # }
 ```

 This is actually a bit subtle. So as to avoid ever making two `&mut`'s to the
 same 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:

 ```rust
 trait Iterator {
     type Item;

     fn next(&mut self) -> Option<Self::Item>;
 }
 ```

 Given this definition, Self::Item has *no* connection to `self`. This means that
 we can call `next` several times in a row, and hold onto all the results
 *concurrently*. This is perfectly fine for by-value iterators, which have
 exactly these semantics. It's also actually fine for shared references, as they
 admit arbitrarily many references to the same thing (although the iterator needs
 to be a separate object from the thing being shared).

 But mutable references make this a mess. At first glance, they might seem
 completely incompatible with this API, as it would produce multiple mutable
 references 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't
 actually ever yield multiple mutable references to the same piece of data.

 Perhaps surprisingly, mutable iterators don't require unsafe code to be
 implemented for many types!

 For instance here's a singly linked list:

 ```rust
 # 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:

 ```rust
 # 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::take(&mut self.0);
         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::take(&mut self.0);
         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:

 ```rust
 # 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 ultimately
 falls out of the simple struct case we saw before: Rust understands that you
 can safely split a mutable reference into subfields. We can then encode
 permanently consuming a reference via Options (or in the case of slices,
 replacing with an empty slice).
	# Splitting Borrows

	The mutual exclusion property of mutable references can be very limiting when
	working with a composite structure. The borrow checker (a.k.a. borrowck)
	understands some basic stuff, but will fall over pretty easily. It does
	understand structs sufficiently to know that it's possible to borrow disjoint
	fields of a struct simultaneously. So this works today:

	```rust
	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't
	work:

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

	```text
	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's
	pretty clearly hopeless for borrowck to understand disjointness in general
	container types like a tree, especially if distinct keys actually do map
	to the same value.

	In order to "teach" borrowck that what we're doing is ok, we need to drop down
	to unsafe code. For instance, mutable slices expose a `split_at_mut` function
	that consumes the slice and returns two mutable slices. One for everything to
	the left of the index, and one for everything to the right. Intuitively we know
	this is safe because the slices don't overlap, and therefore alias. However
	the implementation requires some unsafety:

	```rust
	# 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!() }
	pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
	let len = self.len();
	let ptr = self.as_mut_ptr();

	unsafe {
	assert!(mid <= len);

	(from_raw_parts_mut(ptr, mid),
	from_raw_parts_mut(ptr.add(mid), len - mid))
	}
	}
	# }
	```

	This is actually a bit subtle. So as to avoid ever making two `&mut`'s to the
	same 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:

	```rust
	trait Iterator {
	type Item;

	fn next(&mut self) -> Option<Self::Item>;
	}
	```

	Given this definition, Self::Item has no connection to `self`. This means that
	we can call `next` several times in a row, and hold onto all the results
	concurrently. This is perfectly fine for by-value iterators, which have
	exactly these semantics. It's also actually fine for shared references, as they
	admit arbitrarily many references to the same thing (although the iterator needs
	to be a separate object from the thing being shared).

	But mutable references make this a mess. At first glance, they might seem
	completely incompatible with this API, as it would produce multiple mutable
	references 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't
	actually ever yield multiple mutable references to the same piece of data.

	Perhaps surprisingly, mutable iterators don't require unsafe code to be
	implemented for many types!

	For instance here's a singly linked list:

	```rust
	# 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:

	```rust
	# 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::take(&mut self.0);
	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::take(&mut self.0);
	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:

	```rust
	# 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 ultimately
	falls out of the simple struct case we saw before: Rust understands that you
	can safely split a mutable reference into subfields. We can then encode
	permanently consuming a reference via Options (or in the case of slices,
	replacing with an empty slice).