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

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.