前言

昨天我们失败了，倒在了Iter和IterMut面前，今天我们用unsafe来实现一波！

一个好但是不安全的队列（An Ok Unsafe Queue）

因为步子迈的太开，吃了教训，所以我们重新回归单向队列。

另外，因为受够了Rc和RefCell两位“阿嫲”的训斥，我们准备找彬彬去“unsafe网吧”玩raw pointer。

老规矩，搞个firth.rs然后添加到lib.rs

布局

我们的代码准备在second.rs也就是一个ok的单向栈上改动，因为队列和栈是相似的，除了特性。

队列讲究的是先进先出，我们只需要改变pop，让它导出最后那个即可

当然，我们也可以思维稍微绕一下，我们把准备push的节点放到list的最后，然后pop不动，也是可以的。

但是两种方案其实都有问题，因为我们都需要走到最后一个节点，这就意味着每次push和pop的时间复杂度是O(n)！，那么链表的优势就没了。

这个问题其实也好解决，直接搞个指针指向最后一个节点即可，当然，在其它语言中，这非常简单。

但是在rust中有 生命周期的问题！

抛开这个关键点不谈，我们回到问题本身，如果这么做的话，pop就不行了，因为最后一个节点pop掉之后，指针应该指向原本倒数第二个节点，但是我们是单向的，所以没办法指回去。你可能会想：那我们指倒数第二个不就好了？（章北海：）都一样的，你怎么让倒数第二个指向原本的倒数第三个？

所以我们只能采用push的方案，因为push简单，只需要保留最后一个节点的指针即可，下个节点来了再刷新成这个节点的指针即可。然后出的话还是从头出，完美！

那么回到关键点：怎么解决生命周期的问题

你可能会疑惑，是啥生命周期？我们来尝试下就知道了：

看着挺完美，运行下：

额，忘了

这样就没问题了，然后我们把pop搬过来

同样加上生命周期，然后再搞几个测试用例：

然后我们直接开测

是的，报错不是在我们的链表，而是在调用时。

我们犯了个大错：我们在我们里面搞了个指针指向自己

但是可能又疑惑了，我们前面不也是这样么？

是这样，但是我们这次多了生命周期，我们尝试在同一个生命周期中多次使用同一个&mut self，这就是前面所说的生命周期问题。

那咋整，回到Rc<RefCell<T>>，未尝不可，但是Iter这块我们依旧没法解决。

所以这个时候我们要使用unsafe的raw pointer了。

我们前面也有学习过，这里就不多说了，简单地说就是让编译器彻底放开管控。

**PS：**如果你的unsafe代码非常简单，那么编译器其实也是可以管的，帮你优化下。

*mut表示这货是个可变的原始指针。

当然这个定义还是有些问题，后面会遇到。

Let's be C everyone. Let's be C all day.

I'm home. I'm ready.

Hello unsafe.

笑

unsafe Rust

之前的文章，如果你忘了可以回去看下：rust基础学习--day37：高级功能 (serenesyllables.com)

它有两种：

1. *const T：参考的C里的const T*
2. *mut T：同样参考的c里的T*，这货就是我们要用的，简单地看做是&unchecked mut T即可。

作者还有另一篇教程教unsafe rust的：https://doc.rust-lang.org/nightly/nomicon/

基础方法

还是new，不过这回我们需要调整了：

当然，更推荐使用ptr::null_mut来初始化。

我们这里没有指向Option<&mut Node<T>>，既然都使用unsafe了，那一步到位，直接指向Node<T>。

pop就简单了，还是头出去，不过需要兼容下空的场景

测试用例：

Miri

上面的代码看着正常，其实里面埋着一个雷。

但是我们没办法找到这颗雷，因为编译器已经被我们舍弃了，runtime跑起来看着又正常。。。

...Wait, who's that sketchy looking person in the alleyway?

"Hey kid, you wanna interpret some Rust code?"

Wh- no? Why,

