Rust crash when dropping recursive structure

Defining a recursive data structure in Rust is simple,

enum Recursive {
    Node(Box<Recursive>),
    End,
}

Making an instance is also simple

fn main() {
    let mut node: Recursive = Recursive::End;
    for _ in 0..10_000_000 {
        node = Recursive::Node(Box::new(node));
    }
    println!("Hello!");
    std::process::exit(0); // note this
}

And just like that, a recursive structure ten million nodes deep has been created; the program prints “Hello!” and exits successfully. If std::process:exit(0) is removed though, the result is

Hello!

thread 'main' has overflowed its stack
fatal runtime error: stack overflow
Aborted (core dumped)

The message “Hello!” still prints, which indicates that the crash happens after creating the structure. In this case it’s fairly clear that the println is not responsible for the crash, but no code follows it, making this an implicit crash.

Debugger time. Whipping up LLDB, we see that the stack overflow occurs in the following function

; Symbol: core::ptr::drop_in_place<alloc::boxed::Box<get_size::Recursive>>

And the call stack is filled with

...
core::ptr::drop_in_place<get_size::Recursive> (@core::ptr::drop_in_place<get_size::Recursive>:15)
core::ptr::drop_in_place<alloc::boxed::Box<get_size::Recursive>> (@core::ptr::drop_in_place<alloc::boxed::Box<get_size::Recursive>>:8)
...

Deallocation, or dropping in Rust is mostly implicit and happens automatically at the end of a scope. The structure is implicitly dropped, and given that dropping is recursive, the the call stack is flooded. Evidently, ten million calls is enough to overflow the stack.

To further verify this theory, we can manually drop the structure, printing messages before and after the drop.

println!("before Drop");
stdout().flush().unwrap(); // flush so output is not lost in any crash
std::mem::drop(node);
println!("after Drop");
stdout().flush().unwrap();

And sure enough, “after drop” is never printed.

before Drop

thread 'main' has overflowed its stack
fatal runtime error: stack overflow
Aborted (core dumped)

Drops crashing Rust programs known issue, but it seems to have gone stale.

It should be possible to create an implementation of the Drop trait which operates non recursively. I spent a good while trying to get this to work but wasn’t able to.

In the example above, I created a structure ten million layers deep. A recursive structure like this will start to crash a Rust program (at least on my computer) around 300k layers.

Overall, I don’t consider this a major issue in Rust, but rather something to keep in mind.