3.11 拆分借用
如何安全地拆分借用
译文 · 基于 The Rustonomicon
拆分借用
原文链接: https://doc.rust-lang.org/nomicon/borrow-splitting.html
可变引用的互斥性质在处理复合结构时可能非常受限。借用检查器（borrowck）理解一些基础情况，但很容易翻车。它足够理解结构体，知道可以同时借用结构体的互不相交字段。因此下面代码今天能工作：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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);
|
但 borrowck 以任何方式都不理解数组或切片，因此下面不行：
let mut x = [1, 2, 3];
let a = &mut x[0];
let b = &mut x[1];
println!("{} {}", a, b);
1
2
3
4
5
6
7
8
9
10
11
12
| 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
|
虽然 borrowck 理解这个简单情况并非不可想象，但让它理解树等一般容器类型的互不相交性显然不现实——尤其当不同键实际上确实映射到同一值时。
要「教」borrowck 我们的做法没问题，需要降到 unsafe 代码。例如，可变切片提供 split_at_mut，消费切片并返回两个可变切片：索引左侧一切，以及右侧一切。直觉上我们知道这 safe，因为切片不重叠，因此不 alias。但实现需要一些 unsafety：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| # 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))
}
}
# }
|
这实际上有点微妙。为避免对同一值产生两个 &mut，我们显式通过裸指针构造全新的切片。
但更微妙的是产生可变引用的迭代器如何工作。迭代器 trait 定义如下：
1
2
3
4
5
| trait Iterator {
type Item;
fn next(&mut self) -> Option<Self::Item>;
}
|
给定此定义，Self::Item 与 self 没有关联。这意味着可以连续多次调用 next，并同时持有所有结果。对按值迭代器完全没问题，语义正是如此。对共享引用也没问题，因为它们允许对同一对象的任意多引用（尽管迭代器须与被共享对象分离）。
但可变引用让这变得棘手。乍看之下，它们似乎与此 API 完全不兼容，因为会对同一对象产生多个可变引用！
然而它确实能工作，正因为它是一次性对象。IterMut 产生的每个元素最多产生一次，因此我们实际上不会对同一块数据产生多个可变引用。
或许令人惊讶，对许多类型，可变迭代器的实现不需要 unsafe 代码！
例如单链表：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| # 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
})
}
}
|
可变切片：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| # 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)
}
}
|
二叉树：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| # 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();
if let Some(root) = self.root.as_mut() {
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_deref_mut(),
right: self.right.as_deref_mut(),
}
}
}
impl<'a, T> Iterator for NodeIterMut<'a, T> {
type Item = State<'a, T>;
fn next(&mut self) -> Option<Self::Item> {
self.left.take().map(State::Node).or_else(|| {
self.elem
.take()
.map(State::Elem)
.or_else(|| self.right.take().map(State::Node))
})
}
}
impl<'a, T> DoubleEndedIterator for NodeIterMut<'a, T> {
fn next_back(&mut self) -> Option<Self::Item> {
self.right.take().map(State::Node).or_else(|| {
self.elem
.take()
.map(State::Elem)
.or_else(|| self.left.take().map(State::Node))
})
}
}
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(Iterator::next) {
Some(State::Elem(elem)) => return Some(elem),
Some(State::Node(node)) => self.0.push_front(node.iter_mut()),
None => {
self.0.pop_front()?;
}
}
}
}
}
impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
fn next_back(&mut self) -> Option<Self::Item> {
loop {
match self.0.back_mut().and_then(DoubleEndedIterator::next_back) {
Some(State::Elem(elem)) => return Some(elem),
Some(State::Node(node)) => self.0.push_back(node.iter_mut()),
None => {
self.0.pop_back()?;
}
}
}
}
}
|
这些都是完全安全的，在 stable Rust 上能工作！这最终源于前面看到的简单结构体情况：Rust 理解可以把可变引用安全拆成子字段。然后可通过 Option 编码永久消费引用（对切片则是替换为空切片）。