[HN Gopher] Where is the CRDT for syntax trees
___________________________________________________________________
Where is the CRDT for syntax trees
Author : lewisjoe
Score : 76 points
Date : 2021-12-03 19:09 UTC (3 hours ago)
(HTM) web link (writer.zohopublic.com)
(TXT) w3m dump (writer.zohopublic.com)
| thomasikzelf wrote:
| We are almost there, for lists and structs there are CDRT's but a
| move operation across the data structure is missing. Martin
| Kleppman (from automerge) talks about this in his talk "CRDTs:
| the hard parts"[0].
|
| I also think a range move or range delete is missing from many of
| these algorithms. A submission here on HN did implement a range
| delete on rich text (but I forgot what the name was).
|
| [0]: https://www.youtube.com/watch?v=x7drE24geUw
|
| EDIT: Ah actually Peritext (which you linked to) was the article
| I was thinking of. I think the range delete would be useful for
| regular lists as well.
| pshc wrote:
| Dear zohopublic.com: please use real <a> anchor tags for
| hyperlinks instead of restyled <span>s, thank you
| awinter-py wrote:
| critical for version control, esp if you believe git history is
| important for long-term software maintainability -- smarter
| transplantation tracking leads to history 'surviving for longer'
| even as things jump context
| blueprint wrote:
| what if automerge added a generalization of the 'Text' object's
| features like 'insertAt' etc which reflect the set of operations
| a programmer does in changing an AST during development?
| WhatIsDukkha wrote:
| I ask myself -
|
| "Why is it that almost all programming environments work in plain
| text buffers and not syntax trees?" (there are several strong
| answers to this)
|
| Adding a crdt on top of that...
|
| But I'll go have a noodle about what this would be good for
| anyway, thanks :)
| nawgz wrote:
| There is this really beautiful algorithm implemented behind
| really oldschool JS that I have seen used a couple times: WebGME.
| https://github.com/webgme/webgme
|
| It is a Model-Based-Systems-Engineering tool, as far as I can
| tell, and it lets you create "metamodels" (SysML diagrams / rules
| essentially) and then collaboratively author some model graph,
| giving you a "commit" for every action, a version history, a git-
| like branching and merging model, and more.
|
| The collaborative aspect is pretty strong in their own UI, I've
| tried to build my own and couldn't get it as easily, but I guess
| my question is: has anyone ever used this tool as well?
| dan-robertson wrote:
| I was just talking about this problem yesterday (only to say that
| it is a problem. I don't have any solutions).
|
| I was thinking in the context of a pijul/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).
|
| Fundamentally, I think the problem is that for a good AST model,
| you want to be able to handle transformations of the following
| forms: e <-> (e) if(e) {f; g} <- if(e) f ->
| if(e) {h; f} a (b c) d <-> a b c d (a b) (c d) <-> (a
| b c d)
|
| 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.
|
| Let me briefly describe the pijul/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 <-f- A -g-> C is an object P with morphisms p: B->P,
| q: C->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->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 _partially_ 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.
|
| 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).
|
| 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.
| octopoc wrote:
| Sounds similar to what Semantic Merge[1] does. Of course it would
| also have to handle syntax errors. For that it could fall back to
| the current crop of text CRDTs.
|
| [1] https://www.semanticmerge.com/
| dnautics wrote:
| We _just_ got CRDTs for generic textual documents! yeesh.
| Patience!
|
| code has generic textual components -- like comments -- _plus_
| tree-like elements -- so it 's arguably more complex.
| Furthermore, one expects automatically merging conflicting
| content to often have to be resolved because even a merge + a
| sophisticated node-based merging strategy will fail to capture
| effectful intents. However, i am excited to see tooling where,
| for example competing merges get run through a trichotomy (A
| only, B only, A + B) to see which branch satisfies the most
| number of tests... And then suggests the resolution accordingly.
| rackjack wrote:
| In terms of generic textual documents, do you have a link? The
| only thing that comes to mind is Pijul:
|
| https://pijul.org/
|
| I also found peritext:
|
| https://www.inkandswitch.com/peritext/
| dnautics wrote:
| oh I think peritext is "automerge" with formatting? which is
| referenced by OP. OP calls it a "json-based CRDT", which is
| _true_ for automerge, but that description may be confusing:
| JSON is the "storage/(transport?) datastructure", the
| "materialized datastructure" for automerge is plain text.
| Note that one of the creators of peritext (martin kleppmann)
| is also creator of automerge.
| ath92 wrote:
| There's also yjs:
|
| https://github.com/yjs/yjs
| LAC-Tech wrote:
| We just got CRDTs for generic textual documents! yeesh.
| Patience!
|
| Really? Link?
| dnautics wrote:
| automerge? it's in OP
___________________________________________________________________
(page generated 2021-12-03 23:00 UTC)