5.8 额外内容
原文链接: https://rust-unofficial.github.io/too-many-lists/fifth-extras.html
现在 push 和 pop 写好了，其他一切实际上和栈的情况完全一样，奇怪地。只有改变链表长度的操作需要碰 tail 指针。
当然，现在一切都是 unsafe 指针，我们得重写代码来使用它们！既然要碰所有代码，不妨趁机确保没漏掉什么。
总之，从栈实现复制粘贴代码开始：
1
2
3
4
5
6
7
8
9
10
11
| // ...
pub struct IntoIter<T>(List<T>);
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
pub struct IterMut<'a, T> {
next: Option<&'a mut Node<T>>,
}
|
IntoIter 看起来没问题，但 Iter 和 IterMut 打破了我们类型里不再使用安全指针的简单规则。为安全起见改成用裸指针：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| pub struct IntoIter<T>(List<T>);
pub struct Iter<'a, T> {
next: *mut Node<T>,
}
pub struct IterMut<'a, T> {
next: *mut Node<T>,
}
impl<T> List<T> {
pub fn into_iter(self) -> IntoIter<T> {
IntoIter(self)
}
pub fn iter(&self) -> Iter<'_, T> {
Iter { next: self.head }
}
pub fn iter_mut(&mut self) -> IterMut<'_, T> {
IterMut { next: self.head }
}
}
|
看起来不错！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| error[E0392]: parameter `'a` is never used
--> src\fifth.rs:17:17
|
17 | pub struct Iter<'a, T> {
| ^^ unused parameter
|
= help: consider removing `'a`, referring to it in a field,
or using a marker such as `PhantomData`
error[E0392]: parameter `'a` is never used
--> src\fifth.rs:21:20
|
21 | pub struct IterMut<'a, T> {
| ^^ unused parameter
|
= help: consider removing `'a`, referring to it in a field,
or using a marker such as `PhantomData`
|
看起来不好！他们说的 PhantomData 是什么？
Zero-sized type used to mark things that “act like” they own a T.
Adding a PhantomData<T> field to your type tells the compiler that your type acts as though it stores a value of type T, even though it doesn’t really. This information is used when computing certain safety properties.
For a more in-depth explanation of how to use PhantomData<T>, please see the Nomicon.
嘿别急着，我们读的是我写的书。不是某个大书呆子可能写的那本！我打赌他们那书写的数据结构是像数组栈这种无聊的，不是链表。
Unused lifetime parameters
Perhaps the most common use case for PhantomData is a struct that has an unused lifetime parameter, typically as part of some unsafe code.
啊所以我们在类型里命名了生命周期但实际没用。我们可以走 PhantomData 路线，但我想把它留给下一章真的需要的双向链表。
我们处于实际上不需要 PhantomData 的有趣情况。我想。我就这么声称并相信是真的，如果最后 miri 对我们大喊我就认输做 PhantomData 那套。
我们实际要做的是把引用放回这些 Iterator 类型里，庆幸还能在某些地方用引用。我想那是合理的，因为用迭代器时有一种适当的嵌套：你创建迭代器，用安全引用一段时间，然后丢弃迭代器。
只有迭代器没了你才能访问链表并调用 push、pop 这类需要搞 tail 指针和 Box 的东西。现在，迭代期间我们会解引用一堆裸指针，所以有一种混合，但我们应该能把那些引用看作 unsafe 指针的再借用。
我自己也不是 100% 信服，但我想试试看看！
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
| pub struct IntoIter<T>(List<T>);
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
pub struct IterMut<'a, T> {
next: Option<&'a mut Node<T>>,
}
impl<T> List<T> {
pub fn into_iter(self) -> IntoIter<T> {
IntoIter(self)
}
pub fn iter(&self) -> Iter<'_, T> {
unsafe {
Iter { next: self.head.as_ref() }
}
}
pub fn iter_mut(&mut self) -> IterMut<'_, T> {
unsafe {
IterMut { next: self.head.as_mut() }
}
}
}
|
如果要存引用，需要把裸指针升级为 option-of-references。我们可以检查指针是否为 null，但这是我认为可以用讨厌的 ptr::as_ref 和 ptr::as_mut 的极少数情况之一。
我通常建议像躲瘟疫一样避开这些方法，因为它们做些令人惊讶和恶心的事，而且本质上是在我整个"简单规则是避免那样做"时重新引入引用！
那些方法有很多警告，但最有趣的是：
You must enforce Rust’s aliasing rules, since the returned lifetime 'a is arbitrarily chosen and does not necessarily reflect the actual lifetime of the data. In particular, for the duration of this lifetime, the memory the pointer points to must not get accessed (read or written) through any other pointer.
嘿看我们谈了 25 页的东西！我已经断言我们肯定在这里用引用没问题，所以别名解决了！另一个邪恶部分是签名：
1
| pub unsafe fn as_mut<'a>(self) -> Option<&'a mut T>
|
看到那个生命周期根本没附在输入上，因为 self 是按值吗？是啊那就是我们说的"无界生命周期"，很恶心。它愿意假装成我们要求的那么大，甚至 'static！你处理它的方式是把它放到有界的地方，通常就是"尽快从函数返回，让函数签名限制它"。
男孩我紧张但我们继续冲！从栈偷一些 iterator impl：
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
| impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.0.pop()
}
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
unsafe {
self.next.map(|node| {
self.next = node.next.as_ref();
&node.elem
})
}
}
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
unsafe {
self.next.take().map(|node| {
self.next = node.next.as_mut();
&mut node.elem
})
}
}
}
|
真相时刻……
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| cargo test
running 15 tests
test fifth::test::basics ... ok
test fifth::test::into_iter ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::into_iter ... ok
test fourth::test::peek ... ok
test second::test::basics ... 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::iter ... ok
test third::test::basics ... ok
test result: ok. 15 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out;
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri test
running 15 tests
test fifth::test::basics ... ok
test fifth::test::into_iter ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::into_iter ... ok
test fourth::test::peek ... ok
test second::test::basics ... 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. 15 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
|
好！！！接招吧旁白！有时候我不犯错！
旁白：但整本书的意义不就是错误用来教读者吗。
是啊好吧有时候教训是我对关于 unsafe 代码说的话大家都该听因为我花了太多时间想迭代器实现的健全性？！好吗？！好。
总之这是 peek 和 peek_mut。
1
2
3
4
5
6
7
8
9
10
11
| pub fn peek(&self) -> Option<&T> {
unsafe {
self.head.as_ref()
}
}
pub fn peek_mut(&mut self) -> Option<&mut T> {
unsafe {
self.head.as_mut()
}
}
|
我甚至不打算测它们因为我再也不犯错了。
旁白：cargo build
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| error[E0308]: mismatched types
--> src\fifth.rs:66:13
|
25 | impl<T> List<T> {
| - this type parameter
...
64 | pub fn peek(&self) -> Option<&T> {
| ---------- expected `Option<&T>`
| because of return type
65 | unsafe {
66 | self.head.as_ref()
| ^^^^^^^^^^^^^^^^^^ expected type parameter `T`,
| found struct `fifth::Node`
|
= note: expected enum `Option<&T>`
found enum `Option<&fifth::Node<T>>`
|
好吧。
1
2
3
4
5
6
7
8
9
10
11
| pub fn peek(&self) -> Option<&T> {
unsafe {
self.head.as_ref().map(|node| &node.elem)
}
}
pub fn peek_mut(&mut self) -> Option<&mut T> {
unsafe {
self.head.as_mut().map(|node| &mut node.elem)
}
}
|
我猜我会继续犯错，所以我们要格外小心，加一个我称之为"miri 食物"的新测试：只是到处折腾、大量混合我们的 API，帮 miri 抓我们的错。
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
| #[test]
fn miri_food() {
let mut list = List::new();
list.push(1);
list.push(2);
list.push(3);
assert!(list.pop() == Some(1));
list.push(4);
assert!(list.pop() == Some(2));
list.push(5);
assert!(list.peek() == Some(&3));
list.push(6);
list.peek_mut().map(|x| *x *= 10);
assert!(list.peek() == Some(&30));
assert!(list.pop() == Some(30));
for elem in list.iter_mut() {
*elem *= 100;
}
let mut iter = list.iter();
assert_eq!(iter.next(), Some(&400));
assert_eq!(iter.next(), Some(&500));
assert_eq!(iter.next(), Some(&600));
assert_eq!(iter.next(), None);
assert_eq!(iter.next(), None);
assert!(list.pop() == Some(400));
list.peek_mut().map(|x| *x *= 10);
assert!(list.peek() == Some(&5000));
list.push(7);
// 扔在地上让析构函数自己锻炼
}
|
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
| cargo test
running 16 tests
test fifth::test::basics ... ok
test fifth::test::into_iter ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test fifth::test::miri_food ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::into_iter ... ok
test fourth::test::peek ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::iter ... ok
test second::test::iter ... ok
test third::test::basics ... ok
test result: ok. 16 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri test
running 16 tests
test fifth::test::basics ... ok
test fifth::test::into_iter ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test fifth::test::miri_food ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::into_iter ... ok
test fourth::test::peek ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::iter ... ok
test second::test::iter ... ok
test third::test::basics ... ok
test result: ok. 16 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
|
完美。