"thread '<main>' has overflowed its stack" 构建大树时

Question

我实现了一个树结构：

use std::collections::VecDeque;
use std::rc::{Rc, Weak};
use std::cell::RefCell;

struct A {
    children: Option<VecDeque<Rc<RefCell<A>>>>
}

// I got thread '<main>' has overflowed its stack
fn main(){
    let mut tree_stack: VecDeque<Rc<RefCell<A>>> = VecDeque::new();

    // when num is 1000, everything works
    for i in 0..100000 {
        tree_stack.push_back(Rc::new(RefCell::new(A {children: None})));
    }

    println!("{:?}", "reach here means we are not out of mem");
    loop {
        if tree_stack.len() == 1 {break;}

        let mut new_tree_node = Rc::new(RefCell::new(A {children: None}));
        let mut tree_node_children: VecDeque<Rc<RefCell<A>>> = VecDeque::new();

        // combine last two nodes to one new node
        match tree_stack.pop_back() {
            Some(x) => {
                tree_node_children.push_front(x);
            },
            None => {}
        } 
        match tree_stack.pop_back() {
            Some(x) => {
                tree_node_children.push_front(x);
            },
            None => {}
        } 

        new_tree_node.borrow_mut().children = Some(tree_node_children);
        tree_stack.push_back(new_tree_node);
    }
}

Playpen link

但是它崩溃了

thread '<main>' has overflowed its stack

我该如何解决？

Answer 1

您遇到的问题是因为您有一个巨大的 linked-list 节点。当删除该列表时，第一个元素首先尝试释放该结构的所有成员。这意味着第二个元素做同样的事情，依此类推，直到列表的末尾。这意味着您将拥有一个与列表中的元素数量成正比的调用堆栈！

这是一个小复制品：

struct A {
    children: Option<Box<A>>
}

fn main() {
    let mut list = A { children: None };

    for _ in 0..1_000_000 {
        list = A { children: Some(Box::new(list)) };
    }
}

下面是您的修复方法：

impl Drop for A {
    fn drop(&mut self) {
        if let Some(mut child) = self.children.take() {
            while let Some(next) = child.children.take() {
                child = next;
            }
        }
    }
}

此代码用迭代代码覆盖了默认的递归删除实现。它将 children 从节点中删除，用终端项 (None) 替换它。然后它允许节点正常下降，但不会有递归调用。

代码有点复杂，因为我们不能掉落自己，所以我们需要做一点two-step舞蹈来忽略第一个项目，然后吃掉所有的children。

另请参阅：

How can I swap in a new value for a field in a mutable reference to a structure?

"thread '<main>' has overflowed its stack" 构建大树时

"thread '<main>' has overflowed its stack" when constructing a large tree

rust