¿Cómo funciona 'git merge' en detalles?

Quiero saber un algoritmo exacto (o cerca de eso) detrás de 'git merge'. Las respuestas al menos a estas subpreguntas serán útiles:

• ¿Cómo detecta git el contexto de un cambio no conflictivo en particular?
• ¿Cómo descubre git que hay un conflicto en estas líneas exactas?
• ¿Qué cosas se fusionan automáticamente con git?
• ¿Cómo funciona git cuando no hay una base común para fusionar ramas?
• ¿Cómo funciona git cuando hay varias bases comunes para fusionar ramas?
• ¿Qué sucede cuando fusiono varias ramas a la vez?
• ¿Cuál es la diferencia entre las estrategias de fusión?

Pero la descripción de todo un algoritmo será mucho mejor.

Puede que sea mejor que busque una descripción de un algoritmo de combinación de 3 vías. Una descripción de alto nivel sería algo como esto:

1. Encuentre una base de combinación adecuada B: una versión del archivo que sea un ancestro de las dos nuevas versiones ( Xy Y), y generalmente la base más reciente (aunque hay casos en los que tendrá que retroceder más, que es uno de los las características de gitla recursivecombinación predeterminada de s )
2. Realiza diferencias de Xcon By Ycon B.
3. Camine por los bloques de cambio identificados en las dos diferencias. Si ambos lados introducen el mismo cambio en el mismo lugar, acepte cualquiera de ellos; si uno introduce un cambio y el otro deja esa región sola, introduzca el cambio en la final; si ambos introducen cambios en un lugar, pero no coinciden, marque un conflicto para resolverlo manualmente.

El algoritmo completo se ocupa de esto con mucho más detalle e incluso tiene algo de documentación ( https://github.com/git/git/blob/master/Documentation/technical/trivial-merge.txt para uno, junto con las git help XXXpáginas , donde XXX es uno de merge-base, merge-file, merge, merge-one-filey posiblemente algunos otros). Si eso no es lo suficientemente profundo, siempre hay código fuente ...

¿Cómo funciona git cuando hay varias bases comunes para fusionar ramas?

Este artículo fue muy útil: http://codicesoftware.blogspot.com/2011/09/merge-recursive-strategy.html (aquí está la parte 2 ).

Recursive usa diff3 de manera recursiva para generar una rama virtual que se usará como ancestro.

P.ej:

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

Entonces:

git checkout E
git merge F

Hay 2 mejores ancestros comunes (ancestros comunes que no son ancestros de ningún otro) Cy D. Git los fusiona en una nueva rama virtual Vy luego los usa Vcomo base.

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

Supongo que Git simplemente continuaría con el si hubiera más mejores ancestros comunes, fusionándose Vcon el siguiente.

El artículo dice que si hay un conflicto de fusión mientras se genera la rama virtual, Git simplemente deja los marcadores de conflicto donde están y continúa.

¿Qué sucede cuando fusiono varias ramas a la vez?

Como explicó @Nevik Rehnel, depende de la estrategia, está bien explicado en la man git-merge MERGE STRATEGIESsección.

Solo octopusy ours/ theirsadmite la fusión de varias ramas a la vez, recursivepor ejemplo, no.

octopusse niega a fusionarse si hubiera conflictos, y ourses una fusión trivial para que no pueda haber conflictos.

Esos comandos que generan un nuevo compromiso tendrán más de 2 padres.

Hice uno merge -X octopusen Git 1.8.5 sin conflictos para ver cómo va.

Estado inicial:

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

Acción:

git checkout B
git merge -Xoctopus C D

Nuevo estado:

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

Como era de esperar, Etiene 3 padres.

TODO: cómo funciona exactamente octopus en las modificaciones de un solo archivo. ¿Fusiones recursivas de dos por dos de 3 vías?

¿Cómo funciona git cuando no hay una base común para fusionar ramas?

@Torek menciona que desde 2.9, la fusión falla sin --allow-unrelated-histories.

Lo probé empíricamente en 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 contiene:

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

Entonces:

git checkout --conflict=diff3 -- .

a contiene:

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

Interpretación:

• la base esta vacia
• cuando la base está vacía, no es posible resolver ninguna modificación en un solo archivo; solo se pueden resolver cosas como la adición de nuevos archivos. El conflicto anterior se resolvería en una combinación de 3 vías con la base a\nc\ncomo una adición de una sola línea
• Yo creo que una combinación de 3 vías sin un archivo de base se denomina una combinación de 2 vías, que es sólo un diff

Yo también estoy interesado. No sé la respuesta, pero ...

Un sistema complejo que funciona invariablemente ha evolucionado a partir de un sistema simple que funcionó

Creo que la fusión de git es muy sofisticada y será muy difícil de entender, pero una forma de abordar esto es a partir de sus precursores y centrarse en el corazón de su preocupación. Es decir, dados dos archivos que no tienen un ancestro común, ¿cómo resuelve git merge cómo fusionarlos y dónde están los conflictos?

Intentemos encontrar algunos 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).

