Where is the CRDT for syntax trees
I was just talking about this problem yesterday (only to say that it is a problem. I don’t have any solutions).<p>I was thinking in the context of a pijul&#x2F;categorical theory of patches model rather than a CRDT that resolves conflicts deterministically (in the pijul model all merges are successful and well-behaved in that the order of mergin doesn’t matter but your data structure may contain representations of merge conflicts).<p>Fundamentally, I think the problem is that for a good AST model, you want to be able to handle transformations of the following forms:<p><pre><code>  e &lt;-&gt; (e)
  if(e) {f; g} &lt;- if(e) f -&gt; if(e) {h; f}
  a (b c) d &lt;-&gt; a b c d
  (a b) (c d) &lt;-&gt; (a b c d)
</code></pre>
The second line is meant to ask: how would you merge people independently making the middle-to-left and middle-to-right changes with your CRDT. I would like to point out particularly the changes of nesting depth and the merging and splitting of subsequences.<p>Let me briefly describe the pijul&#x2F;CToP model. You start with a simple model of files: each file is a totally ordered set of lines, and a model of patches: a patch is an injection taking the lines of one file to equal lines in another file (i.e. it isn’t changing the contents of the line) and furthermore it is increasing which means the relative order is maintained. New lines are points not in the image of the function and deleted lines are represented by pseudo-lines in the new file with a “deleted” tag. This then forms a category with possible files being the objects and patches the morphisms. You then do some magic to figure out how to add all push outs to the category. Push outs correspond to merges (more formally, the push out of the span B &lt;-f- A -g-&gt; C is an object P with morphisms p: B-&gt;P, q: C-&gt;P such that the compositions fp and gq are equal and the universal property that for any other object Q and morphisms rs satisfying the same properties there is a unique morphism u: P-&gt;Q such that fpu = fr = gs = gqu, which in our case means that the merge is fair in the sense that it hasn’t accidentally resolved a conflict that was ambiguous). The result is a model where files are <i>partially</i> ordered sets of lines and patches are just (strictly) increasing functions. If two lines do not have an order relative to each other, that is the representation of a merge conflict.<p>I don’t have a good model for how that sort of thinking could extend to ASTs. Possibly an OT-in-CRDT model could cope with Emacs paredit style transformations of the tree better than this. I’m also unconvinced that solving tables would solve ASTs or vice versa. The constraints on tables feel different to me (no nesting but global constraints on the length of each row or column. Maybe allowing irregular tables where some cells are merged makes it harder). And a regular table feels like it could better fit into a set-with-extra-structure model (like total orders for each row and column or something somehow like that).<p>Anyway, I’ll be curious to see if someone ever comes up with a really good model to this and, if so, how heuristic-heavy it needs to be (either in the merging or the choice of diff representation) to get good results.