バージョン管理システム Git：Merkle DAG としての履歴と共同開発フロー

情報科学ソフトウェア開発第1章学部無料公開約 45 分2026-08-23

0. この記事の要点

Git は「差分の列」ではなく、内容のハッシュをアドレスとする不変オブジェクトの集まりです。コミットは、そのときのファイル木全体へのポインタと、親コミットへのポインタを持ちます。
全オブジェクトが子のハッシュを含む形で直列化されるため、オブジェクトグラフは Merkle DAG になります。その帰結として、コミットハッシュ 40 文字を照合すれば、そこから到達できる履歴とファイル内容のすべてが確定します（定理 3.3）。
ブランチは「コミットを指す名前つきポインタ」にすぎません。git branch が安価なのはこのためです。
git merge は 2 つのコミットのマージベース（共通祖先の極大元）を求め、ベース・自分・相手の 3 つの版から 3-way マージを行います。マージベースが HEAD 自身になることと、HEAD が相手の祖先であることは同値で、これが fast-forward の正体です（命題 5.3）。
マージベースは一意とは限りません。criss-cross と呼ばれる履歴では 2 つ以上になり、どれを選ぶかでマージ結果が変わります（命題 5.5）。Git の既定戦略はこの問題を「ベース同士をマージして仮想ベースを作る」ことで処理します。
rebase は親を付け替えるので、必ず別のハッシュを持つ別のコミットを作ります（命題 5.7）。共有ブランチで rebase してはいけない理由がここにあります。

1. 動機：バージョン管理は何を解く問題か

report.docx、report_v2.docx、report_v2_修正.docx、report_最終.docx、report_最終_本当に最終.docx。誰もが一度は作ったことのあるファイル名の列です。これは素朴なバージョン管理であり、実際にある程度は機能します。しかし次の 3 つの問いに答えられません。

report_v2.docx と report_v2_修正.docx の違いは何か。ファイル名は違いを記録しません。
report_最終.docx は report_v2.docx から作られたのか、report_v2_修正.docx から作られたのか。つまりどれが誰の子孫なのか。
2 人が同時に report_v2.docx を編集して別々に保存したとき、両方の変更を残すにはどうするか。

1 番目は「差分」、2 番目は「履歴の構造」、3 番目は「並行編集の統合」の問題です。バージョン管理システム（VCS）とは、この 3 つを同時に扱う道具のことです。

歴史的には、この 3 つは順に解かれてきました。1970 年代前半に Bell 研究所の Marc Rochkind が作った SCCS が、ファイルの改訂履歴を 1 つの保管ファイルにまとめる方式を確立します。1980 年代前半に Purdue 大学の Walter Tichy が作った RCS はこれを改良し、最新版を丸ごと持ち、過去へ遡る差分（逆差分）を蓄える方式を採りました。どちらも 3 番目の問題は「ロック」で回避します。編集する人がファイルを排他ロックし、他の人は待つ、という方式です。

ロック方式は、開発者が数人ならうまくいきます。しかし数十人になると待ち行列が破綻します。そこで CVS（1980 年代後半）以降は方針が反転し、誰でも自由に編集してよい、衝突したら後で統合するという楽観的な方式が主流になりました。データベースの同時実行制御でいう楽観的並行制御と同じ発想です（データベース設計の基礎も参照してください）。統合の道具が、この記事の後半で扱う 3-way マージです。

CVS と、その後継である Subversion（2000 年〜）には、なお中央集権という制約が残っていました。履歴はサーバーにしかなく、コミットするにはネットワークが要ります。ブランチを切るのはサーバー上のディレクトリコピーで、重い操作でした。

2005 年 4 月、Linux カーネル開発チームが使っていた商用の分散型 VCS である BitKeeper の無償利用が打ち切られます。Linus Torvalds は代替を数週間で書き上げました。これが Git です。設計上の要求は明確でした。数万ファイル・数十万コミットの規模で高速に動くこと、ネットワークなしで全操作ができること、そして履歴の改竄を検出できることです。3 番目の要求が、Git を単なるファイル履歴管理ではなく、暗号学的ハッシュに基づくデータ構造にしました。

2. 準備：ハッシュ関数と内容アドレス方式

Git を理解する鍵は、ファイルに名前で触らず、内容のハッシュ値で触るという発想です。まずその道具立てを定義します。

定義 2.1（内容アドレス格納庫）

$B = \{0,1\}^{*}$ を有限バイト列全体、 $b$ を正整数とする。写像 $H : B \to \{0,1\}^{b}$ が暗号学的ハッシュ関数であるとは、次の性質が（計算量的な意味で）成り立つことをいう。

（衝突困難性） $H(x) = H(y)$ かつ $x \neq y$ となる $(x, y)$ を現実的な計算資源で求められない。
（原像困難性） $y \in \{0,1\}^{b}$ が与えられたとき、 $H(x) = y$ となる $x$ を現実的な計算資源で求められない。

いま有限集合 $S \subseteq B$ を格納するとき、 $x \in S$ を鍵 $H(x)$ のもとに保存し、取り出しも $H(x)$ で行う方式を内容アドレス格納庫（content-addressable store）という。この方式では、鍵は内容から決まり、内容が変われば必ず鍵も変わる。

Git はこの $H$ として長らく SHA-1（ $b = 160$ ）を使ってきました。ハッシュ値は 16 進 40 文字で表示されます。「衝突困難」が実際にどれくらいの安全余裕を意味するのか、数で確認しておきます。

命題 2.2（誕生日境界による衝突確率の上界）

$H$ の出力が $\{0,1\}^{b}$ 上の一様乱数として振る舞うと仮定する（ランダムオラクル模型）。相異なる $N$ 個の入力 $x_1, \ldots, x_N$ に対し、そのうちのどこかで衝突が起きる確率 $p$ は

p \;\le\; \binom{N}{2} 2^{-b} \;\le\; \frac{N^{2}}{2^{\,b+1}}

を満たす。

証明（命題 2.2）

$1 \le i < j \le N$ に対し、事象 $A_{ij}$ を「 $H(x_i) = H(x_j)$ 」とします。 $x_i \neq x_j$ であり、仮定より $H(x_i)$ と $H(x_j)$ は $\{0,1\}^{b}$ 上の独立な一様分布に従うので、

\Pr[A_{ij}] = \sum_{v \in \{0,1\}^{b}} \Pr[H(x_i) = v]\,\Pr[H(x_j) = v] = 2^{b} \cdot 2^{-b} \cdot 2^{-b} = 2^{-b}

です。求める事象は $\bigcup_{i<j} A_{ij}$ ですから、和事象の確率が各確率の和以下であること（ブールの不等式）より

p \;\le\; \sum_{i<j} \Pr[A_{ij}] = \binom{N}{2} 2^{-b} = \frac{N(N-1)}{2} \cdot 2^{-b} \;\le\; \frac{N^{2}}{2^{\,b+1}}

を得ます。最後の不等号は $N(N-1) \le N^{2}$ によります。

数を入れてみます。Linux カーネルのリポジトリはオブジェクト数がおよそ $10^{7}$ 個です。安全側に見積もって $N = 10^{9}$ 、 $b = 160$ とすると

