diff - diff

Cet article concerne le programme utilitaire. Pour le sujet général de la comparaison de fichiers, voir Comparaison de fichiers . Pour les différences dans Wikipedia, voir help:diff . Pour d'autres utilisations, voir DIFF .
différence
Auteur(s) original(aux) Douglas McIlroy
( Laboratoires AT&T Bell )
Développeur(s) Divers open source et commerciaux développeurs
Première version juin 1974 ; il y a 47 ans ( 1974-06 )
Système opérateur Unix , Unix-like , V , Plan 9 , Inferno
Plate-forme Multiplateforme
Taper Commander

En informatique , l'utilitaire diff est un outil de comparaison de données qui calcule et affiche les différences entre le contenu des fichiers. Contrairement aux notions de distance d'édition utilisées à d'autres fins, diff est orienté ligne plutôt que caractère, mais c'est comme la distance de Levenshtein en ce sens qu'il essaie de déterminer le plus petit ensemble de suppressions et d'insertions pour créer un fichier à partir de l'autre. L'utilitaire affiche les modifications dans l'un des nombreux formats standard, de sorte que les humains ou les ordinateurs puissent analyser les modifications et les utiliser pour appliquer des correctifs .

Typiquement, diff est utilisé pour montrer les changements entre deux versions du même fichier. Les implémentations modernes prennent également en charge les fichiers binaires . La sortie est appelée un "diff", ou un patch , car la sortie peut être appliquée avec le patch du programme Unix . La sortie d'utilitaires de comparaison de fichiers similaires est également appelée « diff » ; comme l'utilisation du mot " grep " pour décrire l'acte de recherche, le mot diff est devenu un terme générique pour calculer la différence de données et les résultats de celle-ci. La norme POSIX spécifie le comportement des utilitaires "diff" et "patch" et leurs formats de fichiers.

Histoire

diff a été développé au début des années 1970 sur le système d'exploitation Unix, qui émergeait des Bell Labs de Murray Hill, New Jersey. La première version publiée a été livrée avec la 5e édition d'Unix en 1974 et a été écrite par Douglas McIlroy et James Hunt . Cette recherche a été publiée dans un article de 1976 co-écrit avec James W. Hunt, qui a développé un premier prototype de diff . L'algorithme que cet article décrit est devenu connu sous le nom d' algorithme de Hunt-Szymanski .

Le travail de McIlroy a été précédée et influencé par Steve Johnson 's programme de comparaison sur GECOS et Mike Lesk est la preuve programme. La preuve est également originaire d'Unix et, comme diff , a produit des modifications ligne par ligne et a même utilisé des crochets angulaires (">" et "<") pour présenter les insertions et suppressions de lignes dans la sortie du programme. Les heuristiques utilisées dans ces premières applications ont cependant été jugées peu fiables. L'utilité potentielle d'un outil de comparaison a poussé McIlroy à rechercher et à concevoir un outil plus robuste qui pourrait être utilisé dans une variété de tâches, mais qui fonctionne bien dans les limites de traitement et de taille du matériel du PDP-11 . Son approche du problème est le résultat d'une collaboration également avec des personnes des Bell Labs, notamment Alfred Aho , Elliot Pinson, Jeffrey Ullman et Harold S. Stone.

Dans le contexte d'Unix, l'utilisation de l' éditeur de ligne ed a fourni à diff la capacité naturelle de créer des "scripts d'édition" utilisables par la machine. Ces scripts d'édition, lorsqu'ils sont enregistrés dans un fichier, peuvent, avec le fichier d'origine, être reconstitués par ed dans le fichier modifié dans son intégralité. Cela a considérablement réduit le stockage secondaire nécessaire pour conserver plusieurs versions d'un fichier. McIlroy a envisagé d'écrire un post-processeur pour diff où une variété de formats de sortie pourraient être conçus et implémentés, mais il a trouvé plus frugal et plus simple que diff soit responsable de la génération de la syntaxe et de l'entrée dans l'ordre inverse acceptées par la commande ed .

À la fin de 1984, Larry Wall a créé un utilitaire séparé, patch , publiant son code source sur les groupes de discussion mod.sources et net.sources . Ce programme a généralisé et étendu la possibilité de modifier les fichiers avec la sortie de diff .

Les modes d' Emacs permettent également de convertir le format des correctifs et même d'éditer les correctifs de manière interactive.

