「git diff」のソースを読んで理解を深める
1. 概要
git diff は開発をしている使用する機会が多いgitのコマンドです。
出来ることは、色んなものの差分を取ることです。例えば、
- 2つのコミット間の変更点比較
- 特定のブランチやタグとの比較
- 変更された行数やファイル数を統計的に表示（--statオプション）。
などがあります。開発中に使える便利ツールです。
しかし、diffはどうやって差分をとっているのでしょうか。また、なぜ中身が一致しないファイルを探し出して比較できるのでしょうか。
この辺りの詳細について知るためには、diffの中身(ソースコード)をみて学ぶのがよいと思ったため、本文書では簡単に解析した結果を示します。
2. git diff の解析をするために勘所を探る
以下がgitのソースコード(と思われる)。
C言語とshell scriptなどで構成されています。
gitのリポジトリには大量のファイルがあります。しかし、コマンド名などで区切られていそうな雰囲気を感じます。
gitコマンドに大きくかかわりそうなものとして、builtin ディレクトリというものがあります。
buildinというののは、組み込みコマンド などを意味することがあるため、この辺りを追っていけば良さそうに思います。
この buitin ディレクトリの中に ./builtin/diff.c があります。
その中に、cmd_diff という関数があり、おそらくこれが git diff コマンド本体ではないかと思われます。
この cmd_diff 関数の前方宣言は、./builtin.h にあります。
また、./Makefile にもコンパイルされた .o ファイルがあり、リンクされています。
どのようにgitのバイナリがビルドされるのかを知るためにMakefileを2.1.節で眺めてみます。
2.1. Makefileを眺めてみる
gitのバイナリをビルドしているのはたぶんここ。
gccで./builtin/以下の*.c をコンパイルして *.o を生成している。
QUIET_CCは以下の通りです。CC=gcc であり、別途記載されています。
コンパイルされたオブジェクトファイルは,BUILTIN_OBJSに格納されます。
BUILIN_OBJSはGIT_OBJSに格納されます。
最終的に、GIT_OBJSはOBJECTSに格納されます。そしてこれは上記のgccビルド時に指定されています。
2.2. ./builtin/diff.c を眺める
おそらく、git diff を実行するとcmd_diff関数がコールされると思われます。
この辺りもincludeしていることを確認できます。
例えば、./diff.h の実装は、./diff.c に書かれているので一例を見てみると、
コンポーネントとなる関数が実装されている感じに思われます。
3. git diff を解析
./builtin/diff.cのcmd_diff の流れは以下のような感じ。
- 引数の解析（例：--cachedやファイルパス）
- リポジトリ設定の初期化
- 適切な diff 処理（ファイル、ツリー、インデックス間の比較）
- 最終的な diff 結果の計算と後処理
この辺りで差分をとる対象について設定している。
3.1. tree vs tree
ゆくゆく他も解析することとして、一旦私が知りたいtree vs treeのdiffについて調べます。
(N (tree-ish): ツリー、M (blobs): Gitにおけるファイルの内容、P (pathspecs):パス指定)
./builtin/diff.cのcmd_diffの該当部は以下であると思われます。
ここでコールされているbuiltin_diff_tree はこんな感じ。
コールされているdiff_tree_oidはこれ。
ここでコールされているll_diff_tree_oidはこれ。
ここのdiff_tree_paths からが目的の部分っぽい。
これが該当部分と思われます。
- 準備段階
- まず、ツリーオブジェクトと親ツリー（
parents_oid）をロードし、それぞれをtree_desc構造体に格納します。 -
fill_tree_descriptor関数でツリー情報を取得し、ツリーの構造体を初期化します。
- まず、ツリーオブジェクトと親ツリー（
- 再帰の有効化
-
opt->pathspec.recursiveを設定して、ツリーの深さに関わらず再帰的に探索を続けるようにします。 - どんどん深くに進んでいく
-
- 差分の取得と処理
- ツリー内の差分を比較し、
tree_entry_pathcmp関数を使って、ツリー内のエントリをパス名とモードで比較します。 - 最も小さなエントリ（
imin）を特定し、そのエントリと現在のツリー（t）を比較します。 - 同一であれば、変更がない部分（
t = p[imin]）をスキップしますが、異なる場合（t < p[imin]またはt > p[imin]）は、それぞれ追加または削除をemit_path関数で処理します。
- ツリー内の差分を比較し、
- ツリーの更新
- 比較後は、
update_tree_entryやupdate_tp_entriesを使って、ツリーエントリの状態を更新します。
- 比較後は、
- 終了条件
- すべてのツリーが処理された場合、ループを終了します。差分が満たされた場合や最大変更数を超えた場合にも終了します。
- メモリの解放
- 最後に、使用したメモリを解放します。
探索の順番は、明示的に設定した値まで深く探索する深さ優先探索のように思える。
ちなみにhashで比較している。
3.3.1. 子ノードを選ぶ順番
ここで、imin は、tp[i] と tp[imin] の間でパス名を比較し、最も小さい（辞書順で最初に来る）エントリを選んでいます。この imin が、次に進むべき子ノードを決める際の基準となります。
-
cmp < 0であれば、tp[i]のエントリがtp[imin]よりも辞書順で前に来るため、iminを更新します。 -
cmp == 0の場合、同じパス名であれば、tp[i]とtp[imin]は等しいとみなします。 -
cmp > 0の場合は、tp[i]のエントリがtp[imin]よりも後に来るため、tp[i]は「iminとは異なる」とマークされます（tp[i].entry.mode |= S_IFXMIN_NEQ）。
このように、imin は tp 配列の中で最も辞書順で前に来るパス を選び、その後の処理で imin に基づいて探索が進みます。
3.1.1. 子ノードへの移動
ここでは、現在のツリーのエントリ t と、選ばれた最小の親ツリーのエントリ tp[imin] とを比較しています。比較の結果に応じて、次にどのように処理を進めるかが決まります。
-
cmp == 0:tとtp[imin]が等しい場合、次に進むべき処理（差分を出力するなど）が行われます。 -
cmp < 0: t がtp[imin]よりも小さい場合、tを探索した後、次に進む処理が行われます。 -
cmp > 0:tがtp[imin]よりも大きい場合、tp[imin]に関連する処理が行われます。
もう少し探索方法についてまとめたい(UML書いておきたい)
次はこれかな？
Discussion