1つ目と2つ目の仮定はこのドキュメント全体に渡る仮定です:

and a third that will hold in sections 3-6 for simplicity, that I’ll later address in section 9:

それぞれの仮定とそれを含める理由について、詳しく説明します:

最初の仮定は、この文書の目的をより明確にするためのものです。 最適化の実装は実際、これには依存しません。 ただし、rebase と cherry-pick の両方が実装された方法を反映しているため、この仮定はすべての場合に当てはまります。 そしてまた、 cherry-pick と rebase の実装は、下位互換性の理由により簡単には変更できません(たとえば、 git checkout のドキュメントの --ours フラグと --theirs フラグに関する議論、特に rebase での動作に関するコメントを参照してください)。 ただし、最適化により、1番目の親のチェック(checking first-parent-ness)が回避されます。 最適化を有効にする代わりの条件をチェックするため、 cherry-pick と rebase が使用する親の順序が変更された場合でも引き続き機能します。 しかし、この仮定を行うことで、このドキュメントがより明確になり、すべての例を 2 回繰り返す必要がなくなります。

2番目の仮定に違反した場合、最適化は単純にオフになるため、その後を考慮する必要はありません。 2番目の仮定は、「ユーザーが競合を解決したり、ファイルをさらに編集または微調整したりするために中断(interrupt)されることはない」とも言えます。 実際のリベースとチェリーピックはしばしば中断(interrupt)されますが(ユーザーが停止と編集を要求した対話的なリベースであるか、ユーザーが解決する必要がある競合があったため)、名前変更のキャッシュはディスクに保存されないので、ユーザーが操作を解決するためにリベースまたはチェリーピックが停止(stop)すると直ちに破棄されます。

The third assumption makes sections 3-6 simpler, and allows people to understand the basics of why this optimization is safe and effective, and then I can go back and address the specifics in section 9. It is probably also worth noting that if directory renames do occur, then the default of merge.directoryRenames being set to "conflict" means that the operation will stop for users to resolve the conflicts and the cache will be thrown away, and thus that there won’t be an optimization to apply. So, the only reason we need to address directory renames specifically, is that some users will have set merge.directoryRenames to "true" to allow the merges to continue to proceed automatically. The optimization is still safe with this config setting, but we have to discuss a few more cases to show why; this discussion is deferred until section 9.

以下の図について考えてみましょう(git-rebase マニュアルページより):

topic を main にリベースまたはチェリーピッキングした後、以下のようになります:

コミット A' と B' と C' がどのように作成されるかというと、一連のマージによって行われます。この場合、リベースまたはチェリーピックは、特殊なマージ操作にて 3 つの A-B-C コミットのそれぞれを順番に使用します。 ここで、マージ操作の 3 つのコミットに、 MERGE_BASE と、MERGE_SIDE1 と MERGE_SIDE2 というラベルを付けることにしましょう。 この図では、その 3 つのマージのそれぞれに対する 3 つのコミットは以下のようになります:

ときどき、これらの 3 方向のマージが行われることに驚かれることがあります。 これらの 3 方向のマージを理解するには、これらを少し異なる観点から見ることが役に立ちます。 たとえば、 C' の作成は、以下のいずれかとして観る事ができます:

概念的には、上記の 2 つの文は、少なくともあなたがコミットの記録を決定する前の時点では、B と B' と C の 3 方向マージと同一です。

マージ機構は、MERGE_BASE と MERGE_SIDE1 と MERGE_SIDE2 から供給されるファイル名を使用します。 以下の 3 つの条件のいずれかでのみ、コンテンツを別のファイル名に移動(move)します:

まず、cherry-pick または rebase シーケンスの 1 番目と 2 番目のピックに含まれるコミットを思い出してください:

そして、特に、 E と G の間の名前変更は、 A と A' の間の名前変更のスーパーセットであることを示す必要があります。

A' は最初のマージで作成されます。 A' は、上記 3 つの理由のいずれかのみで名前変更されます。 最初のケースである競合では、キャッシュが削除され、この最適化が有効にならない状況が発生するため、このケースを考慮する必要はありません。 3 番目のケースである MERGE_SIDE2 の名前変更 (つまり、G から A へ) は、A' に表れますが、A にも表れます — したがって、 A と A' を比較すると、そのパスは名前変更として表示されません。 名前の変更が A' に表れる唯一の方法は、MERGE_SIDE1 による名前変更です。 それゆえ、A と A' の間のすべての名前変更は、E と G の間の名前変更のサブセットです。 同様に、E と G の間のすべての名前変更は、A と A' の間の名前変更のスーパーセットです。

