Eleven years ago, I wrote Collaborative Editing inProseMirror, my first stab at doingcollaboration in a rich text editor. Then six years ago I wroteCollaborative Editing in CodeMirror,describing a more elegant approach for a text editor. Now, afterreleasing Wordgard last week, I've spent a lot oftime thinking about how to apply those techniques to a rich texteditor. This post is a report on my current thinking (which may stillchange before Wordgard stabilizes).

The core of the approach I'm using in Wordgard is again operationaltransformationwith a central server that's responsible for deciding on a final orderfor concurrently created changes. Check back to the old blogpost for a description of that generalapproach.

See also the example on thewebsite.

Document Structure

The main added challenge with the document structure that Wordgarduses is that the document is a tree, not a sequence of characters likeit is in a text editor.

Many systems in this same space solve this by making their document aflat sequence of characters after all (see for exampleQuill andPeritext). You canget quite far that way by making the document a sequence of blockswith metadata attached to each block, but it requires some contortionsto even do things like nested lists (you'd mark blocks with listmarker flags and an indentation). And as you get to more complexdocument structure (arbitrary nested blocks, say a blockquote in alist in a blockquote, or tables), such a model becomes very messy towork with or breaks down entirely.

Having a clean, obvious document model was an important goal in thedesign of Wordgard. Since many types of document structure really needa hierarchical model, I decided that I could not get aroundrepresenting the document as a tree.

But because you can see such a tree as a flat sequence of tokens (textcharacters, leaf nodes, and open/close tokens for inner nodes), myrepresentation of changes can work in a way similar to whatCodeMirror does for its flat text model. A change replaces certainranges in this token sequence with new sequences of tokens. This meansmy change representation is pretty close to CodeMirror's, andoperational transforations on those can mostly be defined mostly inthe classical way.

Except of course that, while in a flat document any set ofreplacements is a valid change, in a hierarchical model you do needyour open and tokens to balance, and, with Wordgard's schemaconstraints, its node nesting to actually be allowed. Transforming twovalid changes over each other may create an invalid change.

Fixing up Changes

So that adds a complication. A transformation function thatoccasionally produces changes that cannot be applied is useless.

If we require the starting document of the transformed changes as oneof the inputs to the transformation function, we can check its output,and if it isn't valid, synthesize an additional change that makes itvalid. This is definitely a cost���needing to pass in the document isoften inconvenient, and such a check requires the library to do morework. Fortunately most of the code necessary for this was alreadyneeded for the function that creates change sets from a description ofthe changes, since there you also want to make sure you're notreturning invalid sets.

If you can define this correction-computing code in such a way that itproduces the same correction for transforming A over B that itproduces for transforming B over A, you can make sure your resultingchanges still converge. Assuming the basic transformation algorithmconverges, A���B' and B���A' (using ��� to mean composition) would producethe same (possibly invalid) document. Adding the same fix to bothsides makes sure they converge on a valid document.

This only works if both side perform their transformation on the samechange sets. You cannot, for example, expect transforming C over A���Bto produce the same change as transforming it first of A and then overB���but this same issue exists in the basic operational transformationalgorithm I use (as it does, I believe, in all of them that don'tstore information about deleted content), so that contraint alreadyexisted.

Mark Changes

Another thing you need in a rich text model is to be able to add orremove metadata for some content (the thing Wordgard calls marks,modelling things like text styles or alignment) without deleting andre-inserting it.

For example, if your cursor is in the middle of a paragraph andanother peer (or you yourself, for that matter) adds emphasis to theparagraph's text, your cursor should stay in place, and the editorshould know that the content around it is the same content, just withan additional mark.

Wordgard's change format can describe not just replaced ranges butalso modified ranges, that have some marks added or removed. Applyingthese modifies the document but doesn't affect positions ���mapped���through the change. Because the structure of such ranges stays thesame, we lose less information about them then we would for areplacement.

This distinction is also useful when transforming changes. If bothsides modify some marks for a given range, those modifications can bemerged without overwriting each other or duplicating content.

When is a Change Accepted

In network communcation, both parties knowing for sure whether amessage was succesfully transmitted is aproblem. Whena client sends a change to the server, and the connection cuts outbefore the server can return a confirmation, the client doesn't knowwhether its change has been stored or not.

To make the protocol robust against that kind of issue, Wordgard usesa system where all changes are sent to all clients, including theirown changes. That way, clients simply wait for their changes to comeback to them, and only drop them from their set of pending changeswhen they do.

This turns the protocol into two mostly separate streams ofinformation (clients sending their changes, servers notifying aboutconfirmed changes), which is more robust than a request-responseapproach.

Server-Side Transformation

The communication protocol initially used by CodeMirror's (andProseMirror's) approach was wonderfully simple: the server onlyaccepts changes that start from its current document version. If aclient tries to submit a change to an outdated version, it isrejected. It will have to get the new changes from the server,transform its change, and try again.

This makes sure transformation only happens in one place, making itquite straightforward to reason about convergence. But unfortunatelyit has a rather big problem in situations where a bunch of people areactively editing a document over real-world network connection. If aclient is slow (or just has a high latency), and there are other,faster clients constantly submitting changes, that slow client willnever get a word in until all the others stop editing. By the time ithas received the new changes and tries to resubmit its transformedlocal changes, there will be new changes from the peers that beat itto submitting, and it will have to start over again.

There are several solutions to that, such as enforcing fairness bygiving a client that tries to submit an outdated change a grace periodfor resubmitting it before accepting anything from others. But theless messy solution is to make the server just do the transformationitself and accept the change. Now no one has to wait for each other,and throughput isn't negatively affected.

It does require the server to be able to do the transformations. And,more worryingly, to be able to do them in precisely the same way asthe client, so that both sides agree on what the resulting documentlooks like.

Change Grouping

The safe way to perform transformation of two groups of changes overeach other involves a double loop of transformations (see the diamonddiagram in the CodeMirror post). Thisis obviously quadratic in complexity���and thus, especially if yourtransformations are relatively expensive, very unattractive.

You can simplify this a lot by composing both groups into singlechanges, so that you only need to perform one transformation. But as Imentioned, transformation over composed changes is not equivalent totransformation over separate changes. So you'd need to make suretransformation always happens with the same set of changes.

To get most of the benefits of change grouping without affectingconvergence, clients use the following system:

A client has at most one set of changes in flight (sent to theserver but not yet confirmed).

New changes are composed together.

Until they are observed by creating a sendable change, at whichpoint, if there was no set of observed changes yet, the currentpending changes are stored as the in-flight change set, and newchanges composed into a separate group.

This means we have at most two change sets (the in-flight group andthe new group) to transform over incoming changes. And similarly, theserver get single composed sets from clients, which it can linearlytransform over concurrent changes. If latency is high and editingactivity fast, the combined sets will get bigger because more changesare composed together while waiting for the in-flight change to clear.

Corrections

Wordgard supports an abstraction called a ���correction���, which is usedto enforce document shape constraints that the basic parent-childrelations you specify in your schema cannot express. These work byobserving transactions, and for those that would violate theconstraint, amending them so that they don't do that.

The way corrections and collaborative editing combine is not entirelystraightforward. If you just don't do anything special, they mostlywork���clients will apply them before submitting their changes, and inmost cases the corrections are applied properly.

But it is possible for two changes that don't violate a constraint to,when transformed and combined, violate it. For example if two clientsconcurrently split the same table cell, the initial transactions aregenerated in a way that preserves the constraint that tables arerectangular, but when merged, the two inserted cells will both bethere, producing a row that is too wide.

Now these transformed changes will be delived to all clients and wouldtrigger the correction on every one of them. So they will all delete acell. Double deletions will cancel each other, so in this case theresult would just be a bit awkward and wasteful, but it is possible tocreate endless loops like this���corrections causing, in transformedform, more corrections.

To address this, Wordgard doesn't apply corrections to remote changes.That solves half the problem���you can no longer get multiple clientstrying to perform the same correction. At least not immediately. Butnow you can violate the constraints encoded by these correctionsagain, which is not what we want.

For this reason, both the server and the client are set up toimmediately run corrections whenever they transform changes, as partof the transformation���much like the invalid change fixup I mentionedbefore. This way a single party is responsible for applying them,avoiding the potential for duplicated correcting changes.

This does require giving the server access to the corrections, andmaking sure both server and client use the exact same set ofcorrections. But it gives us safe, structure-aware collaborativeediting.

Future Plans

I do intend, eventually, to deliver not just the primitives forimplementing collaborative editing, but actual implementations ofsolid client and server code. This pulls in a whole lot of complexity,like interacting with network communication and databases, recoveringfrom crashes and network issues, and so on���so it's a work in progress.

Another important thing to have in a collaborative setup issynchronization of document-external data. I'm working on a designthat works analogous to the state fields and transaction effects thatare used to track state inside the editor, but in a way thatinitializes the state from a shared server-side value, and broadcastseffects to the server and other clients to update it.

Because such state will often contain references to documentpositions, which will need to be mapped over changes to stay accuratefor the current document, this design is complicated by the fact that,like transformations, position mapping isn't stable overcomposition���mapping a position through changes A and B might yield adifferent result from mapping it directly over A���B.

That means that if you keep your local value of a given shared fieldin sync with your document by eagerly updating it for local changes asthey come in, you may end up with a different value than what otherpeers get when they apply a composed version of your changes all atonce.

But since we do have a stable well-defined sequence of changes (thoseconfirmed by the server), and state fields work with immutable valuesand pure functions, I'm hopeful that I can make something work withkeeping a base, synced version of these shared fields in each client,and replaying the changes as the server confirms them onto that,replacing the temporary estimated version of the fields that wascreated locally.