Les structures de données des éditeurs de texte

• Un parcours pour créer soi-même une structure de données textuelle afin de développer son propre éditeur de texte.
• Concevoir la structure d’un éditeur de texte est très difficile en raison de la variété des fonctionnalités, comme l’édition de fichiers volumineux, les curseurs multiples ou encore l’annulation/rétablissement.
• Les exigences pour cette structure de données sont donc les suivantes.
  • insertion/suppression efficaces
  • annulation/rétablissement efficaces
  • prise en charge de l’encodage UTF-8
  • édition efficace avec curseurs multiples
• Le Gap Buffer est simple à implémenter, mais il est très difficile d’y intégrer l’annulation et les curseurs multiples.
• Le Rope est efficace car il permet de modifier de gros fichiers en les divisant en petits morceaux, mais l’overhead lié à l’annulation peut être important et l’utilisation mémoire peut augmenter davantage que prévu.
• La Piece Table est une structure très efficace, au point d’avoir été utilisée dans Microsoft Word, mais ses performances peuvent se dégrader en cas de nombreuses modifications, et la mémoire consommée pour l’annulation peut augmenter.
• Le Piece Tree est la meilleure structure de données pour les éditeurs de texte, implémentée par l’équipe de VSCode pour résoudre tous les inconvénients ci-dessus.
  • Il combine uniquement les avantages du Rope et de la Piece Table.
  • Comme il utilise un arbre rouge-noir (RB Tree) pour relier les fragments, il reste efficace même lorsqu’il y a beaucoup de modifications.
  • Toutefois, la version implémentée par l’équipe de VSCode n’est pas une structure de données immuable, ce qui introduit une légère inefficacité dans la fonctionnalité d’annulation.
• Il a donc été décidé d’implémenter un nouveau Piece Tree ajoutant l’immuabilité à la structure de données pour résoudre tous ces problèmes.
  • Comme les arbres rouge-noir traditionnels ne permettent pas l’immuabilité, l’implémentation a commencé en s’appuyant sur l’arbre rouge-noir immuable conçu par Bartosz Milewski.
  • Voici les différences avec la structure implémentée par l’équipe de VSCode.
    • Comme les cas où l’éditeur doit prendre en compte le caractère Carriage Return sont rares, les CRLF ne sont pas enregistrés séparément.
    • Une API a été ajoutée pour permettre d’inspecter l’ensemble du buffer sous une forme de type itérateur afin de faciliter le débogage.
    • Comme la structure de données est immuable, l’annulation/le rétablissement deviennent extrêmement simples.
  • L’implémentation de la suppression a été la partie la plus difficile, mais elle a finalement abouti.
• La nouvelle structure de données a été publiée sous le nom de fredbuf.

[junghan0611]

Oh ! Merci. Quelle information précieuse ! Depuis que j’ai commencé à vraiment utiliser Emacs, je m’intéresse beaucoup plus à l’éditeur de texte lui-même. Je vais aussi lire attentivement le texte original ! :-)

[cosine20]

Merci pour ce résumé détaillé. Je me suis déjà demandé au moins une fois comment les structures de données d’un éditeur de texte étaient implémentées, et c’est donc ce type de structure de données qui est utilisé.