p \;\le\; \frac{(10^{9})^{2}}{2^{161}} = \frac{10^{18}}{2.923 \times 10^{48}} \approx 3.4 \times 10^{-31}

となります。偶然の衝突は起こらないと考えてよい水準です。ただしこれは $H$ が乱数のように振る舞うという仮定のもとの話で、攻撃者が意図的に衝突を作れるかどうかは別問題です。この点は注意 2.4 で述べます。

例 2.3（Git のオブジェクト名を手で計算する）

Git はファイル内容 $c$ をそのままハッシュするのではなく、種別と長さを前置したバイト列

\sigma = \texttt{"blob "} \,\Vert\, |c| \,\Vert\, \texttt{NUL} \,\Vert\, c

をハッシュします（ $\Vert$ は連結、 $|c|$ は $c$ のバイト数の 10 進表記、NUL は 1 バイトの 0x00）。内容が test content と改行 1 文字、すなわち 13 バイトの場合を計算します。

import hashlib

content = b"test content\n"                       # 13 バイト
store = b"blob " + str(len(content)).encode() + b"\x00" + content
print(store)                                       # b'blob 13\x00test content\n'
print(hashlib.sha1(store).hexdigest())
# => d670460b4b4aece5915caf5c68d12f560a9fe3e4

同じ値が Git 本体からも得られます。

$ echo 'test content' | git hash-object --stdin
d670460b4b4aece5915caf5c68d12f560a9fe3e4

-w を付けると実際に保存され、.git/objects/d6/70460b4b4aece5915caf5c68d12f560a9fe3e4 というパスにファイルができます。先頭 2 文字をディレクトリ名にするのは、1 ディレクトリ内のエントリ数を抑えるためです。保存時に内容は zlib で圧縮されますが、ハッシュを取るのは圧縮前のバイト列です。だから圧縮方式が変わってもオブジェクト名は変わりません。

同じ規則で、空のディレクトリを表す木オブジェクトの名前も計算できます。中身が 0 バイトなので $\sigma = \texttt{"tree 0"} \Vert \texttt{NUL}$ であり、hashlib.sha1(b"tree 0\x00").hexdigest() は 4b825dc642cb6eb9a060e54bf8d69288fbee4904 です。この値はどのリポジトリでも同じで、「空の木」を指す定数としてスクリプトでよく使われます。

注意 2.4（SHA-1 の衝突と Git の対応）

2017 年、Stevens らが SHA-1 の完全な衝突（同じ SHA-1 値を持つ相異なる 2 つの PDF）を実際に構成しました。これは命題 2.2 の仮定が破れた例です。Git はこれに対して二段構えで対応しています。第一に、2017 年以降の Git は衝突検出機能つきの SHA-1 実装（sha1collisiondetection）を既定で使い、既知の攻撃に特徴的な計算パターンを検出したらエラーで停止します。第二に、SHA-256 を使うリポジトリ形式が用意されており、git init --object-format=sha256 で作成できます（記事執筆時点で実験的な位置づけです）。 $b = 256$ なら $N = 10^{9}$ での上界は $10^{18} / 2^{257} \approx 4.3 \times 10^{-60}$ になります。

3. Git のデータモデル：4 種のオブジェクトと Merkle DAG

定義 3.1（Git オブジェクト）

Git の格納庫に入るオブジェクトは次の 4 種類である。いずれも <種別> <バイト数> に NUL を続けたヘッダと本体を連結したバイト列 $\sigma$ を持ち、その名前（オブジェクト ID）は $h = H(\sigma)$ で定まる。オブジェクトは一度作られたら変更されない。

種別	本体の内容	何を表すか
blob	ファイルの中身そのもの（ファイル名は持たない）	ファイル 1 個分の内容
tree	`<モード> <名前>` に `NUL` と 20 バイトのオブジェクト ID を続けた項目の列（名前順）	ディレクトリ 1 個分の構造
commit	木の ID を 1 個、親コミットの ID を 0 個以上、作者・コミッター・日時、空行、コミットメッセージ	ある時点のプロジェクト全体の状態
tag	対象オブジェクトの ID、種別、タグ名、タグ付け者、メッセージ	注釈つきタグ（署名を付けられる）

tree の項目のモードは、通常ファイルが 100644、実行可能ファイルが 100755、サブディレクトリが 40000、シンボリックリンクが 120000 である。

重要なのは、tree が blob の ID を含み、commit が tree と親 commit の ID を含むという入れ子構造です。子の名前が親の本体に埋め込まれているので、子が 1 バイトでも変われば親の名前も変わります。この構造を Merkle DAG と呼びます。

flowchart LR
H["HEAD"] --> R["refs/heads/main"]
R --> C2["commit C2"]
C2 -->|parent| C1["commit C1"]
C2 -->|tree| T2["tree T2"]
C1 -->|tree| T1["tree T1"]
T2 --> B1["blob B1 : README.md"]
T2 --> B2["blob B2 : main.py（更新後）"]
T1 --> B1
T1 --> B3["blob B3 : main.py（更新前）"]

オブジェクトグラフ。矢印は「相手のハッシュを自分の本体に含む」向き。2 つの木が同じ blob（内容が変わっていないファイル）を共有していることに注意。

定義 3.2（参照・ブランチ・HEAD）

参照（ref）とは、コミットの ID を値として持つ名前である。.git/refs/heads/<名前> に置かれる参照をブランチ、.git/refs/tags/<名前> に置かれる参照をタグという。.git/HEAD は特別な参照で、通常はブランチ名への間接参照（ref: refs/heads/main という 1 行）を保持し、これを現在のブランチという。HEAD が直接コミット ID を保持している状態を detached HEAD という。

コミット $c$ を作る操作は、 $c$ をオブジェクト格納庫に書き込み、現在のブランチの参照の値を $c$ の ID に書き換えることからなる。オブジェクトは不変だが、参照は可変である。

Git で可変なものは参照とインデックス（後述）だけで、あとはすべて不変オブジェクトです。この分離が Git の性質のほとんどを説明します。ブランチの作成が瞬時に終わるのは、41 バイトのファイルを 1 つ書くだけだからです。

定理 3.3（ハッシュによる履歴全体の同定）

オブジェクトの有限集合 $O$ と $O'$ を考える（例えば手元のクローンと相手のリポジトリ）。各オブジェクト $o$ はその直列化 $\sigma(o)$ と同一視され、 $\sigma(o)$ は $o$ が参照する子オブジェクトの ID をすべて含むとする。 $h(o) = H(\sigma(o))$ とおき、 $H$ は $\{\sigma(o) : o \in O \cup O'\}$ 上で単射である（この集合の中に衝突が存在しない）と仮定する。 $o$ から到達可能なオブジェクト全体を $R(o)$ と書く。

このとき、 $o \in O$ 、 $o' \in O'$ に対して

h(o) = h(o') \;\Longrightarrow\; R(o) = R(o')

が成り立つ。すなわち、オブジェクト ID が一致すれば、そこから辿れるオブジェクトの集合とその中身は完全に一致する。

証明（定理 3.3）

