Interleaved Deltas
a day ago
- #weaves
- #SCCS
- #version-control
- Interleaved deltas or weaves, developed in SCCS, store revisions in a data structure with instructions like Line, BeginInsert, BeginDelete, and End, using line indices for efficiency.
- Weaves allow overlapping blocks, making version dependencies ambiguous; activation sets (active revision sets) determine which deltas contribute to reconstructing a specific revision.
- Reconstructing revisions involves scanning instructions with a priority queue to manage overlapping blocks, outputting active lines based on the current block's status.
- Deltas are computed using algorithms like LCS to find minimal transformations between sequences, enabling diff scripts with actions such as Insert, Delete, or Keep.
- Weaves are extended by incorporating new deltas via a parallel traversal of existing instructions and delta actions, adding appropriate blocks for inserts or deletes.
- Deltas can be reconstructed directly from weaves using bit masks from the Reconstruct function, avoiding the need to diff entire file outputs.
- SCCS influenced modern systems like Git via BitKeeper, with concepts similar to weaves appearing in conflict-free replicated data types and tools like Pijul.
- The article concludes with exercises to deepen understanding, such as explaining queue behavior in Reconstruct and building a simple version control system.