The Xi Text Engine CRDT

This is pretty impressive work for an undergrad internship.

I agree with this. The correct way of resolving conflicts is different depending on both the semantics of the document and the context in which the conflict arose.

For example, I think the CRDT approach is probably applicable to most examples of interactive editing, where incorrect conflict resolutions will happen near a point of focus for one of the editors and can be quickly and easily resolved.

If you have wildly divergent documents however (again depending on the document type itself), this is not really the same case, and it's much more likely that a human will need to create a resolved document by consulting the two parent documents.

Lots of people collaborate by emailing files to each other, and do version control by saving under a different filename every time. Using CRDTs as an on-disk file format can make these workflows less annoying, by working with changes instead of differences: the same advantage that Git's 3-way merge algorithm has over Subversion's 2-way merge.

Yes, there is great utility in this approach! For one, most concurrent text editing, rich or not, is actually quite easy to merge in 99% of cases. But even that aside, when you have data structures or document formats that don't ever have to resolve conflicts—or, more accurately, when conflict resolution becomes something that's naturally done in app-space, on the edges, and not as part of the network layer—then you open up the possibility of offline-capable, collaborative apps that require zero coordination between nodes. A node with changes only has to deliver their content to interested servers and peers, not engage in lengthy conversations about who has the definitive version, whether somebody has to revert, etc. You could build a Google Docs clone that synced entirely over Dropbox!

And in any case, the "merge" part would still be up to the app. The data structures will always be able to merge, sure, but the app could still throw up a dialog box on wildly divergent changes saying, "Hey, some crazy stuff happened here—want to look it over and commit manually?" (Where "commit" means generating new changes to overwrite any undesired changes, since it's not possible to literally undo.) You could argue that we've simply implemented ad-hoc coordination protocols in the app layer at that point, but IMO, that's exactly where they belong in cases where there's no authoritative store for your data. (Which is really the case with mobile, offline-first development.)

Glad you found it useful!

Apple’s Notes.app uses CvRDTs (I know this from figuring out the data format). For attributed text, they’re using something homegrown that they’re calling “topotext”. It’s somewhat similar to RGA/Causal tree, but they’re maintaining a digraph (unnecessarily?) and I suspect the conflict resolution isn’t quite right (doesn’t seem to do newest first). But for the sake of discussion, it’s a list of characters with lamport timestamps and a tombstone flag.

On top of this each character has a separate lamport time stamp for the attributes. This appears to act as a LWW register, per character. (So a conflicting attribute mutation would pick one users state and an insert conflicting with a embolding a range would not pick up the bold, but close enough?)

(On disk, runs of increasing clock are stored as one node, with a length, and the resulting text and attribute runs are stored separately from the CRDT data.)

A table is treated as an attachment in the main text (attributes on a placeholder character point to it). It is also encoded as a CRDT. (They compose CRDTs for maps, registers, etc here.) It is modeled as an ordered set of row ids, an ordered set of column ids, and a map of column id -> row id -> topotext. This is needed to preserve the semantics of adding/removing/ordering columns and rows in the face of conflicts.

Drawings are also stored as a CRDT.

(Sorry if this is terse or confusing, I’m typing on mobile.)

I agree with this, but one thing they might have been going for is editing code that you then compile and run on a beefier remote server. Although you don't need a full CRDT for that, it can do that.

> I can’t think of any challenge in text editing that requires beefy hardware.

The expectations of advanced text editors have expanded to create performance concerns which do not apply to the most basic text editor. It's basically what happens when somebody tries to elevate a vulgar art by doing it big: like making the world's largest macaroni sculpture, anything can be done big enough to meet limitations. In addition to this, Atom also has the problems of being an Electron app.

The point is that the frontend is a "thin" JavaScript UI rendered in the browser while the entire real dev environment is remote -- LSP (language sever protocol plugins aka autocomplete, semanic highlighting, nav to reference/definition, etc), other plugins, the project's toolchain, etc, are running in a container/pod on a beefy machine.

Theia (and GitPod.io) will give you this today and it is compelling. GitPod gives you a single button on PRs/Issues that drops you in a dev environment, ready to build and test at the click of a button. No cloning, no installing a toolchain, etc.

If Rust and Rust Language Server are running in a container with Theia, this means I can use a Chromebook-style device for serious, real development without having to enable dev mode or even Linux apps. Every machine in the world becomes a real potential development environment.

Theia even has (or is about to have) debug protocol support too. A real, full IDE running on a remote DC, accessible from your browser. ( If you follow what the Theia and Che devs are doing, they're trying to support the full VS Code API... Which is SUPER exciting!)

(Note, with the level I'm speaking about here, the CRDT is a bit of an implementation detail, but it's useful for collaborative editing and in xrays case, syncing state b/w the browser client and the backend and the underlying SCM system.)

Why is that? Did I say everyone had to adopt it? You don't think there's value in someone in a low-income situation being able to experiment with and use a full development experience without having to upfront invest in computing power?

Have you tried any of this tooling? It's hard to notice that I'm not in VS Code at times. I'd be curious what you find so dystopic.