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

git ver archivos modificados

Question

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 particular no conflictivo?
• ¿Cómo descubre git que hay un conflicto en estas líneas exactas?
• ¿Qué cosas git auto-fusiona?
• ¿Cómo funciona git cuando no hay una base común para fusionar ramas?
• ¿Cómo se realiza 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 un algoritmo completo será mucho mejor.

Answer 1

¿Cómo detecta git el contexto de un cambio particular no conflictivo?
¿Cómo descubre 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 git auto-fusiona?

Cambios que no entren en conflicto (ver arriba)

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

Por la definición de una base de Git , solo hay uno (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 las estrategias ours / theirs apoyan 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 merge .

Answer 2

Aquí está la implementación original.

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

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

Answer 3

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 fusión B adecuada: una versión del archivo que es un antecesor de las dos nuevas versiones ( X e Y ) y, por lo general, la base más reciente (aunque hay casos en los que tendrá que volver más lejos, lo cual es una de las características de la combinación recursive defecto de git )
2. Realiza diferencias de X con B e Y con B
3. Camina a través de los bloques de cambio identificados en las dos diferencias. Si ambos lados introducen el mismo cambio en el mismo lugar, acepte uno de los dos; si uno introduce un cambio y el otro deja solo esa región, 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 trata esto con mucho más detalle, e incluso tiene algo de documentación ( /usr/share/doc/git-doc/technical/trivial-merge.txt para uno, junto con las páginas git help XXX , donde XXX es uno de merge-base , merge-file , merge , merge-one-file y posiblemente algunos otros). Si eso no es lo suficientemente profundo, siempre hay un código fuente ...

Answer 4

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

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

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

Tratemos de encontrar algunos precursores. Desde 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

El último enlace es un pdf de un artículo que describe en detalle el algoritmo diff3 . Aquí hay una versión de google pdf-viewer . Solo tiene 12 páginas, y el algoritmo es solo un par de páginas, pero es un tratamiento matemático completo. Esto puede parecer un poco demasiado formal, pero si quieres entender la combinación de git, primero deberás entender la versión más simple. No lo he comprobado todavía, pero con un nombre como diff3 , probablemente también necesitará entender diff (que utiliza un algoritmo de subsecuencias comunes más largo ). Sin embargo, puede haber una explicación más intuitiva de diff3 , si tienes un Google ...

Ahora, acabo de hacer un experimento comparando diff3 y git merge-file . Toman los mismos tres archivos de entrada version1 oldversion version2 y marcan los conflictos de la misma manera, con <<<<<<< version1 , ======= , >>>>>>> version2 diff3 ( diff3 también tiene ||||||| oldversion ), mostrando su patrimonio común.

Utilicé un archivo vacío para la versión anterior , y archivos casi idénticos para la versión 1 y la versión 2 con solo una línea adicional agregada a la versión 2 .

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

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

$ 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ás realmente interesado en esto, es un poco como un agujero de conejo. Para mí, parece tan profundo como las expresiones regulares, el algoritmo de subsecuencia común más largo de diff, gramáticas sin contexto o álgebra relacional. Si quieres llegar al fondo de la misma, creo que puedes, pero se necesitará un estudio determinado.

Answer 5

¿Cómo se realiza 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 ).

Recursivo utiliza diff3 recursivamente para generar una rama virtual que se utilizará como antecesor.

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), C y D Git los fusiona en una nueva rama virtual V y luego usa V como base.

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

Supongo que Git simplemente continuaría con el caso de que hubiera más ancestros comunes, combinando V con el siguiente.

El artículo dice que si hay un conflicto de fusión al generar 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 lo explicó @Nevik Rehnel, depende de la estrategia, está bien explicado en la sección de MERGE STRATEGIES man git-merge .

Solo el octopus y el ours / theirs admiten la fusión de varias ramas a la vez, recursive , por ejemplo, no lo hace.

octopus niega a fusionarse si hubiera conflictos, y el ours es una combinación trivial por lo que no puede haber conflictos.

Esos comandos generan una nueva confirmación que tendrá más de 2 padres.

Hice una merge -X octopus en 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, E tiene 3 padres.

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

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

@Torek menciona que, desde la versión 2.9, la fusión falla sin las --allow-unrelated-histories no --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 vacía
• cuando la base está vacía, no es posible resolver ninguna modificación en un solo archivo; Sólo cosas como la adición de nuevos archivos pueden ser resueltos. El conflicto anterior se resolvería en una combinación de 3 vías con base a/nc/n como una sola línea adicional
• Creo que una fusión de 3 vías sin un archivo base se llama una fusión de 2 vías, que es solo una diferencia