マージ（バージョン管理）

非構造化マージは、通常、テキストの行を最小単位として、生のテキストに対して動作します。これは、Unixツール（diff/patch）やCVSツール（SVN、Git）で使用されている方式です。ただし、テキストの行はソースコードの構造を表していないため、この方式には限界があります。

構造化マージツール、またはASTマージは、ソースコードを完全に解決されたASTに変換します。これにより、不要な競合を回避するきめ細かなマージが可能になります。

3 方向マージは、ファイル「A」とファイル「B」の自動差分分析の後に、両方のファイル「C」の起源、つまり共通の祖先も考慮して実行されます。これは大まかなマージ方法ですが、マージする変更を再構築するために共通の祖先が 1 つだけ必要であるため、広く適用できます。3 方向マージは、生のテキスト (行のシーケンス) または構造化されたツリーに対して実行できます。^{[ 2 ]}

3方向マージでは、3つのファイルのうち2つのファイルでのみ同じであるセクションを探します。この場合、セクションには2つのバージョンがあり、共通の祖先「C」にあるバージョンは破棄され、異なるバージョンが出力に保持されます。「A」と「B」が一致する場合は、それが出力に表示されます。「A」と「C」で同じセクションは「B」の変更されたバージョンを出力し、同様に「B」と「C」で同じセクションは「A」のバージョンを出力します。

3つのファイルすべてで異なる箇所は、競合状態としてマークされ、ユーザーが解決する必要があります。

3方向マージは、広く普及しているdiff3プログラムによって実装されており、ファイルロックベースのバージョン管理システムからマージベースのバージョン管理システムへの移行を可能にした中心的なイノベーションでした。これは、コンカレントバージョンシステム（CVS）で広く使用されています。

3方向マージに基づくバージョン管理ツールは広く普及しているが、その手法は基本的に、マージするバージョンの共通の祖先を見つけることに依存している。

特に「クロスマージ」^{[ 3 ]}では、修正されたバージョンの唯一の最後の共通祖先が存在しないという厄介なケースがあります。

幸いなことに、この場合、候補となる祖先は最大で2つしか存在しないことが示されており、再帰的な3方向マージによって、まず一意でない祖先をマージすることで仮想的な祖先が構築されます。このマージ自体にも同じ問題が発生する可能性があるため、アルゴリズムはそれらを再帰的にマージします。履歴には有限数のバージョンしか存在しないため、このプロセスは最終的に必ず終了します。この手法は、Gitリビジョン管理ツールで使用されています。

Gitの再帰的マージの実装は、あるバージョンでファイルが変更され、別のバージョンで名前が変更されるといった、その他の扱いにくいケースにも対応していますが、これらは3方向マージの実装の拡張機能であり、マージする3つのバージョンを見つけるための手法の一部ではありません。

再帰的な3方向マージは、ツールがマージ対象の派生要素の完全な祖先指向非巡回グラフ（DAG）に関する情報を持っている場合にのみ使用できます。したがって、派生要素またはマージ要素が親要素を完全に指定していない状況では使用できません。

パッチとは、ファイルへの変更内容を記述したファイルのことです。Unixの世界では、テキストファイルへの変更を「diff -u」コマンドで生成される形式のパッチとして配布するのが慣例となっています。この形式は、パッチプログラムによって、テキストファイル、またはテキストファイルを含むディレクトリ構造への変更の再適用（または削除）に使用できます。

しかし、パッチプログラムには、パッチの作成に使用された元のファイルと完全に一致しないファイルにパッチを適用する機能も備わっています。このプロセスはファジーパッチ適用と呼ばれ、一種の非対称な3方向マージとなります。つまり、パッチプログラムがパッチを適用する場所を見つけられない場合、パッチの変更は破棄されます。

CVSがdiff3のスクリプト群として始まったように、GNU archもpatchのスクリプト群として始まりました。しかし、あいまいパッチ適用は比較的信頼性の低い方法であり、コンテキストが少なすぎるパッチ（特に新しいファイルを作成するパッチ）を誤って適用したり、両方の派生版で行われている削除の適用を拒否したりすることがあります。

Darcsでは、変更をマージするためにパッチ変換が用いられ、Gitにも同様の機能が実装されています（ただし、Gitでは「リベース」と呼ばれています）。パッチ変換マージとは、パッチ（つまり変更内容）の順序を変更して、直線的な履歴を形成することです。実際には、2つのパッチが共通の状況下で作成された場合、マージ時に一方のパッチが書き換えられ、他方のパッチのコンテキスト下で行われたかのように表示されます。

パッチ変換では、派生ファイルに影響を与えた正確な変更内容が保存されているか、または再構築できる必要があります。これらの正確な変更内容から、一方のファイルを他方のファイルに基づいてリベースするために、どのように変更すればよいかを計算できます。たとえば、パッチ A がファイル F の 7 行目の後に「X」行目を追加し、パッチ B がファイル F の 310 行目の後に「Y」行目を追加する場合、パッチ B を A に基づいてリベースするには、パッチ B を書き直す必要があります。つまり、A で追加された行によって行番号が 1 つずれるため、ファイル F の 311 行目に「Y」行目を追加する必要があります。

パッチ交換は形式的にかなり研究されてきましたが、パッチ交換におけるマージ競合に対処するアルゴリズムは依然として未解決の研究課題です。しかし、パッチ交換は「正しい」マージ結果を生成することが証明されています^{[ 4 ]。}他のマージ戦略は、ユーザーが見たいと思うものを生成しようとするヒューリスティックがほとんどです。

flipdiff「patchutils」パッケージのUnixプログラムは、diff -uによって生成された従来のパッチのパッチ変換を実装します。

ウィーブマージは、2つのファイルの共通の祖先を利用しないアルゴリズムです。代わりに、派生バージョンのファイルで個々の行がどのように追加および削除されたかを追跡し、その情報に基づいてマージされたファイルを生成します。

weave merge は、派生ファイルの各行について、その行の前後の行、およびいずれかの派生ファイルの履歴のどこかの段階でその行が削除されたかどうかという情報を収集します。いずれかの派生ファイルでその行が削除された場合、マージされたバージョンにはその行が存在してはなりません。その他の行については、マージされたバージョンに存在していなければなりません。

各行は、履歴上のいずれかの時点でその行より前に存在したすべての行の後に位置し、履歴上のいずれかの時点でその行より後に存在したすべての行の前に位置するように順序付けられます。これらの制約によってすべての行の完全な順序が与えられない場合、互いに順序付けされていない行は、矛盾する追加行となります。

Weave mergeは、商用リビジョン管理ツールであるBitKeeperで使用されているようで、3方向マージで誤った結果や不良な結果が生じるような問題ケースの一部を処理できます。また、 GNU Bazaarリビジョン管理ツールのマージオプションの一つであり、Codevilleでも使用されています。