まず、参照関係が有向非巡回であることを確かめます。オブジェクト $o$ を作るには $\sigma(o)$ を確定させる必要があり、そのためには $o$ が参照する子の ID がすでに決まっていなければなりません。したがって、オブジェクトの生成時刻の順序に沿って親は必ず子より後に作られ、参照の有向路を辿ると生成時刻が真に減少します。もし閉路があれば時刻が真に減少して元に戻ることになり矛盾です。よってグラフは有限 DAG であり、各頂点 $o$ から出る有向路の長さの最大値 $\ell(o)$ （有限）が定義できます。

$\ell(o)$ に関する数学的帰納法で示します。

$\ell(o) = 0$ の場合。 $o$ は子を持たないので、 $h(o) = h(o')$ と $H$ の単射性から $\sigma(o) = \sigma(o')$ 、すなわちバイト列として $o = o'$ です。よって $R(o) = \{o\} = \{o'\} = R(o')$ となります。

$\ell(o) = n \ge 1$ で、 $\ell$ が $n$ 未満のすべての場合に主張が成り立つとする。 $h(o) = h(o')$ と $H$ の単射性より $\sigma(o) = \sigma(o')$ です。 $\sigma$ はヘッダに種別とバイト数を含むので、 $o$ と $o'$ は同じ種別・同じバイト列であり、特に本体に現れる子オブジェクトの ID の並びが一致します。その並びを $h_1, \ldots, h_k$ とし、 $o$ の子を $c_1, \ldots, c_k \in O$ 、 $o'$ の子を $c'_1, \ldots, c'_k \in O'$ とすると、 $h(c_j) = h_j = h(c'_j)$ です。子は $o$ の後続なので $\ell(c_j) \le n - 1$ であり、帰納法の仮定が使えて $R(c_j) = R(c'_j)$ を得ます。したがって

R(o) = \{o\} \cup \bigcup_{j=1}^{k} R(c_j) = \{o'\} \cup \bigcup_{j=1}^{k} R(c'_j) = R(o')

となります（ $o = o'$ は $\sigma(o) = \sigma(o')$ から従います）。以上で帰納法が完成します。

この定理が実務で意味することは大きいので、言い換えておきます。コミット ID を 1 つ、信頼できる経路（署名つきタグ、口頭、別のチャネル）で受け取れば、そのコミットに至る全履歴・全ファイルが 1 バイトも改竄されていないことを検証できます。攻撃者が過去のコミットのファイルを 1 文字書き換えれば、その blob の ID が変わり、tree の ID が変わり、そのコミットの ID が変わり、以後のすべての子孫コミットの ID が変わるからです。git fsck はこの検証を全オブジェクトについて実行するコマンドです。

注意 3.5（インデックス（ステージ領域））

.git/index は、次のコミットで作られる木の下書きを保持するバイナリファイルです。作業ツリーのファイルパスと、対応する blob の ID、モード、更新時刻などが並んでいます。git add は作業ツリーのファイルを読んで blob を書き込み、インデックスの該当行を更新します。git commit はインデックスから木オブジェクトを構築し、それを指すコミットを作ります。「作業ツリー・インデックス・HEAD」という 3 つの状態があることが Git の学習を難しくしていますが、逆にいえば、コミットする内容を作業ツリーとは独立に組み立てられるということです。git add -p で 1 つのファイルの一部の変更だけをステージできるのはこの構造のおかげです。

4. コミットグラフ：祖先関係とマージベース

以降、オブジェクトのうち commit だけを取り出したグラフを考えます。

定義 4.1（コミットグラフと祖先関係）

リポジトリのコミット全体を頂点集合 $C$ 、各コミットからその親コミットへの辺の全体を $E$ とする有向グラフ $G = (C, E)$ をコミットグラフという。 $G$ は有限 DAG である（定理 3.3 の証明冒頭と同じ議論による）。

$a, b \in C$ に対し、 $b$ から $a$ への有向路（長さ $0$ を含む）が存在するとき $a \preceq b$ と書き、 $a$ は $b$ の祖先であるという。 $a \preceq b$ かつ $a \neq b$ のときは $a \prec b$ と書く。

$c \preceq a$ かつ $c \preceq b$ を満たす $c$ を $a, b$ の共通祖先といい、その全体を $\mathrm{CA}(a,b)$ と書く。 $\mathrm{CA}(a,b)$ の $\preceq$ に関する極大元を $a, b$ のマージベースという。

補題 4.2（祖先関係は半順序）

定義 4.1 の $\preceq$ は $C$ 上の半順序である。すなわち、反射律・推移律・反対称律を満たす。

証明（補題 4.2）

反射律。 任意の $a$ について、 $a$ から $a$ への長さ $0$ の路が存在するので $a \preceq a$ です。

推移律。 $a \preceq b$ かつ $b \preceq c$ とします。定義より $c$ から $b$ への有向路 $P_1$ と、 $b$ から $a$ への有向路 $P_2$ があります。 $P_1$ の終点と $P_2$ の始点はともに $b$ なので連結でき、 $c$ から $a$ への有向路が得られます。よって $a \preceq c$ です。

反対称律。 $a \preceq b$ かつ $b \preceq a$ で $a \neq b$ と仮定します。 $b$ から $a$ への路と $a$ から $b$ への路を連結すると、 $b$ から $b$ への路が得られます。 $a \neq b$ より少なくとも一方の路の長さは $1$ 以上なので、この路は長さ $1$ 以上の閉路です。これは $G$ が DAG であること（定義 4.1）に矛盾します。よって $a = b$ です。

命題 4.3（マージベースの存在）

有限コミットグラフ $G = (C, E)$ において、 $a, b \in C$ が共通祖先を少なくとも 1 つ持つ、すなわち $\mathrm{CA}(a,b) \neq \emptyset$ と仮定する。このとき $\mathrm{CA}(a,b)$ は $\preceq$ に関する極大元を少なくとも 1 つ持つ。特に、リポジトリのすべてのコミットが唯一の根コミット $r$ （親を持たないコミット）の子孫であるならば、任意の $a, b$ についてマージベースが存在する。

証明（命題 4.3）

$\mathrm{CA}(a,b) \subseteq C$ は有限集合で、仮定より空でありません。補題 4.2 より $\preceq$ は $\mathrm{CA}(a,b)$ 上でも半順序です。

極大元を構成します。 $c_0 \in \mathrm{CA}(a,b)$ を任意に取ります。 $c_0$ が極大でなければ、 $c_0 \prec c_1$ を満たす $c_1 \in \mathrm{CA}(a,b)$ が存在します。同様に $c_1$ が極大でなければ $c_1 \prec c_2$ なる $c_2$ が取れ、これを繰り返して列 $c_0 \prec c_1 \prec c_2 \prec \cdots$ を作ります。推移律よりすべての $i < j$ で $c_i \prec c_j$ であり、反対称律より $c_i \neq c_j$ です（もし $c_i = c_j$ なら $c_i \prec c_i$ となり、 $\preceq$ の反対称律に反します）。したがってこの列の項はすべて相異なり、 $\mathrm{CA}(a,b)$ が有限であることから列は有限回で止まります。止まった項が極大元です。

後半について。 $r$ がすべてのコミットの祖先であれば $r \in \mathrm{CA}(a,b)$ なので、 $\mathrm{CA}(a,b) \neq \emptyset$ が保証され、前半が適用できます。

git merge-base --all A B を実行すると、Git が計算したマージベースをすべて表示できます。通常のブランチ運用では 1 つしか出ませんが、後で見るようにそうならない履歴も作れます。

5. マージ：3-way マージ、fast-forward、criss-cross

マージベースが求まると、Git は「ベース」「自分の版」「相手の版」という 3 つの状態を比較します。これを 3-way マージといいます。まず抽象化して定義します。

定義 5.1（3-way マージ）

有限集合 $I$ （行やファイルパスなどの「位置」の集合）と集合 $V$ （その位置に入りうる値の集合）を固定し、写像 $x : I \to V$ を版と呼ぶ。版 $b$ （ベース）と版 $x, y$ に対し、各 $i \in I$ で

D_i \;=\; \{\, x(i),\, y(i) \,\} \setminus \{\, b(i) \,\}

とおく。すべての $i \in I$ で $|D_i| \le 1$ が成り立つとき、 $x$ と $y$ は $b$ を基準として衝突しないといい、マージ結果 $m_b(x,y) : I \to V$ を

m_b(x,y)(i) \;=\; \begin{cases} v & (D_i = \{v\} \text{ のとき}) \\ b(i) & (D_i = \emptyset \text{ のとき}) \end{cases}

で定める。ある $i$ で $|D_i| = 2$ となるとき、位置 $i$ で衝突が起きたという。

この定義は「両者の版のうち、ベースから変わっているものを採用する。変わっているものが 2 通りあれば人間に判断を委ねる」という規則をそのまま書いたものです。 $D_i$ を集合として定義したので、場合分けの重複を気にせずに済み、可換性なども見やすくなります。

命題 5.2（3-way マージの基本性質）

定義 5.1 の記法のもとで、任意の版 $b, x, y$ について次が成り立つ。

（衝突の特徴づけ）位置 $i$ で衝突が起きるための必要十分条件は、 $x(i) \neq b(i)$ かつ $y(i) \neq b(i)$ かつ $x(i) \neq y(i)$ が成り立つことである。
（可換性） $x, y$ が $b$ を基準として衝突しないならば $y, x$ も衝突せず、 $m_b(x,y) = m_b(y,x)$ である。
（ベースは単位元） $b$ と $y$ は $b$ を基準として決して衝突せず、 $m_b(b,y) = y$ である。
（冪等性） $x$ と $x$ は $b$ を基準として決して衝突せず、 $m_b(x,x) = x$ である。

証明（命題 5.2）

1. $|D_i| = 2$ とは、集合 $\{x(i), y(i)\}$ から $b(i)$ を除いた結果が 2 元集合になることです。まず $\{x(i), y(i)\}$ 自体が 2 元集合でなければならないので $x(i) \neq y(i)$ 、次に除去で要素が減っていないので $x(i) \neq b(i)$ かつ $y(i) \neq b(i)$ です。逆にこの 3 条件が成り立てば $D_i = \{x(i), y(i)\}$ は 2 元集合です。

2. $D_i$ の定義に現れる集合 $\{x(i), y(i)\}$ は $x$ と $y$ の入れ替えで不変です。したがって $D_i$ も、 $|D_i|$ も、 $m_b(x,y)(i)$ の値も不変です。

3. $x = b$ とすると $D_i = \{b(i), y(i)\} \setminus \{b(i)\}$ です。 $y(i) = b(i)$ なら $D_i = \emptyset$ となり、定義より $m_b(b,y)(i) = b(i) = y(i)$ です。 $y(i) \neq b(i)$ なら $D_i = \{y(i)\}$ となり、 $m_b(b,y)(i) = y(i)$ です。いずれの場合も $|D_i| \le 1$ なので衝突は起きず、値は $y(i)$ に一致します。すべての $i$ でこれが成り立つので $m_b(b,y) = y$ です。

4. $D_i = \{x(i)\} \setminus \{b(i)\}$ なので $|D_i| \le 1$ であり、衝突は起きません。 $x(i) \neq b(i)$ なら $D_i = \{x(i)\}$ で値は $x(i)$ 、 $x(i) = b(i)$ なら $D_i = \emptyset$ で値は $b(i) = x(i)$ です。よって $m_b(x,x) = x$ です。

性質 3 は見た目より重要です。「一方がベースから何も変えていなければ、マージは他方をそのまま採用し、絶対に衝突しない」ということを言っています。これが fast-forward の理論的な中身です。

命題 5.3（fast-forward の特徴づけ）

コミット $a$ （現在の HEAD が指すコミット）と $b$ （取り込む相手のコミット）について、 $\mathrm{CA}(a,b) \neq \emptyset$ とする。このとき次の 2 つは同値である。

$a \preceq b$ 、すなわち $a$ は $b$ の祖先である。
$\mathrm{CA}(a,b)$ の極大元がちょうど $a$ ただ 1 つである（マージベースが $a$ 自身）。

さらにこのとき、ベースを $a$ の木、2 つの版を $a$ の木と $b$ の木として 3-way マージを行うと衝突は起きず、結果は $b$ の木に一致する。したがって Git は新しいコミットを作らず、ブランチの参照の値を $a$ から $b$ に書き換えるだけでよい。この操作を fast-forward という。

証明（命題 5.3）

1 から 2。 補題 4.2 の反射律より $a \preceq a$ であり、仮定より $a \preceq b$ なので $a \in \mathrm{CA}(a,b)$ です。次に任意の $c \in \mathrm{CA}(a,b)$ を取ると、共通祖先の定義から $c \preceq a$ です。つまり $a$ は $\mathrm{CA}(a,b)$ の最大元です。最大元は唯一の極大元になります。実際、 $c$ を極大元とすると $c \preceq a$ ですが、 $c \neq a$ なら $c \prec a$ となって $c$ の極大性に反するので $c = a$ です。また $a$ 自身は、 $a \preceq c'$ なる $c' \in \mathrm{CA}(a,b)$ に対し $c' \preceq a$ でもあるので反対称律より $c' = a$ となり、極大です。

2 から 1。 極大元は $\mathrm{CA}(a,b)$ の元なので、 $a \in \mathrm{CA}(a,b)$ です。共通祖先の定義から $a \preceq b$ が従います。

後半。 木をファイルパスから内容への写像とみなし、 $I$ をパスの集合、 $V$ を blob の ID（存在しないパスには特別な値を割り当てる）とします。ベースは $a$ の木そのもので、2 つの版は $a$ の木と $b$ の木です。命題 5.2 の性質 3 を、ベースの版を $a$ の木、一方の版をそれと同じ $a$ の木、他方の版を $b$ の木として適用すると、衝突は起きず、結果は $b$ の木に一致します。結果の木が $b$ の木と同じで、かつ $a \preceq b$ より $b$ は $a$ の子孫ですから、 $a$ と $b$ の両方を親に持つ新しいコミットを作る意味がありません。参照を $b$ に進めれば十分です。

例 5.4（fast-forward するときとしないとき）

main から feature を切り、feature だけで 2 回コミットした状況を考えます。main が指すコミットを $a$ 、feature が指すコミットを $b$ とすると $a \prec b$ です。

$ git switch main
$ git merge feature
Updating a1b2c3d..d0e1f2a
Fast-forward
 src/auth.py | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)

