Как "git merge" работает в деталях?

Ответ 1

Вам может быть лучше искать описание трехмерного алгоритма слияния. Описание высокого уровня будет выглядеть примерно так:

• Найдите подходящую базу слияния B - версию файла, которая является предком обеих новых версий (X и Y), и обычно самая последняя такая база (хотя бывают случаи, когда он должен будет вернуться назад, что является одной из особенностей git default recursive merge)
• Выполните различие X с B и Y с помощью B.
• Пройдите через блоки изменения, указанные в двух различиях. Если обе стороны вводят одно и то же изменение в одном и том же месте, примите одно; если вводить изменение, а другое оставляет только этот регион, вносите изменение в финале; если оба вводят изменения в пятне, но они не совпадают, отметьте конфликт, который будет разрешен вручную.

Полный алгоритм имеет дело с этим более подробно и даже имеет некоторую документацию (/usr/share/doc/git-doc/technical/trivial-merge.txt для одного, а также страницы git help XXX, где XXX является одним из merge-base, merge-file, merge, merge-one-file и, возможно, несколько других). Если это недостаточно глубоко, всегда есть исходный код...

Ответ 2

Как выполняет git, когда существует несколько общих оснований для объединения ветвей?

Эта статья была очень полезной: http://codicesoftware.blogspot.com/2011/09/merge-recursive-strategy.html

Рекурсивное использование diff3 рекурсивно для создания виртуальной ветки, которая будет использоваться как предок.

например:.

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

Тогда:

git checkout E
git merge F

Есть 2 лучших общих предка (общие предки, которые не являются предками других), C и D. git объединяет их в новую виртуальную ветвь V, а затем использует V в качестве базы.

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

Я предполагаю, что git будет просто продолжать с того, если бы были более лучшие общие предки, слияние V со следующей.

В статье говорится, что если есть конфликт слияния при создании виртуальной ветки git, просто оставлены маркеры конфликтов, где они есть, и продолжается.

Что происходит, когда я объединяю сразу несколько ветвей?

Как пояснил @Nevik Rehnel, это зависит от стратегии, это хорошо объяснено в разделе man git-merge MERGE STRATEGIES.

Только octopus и ours/theirs поддерживают объединение сразу нескольких ветвей, например, recursive.

octopus отказывается сливаться, если возникнут конфликты, а ours - тривиальное слияние, поэтому конфликтов не может быть.

Эти команды генерируют новую фиксацию, которая будет содержать более двух родителей.

Я сделал один merge -X octopus на git 1.8.5 без конфликтов, чтобы понять, как это происходит.

Исходное состояние:

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

Действие:

git checkout B
git merge -Xoctopus C D

Новое состояние:

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

Как и ожидалось, E имеет 3 родителя.

TODO: как именно осьминог работает с одним файлом. Рекурсивные двухфазные 3-сторонние слияния?

Как выполняется git, когда нет общей базы для объединения ветвей?

@Torek упоминает, что с 2.9 слияние происходит без --allow-unrelated-histories.

Я экспериментировал с эмпирически на 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 содержит:

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

Тогда:

git checkout --conflict=diff3 -- .

a содержит:

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

Интерпретация:

• база пуста
• когда база пуста, невозможно разрешить любую модификацию в одном файле; можно разрешить только такие вещи, как добавление нового файла. Вышеупомянутый конфликт будет решаться при трехстороннем слиянии с базой a\nc\n как однострочное дополнение
• Я думаю, что трехстороннее слияние без базового файла называется двухсторонним слиянием, которое представляет собой просто diff

Ответ 3

Мне тоже интересно. Я не знаю ответа, но...

Сложная система, которая работает, неизменно обнаруживается, что она эволюционировала от простой системы, которая работала

Я думаю, что слияние git очень сложное и будет очень трудно понять, но один из способов приблизиться к этому - от его предшественников и сосредоточиться на сердце вашей заботы. То есть, учитывая два файла, которые не имеют общего предка, как git merge работает, как слить их, и где конфликты?

Попробуйте найти некоторые прекурсоры. От 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 functionality which is needed by
       git(1).

Из 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

Эта последняя ссылка является pdf-документом, подробно описывающим алгоритм diff3. Здесь версия google pdf-viewer. Это всего лишь 12 страниц, а алгоритм - всего лишь на пару страниц - но полное математическое лечение. Это может показаться чересчур формальным, но если вы хотите понять слияние git, сначала вам нужно понять более простую версию. Я еще не проверил, но с таким именем, как diff3, вам, вероятно, также понадобится понять diff (в котором используется самая длинная общая подпоследовательность). Однако там может быть более интуитивное объяснение diff3, если у вас есть Google...

Теперь я просто провел эксперимент, сравнивающий diff3 и git merge-file. Они берут те же три входных файла version1 oldversion version2 и отмечают конфликты так же, с <<<<<<< version1, =======, >>>>>>> version2 (diff3 также имеет ||||||| oldversion), показывая их общее наследие.

Я использовал пустой файл для oldversion и почти идентичные файлы для версий1 и version2 с добавлением только одной дополнительной строки в версию 2.

Результат: git merge-file идентифицировал одну измененную строку как конфликт; но diff3 обрабатывал все два файла как конфликт. Таким образом, сложный, как diff3, слияние git еще более сложный, даже для этого простейшего случая.

Здесь фактические результаты (я использовал @twalberg ответ для текста). Обратите внимание на необходимые параметры (см. Соответствующие manpages).

$ 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 not deep enough,
there 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 not deep enough,
there 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 not deep enough,
there always source code...
>>>>>>> fun2.txt

Если вы действительно заинтересованы в этом, это немного кроличьей дыры. Для меня это кажется столь же глубоким, как регулярные выражения, самый длинный общий алгоритм подпоследовательности diff, контекстно-свободные грамматики или реляционная алгебра. Если вы хотите разобраться в этом, я думаю, вы можете, но это займет некоторое определенное исследование.

Ответ 4

Как git определить контекст конкретного несогласованного изменения?
Как git узнать, что в этих точках есть конфликт?

Если одна и та же строка изменилась с обеих сторон слияния, это конфликт; если они этого не сделали, изменение с одной стороны (если оно существует) принимается.

Что делает git авто-слияние?

Изменения, которые не конфликтуют (см. выше)

Как выполняется git, когда существует несколько общих оснований для объединения ветвей?

По определению Git merge-base существует только один (последний общий предок).

Что происходит, когда я объединяю сразу несколько ветвей?

Это зависит от стратегии слияния (только стратегии octopus и ours/theirs поддерживают объединение более двух ветвей).

В чем разница между стратегиями слияния?

Это объясняется в git merge manpage.

Ответ 5

Вот оригинальная реализация

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

В основном вы создаете список общих предков для двух коммитов, а затем рекурсивно объединяете их, либо быстро пересылаете их, либо создаете виртуальные коммиты, которые используются в основе трехстороннего слияния файлов.