# 基础

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

在我们这么做之前：

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

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

```rust
> 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，但是这看起来太乱了。

```rust
use std::ptr;

// defns...

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

```rust
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，我们将有一个指针指向释放的内存。

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

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

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

```rust
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;
}

```

```rust
> 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有点混蛋。 要访问原始指针的内容，它坚持要求我们手动取消对它们的引用，因为这是一种不安全的操作。 因此，让我们这样做：

```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`
```

操作符优先级。

```rust
(*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边界。 这声明整体功能是安全的。 让我们做一个：

```rust
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;
}
```

```rust
> 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，它几乎是逐字逐句的引用版本:

```rust
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调用将开始写入悬垂的尾部！

让我们来测试一下:

```rust
#[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

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://chapin666.gitbook.io/too-many-list-zh/yi-ge-bu-an-quan-de-dui-lie/ji-chu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.