Como o 'git merge' funciona nos detalhes?

Eu quero saber um algoritmo exato (ou perto disso) por trás do 'git merge'. As respostas, pelo menos a essas subquestões, serão úteis:

• Como o git detecta o contexto de uma mudança não conflitante em particular?
• Como o git descobre que há um conflito nessas linhas exatas?
• Quais coisas o git mescla automaticamente?
• Como o git funciona quando não há uma base comum para mesclar branches?
• Como o git funciona quando há várias bases comuns para mesclar branches?
• O que acontece quando mesclo várias ramificações de uma vez?
• Qual é a diferença entre estratégias de mesclagem?

Mas a descrição de todo um algoritmo será muito melhor.

Talvez seja melhor você procurar uma descrição de um algoritmo de mesclagem de 3 vias. Uma descrição de alto nível seria mais ou menos assim:

1. Encontre uma base de mesclagem adequada B- uma versão do arquivo que é ancestral de ambas as novas versões ( Xe Y), e geralmente a mais recente dessa base (embora haja casos em que terá que voltar mais longe, que é um dos os recursos de mesclagem gitpadrão recursive)
2. Execute diferenças de Xcom Be Ycom B.
3. Percorra os blocos de mudança identificados nas duas diferenças. Se ambos os lados introduzirem a mesma mudança no mesmo local, aceite qualquer um; se um introduz uma mudança e o outro deixa essa região em paz, introduza a mudança no final; se ambos introduzirem mudanças em um ponto, mas não corresponderem, marque um conflito para ser resolvido manualmente.

O algoritmo completo lida com isso com muito mais detalhes e ainda tem alguma documentação ( https://github.com/git/git/blob/master/Documentation/technical/trivial-merge.txt para um, junto com as git help XXXpáginas , onde XXX é um dos merge-base, merge-file, merge, merge-one-filee possivelmente alguns outros). Se isso não for profundo o suficiente, sempre há código-fonte ...

Como o git funciona quando há várias bases comuns para mesclar branches?

Este artigo foi muito útil: http://codicesoftware.blogspot.com/2011/09/merge-recursive-strategy.html (aqui está a parte 2 ).

Recursivo usa diff3 recursivamente para gerar uma ramificação virtual que será usada como ancestral.

Por exemplo:

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

Então:

git checkout E
git merge F

Existem 2 melhores ancestrais comuns (ancestrais comuns que não são ancestrais de nenhum outro) Ce D. O Git os mescla em um novo branch virtual Ve os usa Vcomo base.

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

Suponho que o Git apenas continuaria com o se houvesse mais ancestrais comuns melhores, se fundindo Vcom o próximo.

O artigo diz que se houver um conflito de mesclagem durante a geração do branch virtual, o Git apenas deixa os marcadores de conflito onde estão e continua.

O que acontece quando mesclo várias ramificações de uma vez?

Como @Nevik Rehnel explicou, depende da estratégia, está bem explicado na man git-merge MERGE STRATEGIESseção.

Apenas octopuse ours/ theirssuporta mesclar vários ramos de uma vez, recursivepor exemplo, não.

octopusrecusa-se a mesclar se houver conflitos, e oursé uma mesclagem trivial, portanto não pode haver conflitos.

Esses comandos geram um novo commit que terá mais de 2 pais.

Eu fiz um merge -X octopusno Git 1.8.5 sem conflitos para ver como funciona.

Estado inicial:

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

Açao:

git checkout B
git merge -Xoctopus C D

Novo estado:

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

Como esperado, Etem 3 pais.

TODO: exatamente como o polvo opera em modificações de um único arquivo. Mesclagens de três vias recursivas dois por dois?

Como o git funciona quando não há uma base comum para mesclar branches?

@Torek menciona que desde o 2.9, a mesclagem falha sem --allow-unrelated-histories.

Eu tentei empiricamente no 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 contém:

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

Então:

git checkout --conflict=diff3 -- .

a contém:

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

Interpretação:

• a base está vazia
• quando a base está vazia, não é possível resolver nenhuma modificação em um único arquivo; apenas coisas como a adição de um novo arquivo podem ser resolvidas. O conflito acima seria resolvido em uma fusão de 3 vias com base a\nc\ncomo uma adição de linha única
• Eu acho que uma mesclagem de 3 vias sem um arquivo de base é chamada de mesclagem de 2 vias, que é apenas uma diferença

Também estou interessado. Não sei a resposta, mas ...

Um sistema complexo que funciona invariavelmente evoluiu a partir de um sistema simples que funcionou

Acho que a fusão do git é altamente sofisticada e será muito difícil de entender - mas uma maneira de abordar isso é partindo de seus precursores e focar no centro de sua preocupação. Ou seja, dados dois arquivos que não têm um ancestral comum, como git merge funciona como mesclá-los e onde estão os conflitos?

Vamos tentar encontrar alguns precursores. De 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).