Dans les premières années de diff , les utilisations courantes comprenaient la comparaison des modifications de la source du code logiciel et du balisage des documents techniques, la vérification de la sortie de débogage du programme, la comparaison des listes de systèmes de fichiers et l'analyse du code d'assemblage informatique. La sortie ciblée pour ed a été motivée pour fournir une compression pour une séquence de modifications apportées à un fichier. Le système de contrôle du code source (SCCS) et sa capacité à archiver les révisions sont apparus à la fin des années 1970 à la suite du stockage des scripts d'édition de diff .

Algorithme

Le fonctionnement de diff est basé sur la résolution du problème de sous- séquence commune le plus long .

Dans ce problème, étant donné deux séquences d'éléments : 

a b c d f g h j q z

a b c d e f g i j k r x y z

et nous voulons trouver une séquence d'éléments la plus longue qui soit présente dans les deux séquences originales dans le même ordre. C'est-à-dire que nous voulons trouver une nouvelle séquence qui peut être obtenue à partir de la première séquence d'origine en supprimant certains éléments, et à partir de la deuxième séquence d'origine en supprimant d'autres éléments. Nous souhaitons également que cette séquence soit la plus longue possible. Dans ce cas c'est 

a b c d  f  g  j  z

À partir d'une sous-séquence commune la plus longue, il n'y a qu'un petit pas pour obtenir une sortie de type diff : si un élément est absent dans la sous-séquence mais présent dans la première séquence d'origine, il doit avoir été supprimé (comme indiqué par les marques « - », ci-dessous ). S'il est absent dans la sous-séquence mais présent dans la deuxième séquence d'origine, il doit avoir été inséré (comme indiqué par les marques '+'). 

e   h i   q   k r x y
+   - +   -   + + + +

Usage

La diffcommande est invoquée à partir de la ligne de commande, en lui passant les noms de deux fichiers : . La sortie de la commande représente les modifications requises pour transformer le fichier d' origine dans le nouveau fichier. diff original new

Si original et new sont des répertoires, alors diff sera exécuté sur chaque fichier qui existe dans les deux répertoires. Une option, -r, descendra récursivement tous les sous-répertoires correspondants pour comparer les fichiers entre les répertoires.

N'importe lequel des exemples de l'article utilise les deux fichiers suivants, original et nouveau :

Dans ce format de sortie traditionnel, unesignifie ajouté ,répour supprimé etcpour changé . Les numéros de ligne du fichier d'origine apparaissent avantune/ré/cet ceux du nouveau fichier apparaissent après. Les signes inférieur à et supérieur à (au début des lignes ajoutées, supprimées ou modifiées) indiquent dans quel fichier les lignes apparaissent. Les lignes d'ajout sont ajoutées au fichier d'origine pour apparaître dans le nouveau fichier. Les lignes de suppression sont supprimées du fichier d'origine pour être manquantes dans le nouveau fichier.

Par défaut, les lignes communes aux deux fichiers ne sont pas affichées. Les lignes qui ont été déplacées sont affichées comme ajoutées à leur nouvel emplacement et comme supprimées de leur ancien emplacement. Cependant, certains outils de comparaison mettent en évidence les lignes déplacées.

Sortir variantes

Modifier le script

Un script ed peut toujours être généré par les versions modernes de diff avec l' -eoption. Le script d'édition résultant pour cet exemple est le suivant : 

24a

This paragraph contains
important new additions
to this document.
.
17c
check this document. On
.
11,15d
0a
This is an important
notice! It should
therefore be located at
the beginning of this
document!

.

Afin de transformer le contenu du fichier original en contenu du fichier new en utilisant ed , nous devons ajouter deux lignes à ce fichier diff, une ligne contenant une wcommande (écrire) et une autre contenant une qcommande (quitter) (par exemple by ). Ici, nous avons donné au fichier diff le nom mydiff et la transformation se produira alors lorsque nous exécuterons . printf "w\nq\n" >> mydiffed -s original < mydiff

Format de contexte

La distribution Berkeley d'Unix s'est fait un devoir d'ajouter le format de contexte ( -c) et la possibilité de récurser les structures de répertoires du système de fichiers ( -r), ajoutant ces fonctionnalités dans la version 2.8 BSD, publiée en juillet 1981. Le format de contexte de diff introduit à Berkeley a aidé à la distribution correctifs pour le code source qui peut avoir été modifié de façon minimale.

