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
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| CRDT de séquence | un CRDT pour une liste ordonnée, comme un texte | |
| Indice | la place d’un caractère comptée depuis le début | 0, 1, 2 |
| Identifiant de caractère | un nom qu’aucun autre caractère ne porte | (6, 'ben') |
| Pierre tombale | un caractère supprimé gardé comme marque | |
| Entrelacement | deux 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
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
docker exec jupyter python3 steps/text.pyAffiché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é
| Moment | Ana | Ben |
|---|---|---|
| Partagé | Hello | Hello |
| Hors ligne | Hello world | Oh, ello (H supprimé) |
| Après la synchro | Oh, ello world | Oh, ello world |
| Stocké | une pierre tombale, le H | une 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
docker exec jupyter python3 steps/interleave.pyAffiché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é.