基础

好了，回到最基本的问题，我们如何构建我们的列表？

在我们这么做之前：

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None, tail: None }
    }
}

但是我们不再使用 Option 作为 tail：

> cargo build

error[E0308]: mismatched types
  --> src/fifth.rs:15:34
   |
15 |         List { head: None, tail: None }
   |                                  ^^^^ expected *-ptr, found enum `std::option::Option`
   |
   = note: expected type `*mut fifth::Node<T>`
              found type `std::option::Option<_>`

我们可以使用 Option，但是不像 Box，*mut 可以为空。这意味着它不能从空指针优化中获益。相反，我们将使用 null 表示 None。

那么我们如何得到一个空指针呢？有几种方法，但我更喜欢使用 std: : ptr::null_mut()。如果你愿意，你也可以使用 0 作为 *mut，但是这看起来太乱了。

use std::ptr;

// defns...

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None, tail: ptr::null_mut() }
    }
}

cargo build

warning: field is never used: `head`
 --> src/fifth.rs:4:5
  |
4 |     head: Link<T>,
  |     ^^^^^^^^^^^^^
  |
  = note: #[warn(dead_code)] on by default

warning: field is never used: `tail`
 --> src/fifth.rs:5:5
  |
5 |     tail: *mut Node<T>,
  |     ^^^^^^^^^^^^^^^^^^

warning: field is never used: `elem`
  --> src/fifth.rs:11:5
   |
11 |     elem: T,
   |     ^^^^^^^

warning: field is never used: `head`
  --> src/fifth.rs:12:5
   |
12 |     head: Link<T>,
   |     ^^^^^^^^^^^^^

嘘，编译器，我们很快就会用到它们。

好的，让我们继续写 push。这一次，在我们插入之后，我们不是抓取一个 Option<&mut Node<T>> ，而是直接抓取一个 *mut Node<T> 到 Box 的内部。我们知道我们可以很好地做到这一点，因为 Box 里的东西有一个稳定的地址，即使我们把 Box移来移去。当然，这是不安全的，因为如果我们只是删除 Box，我们将有一个指针指向释放的内存。

如何从普通指针生成原始指针？强制转换！如果一个变量被声明为原始指针，则一个普通引用将强制进入该变量：

let raw_tail: *mut _ = &mut *new_tail;

我们拥有所需的所有信息。我们可以将我们的代码翻译成之前的参考版本：

pub fn push(&mut self, elem: T) {
    let mut new_tail = Box::new(Node {
        elem: elem,
        next: None,
    });

    let raw_tail: *mut _ = &mut *new_tail;

    // .is_null checks for null, equivalent to checking for None
    if !self.tail.is_null() {
        // If the old tail existed, update it to point to the new tail
        self.tail.next = Some(new_tail);
    } else {
        // Otherwise, update the head to point to it
        self.head = Some(new_tail);
    }

    self.tail = raw_tail;
}

> cargo build

error[E0609]: no field `next` on type `*mut fifth::Node<T>`
  --> src/fifth.rs:31:23
   |
31 |             self.tail.next = Some(new_tail);
   |             ----------^^^^
   |             |
   |             help: `self.tail` is a raw pointer; try dereferencing it: `(*self.tail).next`

啊? 我们有一个指向 Node 的指针，为什么我们不能得到下一个字段？

使用原始指针时，Rust有点混蛋。 要访问原始指针的内容，它坚持要求我们手动取消对它们的引用，因为这是一种不安全的操作。 因此，让我们这样做：

*self.tail.next = Some(new_tail);

> cargo build

error[E0609]: no field `next` on type `*mut fifth::Node<T>`
  --> src/fifth.rs:31:23
   |
31 |             *self.tail.next = Some(new_tail);
   |             -----------^^^^
   |             |
   |             help: `self.tail` is a raw pointer; try dereferencing it: `(*self.tail).next`

操作符优先级。

(*self.tail).next = Some(new_tail);

> cargo build

error[E0133]: dereference of raw pointer is unsafe and requires unsafe function or block
  --> src/fifth.rs:31:13
   |
31 |             (*self.tail).next = Some(new_tail);
   |             ^^^^^^^^^^^^^^^^^ dereference of raw pointer
   |
   = note: raw pointers may be NULL, dangling or unaligned; they can violate aliasing rules and cause data races: all of these are undefined behavior

