クロノフォルド：バージョン付きテキストのためのデータ構造

本記事では、歴史的なデータ構造である**「ウィーブ（Weave）」構造**に基づいたシンプルなバージョン管理システムの設計手法について解説します。複雑を追求するのではなく、堅牢でシンプルな前提条件から優れたシステムを構築するアプローチを提案します。

なぜウィーブなのか：シンプルさの重要性

進歩は通常、「単純なものから複雑な事物への変化」として捉えられがちですが、長期的には新しいアイデアや技術が**「単純な設計」の実現**を可能にします。

• Git リポジトリのような驚くほどシンプルな構造こそが、洗練された機能の土台となります。
• 複雑なアプリケーションが生まれる土台となる、シンプルで堅牢な前提条件

ウィーブ（Weave）構造とは

ウィーブは、ファイルのリビジョンを再構成するための命令の一連です。各命令は「型」と「演算子」からなり、XML や JSON と異なり、ブロック同士が重なり合うことができます。

命令の定義

Line

BeginInsert

BeginDelete

End

実装の工夫（Go）

• 整数ベース: 文字列ではなくラインインデックスを使用することで、データサイズを縮小し命令を統一します。
• 重なり可能: 異なるバージョンのブロックが空間的に重なることを許容しています。

    ⎧ Insert v1
    ⎪ 1
  Δ1 ⎨ Delete v3  ⎫ (v3 は v1 と v2 の双方に依存)
    ⎪ 2          ⎪
    ⎩ End v1     ⎪
    ⎧ Insert v2  ⎬ Δ3
    ⎪ 3          ⎪
    ⎪ 4          ⎪
  Δ2 ⎨ End v3     ⎭
    ⎪ 5
    ⎪ 6
    ⎩ End v2
  

重要: ウィーブ内ではバージョンは互いに依存しており、単なる命令の列では依存関係を推測できません。多くのシステムはこれを**「アクティブセット（Activation Set）」**で表現しています。

アクティブリビジョンセット（ActiveSet）

システムが特定のバージョンを復元する際、ファイルの内容に寄与するデルタのコレクションを計算する必要があります。これをアクティブセットと呼びます。

• 役割: 街路灯のようなもので、切り替えることでウィーブの一部を表示・非表示にします。
• 構成要素:
  • 複数の親を持つリビジョン（マージコミット）に対応可能。
  • 親の番号 < 子の番号であるため、循環参照を防ぐ。
  • 子版をアクティブにする際、すべての親も自動的にアクティブになる（グラフ走査が必要）。

アクティブセットの計算ロジック

type VersionID int
type ActiveSet []bool

// バージョン v のアクティブセットを取得：v の自分自身と、すべての子孫版を true にする
func activeSetForVersion(versions []Version, v VersionID) ActiveSet {
    // 実装省略...（スタックベースのグラフトラベル）
}

リビジョンの再構築（Reconstruction）

Reconstruct

アルゴリズム流程

1. 指示リストのスキャン: 全命令を順に処理。
2. 優先キューの維持: オープンしているブロック（Insert/Delete）を追跡。
   • Insert ブロック：アクティブ版で開かれた場合、キューへプッシュ（ラインコピー待ち）。
   • Delete ブロック：アクティブ版で開かれた場合、削除対象にマーク。
3. ラインの抽出: プライオリティキューの最上部がアクティブなら、そのラインを出力。

Go の実装ポイント

• ソート済みスライス: 大量データを扱うヘープ（配列リストなど）を避け、メモリ効率を向上させるため。
• エラーハンドリング: ブロックの不整合（誤ったネストや未終了ブロック）を検出して早期に停止。

// Reconstruct は有効なライン命令のマスクと、そのラインを導入したバージョン ID を返します。
func Reconstruct(
    instructions []Instruction,
    activeSet ActiveSet,
) (mask []bool, versions []VersionID, err error) {
    // 実装詳細...（優先キューによるブロック管理）
}

デルタの計算（Diff Script）

2 つのシーケンスを変換するための最小限の変更命令（Insert/Delete/Keep）を算出するDiff スクリプトを作成します。

LCS アルゴリズム（最長共通部分列）

1. LCS テーブル作成: 動的計画法で計算。

   lcs[i][j]

   は

   a[i:]

   と

   b[j:]

   の最長共通部分列の長さ。
2. アクションの復元: テーブルを遡上し、一致する場合は Keep、不一致の場合は Insert/Delete を決定。

func DiffScript(a, b []int) (script []Delta) {
    // LCS テーブルの構築とバックトラックによる操作の生成
}

補足: 実用的なシステムでは Myers Diff や Patience Diff を使用することもありますが、基本的な原理は同様です。

ウィーブへのデルタ適用（Interleave）

計算されたデルタを既存のウィーブに統合し、新しいウィーブを作成します。

Interleave

1. マスクされていない命令: そのまま出力へコピー。
2. マークされたライン: デルタアクションを確認。
   • Insert: 新しいラインを追加し、

     BeginInsert

     /

     End

     で囲む。
   • Delete:

     BeginDelete

     を開き、既存のアクティブラインをコピーして削除処理を行う。
   • Keep: 入力をそのまま通り過ぎる（アクションが発生しない場合）。

func Interleave(
    instructions []Instruction,
    activeSet ActiveSet,
    deltas []Delta,
    v VersionID,
) (out []Instruction, err error) {
    // 実装詳細...
}

デルタの抽出（ReconstructDelta）

特定のバージョンで何が変わったかを効率よく把握するため、デルタを直接抽出します。

• 非効率的な方法: 過去と現在の状態をそれぞれ復元して差分を取る。
• 効率的な方法: アクティブセットの違いに基づいて変更を検出（

  Reconstruct

  を活用）。

func ReconstructDelta(
    instructions []Instruction,
    beforeSet, afterSet ActiveSet,
) (deltas []Delta, err error) {
    // 2 つのアクティブセット間のライン変化を比較して Insert/Delete/Keep を生成
}
// 特定バージョン v のデルタ抽出例：
// vDelta, _ := ReconstructDelta(instructions, vSet.Deactivate(v), vSet)

システムの可能性と歴史的文脈

この仕組みは、現代のシステムにも深い影響を与えています。

• BitKeeper: Git が BitKeeper から借用した思想的な基盤であり、sccs の直接的な後継者としてウィーブを使用していました。
• Git: sccs を直接継承していませんが、思想や構造の単純さを重視する姿勢で共有しています。
• CRDT / Pijul: 履歴表現としてのウィーブ類似構造を採用し、同時性による衝突解決を可能にしています。

"そのシステムは影響力がありましたが、論文自体は重要ではありませんでした。最も重要だったのは、ソフトウェアの進化を追跡でき、そして追跡すべきだという思想でした。" — マルク・J・ロックハインド

今後の課題

このシンプルなアーキテクチャをさらに発展させるための研究方向性：

1. 命令キューの非対称性の解説: なぜ不活性な

   BeginInsert

   をプッシュするが、不活性な

   BeginDelete

   は無視するのか。
2. 単一ファイル VCS の構築: ウィーブアルゴリズムを組み合わせて実装する。
3. 履歴腐敗検出の拡張: データ整合性を自動的に検証する機能を実装する。
4. 双方向マージの実装: 任意の 2 つのバージョン間のマージ処理を可能にする。
5. リポジトリ単位の対応: 単一ファイルから複数ファイルを扱うシステムへ拡張する。