Growing a Tree without interior mutability

[balls]

For my project, χrust, I need to create a fully navigable and mutable tree.

By 'fully navigable' I mean parent <-> child traversals, as well as traversing siblings.

By 'mutable' I mean that the tree must be created (by parsing a specification such as JSON or XML, so I don't know the structure ahead of time), and then there is a phase where nodes may be added or removed from the tree, for example removing nodes that only contain whitespace. The tree doesn't have to be fully navigable during this phase: just depth-first traversal. After that phase, the tree can be made fully navigable but read-only.

Now, I've found a data structure that supports this use-case uses Weak references:

  parent: Option<Weak<Node>>,
  children: Vec<Rc<Node>>,
  data: usize,
}

However, I can't work out how to create the tree structure without using interior mutability. I want to avoid interior mutability so that the last phase, read-only navigation, doesn't have a run-time penalty.

All my attempts to create the tree, without interior mutability, either run into borrow problems at compile-time, or fail at run-time in the get_mut function.

One example:

struct Node {
    parent: Option<Weak<Node>>,
    children: Vec<Rc<Node>>,
    data: usize,
}

impl Node {
    fn new(data: usize) -> Rc<Node> {
	Rc::new(Node{parent: None, children: vec![], data})
    }
}

trait NodeOps {
    fn add_child(&mut self, n: &mut Rc<Node>);
}

impl NodeOps for Rc<Node> {
    fn add_child(&mut self, n: &mut Rc<Node>) {
	match Rc::get_mut(n) {
	    Some(m) => {
		m.parent = Some(Rc::downgrade(self))
	    }
	    None => panic!("cannot get_mut child")
	}
        // get_mut of self fails because there is 1 strong reference and 1 weak reference
	match Rc::get_mut(self) {
	    Some(m) => {
		m.children.push(n.clone())
	    }
	    None => panic!("cannot get_mut parent")
	}
    }
}

fn main() {
    let mut top = Node::new(1);
    top.add_child(&mut Node::new(2));
    println!("all good");
}

I've tried creating the child first, and then hooking it up to the parent. I've also tried creating children first, and then subsequently adding the Weak parent pointers. They all fail due to the same problem of not being able to get_mut something that already has Weak pointers to it.

So how can I create the tree without resorting to interior mutability?

Regards,
Steve Ball

[Coding-Badly]

Is it okay to transform the tree to a read-only structure when the mutating is finished?

[balls]

Hi,

Yes, that would be fine.

Once the tree has completed it’s build/modify phase it can be made read-only and fully navigable.

Cheers,
Steve Ball

[Hyeonu]

This kind of task can be a lot easier if you can eliminate the parent pointer and replace Rc with Box. You may also need to manage additional stacks off-struct to iterate/backtrack data. I don't know your full requirements and not sure it's possible at all, but if it's not fundamentally impossible why don't you try it?

[riking]

If Arc::make_cyclic doesn't solve your use case, then you absolutely need Cells during the build phase.

[balls]

I can't find Arc::make_cycle in the doco. Can you provide a reference, or more info?

[riking]

Misspelled it, new_cyclic:

Arc in std::sync - Rust

[balls]

Not having the parent pointer would absolutely make everything easier, but I'm implementing an XPath processor and navigating to the parent (and ancestors) is a fundamental feature.

I will try Box...

[zrk]

Just to give a direction, would the following be possible for you:

struct Tree<T> {
    nodes: Vec<Node<T>>,
}

type NodeIndex = usize; // an index in the `nodes` vector of a tree

struct Node<T> {
    data: T,
    parent: Option<NodeIndex>,
}

impl<T> Tree<T> {
    fn root_index(&self) -> NodeIndex {
        0
    }

    fn node(&self, index: NodeIndex) -> Option<&Node> {
        nodes.get(index)
    }

    fn add(&mut self, data: T, parent: Option<NodeIndex>) -> NodeIndex {
        let next_index = nodes.len();
        nodes.push(Node { data, parent });
        next_index
    }
}

The penalty of storing indexes and of having to bound check in the vector for each get is probably far outweight by the fact that the nodes are stores inline in the tree (better locality and way less allocations)

[H2CO3]

@balls

However, I can't work out how to create the tree structure without using interior mutability

You can't, pretty much by definition, if you want to stick with the current approach. You are trying to mutate nodes while there are outstanding references to them; this requires interior mutability, period. (Not even Rc::new_cyclic() can help here, since after the addition of the first child, the parent is always referenced by at least one additional Weak.)

What you could do is build the tree without the parent links first, and then build the parent links from the bottom up using Rc::new_cyclic(): Playground.

#[derive(Clone, PartialEq, Eq, Hash, Debug)]
struct Node {
    children: Vec<Node>,
    data: usize,
}

#[derive(Clone, Debug)]
struct RcNode {
    data: usize,
    parent: Weak<RcNode>,
    children: Vec<Rc<RcNode>>,
}

impl RcNode {
    fn from_node(node: Node, parent: Weak<RcNode>) -> Rc<Self> {
        Rc::new_cyclic(|weak_self| {
            let data = node.data;
            let children: Vec<_> = node.children
                .into_iter()
                .map(|child| {
                    RcNode::from_node(child, weak_self.clone())
                })
                .collect();
            
            RcNode { data, parent, children }
        })
    }
}

[balls]

I've looked at Rc::new_cyclic. It gives T a Weak pointer to itself. I guess I'm missing how you would use that to create the parent-child relationship.

If I have a parent Node and I'm creating the child node, then new_cyclic gives me a Weak pointer to the child-being-created, when I want a Weak pointer to the parent.

[H2CO3]

My answer above shows you exactly how. You have to use recursion in order to get to the parents before their children.

[balls]

Thanks! That looks like it will work.

My project is working in two phases anyway: work out what the tree looks like by parsing the specification (JSON, XML, whatever), and then constructing the final, navigable tree. I'll just do the mutating bits in the first phase, and then use this pattern to construct the fully navigable tree.

[Michael-F-Bryan]

Have you considered avoiding Rc and using indices/IDs. Maybe something like this:

#[derive(Copy, Clone)]
struct NodeId(usize);

struct Node {
  parent: Option<NodeId>,
  children: Vec<NodeId>,
}

struct Tree {
  nodes: Vec<Node>,
}

impl Tree {
  fn push_node(&mut self, node: Node) -> NodeId {
    let id = self.nodes.len();
    self.nodes.push(node);
    NodeId(id)
  }

  fn get_parent(&self, node: &Node) -> Option<&Node> {
    node.parent.and_then(|id| &self[id])
  }
}

impl Index<NodeId> for Tree {
  type Output = Node;
  fn index(&self, index: NodeId) -> &Node { &self.nodes[index.0] }
}
impl IndexMut<NodeId> for Tree {
  fn index_mut(&mut self, index: NodeId) -> &mut Node { &mut self.nodes[index.0] }  
}

By using indices instead of cyclic Rcs you can avoid the Rc::new_cyclic() dance and update a node directly (e.g. tree[id].children.push(...)). You'll naturally control mutability at compile time because all node access goes through the Tree.

Otherwise, you may want to look into crates like petgraph which give you nice ways to construct and traverse a graph.

[balls]

Yes, I have used petgraph and Arena Allocators (indices).

A graph approach requires interior mutability. The result is at least an order of magnitude slower.

Arena Allocators have a few disadvantages. The first is that it is difficult to release memory. The second is that you need to have a reference to the arena as well as the index so the API is cumbersome. I got everything working this way, but when I went to get my code working in wasm this approach fell apart.