# バージョン管理システム Git：Merkle DAG としての履歴と共同開発フロー > Git の内容アドレス格納庫とコミット DAG を定義し、ハッシュが履歴全体の完全性を保証すること、fast-forward の判定条件、3-way マージとマージベースが一意にならない場合を証明とともに示し、主要コマンドとプルリクエスト運用に結び付けます。 > https://rikai.mugen-giken.com/computer-science/software-engineering/version-control-git ## 0. この記事の要点 - Git は「差分の列」ではなく、**内容のハッシュをアドレスとする不変オブジェクトの集まり**です。コミットは、そのときのファイル木全体へのポインタと、親コミットへのポインタを持ちます。 - 全オブジェクトが子のハッシュを含む形で直列化されるため、オブジェクトグラフは Merkle DAG になります。その帰結として、**コミットハッシュ 40 文字を照合すれば、そこから到達できる履歴とファイル内容のすべてが確定します**（）。 - ブランチは「コミットを指す名前つきポインタ」にすぎません。`git branch` が安価なのはこのためです。 - `git merge` は 2 つのコミットの**マージベース**（共通祖先の極大元）を求め、ベース・自分・相手の 3 つの版から 3-way マージを行います。マージベースが HEAD 自身になることと、HEAD が相手の祖先であることは同値で、これが fast-forward の正体です（）。 - マージベースは一意とは限りません。criss-cross と呼ばれる履歴では 2 つ以上になり、どれを選ぶかでマージ結果が変わります（）。Git の既定戦略はこの問題を「ベース同士をマージして仮想ベースを作る」ことで処理します。 - rebase は親を付け替えるので、必ず別のハッシュを持つ**別のコミット**を作ります（）。共有ブランチで rebase してはいけない理由がここにあります。 ## 1. 動機：バージョン管理は何を解く問題か `report.docx`、`report_v2.docx`、`report_v2_修正.docx`、`report_最終.docx`、`report_最終_本当に最終.docx`。誰もが一度は作ったことのあるファイル名の列です。これは素朴なバージョン管理であり、実際にある程度は機能します。しかし次の 3 つの問いに答えられません。 1. `report_v2.docx` と `report_v2_修正.docx` の**違いは何か**。ファイル名は違いを記録しません。 2. `report_最終.docx` は `report_v2.docx` から作られたのか、`report_v2_修正.docx` から作られたのか。つまり**どれが誰の子孫なのか**。 3. 2 人が同時に `report_v2.docx` を編集して別々に保存したとき、**両方の変更を残すにはどうするか**。 1 番目は「差分」、2 番目は「履歴の構造」、3 番目は「並行編集の統合」の問題です。バージョン管理システム（VCS）とは、この 3 つを同時に扱う道具のことです。 歴史的には、この 3 つは順に解かれてきました。1970 年代前半に Bell 研究所の Marc Rochkind が作った SCCS が、ファイルの改訂履歴を 1 つの保管ファイルにまとめる方式を確立します。1980 年代前半に Purdue 大学の Walter Tichy が作った RCS はこれを改良し、最新版を丸ごと持ち、過去へ遡る差分（逆差分）を蓄える方式を採りました。どちらも 3 番目の問題は「ロック」で回避します。編集する人がファイルを排他ロックし、他の人は待つ、という方式です。 ロック方式は、開発者が数人ならうまくいきます。しかし数十人になると待ち行列が破綻します。そこで CVS（1980 年代後半）以降は方針が反転し、**誰でも自由に編集してよい、衝突したら後で統合する**という楽観的な方式が主流になりました。データベースの同時実行制御でいう楽観的並行制御と同じ発想です（[データベース設計の基礎](/computer-science/software-engineering/database-design) も参照してください）。統合の道具が、この記事の後半で扱う 3-way マージです。 CVS と、その後継である Subversion（2000 年〜）には、なお中央集権という制約が残っていました。履歴はサーバーにしかなく、コミットするにはネットワークが要ります。ブランチを切るのはサーバー上のディレクトリコピーで、重い操作でした。 2005 年 4 月、Linux カーネル開発チームが使っていた商用の分散型 VCS である BitKeeper の無償利用が打ち切られます。Linus Torvalds は代替を数週間で書き上げました。これが Git です。設計上の要求は明確でした。数万ファイル・数十万コミットの規模で高速に動くこと、ネットワークなしで全操作ができること、そして**履歴の改竄を検出できること**です。3 番目の要求が、Git を単なるファイル履歴管理ではなく、暗号学的ハッシュに基づくデータ構造にしました。 ## 2. 準備：ハッシュ関数と内容アドレス方式 Git を理解する鍵は、ファイルに名前で触らず、**内容のハッシュ値で触る**という発想です。まずその道具立てを定義します。 $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 文字で表示されます。「衝突困難」が実際にどれくらいの安全余裕を意味するのか、数で確認しておきます。 $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}} $$ を満たす。 $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 数を入れてみます。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$ が乱数のように振る舞うという仮定のもとの話で、**攻撃者が意図的に衝突を作れるかどうかは別問題**です。この点は で述べます。 Git はファイル内容 $c$ をそのままハッシュするのではなく、種別と長さを前置したバイト列 $$ \sigma = \texttt{"blob "} \,\Vert\, |c| \,\Vert\, \texttt{NUL} \,\Vert\, c $$ をハッシュします（$\Vert$ は連結、$|c|$ は $c$ のバイト数の 10 進表記、`NUL` は 1 バイトの `0x00`）。内容が `test content` と改行 1 文字、すなわち 13 バイトの場合を計算します。 ```python 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 本体からも得られます。 ```bash $ 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` です。この値はどのリポジトリでも同じで、「空の木」を指す定数としてスクリプトでよく使われます。 2017 年、Stevens らが SHA-1 の完全な衝突（同じ SHA-1 値を持つ相異なる 2 つの PDF）を実際に構成しました。これは の仮定が破れた例です。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 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 と呼びます。
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（更新前）"]`} />
**参照**（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 つ書くだけだからです。 オブジェクトの有限集合 $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 が一致すれば、そこから辿れるオブジェクトの集合とその中身は完全に一致する。 まず、参照関係が有向非巡回であることを確かめます。オブジェクト $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` はこの検証を全オブジェクトについて実行するコマンドです。 「コミットはプロジェクト全体のスナップショット」と聞くと、1000 ファイルのプロジェクトで 100 回コミットしたら 10 万個の blob ができるように思えます。実際にはそうなりません。 の内容アドレス方式では、**内容が同じなら ID が同じ**だからです。1 ファイルだけ変えてコミットすると、新しくできるのは変更されたファイルの blob 1 個、そのファイルを含むディレクトリの木、その先祖ディレクトリの木、そして commit 1 個だけです。深さ $d$ の位置にある 1 ファイルを変更したときに増えるオブジェクトは $1 + d + 1$ 個で、ファイル総数には依存しません。 の後に示したオブジェクトグラフの図でいえば、`README.md` の blob B1 が 2 つの木から共有されている状況です。 さらに Git は、緩いオブジェクトがたまると `git gc` でそれらを**パックファイル**に詰め直し、内容が似たオブジェクト同士を差分（デルタ）圧縮します。ここで重要なのは、この差分はあくまで**格納形式の最適化**であって、履歴の意味を担っていないことです。デルタの相手はコミットの親とは限らず、単に内容が似ているものが選ばれます。RCS や Subversion では差分が履歴そのものでしたが、Git では履歴は commit の親ポインタが担い、差分は圧縮の都合にすぎません。この分離のおかげで、`git log` の表示や `git diff` の計算は、格納形式と独立に定義できます。なお、「内容が同じものは 1 つだけ持ち、複数の版から共有する」という発想は Git 固有のものではなく、コンテナイメージのレイヤ（）も同じ仕組みで容量と転送量を抑えています。 `.git/index` は、次のコミットで作られる木の下書きを保持するバイナリファイルです。作業ツリーのファイルパスと、対応する blob の ID、モード、更新時刻などが並んでいます。`git add` は作業ツリーのファイルを読んで blob を書き込み、インデックスの該当行を更新します。`git commit` はインデックスから木オブジェクトを構築し、それを指すコミットを作ります。「作業ツリー・インデックス・HEAD」という 3 つの状態があることが Git の学習を難しくしていますが、逆にいえば、コミットする内容を作業ツリーとは独立に組み立てられるということです。`git add -p` で 1 つのファイルの一部の変更だけをステージできるのはこの構造のおかげです。 ## 4. コミットグラフ：祖先関係とマージベース 以降、オブジェクトのうち commit だけを取り出したグラフを考えます。 リポジトリのコミット全体を頂点集合 $C$、各コミットからその親コミットへの辺の全体を $E$ とする有向グラフ $G = (C, E)$ を**コミットグラフ**という。$G$ は有限 DAG である（ の証明冒頭と同じ議論による）。 $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$ の**マージベース**という。 の $\preceq$ は $C$ 上の半順序である。すなわち、反射律・推移律・反対称律を満たす。 **反射律。** 任意の $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 であること（）に矛盾します。よって $a = b$ です。 有限コミットグラフ $G = (C, E)$ において、$a, b \in C$ が共通祖先を少なくとも 1 つ持つ、すなわち $\mathrm{CA}(a,b) \neq \emptyset$ と仮定する。このとき $\mathrm{CA}(a,b)$ は $\preceq$ に関する極大元を少なくとも 1 つ持つ。特に、リポジトリのすべてのコミットが唯一の根コミット $r$（親を持たないコミット）の子孫であるならば、任意の $a, b$ についてマージベースが存在する。 $\mathrm{CA}(a,b) \subseteq C$ は有限集合で、仮定より空でありません。 より $\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 マージといいます。まず抽象化して定義します。 有限集合 $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$ を集合として定義したので、場合分けの重複を気にせずに済み、可換性なども見やすくなります。 の記法のもとで、任意の版 $b, x, y$ について次が成り立つ。 1. （衝突の特徴づけ）位置 $i$ で衝突が起きるための必要十分条件は、$x(i) \neq b(i)$ かつ $y(i) \neq b(i)$ かつ $x(i) \neq y(i)$ が成り立つことである。 2. （可換性）$x, y$ が $b$ を基準として衝突しないならば $y, x$ も衝突せず、$m_b(x,y) = m_b(y,x)$ である。 3. （ベースは単位元）$b$ と $y$ は $b$ を基準として決して衝突せず、$m_b(b,y) = y$ である。 4. （冪等性）$x$ と $x$ は $b$ を基準として決して衝突せず、$m_b(x,x) = x$ である。 **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 の理論的な中身です。 コミット $a$（現在の HEAD が指すコミット）と $b$（取り込む相手のコミット）について、$\mathrm{CA}(a,b) \neq \emptyset$ とする。このとき次の 2 つは同値である。 1. $a \preceq b$、すなわち $a$ は $b$ の祖先である。 2. $\mathrm{CA}(a,b)$ の極大元がちょうど $a$ ただ 1 つである（マージベースが $a$ 自身）。 さらにこのとき、ベースを $a$ の木、2 つの版を $a$ の木と $b$ の木として 3-way マージを行うと衝突は起きず、結果は $b$ の木に一致する。したがって Git は新しいコミットを作らず、ブランチの参照の値を $a$ から $b$ に書き換えるだけでよい。この操作を **fast-forward** という。 **1 から 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$ の木です。 の性質 3 を、ベースの版を $a$ の木、一方の版をそれと同じ $a$ の木、他方の版を $b$ の木として適用すると、衝突は起きず、結果は $b$ の木に一致します。結果の木が $b$ の木と同じで、かつ $a \preceq b$ より $b$ は $a$ の子孫ですから、$a$ と $b$ の両方を親に持つ新しいコミットを作る意味がありません。参照を $b$ に進めれば十分です。 `main` から `feature` を切り、`feature` だけで 2 回コミットした状況を考えます。`main` が指すコミットを $a$、`feature` が指すコミットを $b$ とすると $a \prec b$ です。 ```bash $ git switch main $ git merge feature Updating a1b2c3d..d0e1f2a Fast-forward src/auth.py | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) ``` `Fast-forward` と表示され、マージコミットは作られていません。 の状況です。履歴は 1 本の直線になり、`feature` というブランチが存在したという情報は残りません。 一方、この間に他の人が `main` に 1 コミット積んでいれば、`main` の指す $a'$ は $b$ の祖先ではありません。$\mathrm{CA}(a', b) = \{a, \ldots\}$ で極大元は $a$ ですから、 の条件 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 つに定まることを暗に前提にしていました。しかしこれは一般には成り立ちません。
A["A"] C --> B["B"] D["D（A と B のマージ）"] --> A D --> B A --> R["R（根コミット）"] B --> R`} />
マージベースが 2 つ以上存在するコミットグラフと、各コミットに割り当てられたファイル内容であって、次を満たすものが存在する。片方のマージベースを基準にすると 3-way マージは衝突せず、もう片方のマージベースを基準にすると衝突する。 図の 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$ でマージすると、 より $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$ ですから、 の性質 1 の条件（$1 \neq 0$、$2 \neq 0$、$1 \neq 2$）がすべて成り立ち、衝突します。 以上により、同じ 2 つのコミットのマージが、ベースの選び方によって「衝突なしで結果 $2$」にも「衝突」にもなります。 が示すように、マージベースが複数あるときに「どちらか一方を選ぶ」のは恣意的です。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 つを選ぶだけの古い戦略に切り替わり、上の例のような差が観察できます。 コミットオブジェクトの直列化 $\sigma$ は、木の ID、親の ID の並び、作者情報、コミッター情報、メッセージから定まるとし、$H$ は考えている範囲の直列化の集合上で単射であるとする（ と同じ仮定）。コミット $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')$ である。 仮定より、$\sigma(c)$ と $\sigma(c')$ は親の ID を記述する部分で異なります。親の ID はコミットオブジェクトの本体に `parent ` の行として、順序を保って現れるので、$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` は、あるコミット列の各コミットについて、変更内容（親との差分）を新しい土台の上に適用し直して新しいコミットを作る操作です。 より、rebase 後のコミットは元のコミットとは**別の ID を持つ別のオブジェクト**です。元のコミットは消えるのではなく、どの参照からも到達できなくなるだけです（ の後の Appendix を参照してください）。 ## 6. 実践：コマンドと共同開発フロー ここまでのモデルに、日常のコマンドを対応させます。 ### 6.1. `.git` の中身 ```text .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` で覗けます。 ```bash $ git cat-file -t HEAD # 種別を見る commit $ git cat-file -p HEAD # 中身を整形して見る tree 9f8e7d6c5b4a39281706f5e4d3c2b1a098765432 parent a1b2c3d4e5f60718293a4b5c6d7e8f9012345678 author Hanako Yamada 1755907200 +0900 committer Hanako Yamada 1755907200 +0900 ログイン処理にレート制限を追加 ``` の表そのままの構造が見えます。`tree` の行を辿れば木が、`parent` の行を辿れば履歴が展開できます。 ### 6.2. 主要コマンドとオブジェクト・参照への作用 | コマンド | 利用者から見た意味 | オブジェクトと参照への作用 | |---|---|---| | `git add ` | 変更をステージする | 内容の blob を書き、index の該当項目を更新する | | `git commit -m "..."` | ステージした内容を記録する | index から tree を構築し、HEAD を親とする commit を書き、現在のブランチ参照を進める | | `git switch -c ` | ブランチを作って移動する | `refs/heads/` を現在のコミット ID で作り、HEAD をそこへ向ける | | `git merge ` | 相手のブランチを取り込む | マージベースを求め、fast-forward か 3-way マージを行う | | `git rebase ` | 自分のコミットを土台に載せ替える | 新しい親を持つ commit を作り直し、ブランチ参照をその先頭に向ける | | `git fetch ` | リモートの履歴を取得する | 不足オブジェクトを取り込み、`refs/remotes/...` を更新する。作業ツリーと自分のブランチは変えない | | `git pull` | 取得して取り込む | `git fetch` の後に `git merge`（設定によっては `git rebase`）を実行する | | `git push ` | 自分の履歴を送る | オブジェクトを送り、リモートの参照を進める。fast-forward でない更新は既定で拒否される | `git fetch` が作業ツリーを一切変えないことは覚えておく価値があります。「まず `git fetch` して `git log --oneline HEAD..origin/main` で相手の変更を確認し、それから取り込む」という手順は、常に安全です。 ### 6.3. プルリクエストに基づく共同開発 GitHub や GitLab で標準になっている流れを、Git の操作として書き下します。ここでは、書き込み権限を持つメンバーが同じリポジトリにブランチを作る方式（外部の貢献者の場合は最初にフォークを作る点だけが異なります）を示します。 1. **最新化する。** `git switch main` のあと `git pull`。`main` を最新のリモートに合わせます。 2. **作業ブランチを作る。** `git switch -c feature/rate-limit`。ブランチ名は「何をするか」がわかる語にします。 3. **小さくコミットする。** `git add -p` で意味のある単位に分け、`git commit` します。1 コミットは「後で単独で取り消せる単位」が目安です。 4. **公開する。** `git push -u origin feature/rate-limit`。`-u` は以後 `git push` だけで済むよう上流を設定するオプションです。 5. **プルリクエスト（PR）を開く。** 何を・なぜ変えたかを本文に書きます。差分を読むだけではわからないのは常に「なぜ」です。 6. **自動検査を通す。** CI がテスト・静的解析・ビルドを実行します。CI の実行環境をコンテナ（）で固定する方法は [仮想化技術（Docker・Kubernetes）](/computer-science/software-engineering/containers-and-kubernetes) で扱います。 7. **レビューを受けて修正する。** 追加コミットを積んで `git push` します。PR は自動で更新されます。 8. **`main` の変更を取り込む。** レビュー中に `main` が進んだら、`git fetch` のあと `git merge origin/main`（または方針により `git rebase origin/main`）を作業ブランチ上で実行します。衝突はここで解消しておきます。 9. **統合する。** PR をマージします。GitHub には 3 つの方式があります。マージコミットを作る方式（履歴の形をそのまま残す）、squash して 1 コミットにする方式（`main` を読みやすく保つ）、rebase して並べる方式（直線的な履歴になる）です。 10. **後片付け。** 作業ブランチを削除し、手元で `git switch main` と `git pull` を実行します。 手順 8 で衝突した場合の実際の操作を追います。 ```bash $ 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 が印を書き込んでいます。 ```text <<<<<<< HEAD MAX_ATTEMPTS = 5 ======= MAX_ATTEMPTS = 3 >>>>>>> origin/main ``` `<<<<<<<` と `=======` の間が自分の版、`=======` と `>>>>>>>` の間が相手の版です。 の性質 1 の状況、つまりベースの値（例えば `MAX_ATTEMPTS = 10`）から双方が別々に変更した箇所です。3 つの版をすべて見たいときは、 ```bash $ git checkout --conflict=diff3 src/auth.py ``` とすると、ベースの内容も `|||||||` で区切って表示されます。どちらが正しいかは、両方の変更の意図を知らなければ決められません。だから Git は自動判断せず、人間に渡すのです。 解消したら、印を消してから次のようにします。 ```bash $ git add src/auth.py # 「この内容で解決した」と Git に伝える $ git merge --continue # マージコミットを作る（git commit でも同じ） ``` 途中でやめたいときは `git merge --abort` でマージ前の状態に完全に戻せます。オブジェクトが不変であること（）から、参照を戻すだけで元の状態が復元できるためです。 ## 7. 演習 `echo 'hello world' | git hash-object --stdin` が出力する値を、 の規則から求めてください。`echo` は末尾に改行を 1 文字付けることに注意してください。計算は Python の `hashlib` を使ってかまいません。また、なぜこの値が「どのリポジトリでも、いつ実行しても同じ」になるのかを説明してください。 `hello world` は 11 バイト、改行が 1 バイトなので内容は 12 バイトです。したがってハッシュを取る対象は `b"blob 12\x00hello world\n"` です。 ```python import hashlib content = b"hello world\n" store = b"blob " + str(len(content)).encode() + b"\x00" + content print(hashlib.sha1(store).hexdigest()) # => 3b18e512dba79e4c8300dd08aeb37f8e728b8dad ``` 値が普遍的である理由は、 の内容アドレス方式では**鍵が内容だけから決まる**からです。blob オブジェクトはファイル名・タイムスタンプ・作者・リポジトリの識別子を一切含みません（ の表で、ファイル名を持つのは tree であって blob ではないことを確認してください）。同じ内容のファイルは、世界中のどのリポジトリでも同じ ID を持ちます。これが `git fetch` で「相手が持っていないオブジェクトだけ」を効率よく判定できる理由でもあります。 次のコミットグラフを考えます。辺は子から親への向きです。 - $A$ の親は $R$ - $B$ の親は $R$ - $C$ の親は $A$ - $D$ の親は $A$ と $B$（マージコミット） - $E$ の親は $C$ と $B$（マージコミット） $\mathrm{CA}(D, E)$ を求め、そのうち極大なもの（マージベース）をすべて挙げてください。また、`git switch D` の状態で `git merge E` を実行したとき fast-forward になるかどうかを、 を使って判定してください。 まず祖先集合を求めます。$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 つで、この履歴は の criss-cross と同じ形をしています。 fast-forward の判定。 によれば、fast-forward になるのは $\mathrm{CA}(D,E)$ の極大元が $D$ ただ 1 つのときです。いま極大元は $A$ と $B$ であり、$D$ ではないうえに 2 つあります。よって fast-forward にはならず、3-way マージが実行されて $D$ と $E$ を親に持つマージコミットが作られます（ の意味で衝突しなければ）。 なお、$E$ が $D$ の祖先でも子孫でもないことは直接にも確認できます。$D$ の祖先集合に $E$ は入っておらず、$E$ の祖先集合に $D$ は入っていないからです。 共通のベース $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 でマージの順序が結果を変えうるのはなぜか、 を踏まえて説明してください。 位置 $i$ を固定し、記号を簡単にするため $\beta = b(i)$, $\xi = x(i)$, $\eta = y(i)$, $\zeta = z(i)$ と書きます。 より、$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 回行うと新しいマージコミットができ、コミットグラフの形が変わるので、次のマージのマージベースは前回と違うコミットになりえます。 は、ベースが変われば衝突の有無すら変わることを具体的に示しています。したがって「取り込む順番を変えたら衝突した」という現象は、3-way マージの規則そのものの非結合性ではなく、**ベース選択が履歴の形に依存すること**から来ています。 あなたと同僚が同じブランチ `feature/x` で作業しています。あなたが `git rebase main` を実行して `git push --force` しました。同僚の手元では次に `git pull` したときに何が起きますか。 を使って説明し、`--force-with-lease` がどのような事故を防ぐのかを述べてください。 rebase は各コミットの親を付け替えます。 より、親の並びが変わったコミットは必ず別の ID を持ちます。したがって rebase 後のリモート `feature/x` は、同僚が持っているコミットとは**別のコミットの列**を指しています。 同僚が既定設定で `git pull` すると、`git fetch` に続いて `git merge origin/feature/x` が走ります。同僚のローカル `feature/x` が指す旧コミット $c$ と、リモートの新コミット $c'$ について、$c \preceq c'$ は成り立ちません（$c'$ の祖先には $c$ が現れないからです）。よって より 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](https://git-scm.com/book/ja/v2) で公開されており、日本語訳もあります。この記事の §3 の内容は第 10 章に対応します。 - Git 公式リファレンス [https://git-scm.com/docs](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](https://doi.org/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](https://doi.org/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](https://doi.org/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](https://doi.org/10.1007/978-3-319-63688-7_19) — で触れた衝突の構成。 - Eugene W. Myers, "An O(ND) Difference Algorithm and Its Variations", *Algorithmica* 1 (1986), 251–266. [DOI: 10.1007/BF01840446](https://doi.org/10.1007/BF01840446) — `git diff` が既定で使う差分アルゴリズム。3-way マージの前段にあたる「位置の対応付け」を与えます。 ## Appendix: 失った作業を取り戻す **参照は動くが、オブジェクトは消えない。** `git reset --hard` でコミットを捨てたつもりでも、`git rebase` で古いコミット列を置き換えたつもりでも、 のとおり動いたのは参照だけで、オブジェクトは格納庫に残っています。残っているものを見つけられれば復旧できます。 **まず reflog を見る。** Git は `.git/logs/` に、各参照が「いつ・どの値から・どの値へ」動いたかを記録しています。これを reflog といいます。 ```bash $ 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 ` が孤立したコミットです。`git show ` で内容を確認し、必要なら `git switch -c rescue ` で救出します。 **ただし無期限ではない。** `git gc` は、到達不能なオブジェクトを一定期間後に本当に削除します。既定では、到達可能な参照の reflog は約 90 日、到達不能なものの reflog は約 30 日で期限切れになります（`gc.reflogExpire` と `gc.reflogExpireUnreachable` で設定できます）。事故に気づいたら早めに探してください。そして、重要な作業は早めに push してください。分散型 VCS における最良のバックアップは、別のクローンが存在することです。リモートの可用性そのものについては [クラウドコンピューティング（AWS, GCP）](/computer-science/software-engineering/cloud-computing)（可用性の定義は 、複製を増やすと可用性が上がることの計算は ）、`git push` が実際に何を喋っているかについては [ネットワーク（TCP/IP）](/computer-science/software-engineering/networking-tcp-ip)（）を参照してください。