最初の 2 つのピックをもう一度見てみましょう:

次に、最初のピックでの MERGE_SIDE1 からの任意の名前変更、つまり E から G への任意の名前変更を見てみましょう。デモンストレーションのために、ファイル名「oldfile」と「newfile」を使用してみることにします。 その最初のピックは次のように機能します。 つまり、名前の変更が検出されると、マージ機構は以下の 3 方向のコンテンツ マージを実行します:

そして新しい結果を生成します:

上記で、E→A が oldfile の名前変更しなかったと仮定したことに注意してください。 そのMERGE_SIDEが名前を変更した場合は、名前変更/名前変更(1to2) の競合が発生している可能性が高く、リベースまたはチェリーピック操作が停止(halt)し、名前変更のメモリ内キャッシュが削除(drop)されるため、これ以降を考慮する必要はありません。 E→A がファイルの名前を変更するだけでなく、 newfile に名前を変更するという特別なケースでは、名前変更による競合はなく、マージは成功します。 この特殊なケースでは、2 回目のマージで MERGE_BASE 内の A:newfile が検出されるため、名前変更はキャッシュに有効ではありません (t6429 の新しいテストケースの「rename same file identically」(同一ファイルを全く同じに名前変更する)という説明も参照してください)。 したがって、 rename/rename(1to1) は、キャッシュから名前変更を刈り込み、それらの名前変更に関連付けられた現在および主要なディレクトリの dir_rename_counts を減らすことによって、特別に処理する必要があります。 または、これらは非常にまれであるため、名前の変更/名前の変更(1to1)が発生したときに名前の記憶の最適化を無効にして、簡単な方法を取ることができます。

さて、前の段落では、 E→A で oldfile の名前を変更する特殊なケースについて説明しましたけれども、引き続き A で oldfile の名前が変更されていないと仮定して議論を続行すします。

B' を作成するための図によると、 MERGE_SIDE1 には A から A' への変更が含まれます。 そのため私達は A:oldfile と A':newfile が名前変更として表れるかどうかに興味があるのです。 以下ご留意下さい:

上記の 3 番目のポイントについても説明できます。3 方向のコンテンツのマージは、ベースと一方の側の違いを他方の側に適用することと見なすこともできます。 したがって、 E:oldfile と G:newfile の間の変更(関連していると検出されたもの、つまり 50% 未満の変更)を A:oldfile に適用することによって、 A':newfile が作成されたと見なすことができます。

したがって、 A:oldfile と A':newfile は、 E:oldfile と G:newfile が関連しているのと同じように関連しています — これらはまったく同一の違いがあります。 後者は名前変更として検出されたので、 A:oldfile と A':newfile もほとんど常に名前変更として検出できるはずです。

We already noted in section 4 that rename/rename(1to1) (i.e. both sides renaming a file the same way) was one counter-example. The more interesting bit, though, is why did we need to use the "almost" qualifier when stating that A:oldfile and A':newfile are "almost" always detectable as renames?

Let’s repeat an earlier point that section 4 made:

E:oldfile のサイズの 50% 未満であった変更が、 A:oldfile のサイズの 50% 未満であるならば、 A:oldfile と A':newfile では名前変更として検出されます。 ただし、 E:oldfile と A:oldfile の間で劇的なサイズの縮小がある場合 (ただし、E:oldfile、G:newfile、および A:oldfile の間の変更は依然として何らかの形できれいにマージされるとして)、従来の名前変更検出では A:oldfile と A':newfile の間の名前変更が検出されません。

これが発生する可能性のある例を以下に示します:

then

In the rename/rename(1to1) case, A:newfile and A':newfile are not renames since they use the same filename. However, files with the same filename are obviously fine to pair up for three-way content merging (the merge machinery has never employed break detection). The interesting counter-example case is thus not the rename/rename(1to1) case, but the case where A did not rename oldfile. That was the case that we spent most of the time discussing in sections 4 and 5. The remainder of this section will be devoted to that case as well.

