質問: Git のドキュメントによると、`git merge` は内部で 3-way merge を行います。 2-way merge だと不都合があるのは分かるのですが、ではこの 3-way merge は具体的にどのようなアルゴリズムでマージをするのでしょうか? 厳密には 3-way merge と recursive 3-way merge というものがあるようですが、ここでは Git が内部で使っているものの詳細を教えて頂きたいです。
回答: 「way」とは ここでの「way」とは、マージする際に "見て" いる場所のこと。3-way merge は 3 つの場所を見ている。 * 2-way merge:「マージの起点コミット」「マージさせたいコミット」を見てマージする * 3-way merge:「マージの起点コミット」「マージさせたいコミット」「2 つのコミットの最近共通祖先となるコミット」を見てマージする アルゴリズムの概略 ここでは Git のデフォルト・マージ戦略である「recursive」にしたがった 3-way merge のアルゴリズムを書きます。簡単のために省略して書いています。 * **入力**: コミットグラフ。マージの起点としたいコミット `X`。`X` にマージしたいコミット `Y`。 * **出力**: マージできるかどうか。マージできるなら、マージ済みコミット `Z` を含む新しいコミットグラフ。マージできないなら、コンフリクト箇所。 * **手順** 1. **`X` と `Y` の共通祖先となるコミット `B` (base) を見つける**。このとき、`X` と `Y` に最も近い共通祖先を見つける。そのような祖先が一意に定まらない場合があるが、後述するように上手く処理される。 2. **`X` と `B` の diff、`Y` と `B` の diff をそれぞれ求める**。 3. **2つの diff 結果をそれぞれの変更箇所ごとに比較しつつマージする**。両方が同じ変更を行っている場合、そのまま採用する。片方が変更して他方が何もしていない場合、変更している方を採用する。同じ箇所で異なる変更が行われている場合、自動マージできないのでその部分のコンフリクトを報告する。 4. **結果を出力する**。自動マージがすべて成功した場合、マージコミットを `Z` を作って付け足したコミットグラフを作る。そうでない場合、コンフリクト箇所を示す (手動マージに任せる)。 上の手順ではひとつ説明していない部分があるので、以下それを説明します。 ### 共通祖先 `B` が一意に定まらない場合について `X` と `Y` の共通祖先が複数あり、どれが最も近いか決められない場合があります。 ``` ( )----( )----(P)-----( )----(X) | | | | | +---+ | | | | +-------+ | | | | +---+ | | | | +-----(Q)-----(Y) 親コミット <-- --> 子コミット ``` たとえば上のように交差したコミットグラフでは、`P` と `Q` は共に `X` と `Y` に近い共通祖先です。`P` と `Q` のどちらがより近いのかは、グラフからは比較不能です。共通祖先 `B` の候補が 2 つ出てきてしまいました。 この場合 recursive 3-way merge では、共通祖先たちをマージした**仮想的なコミット**を作り、その仮想コミットを `B` だと思って次の手順に移ります。なお共通祖先が 3 つ以上あった場合は先頭の 2 つから順番に「2 つのコミットをマージする」を繰り返します。祖先のマージをする際にも同じ問題が起こる可能性があるため、このマージは再帰的に (recursive に) 行われます。 こうすることで共通祖先が複数あってもひとつだと思うことができます。この手法は、実験する限りは良い感じだと考えられています。 > > This has been reported to result in fewer merge conflicts without causing mismerges by tests done on actual merge commits taken from Linux 2.6 kernel development history. > > > > > > この回答で説明されていないこと * Fast-forward merge * recursive 以外のマージ戦略 (resolve, octopus, ours, subtree) * recursive 戦略の細かいオプション * ファイルの削除やリネームも合わせて考えたマージ * ファイルのパーミッションだけ変わった場合の処理 参考 * How does 'git merge' work in details? -- Stack Overflow * Plastic SCM のブログ記事 + Three-way merging: A look under the hood + The basics: elements of a merge + More on recursive merge strategy * Git ドキュメント + git-merge-base + git-merge * Git のソースコード + merge-recursive.c * Merge (version control)) -- Wikipedia 英語版 * 7.8 Git のさまざまなツール - 高度なマージ手法 -- Pro Git