Jak szczegółowo działa funkcja „git merge”?

97

Chcę poznać dokładny algorytm (lub blisko tego) stojący za „git merge”. Pomocne będą odpowiedzi przynajmniej na te pytania podrzędne:

  • W jaki sposób git wykrywa kontekst konkretnej niesprzecznej zmiany?
  • W jaki sposób git dowiaduje się, że istnieje konflikt w tych dokładnych wierszach?
  • Jakie rzeczy wykonuje automatyczne scalanie git?
  • Jak działa git, gdy nie ma wspólnej podstawy do łączenia gałęzi?
  • Jak działa git, gdy istnieje wiele wspólnych baz do łączenia gałęzi?
  • Co się stanie, gdy połączę wiele oddziałów jednocześnie?
  • Jaka jest różnica między strategiami scalania?

Ale opis całego algorytmu będzie znacznie lepszy.

przepaść 7
źródło
8
Myślę, że możesz wypełnić całą książkę tymi odpowiedziami ...
Daniel Hilgarth,
2
Możesz też po prostu przejść i przeczytać kod, co potrwa tak długo, jak „opisanie całego algorytmu”
Nevik Rehnel
3
@DanielHilgarth Z przyjemnością się dowiem, czy taka książka już gdzieś istnieje. Referencje są mile widziane.
otchłań. 7
5
@NevikRehnel Tak, mogę. Ale może być znacznie łatwiej, jeśli ktoś zna już teorię kryjącą się za tym kodem.
otchłań. 7
1. Jaki jest „kontekst konkretnej niesprzecznej zmiany”? Punkty 2. i 3. są takie same, ale zanegowane, połączmy te dwa pytania?
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功

Odpowiedzi:

67

Najlepiej byłoby poszukać opisu algorytmu łączenia trójstronnego. Opis wysokiego poziomu wyglądałby mniej więcej tak:

  1. Znajdź odpowiednią bazę do scalania B- wersję pliku, która jest przodkiem obu nowych wersji ( Xi Y), i zazwyczaj najnowszą taką bazę (choć zdarzają się przypadki, w których będzie musiała się cofnąć dalej, czyli jedną z funkcje gitdomyślnego recursivescalania)
  2. Wykonaj dyferencjału o Xz Bi Yo B.
  3. Przejdź przez bloki zmian zidentyfikowane w dwóch różnicach. Jeśli obie strony wprowadzą tę samą zmianę w tym samym miejscu, zaakceptuj jedną; jeśli jeden wprowadza zmianę, a drugi opuszcza ten region sam, wprowadź zmianę w finale; jeśli obaj wprowadzają zmiany w miejscu, ale nie pasują, zaznacz konflikt do rozwiązania ręcznie.

