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

Я хочу знать точный алгоритм (или близкий к нему), стоящий за «git merge». По крайней мере, ответы на эти подвопросы будут полезны:

• Как git определяет контекст конкретного неконфликтного изменения?
• Как git обнаруживает конфликт именно в этих строках?
• Что делает git auto-merge?
• Как работает git, когда нет общей базы для слияния веток?
• Как работает git, когда есть несколько общих баз для слияния веток?
• Что произойдет, если я объединю сразу несколько веток?
• В чем разница между стратегиями слияния?

Но описание всего алгоритма будет намного лучше.

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

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

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

Как работает git, когда есть несколько общих баз для слияния веток?

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

Рекурсивный рекурсивно использует 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: как именно осьминог работает с модификациями одного файла. Рекурсивное двухстороннее трехстороннее слияние?

Как работает 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 как добавление одной строки.
• Я думаю, что трехстороннее слияние без базового файла называется двухсторонним слиянием, которое представляет собой просто разницу

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

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

Я думаю, что слияние 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's functionality which is needed by
       git(1).

Из википедии: 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 , а также файлы почти одинаковые для version1 и version2 с добавлением только одна дополнительная линия Version2 .

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

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

$ 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

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

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

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

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

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

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

Что делает git auto-merge?

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

Как работает git, когда есть несколько общих баз для слияния веток?

По определению базы слияния Git существует только один (последний общий предок).

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

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

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

Это объясняется на git mergeстранице руководства .