version-control - VCS 理論 - マージ: 再帰的リビジョンマージまたは 3 リビジョンマージ?

Question

VCS のマージの可能性について理論的な質問があります。多くの VCS が 3 つのリビジョンマージを使用していることを知っています。これは、共通の祖先である「私の」リビジョンと「あなたの」リビジョンです。私はそれらがどのように機能するかを知っています。

別の代替案である再帰的なリビジョンのマージについて考えましたが、Google では見つかりませんでした。「あなたはアメリカを見つけました！」あなたが考えるかもしれません。Git が再帰マージを使用することは知っています。しかし、Git が再帰マージを使用する理由は、十字型マージのためです。

私は通常のケース、非交差マージについて話しています。

たとえば、共通の祖先 A と分岐 1 および 2 があります。

branch 1: B,  C,  D,  E,  F,  G

branch 2: B', C', D', E', F', G'

前に述べたように、A は共通の祖先なので、B と B' の親です。

G と G' をブランチ 1 にマージします。Git と Mercurial が使用する一般的な方法は、diff3 です。

diff3(ancestor = A, mine = G, yours = G')

これは、O(1) である 3 つのバージョンのみを計算することによってマージを計算します。

私が考えた代替アルゴリズムは O(n) です。

上記の例では、次のようになります。

私が解決できなかった質問は、従来の 3 つのリビジョンのマージよりも、私の方法がより安全で正確であるというケースはありますか?

私のやり方は、従来のやり方が引き起こす衝突を避けることができますか?

私のやり方は、伝統的なやり方では起こらない新たな対立を生み出すことができますか?

私の方法の競合は「本当の」競合ではありませんか? （伝統的なやり方では起こらない）

score 0 · Accepted Answer

G と G' をブランチ 1 にマージします。

なぜ G を branch1 にマージしたいのでしょうか? G はすでに branch1 にいます。最良の場合、このマージから何も得られません。最悪の場合、競合が発生します。' のない他のすべてのリビジョンでも同じ

したがって、B' - G' のみを branch1 にマージする必要があります。そして、これが 3 方向マージです。

ところで。3 方向マージの 3 番目のコンポーネントは、「共通の祖先」ではなく「ベース」です。共通の祖先がベースになることはありますが、常にそうとは限りません。

version-control - VCS 理論 - マージ: 再帰的リビジョン マージまたは 3 リビジョン マージ?