Git 最初のコミットを Go で再実装した話
前回の記事 Git 最初のコミット e83c516331 を読むで Git の基本的な仕組みを学んだ。この一環として C で書かれているオリジナルの Git の initial commit（以下、最初の Git と呼ぶ）を Go で再実装したので、この記事に記録を残しておく。
ソースコード自体は基本的に最初の Git と同じことをやってるだけで LLM に頼めば一発で生成してくれるので特に面白くない。そのため、本記事では再実装版を動かして得た学びを中心に書くことにする。
成果物
https://github.com/lyohe/initial-git-go
Docker コンテナで動かす。
mkdir -p work
docker build -t initial-git-go .
docker run --rm -it -v "$PWD/work:/work" initial-git-goGit の initial commit を動かした環境については前回の記事を参照。注意点として、これは実際に Git の initial commit がされたときの環境ではない。つまり、厳密にいえば当時の環境を再現できていない。
復習: Git とはそもそも何なのか
最初の Git は本質的に object database と current directory cache の2つの概念で表現できる。
The Object Database
環境変数 SHA1_FILE_DIRECTORY のパスに配置される content-addressable な object の集合。
content-addressable とは、object 自身がその content の SHA-1 ハッシュによって名付けられることを指す。全ての object は zlib で圧縮され、圧縮後の SHA-1 ハッシュで識別される。object には以下の 3 種類がある。
blob: バイナリデータの塊で、ファイルの内容を指す objecttree: パーミッション/ファイル・ディレクトリ名/blob または tree ハッシュ のリストで、ディレクトリ構造を指す object。これを再帰的に積み重ねることでリポジトリ全体の構造を示すことができるchangeset: 変更内容、親となる changeset、変更内容に対するコメントを示す object。README では changeset という名前だが実際にはcommitを意味している
全ての object は SHA-1 でハッシュされているので、再度ハッシュして突合することで壊れたり改竄されていないことを信頼できる。
Current Directory Cache
ある時点の仮想ディレクトリ状態を表す単純なバイナリで、.dircache/index に配置される。コミット前に tree object を生成する際の元データとなる。
名前・日付・パーミッション・内容（Blob）を関連付けた配列を保持し、常に名前順に並び、名前は一意となる。これにより、以下を効率的に行える。
- 再構成: キャッシュ状態（blob や tree）を完全に再生成できる
- 差分検出: 未コミットの tree と実際のディレクトリとの差分を効率的に検出できる
cache は対応する tree の SHA-1 が分かれば復元でき、編集したファイルだけを部分的に更新できる。
再実装版を動かしてみていくつか差分を見つける
変わる SHA-1
最初の Git では zlib で圧縮してから SHA-1 を計算して object の id とする。圧縮の実装が違えば圧縮後のバイナリも異なるから、SHA-1 も変わってしまう。最初の Git はそもそも Linux カーネル開発のために作られたツールで、各自のマシンに同じ zlib 実装が入っていて問題になりにくかったのかもしれない。今回は Ubuntu:22.04 の zlib 実装を使った（Dockerfile は前回の記事を参照）ので、厳密に言えば当時の環境とは異なる。
なお、現在の Git では未圧縮のファイル内容等からハッシュを計算した上で圧縮するので、圧縮の実装が異なっても元のファイル内容が同じであれば基本的には同じハッシュが生成される。
Go で再実装するときには標準ライブラリ compress/zlib を使って圧縮したが、当時の実装と異なるから圧縮後の文字列が変わり、全く同じファイルを commit しても異なる SHA-1 の object が生成されてしまう。
全く同じ内容の test.txt というファイルを作る。
$ echo "Hello,world!" > test.txtオリジナルの git の e83c516331 コミットで init-db して update-cache した上で index を hexdump してみる。これにより、test.txt の blob object の SHA-1 ハッシュが分かる。
# init-db
defaulting to private storage area
# update-cache test.txt
# hexdump -C .dircache/index | head -n 40
00000000 43 52 49 44 01 00 00 00 01 00 00 00 d7 d7 0b 33 |CRID...........3|
00000010 3d 35 e7 aa 6d c7 b5 87 fa cf 0c d8 0b 13 b1 17 |=5..m...........|
00000020 86 7a 58 69 e2 f4 07 03 64 7a 58 69 0a 89 43 23 |.zXi....dzXi..C#|
00000030 2b 00 00 00 10 00 00 00 a4 81 00 00 00 00 00 00 |+...............|
00000040 00 00 00 00 0d 00 00 00 87 6b c5 78 8f 4e d7 e4 |.........k.x.N..|
00000050 ac 29 83 3a a8 2a d2 94 6d a7 7c c3 08 00 74 65 |.).:.*..m.|...te|
00000060 73 74 2e 74 78 74 00 00 |st.txt..|
00000068前回の記事を参考にするとハッシュは 73 バイト目からだから 87 6b c5 78 8f... であることが分かる。
しかし、私が作った Go 実装だと f6 c4 bf 11 5e... となっている。
# hexdump -C .dircache/index | head -n 40
00000000 43 52 49 44 01 00 00 00 01 00 00 00 3b b9 af 22 |CRID........;.."|
00000010 5f ce 5f 2b 8e 86 33 cf 7c 93 b1 df 3b 38 f1 14 |_._+..3.|...;8..|
00000020 7e 7a 58 69 bf 4a f8 09 73 7a 58 69 35 45 65 1a |~zXi.J..szXi5Ee.|
00000030 2b 00 00 00 0a 00 00 00 a4 81 00 00 00 00 00 00 |+...............|
00000040 00 00 00 00 0d 00 00 00 f6 c4 bf 11 5e 93 28 64 |............^.(d|
00000050 86 e4 7b f6 15 ba 9f 9d 02 4c f2 be 08 00 74 65 |..{......L....te|
00000060 73 74 2e 74 78 74 00 00 |st.txt..|
00000068どの zlib 圧縮も RFC1950/1951 の仕様に従って実装されているはずだが、実は同一の入力に対して圧縮結果のビット列が一致することは要求されていない。
例えば Go の標準ライブラリの compress/zlib では、現在の実装ではデータを示すブロックとは別に終端用の空の最終ブロックを追加する。Hello,world!\n のような短い入力では、Ubuntu 22.04 上の libz とは圧縮後のバイト列が異なることを確認できた。一方、libz は。
例えば Go の標準ライブラリの compress/zlib では、現在の実装ではデータを示すブロック（圧縮データを分割して保持する単位）とは別に終端用に特定のバイト列を追加する。Hello,world!\n のような短い入力では、Ubuntu 22.04 上の libz は最後のデータブロック自体を final として閉じられるため、両者は同じ内容を正しく表現していても異なるバイト列になり得る。もっと一般には、一致探索やブロック分割の違いでも圧縮結果は変わり得る。
RFC 外の詳細な実装については、用途によって差分が生じている。Go の標準ライブラリの方はストリーミングを想定して作られていて、ストリームを close した時に終端用の特定バイト列を追記するのでタイミングが異なる。
古くからある標準的な圧縮形式であっても、仕様が固定しているのは「どう展開できるか」であって「どう圧縮するか」の細部ではない。初期 Git のように圧縮後のバイト列そのものを hash 化する設計では、こうした実装差がそのまま object id の差として現れる。
変わる index の byte order
最初の Git の .dircache/index は「CPU ネイティブの byte order」で保存される。より正確に言うと、struct cache_header や struct cache_entry のメモリ表現をそのまま書き出しており、byte order だけでなく整数型のサイズや struct のレイアウトにも依存している。ポータビリティは考慮されておらず、これはソースコード中のコメントでも明記されている。
一方、Go で再実装した版では binary.LittleEndian を使って index を組み立てている。これは実装としては分かりやすく big-endian 環境でも一貫して動作するが、「その CPU のネイティブ表現を書き出す」という元の方針とは少し異なる。
x86_64 や arm64 のような現在主流の環境はほぼ little-endian なので普段は問題になりにくいものの、big-endian 環境まで含めて考えると最初の Git と再実装版の index は非互換になり得る。また、最初の Git の同じソースからビルドしたバイナリでも CPU の byte-order が異なれば index は非互換になる。
もっとも、これは Git の本質的な設計差分というより、index をどこまで「移植性のあるファイル形式」として扱うかの違いである。Git にとって index はあくまでローカルな cache であり、永続的かつ可搬なデータフォーマットである必要はなかった。そして、ユーザーはカーネル開発者のみだったから作業環境もほぼ統一されていたと思われるから、仮に cache を共有していたとしても大きな問題にはならなかっただろう。
変わる cat-file の出力ファイル名
cat-file は object の中身を標準出力するのではなく、一時ファイルに展開してそのファイル名を表示する。最初の Git では mkstemp を使って temp_git_file_XXXXXX というテンプレートからファイル名を生成するため、XXXXXX の部分がランダム文字列に置き換わる。
Go 版では標準ライブラリの os.CreateTemp をそのまま使っている。これは現行の Go の実装では1~10桁のランダムな数値を生成する（API の仕様として保証しているわけではなく、デフォルト挙動の実装がそのようになっている）から、ファイル名の規則は完全には一致しない。
https://go.dev/src/os/tempfile.go
// 具体例
// Go で再実装した git
# cat-file f6c4bf115e93286486e47bf615ba9f9d024cf2be
./temp_git_file_2843355975: blob
// 最初の git
# cat-file 876bc5788f4ed7e4ac29833aa82ad2946da77cc3
temp_git_file_Nyjl4f: blob最初の Git で使われている mkstemp では POSIX API なので大枠の挙動は標準化されているが、XXXXXX をどの文字列に置換するかという生成アルゴリズム自体は規定されていない。そのため、ファイル名の長さはテンプレートどおり固定される一方、実際に埋め込まれる 6 文字の内容は実装によって異なり得る。
もっとも、ここはランダムな文字列が生成されて cat-file 実行ごとに異なれば十分なので、実装によって差異があっても問題にはならないだろう。
最後に
再実装自体は LLM に頼めばすぐやってくれるのだが、実装されたものの挙動を確認して深掘りしていくのは面白かった。この記事に書かなかったこと以外にも差分はたくさんあるが、最初の Git の特徴として環境依存があるのでそれが影響するものを本記事ではピックアップしてみた。
最初の Git は環境依存の要素が多い。開発者が異なる環境を使っていれば index や object id が変わる。例えば index は CPU の byte order が変われば読めなくなる。ただ、初期は Linux カーネルの開発者しか使っていなかったので皆ほぼ同じ環境だろうし、実装をシンプルに保つことが優先されていたと考えられる。
こういったシンプルな概念で構成された小さい（小さかった）ソフトウェアの実装を辿るのは面白いのでまたやっていきたい。