Plus facile à lire avec un fond crème, une teinte, plus de contraste ou un texte plus grand ? Choisissez vos couleurs et votre texte, une fois pour toutes les pages.

Leçon gratuite

Un texte qui fusionne : les CRDT de séquence

Après cette leçon: Je peux fusionner deux répliques d’un texte dont les caractères portent des positions.

Leçon de 70 min2 commandesLab CRDT : synchro local-first, compteurs et texte en Python

Deux personnes, une phrase

Deux étudiants rédigent un rapport de groupe dans un document partagé. L’un corrige un mot au début pendant que l’autre ajoute une phrase à la fin, tous deux hors ligne.

Le texte est la donnée la plus difficile à fusionner : chaque caractère a une place, et les places bougent dès que quelqu’un tape.

À la fin de cette leçon

Remarque

Je peux fusionner deux répliques d’un texte dont les caractères portent des positions.

Mots-clés

MotCe que ça veut direExemple
CRDT de séquenceun CRDT pour une liste ordonnée, comme un texte
Indicela place d’un caractère comptée depuis le début0, 1, 2
Identifiant de caractèreun nom qu’aucun autre caractère ne porte(6, 'ben')
Pierre tombaleun caractère supprimé gardé comme marque
Entrelacementdeux mots tapés en même temps qui se mélangent lettre par lettre

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

Un indice change de sens

La façon simple d’envoyer une édition, c’est « insérer a à l’indice 0 » ou « supprimer l’indice 3 ». Mais un indice se compte depuis le début d’un texte qui a déjà changé sur l’autre réplique.

Si Ana insère au début, chaque caractère suivant recule d’une place. Le « supprimer l’indice 3 » de Ben désigne alors un autre caractère.

À vous : deux éditions par indice

Code: python
def appliquer(texte, edition):
    genre, indice, car = edition
    if genre == "inserer":
        return texte[:indice] + car + texte[indice:]
    return texte[:indice] + texte[indice + 1:]

depart = "chat"
ana = ("inserer", 0, "a")      # Ana tape a au début : "achat"
ben = ("supprimer", 3, "")     # Ben supprime le t, à l’indice 3 : "cha"

# Chaque réplique applique sa propre édition, puis celle de l’autre.
chez_ana = appliquer(appliquer(depart, ana), ben)
chez_ben = appliquer(appliquer(depart, ben), ana)
print("Ana voit :", chez_ana)
print("Ben voit :", chez_ben)
# Quel caractère Ben voulait-il supprimer ? Et la copie d’Ana ?

Idée 1 : une position entre voisins

On donne à chaque caractère un numéro de position, et on trie par ce numéro. Pour taper entre les positions 0,4 et 0,5, on choisit 0,45. Rien d’autre ne bouge.

Les vrais systèmes utilisent une liste d’entiers, comme [4, 5], pour qu’il y ait toujours de la place pour un de plus. Le nom de réplique départage une égalité. C’est l’idée de Logoot.

Idée 2 : un identifiant et un parent

RGA donne à chaque caractère un identifiant, fait d’un compteur et du nom de réplique, et retient après quel caractère il a été tapé. On lit le texte en partant du début, les enfants les plus récents d’abord.

Une suppression marque seulement le caractère comme pierre tombale, car une autre réplique peut encore taper après lui. Le fichier rga.py du labo fonctionne ainsi.

Fusionner deux éditions d’une même ligne

Commande
docker exec jupyter python3 steps/text.py

Affichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.

Exemple travaillé : ce que le labo a affiché

MomentAnaBen
PartagéHelloHello
Hors ligneHello worldOh, ello (H supprimé)
Après la synchroOh, ello worldOh, ello world
Stockéune pierre tombale, le Hune pierre tombale, le H

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

Quand deux mots se mélangent

Ana tape « cat » et Ben tape « dog » au même endroit, au même moment. Avec des positions entre voisins, les deux choisissent les mêmes numéros, et le nom de réplique trie chaque paire.

Les lettres alternent. RGA attache chaque lettre à la précédente, donc chaque mot reste entier.

Voir deux mots s’entrelacer

Commande
docker exec jupyter python3 steps/interleave.py

Affichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.

Erreur fréquente

Attention

On croit souvent que si chaque réplique finit avec le même texte, la fusion est juste. « cdaotg » est identique sur chaque réplique, et personne ne l’a tapé. Converger est nécessaire, mais un bon CRDT de texte garde aussi ensemble ce que chaque personne a tapé.

À propos de ce labo et de sa source: Lab CRDT : synchro local-first, compteurs et texte en Python

Vous enseignez à une classe ? Proposez ce module à vos étudiants avec un guide de l'enseignant, des devoirs corrigés et un laboratoire pour chaque étudiant.