4.3 破坏

3 分钟阅读

原文链接: https://rust-unofficial.github.io/too-many-lists/fourth-breaking.html

pop_front 应该和 push_front 是同样的基本逻辑，只是反过来。我们来试试：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
pub fn pop_front(&mut self) -> Option<T> {
    // 需要取出旧的 head，确保它是 -2
    self.head.take().map(|old_head| {                         // -1 old
        match old_head.borrow_mut().next.take() {
            Some(new_head) => {                               // -1 new
                // 没有清空链表
                new_head.borrow_mut().prev.take();            // -1 old
                self.head = Some(new_head);                   // +1 new
                // 总计：-2 old, +0 new
            }
            None => {
                // 清空链表
                self.tail.take();                             // -1 old
                // 总计：-2 old,（没有 new）
            }
        }
        old_head.elem
    })
}

1
2
3
4
5
6
7
> cargo build

error[E0609]: no field `elem` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:64:22
   |
64 |             old_head.elem
   |                      ^^^^ unknown field

啊。RefCell。我猜又得 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
6
7
cargo build

error[E0507]: cannot move out of borrowed content
  --> src/fourth.rs:64:13
   |
64 |             old_head.borrow_mut().elem
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot move out of borrowed content

叹气

cannot move out of borrowed content

嗯……看来 Box 真是把我们惯坏了。borrow_mut 只能给我们一个 &mut Node<T>，但我们不能从中移出值！

我们需要某种东西，接受 RefCell<T> 并返回 T。我们来查一下文档，看看有没有类似的东西：

fn into_inner(self) -> T
Consumes the RefCell, returning the wrapped value.

看起来很有希望！

1
old_head.into_inner().elem

1
2
3
4
5
6
7
> cargo build

error[E0507]: cannot move out of an `Rc`
  --> src/fourth.rs:64:13
   |
64 |             old_head.into_inner().elem
   |             ^^^^^^^^ cannot move out of an `Rc`

啊糟了。into_inner 想移出 RefCell，但我们做不到，因为它在 Rc 里。正如我们在上一章看到的，Rc<T> 只允许我们获得其内部数据的共享引用。这很合理，因为引用计数指针的全部意义就在于共享！

这在我们要为引用计数链表实现 Drop 时是个问题，解决方案也一样：Rc::try_unwrap，当引用计数为 1 时移出 Rc 的内容。

1
Rc::try_unwrap(old_head).unwrap().into_inner().elem

Rc::try_unwrap 返回 Result<T, Rc<T>>。Result 基本上是一个泛化的 Option，其中 None 情况会附带数据。在这里，就是你尝试解包的那个 Rc。因为我们不关心失败的情况（如果程序写得正确，它必须成功），我们直接对它调用 unwrap。

总之，来看看下一个编译器错误（面对现实吧，肯定会有）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
> cargo build

error[E0599]: no method named `unwrap` found for type `std::result::Result<std::cell::RefCell<fourth::Node<T>>, std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>>` in the current scope
  --> src/fourth.rs:64:38
   |
64 |             Rc::try_unwrap(old_head).unwrap().into_inner().elem
   |                                      ^^^^^^
   |
   = note: the method `unwrap` exists but the following trait bounds were not satisfied:
           `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>> : std::fmt::Debug`

呃。Result 上的 unwrap 要求你能对错误情况做 debug 打印。RefCell<T> 只在 T 实现了 Debug 时才实现 Debug。Node 没有实现 Debug。

与其那样做，不如用 ok 把 Result 转成 Option 来绕过：

1
Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem

求你了。

1
cargo build

好。

呼

我们做到了。

我们实现了 push 和 pop。

来偷一下旧的 stack 基础测试（因为目前我们只实现了这些）：

 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
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 9 tests
test first::test::basics ... ok
test fourth::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::basics ... ok
test fifth::test::iter_mut ... ok
test third::test::basics ... ok
test second::test::iter ... ok
test third::test::iter ... ok
test second::test::into_iter ... ok

test result: ok. 9 passed; 0 failed; 0 ignored; 0 measured

完美。

现在我们能正确从链表中移除元素了，可以实现 Drop。这次 Drop 在概念上更有趣。之前我们为栈实现 Drop 只是为了避免无界递归，而现在我们必须实现 Drop 才能让任何事情发生。

Rc 无法处理循环引用。如果有环，一切都会让其他一切保持存活。事实证明，双向链表就是一连串小环！所以当我们 drop 链表时，两个端节点的引用计数会减到 1……然后就没有然后了。嗯，如果链表恰好只有一个节点，我们倒没问题。但理想情况下，链表在包含多个元素时也应该正常工作。也许只是我这么认为。

正如我们所见，移除元素有点痛苦。所以对我们来说最简单的做法就是一直 pop 直到得到 None：

1
2
3
4
5
impl<T> Drop for List<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
    }
}

1
cargo build

（其实我们也可以用可变栈这样做，但走捷径是留给理解事物的人！）

我们可以看看实现 push 和 pop 的 _back 版本，但它们只是复制粘贴的工作，我们留到本章后面再说。现在，让我们看看更有趣的东西！

最后修改 August 23, 2026: 更新 (499855b16)