コミットはスナップショットであり差分ではない

Image of derrickstolee

Git は紛らわしいという評判です。用語や言い回しが意味するものと、そこから想像する挙動が違ってユーザーが混乱すると言われます。これは、git cherry-pick や git rebase のような「履歴を書き換える」コマンドに最も顕著です。私の経験では、この混乱の根本的な原因は、コミットは 差分 であり順番を入れ替えることができるという解釈にあります。しかし、コミットはスナップショットであって、差分ではありません!

Git がリポジトリデータをどのように保存しているかを見てみると、Git を理解しやすくなります。このモデルを調べた後に、この新しい視点が git cherry-pick や git rebase のようなコマンドを理解するのにどのように役立つのかを探っていきます。

本当に深く 掘り下げたいのであれば、Pro Git という書籍の Git Internals の章を読むといいでしょう。

今回は例として v2.29.2 でチェックアウトした git/git リポジトリを使います。記事で紹介するコマンドラインの例に従ってぜひ実際に試してみてください。

オブジェクト ID はハッシュ

Git オブジェクトについて知っておくべき最も重要なことは、Git はそれぞれのオブジェクトをオブジェクト ID (略して OID) で参照しているということです。この OID がオブジェクトへのユニークな名前となります。これらの OID を調べるには git rev-parse <ref> コマンド を使用します。それぞれのオブジェクトは基本的にはプレーンテキストファイルであり、その内容を調べるには git cat-file -p <oid> コマンドを使用します。

また、もっと短い 16 進数の文字列で表現された OID の方をよく目にするかもしれません。この文字列は、リポジトリ内のただ一つのオブジェクトが持つ OID と一致する省略形として十分な長さのものが指定されています。あまりにも短く省略した OID を使ってオブジェクトの型を調べると、一致する OID の一覧が表示されます。

$ git cat-file -t e0c03
error: short SHA1 e0c03 is ambiguous
hint: The candidates are:
hint:   e0c03f27484 commit 2016-10-26 - contrib/buildsystems: ignore irrelevant files in Generators/
hint:   e0c03653e72 tree
hint:   e0c03c3eecc blob
fatal: Not a valid object name e0c03

blobtreecommitというこれらの型はなんでしょうか?順に説明していきます。

ブロブはファイルの内容

オブジェクトモデルの一番下に位置する ブロブ には、ファイルの内容が含まれています。現在のリビジョンのファイルの OID を調べるには、 git rev-parse HEAD:<path> を実行します。次に、 git cat-file -p <oid> を使用してファイルの内容を調べます。

$ git rev-parse HEAD:README.md
eb8115e6b04814f0c37146bbe3dbc35f3e8992e0

