thread '<main>' has overflowed its stack in Rust

Question

I got an error trying this code, which realizes a simple linked list.

use std::rc::Rc;
use std::cell::RefCell;

struct Node {
    a : Option<Rc<RefCell<Node>>>,
    value: i32
}

impl Node {
    fn new(value: i32) -> Rc<RefCell<Node>> {
        let node = Node {
            a: None,
            value: value
        };
        Rc::new(RefCell::new(node))
    }
}

fn main() {
    let first  = Node::new(0);
    let mut t = first.clone();
    for i in 1 .. 10_000
    {
        if t.borrow().a.is_none() { 
            t.borrow_mut().a = Some(Node::new(i));
        }
        if t.borrow().a.is_some() {
            t = t.borrow().a.as_ref().unwrap().clone();
        }
    }
    println!("Done!");
}

Why does it happen? Does this mean that Rust is not as safe as positioned?

UPD: If I add this method, the program does not crash.

impl Drop for Node {
    fn drop(&mut self) {
        let mut children = mem::replace(&mut self.a, None);

        loop {
            children = match children {
                Some(mut n) => mem::replace(&mut n.borrow_mut().a, None),
                None => break,
            }
        }
    }
}

But I am not sure that this is the right solution.

Answer 1

For those who come here and are specifically interested in the case where the large struct is a contiguous chunk of memory (instead of a tree of boxes), I found this GitHub issue with further discussion, as well as a solution that worked for me: https://github.com/rust-lang/rust/issues/53827

Vec's method into_boxed_slice() returns a Box<[T]>, and does not overflow the stack for me.

vec![-1; 3000000].into_boxed_slice()

A note of difference with the vec! macro and array expressions from the docs:

This will use clone to duplicate an expression, so one should be careful using this with types having a nonstandard Clone implementation.

There is also the with_capacity() method on Vec, which is shown in the into_boxed_slice() examples.

Answer 2

Does this mean that Rust is not as safe as positioned?

Rust is only safe against certain kinds of failures; specifically memory corrupting crashes, which are documented here: http://doc.rust-lang.org/reference.html#behavior-considered-undefined

Unfortunately there is a tendency to sometimes expect rust to be more robust against certain sorts of failures that are not memory corrupting. Specifically, you should read http://doc.rust-lang.org/reference.html#behavior-considered-undefined.

tldr; In rust, many things can cause a panic. A panic will cause the current thread to halt, performing shutdown operations.

This may superficially appear similar to a memory corrupting crash from other languages, but it is important to understand although it is an application failure, it is not a memory corrupting failure.

For example, you can treat panic's like exceptions by running actions in a different thread and gracefully handling failure when the thread panics (for whatever reason).

In this specific example, you're using up too much memory on the stack.

This simple example will also fail:

fn main() {
  let foo:&mut [i8] = &mut [1i8; 1024 * 1024];
}

(On most rustc; depending on the stack size on that particularly implementation)

I would have thought that moving your allocations to the stack using Box::new() would fix it in this example...

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct Node {
    a : Option<Box<Rc<RefCell<Node>>>>,
    value: i32
}

impl Node {
    fn new(value: i32) -> Box<Rc<RefCell<Node>>> {
        let node = Node {
            a: None,
            value: value
        };
        Box::new(Rc::new(RefCell::new(node)))
    }
}

fn main() {
    let first  = Node::new(0);
    let mut t = first.clone();
    for i in 1 .. 10000
    {
        if t.borrow().a.is_none() {
            t.borrow_mut().a = Some(Node::new(i));
        }
        if t.borrow().a.is_some() {
            let c:Box<Rc<RefCell<Node>>>;
            { c = t.borrow().a.as_ref().unwrap().clone(); }
            t = c;
            println!("{:?}", t);
        }
    }
    println!("Done!");
}

...but it doesn't. I don't really understand why, but hopefully someone else can look at this and post a more authoritative answer about what exactly is causing stack exhaustion in your code.