gitを自作する

何を作るか

git init して git add して git commit するとき、.git の中で何が起きているのか。この記事ではその核心だけを取り出し、blob・tree・commit の3種類のオブジェクトを SHA-1 でハッシュして zlib 圧縮で保存する、gitの最小実装を手を動かして作ります。ゴールは git add 相当でファイルを保存し、git commit 相当で履歴を1本作り、標準の git log や git cat-file で読める状態にすることです。

作ると何が分かるか。第一に、gitが「ファイルを内容から計算したIDで名前付けするKVストア（キーバリューストア）」でしかないこと。第二に、ブランチやタグが単なる「40文字のSHAを書いた小さなテキストファイル」であること。第三に、コミット履歴がなぜ有向非巡回グラフ（DAG）になり、なぜ過去を書き換えると以降のIDが総取っ替えになるのか。この3点が腑に落ちれば、rebase も reset も detached HEAD も、grep する対象が見えるようになります。

最小実装の全体像

横にスクロール

部品は3つだけです。(1)任意のバイト列を「型付きオブジェクト」として保存し、そのIDを返す write_object。(2)IDから中身を復元する read_object。(3)ブランチ名とコミットIDを対応付ける参照(refs)。この3つの上に、ファイルを保存する add、木構造を固める write_tree、履歴を刻む commit を積みます。

保存先は .git/objects/ です。IDが40桁の16進数のとき、先頭2桁をディレクトリ名、残り38桁をファイル名にします（例 ab/cdef...）。これは1ディレクトリに数万ファイルが並ぶとファイルシステムが遅くなるのを避けるための、単純なシャーディングです。

段階を追って作る

ステップ1: オブジェクトを1個保存する

すべての土台が write_object です。gitはオブジェクトの前に 型 バイト長\0（NUL区切り）というヘッダを付けます。重要なのは、SHA-1 を計算する対象が「ヘッダ＋本体」の非圧縮バイト列であること。そのIDが決まってから、まったく同じバイト列を zlib で圧縮してファイルに書きます。ハッシュ対象と圧縮対象は同じで、圧縮は保存の直前だけ、という順序を取り違えないのが肝心です。

import hashlib, zlib, os

def write_object(obj_type, data):
    # 例: b"blob 11\0hello world"
    header = f"{obj_type} {len(data)}\0".encode()
    store  = header + data
    oid    = hashlib.sha1(store).hexdigest()   # 40桁の16進
    path   = f".git/objects/{oid[:2]}/{oid[2:]}"
    if not os.path.exists(path):               # 既存なら書かない＝重複排除
        os.makedirs(os.path.dirname(path), exist_ok=True)
        with open(path, "wb") as f:
            f.write(zlib.compress(store))       # 中身と同じバイト列を圧縮
    return oid

ヘッダにバイト長を含めるのは、本体に NUL やあらゆるバイトが現れても、ヘッダとの境界と全長が曖昧にならないためです。read_object は逆順で、zlib 展開 → 最初の NUL までをヘッダとして型と長さを取り出し、残りを本体として返します。

ステップ2: ファイルをblobにする

blob はファイルの中身そのもので、ファイル名も更新日時も含みません。だから同じ内容の2ファイルは、名前が違っても同一のblob1個に収束します（重複排除）。add はファイルを読んで write_object("blob", ...) に渡すだけです。

def hash_file(path):
    with open(path, "rb") as f:
        return write_object("blob", f.read())

ここで「名前はどこへ行った」と思うのが正しい直感です。名前とディレクトリ構造は blob ではなく、次の tree が持ちます。

ステップ3: treeでディレクトリを固める

tree はディレクトリ1階層の一覧表で、各エントリは モード 名前\0 の後ろに、子のIDを16進テキストではなく20バイトの生バイナリで連結したものです。エントリは名前でソートして並べます（ソート順が違うと別のtreeになり、別IDになる）。モードは通常ファイルが 100644、実行可能ファイルが 100755、サブディレクトリ（tree）が 40000 です。

def write_tree(entries):
    # entries: [(mode, name, oid_hex), ...]
    body = b""
    for mode, name, oid_hex in sorted(entries, key=lambda e: e[1]):
        body += f"{mode} {name}".encode() + b"\0" + bytes.fromhex(oid_hex)
    return write_object("tree", body)

これが gitが「ディレクトリのスナップショット木」を表す方法です。ルートtreeが子treeを指し、子treeがさらに孫treeやblobを指す。あるコミットのルートtreeのIDが同じなら、作業ツリー全体が1バイトも違わないと数学的に保証されます。ファイルを1個でも変えれば、そのblobのIDが変わり → 親treeのIDが変わり → ルートtreeのIDまで変わる、という連鎖が起きます。これがMerkle木（ハッシュ木）です。

ステップ4: commitで履歴を刻む

