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.

Solution 1

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.

Solution 2

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.

Comments

[usr1234567]

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

[Shepmaster]

Does this mean that Rust is not as safe as positioned? - Please review what safety means in the context of Rust. In this case, "safety" does not mean that a program cannot abort.

[Shepmaster]

"about what exactly is causing stack exhaustion in your code" - that should be explained by the duplicate question.

[Doug]

@Shepmaster personally I still don't understand the answer in the other question. If I have a Box<T> and it gets dropped, it recursively performs drops on all the child elements, so it's not possible ever drop a large graph structure in rust because it'll overflow in the recursive calls? That can't be right?

[Doug]

@Shepmaster ...but you do seem to be right. If you forget(t); it works fine.

[Shepmaster]

It is possible, you just can't use the naïve built-in recursive Drop implementation. That's why the linked question shows an iterative version that drops all the children using a fixed depth of function calls.

[Lilian A. Moraru]

Why the complex example. Here is a short 1 liner on Rust Playground: is.gd/zJ7UNi . But this is one of those good segfaults :), that doesn't corrupt your memory.

[brundolf]

I am actually more interested in @Doug's case, where the offending structure is a single large array that's been Box'ed. Does anyone have insight into why the Box doesn't work there?

[Ekrem Dinçel]

Please update the link: doc.rust-lang.org/reference/behavior-considered-undefined.ht‌​ml