最近 codecrafters というサイトで車輪を再生産するお勉強をしているのですが、そこに載っていた課題である「git clone 相当の処理がそれっぽく動く git client」を自作してみたところ学びがめちゃめちゃあったので、忘れないうちに色々とメモしておきます。

overview

git には本質的には blob, tree, commit, tag という4種類のオブジェクトからなります。これらのオブジェクトをいい感じに .git ディレクトリに格納したり、.git ディレクトリから読み出したりできれば clone の処理のそれっぽい再現までたどり着けます。なお、この中で tag の処理は全部サボっても clone は動きます。ということでやるべきことは以下のようになります。

  1. blob object を read/write できるようにする
    • hash-object ならびに cat-file コマンドに相当する
  2. tree object を read/write できるようにする
    • ls-tree ならびに write-tree コマンドに相当する
  3. commit object を read/write できるようにする
    • write は commit-tree コマンドに相当する。read 側はバチッと一致するものはなさそう。
  4. clone 時に走るサーバーとの通信プロトコルならびに到着するパケットの仕様について理解し、そのとおりに実装する

ここで名前が挙がったコマンドたちは git のコマンドたちの中では知名度が比較的低い部類だと思います。これらのような、git オブジェクトを直接操作する低レイヤコマンドたちは plumbing commands と呼ばれています。対して、我々が普段用いるユーザーフレンドリーなコマンド群は porcelain commands と呼ばれます。詳細は公式ドキュメントに書いてあります。

blob, tree, commit オブジェクト

さて、では各種オブジェクトの read/write をそのまま実装していけばいいわけですが、私が調べる限り公式ドキュメントには self-contained な形では仕様が書いてありません。以下のように、部分的な記述はこのページに見つかるのですが、実装可能な形に落とし込むには（特に tree, commit に関しては）微妙に情報が足りません。

Gitがヘッダを構築する際には、まず初めにオブジェクトのタイプを表す文字列が来ます。（中略）次に、スペースに続いてコンテンツのサイズ、最後にヌルバイトが追加されます。

最後に、zlibでdeflate圧縮されたコンテンツをディスク上のオブジェクトに書き込みます。 まず、オブジェクトを書き出す先のパスを決定します（SHA-1ハッシュ値の最初の2文字はサブディレクトリの名前で、残りの38文字はそのディレクトリ内のファイル名になります）。 

Gitオブジェクトはすべて同じ方法で格納されますが、オブジェクトのタイプだけは様々で、ヘッダーが blobという文字列ではなく、commitやtreeという文字列で始まることもあります。 また、オブジェクトタイプがブロブの場合、コンテンツはほぼ何でもよいですが、コミットとツリーの場合、コンテンツは非常に厳密に形式が定められています。

参考情報として StackOverflow に情報が転がっているのが見つかります。tree はここで、commit はここです。

commit に関しては手元の適当な git リポジトリにある commit オブジェクトを zlib inflate してから cat することでも形式がわかると思います。tree に関しては、20byte の sha1 が含まれる（いわゆる hex ではないため、UTF-8 文字列としては解釈不可能です）ので cat でうまく表示できるかわかりません。

形式がわかってしまえばあとは書くだけです。

git clone internals

という事で git clone の実装をやっていきます。とっかかりとして使えるのは git における smart http プロトコルについて解説したこのドキュメントです。

なんとなく読むと /info/refs?service=git-upload-pack への GET と /git-upload-pack への POST をすればよさそうだとわかります。前者は reference discovery, 後者は packfile negotiation と呼ばれます。http で通信しているので、手元でも例えば curl を使えばどんなレスポンスを処理すればいいかわかります。以下は私のgithubにある公開リポジトリに対してリクエストを投げてみた結果です。ヌルバイトなどが表示されていないことには注意が必要ですが気分を掴むにはこれでもいいでしょう。

$ curl -i https://github.com/xenolay/calculus_on_manifolds.git/info/refs?service=git-upload-pack --output -
HTTP/2 200
server: GitHub-Babel/3.0
content-type: application/x-git-upload-pack-advertisement
content-security-policy: default-src 'none'; sandbox
expires: Fri, 01 Jan 1980 00:00:00 GMT
pragma: no-cache
cache-control: no-cache, max-age=0, must-revalidate
vary: Accept-Encoding
date: Sat, 12 Jul 2025 09:04:16 GMT
x-frame-options: DENY
strict-transport-security: max-age=31536000; includeSubDomains; preload
x-github-request-id: 238D:32F20C:63844:87BC4:68722510

