Conflict-Free Three-Way Text Merging

Why

Merging concurrent edits is a solved problem when you control the whole editing stack¹: conflict-free replicated data types² (CRDTs) and operational transformation³ (OT) capture changes as they happen, which works well when you own the editor, transport layer, and storage format. However, there are workflows where that’s not the case.

For instance, text files on disk can be edited in Obsidian⁴, Vim, or VS Code and updated through Syncthing or even OneDrive. A sync engine therefore sees only the resulting file snapshots, often after a delay, rather than the individual edits that produced them. This is the same constraint Git works under: Git-tracked files may be edited by many programs, all outside Git’s control. Git rightly highlights ambiguous write-write conflicts with <<<<<<< markers: a bad source-code merge may introduce a bug, so a human should verify the result.

Git’s union merge driver is the closest to a built-in solution. The union driver works line by line and resolves a conflict by retaining both sides’ line sequences. As a result, independent word-level edits can duplicate whole lines, while overlapping deletions can restore or reorder text that one side deleted.

But I wanted fully automated merges for my text files with intuitive merge results. That’s why I created reconcile-text, which is built on the assumption that human languages are more forgiving than code: 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 it does this without client-side tombstones or an operation history. 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 API is essentially just this one function, plus a few helpers to make transport easier. It takes a parent and two diverging versions, derives and applies both sets of changes, and repositions cursors and selections along the way. Cursor support makes it possible to use reconcile-text in a text editor too.

How it works

The first step is splitting the inputs into tokens, which is why the demo website offers a choice of tokeniser. Even though human text is forgiving of merge artefacts, I still wouldn’t want characters within words interleaved into nonsense. That’s why treating words, or even sentences, as atoms can be useful. The built-in Markdown tokeniser extends word tokenisation to account for Markdown syntax. The Rust API also lets you specify custom tokenisation rules. We can’t guarantee that the merged Markdown, or other marked-up text, will be syntactically correct⁷, but we can guarantee that the selected tokeniser’s tokens won’t be split up.

After tokenising, the algorithm diffs each edited version against the parent (diff(parent, left), diff(parent, right)), as diff3⁸ does. It uses Myers’ diff algorithm⁹ to compute those diffs, then cleans them up to make insertions and deletions contiguous, keeping as many 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. Cursor offsets are updated along the way, making each cursor “stick” to the nearest token and travel with it during the merge.

I didn’t set out to implement OT for its own sake. Transforming batched diffs simply turned out to be an elegant way to merge the outputs of two Myers diffs. A CRDT could achieve the same result. But when all you can observe is the final state, merge quality is limited by the underlying two-way diffs, regardless of the machinery used to combine them.

How to implement a syncer

The library’s merging primitive can support a wide range of text-syncing apps, including ones inspired by differential synchronisation¹⁰. A simple starting point is Git’s fetch-merge-push loop, with reconcile-text handling conflicts automatically. An implementation could work as follows:

The server keeps immutable versions of each document, each with a unique ID, and tracks which is the latest. Each client has an editable file and remembers the ID and content hash of the last server version it incorporated. Let’s call that version the base. The client gets it from an initial fetch; after that, it only needs to fetch the base’s text when a merge is necessary.

For each document, the client runs one sync loop at a time:

1. Check for local edits. Take a snapshot of the file and compare its hash with the base’s hash. If they differ, push the snapshot along with the base’s ID to the server.

2. Accept if the server hasn’t moved on. The server saves the snapshot only if the base is still its latest version. Checking the ID, saving the new version, and making it the latest happen atomically. Otherwise, it rejects the push and returns its latest version’s ID and text.

3. On success, remember what was sent. Record the returned ID and the pushed snapshot’s hash as the new base. Keep the live file as it is: the user may have edited it while the request was in flight.

4. On rejection, merge locally. Fetch the old base’s text and merge it with the current file and the server’s latest text. Record that latest server version’s ID and hash as the new base. The local merge¹¹ is just the same three-way call as before:

   file = reconcile(base, file, latest.text).text;

After either outcome, check for local edits again. A merge may need pushing, and so may edits made during a successful push. The loop pauses once the file’s hash matches the base’s hash, then wakes on local edits, a timer, or a server notification. The timer or notification triggers a fetch: if the server’s version ID has changed, merge and update the base as above, even if the local file hasn’t changed.

Extensions

A real sync app also needs to handle lost responses and application crashes. Giving each push a unique idempotency key lets the client safely retry it: if the server already accepted it, the server can return the original acknowledgement.

To save bandwidth after a merge, the client can use to_diff¹² to send only the changes relative to the fetched server version. The server reconstructs the snapshot with from_diff¹³ and its stored copy of that version.

If fairness becomes an issue, we can let a high-latency client lease a server-side lock long enough to get its edits through.

Where reconcile-text sits among alternatives

diff3 and git merge-file do the hard work of merging but explicitly don’t resolve most write-write conflicts. Neil Fraser’s diff-match-patch is the closest tool in spirit, but it applies two-way patches heuristically rather than reasoning over a common ancestor and both edited versions. So failed patches can lose edits. 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 the niche reconcile-text fills: syncing systems that need automatic merges but only have snapshots to work with.

One implementation, many ecosystems

The Rust library 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. Since React Native’s Hermes engine doesn’t support WebAssembly, that entry point ships a pure-JavaScript build produced by Binaryen’s wasm2js.

1. a solved problem when you control the whole editing stack: https://marijnhaverbeke.nl/blog/collaborative-editing-cm.html↩
2. conflict-free replicated data types: https://crdt.tech/↩
3. operational transformation: https://sigmodrecord.org/1989/06/15/concurrency-control-in-groupware-systems/↩
4. Obsidian: https://obsidian.md/↩
5. git merge-file: https://git-scm.com/docs/git-merge-file↩
6. https://reconcile.schmelczer.dev/↩
7. Ink & Switch’s Peritext¹⁶ is a good write-up on this problem for rich text.↩
8. diff3: https://blog.jcoglan.com/2017/05/08/merging-with-diff3/↩
9. Myers’ diff algorithm: https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/↩
10. differential synchronisation: https://neil.fraser.name/writing/sync/↩
11. local merge: https://git.schmelczer.dev/andras/reconcile/src/commit/08a656c6ed32d7c307b36bc6dec0134c40ac0a43/reconcile-js/src/core.ts↩
12. to_diff: https://git.schmelczer.dev/andras/reconcile/src/commit/08a656c6ed32d7c307b36bc6dec0134c40ac0a43/src/operation_transformation/edited_text.rs#L406↩
13. from_diff: https://git.schmelczer.dev/andras/reconcile/src/commit/08a656c6ed32d7c307b36bc6dec0134c40ac0a43/src/operation_transformation/edited_text.rs#L475↩
14. wasm-bindgen: https://docs.rs/wasm-bindgen↩
15. PyO3: https://pyo3.rs/↩
16. Peritext: https://www.inkandswitch.com/peritext↩