Algorithmes de diff textuel : comment fonctionnent Git, les patches et les outils de diff

Chaque outil de revue de code, chaque sortie de git diff, chaque fichier de patch que vous avez jamais lu remonte à un petit nombre d’algorithmes inventés entre 1976 et 2009. Savoir lequel votre outil utilise — et quelle hypothèse il fait — fait la différence entre lire un diff en 30 secondes et en fixer un déroutant pendant dix minutes.

Ce qu’est réellement un diff

Un diff est un script d’édition: une séquence minimale d’insertions et de suppressions qui transforme le fichier A en fichier B. Pour deux fichiers de longueur totale N avec Ddifférences, il existe de nombreux scripts possibles. Un algorithme de diff en choisit un selon un critère d’optimisation — généralement le plus petit D, mais pas toujours.

Deux corollaires en découlent. Premièrement, le même changement de fichier peut légitimement produire des diffs d’apparence différente selon les outils ; ils sont tous corrects dans le sens où les appliquer reconstruit le fichier B. Deuxièmement, « diff lisible » est une contrainte plus faible que « diff minimal », et les deux sont souvent en désaccord. Vous pouvez comparer deux fichiers vous-même avec notre outil de diff textuel.

Myers diff — le défaut partout

L’article de 1986 d’Eugene Myers An O(ND) Difference Algorithm and Its Variations a défini l’algorithme que GNU diff, Git, Mercurial, SVN et la plupart des éditeurs utilisent encore par défaut. Il formule le problème de diff comme la recherche du chemin le plus court dans un graphe d’édition.

La complexité temporelle est O(N × D) où N est la longueur totale du fichier et Dest le nombre de différences. Pour des fichiers sources typiques avec de petites modifications, l’algorithme est essentiellement linéaire.

La faiblesse de Myers est qu’il minimise la taille du diff sans aucun sens de la structure. Après avoir déplacé un bloc de code, Myers associe souvent l’accolade fermante d’une fonction avec celle d’une autre différente parce que cela produit moins de lignes modifiées au total. Le résultat est techniquement minimal et humainement déconcertant.

Patience diff — conçu pour la lisibilité

Bram Cohen (l’auteur de BitTorrent) a introduit le Patience diff en 2007 spécifiquement pour résoudre le problème de lisibilité des refactorings de Myers. L’algorithme :

1. Trouve toutes les lignes qui n’apparaissent qu’une seule fois dans les deux fichiers. Ce sont des lignes d’ancrage uniques.
2. Calcule la plus longue sous-séquence commune des ancres uniques (en utilisant l’algorithme patience-sort — d’où le nom).
3. Diffe récursivement chaque région entre des ancres consécutives avec la même procédure, revenant à Myers quand aucune ancre unique ne reste.

Activez-le dans Git avec git diff --patience ou globalement avec git config diff.algorithm patience.

Histogram diff — Patience, affiné

Le diff Histogram a été introduit par JGit (l’implémentation Java de Git) et porté ultérieurement dans Git en amont. Il améliore Patience en étant plus intelligent sur les lignes d’ancrage à choisir : au lieu d’exiger l’unicité, il choisit les lignes rares avec le plus faible nombre d’occurrences dans les deux fichiers.

Histogram est le défaut recommandé pour la plupart des dépôts aujourd’hui. Activez-le globalement avec git config --global diff.algorithm histogram.

Lire un hunk diff unifié

Le diff unifié (-u) est le format d’échange de facto. Un hunk ressemble à :

@@ -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 ligne @@est l’en-tête du hunk. Elle indique : l’ancien fichier commence à la ligne 42 et s’étend sur 7 lignes ; le nouveau fichier commence à la ligne 42 et s’étend sur 9 lignes.

Les lignes sans préfixe sont du contexte inchangé. Les lignes commençant par -n’existent que dans l’ancien fichier ; les lignes commençant par +n’existent que dans le nouveau.

Espaces et fins de ligne

La principale source de diffs déroutants est l’espace. Les coupables courants :

• Espaces de fin.Un éditeur qui supprime les espaces de fin à l’enregistrement signalera chaque ligne touchée. Configurezcore.whitespace et git diff --ignore-space-at-eol.
• Indentation mixte.Passer des tabulations aux espaces (ou vice versa) est un diff sur l’ensemble du fichier même si aucune logique n’a changé. Utilisez git diff -wpour ignorer toutes les différences d’espaces.
• Fins de ligne. Les différences CRLF vs LF font apparaître chaque ligne comme modifiée. Configurez .gitattributes avec * text=auto pour normaliser lors du commit.

Fichiers binaires

Les algorithmes de diff opèrent sur des lignes. Les fichiers sans sauts de ligne naturels — images, exécutables, PDF — produisent une sortie inutile en diff textuel. Git détecte le contenu binaire en cherchant des octets nuls dans les 8 premiers Ko ; quand c’est trouvé, le diff se réduit àBinary files a/x and b/x differ.

Fusion à trois voies et pourquoi les conflits se produisent

Quand vous fusionnez la branche B dans la branche A, Git examine trois versions : l’ancêtre commun C, la version A et la version B. La fusion procède ligne par ligne :

• Ligne inchangée de C à A mais modifiée dans B → prendre B.
• Ligne modifiée dans A mais inchangée dans B → prendre A.
• Ligne modifiée identiquement dans les deux → prendre l’une ou l’autre ; pas de conflit.
• Ligne modifiée différemment dans A et B → conflit.

Les conflits sont signalés dans le fichier de travail avec les marqueurs <<<<<<<, ======= et >>>>>>> montrant les deux versions. La version ancêtre peut également être incluse avec merge.conflictStyle diff3.

Choisir un algorithme en pratique

Pour le travail quotidien, Histogram est le meilleur défaut. Patience produit des résultats très similaires et reste utile pour les très grands fichiers où l’utilisation de mémoire de Histogram devient notable. Myers est le bon choix pour les pipelines machine-à-machine qui consomment des diffs de manière programmatique, car sa sortie est le minimum canonique.

La conclusion honnête

Passez votre algorithme Git global à Histogram et n’y pensez plus pour la plupart des dépôts. Quand un diff vous déconcerte après un refactoring, re-rendez avec un algorithme différent avant de supposer que le changement est erroné. Normalisez les espaces et les fins de ligne au niveau du dépôt. Et rappelez-vous que le diff est une présentation, pas la vérité — la vérité est dans les deux fichiers, et un diff n’est qu’une des nombreuses façons valides de décrire le chemin entre eux.