001e# service=git-upload-pack
00000155ea65a32b30d5f2753381ee5e2ee79f10200042ea HEADmulti_ack thin-pack side-band side-band-64k ofs-delta shallow deepen-since deepen-not deepen-relative no-progress include-tag multi_ack_detailed allow-tip-sha1-in-want allow-reachable-sha1-in-want no-done symref=HEAD:refs/heads/master filter object-format=sha1 agent=git/github-e744e5203bf9
0041817d20053c1925c82b81ba0a43970f9c1e9093a8 refs/heads/gh-pages
003fea65a32b30d5f2753381ee5e2ee79f10200042ea refs/heads/master
003f354857e298ecf34e162c581a40f4747eb878e25e refs/pull/11/head
003f1ad524020e26fea0851241599dba645deabfdeff refs/pull/12/head
0000

このレスポンスについては、このドキュメントにある程度仕様がまとまっています。git は「1行の先端に、当該1行の長さを4バイトで表記する」という独自規格を採用しています（そのような行のことを pkt-line といいます）。例えば上の例でいうと 001e# service=git-upload-pack\n と書かれています（末尾に改行があります）が 001e が長さにあたります。16進数表記されていますが10進数に戻すと30で、実際この行の長さは30です（001e 自体も長さに含めること、改行 LF \n は1文字であることに注意）。その他 pkt-line の細かいことはここに書いてあります。

通常であれば、このレスポンスに HEAD への reference が最初に書かれているはず（The stream SHOULD include the default ref named HEAD as the first ref）。その commit object を取得し、書かれている tree object の内容を checkout すればよいわけです。

が、そのためには当該 commit object と、 tree object ならびにその tree に含まれる blob とか tree とかを全て取得してくる必要があります。git では packfile というファイルにこの情報が書かれています。

結論だけ書くとたとえば以下のようにすると packfile を落としてローカルに保存できます。

echo -e '0032want ea65a32b30d5f2753381ee5e2ee79f10200042ea\n00000009done\n' | curl https://github.com/xenolay/calculus_on_manifolds.git/git-upload-pack -H "Content-Type: application/x-git-upload-pack-request" --data-binary @- --output packfile.pack

が packfile には deflate 圧縮された blob が含まれているので通常のテキストエディタ等では全体像を把握することは難しいです。他方で一番最初のヘッダくらいであれば UTF-8 で解釈可能な内容が書かれている（packfile 本体は PACK0002 からスタートするはずです）ので、自分の手元に降りてきたファイルが packfile かどうかくらいは目視で確認できるでしょう。

またこの時点で packfile.pack のうち PACK0002 からスタートする部分を切り出してきて index-pack すれば verify-pack が通り、この packfile に含まれているオブジェクトが取得できます。index-pack というのは packfile のパースを補助するための index file (.idx) と reverse-index (.rev) を作成するコマンドのようなのですが詳しいことは調べていません。重要なことは、packfile をパースした結果がどうなるかの答えがこれでわかるということです。私の手元の環境ですが以下のような感じで出力できました。

$ git verify-pack -v .git/objects/pack/pack-1f23b425cb9da07c669b4b128276a42f14a2138f.pack
d430e8442d0676c7e6095fba6051eedd44a9a2f0 commit 239 155 12
5dd81e7f68f8c769cae43cccd2fc75db3ef96aa5 commit 199 136 167
cc3a771dfdbd4e0b585a4e0c8017920afc3ce868 tree   37 47 303
a2d97aea4d3e7962043063f83e6a29763b6108c9 blob   37 45 350
16c24e1d49c67af0812d314a389dfac76b37d29c tree   37 48 395
ed8bdd0836a8165dd4aaa2fd7603df2eb1d817f1 blob   15 24 443
non delta: 6 objects
.git/objects/pack/pack-1f23b425cb9da07c669b4b128276a42f14a2138f.pack: ok

parsing a packfile

さてあとは packfile をパースすればいいんですが、公式ドキュメントにはあんまりちゃんと書いてありません。TODO と書いてあります。マジかよ……

C: Parse the upload-pack response: TODO: Document parsing response