这应该不会这么难。

还记得我说过的Unsafe Rust就像是Safe Rust的FFI语言吗？ 好吧，编译器希望我们明确界定执行此FFI处理的位置。 我们有两个选择。 首先，我们可以将整个函数标记为不安全，在这种情况下，它会变成不安全的Rust函数，并且只能在不安全的上下文中调用。 这不是很好，因为我们希望我们的列表可以安全使用。 其次，我们可以在函数内部编写一个不安全的块，以划定FFI边界。 这声明整体功能是安全的。 让我们做一个：

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;

    // Put the box in the right place, and then grab a reference to its Node
    if !self.tail.is_null() {
        // If the old tail existed, update it to point to the new tail
        unsafe {
            (*self.tail).next = Some(new_tail);
        }
    } else {
        // Otherwise, update the head to point to it
        self.head = Some(new_tail);
    }

    self.tail = raw_tail;
}

> cargo build
warning: field is never used: `elem`
  --> src/fifth.rs:11:5
   |
11 |     elem: T,
   |     ^^^^^^^
   |
   = note: #[warn(dead_code)] on by default

耶！

到目前为止，这是我们唯一必须编写不安全块的地方，这很有趣。 我们到处都是原始指针，这是怎么回事？

事实证明，当涉及到不安全时，Rust是一个庞大的规则书呆子。我们非常合理地希望最大限度地利用 Safe Rust 程序，因为这些程序我们可以更有信心。为了做到这一点，Rust 小心地划出一个不安全的最小表面积。请注意，我们使用原始指针的所有其他地方都在分配它们，或者只是观察它们是否为null。

如果您从未真正取消引用原始指针，那是完全安全的事情。 您只是在读取和写入一个整数！ 唯一真正遇到麻烦的是原始指针是否要取消引用。 因此，Rust说只有操作是不安全的，其他一切都是完全安全的。

超级迂腐但技术上是正确的。

然而，这提出了一个有趣的问题: 尽管我们应该用不安全的块来限定不安全的范围，但它实际上取决于在块之外建立的状态。甚至在功能之外！

这就是我所说的不安全的污点。 一旦在模块中使用不安全，整个模块便会受到不安全的污染。 必须正确编写所有内容，以确保对于不安全的代码保持不变。

这种污染是可控的，因为隐私。在我们的模块之外，我们的所有结构字段都是完全私有的，所以没有其他人可以以任意的方式干扰我们的状态。只要我们公开的 api 没有组合导致糟糕的事情发生，对于外部观察者来说，我们所有的代码都是安全的！事实上，这和 FFI 的案子没什么不同。只要 python 数学库公开了一个安全的接口，就没有人需要关心它是否外壳到 C 中。

无论如何，让我们继续讨论  pop，它几乎是逐字逐句的引用版本:

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
    })
}

我们又看到了另一个安全是有状态的。如果我们不能使这个函数中的尾部指针为空，我们就不会看到任何问题。然而，随后的push调用将开始写入悬垂的尾部！

让我们来测试一下:

#[cfg(test)]
mod test {
    use super::List;
    #[test]
    fn basics() {
        let mut list = List::new();

        // Check empty list behaves right
        assert_eq!(list.pop(), None);

        // Populate list
        list.push(1);
        list.push(2);
        list.push(3);

        // Check normal removal
        assert_eq!(list.pop(), Some(1));
        assert_eq!(list.pop(), Some(2));

        // Push some more just to make sure nothing's corrupted
        list.push(4);
        list.push(5);

        // Check normal removal
        assert_eq!(list.pop(), Some(3));
        assert_eq!(list.pop(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop(), Some(5));
        assert_eq!(list.pop(), None);

        // Check the exhaustion case fixed the pointer right
        list.push(6);
        list.push(7);

        // Check normal removal
        assert_eq!(list.pop(), Some(6));
        assert_eq!(list.pop(), Some(7));
        assert_eq!(list.pop(), None);
    }
}

这只是堆栈测试，但是预期的 pop 结果反过来了。我还在结尾添加了一些额外的步骤，以确保 pop 中的尾指针损坏情况不会发生。

cargo test

     Running target/debug/lists-5c71138492ad4b4a

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. 8 passed; 0 failed; 0 ignored; 0 measured