Why CRDT didn't work out as well for collaborative editing xi-editor

Yeah I think I get what you're saying -- basically that if you have incremental algorithms then you don't need to take a dependency on CRDT or OT to make the UI updates fast?

In other words, you can do things synchronously BUT still quickly, since you have an incremental algorithm. In any case, I basically asked that same question here:

https://lobste.rs/s/jembrx/thoughts_on_why_crdt_didn_t_work_...

I've seen Treesitter and am impressed by it, which I wrote a little about in that comment.

-----

Since you speak of "sane" languages, I wrote a parser for an "insane" language by hand, with a principled regex-based lexer:

How to Parse Shell Like a Programming Language http://www.oilshell.org/blog/2019/02/07.html

In fact the first thing I tried was to use ANTLR to translate the POSIX shell grammar (which only covers about 1/4 of the shell language). This drove home the limitations of grammar-based approaches. I found its model of lexing to be very limited (along with insisting on materializing a parser tree rather than providing semantic actions in ANTLR v4).

So it's good to hear that it's being updated for "context-aware lexing", and incremental lexing. Are you using ANTLR for IDE-like tools? I wasn't aware that it was good or commonly used for that kind of use case.

-----

I briefly talked with the author of Treesitter on Github about his bash syntax highlighter with Treesitter, which is of course a parser and not just a lexer, and can be made incremental.

I wasn't sure if the context-aware lexing mechanisms here could really handle the shell language:

https://tree-sitter.github.io/tree-sitter/creating-parsers#l...

I think his response was basically that it doesn't have to be 100% correct, which I agree with for an editor. Trading off some corner cases for speed is probably the right thing.

But I have thought about what it would take make a parser for a "crazy" language incremental and 100% correct (which you would want for further semantic analysis).

I wonder if you can write recursive descent parser in the Skip language and then get incrementality for free? The language is designed so that every algorithm can be made incremental, and it's not limited to pure functional constructs like other systems. Supposedly it goes to some lengths to provide you with a more imperative / mutable state modelk, so it should be able to express an "arbitrary" parser.

http://skiplang.com/

In other words, instead of having different algorithms for making LL(star) and GLR parsing incremental, Skip might give you a more expressive model for the parser. A bunch of my blog posts are about the limitations of grammar-based approaches.

-----

FWIW the style of context-aware lexing I use is explained here:

When Are Lexer Modes Useful? http://www.oilshell.org/blog/2017/12/17.html

And the other post lists the 14 different modes or contexts that the shell front end has:

http://www.oilshell.org/blog/2019/02/07.html#toc_7

It's a very simple and powerful mechanism, but my parser only cares about batch mode for now. It's not clear to me how it differs in expressiveness from what Treesitter offers (or ANTLR). The current lexer mode basically depends on the control flow of the parser.

Yeah definitely. I would consider this a form of semantic analysis, of the kind provided by Language Server implementations rather than the kind of syntax highlighting provided by syntect. Also note, the syntax highlighting done in xi-editor is both incremental and async[11]. This actually worked out well, and I would preserve it going forward. What I wrote above actually overstates the case, I think the ideal solution is an extremely simple form of OT so you can reuse as much as possible of the already-computed highlighting state, but you certainly throw away the highlighting result for the region being edited. Preserving "before" is trivial, and preserving "after" should be a simple matter of fixing up line counts.

[11]: https://xi-editor.io/docs/rope_science_11.html

Interesting - that’s definitely compelling. In a nutshell what exactly is the issue with IME?

Collaborative editing is not something you can just bolt on after the fact if you want it to actually work well. Things like building a robust server that can be exposed to the internet can certainly wait, but how you are you supposed to develop a plugin ecosystem when you haven't even settled on a conceptual model for how to store and manipulate text yet?

> Indeed, the literature of CRDT does specify a mathematically correct answer. But this does not always line up with what humans would find the most faithful rendering of intent.

This is a very salient point that anyone thinking of using CRDTs to "solve" synchronization in an user-facing application needs to take into consideration. Yes, CRDTs will guarantee that clients converge to an identical, mathematically "consistent" state eventually, but there's no guarantee whether or not that mathematically "consistent" state would make any sense to the application business logic that needs to consume that state, or to the human that needs to reason about the rendered result. That is a completely different can of worms that we'll still have to tackle to build a usable application.

Here's great example to illustrate this from Martin Kleppmann's talk on this topic: https://youtu.be/yCcWpzY8dIA?t=2634

Rest of the talk is also highly recommended for anyone interested in an approachable primer on CRDTs.

The trade-offs to CRDTs mentioned by the author in the context of text-editors make sense, but I would be curious to hear from the Xray team on what their current thinking on the topic is, given that they have collaborative editing as an explicit core objective (which might shift the value prop in favor of using CRDTs relatively speaking since in Xi it seems to be only an aspirational goal), and that their approach to implementation was similar but not quite identical to Xi's:

> Our use of a CRDT is similar to the Xi editor, but the approach we're exploring is somewhat different. Our current understanding is that in Xi, the buffer is stored in a rope data structure, then a secondary layer is used to incorporate edits. In Xray, the fundamental storage structure of all text is itself a CRDT. It's similar to Xi's rope in that it uses a copy-on-write B-tree to index all inserted fragments, but it does not require any secondary system for incorporating edits.

https://github.com/atom/xray#text-is-stored-in-a-copy-on-wri...