Éditeur concurrent : parcours OT avancé

Deux personnes partent du texte ab. Alice insère X entre les deux lettres, Bob supprime a. Chacun voit immédiatement son édition. Comment intégrer celle de l’autre pour que tous deux finissent avec Xb ? Ce projet étudie les transformations opérationnelles, ou OT : nous adaptons une édition à ce qui a changé depuis sa création, au lieu de donner une identité à chaque caractère comme le fait le CRDT.

Ce parcours avancé est une alternative au CRDT guidé. Dans le CRDT, les caractères gardent des identifiants stables et nous fusionnons des états. Ici, les clients échangent des opérations et un serveur leur donne un ordre commun. Les deux projets ont un périmètre pédagogique différent ; ils ne constituent pas deux étapes obligatoires d’un même travail.

Vous commencez en semi-autonomie en AP9, avec un démarrage accompagné en cours, puis terminez à la maison. Le projet choisi est noté ; les modalités et l’échéance seront précisées avant le lancement, et les paliers ne sont pas un barème. Le démarrage en cours permet d’aborder un algorithme exigeant, avec des outils de vérification déjà fournis.

Téléchargez le squelette editeur-ot. Il contient une interface avec trois copies, le serveur, les files de messages, les accusés de réception et le buffer d’édition. Tout le HTML, le CSS et le JavaScript sont écrits. Votre travail porte sur cinq clauses Elixir, les expériences et vos propres tests. Le README du projet est le guide complet à garder ouvert à côté de l’éditeur ; cette page explique le parcours.

Démarrer sans prérequis web

Dans le dossier extrait :

mix deps.get
mix test test/operation_test.exs test/web_test.exs
mix run --no-halt

Ouvrez localhost:4010. Les trois copies commencent avec ab. Vous pouvez déjà saisir du texte et lire la structure des messages. Une commande qui atteint une partie incomplète affiche une erreur « à compléter » sans perdre l’état précédent. Pour reprendre après une modification, arrêtez l’application (Ctrl-C, puis a), relancez-la et rechargez la page.

mix test seul doit encore échouer sur les insertions à écrire. Les tests des outils fournis passent déjà. Le README explique les commandes des paliers et comment changer de port si nécessaire.

Une position appartient à une version du texte

Alice produit aXb, Bob produit b. Si l’insertion d’Alice arrive après la suppression de Bob, l’indice 1 désigne maintenant la fin du texte : insérer sans transformation donnerait bX. Il faut déplacer l’insertion à l’indice 0.

La fonction TextOT.transform(left, right) reçoit deux opérations définies sur le même document de départ. Elle renvoie {:ok, {left_after_right, right_after_left}}. Le contrat est :

appliquer left, puis right_after_left
  donne le même texte que
appliquer right, puis left_after_right

Ce losange est une propriété locale. Deux opérations de même longueur ne proviennent pas nécessairement de la même version : le protocole doit fournir les bons contextes. Nous vérifierons donc aussi les clients, les révisions et les échanges, au-delà de cette égalité.

Étape 0 : lire une opération

Une opération parcourt toute sa source à l’aide de trois composants :

Pour insérer X entre a et b, Alice produit :

[{:retain, 1}, {:insert, ["X"]}, {:retain, 1}]

Bob produit [{:delete, 1}, {:retain, 1}]. Prédisez leurs longueurs de départ et d’arrivée, puis vérifiez-les avec les helpers Operation.base_length/1, Operation.target_length/1 et Operation.apply/2. Cette dernière renvoie par exemple {:ok, "b"} pour l’opération de Bob sur ab.

La représentation emploie des comptes strictement positifs et des insertions non vides. La normalisation fournie fusionne les composants voisins de même nature. Pour limiter les questions annexes, le texte admis est l’ASCII imprimable et le saut de ligne. Accents et emoji ne font pas partie de cette version.

Palier 1 : transformer les insertions

Ouvrez lib/ot_editor/text_ot.ex. La validation, la récursion sur deux listes et le découpage en morceaux de même longueur sont fournis. Vous complétez d’abord les deux clauses de walk/2 qui rencontrent une insertion.

Une insertion ne consomme rien de la source. Après l’avoir traitée, poursuivez avec sa queue, en gardant l’autre liste inchangée. Quels composants faut-il ajouter aux deux résultats pour préserver cette insertion et la traverser dans l’autre chemin ? Le README détaille le contrat de cette étape.

En cas d’insertions simultanées au même endroit, le paramètre de gauche a priorité. L’ordre des clauses rend ce choix explicite. Insérer XY à gauche et Z à droite au milieu de ab doit donner aXYZb.

mix test --only palier_1

Ajoutez un essai dans le texte vide et expliquez l’effet d’un échange des arguments. La convention porte sur l’ordre de transformation, pas sur l’heure réelle de la frappe.

