[解決済み] recursive'戦略によるマージ

質問

git merge recursiveは、共通の先祖が1つ以上ある場合に発生し、これらの共通の先祖をマージするために仮想コミットを作成してから、より新しいコミットをマージすると理解しました（すみません、この用語があるかどうか分かりませんが）。

しかし、git merge recursive strategy が実際にどのように機能するのか、詳細な情報を探したのですが、あまり多くの情報は見つかりませんでした。

どなたか、git merge recursive が実際にどのように実行されるのか、例や、場合によっては可視化を助けるためのフローマップを交えて詳しく説明していただけませんか？

どのように解決するのですか？

を見つけることができます。 説明文はこちら (参照 パート2 ):

merge recursiveはどのような場合に必要ですか？

(Git 2.30、2020年第1四半期には 新しい マージ・オートの戦略 )

もし、共通の祖先が2つ見つかったらどうしますか？下のブランチエクスプローラービューは、2つの共通の祖先が存在する可能性があることを示しています。

開発者がチェンジセット15 (マージの時点でメインブランチの最新) からマージする代わりに、チェンジセット11から16にマージする正当な理由が - 最初は - ないため、この例は少々強引です。
しかし、例えば、チェンジセット11が安定していて、13と15がそうでないなど、何らかの理由でそうしなければならないとしましょう。

<ブロッククオート

要は、15と16の間には、一意な先祖がいるわけではなく、同じ"距離"にある先祖が2つあるということです。12と11です。

これは頻繁に起こることではありませんが、長寿命の枝や複雑な枝のトポロジーで本当に起こりやすいことです。(上に描いたケースは、quot;multiple ancestor"問題につながる最も短いものですが、いくつかのチェンジセットやブランチがquot;crossed"マージされる間にも起こり得ます).

解決策のひとつは、マージに有効な先祖のひとつを "select" することです (Mercurial が採用しているオプションです) が、これには多くの欠点があります。

<ブロッククオート

再帰的マージはどのように機能するのですか？

<ブロッククオート

複数の有効な祖先が見つかった場合、再帰的マージ戦略は最初に見つかったものをマージして新しい一意の"仮想祖先"を作成します。

次の画像は、そのアルゴリズムを表したものです。

新しい祖先2は、"src" と "dst" をマージするための "ancestor" として使用されます。

以下に説明するように、quot;merge recursive strategy"は、単に2つのうち1つを選択するよりも良い解決策を見出すことができます。

---

注：マージ再帰戦略は、当初はマージ "fredrik"戦略であった( コミット e4cf17c , Sept. 2005, Git v0.99.7a)の後に フレドリック・クイビネン .
であった。 pythonスクリプト で開始されます。 コミット 720d150 これは、オリジナルのアルゴリズムを示しています。

詳しくは、"をご検討ください。 バージョン管理システムにおける最新のコンセプト from Petr Baudiˇs 2009-09-11 の17ページです。

|B| = 1 : b(B) = B0
|B| = 2 : b(B) = M(LCA(B0, B1), B0, B1)
M(B, x, y) = ∆−1
(b(B), x ∪ y)
m(x, y) = M(LCA(x, y), x, y)

(そう、私はこれをどう読めばいいのか、どちらもわからないのです)

<ブロッククオート

競合が発生した場合、その結果をさらにマージのベースとして使用する際に、競合マーカーをそのままにしておくだけでよいというのが、このアルゴリズムの主な考え方です。
つまり、以前のコンフリクトは、新しいリビジョンでのコンフリクトと同様に適切に伝搬されるのです。

これは、以下のことを指しています。 revctrl.org/CrissCrossMerge での再帰的マージのコンテクストを記述しています。 クリスクロスマージ .

クリスクロスマージとは、最小の共通祖先が一意でない祖先のグラフのことです。
スカラーを使った最も単純な例は次のようなものだ。

  a
 / \
b1  c1
|\ /|
| X |
|/ \|
b2  c2