Dans le format contextuel, toutes les lignes modifiées sont affichées à côté des lignes inchangées avant et après. L'inclusion d'un nombre quelconque de lignes inchangées fournit un contexte au correctif. Le contexte se compose de lignes qui n'ont pas changé entre les deux fichiers et sert de référence pour localiser la place des lignes dans un fichier modifié et trouver l'emplacement prévu pour un changement à appliquer, que les numéros de ligne correspondent toujours ou non. Le format de contexte introduit une plus grande lisibilité pour les humains et une plus grande fiabilité lors de l'application du correctif, ainsi qu'une sortie qui est acceptée comme entrée du programme de correctif . Ce comportement intelligent n'est pas possible avec la sortie diff traditionnelle.

Le nombre de lignes inchangées affichées au-dessus et au-dessous d'un morceau de changement peut être défini par l'utilisateur, même zéro, mais trois lignes sont généralement la valeur par défaut. Si le contexte des lignes inchangées d'un morceau se chevauche avec un morceau adjacent, alors diff évitera de dupliquer les lignes inchangées et fusionnera les morceaux en un seul morceau.

Un " !" représente un changement entre les lignes qui correspondent dans les deux fichiers. Un " +" représente l'ajout d'une ligne, tandis qu'un espace vide représente une ligne inchangée. Au début du patch se trouvent les informations du fichier, y compris le chemin complet et un horodatage délimité par un caractère de tabulation. Au début de chaque morceau se trouvent les numéros de ligne qui s'appliquent au changement correspondant dans les fichiers. Une plage de nombres apparaissant entre des ensembles de trois astérisques s'applique au fichier d'origine, tandis que des ensembles de trois tirets s'appliquent au nouveau fichier. Les plages hunk spécifient les numéros de ligne de début et de fin dans le fichier respectif.

La commande diff -c original newproduit la sortie suivante : 

*** /path/to/original	timestamp
--- /path/to/new	timestamp
***************
*** 1,3 ****
--- 1,9 ----
+ This is an important
+ notice! It should
+ therefore be located at
+ the beginning of this
+ document!
+
  This part of the
  document has stayed the
  same from version to
***************
*** 8,20 ****
  compress the size of the
  changes.

- This paragraph contains
- text that is outdated.
- It will be deleted in the
- near future.

  It is important to spell
! check this dokument. On
  the other hand, a
  misspelled word isn't
  the end of the world.
--- 14,21 ----
  compress the size of the
  changes.

  It is important to spell
! check this document. On
  the other hand, a
  misspelled word isn't
  the end of the world.
***************
*** 22,24 ****
--- 23,29 ----
  this paragraph needs to
  be changed. Things can
  be added after it.
+
+ This paragraph contains
+ important new additions
+ to this document.

Remarque : Ici, la sortie diff est affichée avec des couleurs pour faciliter la lecture. L'utilitaire diff ne produit pas de sortie colorée ; sa sortie est en texte brut . Cependant, de nombreux outils peuvent afficher la sortie avec des couleurs en utilisant la coloration syntaxique .

Format unifié

Le format unifié (ou unidiff ) hérite des améliorations techniques apportées par le format contextuel, mais produit un diff plus petit avec l'ancien et le nouveau texte présentés immédiatement à côté. Le format unifié est généralement appelé à l'aide de l' option " -u" de la ligne de commande . Cette sortie est souvent utilisée comme entrée du programme de patch . De nombreux projets demandent spécifiquement que les "diffs" soient soumis au format unifié, faisant du format diff unifié le format le plus courant pour l'échange entre les développeurs de logiciels.

Les différences de contexte unifiées ont été développées à l'origine par Wayne Davison en août 1990 (en unidiff paru dans le volume 14 de comp.sources.misc). Richard Stallman a ajouté le support diff unifié à l' utilitaire diff du projet GNU un mois plus tard, et la fonctionnalité a fait ses débuts dans GNU diff 1.15, publié en janvier 1991. GNU diff a depuis généralisé le format de contexte pour permettre un formatage arbitraire des diff.

Le format commence par le même en- tête de deux lignes que le format de contexte, sauf que le fichier d'origine est précédé de "---" et le nouveau fichier est précédé de "+++". Viennent ensuite un ou plusieurs modules de modification qui contiennent les différences de ligne dans le fichier. Les lignes contextuelles inchangées sont précédées d'un espace, les lignes d'ajout sont précédées d'un signe plus et les lignes de suppression sont précédées d'un signe moins .