Fast-forward と表示され、マージコミットは作られていません。命題 5.3 の状況です。履歴は 1 本の直線になり、feature というブランチが存在したという情報は残りません。

一方、この間に他の人が main に 1 コミット積んでいれば、main の指す $a'$ は $b$ の祖先ではありません。 $\mathrm{CA}(a', b) = \{a, \ldots\}$ で極大元は $a$ ですから、命題 5.3 の条件 2 が破れています。この場合は 3-way マージが実行され、親を 2 つ持つマージコミットが作られます。

fast-forward できる場合でもマージコミットを作りたいときは git merge --no-ff feature とします。こうするとブランチの範囲が履歴に残り、git log --first-parent で「main に何が取り込まれたか」を機能単位で追えるようになります。逆に、直線的な履歴を保ちたい方針なら git config --global pull.ff only として fast-forward できないときは失敗させる、という運用もあります。どちらを選ぶかはチームの方針の問題です。

ここまでは、マージベースが 1 つに定まることを暗に前提にしていました。しかしこれは一般には成り立ちません。

flowchart RL
C["C（A と B のマージ）"] --> A["A"]
C --> B["B"]
D["D（A と B のマージ）"] --> A
D --> B
A --> R["R（根コミット）"]
B --> R

criss-cross（たすき掛け）マージ。矢印は子コミットから親コミットへの参照で、時間は左から右に流れる。C と D の共通祖先は A, B, R の 3 つで、そのうち極大なものは A と B の 2 つある。

