Quill Sync: Three-Way Merge for Offline Notes

Quill Sync: Three-Way Merge for Offline Notes

You've joined the sync team behind Quill, a notes app that lets people edit documents offline on several devices. notesync is the server-side service: it keeps every version of every document, remembers the version each device last synced against (its base), and reconciles a device's copy with the server's copy using a line-based three-way merge (diff3 style). Support has two escalations open and three features are queued behind them. A document is a list of lines.

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh server and returns one result per operation. Every operation is [name, *args]. Errors are returned as "error: <code>" strings, never raised. There are no timestamps; operations simply happen in order.

• doc and device are non-empty strings; the device name "server" is reserved (it means "the server's copy" in read and digest). Wrong arity or a wrongly typed argument is invalid arguments.
• A body (used by create and by the insert edit) is a list of lines (strings without "\n"), or a generator object: {"gen": ["row ", 3]} is ["row 0", "row 1", "row 2"]; {"cycle": ["x", "y"], "count": 5} is ["x", "y", "x", "y", "x"]. Anything else is malformed (counts are non-negative integers, at most 20,000). The empty document is [].

create also gives the creating device a working copy of version 1; clone gives another device a copy of the current head. where is "server" (the head) or a device that has a copy. A device edits only its own copy. edit applies an edit script (list of edits, applied in order, each seeing the result of the previous ones; indices are 0-based and edits.py has the exact forms: set, insert, delete, suffix_every). A script is all-or-nothing: if any edit is malformed or out of range, bad edit is returned and the copy is untouched. A non-list edits is invalid arguments.

What sync does

The device's copy is *A*, its base version *V*, the server head *H*. Compare lines exactly.

conflicts is the number of conflict hunks (0 unless status is conflict). While a copy contains a line equal to <<<<<<< device or >>>>>>> server, sync for it returns unresolved conflicts until the user edits those lines away.

The diff under the merge

diff_changes(old, new) returns the regions where new departs from old as Change(old_start, old_end, new_start, new_end) (old[old_start:old_end] was replaced by new[new_start:new_end], and a pure insertion has old_start == old_end). The alignment is an LCS chosen by a fixed walk, written out in the diff.py docstring: matching equal lines front to back, and on a mismatch preferring to delete the old line when lcs[i+1][j] >= lcs[i][j+1]. Example: diff_changes(["x"], ["x", "x"]) is one insertion at old position 1 (the *first* x is the one that is matched). Everything below depends on exactly these boundaries.

Part 1 — Fix NS-2291 and NS-2305

Support reports:

1. NS-2291 "Two of us edited *neighbouring* lines of the same note offline and sync reported a conflict, even though we never touched the same line." Worse: when one person's change overlapped several of the other's, the conflict block contained text twice.
2. NS-2305 "After I edited my copy of a note, the *server's* version changed, my own edits vanished when I synced, and the read I made earlier now shows different text." A script that failed halfway through also left half its edits behind.

Rules (these define a correct merge3; merge.py currently implements them only partly)

1. Diff the device copy and the server copy each against the base. A *device change* and a *server change* are linked when they cannot be applied independently:

• both replace or delete lines and share at least one base line; or
• one is a pure insertion lying strictly inside the base lines the other replaces or deletes; or
• both are pure insertions at the same base position.

Changes that merely touch are independent: one ends on the base line where the other starts, or an insertion sits at the edge of the other's region (before its first or after its last base line). Independent changes both apply. In the output, an insertion at a position comes before a replacement that *starts* there and after one that *ends* there.

1. Linked changes are grouped transitively into a *cluster* (a device change that overlaps two server changes puts all three in one cluster, and so on). A cluster covers base lines [start, end) (start == end for a pure insertion), from its earliest start to its latest end.
2. For each cluster compute *the device's text* and *the server's text* for that region: the lines of that side's version that correspond to base lines start..end once all of that side's changes in the cluster are applied (lines between its own changes included).

• A cluster with changes from only one side: that side's text is used.
• Both sides: if the two texts are identical, they agree and the text is used once (this covers both sides deleting the same lines and both making the same edit). Otherwise it is a conflict and the output gets, with those exact marker lines:

<<<<<<< device
     (device's text)
     ||||||| base
     (base lines start..end)
     =======
     (server's text)
     >>>>>>> server

A side whose text is empty leaves its part of the block empty (the markers stay).

1. Lines outside every cluster are copied unchanged.
2. A device's copy, the server's versions and the lists read returns never share state: editing a copy never changes a stored version or an earlier result, and a pushed or merged version never changes when the device keeps editing.

Examples (bob and alice both cloned version 1)

[["create", "plan", "alice", ["intro", "goals", "plan", "risks", "notes"]], ["clone", "plan", "bob"],
 ["edit", "plan", "alice", [["set", 1, "goals (v2)"]]], ["edit", "plan", "bob", [["set", 2, "plan (v2)"]]],
 ["sync", "plan", "alice"], ["sync", "plan", "bob"], ["read", "plan", "bob"]]

returns [1, 1, 5, 5, ["pushed", 2, 0], ["merged", 3, 0], ["intro", "goals (v2)", "plan (v2)", "risks", "notes"]].

Base a b c d e f g. Alice deletes b c and changes f to F; Bob replaces c d e f with new1 new2 (Bob's script: delete 2 4, then insert 2 [new1, new2]; as a diff against the base his copy is a b new1 new2 g, a single change over base lines c..f). Alice syncs first, then Bob: Bob's one change overlaps Alice's two, so all three form one cluster over base b..f:

["pushed", 2, 0]   /  ["conflict", 2, 1]
Bob's copy: ["a", "<<<<<<< device", "b", "new1", "new2", "||||||| base", "b", "c", "d", "e", "f",
             "=======", "d", "e", "F", ">>>>>>> server", "g"]

Part 2 — Whitespace-insensitive sync (NS-318)

Autoformatters and mobile keyboards re-indent and re-space lines, producing conflicts nobody can read. sync gets an optional third argument, {"ignore_whitespace": true}: ["sync", doc, device, {"ignore_whitespace": true}]. The options object may contain only that key, whose value must be a boolean (false and {} behave exactly like no options); anything else is invalid arguments. This is checked first, before doc not found.

With the option on, line equality becomes equality of keys, where the key of a line is its text with leading and trailing whitespace removed and every run of whitespace characters (spaces, tabs, any str.split() whitespace) collapsed to one space. So "a b ", "\ta b" and "a b" are the same line, and "" equals " ".

Rules (everything else from Part 1 is unchanged)

1. The diff walk, and therefore both sets of changes, compares lines by key. A line that was only reformatted is not a change.
2. "Agree" in a cluster means the two texts are equal line by line *by key*.
3. The output keeps original text, never keys:

• a line outside every cluster comes from the device if the device's text for it differs from the base line's text (exact comparison), otherwise from the server's copy; so when both reformatted a line the device's spacing is kept, and when only the server did, the server's is;
• a cluster with one side's changes emits that side's text verbatim;
• an agreed cluster emits the device's text;
• conflict blocks contain the raw lines of every side.

1. Which row of the sync table applies is judged on exact text, even with the option on: a copy that differs from its base only in whitespace is still "edited" (it is pushed as a new version), and absorbed means the merge result is exactly the head's text.

Example (bob cloned version 1; alice pushed version 2)

[["create", "soup", "alice", ["# Soup", "2 cups water", "1 onion", "salt"]], ["clone", "soup", "bob"],
 ["edit", "soup", "alice", [["set", 2, "1 red onion"]]],
 ["edit", "soup", "bob", [["set", 1, "2 cups  water "], ["set", 2, "1\tonion"]]],
 ["sync", "soup", "alice"], ["sync", "soup", "bob", {"ignore_whitespace": true}], ["read", "soup", "bob"]]

returns [1, 1, 4, 4, ["pushed", 2, 0], ["merged", 3, 0], ["# Soup", "2 cups water ", "1 red onion", "salt"]]. Without the option the same sync is a conflict over lines 2..3.

Part 3 — Version history and line blame (NS-342)

Three new read-only operations (the routes already exist):

device is the device whose sync created the version and kind is "create", "push" or "merge". fast-forward, up-to-date, absorbed and conflict syncs create no version. version, first and last must be integers (else invalid arguments); line out of range means not 1 <= first <= last <= (line count of that version).

Who last touched a line is decided when a version is created and never changes:

1. create: every line belongs to the creating device.
2. push: diff the previous head against the pushed copy (the same walk, with the same equality as the sync used). Lines matched to a head line keep that line's blame; all other lines of the new version belong to the pushing device.
3. merge, line by line of the merge result:

• base lines outside every cluster keep the base version's blame for that line, even when the text itself came from a side that only reformatted it;
• lines of a cluster with only the device's changes belong to the syncing device;
• lines of a cluster with only the server's changes keep the head's blame for those lines;
• lines of an *agreed* cluster belong to whoever the head says wrote them: the server got there first, so the device's identical change earns no credit (the text shown is still the device's). Line *k* of the device's text corresponds to line *k* of the server's text.

Example (continuing the Part 1 style: bob cloned version 1)

[["create", "plan", "alice", ["intro", "goals", "plan", "risks"]], ["clone", "plan", "bob"],
 ["edit", "plan", "alice", [["set", 1, "goals v2"]]],
 ["edit", "plan", "bob", [["insert", 4, ["appendix"]], ["set", 3, "risks (bob)"]]],
 ["sync", "plan", "alice"], ["sync", "plan", "bob"],
 ["history", "plan"], ["blame", "plan", 3, 1, 5], ["blame", "plan", 1, 1, 4], ["show", "plan", 2]]

returns [1, 1, 4, 5, ["pushed", 2, 0], ["merged", 3, 0], [[1, "alice", "create"], [2, "alice", "push"], [3, "bob", "merge"]], ["alice", "alice", "alice", "bob", "bob"], ["alice", "alice", "alice", "alice"], ["intro", "goals v2", "plan", "risks"]].

Part 4 — Long notes (NS-361)

Some customers keep their whole life in one note. Hidden tests use notes of two to three thousand lines edited in many places on several devices, mass reformatting passes, and histories of dozens of versions that are blamed over and over. diff.py builds a full n x m table and times out; replaying history for every blame query does too.

Goal: make all of it fast without changing a single result. The alignment must stay exactly the one in the diff.py docstring, so every hunk boundary and every blame stays identical to today's (for the notes that today's code can still handle).

Rules

1. Equal leading lines are always matched by the walk, so skipping them is safe. Skipping the *trailing* equal lines is not: diff_changes(["a","x"], ["b","x","x"]) is two changes, Change(0,1,0,1) and Change(2,2,2,3) (the first x is matched), but trimming the common suffix first yields the single change Change(0,1,0,2). Likewise a Myers-style diff may choose another among the equally long alignments. Repeated lines (list items, blank lines, rulers) are common in notes and the tests include them.
2. read with a window and digest exist so large results can be checked cheaply; they are unchanged.
3. Earlier Parts must keep working exactly, with and without ignore_whitespace.

Notes

• config.py, errors.py, models.py and textlines.py are known-good (Part 2 may add helpers).
• You may use the AI assistant freely; you are expected to verify what it produces. A random differential test against the current diff_changes is a cheap way to do that.
• Later parts must not break earlier ones; hidden tests re-check earlier behaviour.
• Parts 1-3 is a strong result. Part 4 is a stretch.