"It's wild man, it can validate that the actual dynamic execution of your program conforms to the semantics of Rust's memory model. Blows your mind..."

What?

"It checks if you Do An Undefined Behaviour."

I guess I could try interpretters just once.

"You've got rustup installed right?"

这段对话有些搞笑，就不翻译了（没这能力知道吧，可以看：Miri - Rust语言圣经(Rust Course)，翻译的也很好笑）

就是介绍了下[Miri](GitHub - rust-lang/miri: An interpreter for Rust's mid-level intermediate representation)，一个实验性的Rust MIR解析器(interpreter)，可以执行我们的二进制和测试单元并且监听确定的类(classes)的未知行为（ undefined behavior），比如：

• 访问越界的内存以及试图在释放后使用（use-after-free）
• 使用未初始化的数据
• 违反确定好的前提条件（触发unreachable_unchecked，在重叠区域调用copy_nonoverlapping）（没搞懂，建议去看下Miri官网的描述）
• 数据竞争
• 内存访问和引用不一致（没对齐）
• 违反一些基础类型的变体，比如一个布尔值被设置成0或者1。
• 实验性：违反 Stacked Borrows规则控制（governing）一个引用类型的别名（aliasing）。
• 实验性：违反 Tree Borrows别名规则，作为 Stacked Borrows的可选替代
• 实验性：数据竞争
• 内存泄漏

简单地说就是一个检查runtime的工具

实验性，那就意味着是nightly。

你可以通过rustup toolchain install nightly下载nightly的分支：

然后再通过rustup override set nightly切换到nightly。

注意：nightly是根据文件夹来区分的，简单地说就是作用域，只作用于当前文件夹。

然后我们再安装Miri，以前是一个crate，现在是工具

通过rustup component add miri安装miri。

或者跟着作者：

What did you just install on my computer!?

What did you just install on my computer!?

"The Good Stuff"

安装完之后我们可以通过cargo miri test来测试下是否正常安装（注意要在nightly的环境）

然后我们运行后发现了报错，而这在cargo test的时候是没有的：

(注意，和作者的报错不同)

Woah. That's one heck of an error.

"Yeah, look at that shit. You love to see it."

Thank you?

"Here take the bottle of estradiol too, you're gonna need it later."

Wait why?

"You're about to think about memory models, trust me."

NARRATOR: The mysterious person then proceeded to transform into a fox and scampered through a hole in the wall. The author then stared into the middle distance for several minutes while they tried to process everything that just happened.

ok，我们现在来看下报错是啥.....看不懂，但是这里有关键字：borrow stack。

stacked Borrows

我们不深入了解，浅尝即止

这玩意儿目前还是实验性的，所以不一定就是大问题，不过精益求精的精神我们得有！

为什么这里会有一个实验性的规则呢？

Safe Stacked Borrows

问题的主要诱因（motivation）是：Pointer Aliasing。

别名，顾名思义就是这个数据有俩指针指向，换句话说就是一块重叠区域存在俩指针指向它，这种自然就是违背了Rust 借用规则的。

这个问题主要是内存访问，并且只有指针是mut的才会危险。

打个比喻（The Parable of the Tiny Angry Man）

原文太长，我简单地说，想看原文的请出门左拐：Stacked Borrows - Learning Rust With Entirely Too Many Linked Lists (rust-unofficial.github.io)

简单地说就是俩人死对头，其中A发现了一本旧书放在书架上*《战争与和平》(War and Peace)*，这是他以前看过的，后面扔到这里就没动过了，现在才想起。

这时他的死对头B过来了，然后他俩在这“嘘寒问暖”，这时A想装逼，问B看过*《战争与和平》*吗，B说没有，没人看过，这个时候A说他看过，并指向了刚拿书的地方。B怒了，走过去拿出那本书，上面赫然写着《War And Feet》。B笑的乐开了腿，A则羞愧难以，但他发誓看到的绝对是战争与和平。

B（带着从未有过的）开心的走了，徒留A在这哭断肠。

A重新拿起书，发现书上面有一个很小很小的人，它满脸的愤怒，飞到A面前说：“你颜面扫地，不会再有人信你了”

A之后在当地人脉网络中失去威望。。。

故事有点莫名其妙，其实就是A觉得他的看到的不可能被改变（眼见为实），所以敢装逼，但是突然不知哪里来的小人儿给了他一闷棍。

那么映射到我们这个问题，就是我们觉得我们的数据因为所有权的规则，不可能改变，所以我们直接用这个数据来做其它计算，但是不知道哪里来的野指针把我们的数据改了，导致全乱了。

这就是指针混叠的关键：什么时候编译器可以假设这个数据是安全可以cache的，要确定是否可以cache，编译器必须得知道有没有小人给闷棍。

这一点自然不需要我们担心，对于编译器来说，借用规则就是它最好的武器。

我们来看个例子：

这段代码是可以跑的

然后我们调整下ref1 += 1和ref2 += 2的位置

这个时候就报错了：

原理：当我们引用一个指针的时候，原来的就不能用了，直到新引用的没有用了。例子1能跑就是因为ref1 += 1之后的代码中不再用到ref2。

等等！这不就是栈吗？？这不就是借用栈吗？？

只有栈头的引用可以动数据本身，也就不用担心哪来的野孩子给闷棍了。

但是，我们用了unsafe，触碰了那禁忌的深渊。。

Unsafe Stacked Borrows

原始指针自身就是野孩子，根本没人管，还管什么规则。。。

所以我们要借助Miri来管教一下。。成何体统！

不过我们也可以《有较强的自我管理意识》，我们自行按照编译器那样管理指针不就好了？自我管理终究是局限的，超出三个就很麻烦了，当然，我们自己也可以搞个mini的栈来维护（？？？那和引用有什么区别）。

Miri还有一个严格模式：-Zmiri-tag-raw-pointers，自然就是针对原始指针的。

要开启这个，我们需要设置下环境变量

powerShell的是$Env:MIRIFLAGS="-Zmiri-tag-raw-pointers"

管理借用栈

一旦我们用上了原始指针，我们应该尽量简单的、直接的使用原始指针，并且只使用原始指针。

这样就可以避免一些莫名其妙的丢失。

这里有两点需要注意：

1. 安全指针不一定只是因为重叠而断言，其它的还有内存的分配，对齐内存，是否足够大到可以装下类型、是否初始化。所以如果事情变得危险起来，直接失效这个指针不是一个好方案。
2. 即使你停留在原始指针的土地上，你也不能随意重叠任何内存。从概念上讲，指针与特定的“分配”（可以像堆栈上的局部变量一样精细）相关联，并且您不应该从一个分配中获取指针，偏移它，然后访问不同分配中的内存。如果允许这样做，那么到处都是愤怒的小人的威胁。这就是“指针只是整数”是一个有问题的观点的部分原因。

虽然我们用上了unsafe，但是我们希望暴露出去的接口是safe的（正如其它人做的那样）。

所以我们接下来准备实现这几点：

1. 方法输入的参数还是是引用，我们通过这个引用去拿原始指针
2. 尽量只使用原始指针
3. 将我们的原始指针变成安全的指针再输出

实际上我们代码中还有一个大问题，就是用了Box，根据我们上面几点，我们是不能用安全指针的，但是Box自身返回的就是一个安全指针，几乎等同于&mut。

一旦我们操作于这个Box，那么我们的原始指针可能就存在问题。

所以我们需要调整这一点。

测试借用栈

先整理下上一小节中学到的知识点：

1. Rust概念上针对同一块内存重复借用（reborrows）的问题是通过维护一个叫借用栈（borrow stack）的方式来处理的
2. 只有栈顶的指针是live也就是可用于使用的
3. 如果你使用的非栈顶的指针突然变成live的，那就意味着之前栈顶的指针已经出栈
4. 已经出栈的指针是不能使用的
5. borrowchecker保证了安全的代码一定遵守这规则
6. Miri理论上也是遵守这规则来检查runtime的原始指针

Basic Borrows

前面我们已经知道了这块代码在safe的情况下是无法运行的，因为ref2还在借用栈顶。

那么如果我们将ref2变成原始指针呢？

这样就没问题了，因为ref1还是在栈顶，原始指针ptr2不会入栈。

数据也是正常改动。

然后我们再用miri过一遍

报错了。。这货不是被允许的那个访问内存的item

我们在来搞个复杂点的：&mut -> *mut -> &mut -> *mut

然后分别用cargo和miri运行下：

cargo runtime给过了，因为确实不存在同一个数据同时拥有两个可变指针。

miri喜闻乐见的报错了，因为ptr4此时违反了借用栈的规则，即使是在runtime，因为ptr2先跑了。

如果我们移除ptr2的改动，那么就会正常

测试数组

我们搞个复杂点的：

注意，我们这里用的是数组，放在栈上的，所以元素在内存上是连续的。

这里用的是pointer::add，返回一个指向数组的第一个元素的原始指针。

那么我们的预期结果就是[3, 3, 0, ...]

cargo runtime依旧是顺利，miri也依旧很顺利的报错了。

Rips up gradschool application

这回我们应该是没作妖的，每一步都是按照栈的规则来的，为啥还是有问题。

我们先把ptr_at_1移除：

这回就正常了，那说明问题是出在add这一块。

虽然array自身只有一个allocation，但是它里面元素的借用是独立的。

（部分数据结构都可以，比如struct）

我们虽然不知道上面的问题原因，但是我们可以绕过这个问题：

我们可以用Slice::split_at_mut来拆分，返回两部分&mut。

确实可行！

但是问题到底是啥呢？

我们再重新指回去：

不是指向单个元素，而是数组本身，这样居然也是可以的！

但我们仍未知道通过之前的指针add返回的指针为什么不行

其实问题很简单，这里引用一个老哥的评论（原文翻译那篇底下的评论测试栈借用 - Rust语言圣经(Rust Course)）：普通情况下，rust无法通过下标来判断对数组不同部分的借用是不相交的，比如：

这么做是不行的，会报错

所以我们不能通过这种方式去创建新的指针。

测试不可变引用

我们前面都是用的可变原始指针，现在我们来试下不可变原始指针，原来我们可以直接堆原始指针进行复制，编译器不会拦截，现在我们用miri来试下。

不过在这之前，我们先复习下不用miri的表现：

在cargo run中是可行的, 因为是不可变的，所以不会有问题，只要可变的mref1后面没有读的代码即可，然而下面这种代码不行：

指向一个引用的原始指针，一不小心就会变悬浮原始指针。

当然，改成self3 = &*mref1也是不行的

因为类型不对，我们试图将一个不可变的变成一个可变的。

但是，这套并不适用于原始指针，啥意思呢？比如：

先变成一个不可变的原始指针，符合了要求，然后原始指针可以无限复制，并且没有可变和不可变的问题。

然后我们用Miri运行一下：

不行了，简单的说还是那一套：如果借用栈中存在一个不可变引用，那么它前面的那些引用都不可变。

那么我们上面的代码要调整下：

3和4都只能是不可变，也就是只读，当3出栈之后，栈顶则可以访问内存并修改。

注意，只有3出栈了才可以修改，也就是2不能放到3前面去修改数据，这个顺序问题和上面可变引用的没差别，两者共用这套规则，所以混着来也没问题。

测试内部可变性

回想一下我们前面使用Rc和RefCell写的那个双向链表，我们卡在了Iter也就是不可变引用的地方，当时的问题是我们没办法通过内部去返回这个数据的引用，主要就是生命周期的问题（当然，是泛型的问题，如果是支持Copy的，那其实可以实现，但就算如此，IterMut也实现不了，因为还是需要一个引用）。

这次我们不用RefCell了，我们改用std::cell::Cell ，这货简单的说也是可以访问数据，但是它比RefCell舒服，可以直接访问，而不是borrow。

但是代价自然是得是实现了Copy（前面貌似说过？）。

那我们这里依旧不适用啊（后面会有适用的）

噢，不对，我们这里只是测试下Miri的检查能力而已，那么我们就固定类型为i32了。

你应该有些奇怪，为什么Miri没有报错，明明我们的代码写和读的顺序有问题。

答案其实藏在它的源码里面：

是它！std::cell::UnsafeCell

这货顾名思义就是一个unsafe的cell，它不要求数据实现Copy，所以理论上它可以作为我们实现Iter和IterMut的最佳方案。

前面貌似没有介绍过内部可变性，这里简单的说一下：

如果我们有一个&T，然后编译器会根据它遵守的关于&T的规则去优化它，如果我们修改数据比如通过别名化把一个&T变成&mut T，那么这个时候编译器就会认为这是个UB（undefined behavior）。

而UnsafeCell<T>则是去掉（opts-out）&T不可变的保证（guarantee）,&UnsafeCell可能指向一个已经被修改了的数据。

这就是内部可变性。

然后我们直接用UnsafeCell走一波：

喜闻乐见的报错了，问题自然是读写顺序违反借用栈的规则。

那么问题来了，为啥Cell那小子没问题？它明明只是根据我UnsafeCell封装的一层（这届金马奖最佳男主角就是~~~阿发！！！的岳父~）。先按下不表

这里补充下，一般内部使用unsafe的不代表调用它的时候也是unsafe的，它们是人工确认过safe了才暴露的，所以对于调用者来说，它就是safe的。

回到问题，我们来看下get_mut

那么一切就说得通了！

搞清楚后，那这个问题就简单了，换成get,这货返回的是一个*mut T，而不是引用。

那么回到我们前面的问题：同样是顺序问题，为什么Cell是正常的？

为了搞清楚这问题，我们模仿Cell写一个Unsafe的例子：

也没问题！

前面我们说过，get方法返回一个*mut T，那么关键就在这里，相当于每次都复制一个原始指针！所以是没问题的。

来看下Cell::get的源码：

就是用的UnsafeCell::get,也就是复制一个*mut T。原始指针搞几个都没问题！（注意，这里是指向源数据的原始指针，而不是根据当前的原始指针，所以没有借用栈）。

测试Box

ok，最后一个小小章节（有点崩溃(ㄒoㄒ)）

我们来测试下Box

前面说过Box是返回一个引用，那和我们的目标（尽量只用原始指针）有冲突，不过Box虽然类似&mut T，但是它要求拥有指向的那块内存的所有权。

熟悉的错误，顺序问题，看来用了Box也没啥问题，调整下代码：

这回没有问题了，看样子Box并不会阻碍我们的开发。

不对。。。还是有问题，因为我们并不能控制顺序，我们要指向Box所在位置并且保留这个原始指针很久。。。

不管了，走一步算一步，大不了去掉Box（?）

重新设计结构 + 基础方法

结构

先回看下我们之前的结构：

夹生饭，然后我们调整下，都改成原始指针

其实去掉Box就好啦，就它碍事~。

注意：Option<T>对于原始指针来说不一定是一件好事。不过我们确实需要None来表示没有，那咋整呢？没事，后面会有合适的

基础方法

new还是微调：

现在头尾都是原始指针

然后我们来重新设计下push，还记得我们前面说的么？我们希望我们的链表是safe的，即使内部用的unsafe，只要输入和输出是safe的，那么就可以认定是safe的，所以push的输入参数得是引用，然后我们再根据这个引用去获取原始指针。

==，我们去掉了Box，但是这里又有个问题了，怎么关联前后俩节点？不能直接存放吧，那又回到最初最初的那个问题：无法分配空间。

没事！没了Box，我们还有std::alloc::alloc？然而这太杀鸡用牛刀了，太浪费先不说，自行维护也是个大问题。

难道我们必须使用Box才行吗？

也许我们不一定得移除Box，我们可以将Box**“隐藏”**起来，比如：

我们将Box放到了real_next里，而我们平时使用的还是next。

如果你想这么做，自娱自乐可以，太尴尬了。。。

是时候不扯皮了，现在我们确实非Box不可，那么不如转换下思维，我们能不能拿到Box的原始指针？

当然可以！（搁这扯半天的皮）

Box::into_raw：

顾名思义，就是返回这个Box的原始指针！

那么一切就都迎刃而解了。

不过这里有个注意事项：我们前面说过Box虽然是&mut T，但是它要求占有这个空间，所以当我们使用into_raw的时候，它的所有权也会跟着移出，也就是说这个Box被消耗(consumes)了，返回的原始指针对齐内存并且non-null。因此有点需要特别注意，调用方应适当地销毁 T 并释放内存，同时考虑到 Box 使用的内存布局，对此，最简单的方案就是将原始指针拥有的所有权交还给Box，使用Box::from_raw，然后让Box自行去销毁。

**另外一点：**获得所有权不能使用pointer = box.into_raw()，而是得通过Box::into_raw(box)的方式，因为这是个关联函数。

例子：

说的貌似有点多，我们回到push方法中

然后我们再来实现pop的，这个时候因为需要释放，所以我们需要将原始指针的所有权交还给Box，所以需要使用Box::from_raw的方法：

这俩都是关联函数，都得通过Box来调用。

另外，因为我们去掉了Option<T>，所以我们需要手动使用is_null去确认原始指针是否指向一个空的地址。

注意这里我们的输出是一个Some(T)，是一个safe的。

然后drop依旧是调用pop就好

ok,基础的几个都搞完了，那么现在来写测试用例！

然后分别用cargo test和cargo miri test

都没问题！

当然，不代表着真的都没问题，但是已经尽我们所能的去确认了，问心无愧😀

Extra Junk

ok，又要面对IntoIter、Iter以及IterMut三兄弟了，上次我们就在这折戟（貌似还有步子迈太开的问题）

我们先回看下我们之前定义的结构

现在我们需要调整，Option<T>不要了，生命周期是推卸产物，自然也不要。

看起来很不错！然后运行下

看起来是生命周期有问题，这里的PhantomData又是个啥?

简单的说，就是一个Zero-sized type也就是无空间占用的类型，是用来标记事务，让它们表现的像拥有T的所有权。

我们加上PhantomData<T>标记我们的类型，告诉编译器这个类型目前拥有数据的所有权，尽管实际上并不是。

更深一点的解释：the Nomicon

至于Unused lifetime parameters，对struct来说比较常见，特别是struct保有一些unsafe的code。

这里我们先不解决，我们保留这个问题,后面我们还要接触到。

但是如果不能解决这个问题，我们要咋整？

等等！！回想一下IntoIter，它只是self.pop！然后Iter和IterMut则是返回节点的引用！！！

所以我们根本没必要去改动！！！

唯一有影响到节点本身的就push和pop。

另外还记得我们的目标吗？安全的抽象接口，所以返回的数据都是Option<T>，所以我们没必要去变成原始指针！！！

直接抄过来就好：

当然，这貌似违背了我们的预期：尽量使用原始指针，但是如果我们要的对象只是链表本身呢？那其实我们的目标已经实现了。这三个迭代其实并不算是链表的本体（强词夺理一波）

注意这里as_ref和as_mut是 ptr::as_ref和ptr::as_mut。

这俩方法有一堆的warning，不过其中一条比较重要：

你必须强调别名规则，因为返回的生命周期‘a不一定是实际的生命周期，它是随便选的一个作为返回的生命周期。具体而言，在这个生命周期存活期间，其它指针都不能对这个内存进行访问

还剩下的那几个peek之类的

然后是测试用例：

搞定！！！

代码整合

总结

老实说有些复杂，知识点有些多和乱。。。这篇理解了下面我们就会轻松很多。。