Diff XML

Un document XML est un fichier texte (encodé en Unicode) qui respecte la syntaxe arborescente définie par le standard XML. Cette syntaxe permet la structuration logique du contenu : « un livre est organisé en chapitres, chaque chapitre en sections, sous-sections, paragraphes, etc. » (André et al., 1989[1]). La représentation en mémoire d'un document XML est donc un arbre, dont les nœuds sont de différents types, parmi lesquels : nœuds document, élément, attribut, texte (ici, nous ne considérerons pas les autres types de nœud tels que les commentaires ou les processing instructions). Le standard XML ajoute des contraintes syntaxiques supplémentaires en fonction de ces types :

  • un document XML possède un unique nœud document qui est la racine de l'arbre ;

  • les éléments sont identifiés par un nom et peuvent contenir des attributs, des nœuds textes et d'autres éléments ;

  • un élément terminal est dit élément vide ;

  • les attributs sont identifiés par un nom unique au sein de l'élément et ne peuvent contenir qu'un seul nœud texte ;

  • les nœuds textes sont des feuilles et ont une valeur (chaîne de caractères) ;

  • on peut considérer que le label d'un nœud élément ou attribut correspond à son nom, et que le label d'un nœud texte correspond à sa valeur (ou bien un hash de sa valeur, tel que décrit dans (Rönnau et al., 2009[2]) et comme nous l'avons vu plus haut avec le diff orienté lignes).

Un diff XML est donc un cas particulier de calcul de la distance d'édition entre deux arbres. L'ordre des nœuds enfants peut être pris en compte de différentes façons selon le domaine d'application ou d'usage du document XML. Typiquement :

  • Dans les langages XML orientés données (sérialisation d'une table de base de données par exemple), l'ordre des nœuds enfants n'est pas signifiant. Par exemple, les entrées de la table Catalogue ci-dessous peuvent être sérialisées dans un ordre arbitraire (par un tri alphanumérique sur le numéro, la désignation, le stock...), tous les ordres possibles étant potentiellement signifiants.

    1
    <catalogue>
    2
        <ouvrage num="1" designation="La raison graphique" auteur="Goody, J." stock="5"/>
    3
        <ouvrage num="2" designation="La technique et le temps, tome 1" auteur="Stiegler, B." stock="3"/>
    4
        <ouvrage num="3" designation="Du mode d'existence des objets techniques" auteur="Simondon, G." stock="1"/>
    5
        ...
    6
    </catalogue>

  • Dans les langages XML orientés documents (formats portés avant tout sur la structuration logique, comme DocBook, TEI, DITA... ou également dédiés à la présentation, comme XHTML), l'ordre des nœuds enfants (hors attributs) dans le fichier sérialisé est signifiant. Par exemple dans le fragment XHTML ci-dessous, la balise h1 est affichée par le navigateur avant la balise p, sans quoi le sens n'est pas le même. En revanche, l'inversion des deux attributs id et class n'aura aucune conséquence visuelle.

    1
    <h1 id="456" class="section_title">Introduction à Oracle</h1>
    2
    <p>Oracle est le premier SGBDR commercialisé en 1979.</p>
    3
    ...

    C'est dans ce second cas que nous nous situons.

Le delta produit par un diff XML est donc une liste d'opérations concernant les nœuds de l'arbre XML. Il est difficile d'établir un consensus sur un modèle de delta du point de vue des types d'opérations à considérer, qui varient souvent selon l'algorithme, classiquement parmi l'insertion, la suppression, la modification, le déplacement ou encore la copie d'un nœud. En effet, comme le souligne Vion-Dury (2011[3]), la plupart des algorithmes sont optimisés pour une certaine application et/ou une certaine taille de document. Seules les opérations d'insertion et de suppression de nœuds (avec leur descendance, éventuellement aucune si le nœud est une feuille) sont communément supportées par les diffs, et ce de manière univoque.

Dans le modèle formel proposé par Vion-Dury (ibid.[3]), un delta est composé uniquement de ces deux types d'opérations, ins et del, qualifiées d'atomiques. Chaque nœud de l'arbre XML doit être accessible via un unique chemin. Dans l'exemple suivant (inspiré de (ibid.[3])), les chemins des nœuds éléments a, b, c et d sont respectivement 1, 1/1, 1/1/1 et 1/2.

1
<a>
2
    <b>
3
        <c/>
4
    </b>
5
    <d/>
6
</a>

La suppression de d s'écrit del(1/2), tandis que l'ajout de e en tant qu'élément frère de b s'écrit ins(1/1/2, e). Comme nous l'avons vu plus haut, les opérations du delta ne peuvent être exécutées dans un ordre quelconque que si elles n'interfèrent pas les unes avec les autres. Dans le cas du diff XML, Vion-Dury formalise cette exigence avec le concept d'orthogonalité des chemins. Voici un pseudo-algorithme que nous proposons à partir des propriétés formelles de l'orthogonalité caractérisées dans (ibid.[3]) :

1
Si les deux chemins sont égaux ou désignent des nœuds frères (de même nœud parent), ils ne sont pas orthogonaux
2
	Sinon :
3
		Si les deux chemins sont de même profondeur, ils sont orthogonaux
4
		Sinon, on remonte le plus long chemin jusqu'à arriver au niveau du plus court :
5
			Si le nœud "remonté" précède le nœud désigné par le chemin le plus court, alors les chemins sont orthogonaux
6
			Sinon, les chemins ne sont pas orthogonaux

Dans l'exemple précédant, les chemins 1/1/2 et 1/2 sont orthogonaux car 1/1/2 est plus profond que 1/2 d'une part, et 1/1 (sous-partie de 1/1/2 de même niveau que 1/2) précède bien 1/2 dans l'ordre logique de l'arbre d'autre part. Par ailleurs, 1/2/1 et 1/1 ne sont pas orthogonaux car 1/2 (sous-partie de 1/2/1 de même niveau que 1/1) ne précède pas 1/1 ; 1/1 et 1/2 ne le sont pas non plus car ce sont des nœuds frères. Les opérations ins(1/1/2, e) et del(1/2) portant sur des chemins orthogonaux, le résultat final ne dépendra pas de leur ordre d'exécution.

Par suite, Vion-Dury redéfinit le delta comme un groupe de transformations, qui sont soit des opérations atomiques, soit des deltas, pouvant être exécutés :

  • séquentiellement, c'est-à-dire selon un ordre prescrit ;

  • parallèlement, c'est-à-dire que la séquence choisie n'influence pas le résultat final, à condition que toutes les transformations du delta soient orthogonales deux à deux.

Un troisième type de composition, nommé snapshot, concerne le cas où deux transformations ont des chemins orthogonaux d'une part, et où le chemin de la première précède le chemin de la seconde dans l'ordre total des nœuds (ordre dans le document XML sérialisé) d'autre part. Par exemple, considérons deux opérations del sur les chemins 1/1 et 1/2/1, qui ne sont pas orthogonaux comme nous l'avons vu plus haut. La séquence del(1/2/1);del(1/1) peut être considérée comme correcte (1/2/1 ne précède pas 1/1 dans l'ordre des nœuds), la séquence inverse del(1/1);del(1/2/1) doit être réécrite à l'aide de la composition snapshot comme del(1/1);del(1/1/1).