Pour les deux mêmes fichiers, le résultat peut varier selon l'algorithme diff utilisé. Tous produisent un diff « correct », mais ils n'apparient pas les mêmes lignes entre elles, ce qui change la facilité de lecture. git en propose quatre via l'option --diff-algorithm.
| Valeur | Description de la documentation git | Caractéristiques |
|---|---|---|
myers (default) | L'algorithme glouton (greedy) de base, valeur par défaut actuelle | Rapide, généralement proche du minimum |
minimal | Prend plus de temps pour produire le plus petit diff possible | Toujours minimal, parfois lent sur de grosses entrées |
patience | L'algorithme patience diff | Prend les lignes uniques comme points d'ancrage |
histogram | Étend patience pour prendre en charge les éléments communs peu fréquents | Prend les lignes rares comme points d'ancrage |
Il existe aussi des options courtes comme git diff --patience ou git diff --histogram, et la valeur par défaut peut être changée avec git config diff.algorithm histogram.
Myers : la valeur par défaut, qui cherche l'édition minimale
L'algorithme de Myers cherche le chemin qui réduit au minimum le nombre de suppressions et d'ajouts (voir le principe dans Comment fonctionne diff). La difficulté survient quand plusieurs choix sont possibles pour décider quelles lignes sont identiques. Le code contient beaucoup de lignes très fréquentes comme }, {, des lignes vides ou return : même si l'algorithme apparie des lignes sans rapport de sens, le nombre d'éditions peut rester tout aussi minimal.
Une même modification, deux résultats
Supposons qu'on ait inséré une nouvelle fonction h entre les fonctions f et g, comme ci-dessous. Les deux diff suivants comptent chacun 4 lignes ajoutées : leur nombre d'éditions est identique.
@@ -1,6 +1,10 @@ int f() { return 1; }++int h() {+ return 3;+} int g() { return 2;@@ -1,5 +1,9 @@ int f() { return 1;+}++int h() {+ return 3; } int g() {Le premier montre la nouvelle fonction d'un seul bloc ; le second traite l'accolade fermante de la fonction existante f comme celle de la nouvelle fonction, si bien que la partie ajoutée est découpée maladroitement. Ce genre de forme dépend de l'ordre d'exploration. Les versions récentes de git corrigent une bonne partie de ces cas avec une heuristique qui déplace les limites des portions modifiées en fonction de l'indentation (--indent-heuristic, activée par défaut).
Patience : aligner d'abord les lignes uniques
Le patience diff, proposé par Bram Cohen, commence par chercher les lignes qui n'apparaissent qu'une seule fois dans chacun des deux fichiers. Une ligne unique comme la déclaration de fonction int h() { a un correspondant certain. Parmi ces lignes uniques, il choisit la plus longue liste dont l'ordre concorde (plus longue sous-séquence croissante) comme points d'ancrage, puis ne compare de nouveau que les petites portions situées entre ces points.
- Avantage : il ne se laisse pas entraîner par des lignes fréquentes comme
}ou les lignes vides, si bien que les modifications apparaissent par blocs, fonction par fonction ou paragraphe par paragraphe. - Inconvénient : sur des entrées qui n'ont presque aucune ligne unique (données où les mêmes lignes se répètent, journaux), il ne trouve pas de points d'ancrage et ne fait pas mieux qu'un diff ordinaire, voire regroupe les changements en gros blocs.
Histogram : privilégier les lignes rares
L'algorithme histogram a été développé dans JGit (une implémentation de git en Java) puis intégré à git. Alors que patience ne considère que les « lignes présentes exactement une fois », histogram compte le nombre d'occurrences de chaque ligne et choisit comme points d'ancrage celles qui apparaissent le moins. Il peut ainsi s'appuyer sur des lignes relativement rares même en l'absence de lignes uniques. La documentation de git le décrit comme une extension de l'algorithme patience « pour prendre en charge les éléments communs peu fréquents ». En pratique, il produit souvent, comme patience, des résultats qui respectent bien la structure du code.
Lequel choisir
- Revue de code courante : la valeur par défaut suffit. Si le résultat semble découpé bizarrement, relancez avec
--histogram. - Grand remaniement où des fonctions sont déplacées ou ajoutées en nombre :
--histogramou--patienceconservent mieux les blocs. - Besoin de compter exactement le nombre minimal de lignes modifiées :
--minimal. - Fichiers de données très répétitifs : le tri et la normalisation comptent parfois plus que l'algorithme. Pour du JSON, voir Comparer du JSON.
Quel que soit l'algorithme, le fichier obtenu en appliquant le résultat est le même. Seule change la forme présentée au lecteur.
Dans cet outil
Ce site compare les lignes avec un algorithme de la famille Myers, puis évalue la similarité de contenu entre lignes modifiées pour les apparier comme « modifiées » et comparer de nouveau l'intérieur des lignes. Ainsi, même si le résultat par ligne est un peu maladroitement découpé, on voit tout de suite quel mot a changé. Collez l'exemple ci-dessus dans le comparateur de texte et comparez son rendu en vue unifiée et en vue côte à côte. La lecture du résultat est expliquée dans Lire un diff unifié.