为什么我对链表的 drop 迭代实现仍然会导致堆栈溢出？

Question

我正在跟随 Learning Rust With Entirely Too Many Linked Lists 用 Rust 编写我的第一个程序。我将程序更改为：

use std::mem;

#[derive(Debug)]
pub enum List {
    Nil,
    More(Box<Node>),
}

#[derive(Debug)]
pub struct Node {
    val: i32,
    next: List
}

impl List {
    pub fn new() -> Self {
        List::Nil
    }

    pub fn insert(&mut self, v : i32) {
        let old_head = mem::replace(&mut *self, List::Nil);
        let new_head = List::More(Box::new(Node { val : v, next: old_head}));
        *self = new_head
    }

    pub fn remove(&mut self) -> Option<i32> {
        match mem::replace(&mut *self, List::Nil) {
            List::Nil => {
                None
            },
            List::More(ref mut boxed_node) => {
                let result = Some(boxed_node.val);
                *self = mem::replace(&mut boxed_node.next, List::Nil);
                result
            }
        }
    }
}

impl Drop for List {
    fn drop(&mut self) {
        let mut head = mem::replace(&mut *self, List::Nil);

        while let List::More(ref mut node) = mem::replace(&mut head, List::Nil) {
            head = mem::replace(&mut node.next, List::Nil);
        }
    }
}

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn basics() {
        let mut list = List::new();
        list.insert(7);
        assert_eq!(Some(7), list.remove());
        assert_eq!(None, list.remove());

        list.insert(1);
        list.insert(2);
        list.insert(3);

        assert_eq!(Some(3), list.remove());
        assert_eq!(Some(2), list.remove());
        assert_eq!(Some(1), list.remove());
        assert_eq!(None, list.remove());
    }

    #[test]
    fn drop_long_list() {
        let mut list = List::new();
        for i in 1..100000 {
            list.insert(i);
        }
    }
}

我的两个测试都因 drop 中的堆栈溢出而失败。是因为*self in RHS?

我不知道 let mut head = mem::replace(&mut *self, List::Nil); 发生了什么。

我的理解是：

在self中设置List::Nil。
将 self 的原始值放入 head。

*self 是不是在做更多的事情？

我也试过这个版本drop:

impl Drop for List {
    fn drop(&mut self) {
        let mut head = mem::replace(self, List::Nil);

        while let List::More(ref mut node) = mem::replace(&mut head, List::Nil) {
            head = mem::replace(&mut node.next, List::Nil);
        }
    }
}

再试一次：

impl Drop for List {
    fn drop(&mut self) {
        while true {
            match self {
                &mut List::Nil => break,
                &mut List::More(ref mut node) => {
                    *self = mem::replace(&mut node.next, List::Nil)
                }
            }
        }
    }
}

error[E0506]: cannot assign to `*self` because it is borrowed
  --> src\list.rs:48:21
   |
47 |                 &mut List::More(ref mut node) => {
   |                                 ------------ borrow of `*self` occurs here
48 |                     *self = mem::replace(&mut node.next, List::Nil)
   |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `*self` occurs here

Answer 1

您遇到堆栈溢出，因为您的 drop 函数是无限递归的。

代码如下：

let mut head = mem::replace(self, List::Nil);

在 head 中存储一个 List 对象，它将在作用域的末尾被删除。这意味着，当您删除时，您创建了一个也需要删除的新列表。重复此操作足够多次，就会出现堆栈溢出。

注意：在您链接的教程中，他们使用let mut cur_link = mem::replace(&mut self.head, Link::Empty)来避免递归。

Answer 2

每当您编写递归（或迭代）代码时，您需要有一个停止条件。您的代码没有，因此它会永远循环。

产生一个 MCVE 你的问题总是一个好的开始：

use std::mem;

#[derive(Debug)]
pub enum List {
    Nil,
    More(Box<List>),
}

impl Drop for List {
    fn drop(&mut self) {
        let mut head = mem::replace(self, List::Nil);

        while let List::More(ref mut node) = mem::replace(&mut head, List::Nil) {
            head = mem::replace(node, List::Nil);
        }
    }
}

#[test]
fn basics() {
    List::Nil;
}

然后注释代码以查看重复出现的位置：

fn drop(&mut self) {
    eprintln!("1");
    let mut head = mem::replace(self, List::Nil);
    eprintln!("2");
    while let List::More(ref mut node) = mem::replace(&mut head, List::Nil) {
        eprintln!("3");
        head = mem::replace(node, List::Nil);
        eprintln!("4");
    }
    eprintln!("5");
}

这打印出来

所以删除之后的所有内容：

fn drop(&mut self) {
    eprintln!("1");
    let mut head = mem::replace(self, List::Nil);
    eprintln!("2");
}

为什么会导致无限递归？您已经定义了它，以便删除 List，您必须创建一个新的 List，而后者又需要被删除，这将创建一个新的 List，它.. .

添加停止条件：

fn drop(&mut self) {
    if let List::Nil = *self { return }

    let mut head = mem::replace(self, List::Nil);

    while let List::More(ref mut node) = mem::replace(&mut head, List::Nil) {
        head = mem::replace(node, List::Nil);
    }
}

不再有无限递归。

然后再扩展回原来的位置再试一次。它适用于这个测试用例，但不适用于 List::More(Box::new(List::Nil)) 所以我们缩小它：

fn drop(&mut self) {
    eprintln!("1");
    if let List::Nil = *self { return }
    eprintln!("2");
    let mut head = mem::replace(&mut *self, List::Nil);
    eprintln!("3");
    while let List::More(ref mut node) = mem::replace(&mut head, List::Nil) {
        eprintln!("4");
        head = mem::replace(node, List::Nil);
        eprintln!("5");
    }
    eprintln!("6");
}

现在的问题是，当我们重新赋值head时，我们覆盖的值需要被丢弃，从而再次触发递归。

修复此问题复杂。就像，令人惊讶的是。你准备好了吗？

impl Drop for List {
    fn drop(&mut self) {
        match *self {
            List::Nil => return,
            List::More(ref more) => {
                if let List::Nil = **more {
                    return;
                }
            }
        }

        let mut head = mem::replace(self, List::Nil);

        while let List::More(ref mut next) = {head} {
            head = mem::replace(next, List::Nil);
        }
    }
}

现在有两个停止条件：

Nil
More(Nil)

在所有其他情况下，我们迭代地将 More(x) 转换为 More(Nil)，这是由停止条件处理的。这意味着我们只有一个递归深度：对于每个值，当 head 的前一个值在被替换时超出范围时被丢弃。

对于您的原始代码：

impl Drop for List {
    fn drop(&mut self) {
        match *self {
            List::Nil => return,
            List::More(ref more) => {
                if let List::Nil = more.next {
                    return;
                }
            }
        }

        let mut head = mem::replace(self, List::Nil);

        while let List::More(ref mut node) = {head} {
            head = mem::replace(&mut node.next, List::Nil);
        }
    }
}

在您链接的原始教程中，这不是问题，因为 List::drop 的定义根本不会修改 self，因此它不是自递归的：

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

为什么我对链表的 drop 迭代实现仍然会导致堆栈溢出？

Why does my iterative implementation of drop for a linked list still cause a stack overflow?

stack-overflow

list

rust