Wie funktioniert "Git Merge" im Detail?

90

Ich möchte einen genauen Algorithmus (oder einen ähnlichen) hinter 'git merge' kennen. Die Antworten zumindest auf diese Unterfragen sind hilfreich:

  • Wie erkennt git den Kontext einer bestimmten nicht widersprüchlichen Änderung?
  • Wie findet Git heraus, dass es in genau diesen Zeilen einen Konflikt gibt?
  • Welche Dinge führt Git automatisch zusammen?
  • Wie funktioniert git, wenn es keine gemeinsame Basis für das Zusammenführen von Zweigen gibt?
  • Wie funktioniert Git, wenn es mehrere gemeinsame Grundlagen für das Zusammenführen von Zweigen gibt?
  • Was passiert, wenn ich mehrere Zweige gleichzeitig zusammenführe?
  • Was ist ein Unterschied zwischen Zusammenführungsstrategien?

Aber die Beschreibung eines ganzen Algorithmus wird viel besser sein.

Abgrund.7
quelle
5
Ich denke, Sie könnten ein ganzes Buch mit diesen Antworten füllen ...
Daniel Hilgarth
2
Oder Sie könnten einfach den Code lesen, was ungefähr so ​​lange dauern würde, wie "den gesamten Algorithmus beschreiben"
Nevik Rehnel
3
@ DanielHilgarth Ich würde mich freuen herauszufinden, ob es irgendwo schon ein solches Buch gibt. Referenzen sind willkommen.
Abyss.7
5
@ NevikRehnel Ja, ich kann. Aber es kann viel einfacher werden, wenn jemand die Theorie hinter diesem Code bereits kennt.
Abyss.7
1. Was ist "der Kontext einer bestimmten nicht widersprüchlichen Änderung"? Die Punkte 2. und 3. sind gleich, aber negiert. Lassen Sie uns diese beiden Fragen zusammenführen.
Ciro Santilli 17 冠状 病 六四 事件 17

Antworten:

65

Am besten suchen Sie nach einer Beschreibung eines 3-Wege-Zusammenführungsalgorithmus. Eine Beschreibung auf hoher Ebene würde ungefähr so ​​aussehen:

  1. Suchen Sie eine geeignete Zusammenführungsbasis B- eine Version der Datei, die ein Vorfahr der beiden neuen Versionen ( Xund Y) ist, und normalerweise die neueste dieser Basis (obwohl es Fälle gibt, in denen sie weiter zurückgehen muss, eine davon die Funktionen von gits Standard recursiveMerge)
  2. Führen Sie Unterschiede Xmit Bund Ymit durch B.
  3. Gehen Sie durch die Änderungsblöcke, die in den beiden Unterschieden angegeben sind. Wenn beide Seiten dieselbe Änderung an derselben Stelle einführen, akzeptieren Sie eine der beiden. Wenn einer eine Änderung einführt und der andere diese Region in Ruhe lässt, führen Sie die Änderung im Finale ein. Wenn beide Änderungen an einer Stelle einführen, diese jedoch nicht übereinstimmen, markieren Sie einen Konflikt, der manuell gelöst werden soll.

