为什么我对链表的drop的迭代实现仍然会导致堆栈溢出? [英] Why does my iterative implementation of drop for a linked list still cause a stack overflow?

查看:70
本文介绍了为什么我对链表的drop的迭代实现仍然会导致堆栈溢出?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我正在关注 学习Rust用太多的链接列表 来用Rust编写我的第一个程序.我程序更改为:

I am following Learning Rust With Entirely Too Many Linked Lists to write my first program in Rust. I changed the program to:

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中出现了堆栈溢出.是因为RHS中的*self?

Both of my tests are failing with a stack overflow in drop. Is it because of *self in RHS?

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

我的理解是:

  1. 它在self中设置List::Nil.
  2. head中放入self的原始值.
  1. It sets List::Nil in self.
  2. Puts original value of self in 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

推荐答案

每当编写递归(或迭代)代码时,您需要有一个停止条件.您的代码没有,因此它会永远循环.

Whenever you write recursive (or iterative) code, you need to have a stopping condition. Your code doesn't, so it loops forever.

产生问题的 MCVE 始终是一个好的开始:

Producing a MCVE of your problem is always a good start:

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

然后注释代码以查看重复发生的位置:

Then annotate the code to see where it's recurring:

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

这将打印出来

1
2
1
2

因此请删除之后的所有内容:

so delete everything after that:

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

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

Why does this cause infinite recursion? You've defined it so that in order to drop List, you have to create a new List, which in turn needs to be dropped, which creates a new List, which...

添加停止条件:

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

没有更多的无限递归了.

No more infinite recursion.

然后将其扩展回原始位置,然后重试.它适用于此测试用例,但不适用于List::More(Box::new(List::Nil)),因此我们将其缩小:

Then expand back out to the original and try again. It works for this test case, but not for List::More(Box::new(List::Nil)) so we shrink it back:

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

1
2
3
4
1
5
1
2
3
4
1
5

现在的问题是,当我们重新分配head时,需要删除正在覆盖的值,这将再次触发递归.

The problem now is that when we re-assign head, the value we are overwriting needs to be dropped, which triggers the recursion again.

解决此问题很复杂.喜欢,令人惊讶地如此.你准备好了吗?

Fixing this is complicated. Like, surprisingly so. You ready for this?

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

现在有两个停止条件:

  1. Nil
  2. More(Nil)
  1. Nil
  2. More(Nil)

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

In every other case, we iteratively convert the More(x) into a More(Nil), which is handled by the stopping condition. That means that we only have a single depth of recursion: for each value that is dropped when the previous value of head goes out of scope when it is replaced.

使用原始代码:

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,因此它不是自递归的:


In the original tutorial you linked, this isn't a problem because the definition of List::drop doesn't modify self at all so it's not self-recursive:

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的迭代实现仍然会导致堆栈溢出?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