Storing a DOM Tree in Rust

short version:

What data structure would you use to store a DOM Tree in Rust ?

long version

  1. Yes, it is guaranteed that there are no loops. Yes, it’s guaranteed that it is directed and acyclic. Yes, it’s guaranteed to be a TREE rather than merely a DAG.

  2. If all we wanted to do was to store a purely functional tree, we can do something like

pub enum TreeNode {
  Div(Vec<TreeNode>),
  Span(Vec<TreeNode>),
  Br(),
  Img(src: String, width: u32, height: u32),
 ...
}

But the problem wit this approach is that it is hard to get a “pointer to that location” – i.e. suppose we had opts for:

delete all subtree starting at this node
swap subtres at node1 and node2

… basically, in a “purely functional” approach, it is messy to capture the notion of “that node”

  1. Now, back to the original question. In Rust, what is the right data structure to use?

A simple solution to this problem is Rc. Once you put a node into Rc, you can get another strong (Rc) or weak (Weak) reference to the same object. Nodes will store Rc for each of their children. The nodes can also have a Weak reference to their parent nodes for easier navigation.