Algoritmos de diff de texto: cómo funcionan Git, los parches y las herramientas de diff

Todas las herramientas de revisión de código, todas las salidas de git diff, todos los archivos de parche que ha leído alguna vez se remontan a un pequeño número de algoritmos inventados entre 1976 y 2009. Saber cuál usa su herramienta — y qué suposición hace — es la diferencia entre leer un diff en 30 segundos y mirarlo confundido durante diez minutos preguntándose si la refactorización realmente preservó el comportamiento.

Qué es realmente un diff

Un diff es un script de edición: una secuencia mínima de inserciones y eliminaciones que transforma el archivo A en el archivo B. Para dos archivos de longitud total N con D diferencias, hay muchos scripts posibles. Un algoritmo de diff elige uno según algún criterio de optimización — generalmente el D más pequeño, pero no siempre.

Se derivan dos corolarios. Primero, el mismo cambio de archivo puede producir legítimamente diffs de apariencia diferente de distintas herramientas; todos son correctos en el sentido de que aplicarlos reconstruye el archivo B. Segundo, “diff legible” es una restricción más débil que “diff más pequeño”, y los dos a menudo no coinciden. Puede comparar dos archivos usted mismo con nuestra herramienta de diff de texto y ver la salida unificada lado a lado.

Diff de Myers — el predeterminado en todas partes

El artículo de 1986 de Eugene Myers An O(ND) Difference Algorithm and Its Variations definió el algoritmo que GNU diff, Git, Mercurial, SVN y la mayoría de los editores aún usan por defecto. Enmarca el problema del diff como encontrar el camino más corto a través de un grafo de edición: cada paso diagonal es una línea que coincide, cada paso horizontal elimina una línea de A, cada paso vertical inserta una línea de B. El camino más corto corresponde al script de edición mínima.

La complejidad temporal es O(N × D) donde N es la longitud total del archivo y D es el número de diferencias. Para archivos de código fuente típicos con ediciones pequeñas el algoritmo es esencialmente lineal; para archivos que han sido reescritos de principio a fin se degrada.

La debilidad de Myers es que minimiza el tamaño del diff sin ningún sentido de la estructura. Después de mover un bloque de código, Myers a menudo empareja la llave de cierre de una función con la llave de cierre de una función diferente porque eso produce menos líneas cambiadas en total. El resultado es técnicamente mínimo y humanamente desconcertante.

Diff de Patience — diseñado para la legibilidad

Bram Cohen (el autor de BitTorrent) introdujo el diff de Patience en 2007 específicamente para solucionar el problema de legibilidad de refactorización de Myers. El algoritmo:

1. Encuentra todas las líneas que aparecen exactamente una vez en ambos archivos. Estas son líneas de anclaje únicas.
2. Calcula la subsecuencia común más larga de los anclajes únicos (usando el algoritmo de ordenación de paciencia — de ahí el nombre).
3. Hace diff recursivamente de cada región entre anclajes consecutivos usando el mismo procedimiento, recurriendo a Myers cuando no quedan anclajes únicos.

El resultado alinea el diff alrededor de las líneas que un humano reconocería como “la misma cosa” — firmas de funciones, comentarios únicos, declaraciones de clase. Patience es más lento que Myers en el peor caso pero produce una salida mucho más legible para cambios de código típicos. Actívelo en Git con git diff --patience o globalmente con git config diff.algorithm patience.

Diff de Histogram — Patience, refinado

El diff de Histogram fue introducido por JGit (la implementación de Git en Java) y luego portado al Git original. Mejora a Patience siendo más inteligente sobre qué líneas de anclaje elegir: en lugar de requerir unicidad, elige las líneas raras con el menor recuento de ocurrencias en ambos archivos. Las líneas comunes (llaves de cierre, líneas en blanco) se desclasifican; las líneas raras (nombres de funciones, cadenas distintivas) se convierten en anclajes.

Histogram es el predeterminado recomendado para la mayoría de los repositorios hoy en día. Produce una salida similar a Patience para casos típicos y notablemente mejor para archivos con muchas líneas repetidas (como archivos de datos, fixtures y configuración con mucha indentación). Actívelo globalmente con git config --global diff.algorithm histogram.

Leyendo un hunk de diff unificado

El diff unificado (-u) es el formato de intercambio de facto. Un hunk se ve así:

