Git のドキュメントによると、git merge
は内部で 3-way merge を行います。
2-way merge だと不都合があるのは分かるのですが、ではこの 3-way merge は具体的にどのようなアルゴリズムでマージをするのでしょうか? 厳密には 3-way merge と recursive 3-way merge というものがあるようですが、ここでは Git が内部で使っているものの詳細を教えて頂きたいです。
スタック・オーバーフローはプログラマーとプログラミングに熱心な人のためのQ&Aサイトです。すぐ登録できます。
登録してこのコミュニティに参加するGit のドキュメントによると、git merge
は内部で 3-way merge を行います。
2-way merge だと不都合があるのは分かるのですが、ではこの 3-way merge は具体的にどのようなアルゴリズムでマージをするのでしょうか? 厳密には 3-way merge と recursive 3-way merge というものがあるようですが、ここでは Git が内部で使っているものの詳細を教えて頂きたいです。
ここでの「way」とは、マージする際に "見て" いる場所のこと。3-way merge は 3 つの場所を見ている。
ここでは Git のデフォルト・マージ戦略である「recursive」にしたがった 3-way merge のアルゴリズムを書きます。簡単のために省略して書いています。
入力: コミットグラフ。マージの起点としたいコミット X
。X
にマージしたいコミット Y
。
出力: マージできるかどうか。マージできるなら、マージ済みコミット Z
を含む新しいコミットグラフ。マージできないなら、コンフリクト箇所。
手順
X
と Y
の共通祖先となるコミット B
(base) を見つける。このとき、X
と Y
に最も近い共通祖先を見つける。そのような祖先が一意に定まらない場合があるが、後述するように上手く処理される。X
と B
の diff、Y
と B
の diff をそれぞれ求める。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.
recursive
からort
に変わりました github.blog/2021-11-15-highlights-from-git-2-34/…