This page shows how two copies of a notebook can be merged without conflicts in most cases, when each note is a merkle tree of blocks. It is a working model: every hash is a real SHA-256, computed in your browser, over a byte layout this page defines. Edit the Mine and Theirs text and everything recomputes.
The layout is illustrative. It shows the idea, and it is not any program's file format. burl, the note-taking program this model is drawn from, hashes different bytes and keeps more kinds of saved state. Its exact bytes and retention rules are on its own page, listed at the end. Where this page does not model a rule, it says so in place.
Plain words first; the program's own term follows in parentheses, and the section after these pictures defines each one. The pictures are drawn from the example in section 3 and change with it, so what they show and what the table shows are one computation.
A notebook here is one file holding notes. One sentence each for the terms that follow, in the order they are needed.
block-v1, note-v1, tree-v1), so one kind can never be mistaken for another.livepinStart with a task-list note, five lines. The model splits the body on newlines, and each line is a block
with its own stable id. The block's bytes are a fixed sequence of netstrings —
<byte length>:<bytes>, — beginning with the tag; a field that may be absent is written
as - when absent and + followed by a netstring when present. The block's hash is the
SHA-256 of exactly those bytes. Note that the stable id is inside the hash: two blocks with the same
text and different ids are different blocks, which is what lets a merge tell "one line retyped" from "one
line moved".
This layout is the model's own. A real store hashes more fields in a different order, and the merge works the same way.
| # | stable id | text | hash |
|---|
Click any hash or id to see the whole value. Ids on this page are derived from labels so they stay put while you type; real ones are random or time-ordered and cannot be predicted from the text.
A note's bytes are its scalar fields, then the count and hashes of its blocks in order, then the count and hashes of its child notes. No row ids and no timestamps: a wall-clock value in the hash would make two devices disagree about nothing. Editing one line therefore changes one block hash, which changes the note hash, which changes every ancestor's hash, which changes the root.
Note hash:
Notes form a forest (many notes have no parent), so the root is a synthetic object over the top-level
notes' hashes, with one optional field before them for notebook-wide settings (absent here, so
-). This example has two top-level notes: the one both sides edit, and one nobody touches (so the pictures at the top can show a branch being skipped).
Root hash:
Objects are never edited, only added, so every tree that ever existed is still in the store until garbage collection removes what nothing names. The merge needs two kinds of name:
A drain both consumes named roots and produces one. It reads the fork pin (base), live (mine) and
the copy's root (theirs), and writes the merged tree to live. Afterwards the fork pin advances to theirs' root,
not the merged root: the merged root is not an ancestor of the copy, and diffing the next drain against it would
read every home-side change as a deletion on the copy's side.
A real notebook usually names more states than these two: automatic checkpoints, undo points before a destructive write, and rules for thinning them out. The model leaves them out because the merge does not need them. burl's are on its own page.
Driven by section 3's texts. The drain is collapsed; open it to see the roots it consumed and produced. Resolving a queued conflict in section 3 appends to this list.
| name | kind | hash | reason / note |
|---|
Garbage collection walks from every row here, and additionally from the three hashes of every unresolved conflict row. Nothing reachable from those is ever collected.
Home published a copy of the note; both then edited it; now home drains the copy back. The diff between two trees descends only where hashes differ and matches notes by stable id, so a note nobody touched costs one string comparison. For a note both sides touched, its scalar fields merge per field and its body merges per block, in three tiers:
Two more rules apply in both directions: deletion loses to edit (a block one side deleted and the other edited comes back with the edit), and a block only one side ever had is kept.
Whole-body writers are scripts, importers and assistants that send the full text; an editor sends per-line edits.
An editor edit keeps the line's id. A whole-body write gives a changed line a new id in the same slot: identical text at the same index keeps the id, anything else is a new id, and extra or missing trailing lines are adds or deletes.
| # | base | mine | theirs | result | rule |
|---|
Merged body:
Free of conflicts by construction: different notes; different fields of one note; different blocks of one note; disjoint character spans of one block; identical edits made on both sides. Most of what a whole-note or whole-file sync would have flagged is in this list. Not free, and queued: overlapping spans of one block; a scalar field (title, parent, icon, format) changed differently on both sides — mine is kept and the note itself is queued; a block with rich-text formatting on either side (no text merge can reposition the spans, so it is not attempted). Not free, and not queued either: both sides reordering the same note's blocks differently — mine's order stands and the drain reports the declined reorder rather than queueing it, because a conflict row's three sides are objects that carry no ordering and would show a person two identical lines to choose between. The rule throughout is that a conflict never blocks the drain: the queue is a to-do list, not a modal.
This page simulates the block tiers and the re-mint edge; it does not simulate scalar fields, rich spans, or reorders.
The three tiers are defined over block identity. A whole-body write gives a changed line a fresh stable id, so if both files rewrite the same line that way, the drain never sees one block with two edits. It sees the base block gone on both sides and one unknown block added on each — and an added block has no base to compare with. Both survive as two lines, the text merge never runs, and nothing is queued: the drain reports zero conflicts and the note holds both versions. Press "Load the re-mint edge" above to watch it. The same two texts through the editor path (identity kept) produce one block and one queued conflict.
The order of the two survivors is decided in a real store by comparing per-device sort keys, which this page cannot know, so it shows mine first and says so.
Every row in the conflict queue names three objects by hash (base, mine, theirs), never text, and an unresolved row is itself a garbage-collection root. What the resolver shows as mine is read live from the note, because the block goes on being edited while the row waits. The person has three answers, and none of them is chosen for them: Mine writes nothing at all (mine is already in the note); Theirs writes theirs' text over the block; Edited writes text the person typed, seeded with the best composition the engine could make and the colliding span highlighted. There is no "keep both": an engine has no basis to pick an ordering, so that was dropped once a person could type instead.
Everything above happens between two files. Two programs can also write one open file, such as a person typing and an assistant writing the same line. A collision there has none of a drain's shape: no copy to reference, no fork pin, and the losing text was never stored as an object, so there is no hash to name. It gets its own queue. The rules are the same three tiers, applied against the block list the writer loaded. A collision keeps the version belonging to the person at the screen (the caller says which side that is, with no default), stores the incoming version as text, marks the line in the editor's gutter, and shows both on hover. A line can collect several incoming versions, and answering one supersedes the others. Writing both versions into the body, one under the other, would be a silent "keep both", which the drain's resolver also refuses.
The two queues are separate and have separate counts: the drain's queue says nothing about the live one and vice versa. Neither auto-resolves.
The hashes on this page are computed from the layout above, so they will not match a real .burl file.
How burl lays out its objects, how it names and thins its saved roots, and how to check a hash against your own file
are on a page of their own: How burl stores a notebook.
You can still hash any text with this page's SHA-256:
SHA-256: