八、如何实现链表 在rust的世界中，实现链表并不容易，我们一步一步来。
首先创建一个新项目：
1 cargo new --lib liststudy
1 一个不太优秀的栈实现 栈可以使用单向链表来实现，我们首先来完成它。先创建一个crate：
然后新建一个first.rs，后面的代码全部写在这里。
1.1 布局 链表实际上就是逻辑上相邻而物理上不相邻的线性数据结构，它的定义类似于下面的结构：
1 List a = Empty | Elem a (List a)
显然，它是一个递推关系式，大致读作“列表要么是空的，要么是一个元素后面跟着一个列表”。
为了简单起见，我们将避免使用泛型，基于这个定义的代码如下：
1 2 3 4 pub enum List { Empty, Elem (i32 , List), }
cargo build编译一下看看：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 error[E0072]: recursive type `List` has infinite size --> src\first.rs:1:1 | 1 | pub enum List { | ^^^^^^^^^^^^^ 2 | Empty, 3 | Elem(i32, List), | ---- recursive without indirection | help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle | 3 | Elem(i32, Box<List>), | ++++ + For more information about this error, try `rustc --explain E0072`. error: could not compile `lists` due to previous error
很好，它报错了。在前面box允许创建递归类型 中介绍过，这是一种无限大小的类型，对于编译器而言，所有栈上的类型都必须在编译期有固定的长度。一个简单地解决方案是使用间接的方式打破循环，编译器也给出了提示：
1 2 3 4 help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle | 3 | Elem(i32, Box<List>), | ++++ +
我们按照这个提示，使用智能指针Box改写这个链表的定义：
1 2 3 4 pub enum List { Empty, Elem (i32 , Box <List>), }
再次编译，成功通过。
虽然语法没有问题，但这是非常愚蠢的链表定义，原因如下：
考虑一个拥有两个元素的 List:
1 2 3 4 [] = Stack () = Heap [Elem A, ptr] -> (Elem B, ptr) -> (Empty, *junk*)
有两个关键问题：
最后一个节点分配在了堆上，但是它看上去根本不像一个节点 我们的节点之一根本不是堆分配的，这些节点的分配并不统一 我们希望所有的节点都分配在堆上，但而且，我们发现最后一个节点根本不需要堆分配。
下面考虑另一种布局方式：
1 [ptr] -> (Elem A, ptr) -> (Elem B, *null*)
在这个布局中，我们无条件地堆分配我们的节点。关键区别在于我们的布局中没有垃圾（junk）。这是什么垃圾？要理解这一点，我们需要查看枚举在内存中的布局方式。
一般来说，如果我们有一个像这样的枚举：
1 2 3 4 5 6 enum Foo { D1 (T1), D2 (T2), ... Dn (Tn), }
Foo会占用多少内存空间呢？首先它需要一些整数来指示它代表的枚举的标签（D1,D2,...,Dn），此外，它还需要足够的空间来保证任意一个Di都可以被容纳，因此它占用空间是这些标签中所占内存最大的那一个，最后，可能还需要一些额外的空间来满足内存对齐的需求。
这里最大的问题是，即使 Empty 只占一比特信息，它仍然会为指针和元素消耗更大的空间（所有枚举中所占内存最大的那个），因此我们的第一种布局方式的最后一个节点是额外的元素，其中充满了垃圾，它比第二种布局更消耗空间。
与其让一个节点不进行内存分配，不如让它一直进行内存分配，这是因为它我们需要一个一致的节点布局。这种一致性对于 push 和 pop 节点来说可能没有什么影响，但是对于链表的拆分和合并有影响。
下面就来看一下这两种布局拆分链表时的表现：
1 2 3 4 5 6 7 8 layout 1 : [Elem A, ptr] -> (Elem B, ptr) -> (Elem C, ptr) -> (Empty *junk*) split off C: [Elem A, ptr] -> (Elem B, ptr) -> (Empty *junk*) [Elem C, ptr] -> (Empty *junk*)
1 2 3 4 5 6 7 8 layout 2 : [ptr] -> (Elem A, ptr) -> (Elem B, ptr) -> (Elem C, *null*) split off C: [ptr] -> (Elem A, ptr) -> (Elem B, *null*) [ptr] -> (Elem C, *null*)
可以看出，布局 2 的拆分仅涉及将 B 的指针复制到堆栈并将旧值清空。而在布局 1 中，涉及同样的操作，且需要将 C 节点从堆上拷贝到栈中，而布局 2 则无需此过程。而且从分割后的布局清晰度而言，2 也要优于 1。
很不幸地是我们之前实现的就是布局1的链表，下面改进我们的链表：
1 2 3 4 5 pub enum List { Empty, ElemThenEmpty (i32 ), ElemThenNotEmpty (i32 , Box <List>), }
但是这样做看起来更复杂了，假设现在有一个完全无效的状态： ElemThenNotEmpty(0, Box(Empty)) ，它还仍然会出现分配元素内存不均匀的情况。
我们之前所实现的每个枚举项都必须存储一个标签来指定它所占的比特位代表枚举的哪个变体。但是，如果我们有一种特殊类型的枚举：
1 2 3 4 enum Foo { A, B (ContainsANonNullPtr), }
在这种情况下，会启动空指针的优化，也就是说它会消除枚举成员 A 占用的额外空间，原因在于编译器可以直接将 A 优化成 0，而 B 则不行，因为它包含了非 null 指针。这样一来，编译器就无需给 A 打 tag 进行识别了，而是直接通过 0 就能识别出这是 A 成员，非 0 的自然就是 B 成员。
其实进行这种优化的其他枚举和类型有很多，这就是 Rust 完全未指定枚举布局的原因。 Rust 将为我们做一些更复杂的枚举布局优化，但空指针优化绝对是最重要的，它意味着 & 、 &mut 、 Box 、 Rc 、 Arc 、 Vec 、 Rust 中的其他几个重要类型在放入 Option 时没有任何开销。
那么我们如何避免额外的垃圾，统一分配，并获得优秀的空指针优化呢？我们需要将拥有一个元素的想法与分配另一个链表分开。为此，我们必须像 C 语言一样思考：结构体。
枚举让我们声明一个可以包含多个值之一的类型，而结构体让我们声明一个同时包含多个值的类型。让我们将链表分为两种类型：链表和节点。
1 2 3 4 5 6 7 8 9 struct Node { elem: i32 , next: List, } pub enum List { Empty, More (Box <Node>), }
链表要么是空的，要么有一个元素，然后后面跟着另一个链表，我们通过Node结构体这种独立的类型来表示“有一个元素后面跟着另一个链表的情况”。下面来检查一下这个定义是否符合我们的需求：
链表尾部永远不会分配额外的垃圾 List 枚举的形式可以享受 null 指针优化所有的元素都拥有统一的内存分配 非常好，这也证明了我们最开始的定义是有问题的。编译一下试试：
1 2 3 4 5 6 7 8 error[E0446]: private type `Node` in public interface --> src\first.rs:8:10 | 1 | struct Node { | ----------- `Node` declared as private ... 8 | More(Box<Node>), | ^^^^^^^^^ can't leak private type
这里的错误在于， pub enum 会要求它的所有成员必须是 pub，但是由于 Node 没有声明为 pub，因此产生了冲突。
这里最简单的解决方法就是将 Node 结构体和它的所有字段都标记为 pub :
1 2 3 4 pub struct Node { pub elem: i32 , pub next: List, }
但通常在 Rust 中我们倾向于将实现细节保密。让我们将 List 制作为一个结构体，以便我们可以隐藏实现细节：
1 2 3 4 5 6 7 8 9 10 11 12 13 pub struct List { head: Link, } enum Link { Empty, More (Box <Node>), } struct Node { elem: i32 , next: Link, }
因为 List 是一个具有单个字段的结构体，所以它的大小与该字段相同，这就是rust的零成本抽象。
至此，一个相对还不错的链表布局设计完成，下面尝试使用一下它。
1.2 实现方法 新建链表new 我们想要的第一个方法是构建链表的方法。也就是为List提供一个静态方法：
1 2 3 4 5 impl List { pub fn new () -> Self { List { head: Link::Empty } } }
向链表中push 接下来，让我们编写将一个值推入列表的操作，由于这个方法会改变原链表，因此这里需要使用&mut self：
1 2 3 4 5 impl List { pub fn push (&mut self , elem: i32 ) { } }
首先，我们需要创建一个节点来存储我们的元素：
1 2 3 4 5 6 pub fn push (&mut self , elem: i32 ) { let new_node = Node { elem: elem, next: ????? }; }
我们这里采用的是头插法，next应该填什么呢？好吧，它应该是头节点：
1 2 3 4 5 6 pub fn push (&mut self , elem: i32 ) { let new_node = Node { elem: elem, next: self .head, }; }
但这样会出现问题：
1 2 3 4 5 error[E0507]: cannot move out of `self.head` which is behind a mutable reference --> src\first.rs:23:19 | 23 | next: self.head, | ^^^^^^^^^ move occurs because `self.head` has type `Link`, which does not implement the `Copy` trait
这是由于head并没有实现 Copy特征，我们试图将借用的值 self 中的 head 字段的所有权转移给 next，显然这是不被允许的，因为当我们结束借用并将其“归还”给其合法所有者时，这将使 self 仅部分初始化。
如果我们在最后把东西放回去可不可以呢？
1 2 3 4 5 6 7 8 pub fn push (&mut self , elem: i32 ) { let new_node = Box ::new (Node { elem: elem, next: self .head, }); self .head = Link::More (new_node); }
原则上，这是 Rust 实际上可以接受的，但是由于各种原因（主要是Exception safety ），这种方法并不会被接受。
我们需要一个办法，让 Rust 不再阻挠我们，其中一个可行的办法是使用 clone：
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 pub struct List { head: Link, } #[derive(Clone)] enum Link { Empty, More (Box <Node>), } #[derive(Clone)] struct Node { elem: i32 , next: Link, } impl List { pub fn new () -> Self { List { head: Link::Empty } } pub fn push (&mut self , elem: i32 ) { let new_node = Node { elem: elem, next: self .head.clone (), }; } }
我们为Link和Node派生clone，然后不需要转移所有权，只需要将其克隆即可。但是，这样显然每次插入都需要有额外的拷贝内存的花销，性能上并不是一个好的方案。
Rust Hacker Indiana Jones 提供了一种方法，就是采用 mem::replace 策略。这个非常有用的函数让我们可以通过用另一个值替换它来从借用中窃取一个值。
1 2 3 4 5 6 7 8 9 use std::mem;pub fn push (&mut self , elem: i32 ) { let new_node = Box ::new (Node { elem: elem, next: mem::replace (&mut self .head, Link::Empty), }); self .head = Link::More (new_node); }
std::mem::replace
1 pub fn replace <T>(dest: &mut T, src: T) -> T
将 src 移动到引用的 dest 中，返回之前的 dest 值。两个值都不会被丢弃。比如：
1 2 3 4 5 6 7 use std::mem;let mut v : Vec <i32 > = vec! [1 , 2 ];let old_v = mem::replace (&mut v, vec! [3 , 4 , 5 ]);assert_eq! (vec! [1 , 2 ], old_v);assert_eq! (vec! [3 , 4 , 5 ], v);
在我们的例子中，我们先暂时将self.head替换为Link::Empty，mem::replace的返回值仍然是原来的头节点。最后，我们再将其替换为新的链表头：self.head = Link::More(new_node)。这种看起来偷梁换柱的做法似乎是目前rust可以实现的最好方法了。
从链表中pop 与 push 一样， pop 会改变链表。与 push 不同，我们实际上想要返回pop出去的元素。但是 pop 还必须处理一个棘手的极端情况：如果链表此时为空怎么办？因此，为了表示这种情况，我们使用可信的 Option 类型：
1 2 3 pub fn pop (&mut self ) -> Option <i32 > { }
判断链表是否为空可以使用match匹配：
1 2 3 4 5 6 7 8 9 10 pub fn pop (&mut self ) -> Option <i32 > { match self .head { Link::Empty => { } Link::More (node) => { } }; }
这段代码还不可以直接编译，这是因为pop 必须返回一个值，但我们还没有这样做。返回 unimplemented!() 是不错的主意，以表明我们尚未完成该函数的实现。该宏可以明确地表示目前的代码还没有实现，一旦代码执行到 unimplemented!() 的位置，就会发生一个 panic。panics是一种发散函数，发散函数永远不会返回给调用者，因此它们可以用在需要任何类型值的地方。因此，可以使用 unimplemented!() 代替 Option<T> 类型的值。另外，match会发生所有权转移，因此这里还需要使用引用&self.head：
1 2 3 4 5 6 7 8 9 10 11 pub fn pop (&mut self ) -> Option <i32 > { match &self .head { Link::Empty => { } Link::More (node) => { } }; unimplemented! () }
cargo build编译一下，可以通过。
下面开始填写内部逻辑，当链表为空时，返回None即可；当链表不为空时，我们需要返回 Some(i32) ，并更改列表的头部。
1 2 3 4 5 6 7 8 9 10 11 12 13 pub fn pop (&mut self ) -> Option <i32 > { let result ; match &self .head { Link::Empty => { result = None ; } Link::More (node) => { result = Some (node.elem); self .head = node.next; } }; result }
再次编译，报错了：
1 2 3 4 5 error[E0507]: cannot move out of `node.next` which is behind a shared reference --> src\first.rs:38:29 | 38 | self.head = node.next; | ^^^^^^^^^ move occurs because `node.next` has type `Link`, which does not implement the `Copy` trait
发生了类似的错误，我们试图转移node.next的所有权，但我们仅仅拥有它的引用，这是rust不允许的。看来，只能故技重施了，利用上一节的方法：
1 2 3 4 5 6 7 8 9 10 11 12 13 pub fn pop (&mut self ) -> Option <i32 > { let result ; match mem::replace (&mut self .head, Link::Empty) { Link::Empty => { result = None ; } Link::More (node) => { result = Some (node.elem); self .head = node.next; } }; result }
我们将 self.head 的值窃取出来，然后再将 Link::Empty 填回到 self.head 中。此时用于 match 匹配的就是一个拥有所有权的值类型，而不是之前的引用类型。
实际上，我们这里并不需要定义result，而是利用表达式返回的特性：
1 2 3 4 5 6 7 8 9 pub fn pop (&mut self ) -> Option <i32 > { match mem::replace (&mut self .head, Link::Empty) { Link::Empty => None , Link::More (node) => { self .head = node.next; Some (node.elem) } } }
这更加简洁和常用，Link::Empty分支只有一个表达式，因此可以将大括号去掉。
1.3 单元测试 下面为实现的链表添加一个小的单元测试：
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 (3 )); assert_eq! (list.pop (), Some (2 )); list.push (4 ); list.push (5 ); assert_eq! (list.pop (), Some (5 )); assert_eq! (list.pop (), Some (4 )); assert_eq! (list.pop (), Some (1 )); assert_eq! (list.pop (), None ); } }
这里需要注意将测试代码与定义代码放在一起，并且使用use super::List进行导入。运行cargo test：
1 2 3 4 5 6 7 8 9 10 running 1 test test first::test::basics ... ok test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s Doc-tests liststudy running 0 tests test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
通过测试。
1.4 手动清理 前面已经可以创建一个基于链表实现的栈， 并测试了推入和弹出元素的功能一切正常。
下面还有一个问题，我们需要担心清理我们的列表吗？事实上并不需要，如果一个类型实现了Droptrait，则该类型具有析构函数。rust为几乎所有类型都实现了Drop，对于自定义的结构体，只要结构体的所有字段都实现了 Drop，那结构体也会自动实现 Drop。rust会自动地帮我们处理好一切。
但是，有些时候由rust自动处理会很糟糕。我们实现的链表就是一个例子，考虑以下链表:
当 List 被自动 drop 后，接着会去尝试 Drop A ，然后是 B，最后是 C。这是一个递归代码，而递归代码可以炸毁堆栈。事实上确实如此，我们再添加一个测试：
1 2 3 4 5 6 7 8 #[test] fn long_list () { let mut list = List::new (); for i in 0 ..100000 { list.push (i); } }
测试代码会试图创建一个很长的链表，当超出作用域被自动Drop时，会直接爆栈：
1 thread 'first::test::long_list' has overflowed its stack
你可能会想“这是尾递归，编译器会确保这样的代码不会破坏堆栈”，那就大错特错了。首先，rust目前似乎还没有支持尾递归优化，其次，就算支持尾递归，也是不可行的。让我们尝试模拟编译器在Drop时进行的操作：
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 impl Drop for List { fn drop (&mut self ) { self .head.drop (); } } impl Drop for Link { fn drop (&mut self ) { match *self { Link::Empty => {} Link::More (ref mut boxed_node) => { boxed_node.drop (); } } } } impl Drop for Box <Node> { fn drop (&mut self ) { self .ptr.drop (); deallocate (self .ptr); } } impl Drop for Node { fn drop (&mut self ) { self .next.drop (); } }
可以看出，在 self.ptr.drop 后调用的 deallocate 会导致非尾递归的情况发生。
因此，这里需要手动为 List 实现 Drop：
1 2 3 4 5 6 7 8 9 10 11 impl Drop for List { fn drop (&mut self ) { let mut cur_link = mem::replace (&mut self .head, Link::Empty); while let Link ::More (mut boxed_node) = cur_link { cur_link = mem::replace (&mut boxed_node.next, Link::Empty); } } }
这里手动为 List 编写一个迭代丢弃节点的析构函数。
再次运行测试，通过。
事实上，我们在这里做了提前优化。drop函数与 while let Some(_) = self.pop() { } 非常相似，为什么不使用这个方法呢？这是因为，pop返回 Option<i32> ，而我们的实现仅操作 Box<Node> 。因此，我们的实现仅围绕指向节点的指针移动，而基于弹出的实现将围绕我们存储在节点中的值移动。当链表中包含的值是其他较大的类型时，这种移动的开销可能会非常高昂，Box能够原地运行其内容的 drop实现，因此它不会遇到此问题。
1.5 最终代码 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 use std::mem;pub struct List { head: Link, } enum Link { Empty, More (Box <Node>), } struct Node { elem: i32 , next: Link, } impl List { pub fn new () -> Self { List { head: Link::Empty } } pub fn push (&mut self , elem: i32 ) { let new_node = Box ::new (Node { elem: elem, next: mem::replace (&mut self .head, Link::Empty), }); self .head = Link::More (new_node); } pub fn pop (&mut self ) -> Option <i32 > { match mem::replace (&mut self .head, Link::Empty) { Link::Empty => None , Link::More (node) => { self .head = node.next; Some (node.elem) } } } } impl Drop for List { fn drop (&mut self ) { let mut cur_link = mem::replace (&mut self .head, Link::Empty); while let Link ::More (mut boxed_node) = cur_link { cur_link = mem::replace (&mut boxed_node.next, Link::Empty); } } } #[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 (3 )); assert_eq! (list.pop (), Some (2 )); list.push (4 ); list.push (5 ); assert_eq! (list.pop (), Some (5 )); assert_eq! (list.pop (), Some (4 )); assert_eq! (list.pop (), Some (1 )); assert_eq! (list.pop (), None ); } #[test] fn long_list () { let mut list = List::new (); for i in 0 ..100000 { list.push (i); } } }
2 还可以的栈实现 上一小节我们编写了一个最小可行的基于链表实现的栈，然而，有一些设计决策让它变得有点糟糕。让我们添加一个名为 second.rs 的新文件：
1 2 3 4 pub mod first;pub mod second;
并将 first.rs 中的所有内容复制到其中。
2.1 使用Option 你可能已经注意到了，我们发明了一个非常糟糕的Option：
1 2 3 4 enum Link { Empty, More (Box <Node>), }
它其实跟 Option<Box<Node>> 非常类似，因此没必要重复造轮子，直接使用Option替代枚举。并且我们可以使用类型别名优化这种写法，不必在任何地方都编写 Option<Box<Node>>。首先，我们将简单通过将所有内容重命名为使用 Some 和 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 47 use std::mem;pub struct List { head: Link, } type Link = Option <Box <Node>>;struct Node { elem: i32 , next: Link, } impl List { pub fn new () -> Self { List { head: None } } pub fn push (&mut self , elem: i32 ) { let new_node = Box ::new (Node { elem: elem, next: mem::replace (&mut self .head, None ), }); self .head = Some (new_node); } pub fn pop (&mut self ) -> Option <i32 > { match mem::replace (&mut self .head, None ) { None => None , Some (node) => { self .head = node.next; Some (node.elem) } } } } impl Drop for List { fn drop (&mut self ) { let mut cur_link = mem::replace (&mut self .head, None ); while let Some (mut boxed_node) = cur_link { cur_link = mem::replace (&mut boxed_node.next, None ); } } }
看上去稍微好了一些，但是 Option 的好处远不止这些。
首先， mem::replace(&mut option, None) 是一个极其常见的习惯用法，以至于 Option 实际上继续将其变成一个方法：take。
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 pub struct List { head: Link, } type Link = Option <Box <Node>>;struct Node { elem: i32 , next: Link, } impl List { pub fn new () -> Self { List { head: None } } pub fn push (&mut self , elem: i32 ) { let new_node = Box ::new (Node { elem: elem, next: self .head.take (), }); self .head = Some (new_node); } pub fn pop (&mut self ) -> Option <i32 > { match self .head.take () { None => None , Some (node) => { self .head = node.next; Some (node.elem) } } } } impl Drop for List { fn drop (&mut self ) { let mut cur_link = self .head.take (); while let Some (mut boxed_node) = cur_link { cur_link = boxed_node.next.take (); } } }
其次， match option { None => None, Some(x) => Some(y) } 是一个极其常见的习惯用法，可以直接使用 map 方法代替，map 会对 Some(x) 中的值进行映射，最终返回一个新的 Some(y) 值。
1 2 3 4 5 6 pub fn pop (&mut self ) -> Option <i32 > { self .head.take ().map (|node| { self .head = node.next; node.elem }) }
关于map的具体用法和函数签名可以参考这里 。
再次运行cargo test，可以通过，说明我们的改动确保链表依然可以正常运行。
2.2 使用泛型 目前链表只能支持i32类型，我们可以使用泛型来优化这一限制：
1 2 3 4 5 6 7 8 9 10 pub struct List <T> { head: Link<T>, } type Link <T> = Option <Box <Node<T>>>;struct Node <T> { elem: T, next: Link<T>, }
这实际上非常简单，只需要将所有类型标注替换为T即可，但是仅仅这样还是不够：
1 2 3 4 5 6 7 8 9 10 11 12 13 > cargo test error[E0107]: wrong number of type arguments: expected 1, found 0 --> src/second.rs:14:6 | 14 | impl List { | ^^^^ expected 1 type argument error[E0107]: wrong number of type arguments: expected 1, found 0 --> src/second.rs:36:15 | 36 | impl Drop for List { | ^^^^ expected 1 type argument
问题很清楚：泛型参数也是类型定义的一部分，我们现在要实现的是List<T>：
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>, } 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 } } pub fn push (&mut self , elem: T) { let new_node = Box ::new (Node { elem: elem, next: self .head.take (), }); self .head = Some (new_node); } pub fn pop (&mut self ) -> Option <T> { self .head.take ().map (|node| { self .head = node.next; node.elem }) } } impl <T> Drop for List <T> { fn drop (&mut self ) { let mut cur_link = self .head.take (); while let Some (mut boxed_node) = cur_link { cur_link = boxed_node.next.take (); } } }
很好，我们所有的代码现在对于任意T的类型都是完全通用的。并且，new甚至没有改变：
1 2 3 pub fn new () -> Self { List { head: None } }
这是由于Self决定了构造时永远返回自身所代表的类型，因此这里返回的就是 List<T>，很方便。
2.3 实现peek 下面尝试为链表实现peek方法，该方法返回对列表头部元素的引用（如果存在）。听起来很简单，让我们尝试一下：
1 2 3 4 5 pub fn peek (&self ) -> Option <&T> { self .head.map (|node| { &node.elem }) }
不出意外的话就要出意外了：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 error[E0515]: cannot return reference to local data `node.elem` --> src\second.rs:34:30 | 34 | self.head.map(|node| &node.elem) | ^^^^^^^^^^ returns a reference to data owned by the current function error[E0507]: cannot move out of `self.head` which is behind a shared reference --> src\second.rs:34:9 | 34 | self.head.map(|node| &node.elem) | ^^^^^^^^^ ---------------------- `self.head` moved due to this method call | | | help: consider calling `.as_ref()` or `.as_mut()` to borrow the type's contents | move occurs because `self.head` has type `Option<Box<second::Node<T>>>`, which does not implement the `Copy` trait
问题很明显，我们不能将内部值的引用返回给函数外的调用者。一个比较好的解决办法就是让 map 作用在引用上，而不是直接作用在 self.head 上，为此我们可以使用 Option 的 as_ref 方法：
1 2 3 impl <T> Option <T> { pub fn as_ref (&self ) -> Option <&T>; }
它获取&self返回Option<&T>，然后再调用 map 就会对引用进行处理了：
1 2 3 4 5 pub fn peek (&self ) -> Option <&T> { self .head.as_ref ().map (|node| { &node.elem }) }
我们还可以使用 as_mut 制作此方法的可变版本：
1 2 3 4 5 pub fn peek_mut (&mut self ) -> Option <&mut T> { self .head.as_mut ().map (|node| { &mut node.elem }) }
测试一下，编写一个新的单元测试函数：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #[test] fn peek () { let mut list = List::new (); assert_eq! (list.peek (), None ); assert_eq! (list.peek_mut (), None ); list.push (1 ); list.push (2 ); list.push (3 ); assert_eq! (list.peek (), Some (&3 )); assert_eq! (list.peek_mut (), Some (&mut 3 )); list.peek_mut ().map (|&mut value| { value = 42 }); assert_eq! (list.peek (), Some (&42 )); assert_eq! (list.pop (), Some (42 )); }
运行cargo test，报错了：
1 2 3 4 5 6 7 100 | list.peek_mut().map(|&mut value| { | ----- | | | first assignment to `value` | help: consider making this binding mutable: `mut value` 101 | value = 42 | ^^^^^^^^^^ cannot assign twice to immutable variable
编译器提示 value 是不可变的，但我们非常清楚地写了 &mut value。这是什么原因导致的？
实际上 &mut value 是一个模式匹配，它用 &mut value 模式去匹配一个可变的引用，|&mut value| 表示“参数是可变引用，但请将其指向的值复制到 value 中。此时匹配出来的 value 显然是一个值，而不是可变引用，如果我们只使用 |value| ， value 的类型将是 &mut i32：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #[test] fn peek () { let mut list = List::new (); assert_eq! (list.peek (), None ); assert_eq! (list.peek_mut (), None ); list.push (1 ); list.push (2 ); list.push (3 ); assert_eq! (list.peek (), Some (&3 )); assert_eq! (list.peek_mut (), Some (&mut 3 )); list.peek_mut ().map (|value| { *value = 42 }); assert_eq! (list.peek (), Some (&42 )); assert_eq! (list.pop (), Some (42 )); }
这次我们直接匹配出来可变引用 value，然后对其修改即可。
再次运行测试，全部通过。
2.4 迭代器 rust中，你可以通过为类型实现Iteratortrait来实现迭代器，它的定义之前已经见过了，再复习一下：
1 2 3 4 pub trait Iterator { type Item ; fn next (&mut self ) -> Option <Self ::Item>; }
Item是关联类型，被用作 next 方法的返回值类型。换句话说，Item 类型将是迭代器返回元素的类型。这样说可能并不准确，因为该类型被包含在Option中，使用Option<Self::Item>的原因是因为该接口合并了 has_next 和 get_next 概念。调用next时，有值时返回 Some(T)，无值时返回 None，这使得 API 通常更符合人体工程学，并且使用和实现更安全，同时避免 has_next 和 get_next 之间的冗余检查和逻辑。
遗憾的是，rust目前还没有类似 yield 语句的东西，所以我们必须自己实现逻辑。另外，迭代器有三种：
iter返回的迭代器会获取集合元素的不可变引用，对应Itertarititer_mut返回的迭代器会获取集合元素的可变引用，对应IterMuttaritinto_iter返回的迭代器会获取集合元素的所有权，对应IntoItertarit实现IntoIter 它是最好实现的，我们通过元组结构体的方式定义IntoIter：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 pub struct IntoIter <T>(List<T>);impl <T> List<T> { pub fn into_iter (self ) -> IntoIter<T> { IntoIter (self ) } } impl <T> Iterator for IntoIter <T> { type Item = T; fn next (&mut self ) -> Option <Self ::Item> { self .0 .pop () } }
只需一遍又一遍地调用 pop 即可。编写一个测试：
1 2 3 4 5 6 7 8 9 10 11 #[test] fn into_iter () { let mut list = List::new (); list.push (1 ); list.push (2 ); list.push (3 ); let mut iter = list.into_iter (); assert_eq! (iter.next (), Some (3 )); assert_eq! (iter.next (), Some (2 )); assert_eq! (iter.next (), Some (1 )); assert_eq! (iter.next (), None ); }
OK，可以通过。
实现Iter 现在尝试实现Iter，这次会稍微复杂点，因为这涉及到引用和生命周期。
我们实现的基本逻辑是保存一个指向我们要生成下一个的当前节点的指针。因为该节点可能不存在（列表为空或者我们已经完成迭代），所以我们希望该引用是一个Option。当产生一个元素时，我们想要继续到当前节点的 next 节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 pub struct Iter <T> { next: Option <&Node<T>>, } impl <T> List<T> { pub fn iter (&self ) -> Iter<T> { Iter { next: self .head.map (|node| &node) } } } impl <T> Iterator for Iter <T> { type Item = &T; fn next (&mut self ) -> Option <Self ::Item> { self .next.map (|node| { self .next = node.next.map (|node| &node); &node.elem }) } }
编译…失败了。
1 2 3 4 5 6 7 8 9 | 72 | next: Option<&Node<T>>, | ^ expected lifetime parameter error[E0106]: missing lifetime specifier --> src/second.rs:82:17 | 82 | type Item = &T; | ^ expected lifetime parameter
我们按照提示来修改代码，加入生命周期注解：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 pub struct Iter <'a , T> { next: Option <&'a Node<T>>, } impl <'a , T> List<T> { pub fn iter (&'a self ) -> Iter<'a , T> { Iter { next: self .head.map (|node| &'a node) } } } impl <'a , T> Iterator for Iter <'a , T> { type Item = &'a T; fn next (&'a mut self ) -> Option <Self ::Item> { self .next.map (|node| { self .next = node.next.map (|node| &'a node); &'a 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 pub struct Iter <'a , T> { next: Option <&'a Node<T>>, } impl <T> List<T> { pub fn iter <'a >(&'a self ) -> Iter<'a , T> { Iter { next: self .head.map (|node| &node) } } } impl <'a , T> Iterator for Iter <'a , T> { type Item = &'a T; fn next (&mut self ) -> Option <Self ::Item> { self .next.map (|node| { self .next = node.next.map (|node| &node); &node.elem }) } }
编译一下。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 error[E0308]: mismatched types --> src/second.rs:77:22 | 77 | Iter { next: self.head.map(|node| &node) } | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box` | = note: expected type `std::option::Option<&second::Node<T>>` found type `std::option::Option<&std::boxed::Box<second::Node<T>>>` error[E0308]: mismatched types --> src/second.rs:85:25 | 85 | self.next = node.next.map(|node| &node); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box` | = note: expected type `std::option::Option<&'a second::Node<T>>` found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`
生命周期的问题解决了，但是又引入了新的错误。原因在于，我们希望存储 &Node 但是获取的却是 &Box<Node>。好吧，这很简单，我们只需要在获取引用之前取消引用Box即可：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 impl <T> List<T> { pub fn iter <'a >(&'a self ) -> Iter<'a , T> { Iter { next: self .head.map (|node| &*node) } } } impl <'a , T> Iterator for Iter <'a , T> { type Item = &'a T; fn next (&mut self ) -> Option <Self ::Item> { self .next.map (|node| { self .next = node.next.map (|node| &*node); &node.elem }) } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | 77 | Iter { next: self.head.map(|node| &*node) } | ^^^^^^ returns a reference to data owned by the current function error[E0507]: cannot move out of borrowed content --> src/second.rs:77:22 | 77 | Iter { next: self.head.map(|node| &*node) } | ^^^^^^^^^ cannot move out of borrowed content error[E0515]: cannot return reference to local data `*node` --> src/second.rs:85:46 | 85 | self.next = node.next.map(|node| &*node); | ^^^^^^ returns a reference to data owned by the current function error[E0507]: cannot move out of borrowed content --> src/second.rs:85:25 | 85 | self.next = node.next.map(|node| &*node); | ^^^^^^^^^ cannot move out of borrowed content
又怎么了？原因是这里我们忘记了 as_ref ，然后值的所有权被转移到了 map 中，结果我们在内部引用了一个局部值，造成一个悬垂引用：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 pub struct Iter <'a , T> { next: Option <&'a Node<T>>, } impl <T> List<T> { pub fn iter <'a >(&'a self ) -> Iter<'a , T> { Iter { next: self .head.as_ref ().map (|node| &*node) } } } impl <'a , T> Iterator for Iter <'a , T> { type Item = &'a T; fn next (&mut self ) -> Option <Self ::Item> { self .next.map (|node| { self .next = node.next.as_ref ().map (|node| &*node); &node.elem }) } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 --> src/second.rs:77:22 | 77 | Iter { next: self.head.as_ref().map(|node| &*node) } | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box` | = note: expected type `std::option::Option<&second::Node<T>>` found type `std::option::Option<&std::boxed::Box<second::Node<T>>>` error[E0308]: mismatched types --> src/second.rs:85:25 | 85 | self.next = node.next.as_ref().map(|node| &*node); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box` | = note: expected type `std::option::Option<&'a second::Node<T>>` found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`
还是不行，这次是为什么？错误的原因是，as_ref 增加了一层间接引用，需要被移除，这里使用另外一种方式来实现：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 pub struct Iter <'a , T> { next: Option <&'a Node<T>>, } impl <T> List<T> { pub fn iter <'a >(&'a self ) -> Iter<'a , T> { Iter { next: self .head.as_deref () } } } impl <'a , T> Iterator for Iter <'a , T> { type Item = &'a T; fn next (&mut self ) -> Option <Self ::Item> { self .next.map (|node| { self .next = node.next.as_deref (); &node.elem }) } }
as_deref 和 as_deref_mut 函数在 Rust 1.40 版本中正式稳定下来。在那之前，你只能在 stable 版本中使用 map(|node| &**node) 和 map(|node| &mut**node) 的方式来替代。参考官方文档 。
但是 Deref 在这里并不能很好的完成自己的任务，原因是在闭包中使用 Option<&T> 而不是 &T 对于它来说有些过于复杂了，因此我们需要显式地去帮助它完成任务。好在根据我的经验来看，这种情况还是相当少见的。
事实上，还可以使用另一种方式来实现：
1 self .next = node.next.as_ref ().map::<&Node<T>, _>(|node| &node);
这种类型暗示的方式可以使用的原因在于 map 是一个泛型函数：
1 pub fn map <U, F>(self , f: F) -> Option <U>
turbofish 形式的符号 ::<> 可以告诉编译器我们希望用哪个具体的类型来替代泛型类型，在这种情况里，::<&Node<T>, _> 意味着: 它应该返回一个 &Node<T>。这种方式可以让编译器知道它需要对 &node 应用 deref，这样我们就不用手动的添加 ** 来进行解引用。
总之，让我们编写一个测试看看效果：
1 2 3 4 5 6 7 8 9 10 #[test] fn iter () { let mut list = List::new (); list.push (1 ); list.push (2 ); list.push (3 ); let mut iter = list.iter (); assert_eq! (iter.next (), Some (&3 )); assert_eq! (iter.next (), Some (&2 )); assert_eq! (iter.next (), Some (&1 )); }
1 2 3 4 5 6 7 8 9 10 running 7 tests test second::test::basics ... ok test first::test::basics ... ok test second::test::iter ... ok test second::test::into_iter ... ok test second::test::peek ... ok test second::test::long_list ... ok test first::test::long_list ... ok test result: ok. 7 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.03s
没有问题。
最后，应该指出的是，我们实际上可以在这里应用生命周期消除（Lifetime Elision） 规则。
1 2 3 4 5 impl <T> List<T> { pub fn iter <'a >(&'a self ) -> Iter<'a , T> { Iter { next: self .head.as_deref () } } }
相当于：
1 2 3 4 5 impl <T> List<T> { pub fn iter (&self ) -> Iter<T> { Iter { next: self .head.as_deref () } } }
实现IterMut 再来回顾下 Iter 的实现：
1 2 3 4 5 impl <'a , T> Iterator for Iter <'a , T> { type Item = &'a T; fn next (&mut self ) -> Option <Self ::Item> { } }
它可以脱糖为：
1 2 3 4 5 impl <'a , T> Iterator for Iter <'a , T> { type Item = &'a T; fn next <'b >(&'b mut self ) -> Option <&'a T> { } }
可以看出 next 方法的输入和输出之间的生命周期并没有关联，这样我们就可以无条件的一遍又一遍地调用 next：
1 2 3 4 5 6 7 let mut list = List::new ();list.push (1 ); list.push (2 ); list.push (3 ); let mut iter = list.iter ();let x = iter.next ().unwrap ();let y = iter.next ().unwrap ();let z = iter.next ().unwrap ();
对于不可变借用而言，这种方式没有任何问题，因为不可变借用可以同时存在多个，但是可变引用不能共存，你可能会认为最终结果是使用安全代码编写IterMut变得非常困难，但是令人诧异的是，事实上，我们可以使用安全的代码来为很多数据结构实现 IterMut。
我们首先使用Iter代码并将所有内容更改为可变的：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 pub struct IterMut <'a , T> { next: Option <&'a mut Node<T>>, } impl <T> List<T> { pub fn iter_mut (&mut self ) -> IterMut<'_ , T> { IterMut { next: self .head.as_deref_mut () } } } impl <'a , T> Iterator for IterMut <'a , T> { type Item = &'a mut T; fn next (&mut self ) -> Option <Self ::Item> { self .next.map (|node| { self .next = node.next.as_deref_mut (); &mut node.elem }) } }
1 2 3 4 5 6 7 8 9 10 11 12 error[E0507]: cannot move out of `self.next` which is behind a mutable reference --> src\second.rs:104:9 | 104 | self.next.map(|node| { | _________^^^^^^^^^_- | | | | | help: consider calling `.as_ref()` or `.as_mut()` to borrow the type's contents | | move occurs because `self.next` has type `Option<&mut second::Node<T>>`, which does not implement the `Copy` trait 105 | | self.next = node.next.as_deref_mut(); 106 | | &mut node.elem 107 | | }) | |__________- `self.next` moved due to this method call
错误原因在于，对于有些类型是不可以Copy的，对于之前的Iter来说，因为 & 是可以被copy，所以 Option<&> 也可以被copy。但尴尬的是，可变引用 &mut T 不可以（如果复制了&mut，则会将两个&mut复制到内存中的同一位置，这是不允许的，一般可变引用只能同时存在一个），因此我们需要使用 take 方法来处理这种情况：
1 2 3 4 5 6 fn next (&mut self ) -> Option <Self ::Item> { self .next.take ().map (|node| { self .next = node.next.as_deref_mut (); &mut node.elem }) }
可以通过编译，让我们测试一下。
1 2 3 4 5 6 7 8 9 10 #[test] fn iter_mut () { let mut list = List::new (); list.push (1 ); list.push (2 ); list.push (3 ); let mut iter = list.iter_mut (); assert_eq! (iter.next (), Some (&mut 3 )); assert_eq! (iter.next (), Some (&mut 2 )); assert_eq! (iter.next (), Some (&mut 1 )); }
1 2 3 4 5 6 7 8 9 10 11 12 13 > cargo test Running target/debug/lists-5c71138492ad4b4a running 6 tests test first::test::basics ... ok test second::test::basics ... ok test second::test::iter_mut ... ok test second::test::into_iter ... ok test second::test::iter ... ok test second::test::peek ... ok test result: ok. 7 passed; 0 failed; 0 ignored; 0 measured
2.5 最终代码 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 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 pub struct List <T> { head: 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 } } pub fn push (&mut self , elem: T) { let new_node = Box ::new (Node { elem: elem, next: self .head.take (), }); self .head = Some (new_node); } pub fn pop (&mut self ) -> Option <T> { self .head.take ().map (|node| { self .head = node.next; node.elem }) } pub fn peek (&self ) -> Option <&T> { self .head.as_ref ().map (|node| { &node.elem }) } pub fn peek_mut (&mut self ) -> Option <&mut T> { self .head.as_mut ().map (|node| { &mut node.elem }) } pub fn into_iter (self ) -> IntoIter<T> { IntoIter (self ) } pub fn iter (&self ) -> Iter<'_ , T> { Iter { next: self .head.as_deref () } } pub fn iter_mut (&mut self ) -> IterMut<'_ , T> { IterMut { next: self .head.as_deref_mut () } } } impl <T> Drop for List <T> { fn drop (&mut self ) { let mut cur_link = self .head.take (); while let Some (mut boxed_node) = cur_link { cur_link = boxed_node.next.take (); } } } pub struct IntoIter <T>(List<T>);impl <T> Iterator for IntoIter <T> { type Item = T; fn next (&mut self ) -> Option <Self ::Item> { self .0 .pop () } } pub struct Iter <'a , T> { next: Option <&'a Node<T>>, } impl <'a , T> Iterator for Iter <'a , T> { type Item = &'a T; fn next (&mut self ) -> Option <Self ::Item> { self .next.map (|node| { self .next = node.next.as_deref (); &node.elem }) } } pub struct IterMut <'a , T> { next: Option <&'a mut Node<T>>, } impl <'a , T> Iterator for IterMut <'a , T> { type Item = &'a mut T; fn next (&mut self ) -> Option <Self ::Item> { self .next.take ().map (|node| { self .next = node.next.as_deref_mut (); &mut node.elem }) } } #[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 (3 )); assert_eq! (list.pop (), Some (2 )); list.push (4 ); list.push (5 ); assert_eq! (list.pop (), Some (5 )); assert_eq! (list.pop (), Some (4 )); assert_eq! (list.pop (), Some (1 )); assert_eq! (list.pop (), None ); } #[test] fn peek () { let mut list = List::new (); assert_eq! (list.peek (), None ); assert_eq! (list.peek_mut (), None ); list.push (1 ); list.push (2 ); list.push (3 ); assert_eq! (list.peek (), Some (&3 )); assert_eq! (list.peek_mut (), Some (&mut 3 )); list.peek_mut ().map (|value| { *value = 42 }); assert_eq! (list.peek (), Some (&42 )); assert_eq! (list.pop (), Some (42 )); } #[test] fn into_iter () { let mut list = List::new (); list.push (1 ); list.push (2 ); list.push (3 ); let mut iter = list.into_iter (); assert_eq! (iter.next (), Some (3 )); assert_eq! (iter.next (), Some (2 )); assert_eq! (iter.next (), Some (1 )); assert_eq! (iter.next (), None ); } #[test] fn iter () { let mut list = List::new (); list.push (1 ); list.push (2 ); list.push (3 ); let mut iter = list.iter (); assert_eq! (iter.next (), Some (&3 )); assert_eq! (iter.next (), Some (&2 )); assert_eq! (iter.next (), Some (&1 )); } #[test] fn iter_mut () { let mut list = List::new (); list.push (1 ); list.push (2 ); list.push (3 ); let mut iter = list.iter_mut (); assert_eq! (iter.next (), Some (&mut 3 )); assert_eq! (iter.next (), Some (&mut 2 )); assert_eq! (iter.next (), Some (&mut 1 )); } }
3 持久化单链表 迄今为止，我们已经掌握了如何实现一个可变的单向链表。但是之前的链表都是单所有权的，在实际使用中，共享所有权才是更实用的方式，下面一起来看看该如何实现一个不可变的、共享所有权的持久化链表。我们将在很大程度上熟悉Rc和Arc，首先，我们添加一个名为 third.rs 的新文件：
1 2 3 4 5 pub mod first;pub mod second;pub mod third;
这次我们无需拷贝之前的代码，而是从零开始构建一个新的链表。
3.1 数据布局 持久化单链表最重要的是，基本上可以自由操作列表的尾部：
例如以下是一个不太常见的持久化链表布局：
1 2 3 list1 = A -> B -> C -> D list2 = tail(list1) = B -> C -> D list3 = push(list2, X) = X -> B -> C -> D
从内存的角度看起来像这样：
1 2 3 4 5 6 7 list1 -> A ---+ | v list2 ------> B -> C -> D ^ | list3 -> X ---+
在这种布局下，B 的所有权是共享的，因此Box无法完成任务，如果使用 Box，那么谁来负责清理释放？如果drop list2，那 B 节点会被清理释放吗？
函数式语言（实际上几乎所有其他语言）都通过使用垃圾收集（GC）来解决这个问题。借助GC的魔力，只有当所有人都停止使用B时，B才会被释放。Rust 没有像这些语言那样的垃圾收集器，相反，Rust 今天所拥有的只是引用计数。引用计数可以被认为是一个非常简单的GC，也就是标准库提供的 Rc / Arc。
于很多场景来说，引用计数的数据吞吐量要远小于垃圾回收，如果你设法构建循环引用，它就会完全崩溃。但就目前而言，我们永远不会遇到循环，因此暂时不用担心这个问题。另外，使用Rc意味着我们的数据将无法被改变，因为它不具备内部可变性。
那么我们的布局会是什么样子呢？之前我们有：
1 2 3 4 5 6 7 8 9 10 pub struct List <T> { head: Link<T>, } type Link <T> = Option <Box <Node<T>>>;struct Node <T> { elem: T, next: Link<T>, }
把Box替换为Rc，注意需要将 Rc<T> 引入作用域，因为它不在prelude中：
1 2 3 4 5 6 7 8 9 10 11 12 use std::rc::Rc;pub struct List <T> { head: Link<T>, } type Link <T> = Option <Rc<Node<T>>>;struct Node <T> { elem: T, next: Link<T>, }
3.2 基本操作 新建链表 对于构造函数，我们可以再次复制粘贴：
1 2 3 4 5 impl <T> List<T> { pub fn new () -> Self { List { head: None } } }
prepend和tail 之前的 push 和 pop 已无任何意义，因为新链表是不可变的，但我们可以使用功能相似的 prepend 和 tail 来返回新的链表。
首先是prepend，与可变链表的情况类似，我们想要创建一个新节点，将旧链表作为其 next 值。唯一新颖的是如何获得下一个值，因为我们不允许改变任何东西。
答案就是Clonetrait，Rc特别使用Clone作为增加引用计数的方式，因此我们只需要克隆旧链表的头部节点即可，并且甚至不需要先匹配出内部的 Rc<Node<T>>，然后克隆，由于 Option 也提供了相应的克隆API，只需要在Option上操作即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 impl <T> List<T> { pub fn new () -> Self { List { head: None } } pub fn prepend (&self , elem: T) -> List<T> { List { head: Some (Rc::new (Node { elem: elem, next: self .head.clone (), })), } } }
继续来实现 tail，该方法会将现有链表的首个元素移除，并返回剩余的链表：
1 2 3 pub fn tail (&self ) -> List<T> { List { head: self .head.as_ref ().map (|node| node.next.clone ()) } }
1 2 3 4 5 6 7 8 error[E0308]: mismatched types --> src\third.rs:28:22 | 28 | List { head: self.head.as_ref().map(|node| node.next.clone()) } | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `Rc`, found enum `Option` | = note: expected enum `Option<Rc<_>>` found enum `Option<Option<Rc<_>>>`
map 期望我们返回Y，但这里我们返回 Option<Y> 。值得庆幸的是，这是另一种常见的选项模式，我们可以使用 and_then 来返回一个选项：
1 2 3 4 5 pub fn tail (&self ) -> List<T> { List { head: self .head.as_ref ().and_then (|node| node.next.clone ()), } }
在这里可以查看详细的and_then文档
实现head 现在我们有了 tail ，还应该提供 head ，它返回对第一个元素的引用。这只是可变列表中的 peek ：
1 2 3 pub fn head (&self ) -> Option <&T> { self .head.as_ref ().map (|node| &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 #[cfg(test)] mod test { use super::List; #[test] fn basics () { let list = List::new (); assert_eq! (list.head (), None ); let list = list.prepend (1 ).prepend (2 ).prepend (3 ); assert_eq! (list.head (), Some (&3 )); let list = list.tail (); assert_eq! (list.head (), Some (&2 )); let list = list.tail (); assert_eq! (list.head (), Some (&1 )); let list = list.tail (); assert_eq! (list.head (), None ); let list = list.tail (); assert_eq! (list.head (), None ); } }
1 2 3 4 5 6 7 8 cargo test third Finished test [unoptimized + debuginfo] target(s) in 0.00s Running unittests src\lib.rs (target\debug\deps\liststudy-91fb811e99388d6d.exe) running 1 test test third::test::basics ... ok test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 8 filtered out; finished in 0.00s
Perfect！
迭代器 Iter也与我们的可变列表实现相同：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 pub struct Iter <'a , T> { next: Option <&'a Node<T>>, } impl <T> List<T> { pub fn iter (&self ) -> Iter<'_ , T> { Iter { next: self .head.as_deref () } } } impl <'a , T> Iterator for Iter <'a , T> { type Item = &'a T; fn next (&mut self ) -> Option <Self ::Item> { self .next.map (|node| { self .next = node.next.as_deref (); &node.elem }) } }
请注意，我们无法为此类型实现IntoIter或IterMut。我们只能共享对元素的访问，不能获取可变引用或所有权。
3.3 实现Drop 与可变链表一样，这里也有递归析构函数问题。
之前我们是这样解决的：
1 2 3 4 5 6 7 8 impl <T> Drop for List <T> { fn drop (&mut self ) { let mut cur_link = self .head.take (); while let Some (mut boxed_node) = cur_link { cur_link = boxed_node.next.take (); } } }
问题在于循环体：
1 cur_link = boxed_node.next.take ();
这里不再适用了，因为我们没办法去修改 Rc 持有的值。
但是如果当前的节点仅被当前链表所引用（引用计数为 1），那么实际上是可以将该节点移出并 drop 的。Rc有一个方法可以做到这一点： try_unwrap ：
1 2 3 4 5 6 7 8 9 10 11 12 impl <T> Drop for List <T> { fn drop (&mut self ) { let mut head = self .head.take (); while let Some (node) = head { if let Ok (mut node) = Rc::try_unwrap (node) { head = node.next.take (); } else { break ; } } } }
该方法会判断当前的 Rc 是否只有一个强引用，若是，则返回 Rc 持有的值，否则返回一个错误。
我们会一直 drop ，直到某个节点的引用计数大于1。
1 2 3 4 5 6 7 list1 -> A ---+ | v list2 ------> B -> C -> D ^ | list3 -> X ---+
例如要 drop List2，那会从头节点开始一直 drop 到 B 节点时停止，剩余的 B -> C -> D 三个节点由于引用计数不为 1 (同时被多个链表引用) ，因此不会被 drop。
完美！
3.4 最终代码 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 101 102 103 104 use std::rc::Rc;pub struct List <T> { head: Link<T>, } type Link <T> = Option <Rc<Node<T>>>;struct Node <T> { elem: T, next: Link<T>, } impl <T> List<T> { pub fn new () -> Self { List { head: None } } pub fn prepend (&self , elem: T) -> List<T> { List { head: Some (Rc::new (Node { elem: elem, next: self .head.clone (), }))} } pub fn tail (&self ) -> List<T> { List { head: self .head.as_ref ().and_then (|node| node.next.clone ()) } } pub fn head (&self ) -> Option <&T> { self .head.as_ref ().map (|node| &node.elem) } pub fn iter (&self ) -> Iter<'_ , T> { Iter { next: self .head.as_deref () } } } impl <T> Drop for List <T> { fn drop (&mut self ) { let mut head = self .head.take (); while let Some (node) = head { if let Ok (mut node) = Rc::try_unwrap (node) { head = node.next.take (); } else { break ; } } } } pub struct Iter <'a , T> { next: Option <&'a Node<T>>, } impl <'a , T> Iterator for Iter <'a , T> { type Item = &'a T; fn next (&mut self ) -> Option <Self ::Item> { self .next.map (|node| { self .next = node.next.as_deref (); &node.elem }) } } #[cfg(test)] mod test { use super::List; #[test] fn basics () { let list = List::new (); assert_eq! (list.head (), None ); let list = list.prepend (1 ).prepend (2 ).prepend (3 ); assert_eq! (list.head (), Some (&3 )); let list = list.tail (); assert_eq! (list.head (), Some (&2 )); let list = list.tail (); assert_eq! (list.head (), Some (&1 )); let list = list.tail (); assert_eq! (list.head (), None ); let list = list.tail (); assert_eq! (list.head (), None ); } #[test] fn iter () { let list = List::new ().prepend (1 ).prepend (2 ).prepend (3 ); let mut iter = list.iter (); assert_eq! (iter.next (), Some (&3 )); assert_eq! (iter.next (), Some (&2 )); assert_eq! (iter.next (), Some (&1 )); } }
4 一个糟糕但安全的双端队列 使用Rc和RefCell可以实现内部可变性，因此也许我们可以完全安全地实现双向链表。
让我们添加一个名为 fourth.rs 的新文件：
1 2 3 4 5 6 pub mod first;pub mod second;pub mod third;pub mod fourth;
不需要复制之前的代码，我们从零开始编写。不过，在开始之前，你需要先复习一下内部可变性模式和RefCell<T> ，这很重要，我们设计的关键就是它。
4.1 数据布局 我们想要双向链表。这意味着每个节点都有一个指向前一个和下一个节点的指针。此外，链表本身有一个指向第一个和最后一个节点的指针，这使我们能够在链表的两端快速插入和删除。
所以我们可能想要这样的东西：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 use std::rc::Rc;use std::cell::RefCell;pub struct List <T> { head: Link<T>, tail: Link<T>, } type Link <T> = Option <Rc<RefCell<Node<T>>>>;struct Node <T> { elem: T, next: Link<T>, prev: Link<T>, }
编译一下，可以通过。让我们尝试使用它。
4.2 基本操作 构建new 从构建列表开始，这非常简单。 不过，因为写在一起使它变得有点笨拙，这里分解出一个Node构造函数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 impl <T> Node<T> { fn new (elem: T) -> Rc<RefCell<Self >> { Rc::new (RefCell::new (Node { elem: elem, prev: None , next: None , })) } } impl <T> List<T> { pub fn new () -> Self { List { head: None , tail: None } } }
push_front 再来实现向链表的头部推入一个元素的功能，由于双向链表的数据结构和操作逻辑明显更加复杂，因此相比单向链表的单行实现，双向链表的 push 操作也要复杂的多。
除此之外，我们还需要处理一些关于空链表的边界问题：对于绝大部分操作而言，可能只需要使用 head 或 tail 指针，但是对于空链表，则需要同时使用它们。
我们验证我们的方法是否有意义的一个简单方法是，我们是否保持以下不变量：每个节点应该有两个指向它的指针。链表中间的每个节点由其前任和后继节点指向，而左右两端的节点由链表本身指向。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 pub fn push_front (&mut self , elem: T) { let new_head = Node::new (elem); match self .head.take () { Some (old_head) => { old_head.borrow_mut ().prev = Some (new_head.clone ()); new_head.borrow_mut ().next = Some (old_head); self .head = Some (new_head); } None => { self .tail = Some (new_head.clone ()); self .head = Some (new_head); } } }
编译…通过。非常好。
pop_front pop_front 应该与 push_front 具有相同的基本逻辑，但操作相反。试试吧：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 pub fn pop_front (&mut self ) -> Option <T> { self .head.take ().map (|old_head| { match old_head.borrow_mut ().next.take () { Some (new_head) => { new_head.borrow_mut ().prev.take (); self .head = Some (new_head); } None => { self .tail.take (); } } old_head.elem }) }
1 2 3 4 5 6 7 cargo build error[E0609]: no field `elem` on type `Rc<RefCell<fourth::Node<T>>>` --> src\fourth.rs:62:22 | 62 | old_head.elem | ^^^^ unknown field
这里还是需要borrow_mut ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 pub fn pop_front (&mut self ) -> Option <T> { self .head.take ().map (|old_head| { match old_head.borrow_mut ().next.take () { Some (new_head) => { new_head.borrow_mut ().prev.take (); self .head = Some (new_head); } None => { self .tail.take (); } } old_head.borrow_mut ().elem }) }
1 2 3 4 5 error[E0507]: cannot move out of dereference of `RefMut<'_, fourth::Node<T>>` --> src\fourth.rs:60:13 | 60 | old_head.borrow_mut().elem | ^^^^^^^^^^^^^^^^^^^^^^^^^^ move occurs because value has type `T`, which does not implement the `Copy` trait
borrow_mut 只能返回一个 &mut Node<T>，因此无法拿走其所有权。我们需要一个方法来拿走 RefCell<T> 的所有权，然后返回一个 T，让我们检查一下文档 中是否有类似的内容：
1 2 pub fn into_inner (self ) -> T
看起来很有希望，
1 old_head.into_inner ().elem
1 2 3 4 5 6 7 8 error[E0507]: cannot move out of an `Rc` --> src\fourth.rs:60:13 | 60 | old_head.into_inner().elem | ^^^^^^^^^------------ | | | | | value moved due to this method call | move occurs because value has type `RefCell<fourth::Node<T>>`, which does not implement the `Copy` trait
噢不，into_inner 想要移出RefCell，但因为它位于 Rc 中，Rc<T> 只允许我们获取其内部的不可变引用。
回忆我们之前实现 Drop 时用过的方法，Rc::try_unwrap ，如果Rc的引用计数为 1，则移出Rc的内容：
1 Rc::try_unwrap (old_head).unwrap ().into_inner ().elem
Rc::try_unwrap 返回一个 Result，由于我们不关心 Err 的情况（如果我们正确编写了程序，它不会错误），所以我们只需对其调用 unwrap 。
1 2 3 4 5 6 7 error[E0277]: `fourth::Node<T>` doesn't implement `Debug` --> src\fourth.rs:60:13 | 60 | Rc::try_unwrap(old_head).unwrap().into_inner().elem | ^^^^^^^^^^^^^^^^^^^^^^^^ ------ required by a bound introduced by this call | | | `fourth::Node<T>` cannot be formatted using `{:?}`
unwrap 要求目标类型实现了 Debug ，这样才能在报错时提供 debug 输出，而 RefCell<T> 要实现 Debug 需要它内部的 T 实现 Debug，而我们的 Node 并没有实现。我们这里不为Node实现，而是通过将结果转换为带有 ok 的选项来解决这个问题：
1 Rc::try_unwrap (old_head).ok ().unwrap ().into_inner ().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 33 #[cfg(test)] mod test { use super::List; #[test] fn basics () { let mut list = List::new (); assert_eq! (list.pop_front (), None ); list.push_front (1 ); list.push_front (2 ); list.push_front (3 ); assert_eq! (list.pop_front (), Some (3 )); assert_eq! (list.pop_front (), Some (2 )); list.push_front (4 ); list.push_front (5 ); assert_eq! (list.pop_front (), Some (5 )); assert_eq! (list.pop_front (), Some (4 )); assert_eq! (list.pop_front (), Some (1 )); assert_eq! (list.pop_front (), None ); } }
1 2 3 4 running 1 test test fourth::test::basics ... ok test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 9 filtered out; finished in 0.00s
搞定了。
实现Drop 以前我们费心为堆栈实现Drop只是为了避免无限递归，这次更有趣一些，Rc 无法处理引用循环，而双向链表恰恰如此。双向链表只是一个由小循环组成的大链！因此，当我们删除列表时，两个端节点的引用计数将减少到 1……然后不会发生其他任何事情。好吧，如果我们的列表恰好包含一个节点，那么引用循环就一直存在。
所以，这里最好的实现就是将每个节点 pop 出去，直到获得 None:
1 2 3 4 5 impl <T> Drop for List <T> { fn drop (&mut self ) { while self .pop_front ().is_some () {} } }
这里可以考虑实现 push 和 pop 的 _back 版本，但它们跟之前的实现差别不大，因此会在后面直接给出。现在让我们看看更多有趣的事情。
4.3 实现peek 接下来试试实现 peek_front，这在之前很容易，现在也应该…吧？于是直接复制粘贴之前的实现：
1 2 3 4 5 pub fn peek_front (&self ) -> Option <&T> { self .head.as_ref ().map (|node| { &node.elem }) }
等等，有了之前的教训，这里要用borrow：
1 2 3 4 5 6 pub fn peek_front (&self ) -> Option <&T> { self .head.as_ref ().map (|node| { &node.borrow ().elem }) }
1 2 3 4 5 6 7 8 error[E0515]: cannot return value referencing temporary value --> src\fourth.rs:67:13 | 67 | &node.borrow().elem | ^-------------^^^^^ | || | |temporary value created here | returns a value referencing data owned by the current function
好吧，这与我们的单链表的逻辑完全相同。为什么不一样了？要理解这一点，我们需要回到 borrow 的函数签名：
1 2 fn borrow <'a >(&'a self ) -> Ref<'a , T>fn borrow_mut <'a >(&'a self ) -> RefMut<'a , T>
这里返回的并不是 &T 或 &mut T，而是一个 RefRefMut&T 和 &mut T 完全相同。但正是由于这一层，返回的引用与Ref的生命周期相关，也就是 Ref 和内部引用的生命周期不再和 RefCell 相同，这意味着如果保留引用，那么Ref就必须有效，但显然，它在作用域末尾就失效了，这就是错误的原因所在。
这实际上是正确性所必需的。当Ref被丢弃时，它会告诉RefCell它不再被借用。因此，如果我们确实使得保留引用的时间比Ref存在的时间长，我们就可以在这个引用存在的同时，获取到RefMut——这意味着会把rust的引用系统的规则完全破坏。
那该怎么办呢，我们只想返回一个引用，但需要保留这个Ref的东西。而一旦我们从 peek 返回引用，函数就会结束，并且 Ref 就会超出作用范围被drop。
目前来看，已经是死路了。但是…如果我们放弃完全隐藏我们的实现细节呢，比如返回Refs会怎样？
1 2 3 4 5 6 7 use std::cell::{Ref, RefCell}; pub fn peek_front (&self ) -> Option <Ref<T>> { self .head.as_ref ().map (|node| { node.borrow () }) }
1 2 3 4 5 6 7 8 9 10 11 12 error[E0308]: mismatched types --> src\fourth.rs:64:9 | 26 | impl<T> List<T> { | - this type parameter ... 63 | pub fn peek_front(&self) -> Option<Ref<T>> { | -------------- expected `Option<Ref<'_, T>>` because of return type 64 | / self.head.as_ref().map(|node| { 65 | | node.borrow() 66 | | }) | |__________^ expected type parameter `T`, found struct `fourth::Node`
类型不匹配了，要返回的是 Ref<T> 但是获取的却是 Ref<Node<T>>，那么现在看上去有两个选择：1，放弃所有封装并重新开始。2，使事情变得更加复杂，并将 Ref<Node<T>> 包装在新类型中，以仅公开对 &T 的访问。
但是两个选择都不是我们想要的，继续研究下去，发现了这个：
1 2 3 map<U, F>(orig: Ref<'b , T>, f: F) -> Ref<'b , U> where F: FnOnce (&T) -> &U, U: ?Sized
没错，就像在 Result 和 Option 上使用 map 一样，我们还能在 Ref 上使用 map，这太好了，我们正需要它：
1 2 3 4 5 pub fn peek_front (&self ) -> Option <Ref<T>> { self .head.as_ref ().map (|node| { Ref::map (node.borrow (), |node| &node.elem) }) }
cargo build，终于通过了。编写一个测试吧：
1 2 3 4 5 6 7 8 9 10 #[test] fn peek () { let mut list = List::new (); assert! (list.peek_front ().is_none ()); list.push_front (1 ); list.push_front (2 ); list.push_front (3 ); assert_eq! (&*list.peek_front ().unwrap (), &3 ); }
1 2 3 4 5 running 2 tests test fourth::test::peek ... ok test fourth::test::basics ... ok test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 9 filtered out; finished in 0.00s
很好。
4.4 镜像实现 之前我们仅实现了头部的 push、pop ，现在来补全一下从back操作。所要做的就是一些基本的文本替换：
1 2 3 tail <-> head next <-> prev front -> back
还需要添加 _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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 use std::cell::{Ref, RefCell, RefMut};pub fn push_back (&mut self , elem: T) { let new_tail = Node::new (elem); match self .tail.take () { Some (old_tail) => { old_tail.borrow_mut ().next = Some (new_tail.clone ()); new_tail.borrow_mut ().prev = Some (old_tail); self .tail = Some (new_tail); } None => { self .head = Some (new_tail.clone ()); self .tail = Some (new_tail); } } } pub fn pop_back (&mut self ) -> Option <T> { self .tail.take ().map (|old_tail| { match old_tail.borrow_mut ().prev.take () { Some (new_tail) => { new_tail.borrow_mut ().next.take (); self .tail = Some (new_tail); } None => { self .head.take (); } } Rc::try_unwrap (old_tail).ok ().unwrap ().into_inner ().elem }) } pub fn peek_back (&self ) -> Option <Ref<T>> { self .tail.as_ref ().map (|node| { Ref::map (node.borrow (), |node| &node.elem) }) } pub fn peek_back_mut (&mut self ) -> Option <RefMut<T>> { self .tail.as_ref ().map (|node| { RefMut::map (node.borrow_mut (), |node| &mut node.elem) }) } pub fn peek_front_mut (&mut self ) -> Option <RefMut<T>> { self .head.as_ref ().map (|node| { RefMut::map (node.borrow_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 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 #[test] fn basics () { let mut list = List::new (); assert_eq! (list.pop_front (), None ); list.push_front (1 ); list.push_front (2 ); list.push_front (3 ); assert_eq! (list.pop_front (), Some (3 )); assert_eq! (list.pop_front (), Some (2 )); list.push_front (4 ); list.push_front (5 ); assert_eq! (list.pop_front (), Some (5 )); assert_eq! (list.pop_front (), Some (4 )); assert_eq! (list.pop_front (), Some (1 )); assert_eq! (list.pop_front (), None ); assert_eq! (list.pop_back (), None ); list.push_back (1 ); list.push_back (2 ); list.push_back (3 ); assert_eq! (list.pop_back (), Some (3 )); assert_eq! (list.pop_back (), Some (2 )); list.push_back (4 ); list.push_back (5 ); assert_eq! (list.pop_back (), Some (5 )); assert_eq! (list.pop_back (), Some (4 )); assert_eq! (list.pop_back (), Some (1 )); assert_eq! (list.pop_back (), None ); } #[test] fn peek () { let mut list = List::new (); assert! (list.peek_front ().is_none ()); assert! (list.peek_back ().is_none ()); assert! (list.peek_front_mut ().is_none ()); assert! (list.peek_back_mut ().is_none ()); list.push_front (1 ); list.push_front (2 ); list.push_front (3 ); assert_eq! (&*list.peek_front ().unwrap (), &3 ); assert_eq! (&mut *list.peek_front_mut ().unwrap (), &mut 3 ); assert_eq! (&*list.peek_back ().unwrap (), &1 ); assert_eq! (&mut *list.peek_back_mut ().unwrap (), &mut 1 ); }
是否有一些情况我们没有测试？是的。排列组合数量爆炸了。但是我们的代码至少没有明显错误。
1 2 3 4 5 running 2 tests test fourth::test::basics ... ok test fourth::test::peek ... ok test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 9 filtered out; finished in 0.00s
4.5 迭代器 下面，让我们尝试一下为它实现迭代器。
实现IntoIter 一如既往，IntoIter是最简单的 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 pub struct IntoIter <T>(List<T>);impl <T> List<T> { pub fn into_iter (self ) -> IntoIter<T> { IntoIter (self ) } } impl <T> Iterator for IntoIter <T> { type Item = T; fn next (&mut self ) -> Option <Self ::Item> { self .0 .pop_front () } }
这里要考虑一个事情，以前我们的实现都是单向的，但现在我们实际可以是双向的。rust实际上对此有一个答案：DoubleEndedIterator ，它“继承”自Iterator，二者都是迭代器，参考官方文档 ：
1 2 3 4 5 6 7 pub trait DoubleEndedIterator : Iterator { fn next_back (&mut self ) -> Option <Self ::Item>; }
这里用到了Supertraits ，因此意味着要实现该特征，首先需要实现 Iterator。并且提供了从另一端迭代的新方法： next_back 。它具有与 next 完全相同的签名，但它从另一端产生元素。需要注意的是，前后迭代工作都在同一范围内进行，并且不会交叉：当它们在中间相遇时，迭代就结束了。
不过，事实证明 next_back 并不是 DoubleEndedIterator 的使用者真正关心的东西。相反，该接口最好的部分是它公开了 rev 方法，该方法包装迭代器以创建一个以相反顺序生成元素的新迭代器。其语义相当简单：对反向迭代器上的 next 的调用只是对 next_back 的调用。
无论如何，我们先来实现一下它吧，非常简单。
1 2 3 4 5 impl <T> DoubleEndedIterator for IntoIter <T> { fn next_back (&mut self ) -> Option <T> { self .0 .pop_back () } }
测试：
1 2 3 4 5 6 7 8 9 10 11 12 #[test] fn into_iter () { let mut list = List::new (); list.push_front (1 ); list.push_front (2 ); list.push_front (3 ); let mut iter = list.into_iter (); assert_eq! (iter.next (), Some (3 )); assert_eq! (iter.next_back (), Some (1 )); assert_eq! (iter.next (), Some (2 )); assert_eq! (iter.next_back (), None ); assert_eq! (iter.next (), None ); }
实现Iter Iter就比较麻烦了，我们将不得不再次处理那些可怕的 Ref。无法像以前那样存储 &Node 。相反，让我们尝试存储 Ref<Node> ：
1 2 3 4 5 6 7 pub struct Iter <'a , T>(Option <Ref<'a , Node<T>>>);impl <T> List<T> { pub fn iter (&self ) -> Iter<T> { Iter (self .head.as_ref ().map (|head| head.borrow ())) } }
到目前为止都没有问题。接下来实现 next ：
1 2 3 4 5 6 7 8 9 impl <'a , T> Iterator for Iter <'a , T> { type Item = Ref<'a , T>; fn next (&mut self ) -> Option <Self ::Item> { self .0 .take ().map (|node_ref| { self .0 = node_ref.next.as_ref ().map (|head| head.borrow ()); Ref::map (node_ref, |node| &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 error[E0521]: borrowed data escapes outside of closure --> src\fourth.rs:159:13 | 157 | fn next(&mut self) -> Option<Self::Item> { | --------- `self` declared here, outside of the closure body 158 | self.0.take().map(|node_ref| { 159 | self.0 = node_ref.next.as_ref().map(|head| head.borrow()); | ^^^^^^ -------- borrow is only valid in the closure body | | | reference to `node_ref` escapes the closure body here error[E0505]: cannot move out of `node_ref` because it is borrowed --> src\fourth.rs:160:22 | 157 | fn next(&mut self) -> Option<Self::Item> { | --------- lifetime `'1` appears in the type of `self` 158 | self.0.take().map(|node_ref| { 159 | self.0 = node_ref.next.as_ref().map(|head| head.borrow()); | ------ -------- borrow of `node_ref` occurs here | | | assignment requires that `node_ref` is borrowed for `'1` 160 | Ref::map(node_ref, |node| &node.elem) | ^^^^^^^^ move out of `node_ref` occurs here
这里提示我们，node_ref 活得不够久，与普通引用不同，rust不允许我们像这样拆分引用。我们从 head.borrow() 中得到的Ref只允许存在与 node_ref 一样长的时间，但我们最终会在 Ref::map 调用中丢弃它。
我们实际想要的函数也许是这个map_split
1 2 3 4 5 pub fn map_split <U, V, F>(orig: Ref<'b , T>, f: F) -> (Ref<'b , U>, Ref<'b , V>)where F: FnOnce (&T) -> (&U, &V), U: ?Sized , V: ?Sized ,
试一试吧…
1 2 3 4 5 6 7 8 9 10 11 fn next (&mut self ) -> Option <Self ::Item> { self .0 .take ().map (|node_ref| { let (next, elem) = Ref::map_split (node_ref, |node| { (&node.next, &node.elem) }); self .0 = next.as_ref ().map (|head| head.borrow ()); elem }) }
1 2 3 4 5 6 7 8 9 10 error[E0521]: borrowed data escapes outside of closure --> src\fourth.rs:163:13 | 157 | fn next(&mut self) -> Option<Self::Item> { | --------- `self` declared here, outside of the closure body ... 163 | self.0 = next.as_ref().map(|head| head.borrow()); | ^^^^^^ ------------- borrow is only valid in the closure body | | | reference to `next` escapes the closure body here
借用的内容只允许在闭包体中使用，看起来我们还是得用 Ref::map 来解决问题：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 fn next (&mut self ) -> Option <Self ::Item> { self .0 .take ().map (|node_ref| { let (next, elem) = Ref::map_split (node_ref, |node| { (&node.next, &node.elem) }); self .0 = if next.is_some () { Some (Ref::map (next, |next| &**next.as_ref ().unwrap ())) } else { None }; elem }) }
1 2 3 4 5 6 7 error[E0308]: mismatched types --> src\fourth.rs:164:22 | 164 | Some(Ref::map(next, |next| &**next.as_ref().unwrap())) | ---- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `fourth::Node`, found struct `RefCell` | | | arguments to this enum variant are incorrect
多了一个 RefCell ，随着我们的对链表的逐步深入，RefCell 的代码嵌套变成了不可忽视的问题。这是一个死胡同，让我们尝试离开 RefCells。
Rc 怎么样？为什么我们不能克隆整个Rc呢？
1 2 3 4 5 6 7 8 9 10 pub struct Iter <T>(Option <Rc<Node<T>>>);impl <T> List<T> { pub fn iter (&self ) -> Iter<T> { Iter (self .head.as_ref ().map (|head| head.clone ())) } } impl <T> Iterator for Iter <T> { type Item =
呃…等等，现在应该返回什么？ &T ？ Ref<T> ？现在我们的 Iter 已经没有生命周期了：无论是 &T 还是 Ref<T> 都需要我们在 next 之前声明好生命周期。但是我们试图从 Rc 中取出来的值其实是迭代器的引用。
也可以通过对 Rc 进行 map 获取到 Rc<T>？但是标准库并没有给我们提供相应的功能，实际上有人做了一个三方库 可以让你做到这一点。
但是，即使这么做了，我们也会遇到一个更大的问题：可怕的迭代器失效幽灵。事实上，之前我们对于迭代器不合法是免疫的，但是一旦迭代器产生 Rc，那它们就不再会借用链表。这意味着人们可以在持有指向链表内部的指针时，还可以进行 push 和 pop 操作。push 问题不大，因为链表两端的增长不会对我们正在关注的某个子链表造成影响。但是 pop 就是另一个故事了，如果在我们关注的子链表之外 pop，那问题不大。但是如果是 pop 一个正在引用的子链表中的节点呢？那一切就完了，特别是，如果大家还试图去 unwrap try_unwrap 返回的 Result ，会直接造成整个程序的 panic。
其实我们大部分的努力都是为了实现隐藏的细节和优雅的 API，典型的二八原则，八成时间花在二成的细节上。但是如果不关心这些细节，可以接受自己的平凡的话，那把节点简单的到处传递就行。但Rc<RefCell> 真的最终让我们失望了。
实际上，这种设计更适合永远不会向 API 的使用者展示的内部数据结构。内部可变性非常适合编写安全的应用程序。但是如果是写安全性高的库，那内部可变性就有些捉襟见肘了。无论如何，这就是我们在这里放弃 Iter 和 IterMut 的原因。我们也许可以做到，但是，呃，还是算了。
4.6 最终代码 好的，这就是在rust中实现 100% 安全的双向链表。实现起来是一场噩梦，泄露了实现细节，并且不支持几个基本操作。在实现中，还有大量 Rc 和 RefCell 引起的运行时检查，最终会影响链表的性能。尽管如此，这仍然做到了。特别是如果我们不关心向消费者公开内部数据结构的话。
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 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 use std::rc::Rc;use std::cell::{Ref, RefMut, RefCell};pub struct List <T> { head: Link<T>, tail: Link<T>, } type Link <T> = Option <Rc<RefCell<Node<T>>>>;struct Node <T> { elem: T, next: Link<T>, prev: Link<T>, } impl <T> Node<T> { fn new (elem: T) -> Rc<RefCell<Self >> { Rc::new (RefCell::new (Node { elem: elem, prev: None , next: None , })) } } impl <T> List<T> { pub fn new () -> Self { List { head: None , tail: None } } pub fn push_front (&mut self , elem: T) { let new_head = Node::new (elem); match self .head.take () { Some (old_head) => { old_head.borrow_mut ().prev = Some (new_head.clone ()); new_head.borrow_mut ().next = Some (old_head); self .head = Some (new_head); } None => { self .tail = Some (new_head.clone ()); self .head = Some (new_head); } } } pub fn push_back (&mut self , elem: T) { let new_tail = Node::new (elem); match self .tail.take () { Some (old_tail) => { old_tail.borrow_mut ().next = Some (new_tail.clone ()); new_tail.borrow_mut ().prev = Some (old_tail); self .tail = Some (new_tail); } None => { self .head = Some (new_tail.clone ()); self .tail = Some (new_tail); } } } pub fn pop_back (&mut self ) -> Option <T> { self .tail.take ().map (|old_tail| { match old_tail.borrow_mut ().prev.take () { Some (new_tail) => { new_tail.borrow_mut ().next.take (); self .tail = Some (new_tail); } None => { self .head.take (); } } Rc::try_unwrap (old_tail).ok ().unwrap ().into_inner ().elem }) } pub fn pop_front (&mut self ) -> Option <T> { self .head.take ().map (|old_head| { match old_head.borrow_mut ().next.take () { Some (new_head) => { new_head.borrow_mut ().prev.take (); self .head = Some (new_head); } None => { self .tail.take (); } } Rc::try_unwrap (old_head).ok ().unwrap ().into_inner ().elem }) } pub fn peek_front (&self ) -> Option <Ref<T>> { self .head.as_ref ().map (|node| { Ref::map (node.borrow (), |node| &node.elem) }) } pub fn peek_back (&self ) -> Option <Ref<T>> { self .tail.as_ref ().map (|node| { Ref::map (node.borrow (), |node| &node.elem) }) } pub fn peek_back_mut (&mut self ) -> Option <RefMut<T>> { self .tail.as_ref ().map (|node| { RefMut::map (node.borrow_mut (), |node| &mut node.elem) }) } pub fn peek_front_mut (&mut self ) -> Option <RefMut<T>> { self .head.as_ref ().map (|node| { RefMut::map (node.borrow_mut (), |node| &mut node.elem) }) } pub fn into_iter (self ) -> IntoIter<T> { IntoIter (self ) } } impl <T> Drop for List <T> { fn drop (&mut self ) { while self .pop_front ().is_some () {} } } pub struct IntoIter <T>(List<T>);impl <T> Iterator for IntoIter <T> { type Item = T; fn next (&mut self ) -> Option <T> { self .0 .pop_front () } } impl <T> DoubleEndedIterator for IntoIter <T> { fn next_back (&mut self ) -> Option <T> { self .0 .pop_back () } } #[cfg(test)] mod test { use super::List; #[test] fn basics () { let mut list = List::new (); assert_eq! (list.pop_front (), None ); list.push_front (1 ); list.push_front (2 ); list.push_front (3 ); assert_eq! (list.pop_front (), Some (3 )); assert_eq! (list.pop_front (), Some (2 )); list.push_front (4 ); list.push_front (5 ); assert_eq! (list.pop_front (), Some (5 )); assert_eq! (list.pop_front (), Some (4 )); assert_eq! (list.pop_front (), Some (1 )); assert_eq! (list.pop_front (), None ); assert_eq! (list.pop_back (), None ); list.push_back (1 ); list.push_back (2 ); list.push_back (3 ); assert_eq! (list.pop_back (), Some (3 )); assert_eq! (list.pop_back (), Some (2 )); list.push_back (4 ); list.push_back (5 ); assert_eq! (list.pop_back (), Some (5 )); assert_eq! (list.pop_back (), Some (4 )); assert_eq! (list.pop_back (), Some (1 )); assert_eq! (list.pop_back (), None ); } #[test] fn peek () { let mut list = List::new (); assert! (list.peek_front ().is_none ()); assert! (list.peek_back ().is_none ()); assert! (list.peek_front_mut ().is_none ()); assert! (list.peek_back_mut ().is_none ()); list.push_front (1 ); list.push_front (2 ); list.push_front (3 ); assert_eq! (&*list.peek_front ().unwrap (), &3 ); assert_eq! (&mut *list.peek_front_mut ().unwrap (), &mut 3 ); assert_eq! (&*list.peek_back ().unwrap (), &1 ); assert_eq! (&mut *list.peek_back_mut ().unwrap (), &mut 1 ); } #[test] fn into_iter () { let mut list = List::new (); list.push_front (1 ); list.push_front (2 ); list.push_front (3 ); let mut iter = list.into_iter (); assert_eq! (iter.next (), Some (3 )); assert_eq! (iter.next_back (), Some (1 )); assert_eq! (iter.next (), Some (2 )); assert_eq! (iter.next_back (), None ); assert_eq! (iter.next (), None ); } }
现在，我们将关注硬币的另一面：通过使我们的实现变得不安全来夺回所有控制权。
5 一个很棒但不安全的队列 通过内部可变性实现的链表有点失控了，Rc和Refcell非常适合处理简单的情况，但它们可能会变得笨拙。这次，我们使用裸指针，通过unsafe的方式实现一个单向的队列。
让我们添加一个名为 fifth.rs 的新文件：
1 2 3 4 5 6 7 pub mod first;pub mod second;pub mod third;pub mod fourth;pub mod fifth;
fifth.rs 的代码会跟 second.rs 存在一定的重叠，尽管如此，我们仍将从头开始，因为我们想要解决一些布局等基本问题。
5.1 数据布局 栈和队列之间的唯一区别是队列从另一端弹出。因此，栈实现是这样的：
1 2 3 4 5 6 7 8 input list: [Some(ptr)] -> (A, Some(ptr)) -> (B, None) stack push X: [Some(ptr)] -> (X, Some(ptr)) -> (A, Some(ptr)) -> (B, None) stack pop: [Some(ptr)] -> (A, Some(ptr)) -> (B, None)
要变成队列，只需要将pop或者push其中任意一个操作改到另一端，到底选择哪个？由于我们的链表是单链，因此这两种所做的操作是完全相同的，如果选择push：
1 2 3 4 5 input list: [Some(ptr)] -> (A, Some(ptr)) -> (B, None) flipped push X: [Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)
要将X入队，只需要从A开始一直走到末尾（None处）再将其设置为带有新元素的 Some 即可。
如果选择pop：
1 2 3 4 5 input list: [Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None) flipped pop: [Some(ptr)] -> (A, Some(ptr)) -> (B, None)
要出队，只需要从A开始一直走到末尾（None处）之前的节点，然后 take 它。
无论选择哪种改变，都会发现，这两个操作都会遍历整个列表，当元素很多时，入队或出队的性能会大幅下降。
能否设计一个入队和出队都是O(1)级别的数据结构呢？当然可以，问题的关键就是如何避免在整个链表上遍历，以反转push操作为例，如果我们有一个额外的指针指向整个链表的尾部，那么就可以直接插入了。
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, next: None , }); let old_tail = mem::replace (&mut self .tail, Some (new_tail)); match old_tail { Some (mut old_tail) => { old_tail.next = Some (new_tail); } None => { self .head = Some (new_tail); } } } }
1 2 3 4 5 6 7 8 9 10 11 error[E0382]: use of moved value: `new_tail` --> src\fifth.rs:33:38 | 21 | let new_tail = Box::new(Node { | -------- move occurs because `new_tail` has type `Box<fifth::Node<T>>`, which does not implement the `Copy` trait ... 28 | let old_tail = mem::replace(&mut self.tail, Some(new_tail)); | -------- value moved here ... 33 | old_tail.next = Some(new_tail); | ^^^^^^^^ value used here after move
Box 并没有实现 Copy 特征，因此我们不能在两个地方进行赋值。使用没有所有权的引用类型试试：
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 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, next: None , }); let new_tail = match self .tail.take () { Some (old_tail) => { old_tail.next = Some (new_tail); old_tail.next.as_deref_mut () } None => { self .head = Some (new_tail); self .head.as_deref_mut () } }; self .tail = new_tail; } }
1 2 3 4 5 error[E0106]: missing lifetime specifier --> src\fifth.rs:5:18 | 5 | tail: Option<&mut Node<T>>, // NEW! | ^ expected named 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 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, next: None , }); let new_tail = match self .tail.take () { Some (old_tail) => { old_tail.next = Some (new_tail); old_tail.next.as_deref_mut () } None => { 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 error: lifetime may not live long enough --> src\fifth.rs:33:17 | 15 | impl<'a, T> List<'a, T> { | -- lifetime `'a` defined here ... 20 | pub fn push(&mut self, elem: T) { | - let's call the lifetime of this reference `'1` ... 33 | self.head.as_deref_mut() | ^^^^^^^^^^^^^^^^^^^^^^^^ assignment requires that `'1` must outlive `'a`
强大的编译器提示，我们借用了 self ，但编译器希望它至少能持续与 'a 一样长的时间，如果我们告诉它 self 确实持续了那么久：
1 pub fn push (&'a mut self , elem: T) {
再次编译，成功了。
再来实现下 pop:
1 2 3 4 5 6 7 8 9 10 11 12 pub fn pop (&'a mut self ) -> Option <T> { self .head.take ().map (|head| { let head = *head; self .head = head.next; 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 .... ** WAY MORE LINES OF ERRORS ** .... error: aborting due to 11 previous errors
天啊，这是为什么？但编译器真的没错，因为都是我们刚才那个标记惹的祸。我们为 self 标记了 'a，意味着在 'a 结束前，无法再去使用 self，而self的生命周期…好吧，它是整个程序，也就是说我们可以调用一次push或者pop，而之后，我们创建的链表的荒谬性就会产生影响，一切都会被锁定住，无法再次调用。事实上，我们正是创建了一个之前提到过的自引用与循环引用 。
我们的 pop 实现暗示了为什么在我们自己内部存储对我们自己的引用可能非常危险：
1 2 3 4 if self .head.is_none () { self .tail = None ; }
如果我们忘记这样做怎么办？然后我们的尾部将指向已从列表中删除的某个节点。这样的节点会立即被释放，我们就会有一个悬空指针，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>, }
5.2 基本操作 在开始之前，你可以先复习一下不安全的rust ，然后让我们进入unsafe rust的世界。
构建new 在之前我们是这么做的：
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 error[E0308]: mismatched types --> src\fifth.rs:17:34 | 17 | List { head: None, tail: None } | ^^^^ expected raw pointer, found enum `Option`
我们当然可以为裸指针也包裹一个Option，但是裸指针之所以成为裸指针，就是因为*mut 可以为空。它无法从空指针优化中受益。相反，我们将使用 null 来表示None。
rust提供了nullnull_mutnull，然后，你可以通过 *const T 和 *mut T 的 is_null0 as *mut _ ，但这看起来很混乱。
下面是一个创建空指针的例子：
1 2 3 4 use std::ptr;let p : *mut i32 = ptr::null_mut ();assert! (p.is_null ());
因此，此处new我们这样写：
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 () } } }
push 下面继续编写 push 。我们如何从普通指针创建原始指针？答案是强转：
1 let raw_tail : *mut _ = &mut *new_tail;
尝试实现push：
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; if !self .tail.is_null () { self .tail.next = Some (new_tail); } else { self .head = Some (new_tail); } self .tail = raw_tail; }
1 2 3 4 5 6 7 error[E0609]: no field `next` on type `*mut fifth::Node<T>` --> src\fifth.rs:30:23 | 30 | 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 error[E0133]: dereference of raw pointer is unsafe and requires unsafe function or block --> src\fifth.rs:30:13 | 30 | (*self.tail).next = Some(new_tail); | ^^^^^^^^^^^^^^^^^ dereference of raw pointer
创建裸指针可以在unsafe块外面，但是使用时必须放到unsafe内，我们有两个选择。首先，我们可以将整个函数标记为不安全，在这种情况下，它就成为不安全的 Rust 函数，并且只能在 unsafe 上下文中调用。这不太好，因为我们希望我们的列表可以安全使用。其次，我们可以在函数内编写一个 unsafe 块来界定边界。
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; }
pop 让我们继续看 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 }) }
编写单元测试：
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 ); } }
1 2 3 4 running 1 test test fifth::test::basics ... ok test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 12 filtered out; finished in 0.01s
看起来通过了。
5.3 Miri 上一小节编写的测试似乎没有问题，但是我们现在正在编写 unsafe 代码，因此编译器也无法帮助我们捕获错误。测试可能碰巧有效，但实际上可能无法检测到一些未定义的行为。
Miri 正是用来检测未定义行为的工具，我们先安装它，然后再进行介绍。
1 rustup +nightly-2022-01-21 component add miri
我们正在安装的工具 miri 与 rustc 的内部结构紧密配合，因此它仅适用于rust夜版工具链。
+nightly-2022-01-21 告诉 rustup 我们要在该日期使用 rust nightly 工具链安装 miri。这里给出了一个具体的日期，因为有时 miri 会落后，无法为一些nightly版本而建造。如果我们尚未安装它，rustup 将自动下载我们使用 + 指定的任何工具链。
2022-01-21 是我所知的 miri 可以成功运行的版本，你可以检查这个网址 获取更多信息。如果你幸运的话，可以只使用 +nightly 成功安装。
下面继续运行：
1 2 3 $ cargo +nightly-2022-01-21 miri test I will run `"cargo.exe" "install" "xargo" ` to install a recent enough xargo. Proceed? [Y/n]
选择Y
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 > y Updating crates.io index Installing xargo v0.3.24 ... Finished release [optimized] target(s) in 10.65s Installing C:\Users\ninte\.cargo\bin\xargo-check.exe Installing C:\Users\ninte\.cargo\bin\xargo.exe Installed package `xargo v0.3.24` (executables `xargo-check.exe`, `xargo.exe`) I will run `"rustup" "component" "add" "rust-src" ` to install the `rust-src` component for the selected toolchain. Proceed? [Y/n] > y info: downloading component 'rust-src' info: installing component 'rust-src' Compiling lists v0.1.0 (C:\Users\ninte\dev\tmp\lists) Finished test [unoptimized + debuginfo] target(s) in 0.25s Running unittests (lists-5cc11d9ee5c3e924.exe) error: Undefined Behavior: trying to reborrow for Unique at alloc84055, but parent tag <209678> does not have an appropriate item in the borrow stack --> \lib\rustlib\src\rust\library\core\src\option.rs:846:18 | 846 | Some(x) => Some(f(x)), | ^ trying to reborrow for Unique at alloc84055, | but parent tag <209678> does not have an | appropriate item in the borrow stack | = help : this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental = help : see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information = note: inside `std::option::Option::<std::boxed::Box<fifth::Node<i32>>>::map::<i32, [closure@src\fifth.rs:31:30: 40:10]>` at \lib\rustlib\src\rust\library\core\src\option.rs:846:18 note: inside `fifth::List::<i32>::pop` at src\fifth.rs:31:9 --> src\fifth.rs:31:9 | 31 | / self.head.take().map(|head | { 32 | | let head = *head ; 33 | | self.head = head.next; 34 | | ... | 39 | | head.elem 40 | | }) | |__________^ note: inside `fifth::test ::basics` at src\fifth.rs:74:20 --> src\fifth.rs:74:20 | 74 | assert_eq!(list.pop(), Some(1)); | ^^^^^^^^^^ note: inside closure at src\fifth.rs:62:5 --> src\fifth.rs:62:5 | 61 | | ------- in this procedural macro expansion 62 | / fn basics 63 | | let mut list = List::new(); 64 | | 65 | | // Check empty list behaves right ... | 96 | | assert_eq!(list.pop(), None); 97 | | } | |_____^ ... error: aborting due to previous error
哇。这是一个很大的错误。在解释这个错误之前，先来解释一下miri是什么，简单来说，它是rust的中级中间表示（MIR）的实验解释器。使用它可以解释你的程序并通知你是否在runtime违反规则并执行未定义的行为。这是很有必要的，因为未定义行为通常是在运行时发生的事情。如果可以在编译时发现问题，就可以提前避免在运行时出现这些错误。
下面来看看上面发生的具体错误。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 error: Undefined Behavior: trying to reborrow for Unique at alloc84055, but parent tag <209678> does not have an appropriate item in the borrow stack --> \lib\rustlib\src\rust\library\core\src\option.rs:846:18 | 846 | Some(x) => Some(f(x)), | ^ trying to reborrow for Unique at alloc84055, | but parent tag <209678> does not have an | appropriate item in the borrow stack | = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
我可以看到我们犯了一个错误，但这是一个令人困惑的错误消息。什么是borrow stack？
5.4 借用栈 在上一节中，我们尝试在 miri 下运行我们实现的不安全的队列，它说我们违反了栈借用规则，并为我们链接了一些文档。感兴趣的话，可以浏览这些文档，但是我们并不是该文档的真正目标受众。它更多地是为致力于 Rust 语义的编译器开发人员和语法研究者而设计的。
因此，这里只是介绍“借用栈”的高级概念，然后为你提供遵循规则的简单策略。
在这之前要提出一点，目前栈借用在 Rust 语义模型中还是试验阶段，因此破坏这些规则不一定说明你的程序错了。但是除非你在做编译器开发，否则最好还是修复这些错误。对于未定义的行为，安全总比后悔好。
指针别名（Pointer Aliasing） 别名（Aliasing）指的是可以使用不同名称访问同一内存位置的情况。正如“使用别名”的人可以通过两个不同的名称来引用一样，重叠的内存片段可以通过两个不同的指针来引用。这可能会导致问题。
编译器使用有关指针别名的信息来优化对内存的访问，因此如果它所拥有的信息是错误的，那么程序将被错误编译并产生随机垃圾。
实际上，别名更多关心的是内存访问而不是指针本身，而且只有在其中一个访问是可变的时，才可能出问题。之所以说指针，是因为指针这个概念更方便跟一些规则进行关联。
编译器需要获取一个值时，是该去缓存中查询还是每次都去内存中加载呢？关于这个选择，编译器需要清晰地知道是否有一个指针在背后修改内存，如果内存值被修改了，那缓存显然就失效了。
指针别名在C/C++中也是存在的，比如下面的C程序：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <stdio.h> int gfg (int * a, int * b) { *b = *b + 10 ; return *a; } int main () { int data = 20 ; int result = gfg(&data, &data); printf ("%d " , result); }
这里，我们将data地址同时传递给a和b，它们互相是对方的别名，对指针b引用的内存位置所做的更改也会反映在a中，因此，程序会输出30。
显然，无论是从程序员的角度还是编译器优化的角度，都希望尽可能少出现指针别名，即不同类型的指针永远不会指向相同的内存位置，这在C语言中被称为严格的别名规则，这样的限制有助于编译器优化代码。
安全的借用栈 对于rust来说，它没有C那么狂野，因此编译器一定期望拥有良好的指针别名信息，因为rust就是为此而设计的。对于rust正常代码而言，严格的借用规则是我们的后盾：要么只存在一个可变引用，要么同时存在多个不可变引用。
但事情没这么简单。我们可以像这样“重新借用”可变指针：
1 2 3 4 5 6 7 8 let mut data = 10 ;let ref1 = &mut data;let ref2 = &mut *ref1;*ref2 += 2 ; *ref1 += 1 ; println! ("{}" , data);
编译并运行良好，输出13。但是，如果交换解引用的顺序：
1 2 3 4 5 6 7 8 9 let mut data = 10 ;let ref1 = &mut data;let ref2 = &mut *ref1;*ref1 += 1 ; *ref2 += 2 ; println! ("{}" , data);
1 2 3 4 5 6 7 8 9 10 error[E0503]: cannot use `*ref1` because it was mutably borrowed --> src\main.rs:10:5 | 7 | let ref2 = &mut *ref1; | ---------- borrow of `*ref1` occurs here ... 10 | *ref1 += 1; | ^^^^^^^^^^ use of borrowed `*ref1` 11 | *ref2 += 2; | ---------- borrow later used here
突然编译错误了。当我们再借用了一个可变引用时，那原始的引用（ref1）就不能再被使用，直到借用者（ref1）使用完毕。根据NLL规则，借用者的借用有效范围并不是看作用域，而是看最后一次使用的位置，因此第一个例子中的代码中我们重新借用指针，使用新指针一段时间，然后停止使用它，然后再次使用旧指针，这并不会出现错误，但第二个例子就不行。
要想不产生借用错误，所有重新借用（reborrow）都必须明确嵌套，因此我们在任何给定时间只能考虑其中一个“生效的借用”。什么东西可以表示嵌套的事物呢？栈，没错，一个借用栈。这就是borrow stack名字的由来。
借用栈顶部的任何内容都是“生效的”，并且知道它实际上是未别名的。当你重新借用指针时，新指针将被推入栈顶，成为活动指针。当你使用旧指针时，通过弹出其上方借用栈上的所有内容，才可以继续使用。此时，指针“知道”它已被重新借用，并且内存可能已被修改，但它再次具有独占访问权限，无需担心指针别名的问题。
实际上，访问reborrow的指针总是可以的，因为我们总是可以弹出它上面的所有指针，直到它成为栈顶指针。但是，如果是访问一个已经从借用栈中弹出的指针——那么你就搞砸了。
值得庆幸的是，借用检查器的设计确保了安全的 Rust 程序遵循这些规则，正如我们在上面的示例中看到的那样，但编译器通常从栈借用的角度“向后”看待这个问题。它并没有说使用 ref1 会使 ref2 无效，而是坚持 ref2 必须对其所有用途都有效，并且 ref1 是唯一的不按顺序行事的指针。编译器的报错也是选择了这种表述方式：无法使用 *ref1，原因是它已经被可变借用了，可以看出，这种表述方式更加符合直觉。
这一切都运行良好——在safe rust下。当我们开始使用不安全的指针时，借用检查器就无法帮助我们了。
不安全的借用栈 因此，我们希望以某种方式让不安全指针参与到这个堆借用系统中，即使编译器无法正确跟踪它们。我们还希望系统具有相当的宽容性，这样就不会太容易搞砸并导致未定义行为（UB）。
这是一个难题，从事栈借用的开发人员想出了一些看似合理的东西，并且 miri 尝试实现它。
从高层次来看，当我们将一个引用转换成裸指针时，就是一种再借用。那么随后，裸指针就可以对目标内存进行操作，当再借用结束时，发生的事情跟正常的再借用结束也没有区别。但问题是，再借用何时结束？当你再次开始使用原始引用时，可能是过期的好时机。否则，这就不是一个很好的嵌套栈。
但是没这么简单，我们可以将原始指针转换为引用，并且你可以复制裸指针。如果发生了以下转换 &mut -> *mut -> &mut -> *mut，然后去访问第一个 *mut，这时候的栈借用是如何工作的？
这就是为什么事情变得复杂。事实上，它们确实如此，因为栈借用试图变得更加宽松，让更多不安全的代码按照我们期望的方式工作。因此，我们需要在 miri 下运行代码来尝试发现编译器无法发现的错误。
正因为这种情况，miri 提供了试验性的模式: -Zmiri-tag-raw-pointers。可以通过环境的方式来开启该模式：
1 MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri test
如果是 Windows，你需要设置全局变量：
1 2 $env :MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri test
管理借用栈 因为之前的问题，使用裸指针，应该遵守一个原则：一旦开始使用裸指针，就要尝试着只使用它。
这使得意外失去裸指针访问内存的“权限”的可能性尽可能小。
实际上这样的规则在两个方面过于简单化了：
安全指针通常断言的属性不仅仅是别名：已分配的内存，内存对齐，足够大以容纳指向对象的类型，对象已正确初始化等。因此，在状态可疑时过度地使用它们更加危险。 即使你仅限于使用原始指针，也不能随意别名任何内存。指针在概念上与特定的“分配“相关联（可以是栈上的局部变量等粒度较小的对象），不应该从一个分配中获取指针，然后偏移它，并访问另一个分配中的内存。如果允许这样做，就会随处出现微小而难以捉摸的错误。这也是“指针只是整数”观点有问题的原因之一。 现在，我们依然希望在接口中使用安全的引用去构建一个安全的抽象，例如在函数参数中使用引用而不是裸指针，这样我们的用户就可以在安全的rust下调用它们。
所以我们要做的是：
在开始时，将输入参数中的引用转换成裸指针 在函数体中只使用裸指针 返回之前，将裸指针转换成安全的指针 但是由于我们这里数据结构中的字段都是私有的，无需暴露给用户，因此不用这么麻烦，直接使用裸指针即可。
事实上，我们所犯的重大错误的一部分就是继续使用Box。Box有一个特殊的地方，它会告诉编译器：“嘿，这很像 &mut ，因为它唯一拥有该指针”。
但是我们保留在列表末尾的裸指针指向一个Box，因此每当我们正常访问Box时，我们可能都会使该裸指针的“再借用”无效！
5.5 测试借用栈 总结和回顾一下上一小节的内容：
Rust 通过借用栈来处理再借用（reborrow） 只有栈顶的元素是处于 live 状态的( 被借用 ) 当访问栈顶下面的元素时，该元素会变为 live，而栈顶元素会被弹出( pop ) 从借用栈中弹出的元素无法再被借用 借用检查器会保证我们的安全代码遵守以上规则 Miri 可以在一定程度上保证裸指针在运行时也遵循以上规则 现在，尝试编写一些糟糕的代码，并让miri检测出来。通过大量的例子来尝试看看我们的思维模型是否有意义，并尝试对栈借用有一个直观的感受。
在实际代码中捕捉未定义的行为是一件棘手的事情。毕竟，你正在处理编译器字面上假设不会发生的情况。
如果我们足够幸运的话，写出来的代码是可以“正常运行的“，但是一旦编译器聪明一点或者你修改了某处代码，那这些代码可能会立刻化身为一颗安静的定时炸弹。当然，如果你还是足够幸运，那程序会发生崩溃，你也就可以捕获和处理相应的错误。但是如果你不幸运，整件事情就会以奇怪和令人费解的方式被破坏
Miri 尝试通过获取 rustc 最原始且未优化的程序视图并跟踪其解释时的额外状态来解决此问题。这是一种相当确定性和稳健的方法，但它永远不会完美。你的测试程序实际上需要执行带有该未定义行为（UB）的操作，并且对于足够大的程序，很容易引入各种不确定性（比如HashMap默认使用随机数生成器，random number generator，RNG）。
我们永远不能将 miri 批准我们的程序执行视为绝对确定的声明，认为miri通过就不存在 UB，这是不对的。 miri 也有可能认为某些东西是 UB，但实际上并非如此。也就是说，只能把miri当成一个参考。但如果我们对事物如何运作有一个提前的预期，并且 miri 似乎同意我们的观点，那么这是一个好兆头，表明我们走在正确的轨道上。
基本借用 之前这段代码被编译器检查出错误了：
1 2 3 4 5 6 7 8 9 let mut data = 10 ;let ref1 = &mut data;let ref2 = &mut *ref1;*ref1 += 1 ; *ref2 += 2 ; println! ("{}" , data);
让我们看看将 ref2 替换为 *mut 时会发生什么：
1 2 3 4 5 6 7 8 9 10 11 unsafe { let mut data = 10 ; let ref1 = &mut data; let ptr2 = ref1 as *mut _; *ref1 += 1 ; *ptr2 += 2 ; println! ("{}" , data); }
程序正常运行，输出13，产生了我们预期的结果。
现在让我们看看 miri（严格模式下）是如何看待它的：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run Finished dev [unoptimized + debuginfo] target(s) in 0.00s Running cargo-miri.exe target\miri error: Undefined Behavior: no item granting read access to tag <untagged> at alloc748 found in borrow stack. --> src\main.rs:9:9 | 9 | *ptr2 += 2; | ^^^^^^^^^^ no item granting read access to tag <untagged> | at alloc748 found in borrow stack. | = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
错误信息表明在借用栈（borrow stack）中找不到授予对标签为 <untagged> 的 alloc748 进行读取访问的项目。这非常好，我们关于事物如何工作的直观模型得到了支持：尽管编译器无法为我们捕获问题，但 miri 做到了。
让我们尝试一些更复杂的代码，之前提到的 &mut -> *mut -> &mut -> *mut 情况：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 unsafe { let mut data = 10 ; let ref1 = &mut data; let ptr2 = ref1 as *mut _; let ref3 = &mut *ptr2; let ptr4 = ref3 as *mut _; *ptr2 += 2 ; *ptr4 += 4 ; *ref3 += 3 ; *ptr2 += 2 ; *ref1 += 1 ; println! ("{}" , data); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 cargo run 22 MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run error: Undefined Behavior: no item granting read access to tag <1621> at alloc748 found in borrow stack. --> src\main.rs:13:5 | 13 | *ptr4 += 4; | ^^^^^^^^^^ no item granting read access to tag <1621> | at alloc748 found in borrow stack. |
在严格模式下，miri 可以“区分”两个原始指针，并使用第二个指针会它上面的指针无效。让我们看看当我们删除第一次使用时一切是否正常：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 unsafe { let mut data = 10 ; let ref1 = &mut data; let ptr2 = ref1 as *mut _; let ref3 = &mut *ptr2; let ptr4 = ref3 as *mut _; *ptr4 += 4 ; *ref3 += 3 ; *ptr2 += 2 ; *ref1 += 1 ; println! ("{}" , data); }
1 2 3 4 5 cargo run 20 MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run 20
这次就没有问题了。
测试数组 让我们使用裸指针，并用指针偏移量（ add 和 sub ）弄乱一些数组：
1 2 3 4 5 6 7 8 9 10 11 12 13 unsafe { let mut data = [0 ; 10 ]; let ref1_at_0 = &mut data[0 ]; let ptr2_at_0 = ref1_at_0 as *mut i32 ; let ptr3_at_1 = ptr2_at_0.add (1 ); *ptr3_at_1 += 3 ; *ptr2_at_0 += 2 ; *ref1_at_0 += 1 ; println! ("{:?}" , &data[..]); }
1 2 3 4 5 6 7 8 9 10 11 12 13 $ cargo run [3, 3, 0, 0, 0, 0, 0, 0, 0, 0] MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run error: Undefined Behavior: no item granting read access to tag <1619> at alloc748+0x4 found in borrow stack. --> src\main.rs:8:5 | 8 | *ptr3_at_1 += 3; | ^^^^^^^^^^^^^^^ no item granting read access to tag <1619> | at alloc748+0x4 found in borrow stack.
我们命名按照借用栈的方式来完美使用了，为何 miri 还是提示了 UB 风险？当我们去 ptr -> ptr 时，会发生什么奇怪的事情吗？如果我们只是复制指针，使它们都转到相同的位置会怎么样：
1 2 3 4 5 6 7 8 9 10 11 12 13 unsafe { let mut data = [0 ; 10 ]; let ref1_at_0 = &mut data[0 ]; let ptr2_at_0 = ref1_at_0 as *mut i32 ; let ptr3_at_0 = ptr2_at_0; *ptr3_at_0 += 3 ; *ptr2_at_0 += 2 ; *ref1_at_0 += 1 ; println! ("{:?}" , &data[..]); }
1 2 3 4 5 cargo run [6, 0, 0, 0, 0, 0, 0, 0, 0, 0] MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run [6, 0, 0, 0, 0, 0, 0, 0, 0, 0]
顺利通过。我们试试更加复杂的，但是仍指向同一个位置：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 unsafe { let mut data = [0 ; 10 ]; let ref1_at_0 = &mut data[0 ]; let ptr2_at_0 = ref1_at_0 as *mut i32 ; let ptr3_at_0 = ptr2_at_0; let ptr4_at_0 = ptr2_at_0.add (0 ); let ptr5_at_0 = ptr3_at_0.add (1 ).sub (1 ); *ptr3_at_0 += 3 ; *ptr2_at_0 += 2 ; *ptr4_at_0 += 4 ; *ptr5_at_0 += 5 ; *ptr3_at_0 += 3 ; *ptr2_at_0 += 2 ; *ref1_at_0 += 1 ; println! ("{:?}" , &data[..]); }
1 2 3 4 5 cargo run [20, 0, 0, 0, 0, 0, 0, 0, 0, 0] MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run [20, 0, 0, 0, 0, 0, 0, 0, 0, 0]
通过。当涉及到从裸指针派生其它裸指针时，miri实际上更加宽松。它们都共享相同的“借用”（miri称之为标签）。
当代码足够简单时，编译器有可能介入跟踪所有派生的裸指针，并尽可能去优化它们。但是这套规则比引用的那套脆弱得多。
那么问题在哪里呢？
我们发现 ref1_at_0 仅借用data的第一个元素。rust允许一些复合类型的分解借用，例如一个结构体，它的多个字段可以被分开借用，来试试这里的数组可不可以：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 unsafe { let mut data = [0 ; 10 ]; let ref1_at_0 = &mut data[0 ]; let ref2_at_1 = &mut data[1 ]; let ptr3_at_0 = ref1_at_0 as *mut i32 ; let ptr4_at_1 = ref2_at_1 as *mut i32 ; *ptr4_at_1 += 4 ; *ptr3_at_0 += 3 ; *ref2_at_1 += 2 ; *ref1_at_0 += 1 ; println! ("{:?}" , &data[..]); }
1 2 3 4 5 6 7 8 9 10 11 error[E0499]: cannot borrow `data[_]` as mutable more than once at a time --> src\main.rs:5:25 | 4 | let ref1_at_0 = &mut data[0]; // Reference to 0th element | ------------ first mutable borrow occurs here 5 | let ref2_at_1 = &mut data[1]; // Reference to 1th element | ^^^^^^^^^^^^ second mutable borrow occurs here 6 | let ptr3_at_0 = ref1_at_0 as *mut i32; // Ptr to 0th element | --------- first borrow later used here | = help: consider using `.split_at_mut(position)` or similar method to obtain two mutable non-overlapping sub-slices
看来不行。其实在调用不安全函数或方法 中我们介绍过，rust编译器不会跟踪数组索引来证明这些引用是不相交的，它只知道我们同时引用了它两次。
可以使用split_at_mut来将一个数组分成多个部分：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 unsafe { let mut data = [0 ; 10 ]; let slice1 = &mut data[..]; let (slice2_at_0, slice3_at_1) = slice1.split_at_mut (1 ); let ref4_at_0 = &mut slice2_at_0[0 ]; let ref5_at_1 = &mut slice3_at_1[0 ]; let ptr6_at_0 = ref4_at_0 as *mut i32 ; let ptr7_at_1 = ref5_at_1 as *mut i32 ; *ptr7_at_1 += 7 ; *ptr6_at_0 += 6 ; *ref5_at_1 += 5 ; *ref4_at_0 += 4 ; println! ("{:?}" , &data[..]); }
1 2 3 4 5 cargo run [10, 12, 0, 0, 0, 0, 0, 0, 0, 0] MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run [10, 12, 0, 0, 0, 0, 0, 0, 0, 0]
将数组切分成两个部分后，代码就成功了。像 split_at_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 28 29 30 unsafe { let mut data = [0 ; 10 ]; let slice1_all = &mut data[..]; let ptr2_all = slice1_all.as_mut_ptr (); let ptr3_at_0 = ptr2_all; let ptr4_at_1 = ptr2_all.add (1 ); let ref5_at_0 = &mut *ptr3_at_0; let ref6_at_1 = &mut *ptr4_at_1; *ref6_at_1 += 6 ; *ref5_at_0 += 5 ; *ptr4_at_1 += 4 ; *ptr3_at_0 += 3 ; for idx in 0 ..10 { *ptr2_all.add (idx) += idx; } for (idx, elem_ref) in slice1_all.iter_mut ().enumerate () { *elem_ref += idx; } println! ("{:?}" , &data[..]); }
1 2 3 4 5 cargo run [8, 12, 4, 6, 8, 10, 12, 14, 16, 18] MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run [8, 12, 4, 6, 8, 10, 12, 14, 16, 18]
看起来，指针不仅仅是整数：它们具有与其关联的内存范围，而使用rust，我们可以缩小该范围。
测试不可变引用 在之前的例子中，我们使用的都是可变引用，而rust中还有不可变引用（共享引用）。那么它将如何工作呢？我们已经看到裸指针可以自由复制，并且我们可以通过说它们“共享”单个引用来处理这个问题。也许我们以同样的方式看待共享引用？
由于 println 会自动对待打印的目标值进行 ref/deref 等操作，因此为了保证测试的正确性，我们将其放入一个函数中。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 fn opaque_read (val: &i32 ) { println! ("{}" , val); } unsafe { let mut data = 10 ; let mref1 = &mut data; let sref2 = &mref1; let sref3 = sref2; let sref4 = &*sref2; opaque_read (sref3); opaque_read (sref2); opaque_read (sref4); opaque_read (sref2); opaque_read (sref3); *mref1 += 1 ; opaque_read (&data); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 cargo run warning: unnecessary `unsafe` block --> src\main.rs:6:1 | 6 | unsafe { | ^^^^^^ unnecessary `unsafe` block | = note: `#[warn(unused_unsafe)]` on by default warning: `miri-sandbox` (bin "miri-sandbox") generated 1 warning 10 10 10 10 10 11
虽然这里没有使用裸指针，但是可以看到对于不可变引用而言，上面的使用方式不存在任何问题。下面来增加一些裸指针：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 fn opaque_read (val: &i32 ) { println! ("{}" , val); } unsafe { let mut data = 10 ; let mref1 = &mut data; let ptr2 = mref1 as *mut i32 ; let sref3 = &*mref1; let ptr4 = sref3 as *mut i32 ; *ptr4 += 4 ; opaque_read (sref3); *ptr2 += 2 ; *mref1 += 1 ; opaque_read (&data); }
1 2 3 4 5 6 7 cargo run error[E0606]: casting `&i32` as `*mut i32` is invalid --> src\main.rs:11:16 | 11 | let ptr4 = sref3 as *mut i32; | ^^^^^^^^^^^^^^^^^
可以看出，我们无法将一个不可变的引用转换成可变的裸指针。我们可以先将不可变引用强制转换为不可变的裸指针：
1 let ptr4 = sref3 as *const i32 as *mut i32 ;
rust的类型转换系统很棒。*const 类型几乎是一个相当无用的类型，只真正存在于描述C API并模糊地建议正确使用（事实确实如此），如上，先将不可变引用转换成不可变的裸指针，然后再转换成可变的裸指针。
好吧，没问题。看看miri怎么说：
1 2 3 4 5 6 7 8 9 MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run error: Undefined Behavior: no item granting write access to tag <1621> at alloc742 found in borrow stack. --> src\main.rs:13:5 | 13 | *ptr4 += 4; | ^^^^^^^^^^ no item granting write access to tag <1621> | at alloc742 found in borrow stack.
虽然我们可以通过双重强制转换来绕过编译器的检查，但它实际上并没有允许这个操作。当我们获取共享引用时，我们承诺不修改该值。
这很重要，因为这意味着当不可变借用从借用栈中弹出时，其下方的可变指针可以假设内存没有更改，并且可变指针可以假设它们写入的最后一个值仍然存在！
用一句话总结，那就是：一旦不可变引用位于借用栈上，推入其顶部的所有内容（它后面的指针）都仅具有读取权限。
但是我们可以这样做:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 fn opaque_read (val: &i32 ) { println! ("{}" , val); } unsafe { let mut data = 10 ; let mref1 = &mut data; let ptr2 = mref1 as *mut i32 ; let sref3 = &*mref1; let ptr4 = sref3 as *const i32 as *mut i32 ; opaque_read (&*ptr4); opaque_read (sref3); *ptr2 += 2 ; *mref1 += 1 ; opaque_read (&data); }
可以看到，我们仍然可以创建一个可变的裸指针，只要不去使用写操作，而是只使用读操作。
1 2 3 4 5 6 7 8 9 cargo run 10 10 13 MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run 10 10 13
再来检查下不可变的引用是否可以像平时一样正常弹出：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 fn opaque_read (val: &i32 ) { println! ("{}" , val); } unsafe { let mut data = 10 ; let mref1 = &mut data; let ptr2 = mref1 as *mut i32 ; let sref3 = &*mref1; *ptr2 += 2 ; opaque_read (sref3); *mref1 += 1 ; opaque_read (&data); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 cargo run 12 13 MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run error: Undefined Behavior: trying to reborrow for SharedReadOnly at alloc742, but parent tag <1620> does not have an appropriate item in the borrow stack --> src\main.rs:13:17 | 13 | opaque_read(sref3); // Read in the wrong order? | ^^^^^ trying to reborrow for SharedReadOnly | at alloc742, but parent tag <1620> | does not have an appropriate item | in the borrow stack |
我们这次获得了一个相当具体的 miri 提示，而不是之前的某个 tag 。这其实是有道理的，因为一旦存在任何共享引用，基本上其他所有内容都只是一大堆共享引用，因此无需区分它们中的任何一个！
测试内部可变性 之前我们使用内部可变性创建的链表很糟糕，与 RefCell 类似的还有 Cell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 use std::cell::Cell;unsafe { let mut data = Cell::new (10 ); let mref1 = &mut data; let ptr2 = mref1 as *mut Cell<i32 >; let sref3 = &*mref1; sref3.set (sref3.get () + 3 ); (*ptr2).set ((*ptr2).get () + 2 ); mref1.set (mref1.get () + 1 ); println! ("{}" , data.get ()); }
看看miri怎么说：
1 2 3 4 5 cargo run 16 MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run 16
等等，真的吗？没有报错。Cell到底是什么？
1 2 3 pub struct Cell <T: ?Sized > { value: UnsafeCell<T>, }
以上是标准库中的 Cell 源码，可以看到里面有一个 UnsafeCell，点进去看看：
1 2 3 4 5 6 #[lang = "unsafe_cell" ] #[stable(feature = "rust1" , since = "1.0.0" )] #[repr(transparent)] pub struct UnsafeCell <T: ?Sized > { value: T, }
这是它的源码定义，在标准库文档 中这样写道：
The core primitive for interior mutability in Rust. Rust 中内部可变性的核心原语。
If you have a reference &T, then normally in Rust the compiler performs optimizations based on the knowledge that &T points to immutable data. Mutating that data, for example through an alias or by transmuting an &T into an &mut T, is considered undefined behavior. UnsafeCell<T> opts-out of the immutability guarantee for &T: a shared reference &UnsafeCell<T> may point to data that is being mutated. This is called “interior mutability”. 如果您有一个不可变引用 &T ，那么通常在 Rust 中，编译器会根据 &T 指向不可变数据的事实来执行优化。改变该数据，例如通过别名或将 &T 转换为 &mut T ，被视为未定义行为。 UnsafeCell<T> 选择移除 &T 的不变性保证：不可变引用 &UnsafeCell<T> 可能指向正在改变的数据。这称为“内部可变性”。
All other types that allow internal mutability, such as CellRefCellUnsafeCell to wrap their data. 所有其他允许内部可变性的类型（例如 Cell<T> 和 RefCell<T> ）在内部使用 UnsafeCell 来包装其数据。
让我们看看使用UnsafeCell如何会让miri怎么样：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 use std::cell::UnsafeCell;fn opaque_read (val: &i32 ) { println! ("{}" , val); } unsafe { let mut data : UnsafeCell<i32 > = UnsafeCell::new (10 ); let mref1 : &mut i32 = data.get_mut (); let ptr2 : *mut i32 = mref1 as *mut i32 ; let sref3 : &i32 = &*ptr2; *ptr2 += 2 ; opaque_read (sref3); *mref1 += 1 ; println! ("{}" , *data.get ());
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 cargo run 12 13 MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run error: Undefined Behavior: trying to reborrow for SharedReadOnly at alloc748, but parent tag <1629> does not have an appropriate item in the borrow stack --> src\main.rs:15:17 | 15 | opaque_read(sref3); | ^^^^^ trying to reborrow for SharedReadOnly | at alloc748, but parent tag <1629> does | not have an appropriate item in the | borrow stack |
好吧，我们做到了，但后来我们通过使用 get_mut ，它可以窥视 UnsafeCell 内部并获得正确的 &mut i32 。如果编译器必须假设 &mut i32 可以查看 UnsafeCell 内部，那么它根本无法对别名做出任何假设，换句话说，如果编译器不能排除 &mut i32 引用可能访问到 UnsafeCell 内部的情况，那么编译器就无法对别名（aliasing）进行任何假设。这是因为 UnsafeCell 允许对内部数据进行非安全的操作，可能导致别名问题，进而破坏 Rust 提供的内存安全保证。
所以我们需要做的就是将 UnsafeCell 保留在我们的指针类型中，以便编译器理解我们在做什么。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 use std::cell::UnsafeCell;fn opaque_read (val: &i32 ) { println! ("{}" , val); } unsafe { let mut data = UnsafeCell::new (10 ); let mref1 = &mut data; let ptr2 = mref1.get (); let sref3 = &*mref1; *ptr2 += 2 ; opaque_read (&*sref3.get ()); *sref3.get () += 3 ; *mref1.get () += 1 ; println! ("{}" , *data.get ()); }
1 2 3 4 5 6 7 cargo run 12 16 MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run 12 16
很好。但是还有一个问题，代码顺序不对：我们首先创建了 ptr2，然后从可变指针创建了 sref3。然后我们在共享指针sref3之前使用裸指针，这一切似乎都是错误的。
我们可以做出以下假设：
Miri 并不完美，这实际上仍然是未定义行为 我们的简化模型实际上过于简单化了 我会选择第二个。但是为了安全起见，让我们制作一个在简化的借用栈模型中绝对无懈可击的版本：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 use std::cell::UnsafeCell;fn opaque_read (val: &i32 ) { println! ("{}" , val); } unsafe { let mut data = UnsafeCell::new (10 ); let mref1 = &mut data; let sref2 = &*mref1; let ptr3 = sref2.get (); *ptr3 += 3 ; opaque_read (&*sref2.get ()); *sref2.get () += 2 ; *mref1.get () += 1 ; println! ("{}" , *data.get ()); }
1 2 3 4 5 6 7 cargo run 13 16 MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run 13 16
我们的第一个实现实际上可能是正确的一个原因是，如果您认真考虑一下，就别名而言， &UnsafeCell<T> 确实与 *mut T 没有什么不同。
因此，从某种意义上说，我们只是创建了两个裸指针并像平常一样互换使用它们。两者都是从可变引用派生的有点粗略，所以也许第二个的创建仍然应该从借用栈中弹出第一个，但这并不是真正必要的，因为我们实际上并没有访问可变引用的内容，只是复制其地址。
像 let sref2 = &*mref1 是一件棘手的事情。从语法上看，我们似乎在取消引用它，但取消引用本身实际上并不是一件事？考虑 &my_tuple.0 ：实际上并没有对 my_tuple 或 .0 执行任何操作，只是使用它们来引用内存中的位置并将 & 在它前面写着“不要加载这个，只需写下地址”。
&* 是同一件事： * 只是说“嘿，让我们谈谈这个指针指向的位置”，而 & 只是说“现在写该地址下来”。这当然与原始指针的值相同。但是指针的类型已经改变了，因为类型不同。
也就是说，如果执行 &** 那么你实际上是在使用第一个 * 加载一个值。
实际上这就是我们在之前在通过位置和值理解内存模型 中提到的位置和值的概念。
测试Box 还记得为什么我们引入借用栈这个概念吗？原因就在于 Box 和裸指针混合使用时出了问题。Box有点像 &mut ，因为它声明它所指向的内存的唯一所有权。
1 2 3 4 5 6 7 8 9 10 unsafe { let mut data = Box ::new (10 ); let ptr1 = (&mut *data) as *mut i32 ; *data += 10 ; *ptr1 += 1 ; println! ("{}" , data); }
1 2 3 4 5 6 7 8 9 10 11 12 13 cargo run 21 MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run error: Undefined Behavior: no item granting read access to tag <1707> at alloc763 found in borrow stack. --> src\main.rs:7:5 | 7 | *ptr1 += 1; | ^^^^^^^^^^ no item granting read access to tag <1707> | at alloc763 found in borrow stack.
到现在，相信你很容易看出这样并不符合借用栈规则，修改代码：
1 2 3 4 5 6 7 8 9 10 unsafe { let mut data = Box ::new (10 ); let ptr1 = (&mut *data) as *mut i32 ; *ptr1 += 1 ; *data += 10 ; println! ("{}" , data); }
1 2 3 4 5 cargo run 21 MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run 21
很好，我们终于结束了对于借用栈的讨论与思考。但是，该如何使用 Box 来解决栈借用的问题？当然，我们可以像之前的测试例子一样写一些玩具代码，但是在实际链表中中，将 Box 存储在某个地方，然后长时间持有一个裸指针才是经常遇到的。
为了回答这个问题，我们将回到我们真正的使命：编写链表。
5.6 数据布局与基本操作 总结一下，在之前部分中，将安全的指针 & 、&mut 和 Box 跟不安全的裸指针 *mut 和 *const 混用是造成未定义行为的根源之一，原因是安全指针会引入额外的约束，但是裸指针并不会遵守这些约束。
我们将很快删除之前写的大部分内容，因为我们已经在第一次尝试中讨论了设计，并且除了我们如何将安全和不安全指针混合在一起之外，我们所做的一切基本上都是正确的。
新的数据布局 回忆一下旧的布局：
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>, }
这是我们的新布局：
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> = *mut Node<T>; struct Node <T> { elem: T, next: Link<T>, }
当我们使用原始指针时，Option不再那么有用，因此我们不再使用它。在后面的部分中，我们将讨论 NonNull 类型，但现在不用担心。
基本操作 List::new基本上是一样的。
1 2 3 4 5 6 7 use std::ptr;impl <T> List<T> { pub fn new () -> Self { List { head: ptr::null_mut (), tail: ptr::null_mut () } } }
push基本上也是…
1 2 pub fn push (&mut self , elem: T) { let mut new_tail = Box ::new (
等等，我们已经没有Box了，现在如何分配内存？
我们可以使用 std::alloc::alloc ，但这就像把武士刀带进厨房一样。它可以完成这件事，但有点矫枉过正和笨拙。
我们想要Box，但是没有。一种疯狂但也许可行的方案是这样：
1 2 3 4 5 struct Node <T> { elem: T, real_next: Option <Box <Node<T>>>, next: *mut Node<T>, }
先创建一个 Box ，并使用一个裸指针指向 Box 中的 Node，然后就一直使用该裸指针直到我们处理完 Node 且可以销毁它之时。最后，可以将 Box 从 real_next 中 take 出来，并 drop 掉。这符合我们非常简化的借用栈模型。
但这看起来不够优雅，这不是关于Rc和RefCell的章节，我们不会再玩这个游戏了，让我们搞些简单干净的东西。
我们将使用非常方便的Box::into_raw函数
1 pub fn into_raw (b: Box <T, A>) -> *mut T
消费掉 Box ，返回其包装的裸指针，即 *mut T 类型的指针。该方法会释放 Box<T> 指向的堆内存，并返回一个指向相同内存位置的裸指针。
调用这个函数后，调用者需要负责之前由Box管理的内存。特别是调用者应该正确销毁T并释放内存，考虑到Box使用的内存布局。最简单的方法是使用Box::from_raw函数将裸指针转换回Box，让Box的析构函数执行清理操作。
注意：这是一个关联函数，这意味着您必须这样使用 Box::into_raw(b) 而不是 b.into_raw() 。这样就不会与内部类型上的方法发生冲突。
使用 Box::from_raw 将裸指针转换回 Box 以进行自动清理：
1 2 3 let x = Box ::new (String ::from ("Hello" ));let ptr = Box ::into_raw (x);let x = unsafe { Box ::from_raw (ptr) };
当然也可以通过显式运行析构函数并释放内存来手动清理：
1 2 3 4 5 6 7 8 9 use std::alloc::{dealloc, Layout};use std::ptr;let x = Box ::new (String ::from ("Hello" ));let p = Box ::into_raw (x);unsafe { ptr::drop_in_place (p); dealloc (p as *mut u8 , Layout::new::<String >()); }
很好，这看起来确实是为我们的用例设计的。它也符合我们试图遵循的规则：从安全的东西开始，变成裸指针，然后只在最后（当我们想要删除它时）转换回安全的东西。
现在，我们就可以到处使用裸指针，也无需再注意unsafe块的范围，因为内部现在一切都不安全了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 pub fn push (&mut self , elem: T) { unsafe { let new_tail = Box ::into_raw (Box ::new (Node { elem: elem, next: ptr::null_mut (), })); if !self .tail.is_null () { (*self .tail).next = new_tail; } else { self .head = new_tail; } self .tail = new_tail; } }
现在我们坚持使用原始指针，代码实际上看起来简洁多了！
继续实现 pop，它跟之前区别不大，但是要记住必须使用 Box::from_raw 来清理堆内存：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 pub fn pop (&mut self ) -> Option <T> { unsafe { if self .head.is_null () { None } else { let head = Box ::from_raw (self .head); self .head = head.next; if self .head.is_null () { self .tail = ptr::null_mut (); } Some (head.elem) } } }
告诉 take 和 map，我们回不去了。只不过在这里我们得手动检查和设置 null 。
再实现下析构器，直接循环调用 pop 即可：
1 2 3 4 5 impl <T> Drop for List <T> { fn drop (&mut self ) { while let Some (_) = self .pop () { } } }
它非常简单，好了，下面就是最重要的环节——测试：
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 ); } }
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
别高兴得太早，miri会接受吗？
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri 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
太棒了！但是严谨起见，还是要说明：未能找到未定义的行为并不能证明它不会引发问题，因此我们可以将其称之为100%机器验证通过。
5.7 更多的操作 现在 push 和 pop 已经写好了，剩下的操作与之前也没太大区别。只有会改变链表长度的操作才会使用尾指针。
但是所有的东西都是不安全的指针，我们需要重写代码来使用它们。既然我们要接触所有代码，不妨借此机会确保我们没有遗漏任何东西。
让我们从栈的实现中复制代码：
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 error[E0392]: parameter `'a` is never used --> src\fifth.rs:68:17 | 68 | 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:72:20 | 72 | pub struct IterMut<'a, T> { | ^^ unused parameter | = help: consider removing `'a`, referring to it in a field, or using a marker such as `PhantomData`
编译器提示'a并没有被使用，要解决这个问题，可以将其移除，也可以使用PhantomData，它是什么？在深入Waker与Context的内部 中我们曾经见过它，这次有必要来简单研究一下。
PhantomData是零大小类型（Zero-sized type），用于标记“表现得像”拥有 T 的事物。
在你的类型中添加一个 PhantomData<T> 字段，可以告诉编译器你的类型就好像它存储了 T 类型的值，即使事实并非如此。该信息在计算某些安全属性时使用，当然也可以让编译器不再给出 T 未被使用的警告或者错误。
有关如何使用 PhantomData<T> 的更深入说明，请参阅 Nomicon 。==todo==
也许PhantomData最常见的用例是具有未使用的生命周期参数的结构，它们通常作为某些不安全代码的一部分。
我们可以沿着使用PhantomData这个方向走，但是目前还不是很必要，真正需要它的是双向链表，这不在我们本节考虑的范围。
继续使用引用也是不错的选择。能使用引用的原因是：我们可以创建一个迭代器，在其中使用安全引用，然后再丢弃迭代器。一旦迭代器被丢弃后，就可以继续使用 push 和 pop 了。
事实上，在迭代期间，我们还是需要解引用大量的裸指针，但是可以把引用看作裸指针的再借用。总之，尝试一下：
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 来包裹，并通过 ptr::as_refptr::as_mut
通常，我会尽量避免使用 as_ref 这类方法，因为它们在做一些不可思议的转换。但是上面却是极少数可以使用的场景之一。
这两个方法的使用往往会伴随很多警告，其中最有趣的是：
你必须强制遵循 Rust 的别名规则，因为返回的生命周期 'a 是任意选择的，并不一定反映数据的实际生命周期。特别是，当此引用存在时，指针指向的内存不得发生变化（ UnsafeCell 内部除外）。
这正是我们在前面花费了很长篇幅讲的借用栈规则！我们肯定可以在这里遵循此规则，但是除此之外，还要考虑的一个问题是函数签名：
1 pub unsafe fn as_mut <'a >(self ) -> Option <&'a mut T>
注意这里凭空出现的 '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 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 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 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; 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
接下来，是 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 () } }
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>>`
这个简单，使用map就可以了。
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 food”吧。
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
非常好。总算完成了。
5.8 最终代码 好吧，通过一点点的不安全性，新的实现可以获得线性的性能提升，并且我们成功地重用了安全栈实现中的几乎所有逻辑！
除了要处理栈借用和miri的那部分之外，我们不必编写任何Rc或RefCell的东西。
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 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 use std::ptr;pub struct List <T> { head: Link<T>, tail: *mut Node<T>, } type Link <T> = *mut Node<T>;struct Node <T> { elem: T, next: Link<T>, } 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 new () -> Self { List { head: ptr::null_mut (), tail: ptr::null_mut () } } pub fn push (&mut self , elem: T) { unsafe { let new_tail = Box ::into_raw (Box ::new (Node { elem: elem, next: ptr::null_mut (), })); if !self .tail.is_null () { (*self .tail).next = new_tail; } else { self .head = new_tail; } self .tail = new_tail; } } pub fn pop (&mut self ) -> Option <T> { unsafe { if self .head.is_null () { None } else { let head = Box ::from_raw (self .head); self .head = head.next; if self .head.is_null () { self .tail = ptr::null_mut (); } Some (head.elem) } } } 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) } } 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 () } } } } impl <T> Drop for List <T> { fn drop (&mut self ) { while let Some (_) = self .pop () { } } } 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 }) } } } #[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 ); } #[test] fn into_iter () { let mut list = List::new (); list.push (1 ); list.push (2 ); list.push (3 ); let mut iter = list.into_iter (); assert_eq! (iter.next (), Some (1 )); assert_eq! (iter.next (), Some (2 )); assert_eq! (iter.next (), Some (3 )); assert_eq! (iter.next (), None ); } #[test] fn iter () { let mut list = List::new (); list.push (1 ); list.push (2 ); list.push (3 ); let mut iter = list.iter (); assert_eq! (iter.next (), Some (&1 )); assert_eq! (iter.next (), Some (&2 )); assert_eq! (iter.next (), Some (&3 )); assert_eq! (iter.next (), None ); } #[test] fn iter_mut () { let mut list = List::new (); list.push (1 ); list.push (2 ); list.push (3 ); let mut iter = list.iter_mut (); assert_eq! (iter.next (), Some (&mut 1 )); assert_eq! (iter.next (), Some (&mut 2 )); assert_eq! (iter.next (), Some (&mut 3 )); assert_eq! (iter.next (), None ); } #[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 ); } }
6 生产级别可用的不安全的双向链表 7 更多的链表实现 7.1 双向单链表 7.2 栈上分配内存的链表 常用第三方crate
alipay
wechat