ここで言えることは、BobとClaireが別々にある変更を行い、それぞれがその変更をマージしたということです。
二人は対立し、ボブは（もちろん）自分の変更の方が良いと判断し、クレアは（典型的な）自分のバージョンを選びました。
さて、再びマージを行う必要があります。これはコンフリクトになるはずです。

これはテキストのマージでも同じように起こります。ファイルの同じ場所をそれぞれ編集し、競合を解決するときに、それぞれが結果のテキストを元のバージョンと同じにすることを選択します（つまり、2つの編集を何らかの方法で一緒にするのではなく、どちらかを選んで勝つのです）。

だから

もう一つの可能な解決策は、最初に' b1 と' c1 ' を一時的なノードに変換します（基本的には、' X をマージするためのベースとして使用します。 b2 と' c2 '.

面白いのは、' b1 と' c1 の結果はコンフリクトになります。この場合、トリックは、' X は、内部で記録されたコンフリクトと一緒に含まれます（たとえば、古典的なコンフリクトマーカーを使用します）。

というのは、どちらも' b2 と' c2 は同じコンフリクトを解決しなければなりませんでしたが、同じ方法で解決した場合、どちらもコンフリクトを' X のコンフリクトが発生し、きれいなマージが行われます。 X は最終的なマージ結果に伝搬されます。

ということです。 トーレック に記述されています。 "git merge: BASEファイルでコンフリクトが発生したのはなぜですか？ を、"Asymmetric result"と呼びます。

<ブロッククオート

これらの非対称な結果は、時限爆弾そのものと、後で再帰的なマージを実行したことを除けば、無害でした。
葛藤を知ることができる。それを解決するのはあなた次第です--。 また - しかし、今回は簡単に「私たち」「彼ら」というトリックがあるわけではありません。 C と D ."

から再開します。 revctrl.org/CrissCrossMerge :

マージで2塩基以上になる場合（' b1 ', ' c1 , ' d1 ') の場合、それらは連続的にマージされます - 最初に ' b1 で、' c1 ' を使って、その結果を ' d1 '.

これが、"Git" の "recursive merge" 戦略が行うことです。

---

Git 2.29（2020年第4四半期）で、新しいマージ戦略のバックエンドの準備のために、競合の良い説明と、その役割を提供していますか。 再帰的 マージ戦略

(繰り返しになりますが、2020年第1四半期のGit 2.30には 新しい マージ・オートの戦略 )

参照 コミット 1f3c9ba , コミット e8eb99d , コミット 2a7c16c , コミット 1cb5887 , コミット 6c74948 , コミットa1d8b01 , コミット a0601b2 , コミット 3df4e3b , コミット 3b6eb15 , コミットbc29dff , コミット 919df31 (2020年8月10日)による イライジャ・ニューレン( newren ) .
^{(によって統合されました。 ジュニオ・C・ハマノ--。 gitster -- で コミット36d225c , 2020年8月19日)}

<ブロッククオート

t6425 : 名前変更/削除のコンフリクトメッセージをより柔軟に扱えるようになりました。

^{署名: Elijah Newren}

<ブロッククオート

まず最初に 基本的な衝突の種類はmodify/deleteと呼ばれ、コンテンツの衝突である。 .
一方がファイルを削除し、他方がファイルを変更した場合に発生します。

もあります。 リネーム/デリートとして知られるパスの競合 .
これは、一方がパスを削除し、他方がそのパスをリネームした場合に発生します。
これはコンテンツの競合ではなく、パスの競合です。
しかし、これはコンテンツの競合、すなわち変更/削除と組み合わせて発生することが多いでしょう。
そのため、この2つが組み合わされることが多かった。

もう一つ存在しうる対立のタイプは ディレクトリとファイルの競合 . 例えば、一方があるパスに新しいファイルを追加し、もう一方の履歴が同じパスにディレクトリを追加した場合です。
追加されたパスは、リネームによってそこに置かれた可能性もありますが。
このように、1つのパスが、変更/削除、名前変更/削除、ディレクトリ/ファイルの競合の影響を受ける可能性があるのです。

