Interleaved Deltas

Summary

✑2026-05-22dsa 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. 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...