En janvier, nous avons appris que la SNCF souhaitait mettre à jour son système tarifaire, c’est-à-dire l’ensemble des règles qui déterminent le prix d’un billet. Elle laissait tomber les prix des périodes d’affluence des TGV, elle diminuait les changements de prix brusques, elle offrait tant de cadeaux aux porteurs de cartes de réduction que ça sentait bon Noël.

Mais ces nobles objectifs s’accompagnent de grands défis. Tout comme une princesse doit combattre un dragon pour délivrer son prince charmant, la SNCF devrait combattre son système tarifaire actuel pour en extraire une perle de ses cendres. Le sang de ce combat ne pouvait éviter de couler sur leurs partenaires : les guichetiers, les agences de voyage, les GDS, et nous.

Basculer vers une nouvelle API de recherche SNCF

Il fallait quelqu’un au sein de Trainline (anciennement Captain Train) pour mettre à jour notre code, afin qu’il corresponde bien au nouveau système tarifaire de la SNCF, et je me suis porté volontaire. C’était un projet de large envergure, car nous devions basculer vers une nouvelle API de recherche SNCF. Nous avons appris un nouveau langage à notre moteur de recherche de trains, en quelque sorte.

Évaluer l’écart entre les anciens résultats et les nouveaux

Ce moteur convertit les résultats de recherche (spécifiques à un transporteur) dans un format utilisé en interne, commun à tous les transporteurs. L’entrée de cette conversion allait donc totalement changer, mais la sortie devait demeurer identique. En effet, la nouvelle API de recherche SNCF à laquelle nous allions nous connecter supporte à la fois l’ancien et le nouveau système tarifaire, mais nos serveurs en production allaient toujours utiliser l’ancien système, jusqu’à la date fatidique du lancement du nouveau système.

Lorsqu’enfin nous avons obtenu une conversion convenable, il était temps de garantir que rien ne changerait pour nos utilisateurs. J’ai donc ajusté notre moteur de recherche de trains afin qu’il répète les recherches de certains utilisateurs en production, après que ces recherches aient été exécutées avec l’ancien moteur. Ensuite, je sauvegardais le résultat JSON de l’ancien et du nouveau moteur côte à côte.

J’avais ainsi une large quantité de fichiers de type « avant / après », qui étaient supposément identiques par paires. Bien entendu, ces fichiers n’étaient pas littéralement identiques ; comment le destin aurait-il pu permettre une tâche aussi triviale ? Ils contenaient des clefs aléatoires ici, des listes ordonnées différemment là, de façon à ce qu’un bête diff des fichiers ne puisse qu’échouer.

Quand bien même aurais-je pu faire un diff, cela ne m’aurait nullement aidé à comprendre pourquoi deux fichiers sont différents. J’avais besoin d’un diff capable de comprendre du JSON en profondeur. Chaque différence est un bug.

J’ai tenté de trouver un tel algorithme, j’ai navigué de bibliothèque en logiciel prétendant differ du JSON. Ce que j’ai déniché donnait un résultat raisonnable, mais tout ce que j’ai essayé détectait plein de faux-positifs. En particulier, tous se cassaient les dents sur les listes JSON utilisées comme si c’était des ensembles. L’ordre des éléments n’avait pas d’importance, et était souvent différent. Aucun des algorithmes ne pouvait détecter automatiquement qu’un élément dans une de ces listes avait bougé dans ladite liste.

Pourquoi donc ?

Le problème

Comment décririez-vous un changement ?

On peut aisément comparer l’avant et l’après bit par bit et dire : « Salut ! Rien n’a changé ! », ou bien « Tout est chamboulé ! » Bien entendu, votre pouvoir analytique est alors minuscule. Imaginez une base de données gigantesque dans laquelle un seul nombre entier est incrémenté. Si votre diff dit seulement : « Supprimez toute la base et insérez une nouvelle base quasi identique », votre diff est bien trop gros. En outre, vous effacez l’intention qui se cache derrière le changement.

En JSON, la plupart des valeurs ne peuvent pas s’imbriquer. Appelons-les des atomes. Dans l’usage courant, avoir un diff qui fait une comparaison triviale pour les atomes passe sans problème. En revanche, nous avons généralement besoin de parcourir les structures afin d’avoir un diff digne de ce nom. Les objets sont faciles : à moins de vouloir détecter les changements de noms de clefs, on se satisfait d’une comparaison de valeurs clef par clef.

Les soucis arrivent avec les listes. Nous pourrions comparer leurs valeurs indice par indice. C’est ce que fait jsondiff. Toutefois, nous perdons généralement une grande capacité analytique à faire cela.