Der vollständige Algorithmus befasst sich ausführlicher damit und enthält sogar einige Dokumentationen ( https://github.com/git/git/blob/master/Documentation/technical/trivial-merge.txt) sowie die git help XXXSeiten , wobei XXX ist eine merge-base, merge-file, merge, merge-one-fileund möglicherweise einige andere). Wenn das nicht tief genug ist, gibt es immer Quellcode ...

Twalberg
quelle
11

Wie funktioniert Git, wenn es mehrere gemeinsame Grundlagen für das Zusammenführen von Zweigen gibt?

Dieser Artikel war sehr hilfreich: http://codicesoftware.blogspot.com/2011/09/merge-recursive-strategy.html (hier ist Teil 2 ).

Rekursiv verwendet diff3 rekursiv, um einen virtuellen Zweig zu generieren, der als Vorfahr verwendet wird.

Z.B:

(A)----(B)----(C)-----(F)
        |      |       |
        |      |   +---+
        |      |   |
        |      +-------+
        |          |   |
        |      +---+   |
        |      |       |
        +-----(D)-----(E)

Dann:

git checkout E
git merge F

Es gibt 2 beste gemeinsame Vorfahren (gemeinsame Vorfahren, die keine Vorfahren anderer sind) Cund D. Git führt sie zu einem neuen virtuellen Zweig zusammen Vund verwendet sie dann Vals Basis.

(A)----(B)----(C)--------(F)
        |      |          |
        |      |      +---+
        |      |      |
        |      +----------+
        |      |      |   |
        |      +--(V) |   |
        |          |  |   |
        |      +---+  |   |
        |      |      |   |
        |      +------+   |
        |      |          |
        +-----(D)--------(E)

Ich nehme an, Git würde einfach mit dem fortfahren, wenn es mehr gemeinsame Vorfahren gäbe, die Vmit dem nächsten verschmelzen .

Der Artikel besagt, dass Git bei einem Zusammenführungskonflikt beim Generieren des virtuellen Zweigs die Konfliktmarkierungen einfach dort belässt, wo sie sich befinden, und fortfährt.

Was passiert, wenn ich mehrere Zweige gleichzeitig zusammenführe?

Wie @Nevik Rehnel erklärte, hängt es von der Strategie ab, es wird im man git-merge MERGE STRATEGIESAbschnitt gut erklärt .

Nur octopusund ours/ oder theirsdas gleichzeitige Zusammenführen mehrerer Zweige unterstützen dies recursivebeispielsweise nicht.

octopusweigert sich zusammenzuführen, wenn es Konflikte geben würde, und oursist eine triviale Zusammenführung, so dass es keine Konflikte geben kann.

Diese Befehle generieren ein neues Commit und haben mehr als 2 Eltern.

Ich habe eine merge -X octopusauf Git 1.8.5 ohne Konflikte gemacht, um zu sehen, wie es geht.

Ausgangszustand:

   +--B
   |
A--+--C
   |
   +--D

Aktion:

git checkout B
git merge -Xoctopus C D

Neuer Zustand:

   +--B--+
   |     |
A--+--C--+--E
   |     |
   +--D--+

Wie erwartet Ehat 3 Eltern.

TODO: Wie genau Octopus mit einzelnen Dateimodifikationen arbeitet. Rekursive Zwei-mal-Zwei-3-Wege-Zusammenführungen?

Wie funktioniert git, wenn es keine gemeinsame Basis für das Zusammenführen von Zweigen gibt?

@Torek erwähnt, dass die Zusammenführung seit 2.9 ohne fehlschlägt --allow-unrelated-histories.

Ich habe es empirisch auf Git 1.8.5 ausprobiert:

git init
printf 'a\nc\n' > a
git add .
git commit -m a

git checkout --orphan b
printf 'a\nb\nc\n' > a
git add .
git commit -m b
git merge master

a enthält:

a
<<<<<<< ours
b
=======
>>>>>>> theirs
c

Dann:

git checkout --conflict=diff3 -- .

a enthält:

<<<<<<< ours
a
b
c
||||||| base
=======
a
c
>>>>>>> theirs

Deutung:

  • Die Basis ist leer
  • Wenn die Basis leer ist, ist es nicht möglich, Änderungen an einer einzelnen Datei aufzulösen. Nur Dinge wie das Hinzufügen neuer Dateien können behoben werden. Der obige Konflikt würde durch eine 3-Wege-Zusammenführung mit der Basis a\nc\nals einzeilige Addition gelöst
  • Ich denke, dass eine 3-Wege-Zusammenführung ohne Basisdatei als 2-Wege-Zusammenführung bezeichnet wird, was nur ein Unterschied ist
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
quelle
1
Es gibt einen neuen SO-Link zu dieser Frage, daher habe ich diese Antwort gescannt (was ziemlich gut ist) und festgestellt, dass eine kürzliche Git-Änderung den letzten Abschnitt etwas veraltet hat. Seit Git Version 2.9 (Commit e379fdf34fee96cd205be83ff4e71699bdc32b18) lehnt Git das Zusammenführen ab, wenn es keine Zusammenführungsbasis gibt, es sei denn, Sie fügen hinzu --allow-unrelated-histories.
Torek
1
Hier ist der Folgeartikel von dem, den @Ciro gepostet hat: blog.plasticscm.com/2012/01/…
adam0101
Es sei denn, das Verhalten hat sich seit meinem letzten Versuch geändert: --allow-unrelated-historiesKann weggelassen werden, wenn zwischen den zusammengeführten Zweigen keine gemeinsamen Dateipfade vorhanden sind.
Jeremy List
Kleine Korrektur: Es gibt eine oursZusammenführungsstrategie, aber keine theirsZusammenführungsstrategie. recursive+ theirsStrategie kann nur zwei Zweige auflösen. git-scm.com/docs/git-merge#_merge_strategies
nekketsuuu
9

Ich bin auch interessiert. Ich weiß die Antwort nicht, aber ...

Ein komplexes System, das funktioniert, hat sich aus einem einfachen System entwickelt, das funktioniert hat

Ich denke, die Verschmelzung von git ist hochentwickelt und wird sehr schwer zu verstehen sein - aber eine Möglichkeit, dies zu erreichen, sind die Vorläufer und die Konzentration auf das Herz Ihres Anliegens. Das heißt, bei zwei Dateien, die keinen gemeinsamen Vorfahren haben, wie funktioniert Git Merge, wie sie zusammengeführt werden und wo Konflikte auftreten?

Versuchen wir, einige Vorläufer zu finden. Von git help merge-file:

git merge-file is designed to be a minimal clone of RCS merge; that is,
       it implements all of RCS merge's functionality which is needed by
       git(1).

Aus Wikipedia: http://en.wikipedia.org/wiki/Git_%28software%29 -> http://en.wikipedia.org/wiki/Three-way_merge#Three-way_merge -> http: //en.wikipedia .org / wiki / Diff3 -> http://www.cis.upenn.edu/~bcpierce/papers/diff3-short.pdf

Dieser letzte Link ist ein PDF eines Papiers, das den diff3Algorithmus im Detail beschreibt. Hier ist eine Google PDF-Viewer-Version . Es ist nur 12 Seiten lang und der Algorithmus ist nur ein paar Seiten lang - aber eine umfassende mathematische Behandlung. Das mag etwas zu formal erscheinen, aber wenn Sie die Zusammenführung von git verstehen möchten, müssen Sie zuerst die einfachere Version verstehen. Ich habe es noch nicht überprüft, aber mit einem Namen wie diff3müssen Sie wahrscheinlich auch diff verstehen (das einen längsten gemeinsamen Subsequenzalgorithmus verwendet). Es kann jedoch eine intuitivere Erklärung diff3geben, wenn Sie eine Google ...


Jetzt habe ich gerade ein Experiment durchgeführt diff3und git merge-file. Sie nehmen die gleichen drei Eingabedateien version1 oldversion version2 und markieren Konflikte die Art und Weise gleich, mit <<<<<<< version1, =======, >>>>>>> version2( diff3auch hat ||||||| oldversion), ihr gemeinsames Erbe zeigt.

Früher habe ich eine leere Datei für oldversion und nahezu identische Dateien für version1 und version2 mit nur einem zusätzlichen Zeile hinzugefügt version2 .

Ergebnis: git merge-fileidentifizierte die einzelne geänderte Zeile als Konflikt; diff3behandelte aber die ganzen zwei Dateien als Konflikt. So ausgefeilt diff3 auch ist, die Zusammenführung von git ist selbst in diesem einfachsten Fall noch ausgefeilter.

Hier sind die tatsächlichen Ergebnisse (ich habe die Antwort von @ twalberg für den Text verwendet). Beachten Sie die benötigten Optionen (siehe entsprechende Seiten).

$ git merge-file -p fun1.txt fun0.txt fun2.txt

You might be best off looking for a description of a 3-way merge algorithm. A
high-level description would go something like this:

    Find a suitable merge base B - a version of the file that is an ancestor of
both of the new versions (X and Y), and usually the most recent such base
(although there are cases where it will have to go back further, which is one
of the features of gits default recursive merge) Perform diffs of X with B and
Y with B.  Walk through the change blocks identified in the two diffs. If both
sides introduce the same change in the same spot, accept either one; if one
introduces a change and the other leaves that region alone, introduce the
change in the final; if both introduce changes in a spot, but they don't match,
mark a conflict to be resolved manually.
<<<<<<< fun1.txt
=======
THIS IS A BIT DIFFERENT
>>>>>>> fun2.txt

The full algorithm deals with this in a lot more detail, and even has some
documentation (/usr/share/doc/git-doc/technical/trivial-merge.txt for one,
along with the git help XXX pages, where XXX is one of merge-base, merge-file,
merge, merge-one-file and possibly a few others). If that's not deep enough,
there's always source code...

$ diff3 -m fun1.txt fun0.txt fun2.txt

<<<<<<< fun1.txt
You might be best off looking for a description of a 3-way merge algorithm. A
high-level description would go something like this:

    Find a suitable merge base B - a version of the file that is an ancestor of
both of the new versions (X and Y), and usually the most recent such base
(although there are cases where it will have to go back further, which is one
of the features of gits default recursive merge) Perform diffs of X with B and
Y with B.  Walk through the change blocks identified in the two diffs. If both
sides introduce the same change in the same spot, accept either one; if one
introduces a change and the other leaves that region alone, introduce the
change in the final; if both introduce changes in a spot, but they don't match,
mark a conflict to be resolved manually.

The full algorithm deals with this in a lot more detail, and even has some
documentation (/usr/share/doc/git-doc/technical/trivial-merge.txt for one,
along with the git help XXX pages, where XXX is one of merge-base, merge-file,
merge, merge-one-file and possibly a few others). If that's not deep enough,
there's always source code...
||||||| fun0.txt
=======
You might be best off looking for a description of a 3-way merge algorithm. A
high-level description would go something like this:

    Find a suitable merge base B - a version of the file that is an ancestor of
both of the new versions (X and Y), and usually the most recent such base
(although there are cases where it will have to go back further, which is one
of the features of gits default recursive merge) Perform diffs of X with B and
Y with B.  Walk through the change blocks identified in the two diffs. If both
sides introduce the same change in the same spot, accept either one; if one
introduces a change and the other leaves that region alone, introduce the
change in the final; if both introduce changes in a spot, but they don't match,
mark a conflict to be resolved manually.
THIS IS A BIT DIFFERENT

The full algorithm deals with this in a lot more detail, and even has some
documentation (/usr/share/doc/git-doc/technical/trivial-merge.txt for one,
along with the git help XXX pages, where XXX is one of merge-base, merge-file,
merge, merge-one-file and possibly a few others). If that's not deep enough,
there's always source code...
>>>>>>> fun2.txt

Wenn Sie wirklich daran interessiert sind, ist es ein bisschen wie ein Kaninchenbau. Für mich scheint es so tief wie reguläre Ausdrücke, der längste gängige Subsequenzalgorithmus für Diff, kontextfreie Grammatiken oder relationale Algebra. Wenn Sie dem auf den Grund gehen wollen, können Sie es meiner Meinung nach, aber es wird einige entschlossene Studien erfordern.

13ren
quelle
0

Wie erkennt git den Kontext einer bestimmten nicht widersprüchlichen Änderung?
Wie findet Git heraus, dass es in genau diesen Zeilen einen Konflikt gibt?

Wenn sich auf beiden Seiten der Zusammenführung dieselbe Zeile geändert hat, liegt ein Konflikt vor. Wenn dies nicht der Fall ist, wird die Änderung von einer Seite (falls vorhanden) akzeptiert.

Welche Dinge führt Git automatisch zusammen?

Änderungen, die nicht in Konflikt stehen (siehe oben)

Wie funktioniert Git, wenn es mehrere gemeinsame Grundlagen für das Zusammenführen von Zweigen gibt?

Nach der Definition einer Git-Merge-Basis gibt es immer nur eine (den neuesten gemeinsamen Vorfahren).

Was passiert, wenn ich mehrere Zweige gleichzeitig zusammenführe?

Das hängt von der Merge - Strategie (nur die octopusund die ours/ theirsStrategien unterstützen Verschmelzung mehr als zwei Zweige).

Was ist ein Unterschied zwischen Zusammenführungsstrategien?

Dies wird in der git mergeManpage erklärt .

Nevik Rehnel
quelle
2
Was bedeutet die gleiche Zeile? Wenn ich eine neue nicht leere Zeile zwischen zwei anderen einfüge und zusammenführe - welche Zeilen sind gleich? Wenn ich einige Zeilen in einem Zweig lösche, welche sind in einem anderen Zweig gleich?
Abyss.7
1
Das ist etwas schwierig im Text zu beantworten. Git verwendet [diffs] (en.wikipedia.org/wiki/Diff), um den Unterschied zwischen zwei Dateien (oder zwei Revisionen einer Datei) auszudrücken. Durch Vergleichen des Kontexts (standardmäßig drei Zeilen) kann festgestellt werden, ob Zeilen hinzugefügt oder entfernt wurden. "Gleiche Zeile" bedeutet dann Kontext, wobei Hinzufügungen und Löschungen berücksichtigt werden.
Nevik Rehnel
1
Sie schlagen vor, dass die Änderung der "gleichen Linie" auf einen Konflikt hinweist. Ist die Automerge-Engine wirklich linienbasiert? Oder ist es hunk-basiert? Gibt es immer nur einen gemeinsamen Vorfahren? Wenn ja, warum gibt git-merge-recursivees das?
Edward Thomson
1
@EdwardThomson: Ja, die Auflösung ist zeilenbasiert (Hunks können in kleinere Hunks zerlegt werden, bis nur noch eine Zeile übrig ist). Die Standard-Zusammenführungsstrategie verwendet den neuesten gemeinsamen Vorfahren als Referenz. Es gibt jedoch auch andere, wenn Sie etwas anderes verwenden möchten. Und ich weiß nicht, was git-merge-recursivesein soll (es gibt keine Manpage und Google liefert nichts). Weitere Informationen dazu finden Sie auf den zu finden git mergeund git merge-baseman - Seiten.
Nevik Rehnel
1
In der git-mergeManpage und den git-merge-baseManpages, auf die Sie hinweisen, werden mehrere gemeinsame Vorfahren und die rekursive Zusammenführung erläutert. Ich bin der Meinung, dass Ihre Antwort ohne eine Diskussion darüber unvollständig ist.
Edward Thomson