commit は「ルートtree 1個 ＋ 親commitのID（0個以上）＋ 作者・コミッタ・タイムスタンプ＋メッセージ」を持つテキストオブジェクトです。親を持つことが決定的で、これによりコミット同士が鎖でつながり、履歴が有向非巡回グラフ（DAG）になります。最初のコミットだけ親が0個、マージコミットは親が2個以上です。

tree 3c4e9c...          ← このコミット時点のルートtreeのID
parent a1b2c3...        ← 直前のコミット（最初のコミットには無い）
author  Taro <t@ex> 1718900000 +0900
committer Taro <t@ex> 1718900000 +0900

コミットメッセージ本文

def commit(tree_oid, parent_oid, author, message):
    lines = [f"tree {tree_oid}"]
    if parent_oid:
        lines.append(f"parent {parent_oid}")
    lines += [f"author {author}", f"committer {author}", "", message, ""]
    return write_object("commit", "\n".join(lines).encode())

commit は自分の中に親のIDを含みます。親のIDは親の中身から計算された値なので、親を1バイトでも書き換えると親のIDが変わり、それを含む子commitのIDも変わり…と、そのコミット以降のIDが全部変わります。これが「歴史の改竄が数珠つなぎに検出される」仕組みであり、rebase が「新しいコミット列を作り直す（元のIDは再利用できない）」操作である理由でもあります。

ステップ5: 参照(refs)とHEADで名前を付ける

ここまでで履歴は保存できましたが、40桁のIDを人間が覚えるのは無理です。そこで参照(refs)が要ります。ブランチとは .git/refs/heads/<名前> というファイルに、先端コミットのIDを40桁テキストで1行書いただけのものです。コミットするたびに、このファイルを新しいコミットIDで上書きします。

HEAD（.git/HEAD）は「今どのブランチにいるか」を示すファイルで、中身は普通 ref: refs/heads/main という間接参照です。detached HEAD 状態とは、この中身がブランチ名ではなく生のコミットIDに変わった状態にすぎません。

def update_ref(ref, oid):        # 例 ref="refs/heads/main"
    path = f".git/{ref}"
    os.makedirs(os.path.dirname(path), exist_ok=True)
    with open(path, "w") as f:
        f.write(oid + "\n")      # 中身は40桁+改行だけ

def resolve_head():              # HEAD → ブランチ → コミットID
    head = open(".git/HEAD").read().strip()
    if head.startswith("ref: "):
        ref = head[5:]
        p = f".git/{ref}"
        return open(p).read().strip() if os.path.exists(p) else None
    return head                  # detached: 直接コミットID

コミット処理の全体は「現在のHEADが指すコミットIDを親として commit() を呼び、返ったIDで現在ブランチの ref を更新する」だけです。これで git log が親をたどって履歴を表示できるようになります。

発展と本物との違い

ここまでで gitの本質（内容アドレス方式のオブジェクトストア＋refs）は完成です。では本物のgitがこの上に足しているものは何か。核心の理解には不要でも、実運用で効いてくる要素です。

第一にインデックス（ステージング領域、.git/index）。本記事は作業ツリーから直接treeを作りましたが、本物は「次のコミットに入れる状態」を保持する中間層を挟みます。git add はここへ登録する操作で、git status が作業ツリー・インデックス・HEAD の3者を比較して差分を出せるのはこの層があるからです。

第二にパックファイルと差分。ステップ1の実装は、1バイト違う10個のバージョンがあれば、ほぼ同じ内容のオブジェクトを10個丸ごと保存します（ゆるいオブジェクト＝loose object）。これは重複排除が「完全一致」しか効かないためで、放置すると肥大化します。そこでgitは多数のオブジェクトを1本のパックファイル（.git/objects/pack/*.pack）へまとめ、内容の似たオブジェクト同士を選んで差分（デルタ）圧縮します。ここで初めて「バージョン間の差分」という概念が登場する点に注意してください。

第三に整合性と衝突。オブジェクトIDにSHA-1を使うため、理論上は異なる内容が同じIDになる衝突がありえます。実際にSHA-1の衝突は生成可能になっており、現行のgitは衝突攻撃を検出する強化版SHA-1を用い、さらに SHA-256 を使うオブジェクトフォーマットへ移行を進めています。内容アドレス方式の安全性は、ハッシュ関数の衝突耐性に依存する点は押さえておくべきです。

最後に、なぜ内容アドレス方式なのかを改めて整理します。IDを内容から導くことで、(1)同一内容の重複排除が自動で効き、(2)IDがそのまま改竄検出のチェックサムになり、(3)分散環境でも中央の採番役なしに全員が同じ内容へ同じIDを付けられます。この3点が、gitが中央サーバーなしでも履歴の同一性を保証できる根拠です。より広いデータ構造やハッシュの原理はプログラミング、ファイルシステムとの関わりはOS、内容アドレス方式が支える分散の一貫性はデータベースの各トピックも参照してください。