Conflict-free 3-way Text Merging

Why

Merging concurrent edits is a solved problem when you control the whole editing stack¹. CRDTs² and Operational Transformation³ (OT) capture changes as they happen, which works when you own the editor, transport layer, and storage format. However, there are workflows where that’s not the case. For instance, an Obsidian vault can be changed through, among others, Obsidian, Vim, VS Code, or even OneDrive. A sync engine can only see the final state of each file, and only eventually, so it has no visibility of individual edits. This is the same constraint Git operates under. While Git rightly exposes ambiguous write-write conflicts with <<<<<<< conflict markers, I wanted automated merges even when not all edits are observable.

Conflict markers are the right choice for source code, where a bad merge is a bug and a human must verify the result. reconcile-text is built on the assumption that human prose is more forgiving: a slightly imperfect sentence is usually better than conflict markers interrupting a document. So reconcile-text essentially implements git merge (technically, it’s git merge-file⁴) without conflict markers and with support for correctly translating cursor (and selection) offsets. It does all this by diffing both edited states against their common parent, without having to maintain expensive tombstones or other metadata client-side. Let’s look at an example:

import { reconcile } from 'reconcile-text';

// the version both sides start from
const parent = 'Hello world';

// one user added "beautiful"
const left = 'Hello beautiful world';

// the other changed the greeting
const right = 'Hi world';

// "Hi beautiful world"
reconcile(parent, left, right).text;

You can try it out yourself in the interactive playground at reconcile.schmelczer.dev⁵.

The library’s API is essentially just this one function (and a few helpers to make transport easier) which merges the input texts (a parent and two diverging edited versions). Both sets of changes are applied using an algorithm inspired by OT which repositions cursors and selections along the way.

How it works

The demo website prominently offers a choice of tokeniser because splitting the inputs into tokens is the first step. Even though human text is forgiving of merge artefacts, I wouldn’t expect to see the characters of words (technically, UTF-8 grapheme clusters) zipped together into nonsense. That’s why treating words, or even sentences, as atoms can be reasonable. Markdown, however, should be tokenised slightly differently. reconcile-text supports custom tokenisers exactly for this purpose. We can’t guarantee that the merged Markdown, for instance, will be syntactically correct⁶, but at least we can guarantee that tokens won’t be split up.

It then computes token-stream diffs between the parent and each competing current version (diff(parent, left), diff(parent, right)), similarly to diff3⁷. The diffs are cleaned up to ensure contiguous inserts and deletes, keeping as much of each side’s changes together as possible. Finally, the two sides are zipped together using OT principles: each side’s edits are transformed against the other side’s. This process also updates a list of cursor offsets according to rules that make each cursor “stick” to the nearest token and travel with it during the merge.

I never set out to implement OT for its own sake. Transforming batched diffs simply turned out to be an elegant way to merge two Myers⁸ outputs. A CRDT could achieve the same result. But when all you can observe is the final state, merge quality is limited by the underlying 2-way diffs independent of the machinery used to combine them. A moved paragraph, for example, reaches the merger as an unrelated deletion and insertion because that’s all Myers’ algorithm can express.

Differential Synchronisation

With this primitive, we can build a full text syncing app in the spirit of Differential Synchronisation⁹, but simpler. A possible algorithm would be to copy git’s fetch-merge-push loop (but skip conflicts):

The server stores every version of a text and a pointer to the latest version. It can then append a new version if its parent version is still the latest and update the latest version to the new value. Otherwise, reject the text and return the latest. This is a standard compare-and-swap implementation.
The client stores the user’s editable file plus base (the last version it exchanged with the server).
When the file changes, the client pushes it. On rejection, it merges locally, file = reconcile(base, file, latest) (reconcile¹⁰), makes latest the new base, and retries.
On success, the pushed text becomes base.

Extensions

When implementing this algorithm in practice, we will notice a few gaps that can be easily filled. If fairness becomes an issue, we can add a mechanism for leasing a lock on the file to get a high-latency client’s edits through.

Crashes and lost responses can be handled by making the version id the idempotency key. The new version’s ID is calculated by the client (it’s just latest + 1) and saved together with the outgoing snapshot before pushing. When the server sees a retry of a known ID, it can acknowledge it rather than re-apply it.

To save on bandwidth, texts can be sent as to_diff¹¹ outputs and reconstructed with from_diff¹², only sending the changes instead of repeating an ever-growing document.

Where it sits among the alternatives

Each alternative leaves a different part of this job unsolved. diff3 and git merge-file do the structural work, then write <<<<<<< markers when the two sides actually conflict. Neil Fraser’s diff-match-patch is the closest tool in spirit, but it’s 2-way. Without a common ancestor, it can’t reason about what the left and right sides intended, and a failed patch in a one-shot merge can lose an edit. CRDTs preserve concurrent edits, but they require CRDT state and metadata tied to the document’s editing history rather than three plain strings. That’s why reconcile-text fills an admittedly niche gap for syncing systems that lack full control over or visibility into individual edits.

One core, three registries

The Rust core compiles to WebAssembly through wasm-bindgen¹³ for the npm package and provides native Python bindings through PyO3¹⁴. This makes reconcile-text available from Rust, Python, and JavaScript or TypeScript across Node.js, the web, and React Native (whose Hermes engine has no WebAssembly, so that entry point ships a pure-JavaScript build produced by Binaryen’s wasm2js), allowing the same logic to be used across the stack.

a solved problem when you control the whole editing stack: https://marijnhaverbeke.nl/blog/collaborative-editing-cm.html ↩
CRDTs: https://crdt.tech/↩
Operational Transformation: https://en.wikipedia.org/wiki/Operational_transformation ↩
git merge-file: https://git-scm.com/docs/git-merge-file ↩
https://reconcile.schmelczer.dev/↩
Ink & Switch’s Peritext¹⁵ is a good write-up on this problem for rich text.↩
diff3: https://blog.jcoglan.com/2017/05/08/merging-with-diff3/↩
Myers: https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/↩
Differential Synchronisation: https://neil.fraser.name/writing/sync/↩
reconcile: https://home.schmelczer.dev/git/andras/reconcile/src/commit/08a656c6ed32d7c307b36bc6dec0134c40ac0a43/src/operation_transformation.rs#L40 ↩
to_diff: https://home.schmelczer.dev/git/andras/reconcile/src/commit/08a656c6ed32d7c307b36bc6dec0134c40ac0a43/src/operation_transformation/edited_text.rs#L406 ↩
from_diff: https://home.schmelczer.dev/git/andras/reconcile/src/commit/08a656c6ed32d7c307b36bc6dec0134c40ac0a43/src/operation_transformation/edited_text.rs#L475 ↩
wasm-bindgen: https://docs.rs/wasm-bindgen ↩
PyO3: https://pyo3.rs/↩
Peritext: https://www.inkandswitch.com/peritext ↩