これはmerge-recursiveの設計上、自然な副産物であったという面もあります。
作業木の内容を考慮しなければならない4通りのマージを行うため、作業木の処理がコードのあちこちに散らばっていたのです。
また、ディレクトリやファイルのコンフリクトの処理も、他のすべてのコンフリクトの種類を通じて、あらゆるところに分散していました。

このような構造から自然に生まれたのが、現在のコードパスが考慮しているすべての異なるタイプを組み合わせたコンフリクトメッセージです。

しかし、異なるコンフリクトタイプを直交させ、同じことを繰り返して非常にもろいコードになるのを避けたいのであれば、これらの異なるコンフリクトタイプからのメッセージを分離する必要があります。
その上、可能な順列をすべて決定しようとするのは ロイヤル を混乱させる。
rename/delete/directory/fileの競合出力を処理するコードは、すでに解析が難しく、ややもろいです。
しかし、もし本当にその路線で行くのであれば、次のような種類の組み合わせに対して特別な処理をしなければならないでしょう。

• 名前変更/追加/削除 : 与えられたファイルをリネームしなかった履歴の側で、代わりにそのファイルを削除し、リネームの邪魔になる無関係なファイルを配置します。
• リネーム/リネーム(2to1)/モードコンフリクト/削除/delete : 実行可能なファイルとそうでないファイルの2つが同じ場所にリネームされた場合、それぞれが相手側がリネームしたソースファイルを削除します。
• リネーム/リネーム(1to2)/アド/アド : ファイルが履歴のそれぞれの側で異なる名前に変更され、それぞれの側が無関係なファイルを配置している
• リネーム/リネーム(1to2)/内容の衝突/ファイルの場所/(D/F)/(D/F)/ 一方は、もう一方がそのファイルをリネームしたディレクトリをリネームし、そのディレクトリの名前を変更する必要があります。

この狂気の道から離れ、コンフリクトメッセージをそれぞれのタイプに分割できるようにすることで、異なるタイプのコンフリクトを、繰り返しのない別々のコードで扱えるようにしましょう。(複数のコンフリクトタイプが1つのパスに影響する場合、コンフリクトメッセージを順次出力することができます)。 このパスを単純な変更から始めます。このテストをより柔軟に変更し、マージバックエンド（recursiveまたは新しいort）が生成する出力を受け入れるようにします。

---

Git 2.22 (Q2 2019) では、再帰的マージ戦略が改善される予定です。 同じディレクトリにある他のファイルがどのように移動したかに基づいて、ファイルの移動を推論します。 が移動しました。

このヒューリスティックは、ファイル自体の内容の類似性に基づくもの（隣接するファイルが何をしているかに基づくのではなく）よりも本質的にロバストではないので、エンドユーザーが予期しない結果を出すことがあります。 このため、名前を変更したパスは、インデックス内のより高い/競合するステージに残すように調整されました。 その結果をユーザーが検証・確認できるようにしました。

参照 コミット 8c8e5bd , コミット e62d112 , コミット 6d169fd , コミット e0612a1 , コミット 8daec1d , コミット e2d563d , コミット c336ab8 , コミット 3f9c92e , コミット e9cd1b5 , コミット 967d6be , コミット 043622b , コミット 93a02c5 , コミット e3de888 , コミット 259ccb6 , コミット 5ec1e72 (2019/04/05)によるものです。 イライジャ・ニューレン( newren ) .
^{(によって統合されました。 ジュニオ・C・ハマノ--。 gitster -- で コミット 96379f0 , 2019年05月08日)}

<ブロッククオート

merge-recursive ディレクトリ名の変更検出のデフォルトを変更します。

<ブロッククオート

のすべてが x/a , x/b および x/c に移行しています。 z/a , z/b および z/c ある のブランチでは x/d のままであるべきで、別のブランチに追加された x/d に表示されるか z/d を使用すると、2つのブランチがマージされます。
ここでは、さまざまな視点が考えられます。

A) ファイルは x/d に配置されたもので、他のファイルと関係なく x/ のすべてのファイルが、このような方法で作成されたとしても、問題ではありません。 x/ に移動しました。 z/ を1つのブランチに追加しました。 x/d にはまだ残っているはずです。 x/d .