命題 5.5（マージ結果はマージベースの選び方に依存する）

マージベースが 2 つ以上存在するコミットグラフと、各コミットに割り当てられたファイル内容であって、次を満たすものが存在する。片方のマージベースを基準にすると 3-way マージは衝突せず、もう片方のマージベースを基準にすると衝突する。

証明（命題 5.5）

図の criss-cross グラフを用います。まず $\mathrm{CA}(C,D)$ を計算します。 $C$ の祖先は $\{C, A, B, R\}$ 、 $D$ の祖先は $\{D, A, B, R\}$ なので $\mathrm{CA}(C,D) = \{A, B, R\}$ です。 $R \prec A$ かつ $R \prec B$ なので $R$ は極大ではありません。 $A$ の祖先は $\{A, R\}$ で $B$ を含まず、 $B$ の祖先は $\{B, R\}$ で $A$ を含まないので、 $A$ と $B$ は $\preceq$ に関して比較不能であり、どちらも極大です。よってマージベースは $A$ と $B$ の 2 つです。

次に内容を割り当てます。位置の集合を $I = \{1\}$ （1 行だけのファイル）、値の集合を $V = \{0, 1, 2\}$ とし、各コミットの版を次のように定めます。

コミット	版の値	説明
$R$	$0$	出発点
$A$	$1$	この行を $0$ から $1$ に変更した
$B$	$0$	この行は触らず、別のファイルだけ変更した
$C$	$1$	$A$ と $B$ のマージ結果をそのまま採用した
$D$	$2$	$A$ と $B$ をマージした後、この行を $2$ に変更した

$C$ と $D$ が整合的であることを確認します。 $A$ と $B$ をベース $R$ でマージすると、定義 5.1 より $D_1 = \{1, 0\} \setminus \{0\} = \{1\}$ なので衝突せず、結果は $1$ です。 $C$ はこれをそのまま採用したので値 $1$ 、 $D$ はその後この行を編集したので値 $2$ で、どちらも実際に作れるコミットです。

いま $C$ と $D$ をマージします。

ベースに $A$ （値 $1$ ）を選んだ場合。 $D_1 = \{C(1), D(1)\} \setminus \{A(1)\} = \{1, 2\} \setminus \{1\} = \{2\}$ で、 $|D_1| = 1$ ですから衝突せず、結果は $2$ です。

ベースに $B$ （値 $0$ ）を選んだ場合。 $D_1 = \{1, 2\} \setminus \{0\} = \{1, 2\}$ で $|D_1| = 2$ ですから、命題 5.2 の性質 1 の条件（ $1 \neq 0$ 、 $2 \neq 0$ 、 $1 \neq 2$ ）がすべて成り立ち、衝突します。

以上により、同じ 2 つのコミットのマージが、ベースの選び方によって「衝突なしで結果 $2$ 」にも「衝突」にもなります。

注意 5.6（Git は複数のマージベースをどう扱うか）

命題 5.5 が示すように、マージベースが複数あるときに「どちらか一方を選ぶ」のは恣意的です。Git の既定のマージ戦略は、代わりにマージベース同士を再帰的にマージして 1 つの仮想ベースを作り、それを基準に 3-way マージを行います。上の例なら、 $A$ （値 $1$ ）と $B$ （値 $0$ ）をベース $R$ （値 $0$ ）でマージして仮想ベース（値 $1$ ）を作り、それを使って $C$ と $D$ をマージするので、衝突せずに $2$ が得られます。

この戦略は長く recursive と呼ばれていましたが、Git 2.34（2021 年）以降は書き直された実装 ort（Ostensibly Recursive’s Twin）が既定になっています。挙動の考え方は同じで、性能とリネーム検出が改善されています。git merge -s resolve を指定すると、複数のマージベースから 1 つを選ぶだけの古い戦略に切り替わり、上の例のような差が観察できます。

命題 5.7（rebase は必ず別のコミットを作る）

