¿Cómo encuentra Git los cambios? (El algoritmo Diff)

git diff es un comando que todo desarrollador usa a diario.

¿No es sorprendente cómo encuentra instantáneamente exactamente qué líneas se agregaron o eliminaron entre miles de líneas de código?

¿Simplemente compara dos archivos línea por línea? Si es así, insertar una sola línea en el medio marcaría todas las líneas siguientes como "modificadas".

Git utiliza un método inteligente llamado Algoritmo Myers Diff para encontrar el "conjunto mínimo de cambios".

1. Distancia de Edición

El problema de calcular la diferencia entre dos cadenas (o archivos) se reduce a encontrar el "número mínimo de ediciones requeridas para transformar A en B". Esto se llama Distancia de Edición.

Por ejemplo, para cambiar ABC a ABD:

1. Eliminar C
2. Agregar D (Distancia de Edición: 2)

Git realiza este cálculo no carácter por carácter, sino línea por línea.

2. Subsecuencia Común Más Larga (LCS)

El núcleo del algoritmo de Myers es encontrar la Subsecuencia Común Más Larga (LCS) entre dos archivos.

Una vez que se encuentra la LCS, el resto es fácil.

• Las partes de A que no están en la LCS son Eliminadas (-).
• Las partes de B que no están en la LCS son **Agregadas (+)`.

Por ejemplo:

• Archivo A: 1 2 3 4
• Archivo B: 1 3 5 4

Aquí, la LCS es 1 3 4.
Por lo tanto, podemos deducir que 2 fue eliminado y 5 fue agregado.

3. La Magia del Algoritmo de Myers

Publicado por Eugene W. Myers en 1986, este algoritmo transforma el problema LCS en un problema de recorrido de grafos (encontrar el camino más corto) para resolverlo de manera muy eficiente.

Git usa este algoritmo por defecto, pero también ofrece otros algoritmos como histogram o patience como opciones.

Conclusión

Detrás de los signos + y - que damos por sentado se encuentra un elegante algoritmo matemático probado durante más de 30 años.

Si encuentras la salida de git diff confusa o desordenada, prueba git diff --algorithm=histogram. A menudo produce resultados que reflejan mejor la estructura del código.