La plupart des opérations sur listes sont souvent définies en terme de deux actions fondamentales : l’insertion et la suppression. Comparons, disons, [1, 2, 3] et [1, 3]. Un diff qui raconte que « nous avons incrémenté le 2 et supprimé le 3 » ignore une explication plus simple, « nous avons inséré un 2. » Le rasoir d’Ockham penche en faveur de cette dernière.

Trouver le nombre minimal d’opérations d’insertion ou de suppression est équivalent à un problème classique en informatique, la plus longue sous-séquence commune (que nous appellerons LCS). Par chance, c’est formidablement bien adapté à la programmation dynamique, et un de ses plus fameux exemples ! L’algorithme qui le résout prend en paramètres deux listes (avant / après), et parcourt simplement chaque paire d’éléments des deux listes, enregistrant les éléments identiques comme faisant partie d’une possible plus longue sous-séquence commune, et gardant en mémoire les opérations à effectuer pour obtenir cette sous-séquence, élégamment encodées sous la forme d’un chemin à travers la matrice. Quand c’est terminé, la dernière cellule nous permet de retracer notre chemin jusqu’à la première cellule, accumulant à chaque saut une opération du diff complet.

C’est à ce point génial que tout le monde l’utilise, de diff à git en passant par plein de logiciels de comparaison d’ADN. C’est aussi ce qu’utilisent toutes les bibliothèques que j’ai pu trouver. rfc6902-json-diff utilise une variante, la distance de Levenshtein, qui détecte les substitutions (littéralement équivalentes à un ajout et une suppression) . jsondiffpatch tente d’être malin en permettant d’indiquer à l’algorithme que deux objets sont identiques, afin de détecter les changements de position . Enfin, hashdiff intègre un algorithme de similitude qui dit à LCS que deux éléments sont identiques s’ils sont suffisamment similaires, mais il ne détecte pas les changements de position (et il est plutôt lent).

Fondamentalement, LCS ne possède que les opérations de base : insertion et suppression. Ce n’est pas avec cela qu’on peut facilement deviner qu’un élément a changé de place ! En fait, on irait mieux si le déplacement d’élément était une opération de base.

Par ailleurs, LCS est conçu pour des listes où la notion d’identité est sans ambiguïté. Même pour jsondiffpatch, faute de pouvoir trancher, on se retrouve à faire une comparaison triviale indice par indice ! Pour s’affranchir de cette contrainte, l’idée de hashdiff n’est pas mauvaise : comparons la similitude des éléments.

La similitude

Demander à cinq passants ce que la similitude signifie pour du JSON risque de donner huit opinions. Je ne prétends pas faire mieux qu’un micro-trottoir, mais j’ai tenté d’avoir une similitude qui marche bien avec des déplacements d’éléments.

Le but est de calculer arbitrairement la probabilité qu’un élément soit le résultat de la modification d’un autre.

  • Pour un objet, on prend la moyenne des similitudes des valeurs à clef égale. On oublie les renommages de clef.
  • Pour une liste, les éléments les plus similaires entre l’ancienne et la nouvelle liste sont sûrement compatibles, donc on prend la moyenne de la similitude maximale entre des paires d’éléments de chaque liste.
  • Pour un atome, on se rabat sur l’égalité des valeurs.

L’appariement

Obtenir un couplage idéal entre deux listes rappelle le problème d’affectation sur les graphes bipartis. Imaginez que vous maîtrisez une poignée de taxis d’un côté, et que vous devez servir des passagers disséminés dans votre ville. Le problème d’affectation veut minimiser le temps cumulé pris par chaque taxi pour arriver à un passager.

Dans notre cas, nous souhaitons minimiser le meilleur temps, et non le temps cumulé.

Parmi deux appariements de listes de deux éléments, l’un avec pour similitudes 0,9 et 0,1, l’autre avec pour similitudes 0,8 et 0,4, l’un des éléments n’a pas l’air d’avoir bougé ; on dirait qu’un élément a été supprimé et l’autre ajouté. Ceci étant donné, le couplage avec 0,9 est le plus logique, et c’est celui qu’on veut. Cependant, si nous cherchions à maximiser la similitude cumulée, nous obtiendrions l’appariement (0,8, 0,4), qui est inférieur.

Le problème d’affectation a une solution polynomiale en O(n^3), tandis que notre appariement en a une en O(n^2), ce qui signifie qu’en plus d’être mieux, c’est plus rapide.

En fait, ce problème est plus proche de celui des mariages stables. Cependant, ce dernier peut également donner des solutions moins optimales. Au lieu d’optimiser pour la plus haute similitude, il est content avec un couplage tel qu’aucun changement ne pourrait créer une paire avec une similitude plus haute que chaque élément de cette paire n’avait avant. En fonction de l’ordre des éléments dans nos listes, cela peut choisir un couplage plus pauvre pour nos objectifs.

