¿Cómo funciona ‘git merge’ en detalles?

Quiero saber un algoritmo exacto (o cercano) 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 se auto fusionan?
  • ¿Cómo funciona git cuando no hay una base común para fusionar sucursales?
  • ¿Cómo funciona git cuando hay múltiples bases comunes para fusionar sucursales?
  • ¿Qué sucede cuando fusiono varias twigs 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.

Es mejor que busques 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 B adecuada: una versión del archivo que es un antecesor de las dos versiones nuevas ( X e Y ) y, por lo general, la base más reciente (aunque hay casos en los que tendrá que retroceder más, que es una de las características de la fusión recursive predeterminada de git )
  2. Realice diffs 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; si uno introduce un cambio y el otro abandona esa región solo, introduzca el cambio en el final; si ambos introducen cambios en un punto, pero no coinciden, marque un conflicto para resolverlo manualmente.

El algoritmo completo trata esto con mucho más detalle, e incluso tiene alguna documentación ( /usr/share/doc/git-doc/technical/trivial-merge.txt para uno, junto con la git help XXX páginas, 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 …

¿Cómo funciona git cuando hay múltiples bases comunes para fusionar sucursales?

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

Recursive usa diff3 recursivamente para generar una twig virtual que se usará como ancestro.

P.ej:

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

Entonces:

 git checkout E git merge F 

Hay dos mejores antepasados ​​comunes (ancestros comunes que no son antepasados ​​de ningún otro), C y D Git los fusiona en una nueva twig virtual V , y luego usa V como base.

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

Supongo que Git continuaría con el si hubiese más antepasados ​​comunes, fusionando V con el siguiente.

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

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

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

Solo el octopus y el ours soportan la fusión de múltiples twigs a la vez, recursive por ejemplo no.

octopus niega a fusionarse si hubiera conflictos, y el ours es una fusión trivial para que no haya conflictos.

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

Hice una merge -X octopus en Git 1.8.5 sin conflictos para ver cómo funciona.

Estado inicial:

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

Acción:

 git checkout B git merge -Xoctopus CD 

Nuevo estado:

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

Como se esperaba, E tiene 3 padres.

TODO: cómo funciona el pulpo en las modificaciones de un solo archivo. ¿Fusiones recíprocas de dos vías de dos en dos?

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

@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 -ma git checkout --orphan b printf 'a\nb\nc\n' > a git add . git commit -mb 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 está vacía
  • 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 archivos nuevos. El conflicto anterior se resolvería en una fusión de 3 vías con la 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 combinación de dos vías, que es solo una diferencia

Estoy interesado también 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 muy sofisticada y será muy difícil de entender, pero una forma de abordar esto es desde 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 funciona la fusión de git para encontrar la manera de fusionarlos y dónde están los conflictos?

Tratemos de encontrar algunos precursores. Desde la 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 la 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 documento que describe el algoritmo diff3 en detalle. Aquí hay una versión de google pdf-viewer . Solo tiene 12 páginas, y el algoritmo solo tiene un par de páginas, pero tiene un tratamiento matemático completo. Eso puede parecer demasiado formal, pero si quieres entender la fusión de git, primero tendrás que entender la versión más simple. Todavía no lo he comprobado, pero con un nombre como diff3 , probablemente también necesites entender diff (que usa un algoritmo de subsecuencia común 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 version antigua version2 y marcan conflictos del mismo modo, con <<<<<<< version1 , ======= , >>>>>>> version2 diff3 ( diff3 tambien tiene

| oldversion ), mostrando su herencia común.

Usé 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 cambiada como el conflicto; pero diff3 trató los dos archivos completos como un conflicto. Por lo tanto, sofisticado como diff3 es, la fusión de git es aún más sofisticado, 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 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 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 libres de contexto o álgebra relacional. Si quiere llegar al fondo del asunto, creo que puede hacerlo, pero llevará algún estudio determinado.

¿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 se auto fusionan?

Cambios que no entran en conflicto (ver arriba)

¿Cómo funciona git cuando hay múltiples bases comunes para fusionar sucursales?

Según la definición de una base de fusión de Git , solo hay una (el antepasado común más reciente).

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

Eso depende de la estrategia de combinación (solo las estrategias de octopus y de ours / theirs estrategias permiten fusionar más de dos twigs).

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

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

Aquí está la implementación original

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

Básicamente, usted crea una lista de ancestros comunes para dos confirmaciones y luego los fusiona de forma recursiva, ya sea reenviándolos rápidamente o creando compromisos virtuales que se utilizan como base de una combinación tripartita en los archivos.

    Intereting Posts