Pełny algorytm zajmuje się tym bardziej szczegółowo, a nawet ma pewną dokumentację ( https://github.com/git/git/blob/master/Documentation/technical/trivial-merge.txt , wraz ze git help XXXstronami gdzie XXX jeden merge-base, merge-file, merge, merge-one-filei ewentualnie kilka innych). Jeśli to nie jest wystarczająco szczegółowe, zawsze jest kod źródłowy ...

twalberg
źródło
11

Jak działa git, gdy istnieje wiele wspólnych baz do łączenia gałęzi?

Ten artykuł był bardzo pomocny: http://codicesoftware.blogspot.com/2011/09/merge-recursive-strategy.html (tutaj jest część 2 ).

Recursive używa diff3 rekurencyjnie do wygenerowania wirtualnej gałęzi, która będzie używana jako przodek.

Na przykład:

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

Następnie:

git checkout E
git merge F

Istnieją 2 najlepszych wspólnych przodków (wspólnych przodków, którzy nie są przodkami żadnego innego) Ci D. Git łączy je w nową wirtualną gałąź V, a następnie używa Vjako podstawy.

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

Przypuszczam, że Git po prostu kontynuowałby działanie, gdyby było więcej najlepszych wspólnych przodków, scalając się Vz następnym.

Artykuł mówi, że jeśli wystąpi konflikt scalania podczas generowania wirtualnej gałęzi, Git po prostu pozostawia znaczniki konfliktu tam, gdzie się znajdują i kontynuuje.

Co się stanie, gdy połączę wiele oddziałów jednocześnie?

Jak wyjaśnił @Nevik Rehnel, zależy to od strategii, jest to dobrze wyjaśnione w man git-merge MERGE STRATEGIESsekcji.

Tylko octopusi ours/ theirsobsługują łączenie wielu oddziałów jednocześnie, recursivena przykład nie.

octopusodmawia połączenia, jeśli byłyby konflikty, i oursjest to połączenie trywialne, więc nie może być konfliktów.

Te polecenia generują nowe zatwierdzenie, które będzie miało więcej niż 2 rodziców.

Zrobiłem jeden merge -X octopusna Git 1.8.5 bez konfliktów, aby zobaczyć, jak to działa.

Stan początkowy:

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

Akcja:

git checkout B
git merge -Xoctopus C D

Nowy stan:

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

Zgodnie z oczekiwaniami Ema 3 rodziców.

TODO: jak dokładnie octopus działa na modyfikacjach pojedynczego pliku. Rekurencyjne scalanie dwukierunkowe 3-drożne?

Jak działa git, gdy nie ma wspólnej podstawy do łączenia gałęzi?

@Torek wspomina, że ​​od 2.9 scalanie kończy się niepowodzeniem bez --allow-unrelated-histories.

Wypróbowałem to empirycznie na Git 1.8.5:

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 zawiera:

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

Następnie:

git checkout --conflict=diff3 -- .

a zawiera:

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

Interpretacja:

  • baza jest pusta
  • gdy baza jest pusta, nie można rozwiązać żadnej modyfikacji w pojedynczym pliku; można rozwiązać tylko takie rzeczy, jak dodanie nowego pliku. Powyższy konflikt zostałby rozwiązany na 3-kierunkowym połączeniu z bazą a\nc\njako dodaniem pojedynczej linii
  • Myślę , że trójdrożne scalanie bez pliku podstawowego nazywa się dwukierunkowym scalaniem, które jest po prostu różnicą
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
źródło
1
Jest nowy link SO do tego pytania, więc przejrzałem tę odpowiedź (która jest całkiem dobra) i zauważyłem, że ostatnia zmiana w Git trochę zdezaktualizowała ostatnią sekcję. Od wersji Git 2.9 (zatwierdzenie e379fdf34fee96cd205be83ff4e71699bdc32b18), Git odmawia teraz połączenia, jeśli nie ma bazy scalania, chyba że dodasz --allow-unrelated-histories.
torek
1
Oto kolejny artykuł z tego, który @Ciro opublikował: blog.plasticscm.com/2012/01/…
adam0101
Chyba że zachowanie zmieniło się od czasu ostatniej próby: --allow-unrelated-historiesmożna pominąć, jeśli nie ma wspólnych ścieżek plików między scalanymi gałęziami.
Jeremy List
Mała korekta: istnieje oursstrategia łączenia, ale nie ma theirsstrategii łączenia. recursive+ theirsstrategia może rozwiązać tylko dwie gałęzie. git-scm.com/docs/git-merge#_merge_strategies
nekketsuuu
9

Ja też jestem zainteresowany. Nie znam odpowiedzi, ale ...

Złożony system, który działa, niezmiennie wyewoluował z prostego systemu, który działał

Myślę, że scalanie git jest wysoce wyrafinowane i będzie bardzo trudne do zrozumienia - ale jednym ze sposobów podejścia jest od jego prekursorów i skupienie się na sercu twojego zainteresowania. To znaczy, biorąc pod uwagę dwa pliki, które nie mają wspólnego przodka, w jaki sposób git merge sprawdza, jak je scalić i gdzie występują konflikty?

Spróbujmy znaleźć jakieś prekursory. Od 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).

Z Wikipedii: 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

Ten ostatni link to plik PDF z artykułem szczegółowo opisującym diff3algorytm. Oto wersja przeglądarki PDF Google . Ma tylko 12 stron, a algorytm to tylko kilka stron - ale w pełni matematyczne podejście. Może się to wydawać zbyt formalne, ale jeśli chcesz zrozumieć scalanie git, musisz najpierw zrozumieć prostszą wersję. Nie sprawdzałem jeszcze, ale z nazwą taką jak diff3prawdopodobnie będziesz musiał również zrozumieć diff (który używa najdłuższego wspólnego algorytmu podciągów). Jednak może istnieć bardziej intuicyjne wyjaśnienie diff3, jeśli masz Google ...


