3 ms·

In xi, there are two issues. One is the cost of the CRDT representation, the other is whether it accurately represents what you're trying to do. Classical imple

In xi, there are two issues. One is the cost of the CRDT representation, the other is whether it accurately represents what you're trying to do. Classical implementations of CRDT use a heavyweight node per character in the text, each with its own unique and permanent id. In my research in xi, it became clear to me that more compressed representations are possible, and the xi CRDT is one such: it is an "op" object per edit, but the string itself is just a string. Lately there has been other work pursuing those compressed representations: Chronofold, I think Martin Kleppmann's automerge has some memory-efficiency work, and there are others. But at least in the context of xi, this is not where things went wrong. As I've written about (and the author was kind enough to link), it's because CRDT merges aren't a good fit for the problems a code editor is trying to solve, particularly when the "collaborators" are automated processes such as language servers. In human collaborative editing, it's important to preserve text that's being entered, even in the face of conflict. But when a peer is an automated service, it's much better to drop the edit on the floor and recompute. I'm simplifying here, as it depends on the service - some are history-insensitive, some are sensitive to a small window of history (in the case of automatically inserting indentation, etc), and (speculative) other services may be sensitive to more history. In addition, the CRDT constrains the data model considerably. In other words, it's unfortunately not a clean abstraction where you can easily add higher level layers on top of the CRDT, but you always have to design those with the CRDT in mind (ie, everything still has to be a monotonic semi-lattice). So, as with everything else, it's a tradeoff, and it's a question of weighing the pros and cons. I'm glad to see work being done to improve CRDT, but even with a very efficient representation and solid algorithms, the problems with CRDT would be enough for me not to use them in a code editor.

zzz61831 6y ago
> it's because CRDT merges aren't a good fit for the problems a code editor is trying to solve I think you are not talking about CRDTs here. CRDTs are a pretty good fit for distributed systems that share state, which is what collaborative editing is underneath. It's just that semantically completely automatic conflict resolution is incompatible with human collaborative editing, which is pretty obvious, but for some reason plenty of research goes into trying to do just that.
- raphlinus 6y ago
  I was trying to use a CRDT to share state between the GUI editor and the language server process. My attempt didn't work well, for reasons I've written about. I have no doubt it can be made to work, and the research towards that might be interesting.
kevinjahns 6y ago
Hi Raph, your GitHub comment about "Why CRDT didn't work out as well for collaborative editing in xi-editor" [1] was sent to me several times as an argument not to use CRDTs. I agree with you that CRDTs might be too complex for the way the xi-editor used it (although I loved the idea, and appreciate that you tried it). But the title of the Hackernews post tells a very different story. So many people misunderstood WHY CRDTs didn't work out well for the xi-editor. At the very least, my article shows that CRDTs are well suited for shared editing. You brought up some valid points why CRDTs are not well suited for having different editor components communicate with each other (language server, indentation, syntax highlighting, ..). Although, I still think there is a lot of merit in using CRDTs as a data model for a code editor (or any kind of editor). Not for editor components concurrently modifying the editor model, but just as an collaboration-aware model. • Marijn considered a CRDT as a data model for CodeMirror 6 because positions in collaborative software can be better expressed [2]. A position in the Yjs model is simply a reference to the unique id of the character. • Even without collaboration, Yjs servers as a highly efficient selective Undo/Redo manager. Each item on the Undo/Redo stack just consumes a couple of bytes. Furthermore, most existing implementations don't support selective Undo/Redo. This is free when using Yjs as a data model. • Some components can work in the background and annotate the CRDT model (not manipulate it). For example, a code analyzer that runs on a remote computer could annotate a function and notify the user about potential problems. The position of the annotation will still be valid if users modify the model concurrently in a distributed environment. [1]: https://news.ycombinator.com/item?id=19886883 https://news.ycombinator.com/item?id=19886883 [2]: https://marijnhaverbeke.nl/blog/collaborative-editing-cm.html https://marijnhaverbeke.nl/blog/collaborative-editing-cm.htm...
- raphlinus 6y ago
  I'm not sure what to add. I definitely agree that CRDT is viable for collaborative editing, I'm just saying people need to be aware of the issues. Regarding position and undo, these are problems that can also be solved just fine using OT techniques, and are (imho) simpler when there is a central authority that can order all revisions into a globally consistent sequence. I think it's inevitable that people are going to misunderstand arguments, given the complexity of the underlying space and the paucity of good learning resources. So thanks for your writeup, it adds to the discussion.
