Interleaved deltas

✑2026-05-22dsa

Weave structureActive revision setReconstructing revisionsComputing deltasExtending weavesReconstructing deltasConclusionExercises

A weave has a reputation of one of the most reinvented data structures in history.Victor Grishchenko, Mikhail Patrakeev, Chronofold: a data structure for versioned text Progress is often viewed as a transition from simple to complex. Although individual systems do become more complex over time, long-term progress happens when new ideas and advances in hardware make simple designs feasible. Think of the simplest version control system you can imagine. It probably stores project snapshots in a backup directory. Maybe it compresses files for efficiency. Add hashing for content addressing, and the sketch starts to resemble Git. I don’t mean this as an insult to Git; quite the opposite: the structure of a Git repository is stunningly simple. It’s so simple in fact, that you’ll be surprised at the sophistication of the things you can do with it. But that’s the way the best code will always be: simple, solid premises out of which complex applications arise.Wincent Colaiuta, A look back: Bram Cohen vs Linus Torvalds The Source Code Control System (sccs), developed by Marc J. Rochkind in the early seventies, had to be more sophisticated. It operated on one file at a time and stored all its revisions in a data structure called interleaved deltas or weaves. If Git felt like something I could have invented myself, weaves captivated and intimidated me for years. When I finally found time to work out the algorithms, the resources were scarce BitKeeper wiki offers a good introduction. Bram Cohen wrote a reference implementation, but I found it impenetrable. , so I published my study for future explorers. You can find the full source code at roman-kashitsyn/weaver.

Weave structure A weave is a sequence of instructions for reconstructing file revisions. An instruction consists of a type and an operand.

Type Operand Meaning

Line Line index Output a line. BeginInsert Version number Start a block of lines added in a version. BeginDelete Version number Start a block of lines deleted in a version.

End Version number Close a block for a version. ⊕ The weave instruction type. type InstructionType int

const ( Line InstructionType = iota BeginInsert BeginDelete End )

// Instruction is a weave instruction. type Instruction struct { Type InstructionType // Payload contains the instruction payload. // For Line instructions, it's the line number. // For other instructions, it's the version ID. Payload int }

func (i Instruction) Line() int { return i.Payload }

func (i Instruction) VersionID() VersionID { return VersionID(i.Payload) }

All line instructions must belong to an Insert or Delete block. The integer in the line instruction points into the global line pool. Using line indices instead of strings shrinks the weave and makes instructions uniform. Unlike in xml or json, weave blocks can overlap. For example, if v1 adds lines 1 and 2, v2 appends lines 3–6, and v3 removes lines 2–4, then v3’s delta overlaps with deltas of the first two versions. ⎧ Insert v1 ⎪ 1 Δ1 ⎨ Delete v3 ⎫ ⎪ 2 ⎪ ⎩ End v1 ⎪ ⎧ Insert v2 ⎬ Δ3 ⎪ 3 ⎪ ⎪ 4 ⎪ Δ2 ⎨ End v3 ⎭ ⎪ 5 ⎪ 6 ⎩ End v2

Versions in a weave depend on one another. In the example above, v3 depends on both v1 and v2 because it deletes lines that they introduced. The relationship between v1 and v2 is ambiguous: v1 could be v2’s parent, or they could be independent branches that v3 merged. The weave alone is not enough to deduce dependencies between deltas. Most weave-based systems express these dependencies using activation sets.

Active revision set sccs has hierarchical revision names (1.4 and 2.1, for example).

When you check out a revision, the system uses heuristics to compute its activation set—the collection of deltas that contribute to the file content. I think of activation sets as switches controlling streetlamps on a dark avenue. Flipping them reveals or hides parts of the weave. For my experiment, I chose flat sequential revision numbering. Each revision can have one or more parents Revisions with multiple parents represent merge commits. . Parent revisions are numerically smaller than their children, so no version can be its own ancestor. Activating a revision also activates all of its parents, so computing the active set requires a graph traversal. ⊕ An active set is a collection of deltas that together make a file revision. We compute it by traversing the version graph. type VersionID int

type ActiveSet []bool

func (s ActiveSet) Contains(v VersionID) bool { return v >= 0 && int(v) < len(s) && s[v] }

func (s ActiveSet) Deactivate(v VersionID) ActiveSet { out := slices.Clone(s) out[v] = false return out }

type Version struct { ID VersionID Parents []VersionID Author string Description string Date time.Time }

func activeSetForVersion(versions []Version, v VersionID) ActiveSet { activeSet := make(ActiveSet, len(versions)+1) stack := []VersionID{v} for len(stack) > 0 { w := stack[len(stack)-1] stack = stack[:len(stack)-1] activeSet[w] = true for _, p := range versions[w-1].Parents { if !activeSet[p] { stack = append(stack, p) } } } return activeSet }

We’re now ready to tackle the version reconstruction algorithm.

