Splitting Borrows(Splitting 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);

但是,借用不能以任何方式理解数组或切片,因此这不起作用:

  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

虽然借用可以理解这个简单的情况似乎是合理的,但是对于理解一般容器类型(例如树)中的不相交性来说,借助它是非常没有希望的,特别是如果不同的键实际上映射到相同的值.

为了”教(teach)”借用我们正在做的事情是好的,我们需要下降到不安全代码.例如,可变切片暴露split_at_mut函数,该函数使用切片并返回两个可变切片.一个用于索引左侧的所有内容,另一个用于右侧的所有内容.直观地,我们知道这是安全的,因为切片不重叠,因此别名.但是,实现需要一些不安全:

  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.         (from_raw_parts_mut(ptr, mid),
  12.          from_raw_parts_mut(ptr.add(mid), len - mid))
  13.     }
  14. }
  15. # }

这实际上有点微妙.为了避免将两个&mut变为相同的值,我们通过原始指针显式地构建全新的切片.

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

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

根据这个定义,Self::Item与self 没有(no) 关系.这意味着我们可以连续多次调用next,并 同时(concurrently) 保留所有结果.这对于通过值的迭代器来说非常好,因为它具有这些语义.它对于共享引用实际上也很好,因为它们允许任意多次引用相同的东西(尽管迭代器需要来自共享的东西的分离对象).

但是可变引用会把事情搞得一团糟.乍一看,它们似乎与此API完全不兼容,因为它会产生对同一对象的多个可变引用!

然而它实际上 确实(does) 可以工作,因为迭代器是一次性对象.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. }

这是一个可变切片:

  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明白你可以安全地将可变引用拆分为子字段.然后,我们可以通过`Option(或在切片的情况下,用空切片替换）永久地使用引用编码.