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

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.

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 ...

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ą

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ń.

Oto oryginalna realizacja

http://git.kaarsemaker.net/git/blob/857f26d2f41e16170e48076758d974820af685ff/git-merge-recursive.py

Zasadniczo tworzysz listę wspólnych przodków dla dwóch zatwierdzeń, a następnie łączysz je rekurencyjnie, albo szybko przesyłając do przodu, albo tworząc wirtualne zatwierdzenia, które są używane na podstawie trójstronnego scalania plików.

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 .