私はこの記事を参考にしました。正直言うと、色々難しいです。ちゃんとした記事にまとめる気力が尽きてしまったので、実装していた当時のメモ書きをほんの少しだけ整理して、以下に残しておきます……

  • まず可変長整数でファイルの解凍後のサイズを教えてくれる。このフォーマットは、size-encoding と呼ばれている。具体的には、以下。またはこの記事にも詳しい。
    • 最初の1bit（most significant bit, MSB と呼ばれる）が予約されており、next byte がその可変長整数に属するかどうかを示す。あるbyteが1xxxxxxxだったなら、その次のbyteも可変長整数として解釈する。
    • この可変長整数の最初の4bitは object のタイプを教えてくれる
    • MSB を除いた3bitがタイプを教えてくれる。タイプは6種類定義されているので、3bitにおさまる
      • git のソースコードを見ればわかるが、commitが1、treeが2、blobが3、tagが4、ofs_deltaが6，ref_deltaが7。ofs_delta と ref_delta については、後述。
    • 1011xxxx とあるときに最初の 1 は MSB で、次の 011 が blob であることを示す、といった具合
    • のこり4bitからはじまるbitsがその可変長整数。ビッグエンディアン。
    • MSBが0になったところまでがその可変長整数。次のbyteは可変長整数として読んではならない。
  • 可変長整数の次はデータ本体が来るが、このデータは non-deltified なものと deltified なものに分類される
    • non-deltified とは、ふつうのオブジェクトのこと。commit, tree, tag, blob が該当する。
    • deltified とは、なにか別のオブジェクト（base object）に対して適用する差分パッチのこと。この差分パッチを（必要なら再帰的に）適用することで non-deltified なオブジェクトが得られる。
  • non-deltified なファイルの場合、それ以降のデータはzlib圧縮されたオブジェクトデータ。なので、zlib解凍をかければデータが取り出せる。
    • ……のだが、可変長整数に記録されているのは解凍後のサイズ。つまり、packflieのどこまで読めばよいかは実はpackfile単独だとわからない
      • ただし、可変長整数より後ろのデータを丸ごと食わせれば最初のオブジェクトの解凍はできるとのこと。zlibは、後ろに余計なデータが引っ付いていてもそれをちゃんと無視できるようだ。
      • zlib については RFC 1950 に、deflate については RFC 1951 にかかれているので読めばわかりそうなんですがまだ読んでいません。
    • index file を読み解けば、packfile 内部のどこに zlib 圧縮されているのかわかるが、自前で実装する場合は index file はない。私の場合は zlib の圧縮解凍に rust の flate2 を使ったが、この場合は total_in を使うことで zlib 圧縮されたデータの長さがわかったので、この長さだけ読み出しをすすめるという形で対処した。
  • deltified な場合、まず最初に差分パッチの適用対象であるオブジェクトの情報が書かれている
    • ref-delta は base object name を直接エンコードしている（ref を指し示す）
      • つまり20バイトのSHA-1オブジェクトID
    • ofs-delta は base object name への offset をエンコードしている
    • その後ろに deflate compressed な delta data が続く。inflate した後は以下のようになっている。
      • base object と再構築される object のサイズからスタートする。size encoding によりエンコードされている。
        • つまり size encoding によりエンコードされたデータが2つある
      • 適用すべき delta の内容。
        • 最初の1バイトで命令が分岐する。
        • msb(最初の1ビット)が1の場合、base object からの copy 命令。
          • 最初の1バイト 1xxxxxxx のうちのこった下位7ビットがあるはずだが、bit 0 から bit 3 までが offset で、bit 4 から bit 6 までが size をあらわす。
          • offset, size はいずれも little-endian order である。
          • offset と size の記載を省略した場合、いずれも0とみなす
          • ただし size に関しては、0と記載したら65536バイトであるものとみなす
        • msbが0の場合、base object に対する insert 命令。
          • 0xxxxxxx の7ビットは append するデータのサイズを示す
          • 末尾に append するデータが次のバイトから続く

感想

正直むずかしかったけど先人の努力が偲ばれて色々と学びがありました。特に packfile の形式については、何としてでもバイト数を圧縮してネットワークでやり取りするパケット数を減らそうという強い意志を感じました。またこれを実装する過程でシフト演算をはじめてまともにやった気がします。

また動くまでの最小構成を作るというのが難しいなとも思いました。今回私は ofs-delta を実装しないという決定をしており、これで手元のリポジトリはそれっぽく clone 出来ていることを確認してはいるものの、他のリポジトリでで動くかどうかはわかりません。我々が素朴に「（ソフトウェアが）動く」というとき、それは何に依存しているのか、何を以て「動く」と判断しているのか、と考え出すとなんだか難しいなと思います。

それと、git ほどよく使われているソフトウェアであってもドキュメントに TODO がでてくるというのも学びでした。ドキュメントは強い気持ちで書かないと書かれないということを痛感しては来ましたが、どこも事情はある程度似たようなもののようです。まあ、今回に関して言うと、たぶん packfile を自前でパースしたがる人間なんてほとんどいないと思うので、ドキュメントを書いてもしょうがないという部分はあるのでしょうが……ウーム。


← 感想文置き場に戻る