Rc and tree-like structures

[iablokov]

Let's say I have the following struct where I can keep both children and a parent for a given node:

struct TreeNode
{
    name     : String,
    children : RefCell<Vec<Rc<TreeNode>>>,
    parent   : RefCell<Option<Rc<TreeNode>>>,
}

impl TreeNode
{
    pub fn set_parent(&self, parent: Rc<TreeNode>)
    {
        *self.parent.borrow_mut() = Some(parent);
    }
    
    pub fn add_child(&self, child: Rc<TreeNode>)
    {
        self.children.borrow_mut().push(child.clone());
        child.set_parent( /* create Rc from self? */);
    }
}

When adding a child...

fn main()
{
    let node_x = TreeNode { name : "parent".to_owned(), children : RefCell::new(vec![]), parent : RefCell::new(None) };
    let node_y = TreeNode { name : "child".to_owned(),  children : RefCell::new(vec![]), parent : RefCell::new(None) };

    let node_x = Rc::new(node_x);
    let node_y = Rc::new(node_y);

    node_x.add_child(node_y);
}

... I would like to simultaneously set its new parent (i.e., self). However, Rc pointer can either be cloned from the existing one (i.e., node_x) or created from scratch using Rc::new() that requires passing ownership of self inside add_child.

I believe there is no way to solve this problem with the current design. What other design strategies could be suggested to make this kind of tree/node API working?

[jofas]

@iablokov

pub fn add_child(&self, child: Rc<TreeNode>)

Actually, you can pass self not as reference &self but as Rc<Self>, allowing you to call self.clone() to create a new Rc instance to your parent node you can pass to your child:

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

struct TreeNode {
    name: String,
    children: RefCell<Vec<Rc<TreeNode>>>,
    parent: RefCell<Option<Rc<TreeNode>>>,
}

impl TreeNode {
    pub fn set_parent(&self, parent: Rc<TreeNode>) {
        *self.parent.borrow_mut() = Some(parent);
    }

    pub fn add_child(self: Rc<Self>, child: Rc<TreeNode>) {
        self.children.borrow_mut().push(child.clone());
        child.set_parent(self.clone());
    }
}

fn main() {
    let node_x = TreeNode {
        name: "parent".to_owned(),
        children: RefCell::new(vec![]),
        parent: RefCell::new(None),
    };
    let node_y = TreeNode {
        name: "child".to_owned(),
        children: RefCell::new(vec![]),
        parent: RefCell::new(None),
    };

    let node_x = Rc::new(node_x);
    let node_y = Rc::new(node_y);

    node_x.add_child(node_y);
}

Playground.

_{(I wasn't really aware that you could do this until this recent topic reminded me)}

[iablokov]

Interesting...

However, it will consume node_x. So it doesn't seem to help if want to add more than 1 child.

[H2CO3]

But you can trivially clone the Rc before passing it to the method… (or take an &Rc and clone inside, but that's not idiomatic because it forces the clone.)

[jofas]

Here enhanced versions as H2CO3 described.

Explicit cloning:

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

struct TreeNode {
    name: String,
    children: RefCell<Vec<Rc<TreeNode>>>,
    parent: RefCell<Option<Rc<TreeNode>>>,
}

impl TreeNode {
    pub fn set_parent(&self, parent: Rc<TreeNode>) {
        *self.parent.borrow_mut() = Some(parent);
    }

    pub fn add_child(self: Rc<Self>, child: Rc<TreeNode>) {
        self.children.borrow_mut().push(child.clone());
        child.set_parent(self);
    }
}

fn main() {
    let node_x = TreeNode {
        name: "parent".to_owned(),
        children: RefCell::new(vec![]),
        parent: RefCell::new(None),
    };
    let node_y = TreeNode {
        name: "child".to_owned(),
        children: RefCell::new(vec![]),
        parent: RefCell::new(None),
    };

    let node_x = Rc::new(node_x);
    let node_y = Rc::new(node_y);

    node_x.clone().add_child(node_y.clone());
    node_x.clone().add_child(node_y.clone());
    node_x.clone().add_child(node_y);
    
    assert_eq!(node_x.children.borrow().len(), 3);
}

Playground.

Passing self as &Rc<Self>:

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

struct TreeNode {
    name: String,
    children: RefCell<Vec<Rc<TreeNode>>>,
    parent: RefCell<Option<Rc<TreeNode>>>,
}

impl TreeNode {
    pub fn set_parent(&self, parent: Rc<TreeNode>) {
        *self.parent.borrow_mut() = Some(parent);
    }

    pub fn add_child(self: &Rc<Self>, child: Rc<TreeNode>) {
        self.children.borrow_mut().push(child.clone());
        child.set_parent(self.clone());
    }
}

fn main() {
    let node_x = TreeNode {
        name: "parent".to_owned(),
        children: RefCell::new(vec![]),
        parent: RefCell::new(None),
    };
    let node_y = TreeNode {
        name: "child".to_owned(),
        children: RefCell::new(vec![]),
        parent: RefCell::new(None),
    };

    let node_x = Rc::new(node_x);
    let node_y = Rc::new(node_y);

    node_x.add_child(node_y.clone());
    node_x.add_child(node_y.clone());
    node_x.add_child(node_y);
    
    assert_eq!(node_x.children.borrow().len(), 3);
}

Playground.

[scottmcm]

@iablokov

where I can keep both children and a parent for a given node

Note that parent pointers are fundamentally a bit of a mess for ownership. If you can avoid them, you'll make your life much easier. (And you'll be able to share subtrees as well!)

[SkiFire13]

Note that this will create a cycle between Rcs which you'll have to manually break or it will leak memory (no node of the tree will ever be dropped thus deallocated). To fix this you can use Weak for the parent instead of Option<Rc>

[oooutlk]

@iablokov

struct TreeNode

@jofas

pub fn set_parent

Notice that TreeNode is private while its methods e.g. set_parent() are public. I didn’t get the point here.