microcolonel 6y ago
I think it would be interesting to approach this from the language mode side, insisting on structured buffers (syntax tree with rope leaves†). It is pretty rare that two clients (mode and user window, or two user windows) would lock a single large leaf, so you could just choose an authority/leader for each subtree, and have the leader explicitly and synchronously sequence the peon clients' edits. Then, working backward from language specific modes, I could imagine a way to generalize this to free form text, by negotiating the split points with the authority (or not at all, in the case of free text being edited by one client). Though I guess for now just making these completely synchronous across the whole buffer, as you have, is fine in most cases, and already a significant improvement vs some editors (looking at you, beloved Emacs). † i.e. for js, you could imagine a tree of statements/blocks containing expressions (maybe incl. operator precedence); for Clojure you could imagine a plain syntax tree, for JSON you could imagine it being the literal JSON data (plus whitespace metadata).

zzz61831 6y ago

> it's because CRDT merges aren't a good fit for the problems a code editor is trying to solve I think you are not talking about CRDTs here. CRDTs are a pretty good fit for distributed systems that share state, which is what collaborative editing is underneath. It's just that semantically completely automatic conflict resolution is incompatible with human collaborative editing, which is pretty obvious, but for some reason plenty of research goes into trying to do just that.

raphlinus 6y ago
I was trying to use a CRDT to share state between the GUI editor and the language server process. My attempt didn't work well, for reasons I've written about. I have no doubt it can be made to work, and the research towards that might be interesting.

kevinjahns 6y ago

Hi Raph, your GitHub comment about "Why CRDT didn't work out as well for collaborative editing in xi-editor" [1] was sent to me several times as an argument not to use CRDTs. I agree with you that CRDTs might be too complex for the way the xi-editor used it (although I loved the idea, and appreciate that you tried it). But the title of the Hackernews post tells a very different story. So many people misunderstood WHY CRDTs didn't work out well for the xi-editor. At the very least, my article shows that CRDTs are well suited for shared editing. You brought up some valid points why CRDTs are not well suited for having different editor components communicate with each other (language server, indentation, syntax highlighting, ..). Although, I still think there is a lot of merit in using CRDTs as a data model for a code editor (or any kind of editor). Not for editor components concurrently modifying the editor model, but just as an collaboration-aware model. • Marijn considered a CRDT as a data model for CodeMirror 6 because positions in collaborative software can be better expressed [2]. A position in the Yjs model is simply a reference to the unique id of the character. • Even without collaboration, Yjs servers as a highly efficient selective Undo/Redo manager. Each item on the Undo/Redo stack just consumes a couple of bytes. Furthermore, most existing implementations don't support selective Undo/Redo. This is free when using Yjs as a data model. • Some components can work in the background and annotate the CRDT model (not manipulate it). For example, a code analyzer that runs on a remote computer could annotate a function and notify the user about potential problems. The position of the annotation will still be valid if users modify the model concurrently in a distributed environment. [1]: https://news.ycombinator.com/item?id=19886883 https://news.ycombinator.com/item?id=19886883 [2]: https://marijnhaverbeke.nl/blog/collaborative-editing-cm.html https://marijnhaverbeke.nl/blog/collaborative-editing-cm.htm...

raphlinus 6y ago
I'm not sure what to add. I definitely agree that CRDT is viable for collaborative editing, I'm just saying people need to be aware of the issues. Regarding position and undo, these are problems that can also be solved just fine using OT techniques, and are (imho) simpler when there is a central authority that can order all revisions into a globally consistent sequence. I think it's inevitable that people are going to misunderstand arguments, given the complexity of the underlying space and the paucity of good learning resources. So thanks for your writeup, it adds to the discussion.

microcolonel 6y ago

I think it would be interesting to approach this from the language mode side, insisting on structured buffers (syntax tree with rope leaves†). It is pretty rare that two clients (mode and user window, or two user windows) would lock a single large leaf, so you could just choose an authority/leader for each subtree, and have the leader explicitly and synchronously sequence the peon clients' edits. Then, working backward from language specific modes, I could imagine a way to generalize this to free form text, by negotiating the split points with the authority (or not at all, in the case of free text being edited by one client). Though I guess for now just making these completely synchronous across the whole buffer, as you have, is fine in most cases, and already a significant improvement vs some editors (looking at you, beloved Emacs). † i.e. for js, you could imagine a tree of statements/blocks containing expressions (maybe incl. operator precedence); for Clojure you could imagine a plain syntax tree, for JSON you could imagine it being the literal JSON data (plus whitespace metadata).