拆分 Borrows

在处理复合结构时，可变引用的互斥属性会有很大的限制。借用检查器理解一些基本的东西，但是很容易就会出现问题。它对结构有足够的了解，知道有可能同时借用一个结构中不相干的字段。所以现在这个方法是可行的：

  1. struct Foo {
  2.     a: i32,
  3.     b: i32,
  4.     c: i32,
  5. }
  7. let mut x = Foo {a: 0, b: 0, c: 0};
  8. let a = &mut x.a;
  9. let b = &mut x.b;
  10. let c = &x.c;
  11. *b += 1;
  12. let c2 = &x.c;
  13. *a += 10;
  14. println!("{} {} {} {}", a, b, c, c2);

然而 borrowck 完全不理解数组或 slice，所以这会挂：

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

虽然 borrowck 能理解这个简单的案例是合理的，但对于 borrowck 来说，要理解像树这样的一般容器类型的不连通性显然是没有希望的，尤其是当不同的键确实映射到相同的值时。

为了“教导” borrowck 我们正在做的事情是正确的，我们需要使用到不安全的代码。例如，可变 slice 暴露了一个split_at_mut函数，它消耗这个 slice 并返回两个可变 slice。一个用于索引左边的所有内容，一个用于右边的所有内容。直观地讲，我们知道这是安全的，因为这些分片不会重叠，因此可以进行别名操作。然而，这个实现需要一些不安全代码：

  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. pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
  7.     let len = self.len();
  8.     let ptr = self.as_mut_ptr();
  10.     unsafe {
  11.         assert!(mid <= len);
  13.         (from_raw_parts_mut(ptr, mid),
  14.          from_raw_parts_mut(ptr.add(mid), len - mid))
  15.     }
  16. }
  17. # }

这实际上是有点微妙的。为了避免对同一个值进行两次&mut，我们明确地通过原始指针构造全新的切片。

然而，更微妙的是产生可变引用的迭代器如何工作。迭代器 trait 定义如下：

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

考虑到这个定义，Self::Item 与self没有联系。这意味着我们可以连续多次调用next，并将所有的结果并发地保留下来。这对逐值迭代器来说是非常好的，因为它有这样的语义。这对共享引用来说也很好，因为它们允许对同一事物有任意多的引用（尽管迭代器需要和被共享的事物是一个独立的对象）。

但是可变的引用让这变得一团糟。乍一看，它们似乎与这个 API 完全不兼容，因为它将产生对同一个对象的多个可变引用！

然而它实际上是有效的，正是因为迭代器是一次性的对象。IterMut 产生的所有东西最多只能产生一次，所以我们实际上不会产生对同一块数据的多个可变引用。

也许令人惊讶的是，对于许多类型，可变迭代器不需要实现不安全的代码。

例如，这里有一个单向链表：

  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.     }
  30. }

下面是一个可变的 slice：

  1. # fn main() {}
  2. use std::mem;
  4. pub struct IterMut<'a, T: 'a>(&'a mut[T]);
  6. impl<'a, T> Iterator for IterMut<'a, T> {
  7.     type Item = &'a mut T;
  9.     fn next(&mut self) -> Option<Self::Item> {
  10.         let slice = mem::replace(&mut self.0, &mut []);
  11.         if slice.is_empty() { return None; }
  13.         let (l, r) = slice.split_at_mut(1);
  14.         self.0 = r;
  15.         l.get_mut(0)
  16.     }
  17. }
  19. impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
  20.     fn next_back(&mut self) -> Option<Self::Item> {
  21.         let slice = mem::replace(&mut self.0, &mut []);
  22.         if slice.is_empty() { return None; }
  24.         let new_len = slice.len() - 1;
  25.         let (l, r) = slice.split_at_mut(new_len);
  26.         self.0 = l;
  27.         r.get_mut(0)
  28.     }
  29. }

接着是一个二叉树：

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

所有这些都是完全安全的，并且可以在稳定的 Rust 上运行！这最终落在了我们之前看到的简单结构案例中。Rust 知道你可以安全地将一个可变的引用分割成子字段。然后我们可以通过 Options（或者在分片的情况下，用空分片替换）来消耗掉这个引用并进行编码。