Certains diffs que nous avons vus proposent déjà des opérations de déplacement (comme rfc6902-json-diff, jsondiffpatch). Mais l’appariement n’est pas seulement une affaire de détecter des déplacements ; il s’agit de détecter les déplacements les plus logiques. Le fond du problème avec LCS est sa dépendance à une égalité exacte. Notre appariement flou peut détecter l’égalité la plus probable. LCS cible une réponse avec le plus grand nombre d’éléments restant dans le même ordre ; notre appariement en cible une avec les déplacements les plus intuitifs.

Sa faiblesse est la qualité de son calcul de similitude, qui semble donner de bons résultats empiriques, et qui peut être améliorée par des heuristiques paramétrées par l’utilisateur.

Un indice, chez vous

Une fois que tous ces soucis sont derrière nous, on a de quoi s’amuser à convertir les indices que l’on obtient de l’appariement (qui viennent directement des listes source et destination) afin de pouvoir les utiliser lors d’un patch. En effet, lors de l’application du diff, nous prendrons chaque opération séparément et l’appliquerons dans l’ordre. Le patch s’attend à des indices décalés par les opérations précédentes.

Par exemple, [3, 2] diffé avec [1, 2, 3] détectera un appariement de l’indice 0 de la source à l’indice 2 de la destination, mais comme un élément est inséré au début de la liste avant le déplacement du 3, ce déplacement doit être exécuté entre l’indice 1 et 2, plutôt qu’entre l’indice 0 et 2.

Tout d’abord, vous devez exécuter toutes les suppressions de la liste, en commençant avec les suppressions les plus lointaines de la liste (pour éviter de décaler les suppressions suivantes). Vous en extrayez une fonction qui convertit les indices des éléments de la liste de là où ils étaient avant la suppression à là où ils se retrouvent après. Vous faites de même, à l’envers, pour les ajouts que l’on souhaite faire après avoir exécutés les suppressions et les déplacements.

Maintenant, nous avons besoin de réaliser deux choses.

  1. Les paires que l’on a forment un ensemble d’anneaux. Après tout, si ce qui était à la position i est envoyé à la position j, ce qui était à la position j ne peut pas y être resté. Donc i va à j, qui va à k, qui va à… eh bien, à un certain point, il doit revenir à i, parce que la liste est finie. En plus, nous savons que la source et la destination ont la même longueur.
  2. Chaque anneau va tourner d’exactement un cran. Quand il le fait, aucun autre élément de la liste ne va changer de position. Par conséquent, les opérations d’un anneau ne vont pas décaler les indices d’autres anneaux.

Bref. Les détails les plus subtils de l’implémentation sont simplement une histoire de détection de décalage d’indice au sein du même anneau. Ensuite, nous enregistrons les opérations : les suppressions en premier, puis les déplacements, et enfin les ajouts. Fini !

Le format

J’admets qu’il est ardu de faire un format qui satisfasse tout le monde. Ça ne m’empêchera pas de les juger.

Le format qu’utilise hashdiff pour les chemins JSON (ex. foo[0].bar) est maladroit pour les machines et pas si pratique à lire que ça pour les humains.

On dirait que le standard le plus utilisé est RFC6902. Malheureusement, il adopte RFC6901 (JSON Pointer), pour ses chemins (ex. /foo/0/bar).

Je n’ai pas la moindre idée de ce pour quoi RFC6902 n’a pas simplement choisi pour chemins une liste de nombres et de chaînes. C’est facile à lire pour nous autres humains, c’est plaisant à parcourir pour nos amies les machines (qui doivent sinon convertir le chemin dans ce format), et bien que cela réduise le nombre d’octets à la sérialisation, RFC6902 est loin d’être un format dense d’entrée de jeu. Enfin, JSON Pointer est contraint de jouer avec un nouveau système d’échappement bancal : les barres obliques sont traduites par un ~1 et les tildes par un ~0.

Mais c’est le standard… donc j’ai fermé les yeux sur ses faiblesses et je l’ai utilisé.

La route est longue mais sans encombre

Comme j’aurais aimé tomber dessus lorsque j’ai recherché une bibliothèque appropriée, j’ai publié ce nouvel algorithme sous la forme d’une gemme, dont le projet est ici.

Ce projet grouille d’améliorations possibles. Sans effort, je trouve :

  • Optionellement faire un LCS,
  • Differ les chaînes de caractères,
  • Une sortie SVG.

Épilogue

Cet algorithme de diff m’a permis de détecter trois bugs problématiques qui n’ont ainsi causé de tort à personne. Lorsque nous avons basculé sur le nouveau moteur, nous avons graduellement augmenté le pourcentage d’utilisateurs. Au fur et à mesure, nous sommes devenus de plus en plus confiants sur nos résultats, jusqu’à atteindre 100%.

Nous avons remplacé le moteur dans un train à pleine vitesse. Personne n’a remarqué !