「git merge」の背後にある正確な (またはそれに近い) アルゴリズムを知りたいです。少なくとも次のサブ質問への回答が役立ちます。
しかし、アルゴリズム全体の記述ははるかに優れています。
3 方向マージ アルゴリズムの説明を探すのが最善の方法かもしれません。高レベルの説明は次のようになります。
B- 新しいバージョン (XとY) の両方の祖先であるファイルのバージョン、および通常はそのような最新のベースを見つけます (ただし、さらに遡る必要がある場合があります。gits デフォルトのrecursiveマージの機能)XwithBとYwithの差分を実行しBます。完全なアルゴリズムはこれをより詳細に扱い、いくつかのドキュメントもあります ( https://github.com/git/git/blob/master/Documentation/technical/trivial-merge.txtとgit help XXXページ、ここで XXX はmerge-base、merge-file、merge、merge-one-fileおよびその他のいくつかのいずれかです)。それが十分に深くない場合は、常にソースコードがあります...
私も興味があります。答えはわかりませんが…
機能する複雑なシステムは、常に機能する単純なシステムから進化したことがわかっています。
git のマージは非常に洗練されており、理解するのが非常に難しいと思いますが、これにアプローチする 1 つの方法は、その前身から、懸念の核心に焦点を当てることです。つまり、共通の祖先を持たない 2 つのファイルが与えられた場合、git merge はどのようにそれらをマージする方法を見つけ、競合はどこにあるのでしょうか?
いくつかの前駆体を見つけようとしましょう。からgit help merge-file:
git merge-file is designed to be a minimal clone of RCS merge; that is,
it implements all of RCS merge's functionality which is needed by
git(1).
ウィキペディアから: http://en.wikipedia.org/wiki/Git_%28software%29 -> http://en.wikipedia.org/wiki/Three-way_merge#Three-way_merge -> http://en.wikipedia .org/wiki/Diff3 -> http://www.cis.upenn.edu/~bcpierce/papers/diff3-short.pdf
最後のリンクは、diff3アルゴリズムを詳細に説明した論文の pdf です。これはGoogle pdf-viewerバージョンです。長さはわずか 12 ページで、アルゴリズムはわずか数ページですが、完全な数学的処理です。少し堅苦しすぎるように思えるかもしれませんが、git のマージを理解したい場合は、まず単純なバージョンを理解する必要があります。まだ確認していませんが、 のような名前の場合diff3、おそらく diff (最長共通部分列アルゴリズムを使用する) も理解する必要があります。diff3ただし、 Google をお持ちの場合は、より直感的な説明があるかもしれません...
ここで、 と を比較する実験diff3を行いgit merge-fileました。彼らは同じ 3 つの入力ファイルversion1 oldversion version2を取り、競合を同じ方法でマークし<<<<<<< version1、 , =======, >>>>>>> version2(diff3また||||||| oldversion) を付けて、共通の遺産を示します。
oldversionには空のファイルを使用し、version1とversion2にはほぼ同一のファイルを使用し、 version2に 1 行だけ追加しました。
結果:git merge-file単一の変更された行が競合として識別されました。しかしdiff3、2 つのファイル全体を競合として扱いました。したがって、diff3 が洗練されているのと同様に、git のマージは、この最も単純なケースであっても、さらに洗練されています。
これが実際の結果です（テキストには@twalbergの回答を使用しました）。必要なオプションに注意してください (それぞれのマンページを参照してください)。
$ git merge-file -p fun1.txt fun0.txt fun2.txt
You might be best off looking for a description of a 3-way merge algorithm. A
high-level description would go something like this:
Find a suitable merge base B - a version of the file that is an ancestor of
both of the new versions (X and Y), and usually the most recent such base
(although there are cases where it will have to go back further, which is one
of the features of gits default recursive merge) Perform diffs of X with B and
Y with B. Walk through the change blocks identified in the two diffs. If both
sides introduce the same change in the same spot, accept either one; if one
introduces a change and the other leaves that region alone, introduce the
change in the final; if both introduce changes in a spot, but they don't match,
mark a conflict to be resolved manually.
<<<<<<< fun1.txt
=======
THIS IS A BIT DIFFERENT
>>>>>>> fun2.txt
The full algorithm deals with this in a lot more detail, and even has some
documentation (/usr/share/doc/git-doc/technical/trivial-merge.txt for one,
along with the git help XXX pages, where XXX is one of merge-base, merge-file,
merge, merge-one-file and possibly a few others). If that's not deep enough,
there's always source code...
$ diff3 -m fun1.txt fun0.txt fun2.txt
<<<<<<< fun1.txt
You might be best off looking for a description of a 3-way merge algorithm. A
high-level description would go something like this:
Find a suitable merge base B - a version of the file that is an ancestor of
both of the new versions (X and Y), and usually the most recent such base
(although there are cases where it will have to go back further, which is one
of the features of gits default recursive merge) Perform diffs of X with B and
Y with B. Walk through the change blocks identified in the two diffs. If both
sides introduce the same change in the same spot, accept either one; if one
introduces a change and the other leaves that region alone, introduce the
change in the final; if both introduce changes in a spot, but they don't match,
mark a conflict to be resolved manually.
The full algorithm deals with this in a lot more detail, and even has some
documentation (/usr/share/doc/git-doc/technical/trivial-merge.txt for one,
along with the git help XXX pages, where XXX is one of merge-base, merge-file,
merge, merge-one-file and possibly a few others). If that's not deep enough,
there's always source code...
||||||| fun0.txt
=======
You might be best off looking for a description of a 3-way merge algorithm. A
high-level description would go something like this:
Find a suitable merge base B - a version of the file that is an ancestor of
both of the new versions (X and Y), and usually the most recent such base
(although there are cases where it will have to go back further, which is one
of the features of gits default recursive merge) Perform diffs of X with B and
Y with B. Walk through the change blocks identified in the two diffs. If both
sides introduce the same change in the same spot, accept either one; if one
introduces a change and the other leaves that region alone, introduce the
change in the final; if both introduce changes in a spot, but they don't match,
mark a conflict to be resolved manually.
THIS IS A BIT DIFFERENT
The full algorithm deals with this in a lot more detail, and even has some
documentation (/usr/share/doc/git-doc/technical/trivial-merge.txt for one,
along with the git help XXX pages, where XXX is one of merge-base, merge-file,
merge, merge-one-file and possibly a few others). If that's not deep enough,
there's always source code...
>>>>>>> fun2.txt
あなたが本当にこれに興味があるなら、それはちょっとうさぎの穴です. 私には、正規表現、diff の最長共通部分列アルゴリズム、文脈自由文法、または関係代数と同じくらい深いように思えます。真相を究明したいのなら、できると思いますが、それには断固たる研究が必要です。
gitは、競合しない特定の変更のコンテキストをどのように検出しますか？
gitは、これらの正確な行に競合があることをどのようにして見つけますか？
マージの両側で同じ行が変更された場合、それは競合です。そうでない場合は、一方の側からの変更（存在する場合）が受け入れられます。
gitはどのようなものを自動マージしますか？
競合しない変更（上記を参照）
ブランチをマージするための共通のベースが複数ある場合、gitはどのように機能しますか？
Gitマージベースの定義によると、これまでに1つ（最新の共通の祖先）しかありません。
複数のブランチを一度にマージするとどうなりますか？
これはマージ戦略によって異なります（octopusおよびours/theirs戦略のみが3つ以上のブランチのマージをサポートします）。
マージ戦略の違いは何ですか？
これはgit mergeマンページで説明されています。
これが元の実装です
http://git.kaarsemaker.net/git/blob/857f26d2f41e16170e48076758d974820af685ff/git-merge-recursive.py
基本的に、2 つのコミットの共通の祖先のリストを作成し、それらを再帰的にマージします。早送りするか、ファイルの 3 方向マージの基礎として使用される仮想コミットを作成します。