5.1 数据布局
原文链接: https://rust-unofficial.github.io/too-many-lists/fifth-layout.html
单链表队列是什么样的？当我们有单链表栈时，我们从链表一端压入，再从同一端弹出。栈和队列的唯一区别是队列从另一端弹出。所以从我们的栈实现我们有：
1
2
3
4
5
6
7
8
| 输入链表：
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
栈 push X：
[Some(ptr)] -> (X, Some(ptr)) -> (A, Some(ptr)) -> (B, None)
栈 pop：
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
|
要做队列，我们只需决定把哪个操作移到链表末端：push 还是 pop？因为链表是单链的，实际上把任一操作移到末端的工作量相同。
要把 push 移到末端，我们只需一路走到 None 并设为 Some 新元素。
1
2
3
4
5
| 输入链表：
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
翻转后的 push X：
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)
|
要把 pop 移到末端，我们只需一路走到 None 之前的节点，然后 take 它：
1
2
3
4
5
| 输入链表：
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)
翻转后的 pop：
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
|
我们今天可以这样做然后收工，但那会很烂！这两个操作都要遍历整个链表。有人会说这样的队列实现确实是队列，因为它暴露了正确的接口。然而我相信性能保证是接口的一部分。我不在乎精确的渐近界，只要"快"对"慢"。队列保证 push 和 pop 是快的，遍历整个链表绝对不快。
一个关键观察是，我们在反复做同样的事，浪费了大量工作。我们能"缓存"这些工作并复用吗？能！我们可以存储指向链表末端的指针，直接跳过去！
事实证明，只有翻转 push 和 pop 中的一种能与这个配合。要翻转 pop 我们必须把"tail"指针向后移，但因为链表是单链的，我们无法高效地做到这一点。如果我们翻转 push，我们只需把"head"指针向前移，这很容易。
我们来试试：
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
| use std::mem;
pub struct List<T> {
head: Link<T>,
tail: Link<T>, // 新增！
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> List<T> {
pub fn new() -> Self {
List { head: None, tail: None }
}
pub fn push(&mut self, elem: T) {
let new_tail = Box::new(Node {
elem: elem,
// 压到 tail 时，next 总是 None
next: None,
});
// 把旧的 tail 换成指向新 tail
let old_tail = mem::replace(&mut self.tail, Some(new_tail));
match old_tail {
Some(mut old_tail) => {
// 如果旧的 tail 存在，更新它指向新的 tail
old_tail.next = Some(new_tail);
}
None => {
// 否则，更新 head 指向它
self.head = Some(new_tail);
}
}
}
}
|
实现细节我现在写得快一些，因为我们应该对这种事了如指掌。不是说你应该第一次就写出这些代码。我只是跳过一些我们以前不得不处理的试错。实际上我写这段代码犯了很多错没展示，但你只能看我漏掉 mut 或 ; 这么多次，之后就不再有教学意义了。别担心，我们会看到很多其他错误信息！
1
2
3
4
5
6
7
8
9
10
11
12
13
| > cargo build
error[E0382]: use of moved value: `new_tail`
--> src/fifth.rs:38:38
|
26 | let new_tail = Box::new(Node {
| -------- move occurs because `new_tail` has type `std::boxed::Box<fifth::Node<T>>`, which does not implement the `Copy` trait
...
33 | let old_tail = mem::replace(&mut self.tail, Some(new_tail));
| -------- value moved here
...
38 | old_tail.next = Some(new_tail);
| ^^^^^^^^ value used here after move
|
糟了！
use of moved value: new_tail
Box 没有实现 Copy，所以我们不能把它赋给两个位置。更重要的是，Box 拥有它指向的东西，drop 时会尝试释放。如果我们的 push 实现能编译，我们会双重释放链表尾部！实际上，按现在的写法，每次 push 都会释放 old_tail。哎呀！🙀
好吧，我们知道如何制作非拥有指针。那就是引用！
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
| pub struct List<T> {
head: Link<T>,
tail: Option<&mut Node<T>>, // 新增！
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> List<T> {
pub fn new() -> Self {
List { head: None, tail: None }
}
pub fn push(&mut self, elem: T) {
let new_tail = Box::new(Node {
elem: elem,
// 压到 tail 时，next 总是 None
next: None,
});
// 把 Box 放到正确位置，然后拿到其 Node 的引用
let new_tail = match self.tail.take() {
Some(old_tail) => {
// 如果旧的 tail 存在，更新它指向新的 tail
old_tail.next = Some(new_tail);
old_tail.next.as_deref_mut()
}
None => {
// 否则，更新 head 指向它
self.head = Some(new_tail);
self.head.as_deref_mut()
}
};
self.tail = new_tail;
}
}
|
没什么太棘手的。和之前代码同样的基本思路，只是我们用了一些隐式返回的便利，从我们把实际 Box 塞进去的地方提取 tail 引用。
1
2
3
4
5
6
7
| > cargo build
error[E0106]: missing lifetime specifier
--> src/fifth.rs:3:18
|
3 | tail: Option<&mut Node<T>>, // NEW!
| ^ expected lifetime parameter
|
哦对了，类型里的引用需要生命周期。嗯……这个引用的生命周期是什么？嗯，这好像 IterMut，对吧？我们试试 IterMut 的做法，加个泛型 'a：
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
| pub struct List<'a, T> {
head: Link<T>,
tail: Option<&'a mut Node<T>>, // 新增！
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<'a, T> List<'a, T> {
pub fn new() -> Self {
List { head: None, tail: None }
}
pub fn push(&mut self, elem: T) {
let new_tail = Box::new(Node {
elem: elem,
// 压到 tail 时，next 总是 None
next: None,
});
// 把 Box 放到正确位置，然后拿到其 Node 的引用
let new_tail = match self.tail.take() {
Some(old_tail) => {
// 如果旧的 tail 存在，更新它指向新的 tail
old_tail.next = Some(new_tail);
old_tail.next.as_deref_mut()
}
None => {
// 否则，更新 head 指向它
self.head = Some(new_tail);
self.head.as_deref_mut()
}
};
self.tail = new_tail;
}
}
|
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
| cargo build
error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
--> src/fifth.rs:35:27
|
35 | self.head.as_deref_mut()
| ^^^^^^^^^^^^
|
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 18:5...
--> src/fifth.rs:18:5
|
18 | / pub fn push(&mut self, elem: T) {
19 | | let new_tail = Box::new(Node {
20 | | elem: elem,
21 | | // When you push onto the tail, your next is always None
... |
39 | | self.tail = new_tail;
40 | | }
| |_____^
note: ...so that reference does not outlive borrowed content
--> src/fifth.rs:35:17
|
35 | self.head.as_deref_mut()
| ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 13:6...
--> src/fifth.rs:13:6
|
13 | impl<'a, T> List<'a, T> {
| ^^
= note: ...so that the expression is assignable:
expected std::option::Option<&'a mut fifth::Node<T>>
found std::option::Option<&mut fifth::Node<T>>
|
哇，这真是非常详细的错误信息。有点令人担忧，因为它暗示我们在做非常糟糕的事。有趣的部分：
the lifetime must be valid for the lifetime 'a as defined on the impl
我们在从 self 借用，但编译器要我们活得和 'a 一样长，如果我们告诉它 self 确实活那么久呢……？
1
| pub fn push(&'a mut self, elem: T) {
|
1
2
3
4
5
6
7
8
9
| cargo build
warning: field is never used: `elem`
--> src/fifth.rs:9:5
|
9 | elem: T,
| ^^^^^^^
|
= note: #[warn(dead_code)] on by default
|
哦，嘿，行了！太好了！
我们也把 pop 写了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| pub fn pop(&'a mut self) -> Option<T> {
// 取出链表当前的 head
self.head.take().map(|head| {
let head = *head;
self.head = head.next;
// 如果没有 `head` 了，确保把 tail 设为 `None`。
if self.head.is_none() {
self.tail = None;
}
head.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
30
31
32
| #[cfg(test)]
mod test {
use super::List;
#[test]
fn basics() {
let mut list = List::new();
// 检查空链表行为正确
assert_eq!(list.pop(), None);
// 填充链表
list.push(1);
list.push(2);
list.push(3);
// 检查正常移除
assert_eq!(list.pop(), Some(1));
assert_eq!(list.pop(), Some(2));
// 再压入一些，确保没有损坏
list.push(4);
list.push(5);
// 检查正常移除
assert_eq!(list.pop(), Some(3));
assert_eq!(list.pop(), Some(4));
// 检查耗尽
assert_eq!(list.pop(), Some(5));
assert_eq!(list.pop(), None);
}
}
|
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
| cargo test
error[E0499]: cannot borrow `list` as mutable more than once at a time
--> src/fifth.rs:68:9
|
65 | assert_eq!(list.pop(), None);
| ---- first mutable borrow occurs here
...
68 | list.push(1);
| ^^^^
| |
| second mutable borrow occurs here
| first borrow later used here
error[E0499]: cannot borrow `list` as mutable more than once at a time
--> src/fifth.rs:69:9
|
65 | assert_eq!(list.pop(), None);
| ---- first mutable borrow occurs here
...
69 | list.push(2);
| ^^^^
| |
| second mutable borrow occurs here
| first borrow later used here
error[E0499]: cannot borrow `list` as mutable more than once at a time
--> src/fifth.rs:70:9
|
65 | assert_eq!(list.pop(), None);
| ---- first mutable borrow occurs here
...
70 | list.push(3);
| ^^^^
| |
| second mutable borrow occurs here
| first borrow later used here
....
** 更多行的错误 **
....
error: aborting due to 11 previous errors
|
🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀
天哪。
编译器对我们大发雷霆并没有错。我们刚刚犯了 Rust 的大罪：在自己内部存储了指向自己的引用。不知怎的，我们在 push 和 pop 实现里说服了 Rust 这完全说得通（我真心震惊我们做到了）。
这有点能工作的原因是 Rust 根本没有"指向自己的指针"这个概念。代码的每个部分单独看在技术上都是正确的（我们可以调用 push 和 pop 一次），但我们创造的东西的荒谬性随后生效，一切就锁死了。
我确信我们写的东西有某种用途，但在我看来它只是语法上有效的* gibberish*。我们说我们包含生命周期为 'a 的东西，而 push 和 pop 在那个生命周期内借用self。这很奇怪，但 Rust 可以单独看我们代码的每一部分，看不出规则被打破。
但一旦我们试图使用链表，编译器很快会说"是的，你在 'a 内可变借用了 self，所以在 'a 结束之前不能再使用 self"，但同时“因为你包含 'a，它必须在链表整个存在期间有效”。
这几乎是矛盾，但有一个解决方案：一旦你 push 或 pop，链表就把自己"钉"在原地，无法再访问。它吞掉了自己的 proverbial tail，升入了梦境世界。
旁白：这本书刚写的时候还不存在，但 Rust 实际上把pin的概念形式化成了有用的东西！这可能是自借用检查器以来对语言最复杂的添加。我们不希望链表被 pin 住！
Pin 对 async-await/futures/coroutines 是必要且有用的，因为编译器需要能够把函数的所有局部变量打包成某种结构体并存储在某处，直到 future/coroutine 准备好恢复。因为局部变量可以引用其他局部变量，而我们希望那能工作，这些结构体最终可能包含指向自己的引用！
所以 await 或 yield 需要 Rust 能够正确描述和操作被 pin 的值。幸好这些东西* largely* 只是隐藏在自动编译器机制里，正常情况下没人真的需要想 Pin（甚至Futures）。主要例外是这对构建和设计 async 运行时（如 tokio）的人非常重要。
我们不会在这本书里实现 async 运行时。我知道我的朋友们知道各种可以用 Pin 做的"酷"（搞砸的）技巧，但据我所知，不知道它们我会更开心。我会继续告诉自己被 Pin 的类型不是真的，它们伤不了我。
我们的 pop 实现暗示了为什么在自己内部存储指向自己的引用可能真的很危险：
1
2
3
4
| // ...
if self.head.is_none() {
self.tail = None;
}
|
如果我们忘了这样做呢？那我们的 tail 会指向已从链表移除的某个节点。这样的节点会立刻被释放，我们就会有一个悬垂指针，而 Rust 本应保护我们免受那种危险！
确实 Rust 在保护我们免受那种危险。只是以一种非常……绕远路的方式。
那我们怎么办？回到 Rc<RefCell>> 地狱？
拜托。不要。
不，我们要彻底越轨，使用裸指针。我们的布局会是这样：
1
2
3
4
5
6
7
8
9
10
11
| pub struct List<T> {
head: Link<T>,
tail: *mut Node<T>, // 危险 危险
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
|
就这样。不要这些懦弱的引用计数动态借用检查废话！真正的。硬核。未检查的。指针。
旁白： 这个实现实际上仍然危险地错误，但还没到学那课的时候。下一节会像往常一样艰难地学到。
让我们当 C 吧。整天当 C。
我到家了。我准备好了。
你好 unsafe。
旁白： 哇，作者这里的傲慢真是令人难以置信。