Un morceau commence par des informations sur la plage et est immédiatement suivi par les ajouts de lignes, les suppressions de lignes et un nombre quelconque de lignes contextuelles. Les informations de plage sont entourées de doubles signes at , et combinent sur une seule ligne ce qui apparaît sur deux lignes dans le format de contexte ( ci-dessus ). Le format de la ligne d'information de gamme est le suivant : 

@@ -l,s +l,s @@ optional section heading

Les informations sur la plage de tronçons contiennent deux plages de tronçons. La plage du gros morceau du fichier d'origine est précédée d'un symbole moins et la plage du nouveau fichier est précédée d'un symbole plus. Chaque plage de segment est au format l,s où l est le numéro de ligne de départ et s est le nombre de lignes auxquelles le segment de changement s'applique pour chaque fichier respectif. Dans de nombreuses versions de GNU diff, chaque plage peut omettre la virgule et la valeur de fin s , auquel cas s est par défaut à 1. Notez que la seule valeur vraiment intéressante est le numéro de ligne l de la première plage ; toutes les autres valeurs peuvent être calculées à partir du diff.

La plage de morceaux pour l'original doit être la somme de toutes les lignes de morceaux contextuelles et de suppression (y compris modifiées). La plage de segments pour le nouveau fichier doit être la somme de toutes les lignes de segment contextuelles et d'ajout (y compris modifiées). Si les informations sur la taille du segment ne correspondent pas au nombre de lignes du segment, le diff peut être considéré comme invalide et être rejeté.

En option, la plage du morceau peut être suivie du titre de la section ou de la fonction dont fait partie le morceau. Ceci est principalement utile pour rendre le diff plus facile à lire. Lors de la création d'un diff avec GNU diff, l'en-tête est identifié par la correspondance d' expressions régulières .

Si une ligne est modifiée, elle est représentée comme une suppression et un ajout. Étant donné que les morceaux du fichier d'origine et du nouveau fichier apparaissent dans le même morceau, ces modifications apparaîtraient adjacentes les unes aux autres. Une occurrence de ceci dans l'exemple ci-dessous est : 

-check this dokument. On
+check this document. On

La commande diff -u original newproduit la sortie suivante : 

--- /path/to/original	timestamp
+++ /path/to/new	timestamp
@@ -1,3 +1,9 @@
+This is an important
+notice! It should
+therefore be located at
+the beginning of this
+document!
+
 This part of the
 document has stayed the
 same from version to
@@ -8,13 +14,8 @@
 compress the size of the
 changes.

-This paragraph contains
-text that is outdated.
-It will be deleted in the
-near future.
-
 It is important to spell
-check this dokument. On
+check this document. On
 the other hand, a
 misspelled word isn't
 the end of the world.
@@ -22,3 +23,7 @@
 this paragraph needs to
 be changed. Things can
 be added after it.
+
+This paragraph contains
+important new additions
+to this document.

Remarque : Ici, la sortie diff est affichée avec des couleurs pour faciliter la lecture. L'utilitaire diff ne produit pas de sortie colorée ; sa sortie est en texte brut . Cependant, de nombreux outils peuvent afficher la sortie avec des couleurs en utilisant la coloration syntaxique .

Notez que pour séparer avec succès les noms de fichiers des horodatages, le délimiteur entre eux est un caractère de tabulation. Ceci est invisible à l'écran et peut être perdu lorsque les différences sont copiées/collées depuis les écrans de la console/du terminal.

Certaines modifications et extensions des formats diff sont utilisées et comprises par certains programmes et dans certains contextes. Par exemple, certains systèmes de contrôle de révision , tels que Subversion, spécifient un numéro de version, une "copie de travail" ou tout autre commentaire à la place ou en plus d'un horodatage dans la section d'en-tête du diff.

Certains outils permettent de fusionner les différences de plusieurs fichiers différents en un seul, en utilisant un en-tête pour chaque fichier modifié qui peut ressembler à ceci : 

Index: path/to/file.cpp

