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

バージョン管理において、マージ(統合とも呼ばれる) は、バージョン管理されたファイルのコレクションに加えられた複数の変更を調整する基本的な操作です。ほとんどの場合、これは、2 つの独立したブランチでファイルが変更され、その後マージされるときに必要になります。その結果、両方の変更セットを含む単一のファイル コレクションが作成されます。

変更を再構築するのに十分な履歴情報があり、変更が競合していないため、マージを自動的に実行できる場合もあります。それ以外の場合は、結果のファイルに何を含めるかを人が正確に決定する必要があります。多くのリビジョン管理ソフトウェア ツールには、マージ機能が含まれています。

マージには、非構造化と構造化の 2 種類があります。

非構造化マージは、通常、テキスト行を原子単位として使用して、生のテキストに対して操作します。これは、Unix ツール (diff/patch) および CVS ツール (SVN、Git) が使用するものです。テキスト行はソース コードの構造を表していないため、 これには制限があります^{[意見] 。}

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

自動マージは、バージョン管理ソフトウェアが（論理的な意味で）同時に発生した変更を調整するときに行うことです。また、他のソフトウェアでも、同じコンテンツを同時に編集できる場合は自動マージを採用しています。たとえば、Wikipedia では 2 人のユーザーが同時に同じ記事を編集できます。後者が保存すると、以前の変更セットが上書きされるのではなく、その変更が記事にマージされます。^[1] 手動マージは、異なるファイルを調整する必要がある場合にユーザーが頼らなければならない方法です（マージ ツールの助けを借りる場合もあります）。たとえば、2 つのシステムでわずかに異なるバージョンの設定ファイルがあり、ユーザーが両方で適切な内容を使用したい場合は、通常、設定ファイルを手動でマージし、両方のソースから必要な変更を選択することにより実現できます（これは双方向マージとも呼ばれます）。自動マージで変更の競合が発生した場合にも手動マージが必要です。たとえば、同じコード行に対する 2 つの変更 (関数名の変更とコメントの追加など) をマージできる自動マージ ツールはほとんどありません。このような場合、リビジョン コントロール システムでは、ユーザーが意図したマージ結果を指定する必要があります。

自動マージにはさまざまなアプローチがあり、微妙な違いがあります。より注目すべきマージ アルゴリズムには、3 方向マージ、再帰 3 方向マージ、ファジー パッチ適用、ウィーブ マージ、パッチ交換などがあります。

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

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

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

3 方向マージは、広く普及しているdiff3プログラムによって実装されており、ファイル ロック ベースのリビジョン コントロール システムからマージ ベースのリビジョン コントロール システムへの切り替えを可能にした中心的なイノベーションでした。これは、Concurrent Versions System (CVS) によって広く使用されています。

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

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

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

(Git の再帰マージ実装では、あるバージョンでファイルが変更され、別のバージョンで名前が変更されるなどの他の厄介なケースも処理されますが、これらは 3 方向マージ実装の拡張であり、マージする 3 つのバージョンを見つけるための手法の一部ではありません。)

再帰的な 3 方向マージは、ツールがマージする派生物の全体的な祖先の有向非巡回グラフ(DAG) についての知識を持っている場合にのみ使用できます。したがって、派生物またはマージが親を完全に指定していない状況では使用できません。

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

ただし、パッチ プログラムには、パッチの作成に使用された元のファイルとまったく同じではないファイルにパッチを適用する機能もあります。このプロセスはファジー パッチ アプリケーションと呼ばれ、結果として一種の非対称 3 方向マージが行われます。パッチ プログラムがパッチを適用する場所を見つけられない場合、パッチ内の変更は破棄されます。

CVS がdiff3のスクリプトのセットとして始まったように、GNU arch もpatch のスクリプトのセットとして始まりました。しかし、あいまいなパッチ適用は比較的信頼できない方法であり、コンテキストが少なすぎるパッチ (特に新しいファイルを作成するもの) を誤って適用したり、両方の派生プログラムが行った削除を適用しないことがあります。

パッチ交換はDarcsで変更をマージするために使用され、gitでも実装されています(ただし、「リベース」と呼ばれます)。パッチ交換マージとは、パッチ (つまり、変更の説明) の順序を変更して、線形の履歴を形成することを意味します。実際には、共通の状況のコンテキストで 2 つのパッチが作成されると、マージ時に、そのうちの 1 つが書き換えられ、もう一方のコンテキストで行われたように見えます。

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

パッチ交換は正式には多くの研究が行われてきましたが、パッチ交換におけるマージ競合に対処するアルゴリズムは未だに未解決の研究課題です。しかし、パッチ交換は「正しい」マージ結果を生成することが証明されています^[4]。一方、他のマージ戦略は、ユーザーが見たいものを生成するためのヒューリスティックな手法がほとんどです。

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

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

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

行は、各行が、履歴のある時点でその行に先行するすべての行の後、および履歴のある時点でその行に後続するすべての行の前になるように並べ替えられます。これらの制約によってすべての行の完全な順序付けが得られない場合、互いに対して順序付けされていない行は、競合する追加になります。

Weave マージは、商用リビジョン管理ツールBitKeeperで使用されているようで、3 方向マージで間違った結果や悪い結果が生じる問題の一部を処理できます。また、GNU Bazaarリビジョン管理ツールのマージ オプションの 1 つでもあり、Codeville でも使用されています。^{[引用が必要]}

• ファイル比較ツールの比較
• 差分
• ブランチ（リビジョン管理）