Remembering renames

リベースとチェリーピックには一連のマージが含まれ、その結果は新しいひとり親コミット(single-parent commits)として記録されます。 これらのマージの1番目の親の側は「上流」(upstream)側を表し、多くの場合、2 番目の親の側よりもはるかに大きな変更セットが含まれます。 従来、一連のマージの最初の親側の名前変更は、マージごとに繰り返し再検出されていました。 このファイルは、すべてのマージが自動でクリーン(つまり、競合がなく、ユーザー入力または編集のために中断(interrupt)されない)であると仮定して、最適化として、履歴の上流側で名前変更を記憶することが、リベースおよびチェリーピック中に安全かつ効果的である理由を説明します。

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

3つ目の仮定は、セクション 2 〜 5 が対象で、議論をシンプルにするための仮定です。これについては セクション 8 で説明します:

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

最初の仮定は、この文書の目的をより明確にするためのものです。 最適化の実装は実際、これには依存しません。 ただし、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)すると直ちに破棄されます。

3番目の仮定により、セクション 2〜5 がより単純になり、この最適化が安全で効果的である理由の基礎を人々が理解できるようになります。その後、セクション 8 で詳細に取り組むことができます。 ディレクトリの名前変更が発生したときに、merge.directoryRenames のデフォルトが conflict に設定されていることは、ユーザーが競合を解決するために操作が停止(stop)し、キャッシュが破棄されることを意味することにも注意してください。つまり、最適化は適用されません。 したがって、ディレクトリの名前変更に具体的に対処する必要がある唯一の理由は、一部のユーザーが merge.directoryRenames を true に設定して、マージが自動的に続行できるようにするためです。 この構成設定でも最適化は安全ですが、その理由を示すためにさらにいくつかのケースについて説明する必要があります。 この議論についてはセクション 8 にて行います。

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

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

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

To create A':

To create B':

To create C':

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

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

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

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

To create A':

To create B':

そして、特に、 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 つのピックをもう一度見てみましょう:

To create A':

To create B':

次に、最初のピックでの 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 もほとんど常に名前変更として検出できるはずです。

セクション 3 で、rename/rename(1to1) (つまり、両サイドが同一の方法でファイルの名前を変更すること) が 1 つの反例であることを既に述べました。 しかし、もっと興味深いのは、なぜ A:oldfile と A':newfile が名前変更として「ほぼ」常に検出可能であると述べたときに、「ほぼ」という言葉を使用する必要があったのかということです。

セクション 3 で述べた以前のポイントを繰り返しましょう:

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

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

そうすると:

E:oldfile → G:newfile は名前変更として検出されますが、 A:oldfile と A':newfile は検出されません。

rename/rename(1to1) の場合、 A:newfile と A':newfile は 「同一」ファイル名を使用するため、名前変更しません。 ただし、同一ファイル名のファイルは、3方向コンテンツマージ用の組にする(pair up)のに明らかに問題ありません(マージ機構は破壊検出(break detection)を採用していないため)。 したがって、この興味深い反例のケースは、rename/rename(1to1) ケースではなく、A が oldfile の名前変更しなかったケースです。 これは、セクション 3 と 4 でほとんどの時間を議論に費やしたケースです。 このセクションの残りの部分では、そのケースについても説明します。

では、 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 に格納されます

(A) の理由は、セクション 6 で説明した最適化をスキップする無関係な名前変更に由来します。 無関係な名前変更がスキップされるという事実は、検出された可能性のある名前変更のサブセットのみを取得することを意味し、後続のコミットでは、残りの名前変更のサブセットに対してアップストリーム側で名前変更検出を実行する必要がある場合があります(その後のコミットに関連する名前変更を取得するため)。 対になっていない削除は名前変更の検出にも関与するため、移植(transplant)するすべてのコミットでそれらのパスがアップストリーム側で対になっていないままであることを繰り返し確認したくありません。

(B) の理由は、diffcore_rename_extended() が、ディレクトリの名前変更の検出に必要なディレクトリごとの名前変更の数を生成するものであり、 diffcore_rename_extended() を再度実行しない場合は、以前の実行での dir_rename_counts を含む出力が必要です。

© の理由は、merge-ort のツリー トラバーサルがこれらのパスが関連性があると再び判断する(RELEVANT_LOCATION としてマークする)ためですが、それらが RELEVANT_NO_MORE にダウングレードされたという事実は、ディレクトリの名前変更の検出に必要な情報が dir_rename_counts に既に含まれていることを意味します。 (後続のコミットで RELEVANT_CONTENT になるパスは、cached_irrelevant から削除されます。)

(D) の理由は、名前変更の記憶の最適化を使用できるかどうかをどのように判断するかです。 特に、一連のマージが以下のようになっていることを思い出してください:

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

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

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

最初のピックは、以下 3 方向のマージを行います

2 番目のピックは、以下の 3 方向マージを行います

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

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

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

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

このケースは以下のようになります:

最適化されるこの場合、最初のコミット後に以下の点に注意してください:

上記のキャッシュされた名前変更を考えると、2番目のマージは、 A → A' からの名前変更検出を実行する必要なく、期待どおりに続行できます。

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

このケースは以下のようになります:

最適化されるこの場合、最初のコミット後に以下の点に注意してください:

上記のキャッシュされた名前変更を考えると、2番目のマージは、 A → A' からの名前変更検出を実行する必要なく、期待どおりに続行できます。

ケース 3: MERGE_SIDE1は新しいファイルを「古いディレクトリ」に追加し、MERGE_SIDE2は「古いディレクトリ」を名前変更します

このケースは以下のようになります:

この場合、最適化により、最初のコミット後に MERGE_SIDE1 の名前変更がなく、MERGE_SIDE2 の名前変更が破棄されることに注意してください。 しかし、2 回目のマージでは名前変更する必要がなかったので、これで問題ありません。

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

このケースは以下のようになります:

最適化されるこの場合、最初のコミット後に以下の点に注意してください:

上記のキャッシュされた名前変更を考えると、2番目のマージは、 A → A' からの名前変更検出を実行する必要なく、期待どおりに続行できます。

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