$ git cat-file -p eb8115e6b04814f0c37146bbe3dbc35f3e8992e0 | head -n 8
[![Build status](https://github.com/git/git/workflows/CI/PR/badge.png)](https://github.com/git/git/actions?query=branch%3Amaster+event%3Apush)

Git - fast, scalable, distributed revision control system
=========================================================

Git is a fast, scalable, distributed revision control system with an
unusually rich command set that provides both high-level operations
and full access to internals.

ディスク上の README.md ファイルを編集すると、 git status はそのファイルの更新時刻が最近であることに気付き、その内容のハッシュを計算します。もし内容が現在の HEAD:README.md の OID と一致しない場合は、 git status はそのファイルを “modified on disk” と表示します。このようにして、現在の作業ディレクトリのファイルの内容が HEAD の内容と一致しているかどうかを確認することができます。

ツリーはディレクトリ

ブロブにはファイルの内容が含まれていますが、ファイル名は含まれていないことに注意しましょう!ファイル名は、Git のディレクトリの表現である ツリー に含まれています。ツリーとは、パスのエントリを順番に並べたもので、オブジェクトの種類やファイルモード、そしてそのパスにあるオブジェクトの OID を持ちます。サブディレクトリもツリーとして表現され、ツリーは他のツリーを参照することができます。

これらのオブジェクトがどのように関連しているかを視覚化するために図を使います。ブロブは四角、ツリーは三角を使って表現します。

$ git rev-parse HEAD^{tree}
75130889f941eceb57c6ceb95c6f28dfc83b609c

$ git cat-file -p 75130889f941eceb57c6ceb95c6f28dfc83b609c  | head -n 15
100644 blob c2f5fe385af1bbc161f6c010bdcf0048ab6671ed    .cirrus.yml
100644 blob c592dda681fecfaa6bf64fb3f539eafaf4123ed8    .clang-format
100644 blob f9d819623d832113014dd5d5366e8ee44ac9666a    .editorconfig
100644 blob b08a1416d86012134f823fe51443f498f4911909    .gitattributes
040000 tree fbe854556a4ae3d5897e7b92a3eb8636bb08f031    .github
100644 blob 6232d339247fae5fdaeffed77ae0bbe4176ab2de    .gitignore
100644 blob cbeebdab7a5e2c6afec338c3534930f569c90f63    .gitmodules
100644 blob bde7aba756ea74c3af562874ab5c81a829e43c83    .mailmap
100644 blob 05f3e3f8d79117c1d32bf5e433d0fd49de93125c    .travis.yml
100644 blob 5ba86d68459e61f87dae1332c7f2402860b4280c    .tsan-suppressions
100644 blob fc4645d5c08bd005238fc72cfa709495d8722e6a    CODE_OF_CONDUCT.md
100644 blob 536e55524db72bd2acf175208aef4f3dfc148d42    COPYING
040000 tree a58410edddbdd133cca6b3322bebe4fb37be93fa    Documentation
100755 blob ca6ccb49866c595c80718d167e40cfad1ee7f376    GIT-VERSION-GEN
100644 blob 9ba33e6a141a3906eb707dd11d1af4b0f8191a55    INSTALL

ツリーは、各サブアイテムの名前を持ちます。ツリーには、Unix ファイルパーミッション、オブジェクトタイプ(blobまたはtree)、各エントリの OID の情報も含まれています。上記では上位 15 エントリだけに絞っていますが、 grep を使用してこのツリーに先ほどのブロブの OID を指す README.md エントリがあることがわかります。

$ git cat-file -p 75130889f941eceb57c6ceb95c6f28dfc83b609c | grep README.md
100644 blob eb8115e6b04814f0c37146bbe3dbc35f3e8992e0    README.md

ツリーは、これらのパスエントリを使用してブロブや他のツリーを指すことができます。これらの関係はパス名と対になっていますが、図に示す際は必要に応じてパス名を省略します。

ツリー自体は、それがリポジトリ内のどこに存在するかを知りません。その役割を果たすのはそのツリーを参照しているオブジェクトです。 <ref>^{tree} で参照されるツリーは、特別なツリー、つまり ルートツリー です。この指定方法は(これから解説する)コミットからの特別なリンクに基づいています。

コミットはスナップショット

コミット はある時間におけるスナップショットです。各コミットには、その時点での作業ディレクトリの状態を表すルートツリーへのポインタが含まれています。コミットは、以前のスナップショットに対応する親コミットのリストを持ちます。親のないコミットはルートコミットであり、複数の親を持つコミットはマージコミットです。コミットには、作成者やコミッター(名前、メールアドレス、日付を含む)、およびコミットメッセージといったメタデータも含まれます。コミットメッセージは、コミットの作成者がそのコミットの目的を説明するためのものです。

たとえば、Git リポジトリの v2.29.2 でのコミットは、そのリリースについてのもので、Git メンテナが作成しコミットしたものです。

$ git rev-parse HEAD
898f80736c75878acc02dc55672317fcc0e0a5a6

/c/_git/git ((v2.29.2))
$ git cat-file -p 898f80736c75878acc02dc55672317fcc0e0a5a6
tree 75130889f941eceb57c6ceb95c6f28dfc83b609c
parent a94bce62b99be35f2ee2b4c98f97c222e7dd9d82
author Junio C Hamano <gitster@pobox.com> 1604006649 -0700
committer Junio C Hamano <gitster@pobox.com> 1604006649 -0700

Git 2.29.2

Signed-off-by: Junio C Hamano <gitster@pobox.com>

git log の履歴をもう少し見てみると、そのコミットとその親との間の変更について、より説明的なメッセージを見つけることができます。

$ git cat-file -p 16b0bb99eac5ebd02a5dcabdff2cfc390e9d92ef
tree d0e42501b1cf65395e91e22e74f75fc5caa0286e
parent 56706dba33f5d4457395c651cf1cd033c6c03c7a
author Jeff King &lt;peff@peff.net&gt; 1603436979 -0400
committer Junio C Hamano &lt;gitster@pobox.com&gt; 1603466719 -0700

am: fix broken email with --committer-date-is-author-date

Commit e8cbe2118a (am: stop exporting GIT_COMMITTER_DATE, 2020-08-17)
rewrote the code for setting the committer date to use fmt_ident(),
rather than setting an environment variable and letting commit_tree()
handle it. But it introduced two bugs:

- we use the author email string instead of the committer email

- when parsing the committer ident, we used the wrong variable to
compute the length of the email, resulting in it always being a
zero-length string

This commit fixes both, which causes our test of this option via the
rebase "apply" backend to now succeed.

Signed-off-by: Jeff King &lt;peff@peff.net&gt; Signed-off-by: Junio C Hamano &lt;gitster@pobox.com&gt;

私たちの図では、コミットを表すために円を使います。復習してみましょう。

  • 四角形はブロブです。これらはファイルの内容を表しています。
  • 三角形はツリーです。これらはディレクトリを表します。
  • 円はコミットです。ある時点でのスナップショットです。

ブランチはポインタ

Git では、ほとんどの場合 OID を参照せずに履歴を移動したり変更を行ったりします。これは、ブランチがコミットへのポインタを提供してくれるからです。main という名前のブランチは、実際には refs/heads/main と呼ばれる Git の参照です。これらのファイルには、参照しているコミットの OID である 16 進数の文字列が実際に含まれています。作業をしているうちに、これらの参照の内容は他のコミットを指すように変化していきます。

これは、ブランチがこれまでの Git オブジェクトとは大きく異なることを意味します。コミットやツリー、ブロブは 不変 です。つまり、これらの内容を変更することはできません。もし内容を変更した場合は、異なるハッシュとなります。つまり、新しいオブジェクトを参照する新しい OID を得ることになります!ブランチはわかりやすさのためにユーザが命名したもので、例えば trunk や my-special-project などです。作業を追跡したり共有したりするためにブランチを使います。

特別な参照である HEAD は現在のブランチを指します。HEAD にコミットを追加すると、そのブランチは自動的に新しいコミットに更新されます。

新しいブランチを作成して HEAD を更新するには git switch -c を使います:

$ git switch -c my-branch
Switched to a new branch 'my-branch'
$ cat .git/refs/heads/my-branch
1ec19b7757a1acb11332f06e8e812b505490afc6
$ cat .git/HEAD
ref: refs/heads/my-branch

my-branch を作成すると、現在のコミットの OID を含むファイル (.git/refs/heads/my-branch) が作成され、 .git/HEAD ファイルがこのブランチを指すように更新されたことに注目しましょう。さて、新しいコミットを作成して HEAD を更新すると、 my-branch のブランチはその新しいコミットを指すように更新されます!

全体像

これらの新しい用語を一つの巨大な図にまとめてみましょう。ブランチはコミットを指し、コミットは他のコミットとそのルートツリーを指し、ツリーはブロブと他のツリーを指し、ブロブは何も指していません。これらすべてのオブジェクトを一つにまとめた図を下に示します。

この図では、時間は左から右に向かって経過していきます。コミットからその親への矢印は右から左に向かっています。各コミットは一つのルートツリーを持っています。 HEAD はここでは main ブランチを指し、 main は最も新しいコミットを指しています。このコミットのルートツリーの下は完全に展開されていますが、他のルートツリーからはこれらのオブジェクトを指す矢印があります。これは、内容が同じオブジェクトは複数のルートツリーから参照可能だからです!これらのツリーはオブジェクトの OID (内容) を使って参照しているので、これらのスナップショットは同じ内容のデータを複数コピーする必要がありません。このようにして、Git のオブジェクトモデルは マークル木 を形成しています。

このようにしてオブジェクトモデルを見ると、なぜコミットがスナップショットなのかがわかります。各コミットは、そのコミットで期待する完全な作業ディレクトリに直接リンクしているというわけです。

差分の計算

コミットがスナップショットであるにもかかわらず、コミットを履歴ビューや GitHub 上で差分として 見ることがよくあります。実際、コミットメッセージではこの差分を参照することがよくあります。差分は、コミットのルートツリーとその親を比較することで、スナップショットデータから 動的に生成 されます。Git は、隣接するコミットだけでなく、任意の二つのスナップショットを比較することができます。

二つのコミットを比較するには、まずルートツリーを見てみましょう。これらはほぼ常に異なります。次に、この二つのサブツリーに対して深さ優先探索を行います。この探索では現在のツリーのパスに対して異なる OID を持つようなペアを探します。以下の例では、ルートツリーの docs の値が異なるので、これら二つのツリーを再帰的に探索します。これらのツリーは M.md の値が異なるので、これら二つのブロブを 1 行ごとに比較し、その差分を表示します。docs 内であったとしても N.md は同じなので、それをスキップしてルートツリーに戻ります。ルートツリーでは、 things ディレクトリや README.md は同じ OID を持つことがわかります。

上の図では、 things ツリーは検査しないので、そこから到達可能なオブジェクトも検査しないことがわかります。このようにして、差分を計算するコストは、内容の異なるパスの数に比例します。

これで、 コミットはスナップショットであり、任意の二つのコミット間の差分を動的に計算できることが理解できました。では、なぜこれが一般的な知識になっていないのでしょうか?なぜ新しいユーザーは、コミットが差分であるという誤った考えを持ってしまうのでしょうか?

私の好きな例えのひとつに、コミットは粒子と波動の二重性 を持つというものがあります。この例えが意味するのは、コミットはスナップショットとして扱われることもあれば差分として扱われることもあるということです。問題の核心は、Git オブジェクトではない別の種類のデータ、パッチにあります。

待って、パッチって何?

パッチ とは、既存のコードベースへの変更を記述したテキスト文書のことです。パッチは、非常に分散したグループが Git コミットを直接使わずにコードを共有するためのものです。Git のメーリングリスト では、このようなパッチがやり取りされているのを目にすることができます。

パッチには、変更点の説明と、その変更点がなぜ価値あるものなのかという理由が書かれており、それに続いて差分が付けられます。これによって、その変更を自分が持っているコードのコピーに 適用 するかどうかを判断することができる、というアイデアです。

Git では、 git format-patch を使用してコミットをパッチに変換することができます。 git apply を使えば、Git リポジトリにパッチを適用することができます。オープンソースの初期の頃はこれがコードを共有するための主流の方法でしたが、ほとんどのプロジェクトではプルリクエストを使って直接 Git のコミットを共有するようになりました。

パッチを共有する場合の最大の問題点は、パッチは親の情報を失い、新しいコミットは既存の HEAD を親とすることです。しかも、もし同じ親を持っていても別のコミットになってしまうだけでなく、コミッターも変わってしまうのです!これが、Git がコミットオブジェクトに「author」と「committer」の両方を持つ根源的な理由です。

パッチを使う場合の最大の問題点は、自分の作業ディレクトリが送信者の前のコミットと一致しない場合にパッチを適用するのが難しいことです。コミット履歴を失うと、コンフリクトの解決が難しくなります。

「パッチをやりとりする」というこの考え方は、「コミットをやり取りする」と言い換えられていくつかの Git コマンドに引き継がれています。その代わりに、実際に起こっているのはコミットの差分が再計算され、新しいコミットが作成されるということです。

コミットが差分でないのなら git cherry-pick は何をしているの?

git cherry-pick <oid> コマンドは、<oid> との差分と同一の差分を持ち、現在のコミットが親となる新しいコミットを作成します。Git は基本的に、次のような手順を踏んでいます:

  1. コミット <oid> とその親との差分を計算する。
  2. その差分を現在の HEAD に適用する。
  3. ルートツリーが新しい作業ディレクトリにマッチし、その親が HEAD のコミットである新しいコミットを作成する。
  4. HEAD の参照をその新しいコミットに移動する。

Git が新しいコミットを作成した後、git log -1 -p HEAD の出力は git log -1 -p <oid> の出力と一致するはずです。

ここで重要なのは、現在の HEAD の上にあるコミットを「移動」したのではなく、新しいコミットを作成してその差分が古いコミットにマッチするようにしたという点です。

コミットが差分でないのならgit rebaseは何をしているの?

git rebase コマンドは、コミットを移動して新しい履歴を持つようにするためのものです。最も基本的な形では、git cherry-pick を複数回実行しただけのもので、差分を別のコミットの上に重ねて適用していきます。

最も重要なことは、 git rebase <target> は HEAD からは到達可能だが <target> からは到達できないコミットのリストを見つけるという点です。git log --oneline <target>..HEAD を使用すると、これらのコミットの一覧を表示することができます。

そして rebase コマンドは単純に <target> に移動し、見つけたコミットたちに対して git cherry-pick コマンドを最も古いコミットから順に実行し始めます。こうすることで最終的に、元のコミットたちと似たような差分を持ちながらも OID が異なる 新しいコミットのセットができあがります。

たとえば、target ブランチを分岐してから、新たに3つのコミットを実行した現在の HEAD を考えてみましょう。git rebase target を実行すると、共通のベースである P が計算され、コミットリスト ABC が決定されます。これらのコミットは target に対してチェリーピックされて新しいコミット A'B'C' が作成されます。

これらのコミット A'B'C' は、ABC と多くの情報を共有してはいますが、全く新しい別のコミットです。実際、古いコミットはガベージコレクションが実行されるまでリポジトリに存在しています。

git range-diff コマンドを使えば、これらのコミット範囲がどのように異なるのかを調べることもできます!ここでは、Git リポジトリのコミットの例を使って v2.29.2 タグにリベースし、先頭のコミットを少し修正してみます。

$ git checkout -f 8e86cf65816
$ git rebase v2.29.2
$ echo extra line >>README.md
$ git commit -a --amend -m "replaced commit message"
$ git range-diff v2.29.2 8e86cf65816 HEAD
1:  17e7dbbcbc = 1:  2aa8919906 sideband: avoid reporting incomplete sideband messages
2:  8e86cf6581 ! 2:  e08fff1d8b sideband: report unhandled incomplete sideband messages as bugs
    @@ Metadata
     Author: Johannes Schindelin <Johannes.Schindelin@gmx.de>

      ## Commit message ##
    -    sideband: report unhandled incomplete sideband messages as bugs
    +    replaced commit message

    -    It was pretty tricky to verify that incomplete sideband messages are
    -    handled correctly by the `recv_sideband()`/`demultiplex_sideband()`
    -    code: they have to be flushed out at the end of the loop in
    -    `recv_sideband()`, but the actual flushing is done by the
    -    `demultiplex_sideband()` function (which therefore has to know somehow
    -    that the loop will be done after it returns).
    -
    -    To catch future bugs where incomplete sideband messages might not be
    -    shown by mistake, let's catch that condition and report a bug.
    -
    -    Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
    -    Signed-off-by: Junio C Hamano <gitster@pobox.com>
    + ## README.md ##
    +@@ README.md: and the name as (depending on your mood):
    + [Documentation/giteveryday.txt]: Documentation/giteveryday.txt
    + [Documentation/gitcvs-migration.txt]: Documentation/gitcvs-migration.txt
    + [Documentation/SubmittingPatches]: Documentation/SubmittingPatches
    ++extra line

      ## pkt-line.c ##
     @@ pkt-line.c: int recv_sideband(const char *me, int in_stream, int out)

range-diff の結果、コミット 17e7dbbcbc と 2aa8919906 が「等しい」とされている点に注目してください。ここで等しいとはこれら二つのコミットが同じパッチを生成することを意味しています。二つ目のコミットのペアは異なるもので、コミットメッセージが変更され、元のコミットにはなかった README.md の修正が行われていることを示しています。

この二つのコミット列を追ってみると、コミット履歴がどのように残っているかを見ることができるでしょう。新しいコミットでは v2.29.2 タグが履歴の三番目のコミットになっている一方で、古いコミットでは (以前のバージョンである) v2.28.0 タグが三番目のコミットになっています。

$ git log --oneline -3 HEAD
e08fff1d8b2 (HEAD) replaced commit message
2aa89199065 sideband: avoid reporting incomplete sideband messages
898f80736c7 (tag: v2.29.2) Git 2.29.2

$ git log --oneline -3 8e86cf65816
8e86cf65816 sideband: report unhandled incomplete sideband messages as bugs
17e7dbbcbce sideband: avoid reporting incomplete sideband messages
47ae905ffb9 (tag: v2.28.0) Git 2.28

コミットは差分でないのであれば、Git はどのようにリネームを追跡するの?

オブジェクトモデルをよく見てみると、Git は保存されているオブジェクトデータのコミット間の変更を追跡していないことに気づいたかもしれません。「どうやって Git はリネームが起こったことを知っているのだろう?」と思われるかもしれません。

Git はリネームを追跡しません。Git の内部には、コミットとその親の間でリネームが発生したという記録を保存するデータ構造はありません。その代わり、Git は動的に差分を計算する際にリネームを検出しようとします。このリネームの検出には、厳密なリネーム(exact rename)と編集リネーム(edit-rename)の二段階があります。

最初に差分を計算した後、Git は差分の内部モデルを検査して、どのパスが追加されたり削除されたりしたかを調べます。ある場所から別の場所に移動したファイルは当然、最初の場所では削除され、次の場所では追加されたものとして現れます。Git はこれらの追加と削除をマッチして、推測されるリネームのセットを作成しようとします。

このマッチングアルゴリズムの最初の段階では、追加と削除が行われたパスの OID を調べ、完全に一致するものがあるかどうかを調べます。そのような完全一致したパスをペアとして覚えておきます。

第二段階はコストの掛かる部分です: リネームされてかつ編集が行われたファイルをどうやって検出するのでしょうか?Git は追加された各ファイルに対して、削除された各ファイルとの比較を行い、それらの間での共通の行の割合を 類似度 として計算するという処理を繰り返します。デフォルトでは、共通の行が 50% を超えるものは編集リネームの可能性があるとみなされます。このアルゴリズムでは、類似度が最大のものを見つけるまで、ペアの比較を続けます。

ここで問題に気付きましたか?このアルゴリズムは A * D 回差分計算します。ここで A は追加されたファイルの数で、 D は削除されたファイルの数です。この処理は二次関数です!リネームの検出の計算が長くなるのを避けるため、 A + D の値が内部的な制限値よりも大きい場合は、Git は編集リネームの検出をスキップします。この制限値を変更するには diff.renameLimit オプション を使用します。また、 diff.renames の設定を無効にすることで、このアルゴリズムを完全に回避することもできます。

私は Git のリネーム検出を意識して、自分のプロジェクトで使ってみたことがあります。例えば、私は VFS for Git をフォークして Scalar プロジェクトを作り、コードの多くを再利用する一方でファイル構造を大幅に変更しました。これらのファイルの履歴を VFS for Git コードベースのバージョンまで追跡できるようにしたかったので、二つの手順でリファクタを行いました。

  1. ブロブを変更せずにすべてのファイルの名前を変更する。
  2. ファイル名を変更せずにブロブを変更するために文字列を置換する。

この二つの手順により、git log --follow -- <path> を使って、リネーム前後のファイルの履歴をすぐに確認できるようになりました。

$ git log --oneline --follow -- Scalar/CommandLine/ScalarVerb.cs
4183579d console: remove progress spinners from all commands
5910f26c ScalarVerb: extract Git version check
...
9f402b5a Re-insert some important instances of GVFS
90e8c1bd [REPLACE] Replace old name in all files
fb3a2a36 [RENAME] Rename all files
cedeeaa3 Remove dead GVFSLock and GitStatusCache code
a67ca851 Remove more dead hooks code
...

出力を省略しましたが、この最後の二つのコミットは実際には Scalar/CommandLine/ScalarVerb.cs に対応するパスを持っておらず、代わりに以前のパスである GVSF/GVFS/CommandLine/GVFSVerb.cs を追跡していますが、これはコミット fb3a2a36 [RENAME] Rename all files での厳密なリネームを Git が認識したからです。

もう騙されないぞ!

これで、 コミットはスナップショットであって差分ではないことがわかりましたね!これを理解していれば、Git での作業をスムーズに進めることができるでしょう。

これで、Git オブジェクトモデルの深い知識が身につきました。この知識を使って、Git コマンドを使ったり、チームのワークフローを決めたりするスキルを向上させることができます。今後のブログ記事では、この知識を使ってさまざまな Git クローンのオプションや、やりとりが必要なデータを減らす方法について学んでいく予定です!