5.3 基本操作
原文链接: https://rust-unofficial.github.io/too-many-lists/fifth-basics.html
旁白： 本节有一个潜伏的根本错误，因为这就是本书的意义所在。不过一旦我们开始使用 unsafe，就可能做错事却仍能编译且看似正常工作。根本错误会在下一节指出。不要在生产代码中使用本节内容！
好了，回到基础。我们如何构造链表？
之前我们只是：
1
2
3
4
5
| impl<T> List<T> {
pub fn new() -> Self {
List { head: None, tail: None }
}
}
|
但我们不再对 tail 使用 Option：
1
2
3
4
5
6
7
8
9
10
11
| > cargo build
error[E0308]: mismatched types
--> src/fifth.rs:15:34
|
15 | List { head: None, tail: None }
| ^^^^ expected *-ptr, found
| enum `std::option::Option`
|
= note: expected type `*mut fifth::Node<T>`
found type `std::option::Option<_>`
|
我们可以用 Option，但与 Box 不同，*mut 是可空的。这意味着它无法受益于空指针优化。相反，我们用 null 表示 None。
那么如何得到空指针？有几种方式，但我更喜欢 std::ptr::null_mut()。如果你愿意，也可以用 0 as *mut _，但那看起来太乱了。
1
2
3
4
5
6
7
8
9
| use std::ptr;
// 定义...
impl<T> List<T> {
pub fn new() -> Self {
List { head: None, tail: ptr::null_mut() }
}
}
|
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
| cargo build
warning: field is never used: `head`
--> src/fifth.rs:4:5
|
4 | head: Link<T>,
| ^^^^^^^^^^^^^
|
= note: #[warn(dead_code)] on by default
warning: field is never used: `tail`
--> src/fifth.rs:5:5
|
5 | tail: *mut Node<T>,
| ^^^^^^^^^^^^^^^^^^
warning: field is never used: `elem`
--> src/fifth.rs:11:5
|
11 | elem: T,
| ^^^^^^^
warning: field is never used: `head`
--> src/fifth.rs:12:5
|
12 | head: Link<T>,
| ^^^^^^^^^^^^^
|
嘘 编译器，我们马上就会用到它们。
好了，再来写 push。这次，我们不是插入后再拿 Option<&mut Node<T>>，而是直接拿指向 Box 内部的 *mut Node<T>。我们知道可以合理地这样做，因为 Box 的内容有稳定地址，即使我们移动 Box 也是如此。当然，这并不安全，因为如果我们 drop 了 Box，就会有一个指向已释放内存的指针。
如何从普通指针得到裸指针？强制转换！如果变量声明为裸指针，普通引用会强制转换进去：
1
| let raw_tail: *mut _ = &mut *new_tail;
|
我们有了所有需要的信息。可以把代码翻译成，大致上，之前的引用版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| pub fn push(&mut self, elem: T) {
let mut new_tail = Box::new(Node {
elem: elem,
next: None,
});
let raw_tail: *mut _ = &mut *new_tail;
// .is_null 检查 null，等价于检查 None
if !self.tail.is_null() {
// 如果旧的 tail 存在，更新它指向新的 tail
self.tail.next = Some(new_tail);
} else {
// 否则，更新 head 指向它
self.head = Some(new_tail);
}
self.tail = raw_tail;
}
|
1
2
3
4
5
6
7
8
9
10
| > cargo build
error[E0609]: no field `next` on type `*mut fifth::Node<T>`
--> src/fifth.rs:31:23
|
31 | self.tail.next = Some(new_tail);
| ----------^^^^
| |
| help: `self.tail` is a raw pointer;
| try dereferencing it: `(*self.tail).next`
|
嗯？我们有一个指向 Node 的指针，为什么不能访问 next 字段？
使用裸指针时 Rust 有点混蛋。要访问裸指针的内容，它坚持让我们手动解引用，因为这是如此不安全的操作。我们来试试：
1
| *self.tail.next = Some(new_tail);
|
1
2
3
4
5
6
7
8
9
10
| > cargo build
error[E0609]: no field `next` on type `*mut fifth::Node<T>`
--> src/fifth.rs:31:23
|
31 | *self.tail.next = Some(new_tail);
| -----------^^^^
| |
| help: `self.tail` is a raw pointer;
| try dereferencing it: `(*self.tail).next`
|
呃呃呃 运算符优先级。
1
| (*self.tail).next = Some(new_tail);
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| > cargo build
error[E0133]: dereference of raw pointer is unsafe and requires
unsafe function or block
--> src/fifth.rs:31:13
|
31 | (*self.tail).next = Some(new_tail);
| ^^^^^^^^^^^^^^^^^ dereference of raw pointer
|
= note: raw pointers may be NULL, dangling or unaligned;
they can violate aliasing rules and cause data races:
all of these are undefined behavior
|
这。不。该。这。么。难。
记得我说过 Unsafe Rust 就像 Safe Rust 的 FFI 语言吗？嗯，编译器要我们显式标出我们在做 FFI 的边界。我们有两个选择。第一，可以把整个函数标为 unsafe，这样它就变成 Unsafe Rust 函数，只能在 unsafe 上下文中调用。这不太好，因为我们希望链表使用起来安全。第二，可以在函数内写 unsafe 块来界定 FFI 边界。这声明整个函数是安全的。我们选后者：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| pub fn push(&mut self, elem: T) {
let mut new_tail = Box::new(Node {
elem: elem,
next: None,
});
let raw_tail: *mut _ = &mut *new_tail;
if !self.tail.is_null() {
// 你好编译器，我知道我在做危险的事，
// 我保证做个从不犯错的优秀程序员。
unsafe {
(*self.tail).next = Some(new_tail);
}
} else {
self.head = Some(new_tail);
}
self.tail = raw_tail;
}
|
1
2
3
4
5
6
7
8
| > cargo build
warning: field is never used: `elem`
--> src/fifth.rs:11:5
|
11 | elem: T,
| ^^^^^^^
|
= note: #[warn(dead_code)] on by default
|
好耶！
有趣的是，到目前为止那是我们唯一必须写 unsafe 块的地方。我们到处都在用裸指针，怎么回事？
原来 Rust 在 unsafe 方面是个巨大的规则律师书呆子。我们相当合理地希望最大化 Safe Rust 程序的集合，因为那些是我们可以更有信心的程序。为此，Rust 精心划定了一个最小的不安全表面。注意我们使用裸指针的其他地方都是赋值，或者只是观察它们是否为 null。
如果你从不实际解引用裸指针，那些完全是安全的事。你只是在读写一个整数！只有当你实际解引用裸指针时才会惹麻烦。所以 Rust 说只有那个操作是不安全的，其他一切完全安全。
超级。书呆子。但技术上正确。
旁白： 世界另一端的某个硬件工程师感到脊背一凉——肯定又有人在坚持指针只是整数。她低头看着自己关于新硬件指针认证方案的提案，落下一滴泪。隔壁的编译器工程师毫无感觉——他们早就学会总是穿厚毛衣了。
只有部分指针操作实际上不安全，这引出了一个有趣的问题：虽然我们 supposed 用 unsafe 块界定不安全范围，但它实际上依赖于块外建立的状态。甚至在函数外！
这就是我所说的 unsafe 污染。一旦你在模块里使用 unsafe，整个模块就被不安全性污染了。一切都必须正确编写，以确保 unsafe 代码的所有不变量得到维护。
这种污染是可管理的，因为隐私。在我们的模块外，所有结构体字段都是完全私有的，所以别人不能以任意方式搞乱我们的状态。只要我们不暴露的 API 组合不会导致坏事，对外部观察者来说，我们所有代码都是安全的！说真的，这和 FFI 情况没什么不同。没人需要关心某个 Python 数学库是否调用 C，只要它暴露安全的接口。
总之，我们继续 pop，基本上就是引用版本的原文：
1
2
3
4
5
6
7
8
9
10
11
12
| pub fn pop(&mut self) -> Option<T> {
self.head.take().map(|head| {
let head = *head;
self.head = head.next;
if self.head.is_none() {
self.tail = ptr::null_mut();
}
head.elem
})
}
|
我们又看到一个安全性是有状态的例子。如果我们在这个函数里忘记把 tail 指针置 null，完全看不出问题。但随后对 push 的调用会开始写入悬垂的 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
| #[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);
// 检查耗尽情况正确修复了指针
list.push(6);
list.push(7);
// 检查正常移除
assert_eq!(list.pop(), Some(6));
assert_eq!(list.pop(), Some(7));
assert_eq!(list.pop(), None);
}
}
|
这只是栈测试，但预期的 pop 结果反过来了。我还在末尾加了额外步骤，确保 pop 中的 tail 指针损坏情况不会发生。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| cargo test
running 12 tests
test fifth::test::basics ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test second::test::basics ... ok
test fourth::test::into_iter ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok
test result: ok. 12 passed; 0 failed; 0 ignored; 0 measured
|
金星！
旁白： 要来了……