Palier 2 : transformer les suppressions

Les trois clauses restantes de pair/2 comparent une suppression avec une conservation, ou deux suppressions. Le cas retain/retain est déjà écrit. Les composants ont toujours la même longueur : le découpage fourni laisse le reste dans la liste pour l’appel suivant.

Après l’autre opération, les caractères visés existent-ils encore ? Une suppression commune ne doit pas effacer deux fois les mêmes caractères. Sur abcdef, supprimer bcd d’un côté et cde de l’autre laisse af. Une insertion située dans une zone supprimée est conservée avec nos règles : construisez un exemple qui rend ce choix visible.

mix test --include palier_2

Le test du losange énumère des petites opérations sur une même source. Gardez un exemple lisible pour chaque difficulté : début et fin, position identique, suppressions recouvrantes et texte vide. Un ensemble de tests réussi cherche des contre-exemples ; il ne remplace pas une preuve générale.

Palier 3 : comprendre le protocole fourni

Valider une saisie la rend visible dans sa copie. Une seule opération peut être en attente d’accusé par client ; les validations suivantes sont composées dans un buffer. Composer concerne des éditions successives d’un même client. Transformer concerne des éditions concurrentes ; ces deux outils ont des rôles différents.

Deux mots du protocole : une révision est le numéro d’ordre que le serveur attribue à chaque opération acceptée, et un client indique donc sur quelle révision son édition a été faite ; un accusé de réception est le retour de sa propre opération, une fois ordonnée par le serveur.

« Envoyer au serveur » livre une opération avec sa révision de départ. Le serveur la transforme contre les éditions déjà acceptées depuis cette révision, l’applique, puis ajoute une nouvelle révision à chaque file descendante. « Recevoir la prochaine révision » intègre un événement, dans l’ordre serveur. Le propre événement du client sert d’accusé : il sait alors que son édition est ordonnée, et son buffer peut partir.

Le serveur place l’opération déjà acceptée à gauche de transform/2. Le client place lui aussi l’opération distante déjà ordonnée à gauche, face à sa propre opération en attente, puis face à son buffer. Le code fourni garde les contextes compatibles et refuse les doublons ainsi que les révisions hors ordre.

Expérience A : qui le serveur accepte-t-il d’abord ?

Depuis ab, Alice valide aXb et Bob valide b. Envoyez Alice, puis Bob ; recevez les révisions chez tout le monde. Le texte final doit être Xb. Conservez les opérations avant et après transformation.

Recommencez avec aXb chez Alice et aYb chez Bob. Si le serveur accepte Alice d’abord, le résultat est aXYb. S’il accepte Bob d’abord dans une nouvelle expérience, il devient aYXb. Chaque expérience converge : pourquoi cela n’impose-t-il pas un résultat commun aux deux expériences ?

Expérience B : plusieurs éditions avant l’accusé

Depuis ab, Alice valide successivement aXb, aXYb, puis aXYZb, sans échange. Bob valide b et Charlie valide ab!. Envoyez Bob, puis faites recevoir cette révision par Alice : son texte devient XYZb. Envoyez Charlie ; après réception chez Alice, elle voit XYZb!.

Terminez les échanges. Les trois copies et le serveur doivent afficher XYZb!. Quatre opérations ont été acceptées, dont le buffer d’Alice ; les files et buffers sont vides. Le README donne la même trace dans IEx avec les résultats attendus, sans dépendre du navigateur.

mix test --include palier_2 --include palier_3

Cette commande lance tous les tests. La page permet de retenir les échanges à volonté ; elle conserve cependant l’ordre des révisions sur chaque connexion. La simulation vit dans une seule VM et ne nécessite ni réseau distribué ni WebSocket à programmer.

Palier 4 : vos scénarios et votre analyse

Ajoutez test/personal_scenarios_test.exs. Testez une suppression recouvrante mêlée à une insertion, puis trois clients dont l’un édite après avoir reçu une édition distante mais avant son propre accusé. Prédisez les résultats avant l’exécution et vérifiez aussi les révisions et les buffers, pas seulement les textes affichés. Expliquez quelle erreur plausible chaque scénario détecte.

Dans COMPTE-RENDU.md, gardez les commandes exécutées, un losange complet, les traces des expériences A et B, vos deux scénarios et la justification des cinq clauses. Expliquez pourquoi les révisions et les identifiants restent nécessaires quand le losange fonctionne. En fin de séance, notez le prochain petit essai pour la poursuite à la maison.

Le TP garde les états en mémoire, un serveur unique et des files fiables. Il ne traite ni reconnexion, ni persistance, ni curseurs, ni annulation collaborative. La convergence n’est pas une preuve générale de préservation de l’intention humaine. La démonstration OT de Tim Baumann et la machine d’états d’ot.js permettent de comparer les idées après votre propre implémentation.