Weave — одна из самых переизобретаемых структур данных в истории. Её придумал Марк Рочкайнд в начале семидесятых для системы SCCS (Source Code Control System). SCCS работала с одним файлом за раз и хранила все его версии в одном переплетении (weave). Weave — это просто последовательность инструкций для восстановления любой версии файла. Инструкция состоит из типа (Line, BeginInsert, BeginDelete, End) и операнда — номера строки или номера версии. Строки в инструкциях хранятся как индексы в глобальном пуле, а не сами строки — так компактнее.
Блоки в weave могут перекрываться: если v1 добавила строки 1 и 2, v2 — 3–6, а v3 удалила 2–4, дельта v3 накладывается на обе предыдущие. Сама по себе структура не хранит зависимостей между версиями — их задают активационные наборы (active sets). Функция Reconstruct идёт по инструкциям с приоритетной очередью: если открывается insert-блок (любой) или delete-блок активной версии, он попадает в очередь. Строка копируется в результат, только если верхний блок очереди — активный insert.
Новые изменения добавляются через Interleave. Она получает дельту (набор действий Insert/Delete/Keep) и вплетает её в weave, идя по инструкциям и дельтам параллельно. Дельту для конкретной версии можно вытащить обратно функцией ReconstructDelta — она сравнивает битовые маски активных строк до и после применения версии.
Для генерации дельт используется алгоритм LCS (Longest Common Subsequence). Функция DiffScript строит таблицу динамического программирования, а потом проходит по ней, выдавая действия. В реальной системе, конечно, лучше взять Myers diff или patience diff от Брэма Коэна.
У SCCS была огромная тень. Git не использовал weaves напрямую, но его предок — BitKeeper, система, на которой жило ядро Linux с 2002 по 2005 год, — был прямым потомком SCCS и работал на weaves. Сегодня конфликт-фри реплицируемые типы данных (CRDT) и система контроля версий Pijul используют структуры, подозрительно похожие на weaves, потому что такое представление истории проще разрешает конфликты. Ирония: SCCS сама не умела мержить.