@@ -42,7 +42,9 @@ class UserController {
   const user = await User.findById(id);
   if (!user) {
-    return res.status(404).end();
+    logger.warn({ id }, "user not found");
+    return res.status(404).json({ error: "not found" });
   }
   return res.json(user);
 }

La línea @@ es el encabezado del hunk. Dice: el archivo antiguo comienza en la línea 42 y abarca 7 líneas; el archivo nuevo comienza en la línea 42 y abarca 9 líneas. El texto que sigue al segundo @@ es un encabezado de sección — para código generalmente es la función o clase envolvente.

Las líneas sin prefijo son contexto sin cambios. Las líneas que comienzan con - solo existen en el archivo antiguo; las que comienzan con + solo existen en el archivo nuevo. El contexto predeterminado son tres líneas en cada lado; -U10 lo amplía, útil cuando el efecto del cambio depende de una instrucción justo fuera de la vista.

Espacios en blanco y finales de línea

La mayor fuente de diffs confusos es el espacio en blanco. Los culpables más comunes:

• Espacios en blanco finales. Un editor que elimina los espacios finales al guardar marcará cada línea tocada. Configurecore.whitespace y git diff --ignore-space-at-eol para mantener el diff enfocado en cambios reales.
• Indentación mixta. Cambiar de tabulaciones a espacios (o viceversa) es un diff de archivo completo incluso si no cambió ninguna lógica. Use git diff -w para ignorar todas las diferencias de espacio en blanco al revisar tales cambios.
• Finales de línea. Las diferencias CRLF vs LF hacen que cada línea parezca modificada. Configure .gitattributes con * text=auto para normalizar al hacer commit.
• Salto de línea final. Los archivos sin un salto de línea final muestran \ No newline at end of file en el diff. Algunas herramientas añaden el salto silenciosamente al guardar, produciendo diffs de una línea que parecen ruido.

Archivos binarios

Los algoritmos de diff operan en líneas. Los archivos sin saltos de línea naturales — imágenes, ejecutables, PDFs — producen una salida inútil cuando se les hace diff textualmente. Git detecta contenido binario buscando bytes nulos en los primeros 8 KB; cuando se encuentran, el diff se reduce a Binary files a/x and b/x differ.

Para contenido binario que debería ser comparable (DOCX, XLSX, archivos de diseño), .gitattributes puede registrar un filtro textconv personalizado que convierte el archivo a una representación textual antes de hacer el diff.

Merge de tres vías y por qué ocurren los conflictos

Cuando hace merge de la rama B en la rama A, Git mira tres versiones: el ancestro común C, la versión A y la versión B. El merge procede línea por línea:

• Línea sin cambios de C a A pero modificada en B → tomar B.
• Línea modificada en A pero sin cambios en B → tomar A.
• Línea modificada de forma idéntica en ambas → tomar cualquiera; sin conflicto.
• Línea modificada de forma diferente en A y B → conflicto.

Los conflictos se marcan en el archivo de trabajo con marcadores <<<<<<<, ======= y >>>>>>> que muestran ambas versiones. La versión ancestro también puede incluirse con merge.conflictStyle diff3, lo que hace la resolución mucho más fácil porque se puede ver desde dónde partió cada lado.

Elegir un algoritmo en la práctica

Para el trabajo diario, Histogram es el mejor predeterminado y el que la mayoría de los equipos debería configurar globalmente. Patience produce resultados muy similares y sigue siendo útil para archivos muy grandes donde el uso de memoria de Histogram se vuelve notable. Myers es la elección correcta para pipelines de máquina a máquina que consumen diffs programáticamente, porque su salida es el mínimo canónico.

Las herramientas de revisión de código (GitHub, GitLab, Gerrit) todas usan Myers por defecto por razones heredadas; sus interfaces de usuario no siempre exponen la elección del algoritmo. Cuando un diff de revisión parece desalineado, descargue el parche y rerenderícelo localmente con git diff --histogram — el resultado suele ser mucho más fácil de leer.

La conclusión honesta

Cambie su algoritmo global de Git a Histogram y nunca vuelva a pensar en ello para la mayoría de los repositorios. Cuando un diff le confunde después de una refactorización, rerenderícelo con un algoritmo diferente antes de asumir que el cambio es incorrecto. Normalice los espacios en blanco y los finales de línea a nivel del repositorio para que los revisores dediquen su tiempo a la lógica, no al formato. Y recuerde que el diff es una presentación, no la verdad — la verdad son los dos archivos, y un diff es solo una de muchas formas válidas de describir el camino entre ellos.