How to create a completely immutable tree hierarchy? Construction chicken and egg

Question

I like to make data classes immutable to make concurrent programming easier. But making a completely immutable hierarchy seems problematic.

Consider this simple tree class:

public class SOTree {     private final Set<SOTree> children = new HashSet<>();     private SOTree parent;      public SOTree(SOTree parent) {         this.parent = parent;     }      public SOTree(Set<SOTree> children) {         for (SOTree next : children)             children.add(next);     }       public Set<SOTree> getChildren() {         return Collections.unmodifiableSet(children);     }      public SOTree getParent() {         return parent;     } } 

Now, if I want to create a hierarchy of these, when I construct it, either the parent has to exist before the current node, or the children have to exist first.

    SOTree root = new SOTree((SOTree)null);     Set<SOTree> children = createChildrenSomehow(root);     //how to add children now?  or children to the children? 

or

    Set<SOTree> children = createChildrenSomehow(null);     SOTree root = new SOTree(children);     //how to set parent on children? 

Without forcing this to be a singly linked tree, is there any clever way to construct such a tree and still have all the nodes completely immutable?

Answer 1

Eric Lippert recently blogged about this problem. See his blog post Persistence, Facades and Roslyn's Red-Green Trees. Here's an excerpt:

We actually do the impossible by keeping two parse trees. The "green" tree is immutable, persistent, has no parent references, is built "bottom-up", and every node tracks its width but not its absolute position. When an edit happens we rebuild only the portions of the green tree that were affected by the edit, which is typically about O(log n) of the total parse nodes in the tree.

The "red" tree is an immutable facade that is built around the green tree; it is built "top-down" on demand and thrown away on every edit. It computes parent references by manufacturing them on demand as you descend through the tree from the top. It manufactures absolute positions by computing them from the widths, again, as you descend.

Answer 2

Two thoughts:

1. Use some sort of tree factory. You could describe the tree using mutable structures, then have a factory that would assemble an immutable tree. Internally, the factory would have access to the fields of the different nodes and so could rewire internal pointers as necessary, but the produced tree would be immutable.

2. Build an immutable tree wrapper around a mutable tree. That is, have the tree construction use mutable nodes, but then build a wrapper class that then provides an immutable view of the tree. This is similar to (1), but doesn't have an explicit factory.

Hope this helps!