では、 A:oldfile と A':newfile が名前変更として検出されない場合でも、マージ機構で3方向のコンテンツをマージするためにそれらを組(pair)にすることが合理的なのはなぜでしょうか? これには複数の理由があります:

ただし、上記では一般的なシナリオに焦点を当てています。 考えうる異常なシナリオをすべて見て、最適化なしと最適化ありを比較してみましょう。 以下の理論的なケースを検討してみてください。 そして、私達は以下のそれぞれについて掘り下げて、可能なものと、可能な場合の意味を判断します:

私は 4 つのケースすべてを検討しますが、順不同です。

4番目のケースは不可能です。 名前変更の記憶の最適化を行わないコードで競合が発生しないようにするには、 B:oldfile が A:oldfile と正確に一致する必要があります — 一致しない場合は、変更/削除 の競合が発生します。 A:oldfile が B:oldfile と正確に一致する場合、A:oldfile と、A':newfile と B:oldfile の間の3方向のコンテンツマージは競合せず、結果として A' からの newfile のバージョンを提供します。

そして4番目のケースと同一のロジックにより、2 番目のケースは実際には同一のマージになります。 A:oldfile が B:oldfile と正確に一致する場合、検出されない名前変更はこのように言います「ええっと、一方が ‘oldfile` を変更せず、もう一方がそれを削除したようです。よってそれを削除します。 そして、 A に newfile という名前の新しいファイルがあるので、そのままにしておきます。」 これは、 A:oldfile と A’:newfile と B:oldfile の3方向のコンテンツマージと同一の結果をもたらします — A' からの newfile のバージョンを含む oldfile の削除が結果に表れます。

3番目のケースは興味深いです。 これは、A:oldfile と A':newfile が十分に類似しているだけでなく、それらの間の変更が A:oldfile と B:oldfile の間の変更と競合しなかったことを意味します。 これは、ファイルが 3 方向のコンテンツ マージで使用できるほど類似しているという私たちの推測を検証したものでして、つまり、このように使用したことは完全に正しいと思われます。 (補足: ここでの 1 つの特定の例は、啓発的かもしれません。 B が A の直接の復帰(revert)であるとしましょう。A は B の直接の親であるため、B は明らかに A の完全な復帰(revert)でした。 コミットを選択できる場合は、その即時の復帰(revert)も選択できるはずです。 ただし、これは面白いレアケース(corner cases)の 1 つです。 この最適化がなければ、コミットをきれいに選択することに成功しましたが、E:oldfile と A:oldfile のサイズが異なるため、直ちに戻す(revert)ためにそれをチェリーピック(cherry-pick)することはできません。)

考慮すべきなのは最初のケースのみです — それは最適化の有無にかかわらず競合が発生した場合です。 最適化を行わないと、 変更/削除 の競合が発生し、 A':newfile と B:oldfile の両方がツリーに残され、ユーザーが処理できるようになり、2 つの潜在的な類似性についてのヒントがなくなります。 最適化により、 A:oldfile と A':newfile と B:oldfile が 3 方向のコンテンツマージされ、ファイルが関連していると思われる競合マーカーが表示されますが、ユーザーには解決する機会が与えられます。 前述したように、「oldfile」と「newfile」は E と G の間だったので、ユーザーは「oldfile」と「newfile」を関連性があるものとして扱っていることに驚かないと思います。 いずれにせよ、どちらの場合も競合に遭遇し、ユーザーに知っていることを伝え、解決するように依頼したため、このケースは心配する必要がはありません。

つまり、要約すると、ケース 4 は不可能であり、ケース 2 は同一の振る舞いをもたらし、ケース 1 と 3 は、最適化を使用しない場合と同じか、またはより良い振る舞いをもたらすように見えます。

以前の最適化では、「無関係」(irrelevant)と見なされるパスの名前変更検出をスキップしていました。 たとえば、以下のコミットを参照してください:

関連性は常に、履歴の「相手側」(other side)が何をしたかによって決定されます。たとえば、 our side が名前を変更したファイルを変更したり、 our side が名前を変更したディレクトリにファイルを追加したりします。 これは、リベースまたはチェリーピックでシリーズの最初のコミットを選択するときに「無関係」(irrelevant)であるパスが、次のコミットを選択するときに突然「関連あり」(relevant)になる可能性があることを意味します。

この結果、関連するパスの名前変更検出結果のみをキャッシュすることができ、そしてそれゆえに、後続のコミットで関連性を再確認する必要があります。 これらの後続のコミットに、名前変更の検出に関連する追加のパスがある場合は、名前変更の検出をやり直す必要があります — ただし、名前変更がまだ検出されていないパスに限定することはできます。

私達は、名前変更だけでなく、それ以上のものをキャッシュしなければならないことがわかりました。 私達は以下もキャッシュします:

これらはすべて以下のとおり struct rename_info に格納されます

The reason for (A) comes from the irrelevant renames skipping optimization discussed in section 7. The fact that irrelevant renames are skipped means we only get a subset of the potential renames detected and subsequent commits may need to run rename detection on the upstream side on a subset of the remaining renames (to get the renames that are relevant for that later commit). Since unpaired deletes are involved in rename detection too, we don’t want to repeatedly check that those paths remain unpaired on the upstream side with every commit we are transplanting.

The reason for (B) is that diffcore_rename_extended() is what generates the counts of renames by directory which is needed in directory rename detection, and if we don’t run diffcore_rename_extended() again then we need to have the output from it, including dir_rename_counts, from the previous run.

The reason for (C) is that merge-ort’s tree traversal will again think those paths are relevant (marking them as RELEVANT_LOCATION), but the fact that they were downgraded to RELEVANT_NO_MORE means that dir_rename_counts already has the information we need for directory rename detection. (A path which becomes RELEVANT_CONTENT in a subsequent commit will be removed from cached_irrelevant.)

The reason for (D) is that is how we determine whether the remember renames optimization can be used. In particular, remembering that our sequence of merges looks like:

この最適化を可能にするのは、ツリー A と A' が Merge 1 と Merge 2 の両方に表示され、A が A' の親であるという事実です。 そのため、次にマージするように求められたものと比較するために、ツリーを保存します。

仮定セクションで述べたように:

特定のピックが次のピックにどのように影響するかを調べる必要があることを思い出してください。 それでは、セクション 1 の図の最初の 2 つのピックをもう一度見てみましょう:

現在、ディレクトリの名前変更検出が存在するため、履歴の一方がディレクトリを名前変更し、もう一方が古いディレクトリに新しいファイルを追加した場合、マージ(merge.directoryRenames=true を使用)によってファイルを新しいディレクトリに移動できます。 古いディレクトリに新しいファイルを追加するには、質的に異なる 2 つの方法があります。 新しいファイルを作成するか、ファイル名を名前変更してそのディレクトリにします。 また、ディレクトリの名前変更は履歴のどちらの側でも実行できるため、考慮すべき 4 つのケースがあります:

これら 4 つのケースを検討する前に、最後に 1 つ注意してください。ディレクトリの名前変更の検出に関して、この最適化をどのように実装するかについて、これらすべてのケースを検討する際に留意する必要があるいくつかの重要な性質があります:

さて、これらの注意事項を整理して、4 つのケースを順番に見ていきます:

ケース 1: MERGE_SIDE1 は old dir の名前変更し、 MERGE_SIDE2 は old dir に新しいファイルを追加します

Case 2: MERGE_SIDE1 は old dir を名前変更し、 MERGE_SIDE2 はファイルの名前を old dir に名前変更します

Case 3: MERGE_SIDE1 adds new file to old dir, MERGE_SIDE2 renames old dir

ケース 4: MERGE_SIDE1 はファイルの名前を old dir に名前変更し、MERGE_SIDE2 は old dir を名前変更します

最後に、 skip-irrelevant-renames 最適化との相互作用により、名前変更されたディレクトリ内のすべてのファイルの名前変更検出しない場合があることをここで指摘しておきます。 このような場合、ディレクトリが名前変更されたかどうかはわかりません。 ある種の「このディレクトリは名前変更されていません」ステートメントをキャッシュしないように注意する必要があります。 もしそうなら、リベースされている後続のコミットはファイルを古いディレクトリに追加する可能性があり、ユーザーはそれが正しいディレクトリにあることを期待するでしょう — つまり「このディレクトリは名前変更されていません」という誤ったキャッシュが除外されます。