Da 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

O último link é um pdf de um artigo que descreve o diff3algoritmo em detalhes. Aqui está uma versão do visualizador de pdf do google . Tem apenas 12 páginas, e o algoritmo tem apenas algumas páginas - mas um tratamento matemático completo. Isso pode parecer um pouco formal, mas se você quiser entender o merge do git, você precisará entender a versão mais simples primeiro. Eu não verifiquei ainda, mas com um nome como diff3, você provavelmente também precisará entender diff (que usa um algoritmo de subsequência comum mais longo ). No entanto, pode haver uma explicação mais intuitiva do que está diff3por aí, se você tiver um google ...

Agora, acabei de fazer uma experiência comparando diff3e git merge-file. Eles tomam os mesmos três arquivos de entrada version1 OldVersion version2 e conflitos marcam o caminho mesma, com <<<<<<< version1, =======, >>>>>>> version2( diff3também tem ||||||| oldversion), mostrando o seu património comum.

Eu usei um arquivo vazio para OldVersion e arquivos quase idênticas para version1 e version2 com apenas uma linha extra adicionado ao version2 .

Resultado: git merge-fileidentificou a única linha alterada como o conflito; mas diff3tratou os dois arquivos inteiros como um conflito. Portanto, por mais sofisticado que o diff3 seja, o merge do git é ainda mais sofisticado, mesmo para os casos mais simples.

Aqui estão os resultados reais (usei a resposta de @twalberg para o texto). Observe as opções necessárias (consulte as respectivas páginas de manual).

$ 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

Se você estiver realmente interessado nisso, é uma espécie de toca de coelho. Para mim, parece tão profundo quanto expressões regulares, o algoritmo de subsequência comum mais longo de diff, gramáticas livres de contexto ou álgebra relacional. Se você quiser chegar ao fundo disso, acho que pode, mas vai exigir um estudo determinado.

Aqui está a implementação original

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

Basicamente, você cria uma lista de ancestrais comuns para dois commits e então os mescla recursivamente, seja avançando rapidamente ou criando commits virtuais que são usados ​​como base para uma mesclagem de três vias nos arquivos.

Como o git detecta o contexto de uma mudança não conflitante em particular?
Como o git descobre que há um conflito nessas linhas exatas?

Se a mesma linha mudou em ambos os lados da fusão, é um conflito; se não o fizeram, a mudança de um lado (se existente) é aceita.

Quais coisas o git mescla automaticamente?

Mudanças que não entram em conflito (veja acima)

Como o git funciona quando há várias bases comuns para mesclar branches?

Pela definição de uma base de mesclagem Git , existe apenas um (o último ancestral comum).

O que acontece quando mesclo várias ramificações de uma vez?

Isso depende da estratégia de fusão (apenas as estratégias octopuse ours/ theirssuportam a fusão de mais de dois ramos).

Qual é a diferença entre estratégias de mesclagem?

Isso é explicado na página de git mergemanual .