Le cas particulier des fichiers qui ne se terminent pas par un saut de ligne n'est pas traité. Ni l'utilitaire unidiff ni le standard POSIX diff ne définissent un moyen de gérer ce type de fichiers. (En effet, de tels fichiers ne sont pas des fichiers "textes" selon les définitions strictes de POSIX.) Le programme de correctif n'est même pas au courant d'une sortie diff spécifique à l'implémentation.

Implémentations et programmes associés

Les changements depuis 1975 incluent des améliorations de l'algorithme de base, l'ajout de fonctionnalités utiles à la commande et la conception de nouveaux formats de sortie. L'algorithme de base est décrit dans les articles An O(ND) Difference Algorithm and its Variations par Eugene W. Myers et dans A File Comparison Program par Webb Miller et Myers. L'algorithme a été indépendamment découvert et décrit dans Algorithms for Approximate String Matching , par Esko Ukkonen . Les premières éditions du programme diff ont été conçues pour des comparaisons de lignes de fichiers texte en attendant que le caractère de nouvelle ligne délimite les lignes. Dans les années 1980, la prise en charge des fichiers binaires a entraîné un changement dans la conception et la mise en œuvre de l'application.

GNU diff et diff3 sont inclus dans le package diffutils avec d'autres utilitaires liés aux diff et aux correctifs . De nos jours, il existe également un package patchutils qui peut combiner, réorganiser, comparer et corriger les différences de contexte et les différences unifiées.

Formateurs et frontaux

Les post- processeurs sdiff et diffmk restituent des listes de diff côte à côte et appliquent des marques de modification aux documents imprimés, respectivement. Les deux ont été développés ailleurs dans les Bell Labs en 1981 ou avant.

Diff3 compare un fichier à deux autres fichiers en conciliant deux diff. Il a été conçu à l'origine par Paul Jensen pour réconcilier les modifications apportées par deux personnes éditant une source commune. Il est également utilisé par les systèmes de contrôle de révision, par exemple RCS , pour la fusion .

Emacs a Ediff pour montrer les changements qu'un correctif apporterait dans une interface utilisateur qui combine des capacités d'édition et de fusion interactives pour les fichiers de correctif.

Vim fournit vimdiff pour comparer de deux à huit fichiers, avec des différences surlignées en couleur. Invoquant historiquement le programme diff, vim moderne utilise git « s fork de code de la bibliothèque xdiff (libxdiff), assurant une meilleure vitesse et la fonctionnalité.

GNU Wdiff est un frontal à diff qui montre les mots ou les phrases qui ont changé dans un document texte de langue écrite même en présence d'un habillage de mots ou de différentes largeurs de colonnes.

colordiff est un wrapper Perl pour 'diff' et produit la même sortie mais avec une jolie mise en évidence de 'syntaxe'.

Dérivées algorithmiques

Les utilitaires qui comparent les fichiers source par leur structure syntaxique ont été construits principalement comme outils de recherche pour certains langages de programmation ; certains sont disponibles sous forme d'outils commerciaux. De plus, les outils gratuits qui effectuent des diff sensibles à la syntaxe incluent :

  • C++ : zograscope, basé sur AST.
  • HTML : Daisydiff, html-differ.
  • XML : xmldiffpatch par Microsoft et xmldiffmerge pour IBM.
  • JavaScript : astii (basé sur AST).
  • Multi-langue : Pretty Diff (format code puis diff)

spiff est une variante de diff qui ignore les différences dans les calculs à virgule flottante avec des erreurs d'arrondi et des espaces , qui ne sont généralement pas pertinents pour la comparaison du code source. Bellcore a écrit la version originale. Un port HPUX est la version publique la plus récente. spiff ne prend pas en charge les fichiers binaires. sorties SPIFF à la sortie standard en format standard diff et accepte les entrées dans le C , Bourne shell , Fortran , Modula-2 et Lisp langages de programmation .

LibXDiff est une bibliothèque LGPL qui fournit une interface à de nombreux algorithmes à partir de 1998. Un algorithme Myers amélioré avec empreinte Rabin a été initialement implémenté (à partir de la version finale de 2008), mais le fork de git et libgit2 a depuis étendu le référentiel avec de nombreux sa propre. Un algorithme appelé "histogramme" est généralement considéré comme bien meilleur que l'algorithme original de Myers, à la fois en termes de vitesse et de qualité. Il s'agit de la version moderne de LibXDiff utilisée par Vim.

Voir également

Autres outils gratuits de comparaison de fichiers

Les références

Lectures complémentaires

Liens externes