B) x/d は、他のファイルに関連して x/ であり、かつ x/ にリネームされました。 z/ したがって x/d に移動させる必要があります。 z/d .

以前は、ディレクトリのリネームを検出する機能がなかったため Git 2.18 では、ユーザーは (A) コンテキストに関係なく
選択肢 (B) はGit 2.18で実装されました。 (A) 以来、現在に至るまで使用されています。
しかし、あるユーザーから、マージ結果が期待したものと一致しないとの報告があり、特にディレクトリのリネーム検出でファイルが移動したときに通知が出力されないため、デフォルトの変更に問題がありました。

なお、ここで3つ目の可能性もあります。

C) Gitでは判断できない文脈や内容によって異なる答えがあるので、これは矛盾しています。
インデックスの上位ステージを使用して競合を記録し、ユーザーに黙って解決策を選択させるのではなく、潜在的な問題を通知します。

を使用するかどうかをユーザーが指定できるオプションを追加しました。 ディレクトリのリネーム検出を行い、デフォルトは (C) .
ディレクトリ名変更検出がオンの場合でも、新しいディレクトリに移動したファイルについての通知メッセージを追加する。

---

Git 2.31 (2021 年第 1 四半期) では、"ORT" マージ戦略 (これは私が ここで紹介した ) は、レガシーな再帰的戦略に影響を与えます。

参照 コミットc5a6f65 , コミット e2e9dc0 , コミット 04af187 , コミット 43c1dcc , コミット 1c7873c , コミット 101bc5b , コミット6784574 (2020年12月3日)による イライジャ・ニューレン( newren ) .
^{(によって統合されました。 ジュニオ・C・ハマノ--。 gitster -- で コミット 85cf82f 2021年1月6日)}

<ブロッククオート

merge-ort : 修正/削除処理と遅延出力処理の追加

^{サインオフバイ：Elijah Newren}

<ブロッククオート

ここでの焦点は path_msg() これは、マージに関する警告/衝突/通知メッセージをキューに入れ、後で処理するために、これらを pathname -> strbuf マップを作成します。
大きな変化のように見えるかもしれませんが、本当にそれだけなのです。

• 必要なマップの宣言とコメント
• データの初期化および記録
• print/free時にマップを反復処理するためのコード群
• 未使用の関数があるというエラーを回避するために、少なくとも一つの呼び出し元が必要です (これは、modify/delete conflict handling の実装という形で提供されます)。

この段階では、なぜ私が遅延出力処理を選択するのか、おそらく明確ではないでしょう。
理由は複数あります。

1. マージはダーティな変更を上書きする場合、中断することになっています。 を作業ツリーに追加しました。
   リネームが検出され、リネームを含むエントリーの完全な処理が終了するまで、変更が上書きされるかどうかを正しく判断することはできません。
   警告/競合/通知のメッセージは、途中のコードパスで表示されます。したがって、マージが中止されるときに偽の競合/警告メッセージを表示したくない場合は、これらのメッセージを保存して、関連するときだけ表示する必要があります。

2. 1つのパスに対して複数のメッセージが存在することがあり、衝突/警告のタイプごとにグループ化するのではなく、与えられたパスのメッセージをすべて一緒に表示させたいと思います。
   この問題は、すでに merge-recursive.c のコミットメッセージで説明したように、コンフリクトタイプが分割されたことにより、さらに重要になりました。 1f3c9ba707 (" t6425 : 名前変更/削除の衝突メッセージをより柔軟にする", 2020-08-10, Git 2.29.）

3. 呼び出し元によっては、最終結果がクリーンなマージである場合など、特定のケースで出力を表示しないようにしたい場合があります。
   リベースは通常、このようにしてきました。

4. 呼び出し元の中には、出力を標準出力や標準エラー出力に出したくない人もいるかもしれませんが、その出力を使って完全に別のことをしたい人もいるでしょう。
   例えば --remerge-diff オプションから git show または git log -p のような、その場でリマージしてリマージしたバージョンに対して diff をとるようなコミットでは、標準の形式で stdout/stderr に書き込まないほうが有利になります。