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 diff3
algorytm. 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 diff3
prawdopodobnie 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 diff3
i git merge-file
. Biorą te same trzy pliki wejściowe version1 OldVersion Version2 i konflikty Należy zaznaczyć sposób same, z <<<<<<< version1
, =======
, >>>>>>> version2
( diff3
ró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-file
zidentyfikowano pojedynczą zmienioną linię jako konflikt; ale diff3
potraktował 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ń.