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 versiones. La mayoría de las veces, es necesaria cuando se modifica un archivo en dos ramas independientes y luego se fusiona. El resultado es una única colección de archivos que contiene ambos conjuntos de cambios.
En algunos casos, la fusión se puede realizar automáticamente, porque hay suficiente información histórica para reconstruir los cambios y estos 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 revisión incluyen funciones de fusión.
Hay dos tipos de fusiones: no estructuradas y estructuradas.
La fusión no estructurada opera sobre texto sin formato, generalmente utilizando líneas de texto como unidades atómicas. Esto es lo que utilizan las herramientas Unix (diff/patch) y las herramientas CVS (SVN, Git). Esto es limitado [ opinión ] , ya que una línea de texto no representa la estructura del código fuente.
Las herramientas de fusión estructurada, o fusión AST, convierten el código fuente en un AST completamente resuelto . Esto permite una fusión de grano fino que evita conflictos espurios. [ cita requerida ]
La fusión automática es lo que hace el software de control de versiones cuando concilia los cambios que han ocurrido simultáneamente (en un sentido lógico). Además, otros programas 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 anterior de cambios. [1] La fusión manual es a lo que las personas tienen que recurrir (posiblemente asistidas por 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 lo bueno en ambos, esto generalmente se puede lograr fusionando los archivos de configuración a mano y eligiendo los cambios deseados de ambas fuentes (esto también se llama fusión bidireccional). La fusión manual también es necesaria cuando la fusión automática se topa con un conflicto de cambios; Por ejemplo, muy pocas herramientas de fusión automática pueden fusionar dos cambios en la misma línea de código (por ejemplo, uno que cambia el nombre de una función y otro que agrega un comentario). En estos casos, los sistemas de control de revisión recurren al usuario para especificar el resultado de la fusión deseado.
Existen muchos enfoques diferentes para la fusión automática, con diferencias sutiles. Los algoritmos de fusión más notables incluyen la fusión de tres vías, la fusión recursiva de tres vías, la aplicación de parches difusos, la fusión de trama y la conmutación de parches.
Una fusión de tres vías se realiza después de un análisis automático de diferencias entre un archivo "A" y un archivo "B", teniendo en cuenta también el origen, o ancestro común, de ambos archivos "C". Es un método de fusión aproximado, pero de amplia aplicación, ya que solo requiere un ancestro común para reconstruir los cambios que se van a fusionar. La fusión de tres vías se puede realizar en texto sin formato (secuencia de líneas) o en árboles estructurados. [2]
La fusión de tres vías busca secciones que sean iguales en solo dos de los tres archivos. En este caso, hay dos versiones de la sección y la versión que está en el antecesor común "C" se descarta, mientras que la versión que difiere se conserva en la salida. Si "A" y "B" coinciden, eso es lo que aparece en la salida. Una sección que es la misma en "A" y "C" genera la versión modificada en "B", y, de la misma manera, una sección que es la misma 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 los sistemas de control de revisión basados en bloqueo de archivos a los sistemas de control de revisión basados en fusión. El sistema de versiones concurrentes (CVS) lo utiliza ampliamente .
Las herramientas de control de revisión basadas en la fusión 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 extraños, en particular la "fusión entrecruzada", [3] donde no existe un único ancestro común final de las versiones modificadas.
Afortunadamente, en este caso se puede demostrar que hay como máximo dos posibles ancestros candidatos, y la combinación recursiva de tres vías construye un ancestro virtual fusionando primero los ancestros no únicos. Esta combinació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á en algún momento. Esta técnica la utiliza la herramienta de control de versiones de Git .
(La implementación de fusión recursiva de Git también maneja otros casos complicados, 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 fusión de tres vías; no 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 la ascendencia total del grafo acíclico dirigido (DAG) de los derivados que se fusionarán. En consecuencia, no se puede utilizar en situaciones en las que los derivados o las fusiones no especifican completamente sus padres.
Un parche es un archivo que contiene una descripción de los cambios realizados en un archivo. En el mundo Unix, ha existido la tradición de difundir los cambios en los archivos de texto como parches en el formato que se produce con " diff -u". Este formato puede ser utilizado por el programa de parches 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 parches también tiene algunas funciones para aplicar el parche en un archivo que no es exactamente similar al archivo de origen que se utilizó para producir el parche. Este proceso se denomina aplicación de parches difusos 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 parches no puede encontrar un lugar en el que 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, que a veces aplica incorrectamente parches que tienen muy poco contexto (especialmente los que crean un nuevo archivo) y a veces se niega a aplicar eliminaciones que ambos derivados han realizado.
La conmutación de parches se utiliza en Darcs para fusionar cambios, y también se implementa en Git (pero se denomina "rebase"). La fusión de parches mediante conmutación de parches implica cambiar el orden de los parches (es decir, las descripciones de los cambios) para que formen un historial lineal. En efecto, cuando se realizan dos parches en el contexto de una situación común, al fusionarlos, uno de ellos se reescribe para que parezca que se realizó en el contexto del otro.
La conmutación de parches requiere que los cambios exactos que hicieron que los archivos derivados se almacenen o se puedan reconstruir. A partir de estos cambios exactos, es posible calcular cómo se debe cambiar uno de ellos para volver a basarlo en el 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 vuelve a basar en A: la línea debe agregarse en la línea 311 del archivo F, porque la línea agregada en A desplaza los números de línea en uno.
La conmutación de parches se ha estudiado mucho de manera formal, pero los algoritmos para tratar 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" [4], mientras que otras estrategias de fusión son principalmente 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.
La fusión de Weave 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 fusionado con esta información.
Para cada línea de los archivos derivados, la combinación de weave recopila la siguiente información: qué líneas la preceden, cuáles la siguen y si se eliminó en algún momento de la historia de cualquiera de los derivados. Si se eliminó la línea de cualquiera de los derivados en algún momento, no debe estar presente en la versión fusionada. En el caso de otras líneas, deben estar presentes en la versión fusionada.
Las líneas se ordenan de tal forma que cada línea se encuentra después de todas las líneas que la han precedido en algún momento de la historia y antes de todas las líneas que la han seguido 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 con respecto a las demás son adiciones que entran en conflicto.
Al parecer, la combinación de Weave fue utilizada por la herramienta de control de revisión comercial BitKeeper y puede manejar algunos de los casos problemáticos en los que una combinación de tres vías produce resultados incorrectos o erróneos. También es una de las opciones de combinación de la herramienta de control de revisión GNU Bazaar y se utiliza en Codeville. [ cita requerida ]