Reconstructing revisions To reconstruct a revision, we compute its active set and scan the instruction list, keeping track of currently open blocks in a priority queue. If the instruction opens an insert block—for any revision—or a delete block for an active revision, we push it onto the queue. We copy lines if the block at the top of the priority queue is active (that’s why we keep inactive inserts in the queue).

We need a priority queue because blocks can overlap (see the Weave structure section for an example). If blocks were properly nested, a stack would suffice. My implementation uses a sorted slice as a priority queue for brevity (heaps require a lot of boilerplate in Go). ⊕ The Reconstruct function recovers the lines of any file version stored in a weave. var ( ErrBadWeave = errors.New("E001: malformed weave") ErrBadDelta = errors.New("E002: bad delta") )

// Reconstruct locates the lines enabled in the given version set. // It returns the boolean mask of enabled "Line" instructions // and the IDs of versions that introduced the enabled lines. // // Returns [ErrBadWeave] if the instructions aren't a valid weave. func Reconstruct( instructions []Instruction, activeSet ActiveSet, ) (mask []bool, versions []VersionID, err error) { mask = make([]bool, len(instructions)) openBlocksByVersion := make(map[VersionID]int) // activeBlocks are sorted by VersionID (ascending). var activeBlocks []Instruction activeBlock := func(v VersionID) (int, bool) { return slices.BinarySearchFunc(activeBlocks, v, func(instr Instruction, target VersionID) int { return cmp.Compare(instr.VersionID(), target) }) }

for offset, instr := range instructions { switch instr.Type { case Line: if len(activeBlocks) == 0 { return nil, nil, ErrBadWeave } top := activeBlocks[len(activeBlocks)-1] v := top.VersionID() if activeSet.Contains(v) && top.Type == BeginInsert { mask[offset] = true versions = append(versions, v) } case BeginInsert, BeginDelete: v := instr.VersionID() if _, ok := openBlocksByVersion[v]; ok { return nil, nil, ErrBadWeave } if instr.Type == BeginInsert || activeSet.Contains(v) { at, _ := activeBlock(v) activeBlocks = slices.

Insert(activeBlocks, at, instr) } openBlocksByVersion[v] = offset case End: v := instr.VersionID() if _, ok := openBlocksByVersion[v]; !ok { return nil, nil, ErrBadWeave } at, found := activeBlock(v) if found { activeBlocks = slices.Delete(activeBlocks, at, at+1) } delete(openBlocksByVersion, v) default: return nil, nil, ErrBadWeave } } if len(openBlocksByVersion) > 0 { return nil, nil, ErrBadWeave } return mask, versions, nil }

Returning the bit mask of enabled line instructions (instead of their contents) simplifies many operations, including weave extension and delta reconstruction. Before we can start adding changes to weaves, we need diffs.

Computing deltas Given two sequences of items, we want to find a transformation that turns the first sequence into the second and uses the fewest steps. The transformation is a sequence of deltas (also known as hunks) that specify an action (Insert, Delete, or Keep) and the items it acts upon. I called such a transformation a diff script. The diff algorithm I’m most familiar with is the lcs algorithm See, for example, the first section of An Algorithm for Differential File Comparison by J. W. Hunt and M. D. McIlroy. . It computes an optimal diff script in two stages:

Use dynamic programming to build the lcs table. The lcs[i][j] entry is the length of a longest common subsequence of a[i:] and b[j:]. Fill the table back-to-front in both dimensions.

Traverse the lcs table to recover the actions, moving toward lcs increase when a and b don’t align.

⊕ The DiffScript function computes an optimal edit script for two sequences of integers.

type Action int

const ( Insert Action = iota Delete Keep )

type Delta struct { Action Action Items []int }

func appendDelta(script []Delta, action Action, item int) []Delta { n := len(script) if n > 0 && script[n-1].Action == action { script[n-1].Items = append(script[n-1].Items, item) return script } return append(script, Delta{Action: action, Items: []int{item}}) }

// DiffScript computes the optimal edit script for turning a into b. func DiffScript(a, b []int) (script []Delta) { n, m := len(a), len(b)

// Build a table of lengths of LCS(a[i:], b[j:]). lcs := make([][]int, n+1) for i := range lcs { lcs[i] = make([]int, m+1) } for i := range slices.Backward(a) { for j := range slices.Backward(b) { if a[i] == b[j] { lcs[i][j] = 1 + lcs[i+1][j+1] } else { lcs[i][j] = max(lcs[i+1][j], lcs[i][j+1]) } } }

// Traverse the LCS table and reconstruct the optimal edits. for i, j := 0, 0; i < n || j < m; { switch { case i < n && j < m && a[i] == b[j]: script = appendDelta(script, Keep, a[i]) i++ j++ case i < n && (j == m || lcs[i+1][j] >= lcs[i][j+1]): script = appendDelta(script, Delete, a[i]) i++ default: script = appendDelta(script, Insert, b[j]) j++ } }

return script }

A practical system would use Myers diff or Bram Cohen’s patience diff. James Coglan, the author of Building Git, wrote a series of blog posts explaining Myers diff and patience diff in great detail.