Moonbase

I’ve been thinking about the issues inherent in implementing the Palimpsest algorithm in Inkboard. One of the largest is going to be the differences in our data model; in particular, that our document nodes are mutable.

I had considered making XML nodes immutable before (c.f. my next-generation AST design sketch), but that runs counter to the needs and expectations of most of the rest of the codebase. Most code wants to hold a reference that always points to the most recent version of a particular node.

The solution I came up with at the time was a two-layered arrangement: beneath, the immutable trees mentioned; on top, a tree of nodes that simply hold pointers to immutable subtrees representing their current state. You could create new immutable subtrees all you wanted, but the only way to change the state of the top-level nodes was to go through them and let them create new immutable subtrees to represent their own modified state.

It wasn’t possible to take an existing subtree, give it to a mutable node, and say “this is your new state”, since there would be no way to similarly update its child nodes. Which immutable child went to which mutable child was an unanswerable question since the immutable nodes had no identity of their own.

Unfortunately that is precisely the sort of thing a useful Palimpsest implementation would need to do. I realized this morning that there is a relatively easy fix, however. Give the immutable nodes an identity in the form of serial numbers. All immutable nodes representing some version of a node would have the same serial number. Then you could store the serial number in mutable nodes too, and have a way to match them up.

(Why not have a global mapping of serial numbers to mutable nodes? Because storing serial numbers in the mutable nodes would let you have multiple mutable nodes referencing the same serial number—permitting updatable “views” into different versions of the same document. Powerful stuff.)

The associated overhead might not be desirable for general usage, but once I got the XML session stuff squared away it would be possible for Inkboard to create an XML document with a different backend that did this, if it wanted. (I doubt this could be feasibly implemented within the SoC period, however.)

Dave might be able to go ahead and implement a Palimpsest-like model on top of our mutable tree, but at very least he would lack the ability to reference a particular version of a subtree with a single pointer. Also there may be the issue of write conflicts…

So, he could have to settle for a 90% solution that allows the documents to diverge. That may work pretty well, since we can make assumptions based on the normal patterns of document editing to limit the divergence (e.g. append if the referenced prior node for insertion is no longer under the same parent, since we’re usually appending anyway).