Teraz właśnie przeprowadziłem eksperyment porównujący diff3i git merge-file. Biorą te same trzy pliki wejściowe version1 OldVersion Version2 i konflikty Należy zaznaczyć sposób same, z <<<<<<< version1, =======, >>>>>>> version2( diff3również ||||||| oldversion), pokazując ich wspólne dziedzictwo.

Użyłem pustego pliku dla starej wersji i prawie identycznych plików dla wersji1 i wersji2 z tylko jedną dodatkową linią dodaną do wersji2 .

Wynik: git merge-filezidentyfikowano pojedynczą zmienioną linię jako konflikt; ale diff3potraktował całe dwa pliki jako konflikt. Zatem, tak wyrafinowany jak diff3, scalanie gita jest jeszcze bardziej wyrafinowane, nawet w tym najprostszym przypadku.

Oto rzeczywiste wyniki (użyłem odpowiedzi @ twalberg do tekstu). Zwróć uwagę na potrzebne opcje (zobacz odpowiednie strony podręcznika).

$ 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

Jeśli naprawdę cię to interesuje, to trochę królicza nora. Wydaje mi się, że jest tak głęboka, jak wyrażenia regularne, najdłuższy wspólny algorytm podciągów diff, gramatyka bezkontekstowa czy algebra relacyjna. Jeśli chcesz dotrzeć do sedna sprawy, myślę, że możesz, ale wymaga to pewnych zdecydowanych badań.

13ren
źródło
0

W jaki sposób git wykrywa kontekst konkretnej niesprzecznej zmiany?
W jaki sposób git dowiaduje się, że istnieje konflikt w tych dokładnych wierszach?

Jeśli ta sama linia uległa zmianie po obu stronach scalania, jest to konflikt; jeśli nie, zmiana z jednej strony (jeśli istnieje) jest akceptowana.

Jakie rzeczy wykonuje automatyczne scalanie git?

Zmiany, które nie są sprzeczne (patrz wyżej)

Jak działa git, gdy istnieje wiele wspólnych baz do łączenia gałęzi?

Zgodnie z definicją bazy scalającej Git , istnieje tylko jedna (najnowszy wspólny przodek).

Co się stanie, gdy połączę wiele oddziałów jednocześnie?

To zależy od strategii łączenia (tylko octopusi ours/ theirsstrategie obsługują łączenie więcej niż dwóch gałęzi).

Jaka jest różnica między strategiami scalania?

Jest to wyjaśnione na stronie git mergepodręcznika .

Nevik Rehnel
źródło
2
Co oznacza „ta sama linia”? Jeśli wstawię nową, niepustą linię między dwiema innymi i połączę - jakie linie są takie same? Jeśli usunę kilka wierszy z jednej gałęzi, które z nich są „takie same” w innej?
otchłań. 7
1
Odpowiedź w tekście jest trochę trudna. Git używa [diffs] (en.wikipedia.org/wiki/Diff) do wyrażenia różnicy między dwoma plikami (lub dwiema wersjami pliku). Może wykryć, czy linie zostały dodane lub usunięte, porównując kontekst (domyślnie trzy linie). „Ta sama linia” oznacza wtedy kontekst, pamiętając o dodaniach i usunięciach.
Nevik Rehnel,
1
Sugerujesz, że zmiana „tej samej linii” oznaczałaby konflikt. Czy silnik automerge naprawdę jest oparty na linii? Czy jest oparty na przystojniaku? Czy jest tylko jeden wspólny przodek? Jeśli tak, dlaczego git-merge-recursiveistnieje?
Edward Thomson,
1
@EdwardThomson: Tak, rozdzielczość jest oparta na liniach (porcje można podzielić na mniejsze porcje, aż pozostanie tylko jedna linia). Domyślna strategia scalania używa najnowszego wspólnego przodka jako odniesienia, ale są inne, jeśli chcesz użyć czegoś innego. I nie wiem, co git-merge-recursivepowinno być (nie ma strony podręcznika, a Google nic nie daje). Więcej informacji na ten temat można znaleźć na stronach podręcznika git mergei git merge-base.
Nevik Rehnel,
1
git-mergeStrona mężczyzna i git-merge-basestrony man, że podkreślić omówienia wielu wspólnych przodków i rekurencyjną seryjnej. Czuję, że twoja odpowiedź jest niekompletna bez dyskusji na ten temat.
Edward Thomson,