为什么我对链表的drop的迭代实现仍然会导致堆栈溢出? [英] Why does my iterative implementation of drop for a linked list still cause a stack overflow?
问题描述
我正在关注 学习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);
发生了什么.
我的理解是:
- 它在
self
中设置List::Nil
. - 在
head
中放入self
的原始值.
- It sets
List::Nil
inself
. - Puts original value of
self
inhead
.
*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);
}
}
}
现在有两个停止条件:
-
Nil
-
More(Nil)
Nil
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屋!