コミットオブジェクトの直列化 $\sigma$ は、木の ID、親の ID の並び、作者情報、コミッター情報、メッセージから定まるとし、 $H$ は考えている範囲の直列化の集合上で単射であるとする（定理 3.3 と同じ仮定）。コミット $c$ の親の並びを $(p_1, \ldots, p_k)$ から $(p'_1, \ldots, p'_l)$ に取り替え、他の情報はすべて同じにして作ったコミットを $c'$ とする。もし $k \neq l$ であるか、またはある $j$ で $h(p_j) \neq h(p'_j)$ であるならば、 $h(c) \neq h(c')$ である。

証明（命題 5.7）

仮定より、 $\sigma(c)$ と $\sigma(c')$ は親の ID を記述する部分で異なります。親の ID はコミットオブジェクトの本体に parent <ID> の行として、順序を保って現れるので、 $k \neq l$ なら行数が違い、 $h(p_j) \neq h(p'_j)$ なら $j$ 番目の行の内容が違います。いずれにせよバイト列として $\sigma(c) \neq \sigma(c')$ です。

ここで対偶を考えます。もし $h(c) = h(c')$ 、すなわち $H(\sigma(c)) = H(\sigma(c'))$ ならば、 $H$ の単射性より $\sigma(c) = \sigma(c')$ となり、いま示したことに矛盾します。よって $h(c) \neq h(c')$ です。

git rebase は、あるコミット列の各コミットについて、変更内容（親との差分）を新しい土台の上に適用し直して新しいコミットを作る操作です。命題 5.7 より、rebase 後のコミットは元のコミットとは別の ID を持つ別のオブジェクトです。元のコミットは消えるのではなく、どの参照からも到達できなくなるだけです（例 6.1 の後の Appendix を参照してください）。

この事実から実務上の規則が導かれます。他の人がすでに取得したコミットを rebase してはいけません。 あなたが rebase して git push --force すると、リモートのブランチは新しいコミット列を指します。他の人の手元には古いコミット列が残っているので、次に git pull したときに「同じ変更を表す 2 系統のコミット」が両方履歴に入り、後で重複や無意味な衝突を引き起こします。

やむを得ず強制更新する場合は git push --force-with-lease を使ってください。これは「自分が最後に観測したリモートの値と、いまのリモートの値が一致していれば書き換える」という条件付き更新で、自分が知らないうちに他人が積んだコミットを消してしまう事故を防ぎます。素の --force は無条件に上書きします。

6. 実践：コマンドと共同開発フロー

ここまでのモデルに、日常のコマンドを対応させます。

6.1. `.git` の中身

.git/
├── HEAD              現在のブランチへの間接参照（例: ref: refs/heads/main）
├── config            このリポジトリの設定（リモート URL など）
├── index             ステージ領域。次のコミットで作る木の下書き
├── objects/          オブジェクト格納庫
│   ├── d6/70460b...  緩いオブジェクト（zlib 圧縮された 1 個）
│   └── pack/         パックファイル（多数のオブジェクトを差分圧縮してまとめたもの）
├── refs/
│   ├── heads/main    ブランチ。中身はコミット ID 1 行
│   ├── tags/v1.0     タグ
│   └── remotes/origin/main   リモート追跡ブランチ
└── logs/             参照が動いた履歴（reflog）

中身は git cat-file で覗けます。

$ git cat-file -t HEAD          # 種別を見る
commit
$ git cat-file -p HEAD          # 中身を整形して見る
tree 9f8e7d6c5b4a39281706f5e4d3c2b1a098765432
parent a1b2c3d4e5f60718293a4b5c6d7e8f9012345678
author Hanako Yamada <hanako@example.com> 1755907200 +0900
committer Hanako Yamada <hanako@example.com> 1755907200 +0900

ログイン処理にレート制限を追加

定義 3.1 の表そのままの構造が見えます。tree の行を辿れば木が、parent の行を辿れば履歴が展開できます。

6.2. 主要コマンドとオブジェクト・参照への作用

コマンド	利用者から見た意味	オブジェクトと参照への作用
`git add <path>`	変更をステージする	内容の blob を書き、index の該当項目を更新する
`git commit -m "..."`	ステージした内容を記録する	index から tree を構築し、HEAD を親とする commit を書き、現在のブランチ参照を進める
`git switch -c <name>`	ブランチを作って移動する	`refs/heads/<name>` を現在のコミット ID で作り、HEAD をそこへ向ける
`git merge <branch>`	相手のブランチを取り込む	マージベースを求め、fast-forward か 3-way マージを行う
`git rebase <base>`	自分のコミットを土台に載せ替える	新しい親を持つ commit を作り直し、ブランチ参照をその先頭に向ける
`git fetch <remote>`	リモートの履歴を取得する	不足オブジェクトを取り込み、`refs/remotes/...` を更新する。作業ツリーと自分のブランチは変えない
`git pull`	取得して取り込む	`git fetch` の後に `git merge`（設定によっては `git rebase`）を実行する
`git push <remote> <branch>`	自分の履歴を送る	オブジェクトを送り、リモートの参照を進める。fast-forward でない更新は既定で拒否される

git fetch が作業ツリーを一切変えないことは覚えておく価値があります。「まず git fetch して git log --oneline HEAD..origin/main で相手の変更を確認し、それから取り込む」という手順は、常に安全です。

6.3. プルリクエストに基づく共同開発

GitHub や GitLab で標準になっている流れを、Git の操作として書き下します。ここでは、書き込み権限を持つメンバーが同じリポジトリにブランチを作る方式（外部の貢献者の場合は最初にフォークを作る点だけが異なります）を示します。

最新化する。 git switch main のあと git pull。main を最新のリモートに合わせます。
作業ブランチを作る。 git switch -c feature/rate-limit。ブランチ名は「何をするか」がわかる語にします。
小さくコミットする。 git add -p で意味のある単位に分け、git commit します。1 コミットは「後で単独で取り消せる単位」が目安です。
公開する。 git push -u origin feature/rate-limit。-u は以後 git push だけで済むよう上流を設定するオプションです。
プルリクエスト（PR）を開く。 何を・なぜ変えたかを本文に書きます。差分を読むだけではわからないのは常に「なぜ」です。
自動検査を通す。 CI がテスト・静的解析・ビルドを実行します。CI の実行環境をコンテナ（定義 3.1［Docker と Kubernetes］）で固定する方法は仮想化技術（Docker・Kubernetes）で扱います。
レビューを受けて修正する。 追加コミットを積んで git push します。PR は自動で更新されます。
main の変更を取り込む。 レビュー中に main が進んだら、git fetch のあと git merge origin/main（または方針により git rebase origin/main）を作業ブランチ上で実行します。衝突はここで解消しておきます。
統合する。 PR をマージします。GitHub には 3 つの方式があります。マージコミットを作る方式（履歴の形をそのまま残す）、squash して 1 コミットにする方式（main を読みやすく保つ）、rebase して並べる方式（直線的な履歴になる）です。
後片付け。 作業ブランチを削除し、手元で git switch main と git pull を実行します。

例 6.1（衝突を解消する）

手順 8 で衝突した場合の実際の操作を追います。

$ git fetch origin
$ git merge origin/main
Auto-merging src/auth.py
CONFLICT (content): Merge conflict in src/auth.py
Automatic merge failed; fix conflicts and then commit the result.

src/auth.py を開くと、Git が印を書き込んでいます。

<<<<<<< HEAD
MAX_ATTEMPTS = 5
=======
MAX_ATTEMPTS = 3
>>>>>>> origin/main

<<<<<<< と ======= の間が自分の版、======= と >>>>>>> の間が相手の版です。命題 5.2 の性質 1 の状況、つまりベースの値（例えば MAX_ATTEMPTS = 10）から双方が別々に変更した箇所です。3 つの版をすべて見たいときは、

$ git checkout --conflict=diff3 src/auth.py

とすると、ベースの内容も ||||||| で区切って表示されます。どちらが正しいかは、両方の変更の意図を知らなければ決められません。だから Git は自動判断せず、人間に渡すのです。

解消したら、印を消してから次のようにします。

$ git add src/auth.py          # 「この内容で解決した」と Git に伝える
$ git merge --continue         # マージコミットを作る（git commit でも同じ）

途中でやめたいときは git merge --abort でマージ前の状態に完全に戻せます。オブジェクトが不変であること（定義 3.2）から、参照を戻すだけで元の状態が復元できるためです。

7. 演習

演習 7.1易

echo 'hello world' | git hash-object --stdin が出力する値を、例 2.3 の規則から求めてください。echo は末尾に改行を 1 文字付けることに注意してください。計算は Python の hashlib を使ってかまいません。また、なぜこの値が「どのリポジトリでも、いつ実行しても同じ」になるのかを説明してください。

解答

hello world は 11 バイト、改行が 1 バイトなので内容は 12 バイトです。したがってハッシュを取る対象は b"blob 12\x00hello world\n" です。

import hashlib
content = b"hello world\n"
store = b"blob " + str(len(content)).encode() + b"\x00" + content
print(hashlib.sha1(store).hexdigest())
# => 3b18e512dba79e4c8300dd08aeb37f8e728b8dad

値が普遍的である理由は、定義 2.1 の内容アドレス方式では鍵が内容だけから決まるからです。blob オブジェクトはファイル名・タイムスタンプ・作者・リポジトリの識別子を一切含みません（定義 3.1 の表で、ファイル名を持つのは tree であって blob ではないことを確認してください）。同じ内容のファイルは、世界中のどのリポジトリでも同じ ID を持ちます。これが git fetch で「相手が持っていないオブジェクトだけ」を効率よく判定できる理由でもあります。

演習 7.2標準

次のコミットグラフを考えます。辺は子から親への向きです。

$A$ の親は $R$
$B$ の親は $R$
$C$ の親は $A$
$D$ の親は $A$ と $B$ （マージコミット）
$E$ の親は $C$ と $B$ （マージコミット）

$\mathrm{CA}(D, E)$ を求め、そのうち極大なもの（マージベース）をすべて挙げてください。また、git switch D の状態で git merge E を実行したとき fast-forward になるかどうかを、命題 5.3 を使って判定してください。

解答

まず祖先集合を求めます。 $D$ から親を辿ると $D \to A \to R$ と $D \to B \to R$ なので、 $D$ の祖先は $\{D, A, B, R\}$ です。 $E$ から辿ると $E \to C \to A \to R$ と $E \to B \to R$ なので、 $E$ の祖先は $\{E, C, A, B, R\}$ です。共通部分を取って

\mathrm{CA}(D, E) = \{A, B, R\}

を得ます。

極大性を調べます。 $R \prec A$ かつ $R \prec B$ なので $R$ は極大ではありません。 $A$ の祖先は $\{A, R\}$ で $B$ を含まないので $B \preceq A$ は成り立たず、 $B$ の祖先は $\{B, R\}$ で $A$ を含まないので $A \preceq B$ も成り立ちません。つまり $A$ と $B$ は比較不能で、どちらも極大です。よってマージベースは $A$ と $B$ の 2 つで、この履歴は命題 5.5 の criss-cross と同じ形をしています。

fast-forward の判定。命題 5.3 によれば、fast-forward になるのは $\mathrm{CA}(D,E)$ の極大元が $D$ ただ 1 つのときです。いま極大元は $A$ と $B$ であり、 $D$ ではないうえに 2 つあります。よって fast-forward にはならず、3-way マージが実行されて $D$ と $E$ を親に持つマージコミットが作られます（定義 5.1 の意味で衝突しなければ）。

なお、 $E$ が $D$ の祖先でも子孫でもないことは直接にも確認できます。 $D$ の祖先集合に $E$ は入っておらず、 $E$ の祖先集合に $D$ は入っていないからです。

演習 7.3難

共通のベース $b$ と 3 つの版 $x, y, z$ について、 $u = m_b(x,y)$ を作ってから $m_b(u, z)$ を計算する場合と、 $w = m_b(y,z)$ を作ってから $m_b(x, w)$ を計算する場合を比べます。次を示してください。

各位置 $i$ について $S_i = \{x(i), y(i), z(i)\} \setminus \{b(i)\}$ とおくとき、どちらの順序でも、途中と最後を通じて衝突が起きないための必要十分条件は「すべての $i$ で $|S_i| \le 1$ 」であり、衝突しない場合の最終結果も両者で一致する。

つまり、ベースを固定する限り 3-way マージは結合的です。それにもかかわらず実際の Git でマージの順序が結果を変えうるのはなぜか、命題 5.5 を踏まえて説明してください。

解答

位置 $i$ を固定し、記号を簡単にするため $\beta = b(i)$ , $\xi = x(i)$ , $\eta = y(i)$ , $\zeta = z(i)$ と書きます。定義 5.1 より、 $m_b(x,y)(i)$ は $\{\xi, \eta\} \setminus \{\beta\}$ が空なら $\beta$ 、1 元集合ならその元、2 元集合なら衝突です。これは次のように言い換えられます。

補題。 $|\{\xi,\eta\} \setminus \{\beta\}| \le 1$ のとき、 $u(i) = m_b(x,y)(i)$ は「 $\{\xi,\eta\}$ の中で $\beta$ と異なる唯一の値、そのような値がなければ $\beta$ 」であり、いずれにせよ $\{u(i)\} \setminus \{\beta\} = \{\xi,\eta\} \setminus \{\beta\}$ が成り立つ。

実際、 $\{\xi,\eta\}\setminus\{\beta\} = \{v\}$ なら $u(i) = v$ で $\{v\}\setminus\{\beta\} = \{v\}$ 、 $\{\xi,\eta\}\setminus\{\beta\} = \emptyset$ なら $u(i) = \beta$ で $\{\beta\}\setminus\{\beta\} = \emptyset$ です。

十分性と結果の一致。 すべての $i$ で $|S_i| \le 1$ と仮定します。 $\{\xi,\eta\}\setminus\{\beta\} \subseteq S_i$ なので $|\{\xi,\eta\}\setminus\{\beta\}| \le 1$ であり、 $u = m_b(x,y)$ は衝突せずに定義されます。補題より $\{u(i)\}\setminus\{\beta\} = \{\xi,\eta\}\setminus\{\beta\}$ ですから、

\{u(i), \zeta\} \setminus \{\beta\} \;=\; \bigl(\{u(i)\}\setminus\{\beta\}\bigr) \cup \bigl(\{\zeta\}\setminus\{\beta\}\bigr) \;=\; \bigl(\{\xi,\eta\}\setminus\{\beta\}\bigr) \cup \bigl(\{\zeta\}\setminus\{\beta\}\bigr) \;=\; S_i

となります。仮定より $|S_i| \le 1$ なので 2 段目も衝突せず、結果は「 $S_i$ の唯一の元、または $S_i = \emptyset$ なら $\beta$ 」です。この表式は $x, y, z$ について対称ですから、もう一方の順序でも同じ値になります。

必要性。 ある $i$ で $|S_i| \ge 2$ と仮定し、この順序のどこかで衝突が起きることを示します。 $|S_i| \ge 2$ なので、 $\beta$ と異なる相異なる 2 つの値が $\{\xi,\eta,\zeta\}$ に現れます。

$\{\xi,\eta\}\setminus\{\beta\}$ が 2 元集合なら、1 段目の $m_b(x,y)$ が位置 $i$ で衝突します。
そうでなければ $|\{\xi,\eta\}\setminus\{\beta\}| \le 1$ なので $u$ は定義され、上の計算より $\{u(i),\zeta\}\setminus\{\beta\} = S_i$ です。 $|S_i| \ge 2$ かつ $|\{u(i),\zeta\}\setminus\{\beta\}| \le 2$ なので $|S_i| = 2$ となり、2 段目の $m_b(u,z)$ が位置 $i$ で衝突します。

いずれの場合も衝突が起きます。同じ議論が $x,y,z$ の入れ替えでそのまま通るので、もう一方の順序でも衝突します。以上で必要十分性が示せました。

Git で順序が効く理由。 いま示したのは「ベース $b$ を固定すれば」という条件付きの結合性です。実際の Git はベースを固定しません。マージのたびに、そのときの 2 つのコミットからマージベースを計算し直します。マージを 1 回行うと新しいマージコミットができ、コミットグラフの形が変わるので、次のマージのマージベースは前回と違うコミットになりえます。命題 5.5 は、ベースが変われば衝突の有無すら変わることを具体的に示しています。したがって「取り込む順番を変えたら衝突した」という現象は、3-way マージの規則そのものの非結合性ではなく、ベース選択が履歴の形に依存することから来ています。

演習 7.4標準

あなたと同僚が同じブランチ feature/x で作業しています。あなたが git rebase main を実行して git push --force しました。同僚の手元では次に git pull したときに何が起きますか。命題 5.7 を使って説明し、--force-with-lease がどのような事故を防ぐのかを述べてください。

解答

rebase は各コミットの親を付け替えます。命題 5.7 より、親の並びが変わったコミットは必ず別の ID を持ちます。したがって rebase 後のリモート feature/x は、同僚が持っているコミットとは別のコミットの列を指しています。

同僚が既定設定で git pull すると、git fetch に続いて git merge origin/feature/x が走ります。同僚のローカル feature/x が指す旧コミット $c$ と、リモートの新コミット $c'$ について、 $c \preceq c'$ は成り立ちません（ $c'$ の祖先には $c$ が現れないからです）。よって命題 5.3 より fast-forward にはならず、3-way マージが実行されます。その結果、同じ変更を表す 2 系統のコミットが両方とも履歴に残ります。同じ行への同じ変更が 2 度現れるため、内容によっては大量の衝突が出るか、衝突せずに変更が二重適用されて壊れます。ここで同僚がそのまま push すると、あなたが消したはずの旧コミットがリモートに戻ってきます。

正しい対処は、同僚が git fetch のあと自分の未 push のコミットだけを新しい土台に載せ直すこと、例えば git rebase --onto origin/feature/x <旧の分岐点> feature/x を実行することです。ただし、そもそもこの手間を発生させないために、共有ブランチでは rebase しないのが原則です。

--force-with-lease が防ぐのは別の事故です。素の --force は、リモートの現在の値を一切確認せずに参照を上書きします。あなたが git fetch してから push するまでの間に同僚が新しいコミットを push していた場合、そのコミットはどの参照からも到達できなくなり、実質的に失われます。--force-with-lease は「リモートの現在の値が、自分が最後に取得したときの値と一致していること」を条件に付けた更新です。条件が破れていれば push が失敗するので、知らないうちに他人の作業を消す事故を防げます。これは楽観的並行制御における条件付き更新（compare-and-swap）と同じ仕組みです。

参考文献

Scott Chacon, Ben Straub, Pro Git, 2nd ed., Apress, 2014 — 第 3 章「Git Branching」と第 10 章「Git Internals」。全文が https://git-scm.com/book/ja/v2 で公開されており、日本語訳もあります。この記事の §3 の内容は第 10 章に対応します。
Git 公式リファレンス https://git-scm.com/docs — 特に git-merge-base、gitrevisions、githooks、および hash-function-transition の設計文書。
Marc J. Rochkind, “The Source Code Control System”, IEEE Transactions on Software Engineering SE-1, no. 4 (1975), 364–370. DOI: 10.1109/TSE.1975.6312866 — SCCS の原論文。バージョン管理という問題設定そのものを定式化しています。
Walter F. Tichy, “RCS — A System for Version Control”, Software: Practice and Experience 15, no. 7 (1985), 637–654. DOI: 10.1002/spe.4380150703 — 逆差分による履歴保持とロック方式。
Sanjeev Khanna, Keshav Kunal, Benjamin C. Pierce, “A Formal Investigation of Diff3”, in FSTTCS 2007, Lecture Notes in Computer Science 4855, Springer, 2007, 485–496. DOI: 10.1007/978-3-540-77050-3_40 — 3-way マージ（diff3）の代数的性質を扱った論文。§5 の形式化はこの系統の議論を簡略化したものです。
Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov, “The First Collision for Full SHA-1”, in CRYPTO 2017, Lecture Notes in Computer Science 10401, Springer, 2017, 570–596. DOI: 10.1007/978-3-319-63688-7_19 — 注意 2.4 で触れた衝突の構成。
Eugene W. Myers, “An O(ND) Difference Algorithm and Its Variations”, Algorithmica 1 (1986), 251–266. DOI: 10.1007/BF01840446 — git diff が既定で使う差分アルゴリズム。3-way マージの前段にあたる「位置の対応付け」を与えます。

Appendix: 失った作業を取り戻す

参照は動くが、オブジェクトは消えない。 git reset --hard でコミットを捨てたつもりでも、git rebase で古いコミット列を置き換えたつもりでも、定義 3.2 のとおり動いたのは参照だけで、オブジェクトは格納庫に残っています。残っているものを見つけられれば復旧できます。

まず reflog を見る。 Git は .git/logs/ に、各参照が「いつ・どの値から・どの値へ」動いたかを記録しています。これを reflog といいます。

$ git reflog
d0e1f2a HEAD@{0}: reset: moving to HEAD~3
9c8b7a6 HEAD@{1}: commit: 認証エラーのログを追加
5f4e3d2 HEAD@{2}: commit: レート制限を実装

HEAD@{1} のような表記で過去の位置を参照できます。捨てたコミットに戻るには git reset --hard HEAD@{1}、そこから枝を生やすには git switch -c rescue HEAD@{1} とします。reflog はローカルの記録なので、git clone した相手には引き継がれません。

reflog にもなければ fsck を使う。 どの参照からも reflog からも辿れないオブジェクトは、git fsck --lost-found で列挙できます。出力の dangling commit <ID> が孤立したコミットです。git show <ID> で内容を確認し、必要なら git switch -c rescue <ID> で救出します。

ただし無期限ではない。 git gc は、到達不能なオブジェクトを一定期間後に本当に削除します。既定では、到達可能な参照の reflog は約 90 日、到達不能なものの reflog は約 30 日で期限切れになります（gc.reflogExpire と gc.reflogExpireUnreachable で設定できます）。事故に気づいたら早めに探してください。そして、重要な作業は早めに push してください。分散型 VCS における最良のバックアップは、別のクローンが存在することです。リモートの可用性そのものについてはクラウドコンピューティング（AWS, GCP）（可用性の定義は定義 6.1［クラウドコンピューティング］、複製を増やすと可用性が上がることの計算は命題 6.2［クラウドコンピューティング］）、git push が実際に何を喋っているかについてはネットワーク（TCP/IP）（定義 2.1［ネットワーク（TCP/IP）］）を参照してください。

この記事の誤りを報告する・運営: 夢現技研合同会社・料金プラン・利用条件・特定商取引法に基づく表記