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

Question

I implemented a tree struct:

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

But it crashes with

thread '<main>' has overflowed its stack

How do I fix that?

Answer 1

The problem that you are experiencing is because you have a giant linked-list of nodes. When that list is dropped, the first element tries to free all the members of the struct first. That means that the second element does the same, and so on, until the end of the list. This means that you will have a call stack that is proportional to the number of elements in your list!

Here's a small reproduction:

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

And here's how you would fix it:

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

This code overrides the default recursive drop implementation with an iterative one. It rips the children out of the node, replacing it with a terminal item (None). It then allows the node to drop normally, but there will be no recursive calls.

The code is complicated a bit because we can't drop ourselves, so we need to do a little two-step dance to ignore the first item and then eat up all the children.

See also:

• How can I swap in a new value for a field in a mutable reference to a structure?
• How do I move out of a struct field that is an Option?