Was sind herausragende Probleme mit dem rekursiven Three-Way Merge-Algorithmus?

Question

Git implementiert eine recursive 3-way merge Strategie, die solves problems with criss-crossing histories, aber welche Probleme löst diese Strategie nicht?

Die beste Darstellung die ich bisher gefunden habe, ist auf der old revctrl wiki:

Recursive three-way merge usually provides the right answer, however there are some edge cases. For example, conflict markers can be matched incorrectly, because they aren't given any special semantic meaning for the merge algorithm, and are simply treated as lines. In particular, there are (somewhat complicated) cases where the conflict markers of two unrelated conflicts get matched against each other, even though the content sections of them are totally unrelated.

Also, recursive merge can do some of the same invalid merges as SimpleWeaveMerge does, which are described below, although exactly what it does under those circumstances is highly dependant on the details of the 3 way merge algorithm, but it isn't clear that tweaking the 3-way merge algorithm to be more conservative about showing conflicts will make such problems go away. Basically, including the conflict is creating a weave, and that introduces the problems which weaves have.

Finally, recursive three-way merge has all the inherent problems of ImplicitUndo . In particular, merging together multiple things which merge cleanly will sometimes give different answers depending on the order in which the merges happen. In fact, it's possible in a never-ending criss-cross case for a value to flip-flop until the end of time without ever getting a single unclean merge. This is a very fundamental problem, and fixing it requires first deciding what one wants to have happen in such cases, because what is appropriate behavior is unclear.

Allerdings sind diese Probleme vage angegeben. Was sind spezifische Situationen, in denen rekursive 3-Wege-Zusammenführung bricht und auf welche Weise bricht es?

Kann jemand Versionskontrollhistorien zeigen, dass es verschraubt?

(Ich bin nicht über Probleme in dem Diff-Algorithmus zu fragen, wie Verständnis Quellcode Semantik oder Konfliktlösung. Lassen Sie sich annehmen die Benutzer glücklich sind, Konflikte zu lösen und einen naiven String diff.)

Answer 1

Reddit Benutzer/u/PascaleDaVinci schlägt ein Thema here:

A 
/\ 
B B 
| 
A 

The programmer introduced a change in both branches, then reverted it on one side. A three-way merge will reintroduce it without a conflict, though it is not clear whether that is the programmer's intent, as she rejected the change on one side, but kept it on the other. Because three-way merges ignore the history of changes in between the revisions, they don't see the ambiguous programmer intent and thus can't identify that ambiguity.

auf Ihrer Interpretation des Algorithmus der Merge Je tun sollte, nennen könnte Sie dies ein Problem, oder nicht.

Answer 2

(Dies ist keine vollständige Antwort auf die Frage, aber es könnte eine Antwort helfen abzuleiten.)

Es stellt sich heraus, dass die Frage der kreuz und quer verschmilzt in einer Version der Definition analogical sind DAG von semilattices im mathematischen Bereich der order theory, die in CRDT Forschung verwendet werden, um Datenstruktur Versionshistorien zu definieren, die ohne Fehler zusammengefügt werden können:

• CRDTs auf Version analog sind Kontrollsysteme
• A CRDT Halbverband ist ein Äquivalent Versionskontrolle DAG, wenn die DAG keine Kreuzungsversionen enthält
• Die rekursive 3-Wege-Merge-Strategie konvertiert eine kreuzweise DAG in ein gültiges Semilatice, indem sichergestellt wird, dass es einen eindeutigen "kleinsten gemeinsamen Vorfahren" alias "niedrigste obere Grenze" gibt.
• Ein "kleinster gemeinsamer Vorfahr" (im Bereich der Versionskontrolle) entspricht dem Konzept einer "niedrigsten oberen Schranke" (in Gitterordnungstheorie).

Zusammengefasst: CRDTs erfordern eine Semilatizität. Ein Semilatiz erfordert, dass jedes Paar von Einträgen eine einzigartige niedrigste Obergrenze aufweist. Die 3-Wege-Zusammenführung in der Versionskontrolle erfordert auch, dass es einen eindeutigen kleinsten gemeinsamen Vorfahren gibt, und hat einen Algorithmus, um einen zu erstellen, wenn nicht.

Fazit: Es ist möglich, dass CRDT Forschung einen mathematischen Beweis hat, dass eine perfekte Zusammenführung möglich ist, wenn die Version Graph, der eine Halbverband bildet, und wenn ja, kann dieser Nachweis verallgemeinert werden zu zeigen, dass rekursive 3-Wege-Merge auch perfekt. Ein guter Anhaltspunkt könnte darin bestehen, die Nützlichkeit der algebraic operators of a semilattice zu analysieren, die nur gilt, wenn es einen eindeutigen kleinsten gemeinsamen Vorfahren gibt. Diese Operatoren können zum Zusammenführen notwendig sein - und wenn das der Fall ist, ist es notwendig, einen gemeinsamen Vorfahren zu haben.