Operational Transform for plain text, with the convergence property actually tested.
npm install ot-coreZero dependencies. ESM. Node 18+ and any modern browser.
One law defines correctness here. For two edits written against the same document, each participant applies its own first and the other's second, and both must end up holding identical text:
apply(apply(doc, a), transform(b, a, 'right'))
=== apply(apply(doc, b), transform(a, b, 'left'))The fuzzer that checks it is exported, so the claim is not something you have to take on trust:
import { checkConvergence } from 'ot-core/fuzz';
checkConvergence({ pairs: 100_000 });
// { pairs: 100000, divergences: 0, ms: 1120, examples: [] }Zero divergences means nothing on its own — a broken harness reports zero too. So the same runner accepts the transform under test, and there is a deliberately wrong one to compare against:
import { checkConvergence, identityTransform } from 'ot-core/fuzz';
checkConvergence({ pairs: 100_000, transform: identityTransform }).divergences;
// 46990 — 47% of pairs, which is what a transform that ignores
// the other operation looks likeThat is the number that makes the zero worth something.
Try it in the browser → — edit two operations, watch them transform against each other, and run either fuzzer live. The page imports this library rather than reimplementing it, so every figure on it is computed by the same code npm installs.
TP1 is convergence for a pair of concurrent operations, and that is all that is
tested. This library does not implement TP2, so it makes no claim about three or
more operations transformed against each other in different orders — the case an
undo of an old edit can reach. That limitation is documented in src/undo.js
rather than worked around.
I wrote an OT implementation for a collaborative code editor, load-tested it to 1,000 concurrent clients, and shipped it. It looked correct. Every manual test passed.
Then I wrote a property test for TP1 — the one law OT exists to uphold — and fed it random pairs of concurrent edits.
16.2% of them diverged. Two people editing at once ended up with different documents, in every category of edit:
| concurrent pair | diverged |
|---|---|
| delete vs delete | 1,530 |
| insert vs insert | 675 |
| insert vs delete | 561 |
| delete vs insert | 483 |
| of 20,000 | 3,249 |
This library is that implementation with the bugs found and fixed. The test suite is the point of it.
200,000 random concurrent pairs 0 divergences
50,000 on longer documents 0 divergences
20,000 on emoji 0 divergences
100,000 cursor moves 0 drifted off their character
240,000 compositions 0 disagreed with applying both
260,000 inversions 0 failed to round trip
25,000 multi-client sessions 0 clients left holding a different document
1. No tie-breaker. When two people insert at the same index, something has
to decide who goes first. The original returned both operations unchanged, so
each client kept its own position and the result depended on which message
happened to arrive first. transform now takes a side argument and exactly
one participant yields.
2. Delete-versus-delete arithmetic. Nested and partially-overlapping ranges double-counted characters that the other delete had already removed. Replaced with explicit interval arithmetic: subtract the overlap from the length, shift the start by however much of the other delete fell before it.
3. Insert inside a deleted range. The two sides disagreed about whether the inserted text survived. They now agree — see the trade-off below.
import { insert, remove, apply, transform, diff } from 'ot-core';
const doc = 'the cat sat';
// Two people edit the same text at the same moment.
const mine = insert(4, 'big '); // on its own: "the big cat sat"
const theirs = remove(4, 4); // on its own: "the sat"
// Each applies their own edit, then the other's — transformed.
const iSee = apply(apply(doc, mine), transform(theirs, mine, 'right'));
const theySee = apply(apply(doc, theirs), transform(mine, theirs, 'left'));
iSee; // "the big sat"
iSee === theySee; // true, and that is the whole jobA textarea hands you a new value, not an edit. diff bridges the gap, and
covers paste, drag-and-drop and autocorrect, which keystroke interception does
not:
textarea.addEventListener('input', () => {
for (const op of diff(lastValue, textarea.value)) socket.send(op);
lastValue = textarea.value;
});When an edit written against version N arrives and the document is already at N+2, fold it over everything it missed:
import { transformAgainst } from 'ot-core';
const rebased = transformAgainst(incoming, historySince(incoming.version), 'left');Two things this assumes, and neither is checked for you: the history is in the
order it was actually applied, and incoming was written against the document
as it stood immediately before the first of them. Fold the wrong range in and
the result is silently wrong rather than an error.
A single side for the whole run is correct when a server decides the order,
because the question is only ever "does the incoming edit yield to the settled
history" — and the answer is the same for every operation in it.
This used to say that peer-to-peer "needs a side per originating peer", which implied that choosing sides carefully was enough. It is not, and the difference matters enough to state with an example rather than a caveat.
Convergence over a pair of operations is TP1, which this library has and tests exhaustively. Convergence when different participants transform in different orders is TP2, which this library does not have — and almost no operational transform does. Take a two-character document and three edits:
const doc = 'ab';
insert(1, 'X') // peer 0
insert(0, 'XY') // peer 1
remove(0, 1) // peer 2Deliver those three to six peers in the six possible orders, with a stable per-peer tie-break, and they land on two different documents:
0 → 1 → 2 "XYXb"
0 → 2 → 1 "XYXb"
1 → 0 → 2 "XYXb"
1 → 2 → 0 "XYXb"
2 → 0 → 1 "XXYb" <-
2 → 1 → 0 "XXYb" <-
That is the smallest case there is; it was found by exhaustive search, and it is
asserted in test/session.test.js so it cannot quietly stop being true. Across
random triples the rate is about 3.6%.
Impose one order — any order, as long as everybody sees the same one — and it
goes to zero across 200,000 triples. That is what the server is for. It is not a
deployment detail you can engineer around with a cleverer side.
What is tested end to end: 20,000 simulated sessions of up to five clients against one server, with edits in flight and acknowledgements arriving late, all converging on the server's document — and, at every acknowledgement, the client's own rebase of its pending operation matching the server's, which is the invariant the whole protocol rests on.
yuvrajinbhakti.github.io/ot-core/demo, or locally:
npm run demo # http://localhost:4180/demo/Three real Clients and a real Server, over a wire you can make as bad as you
like: latency, jitter, duplicate messages, and connections that die. No bundler
— the page imports ../src straight, because the library is plain ESM with no
dependencies and that is worth being able to see rather than being told.
Two modes, and the second is the argument for the first. Fire the counterexample pushes the same three concurrent edits either way:
with a server all three agree converged
peer to peer Ana "XYXb" Bo "XYXb" Cy "XXYb" diverged
Deliberately not naming the string the server settles on, because it is not fixed and saying otherwise was wrong here until measured: five runs over a jittery wire produced "XYXb" four times and "XXYb" once, depending on the order the three edits happened to reach the server. Every run had all three clients agreeing, which is the entire claim. Which order gets chosen does not matter; that one gets chosen is the whole job.
Identical edits, identical tie-break rule, two different documents on the second row. That is TP2 missing, live, in one click.
Building it found four things wrong with the library, which is the actual reason it exists — see the end of the next section.
npm install ot-core @codemirror/state @codemirror/viewimport { collaborate } from 'ot-core/codemirror';
const view = new EditorView({
doc: client.document,
parent: element,
extensions: [collaborate(client)],
});That is the whole binding from the outside. Inside it is about a hundred lines doing two things that are easy to get wrong:
Units. CodeMirror counts UTF-16 code units and this library counts code points, so an emoji is two to one of them and one to the other. Every offset crossing that boundary is converted, and a change that would cut a character in half — which CodeMirror will happily do if a program asks — is widened to cover it, because "half a code point" is not something this operation model can say.
Echo. An operation arriving from the server is applied to the editor, which fires the same update listener a keystroke does. Sent back, it reaches the server twice. Remote transactions carry an annotation and are skipped on the way out.
Multiple cursors work, which is the part a textarea cannot test:
iterChanges reports every change in the original document's coordinates, so
the running offset in operationsFromChanges is what keeps the second cursor's
edit in the right place once the first has changed the length.
Live at /demo/editor.html.
Typing HELLO into one editor there sends two operations, not five — the first
keystroke goes, the other four compose behind it — and the other editor sends
nothing back.
@codemirror/state and @codemirror/view are optional peer dependencies.
Nothing else in the package imports them, so ot-core is still zero-dependency
for anybody who does not import this file.
import { collaborate } from 'ot-core/codemirror5';
const detach = collaborate(cm, client);A separate module rather than a flag, because the two versions report changes in
different coordinate systems and sharing the code would mean a branch in the one
function where a mistake is invisible. CodeMirror 6's iterChanges gives every
change against the document as it was before the transaction, so converting it
needs a running offset. CodeMirror 5 pushes a change object as each change is
applied, so every entry after the first is already in the coordinates the
previous ones left — sequential, not simultaneous.
Carrying version 6's running offset across to version 5 therefore double-counts, and only when a batch produces more than one change: one cursor is always right, two are always wrong. It is exactly the class of bug that ships.
Version 5 has no transaction annotations either, so the echo is suppressed with
a distinguished origin on remote changes instead. codemirror is an optional
peer dependency alongside the version 6 packages.
The algebra above is the hard part and it is not a collaborative editor. What was missing was everything between two people's keyboards: who holds an edit while an earlier one is in flight, what happens to a socket that drops after the server accepted an edit but before the acknowledgement got home, and what a client does with the four hundred milliseconds of typing it did while offline.
Those ship now, as subpaths of the same package.
// browser
import { connect } from 'ot-core/websocket';
const client = connect(new WebSocket(url), {
id: myUserId,
onReady: () => textarea.removeAttribute('disabled'),
onChange: (c) => { textarea.value = c.document; },
});
textarea.addEventListener('input', () => client.editText(textarea.value));// server
import { Server } from 'ot-core/server';
import { Room } from 'ot-core/websocket';
const room = new Room(new Server({ document: load(docId) }));
wss.on('connection', (socket, request) => room.join(userIdFrom(request), socket));Not seven packages, and the reason is specific to this problem rather than a
preference. A client and a server running different versions of transform
diverge silently — no error, no crash, two documents that drift apart over an
hour and cannot be reconciled afterwards. Separate packages with independent
version ranges make that a thing a lockfile can do to you. One package makes it
impossible. Subpaths tree-shake identically: ot-core/websocket in a browser
bundle does not drag the server in.
synchronized ──edit──► awaiting ──edit──► awaiting-with-buffer
▲ │ │
└────────ack─────────┘ │
▲ ▲───────ack──────────────┘
One operation on the wire at a time. Edits made while waiting go into a buffer and are composed as they arrive, so a burst of typing that spans a round trip leaves as one message rather than twelve.
The third state is where the bodies are. An operation arriving from the server has to be transformed past the outstanding operation and past every buffered one in order, while each of those is rebased past it. Doing only the first half looks entirely plausible and works until three people overlap.
Four came out of 30,000 simulated sessions with a deliberately hostile wire, two more out of building the playground on top of the result, and three more the first time any of it touched a real socket. Every one of them passed a hand-written example first.
A resend must replay the message, not rebuild it. Between the first send and the resend, arriving operations rebase the outstanding operation — so a rebuilt message carries a different operation under the same sequence number. The server applies one and deduplicates the other, and the two sides disagree about which, permanently. Messages are immutable; the server rebases from the revision the message carries.
Reconnecting must not transmit mid-catch-up. Recognising your own operation in the history you missed and promoting the next buffered one is right; sending it there is not, because the rest of the missed history has not rebased it yet. Same failure as above, reached from the other direction.
A client must ignore operations it already has. A reconnecting client
catches up through since(), and a broadcast of one of those revisions can
still be in flight. Applying it twice inserts the text twice, permanently, and
nothing downstream can tell that from an OT bug. The revision is already on the
message, so the check is free.
A rejected operation has to be let go of. A client whose edit the server
refused sat in awaiting forever, transforming everybody else's operations
against something that did not exist. It now drops the unconfirmed work and
hands it back in onError({ discarded }) so the application can decide, rather
than diverging quietly.
The fan-out must broadcast before it acknowledges. The author promotes its next buffered operation the instant it is acknowledged, so with a synchronous transport that operation reached the server and was broadcast first — every other client saw revision N+1 arrive before N, then discarded N as a duplicate. One operation lost per collision, silently. The room now dispatches through a queue that cannot be re-entered, and clients report a revision gap as an error instead of applying across it.
A room must not compact history the moment somebody leaves. Compacting to
the slowest connected member means that the instant a socket dies, the history
that client will need is gone; it comes back, is told behind-history, and is
resynced from a snapshot that silently discards everything it typed while
offline. Room keeps a retention window past what connected members need,
because the cost is a few hundred operations and the alternative is losing a
user's work.
A room must not forget a client when its socket closes. The server remembers
the last sequence number each client had accepted, and that memory exists for
exactly one situation: a socket that died between the operation landing and the
acknowledgement getting home. leave was discarding it at the precise moment it
was about to matter, so the client came back, resent, and the edit was applied a
second time.
A client must ignore its own operation arriving as history. On a rejoin the server sends everything after the client's revision, and the client's own unacknowledged edit is among it. Applying that as though somebody else wrote it inserts the text twice on that client alone.
An acknowledgement may not skip a revision. It lands at exactly one past where the client is, because everything the server accepted in between reaches it first on the same socket. Taking a further one anyway means the next buffered edit is sent claiming a baseline the client never had, and the server rebases it from the wrong place — one character, one position early, no complaint.
All three needed a real socket. A fake never closes between a write and its delivery, never hands a message to a listener that has not been attached yet, and never delivers on a later turn of the event loop.
The test harness asserts that a well-formed client is never rejected — the recovery path exists, and letting it run would hide the next real bug.
Falls out of the state machine rather than being a feature bolted to it.
disconnect() stops sending; edits keep applying locally and accumulating.
reconnect(server.since(client.revision)) catches up and pushes.
client.disconnect();
client.editText('...typed on a train...');
client.reconnect(await fetchMissedOperations(client.revision));The resend is unconditional, because from the client's side "the acknowledgement
never arrived" and "the edit never arrived" are the same observation. The seq
on the message is what lets the server tell them apart.
Rebasing is linear in history depth — 0.016µs against one operation, 22µs
against a thousand — so a room that never drops history gets slower for as long
as it stays open. Room compacts to the slowest member still connected;
Server.compact(revision) is there if you are managing membership yourself. A
client behind the compaction point is told behind-history and has to rejoin,
which is a real answer rather than a wrong document.
side must be 'left' for one participant and 'right' for the other, and
both must agree without talking about it. Compare something stable — site ids,
or client id against server:
const side = myId < peerId ? 'left' : 'right';Getting this wrong is silent. Everything works until two people type in the same place.
Transforming the document is half of collaborative editing. The other half is that every caret, selection and highlight anchored to the text has to move with it, or a remote insert three lines up quietly slides your cursor into the middle of a word.
import { transformPosition, transformSelection } from 'ot-core';
socket.on('operation', (op) => {
setDoc((doc) => apply(doc, op));
setCaret((caret) => transformPosition(caret, op));
setSelection((selection) => transformSelection(selection, op));
});transformPosition takes the same 'left' / 'right' bias, and it decides one
thing: what happens when an insert lands exactly on the position. 'left' is
the default and keeps the cursor where it is, so a collaborator typing at your
caret does not drag it along. Use 'right' for the local echo of your own
typing, where the caret should follow what you wrote.
transformSelection leans each end outward, so text arriving at either boundary
falls outside the selection. The intuitive-looking choice — leaning both ends
inward — makes a selection silently grow to cover whatever a collaborator types
at its edges.
ot-core/presence is the same arithmetic applied to everybody else, plus the
bookkeeping that makes it usable:
import { Presence, track } from 'ot-core/presence';
const presence = new Presence({ onChange: (peers) => draw(peers) });
track(client, presence);
socket.on('cursor', ({ id, selection, revision, name }) =>
presence.see(id, selection, { revision, meta: { name } })
);It is a data structure and the transforms, not a transport. Presence is
ephemeral, high-frequency and tolerant of loss; operations are none of those,
and putting cursors through the operation channel means an unordered droppable
message class inside a state machine built to never drop or reorder anything.
Send cursors however you like — a second socket event is fine — and hand what
arrives to see.
Two details it gets right that naive implementations usually do not. A report carries the revision it was true at, and is transformed forward through exactly the operations it missed, so cursors do not drift when people type quickly. And it is rebased past your unacknowledged edits too, because the peer wrote that position against a document that does not contain them.
One window stays open, and it is documented rather than hidden: an operation of your own that has just been acknowledged is in neither the history ring nor your pending edits, so a report stamped before that acknowledgement is not rebased past it. It is one round trip wide and closes on the peer's next report.
Five keystrokes are five operations on the wire, five entries in the history every future operation has to be transformed against, and five steps in an undo stack that will undo one character at a time. They are also, obviously, one insert:
import { composeAll, insert } from 'ot-core';
composeAll([insert(4, 'h'), insert(5, 'e'), insert(6, 'y')]);
// [ insert(4, 'hey') ]compose(a, b) returns null when the model cannot express the pair as one
operation — edits in two places, or a replacement. composeAll keeps those
separate and drops anything that cancels out entirely, so typing a word and
deleting it again produces nothing to send.
Undo is invert, and then the same transform as everything else, because by the
time somebody presses Ctrl-Z other people have edited. ot-core/undo does the
bookkeeping:
import { attachHistory } from 'ot-core/undo';
const history = attachHistory(client);
undoButton.onclick = () => history.undo();
redoButton.onclick = () => history.redo();It records every local edit, rebases both stacks past every remote operation, and drops entries that other people's edits have flattened to nothing — because an undo button that visibly does nothing reads as broken.
Two things to expect. If somebody has already deleted across the text you typed, your undo correctly does nothing and skips to the next real entry: undo here means "remove what is left of my contribution", not "recompute history as though I never typed" — the second is exclusion transformation, and this library does not do it.
And if somebody types inside a run of text you inserted, undoing your insert
removes their characters too. That is the trade-off below arriving somewhere you
can feel it: your undo is a delete, their text is inside it, and transform
resolves that by letting the delete swallow the insert. Splitting the delete
around foreign text is the better behaviour and a larger change than this
module; until then it is asserted in the tests so it cannot drift silently.
insert() and remove() validate their arguments, which does not help with the
operation a client sent you. apply clamps an out-of-range position on purpose,
so a malformed delete does not throw — it removes the wrong text, and every
client converges on the damage:
import { assertValid } from 'ot-core';
socket.on('operation', (raw) => {
const op = assertValid(raw, Array.from(doc).length); // throws with the reason
doc = apply(doc, op);
});If you type into text that someone else is deleting at that exact moment, your character is dropped.
This is forced by the operation model. An operation here is one position and one length, and preserving your insert would require splitting their delete into two pieces — which this model cannot express. The alternative is to model operations as sequences of retain/insert/delete components, the way Quill Delta and ShareDB do. That is strictly more capable and considerably more machinery.
The single-operation model is the right trade for cursor-level editing, where concurrent insert-into-deleted-text is rare and losing one character to it is defensible: the text you were typing into no longer exists.
Measured with npm run bench on Node 22, Apple silicon:
transform(a, b) 0.015 µs 66,000,000 ops/sec
rebase against 1 operations 0.031 µs 32,000,000 ops/sec
rebase against 10 operations 0.099 µs 10,000,000 ops/sec
rebase against 100 operations 1.011 µs 989,000 ops/sec
rebase against 1000 operations 22.467 µs 44,500 ops/sec
Rebasing is linear in history depth. A single transform is never the bottleneck; letting a room accumulate unbounded history is. Acknowledge and compact.
That measures the algebra, which was never the problem — nine bugs were found in
this library and none of them were in transform. The second benchmark measures
the layer they were actually in:
Client receive with 0 buffered 4.242 µs 235,000 ops/sec
Client receive with 100 buffered 6.721 µs 148,000 ops/sec
Server written 0 revisions behind 4.905 µs 203,000 ops/sec
Server written 100 revisions behind 7.370 µs 135,000 ops/sec
Presence 10 peers, one operation 0.172 µs 5,816,000 ops/sec
Presence 200 peers, one operation 1.659 µs 602,000 ops/sec
Undo stack of 1 0.115 µs 8,701,000 ops/sec
Undo stack of 200 8.864 µs 112,000 ops/sec
End-to-end 2 clients in a room 12.349 µs 80,000 ops/sec
End-to-end 20 clients in a room 77.325 µs 12,900 ops/sec
Nothing there is flat. The steepest curve is undo, roughly 75× from a stack of
one to a stack of two hundred, because every remote operation rebases the whole
stack — so limit is a throughput setting and not only a memory one. A room
costs about 4 µs per additional participant on the fan-out, which is thousands
of edits a second before the network is involved. The network is what you will
actually run out of.
These are single-core numbers with no network, so they are an upper bound and a
shape rather than a capacity plan. They are also measured in short batches
against freshly built state: every insert makes the document longer and apply
copies it, so a straight loop measures string copying instead of the thing
under test. The first version of that benchmark did exactly that and never
finished.
| export | does |
|---|---|
insert(position, content) |
build an insert operation |
remove(position, length) |
build a delete operation |
apply(doc, op) |
apply one operation to a string |
applyAll(doc, ops) |
apply several, in order |
transform(a, b, side) |
rewrite a to apply after b |
transformAgainst(a, ops, side) |
rewrite a over a run of operations, oldest first |
transformPosition(pos, op, bias) |
move a caret when op is applied |
transformSelection(sel, op) |
move both ends of a { anchor, head } selection |
diff(before, after) |
turn two document states into operations |
isNoop(op) |
did transform cancel this operation? |
compose(a, b) |
one operation meaning a then b, or null |
composeAll(ops) |
collapse a run as far as the model allows |
invert(op, doc) |
the operation that undoes op |
invertAll(ops, doc) |
a run that undoes a run |
isValid(op, docLength?) |
is this safe to apply? |
whyInvalid(op, docLength?) |
the reason it is not, or null |
assertValid(op, docLength?) |
the same, but throws |
collaborate(client) |
a CodeMirror extension bound to a client |
From ot-core/presence and ot-core/undo:
| export | does |
|---|---|
Presence |
where everybody's cursor is, moved as the document changes |
track(client, presence) |
keep a Presence in step with a Client |
UndoStack |
inverses, rebased past everything that happened since |
attachHistory(client) |
an undo/redo pair wired to a client |
From ot-core/client, ot-core/server, ot-core/websocket and
ot-core/protocol:
| export | does |
|---|---|
Client |
the three-state client, buffering and rebasing |
Server |
the authority: orders operations, rebases late ones |
connect(socket, options) |
a Client wired to a WebSocket-shaped thing |
Room(server) |
a Server plus fan-out, membership and compaction |
encode / decodeClientMessage |
JSON with the validation a bare parse leaves to chance |
ERRORS |
rejection codes a client has to branch on |
Positions count Unicode code points, not UTF-16 units, so an emoji is one position rather than two.
npm test # 155 tests, over a million property checks + 55,000 simulated sessions
npm run demo # the playground, at http://localhost:4180/demo/
npm run bench # the algebra, and then the layer the bugs were actually inSix of those run over a real WebSocket — ws is the only devDependency, and the
published package still has none. They skip with a reason if it is not
installed, and CI fails if anything skips, because a suite that quietly stops
testing the thing it was written for is worse than one that is simply absent.
The fuzzer uses a fixed seed, so a failure is reproducible rather than a story about something that happened once on CI. It also biases hard towards collisions — short alphabet, short documents, small edits — because the bugs it is looking for only appear when two edits genuinely overlap.
Not a CRDT: it needs a server to order operations, and the section above shows what happens without one. Not rich text: plain strings only. No presence, no transport, no editor bindings — those belong in packages that depend on this one, not in it.
No undo stack, though invert is the piece one needs. Deciding what a user
meant by Ctrl-Z — their last edit, or the last edit in the document — is an
application's question, not this library's.
This section used to claim there was no compose and could not be one, on the
grounds that two operations far apart cannot be expressed as one position and
one length. The first half was true and the second half was wrong. Edits far
apart do stay separate, but consecutive keystrokes are not far apart: typing a
five-letter word produces five inserts that are exactly one insert, and a
backspace run is one delete. compose merges those and returns null for the
rest, which is why composeAll returns an array rather than an operation.
MIT