En el control de versiones , la fusión (también llamada integración) es una operación fundamental que concilia múltiples cambios realizados en una colección de archivos controlada por la versión. En la mayoría de los casos, es necesario cuando un archivo se modifica en dos ramas independientes y posteriormente se fusiona. El resultado es una única colección de archivos que contiene ambos conjuntos de cambios.
En algunos casos, la combinación se puede realizar automáticamente, porque hay suficiente información histórica para reconstruir los cambios y los cambios no entran en conflicto . En otros casos, una persona debe decidir exactamente qué deben contener los archivos resultantes. Muchas herramientas de software de control de revisiones incluyen capacidades de fusión.
Hay dos tipos de fusiones: no estructuradas y estructuradas.
La combinación no estructurada opera en texto sin formato, generalmente usando líneas de texto como unidades atómicas. Esto es lo que utilizan las herramientas Unix (diff/patch) y CVS (SVN, Git). Esto es limitado, ya que una línea de texto no representa la estructura del código fuente.
Las herramientas de combinación estructurada, o combinación AST, convierten el código fuente en un AST completamente resuelto . Esto permite una fusión detallada que evita conflictos espurios.
La fusión automática es lo que hace el software de control de versiones cuando concilia cambios que han ocurrido simultáneamente (en un sentido lógico). Además, otras piezas de software implementan la fusión automática si permiten editar el mismo contenido simultáneamente. Por ejemplo, Wikipedia permite que dos personas editen el mismo artículo al mismo tiempo; cuando el último colaborador guarda, sus cambios se fusionan en el artículo en lugar de sobrescribir el conjunto de cambios anterior. [1] La fusión manual es a lo que las personas tienen que recurrir (posiblemente con la ayuda de herramientas de fusión) cuando tienen que conciliar archivos que difieren. Por ejemplo, si dos sistemas tienen versiones ligeramente diferentes de un archivo de configuración y un usuario quiere tener las cosas buenas en ambos, esto generalmente se puede lograr fusionando los archivos de configuración a mano, seleccionando los cambios deseados de ambas fuentes (esto también es llamada fusión bidireccional). La combinación manual también es necesaria cuando la combinación automática genera un conflicto de cambios; por ejemplo, muy pocas herramientas de combinación automática pueden combinar dos cambios en la misma línea de código (por ejemplo, una que cambia el nombre de una función y otra que agrega un comentario). En estos casos, los sistemas de control de revisiones recurren al usuario para especificar el resultado de la fusión previsto.
Existen muchos enfoques diferentes para la fusión automática, con diferencias sutiles. Los algoritmos de fusión más notables incluyen fusión de tres vías, fusión recursiva de tres vías, aplicación de parche difuso, fusión de tejido y conmutación de parche.
Una fusión de tres vías se realiza después de un análisis de diferencia automatizado entre un archivo "A" y un archivo "B", considerando también el origen, o ancestro común, de ambos archivos "C". Es un método de fusión aproximado, pero ampliamente aplicable ya que sólo requiere un ancestro común para reconstruir los cambios que se van a fusionar. La combinación de tres vías se puede realizar en texto sin formato (secuencia de líneas) o en árboles estructurados. [2]
La combinación de tres vías busca secciones que sean iguales sólo en dos de los tres archivos. En este caso, hay dos versiones de la sección y la versión que está en el ancestro común "C" se descarta, mientras que la versión que difiere se conserva en la salida. Si "A" y "B" están de acuerdo, eso es lo que aparece en el resultado. Una sección que es igual en "A" y "C" genera la versión modificada en "B" y, de la misma manera, una sección que es igual en "B" y "C" genera la versión en "A".
Las secciones que son diferentes en los tres archivos se marcan como una situación de conflicto y se dejan para que el usuario las resuelva.
La fusión de tres vías se implementa mediante el omnipresente programa diff3 y fue la innovación central que permitió el cambio de sistemas de control de revisiones basados en bloqueo de archivos a sistemas de control de revisiones basados en fusión. Es ampliamente utilizado por el Sistema de Versiones Concurrentes (CVS).
Las herramientas de control de revisiones basadas en fusiones de tres vías están muy extendidas, pero la técnica depende fundamentalmente de encontrar un ancestro común de las versiones que se van a fusionar.
Hay casos incómodos, particularmente la "fusión entrecruzada", [3] donde no existe un último ancestro común único de las versiones modificadas.
Afortunadamente, en este caso se puede demostrar que hay como máximo dos posibles ancestros candidatos, y la fusión recursiva de tres vías construye un ancestro virtual fusionando primero los ancestros no únicos. Esta fusión puede sufrir el mismo problema, por lo que el algoritmo los fusiona de forma recursiva . Dado que hay un número finito de versiones en el historial, se garantiza que el proceso terminará eventualmente. Esta técnica es utilizada por la herramienta de control de revisiones Git .
(La implementación de combinación recursiva de Git también maneja otros casos incómodos, como un archivo que se modifica en una versión y se renombra en la otra, pero esas son extensiones de su implementación de combinación de tres vías; no forman parte de la técnica para encontrar tres versiones para fusionar).
La fusión recursiva de tres vías solo se puede utilizar en situaciones en las que la herramienta tiene conocimiento sobre el gráfico acíclico dirigido por ascendencia total (DAG) de las derivadas que se van a fusionar. En consecuencia, no se puede utilizar en situaciones en las que los derivados o fusiones no especifican completamente a sus matrices.
Un parche es un archivo que contiene una descripción de los cambios realizados en un archivo. En el mundo Unix, existe la tradición de difundir cambios en archivos de texto como parches en el formato producido por " diff -u". Luego, el programa de parche puede utilizar este formato para volver a aplicar (o eliminar) los cambios en (o desde) un archivo de texto o una estructura de directorio que contenga archivos de texto.
Sin embargo, el programa de parche también tiene algunas funciones para aplicar el parche en un archivo que no es exactamente similar al archivo original que se utilizó para producir el parche. Este proceso se llama aplicación de parche difuso y da como resultado una especie de fusión asimétrica de tres vías, donde los cambios en el parche se descartan si el programa de parche no puede encontrar un lugar donde aplicarlos.
Así como CVS comenzó como un conjunto de scripts en diff3 , GNU arch comenzó como un conjunto de scripts en patch. Sin embargo, la aplicación de parches difusos es un método relativamente poco confiable, ya que a veces aplica mal parches que tienen muy poco contexto (especialmente aquellos que crean un archivo nuevo) y a veces se niega a aplicar eliminaciones que ambos derivados han realizado.
La conmutación de parches se usa en Darcs para fusionar cambios y también se implementa en git (pero se llama "rebase"). La fusión de conmutación de parches significa cambiar el orden de los parches (es decir, las descripciones de los cambios) para que formen una historia lineal. En efecto, cuando dos parches se crean en el contexto de una situación común, al fusionarse, uno de ellos se reescribe para que parezca hecho en el contexto del otro.
La conmutación de parches requiere que los cambios exactos que realizaron los archivos derivados se almacenen o puedan reconstruirse. A partir de estos cambios exactos es posible calcular cómo se debe cambiar uno de ellos para cambiar la base del otro. Por ejemplo, si el parche A agrega la línea "X" después de la línea 7 del archivo F y el parche B agrega la línea "Y" después de la línea 310 del archivo F, B debe reescribirse si se basa en A: la línea debe agregarse en línea 311 del archivo F, porque la línea agregada en A compensa los números de línea en uno.
La conmutación de parches se ha estudiado mucho formalmente, pero los algoritmos para abordar los conflictos de fusión en la conmutación de parches aún siguen siendo cuestiones de investigación abiertas. Sin embargo, se puede demostrar que la conmutación de parches produce resultados de fusión "correctos" [ cita necesaria ] donde otras estrategias de fusión son en su mayoría heurísticas que intentan producir lo que los usuarios quieren ver.
El programa Unix flipdiffdel paquete "patchutils" implementa la conmutación de parches para los parches tradicionales producidos por diff -u.
Weave merge es un algoritmo que no utiliza un ancestro común para dos archivos. En cambio, rastrea cómo se agregan y eliminan líneas individuales en versiones derivadas de archivos y produce el archivo combinado con esta información.
Para cada línea de los archivos derivados, weave merge recopila la siguiente información: qué líneas la preceden, cuáles la siguen y si se eliminó en algún momento del historial de cualquiera de los derivados. Si a cualquiera de los derivados se le ha eliminado la línea en algún momento, no debe estar presente en la versión fusionada. Para otras líneas, deben estar presentes en la versión fusionada.
Las líneas se clasifican en un orden en el que cada línea aparece después de todas las líneas que la precedieron en algún momento de la historia y antes de todas las líneas que la siguieron en algún momento de la historia. Si estas restricciones no dan un orden total para todas las líneas, entonces las líneas que no tienen un orden entre sí son adiciones que entran en conflicto.
La combinación de tejido aparentemente fue utilizada por la herramienta comercial de control de revisiones BitKeeper y puede manejar algunos de los casos problemáticos en los que una combinación de tres vías produce resultados incorrectos o malos. También es una de las opciones de combinación de la herramienta de control de revisiones GNU Bazaar y se utiliza en Codeville. [ cita necesaria ]
