Comment by josephg | Hacker News Reader

Comment by josephg | Hacker News Reader

Parent Full thread

Martin Kleppman has proposed using range deletes for all deletes in automerge[1]. In diamond types (my own CRDT) I'm still on the fence about whether or not this is a good idea.

The downside is if you select & delete two functions, and I concurrently insert a new function in the middle of that range, then the merged result will delete my function. Thats a really bad outcome - but its pretty rare in practice.

A much more common case is, I deleted 2 lines of code and you modify a parameter in one of those function calls. In this case, using range deletes your edits will also be deleted (which is what we want). Using individual deletes, the result will end up with some random junk left behind, in the form of whichever characters I typed.

When we're editing code as plain text, I don't think there's any such thing as perfect here. For asyncronous collaborative editing (like git), I think generating conflict markers & human supervision for merging might be the best answer.

I'd love to see someone make a prototype editor which can do AST-level concurrent editing. That would be super interesting in a bunch of ways - like, you could use the AST to do syntax highlighting in any editor too. But I'm not sure how it'd merge code when the parse tree is invalid - like, if I remove a closing brace (}) early in the function, what happens?

There's a lot of cool ideas in this space. I'm excited to see people explore them as CRDTs get more popular and more mature.

[1] https://github.com/automerge/automerge/issues/401

Makes sense. Ranged deletes might be key to handle rich-text table mutations.

Seph, thanks for showing up. Author here. This write-up is just a generalization I've landed on, while thinking about the nature of another problem: handling block elements in rich text in Peritext - a project you've collaborated with I guess.

Here's the link - https://github.com/inkandswitch/peritext/issues/27

Do throw your thoughts too. I'd be happy pick your brain on this :)

Commented in the github thread :)

> The downside is if you select & delete two functions, and I concurrently insert a new function in the middle of that range, then the merged result will delete my function.

If the document has a syntax tree format, you would get the right thing if you require that range operations are broken into subranges correspond to subtrees.

Let me work this out where I imagine range operations occur as the insertion of a pair of special characters [range-delete-start] and [range-delete-end], so then we can understand results in terms of merging insertions.

Following your example, if the original is:

  f(x) { ... }
  g(x) { ... }

I delete this whole block; broken into subtree operations that becomes

  [range-delete-start]
  f(x) { ... }
  [range-delete-end]
  [range-delete-start]
  g(x) { ... }
  [range-delete-end]

You simultaneously insert a function:

  f(x) { ... }
  [insert-start]
  h(x) { ... }
  [insert-end]
  g(x) { ... }

CRDT rules for the merge are that when an insert operation occurs at the same location the start or end of a range delete the insert is merged to occur outside of the deletion range: the insert range should be placed after an identically-located [range-delete-end] and before an identically-located [range-delete-start]. Then the merged edit is :

  [range-delete-start]
  f(x) { ... }
  [range-delete-end]
  [insert-start]
  h(x) { ... }
  [insert-end]
  [range-delete-start]
  g(x) { ... }
  [range-delete-end]

which simplifies to a result of:

  h(x) { ... }

If you're operating at the AST level, you don't need range deletes to make the merge result work. In my head I'm imagining a document (at the top level) being a list of functions. Deleting two functions is expressed as deleting the AST node for the function definitions from that list. You don't need a range delete operator to do that - you just delete both function subtrees explicitly.

Your example above is maybe a good example why we do want range deletes, among other operations. In my view the problem is matching the semantics of the CRDT library to the semantics of the problem domain. Having more options always makes this easier (but not for the maker of the CRDT library :-p). I would even think that maybe we need CRDTs with programmable semantics along side inserts, deletes, move, range delete, etc (just an idea).

I would love to work on a structural editor for a programming language. Maybe I will start some experiments after my current project. Keep up the good work!

Reply on news.ycombinator.com