Rust borrowed pointers and lifetimes

Question

In my code I have a mutually recursive tree structure which looks something like the following:

enum Child<'r> {
    A(&'r Node<'r>),
    B, 
    C
}

struct Node<'r> {
    children : [&'r Child<'r>,..25]
}

impl <'r>Node<'r> {
    fn new() -> Node {
        Node {
            children : [&B,..25]
        } 
    }
}

but it doesn't compile as-is. What is the best way to modify it to make it do so?

Answer 1

Here is a version where the nodes can be modified from outside the tree, which I presume is what was asked for.

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

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

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


fn main() {
    let first  = Node::new(0);
    let second = Node::new(0);
    let third  = Node::new(0);

    first.borrow_mut().a = Some(second.clone());
    second.borrow_mut().a = Some(third.clone());

    second.borrow_mut().value = 1;
    third.borrow_mut().value = 2;

    println!("Value of second: {}", first.borrow().a.get_ref().borrow().value);
    println!("Value of third: {}",  first.borrow().a.get_ref().borrow().a.get_ref().borrow().value);
}

Rc is a reference counted pointer and allows a single object to have multiple owners. It doesn't allow mutation however, so a RefCell is required which allows runtime checked mutable borrowing. That's why the code uses Rc<RefCell<Node>>. The Option type is used to represent potential children with Option<Rc<RefCell<Node>>>.

Since, the Rc type auto dereferences, it's possible to directly call RefCell methods on it. These are borrow() and borrow_mut() which return a reference and mutable reference to the underlying Node. There also exist try_borrow() and try_borrow_mut() variants which cannot fail.

get_ref() is a method of the Option type which returns a reference to the underlying Rc<RefCell<Node>>. In a real peogram we would probably want to check whether the Option contains anything beforehand.

Why does the original code not work? References &T imply non-ownership, so something else would have to own the Nodes. While it would be possible to build a tree of &Node types, it wouldn't be possible to modify the Nodes outside of the tree because once borrowed, an object cannot be modified by anything else than the borrowing object.