De 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

Ese último enlace es un pdf de un artículo que describe el diff3algoritmo en detalle. Aquí hay una versión del visor de pdf de Google . Tiene solo 12 páginas y el algoritmo tiene solo un par de páginas, pero un tratamiento matemático completo. Eso puede parecer un poco demasiado formal, pero si desea comprender la fusión de git, primero deberá comprender la versión más simple. Aún no lo he comprobado, pero con un nombre como diff3, probablemente también necesitará comprender diff (que usa un algoritmo de subsecuencia común más largo ). Sin embargo, puede haber una explicación más intuitiva de diff3ahí fuera, si tiene un google ...

Ahora, acabo de hacer un experimento comparando diff3y git merge-file. Se llevan a los mismos tres archivos de entrada version1 OldVersion version2 y conflictos marcan el camino mismo, con <<<<<<< version1, =======, >>>>>>> version2( diff3también tiene ||||||| oldversion), mostrando su patrimonio común.

He utilizado un archivo vacío para OldVersion y archivos casi idénticos para version1 y version2 con una sola línea extra añadido a version2 .

Resultado: git merge-fileidentificó la única línea modificada como el conflicto; pero diff3trató los dos archivos completos como un conflicto. Por lo tanto, por más sofisticada que sea diff3, la fusión de git es aún más sofisticada, incluso para el caso más simple.

Aquí están los resultados reales (utilicé la respuesta de @ twalberg para el texto). Tenga en cuenta las opciones necesarias (consulte las páginas de manual correspondientes).

$ 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

Si está realmente interesado en esto, es una especie de madriguera. Para mí, parece tan profundo como las expresiones regulares, el algoritmo de subsecuencia común más largo de diff, gramáticas libres de contexto o álgebra relacional. Si quiere llegar al fondo, creo que puede, pero requerirá un estudio decidido.

Aquí está la implementación original

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

Básicamente, crea una lista de ancestros comunes para dos confirmaciones y luego los combina de forma recursiva, ya sea adelantándolos rápidamente o creando confirmaciones virtuales que se utilizan para la base de una combinación de tres vías en los archivos.

¿Cómo detecta git el contexto de un cambio no conflictivo en particular?
¿Cómo averigua git que hay un conflicto en estas líneas exactas?

Si la misma línea ha cambiado en ambos lados de la fusión, es un conflicto; si no lo han hecho, se acepta el cambio de un lado (si existe).

¿Qué cosas se fusionan automáticamente con git?

Cambios que no entran en conflicto (ver arriba)

¿Cómo funciona git cuando hay varias bases comunes para fusionar ramas?

Según la definición de una base de fusión de Git , solo hay una (el último ancestro común).

¿Qué sucede cuando fusiono varias ramas a la vez?

Eso depende de la estrategia de fusión (solo el octopus y ours/ theirsadmiten la fusión de más de dos ramas).

¿Cuál es la diferencia entre las estrategias de fusión?

Esto se explica en la página de git mergemanual .