Comment les éditeurs de texte sont-ils généralement mis en œuvre ?

Question

Cette question va probablement me donner l'impression que je ne sais pas grand-chose. C'est parce que c'est le cas.

Je me disais simplement que si j'étais hypothétiquement intéressé par la conception de mon propre contrôle d'interface graphique d'éditeur de texte, widget ou autre (ce qui n'est pas le cas), comment ferais-je ?

La tentation pour un novice comme moi serait de stocker le contenu de l'éditeur de texte sous la forme d'une chaîne de caractères, ce qui semble assez coûteux (je ne suis pas très au fait des différences d'implémentation des chaînes de caractères d'un langage ou d'une plate-forme à l'autre, mais je sais qu'en .NET, par exemple, elles sont immuables, de sorte qu'une manipulation fréquente telle que celle que vous devriez prendre en charge dans un éditeur de texte entraînerait un gaspillage énorme, en construisant une instance de chaîne de caractères après l'autre dans une succession très rapide).

On peut supposer qu'une structure de données mutables contenant du texte est utilisée à la place, mais il me semble difficile de déterminer à quoi cette structure pourrait ressembler. L'accès aléatoire serait une bonne chose (je penser ), mais je m'interroge ensuite sur le coût de la navigation, par exemple, au milieu d'un énorme document et de la saisie immédiate du texte. Encore une fois, l'approche novice (disons que vous stockez le texte sous la forme d'un tableau de caractères redimensionnable) conduirait à de très mauvaises performances, je pense, car chaque caractère tapé par l'utilisateur entraînerait un énorme volume de données à "déplacer".

Si je devais émettre une hypothèse, je supposerais que les éditeurs de texte utilisent une sorte de structure qui divise le texte en morceaux plus petits (des lignes, peut-être ?), qui comprennent individuellement des tableaux de caractères avec accès aléatoire, et qui sont eux-mêmes accessibles de manière aléatoire en tant que morceaux discrets. Même que Il semble toutefois qu'il s'agisse d'une simplification excessive et monstrueuse, si tant est qu'elle soit proche de la réalité.

Bien entendu, je me rends compte qu'il n'y a peut-être pas être Il est possible que les éditeurs de texte soient implémentés d'une manière "standard" ; cela peut varier considérablement d'un éditeur à l'autre. Mais je me suis dit qu'étant donné qu'il s'agit clairement d'un problème qui a été abordé de très nombreuses fois, peut-être qu'une approche relativement commune est apparue au fil des ans.

Quoi qu'il en soit, j'aimerais savoir si quelqu'un a des connaissances sur le sujet. Comme je l'ai dit, je ne cherche absolument pas à écrire mon propre éditeur de texte ; je suis juste curieux.

Answer 1

Une technique courante (en particulier dans les anciens éditeurs) s'appelle le tampon divisé. En gros, vous "séparez" le texte en deux parties : tout ce qui se trouve avant le curseur et tout ce qui se trouve après le curseur. Tout ce qui se trouve avant le curseur est placé au début du tampon. Tout ce qui suit est placé à la fin de la mémoire tampon.

Lorsque l'utilisateur tape du texte, celui-ci s'insère dans l'espace vide entre les deux, sans déplacer de données. Lorsque l'utilisateur déplace le curseur, vous déplacez la quantité de texte appropriée d'un côté à l'autre de la "coupure". En règle générale, il y a beaucoup de déplacements dans une même zone, de sorte que vous ne déplacez généralement que de petites quantités de texte à la fois. La plus grande exception est la possibilité d'aller à la ligne xxx.

Charles Crowley a écrit un ouvrage beaucoup plus complet discussion sur le sujet . Vous pouvez également consulter L'art de l'édition de texte qui couvre les tampons fractionnés (et d'autres possibilités) de manière beaucoup plus approfondie.

Answer 2

Pour plus de ressources, vous pouvez lire comment fonctionnent les éditeurs de texte ?

Answer 3

Il y a quelque temps, j'ai écrit mon propre éditeur de texte en Tcl (en fait, j'ai volé le code quelque part et je l'ai étendu au-delà de toute reconnaissance, ah les merveilles de l'open source).

Comme vous l'avez mentionné, effectuer des opérations sur des chaînes de caractères très, très grandes peut être coûteux. C'est pourquoi l'éditeur divise le texte en chaînes plus petites à chaque saut de ligne (" \n " ou " \r " ou " \r\n "). Il ne me reste donc plus qu'à éditer de petites chaînes au niveau de la ligne et à effectuer des opérations de liste pour passer d'une ligne à l'autre.

L'autre avantage est qu'il s'agit d'un concept simple et naturel. Mon esprit considère déjà que chaque ligne de texte est séparée, ce qui est renforcé par des années de programmation où les nouvelles lignes sont stylistiquement ou syntaxiquement significatives.

Le fait que mon éditeur de texte soit utilisé comme un éditeur de programmation est également un atout. Par exemple, j'ai implémenté la coloration syntaxique mais pas le retour à la ligne. Dans mon cas, il y a donc une correspondance 1:1 entre les nouvelles lignes dans le texte et les lignes dessinées à l'écran.

Si vous voulez jeter un coup d'œil, voici le code source de mon éditeur : http://wiki.tcl.tk/16056

Ce n'est pas un jouet. Je l'utilise quotidiennement comme mon éditeur de texte standard, à moins que le fichier ne soit trop volumineux pour tenir dans la RAM (sérieusement, quel fichier texte l'est ? Même les romans, qui font généralement 4 à 5 Mo, tiennent dans la RAM. Je n'ai vu que des fichiers journaux atteindre des centaines de Mo).

Answer 4

En fonction de la quantité de texte qui doit se trouver dans l'éditeur à un moment donné, une approche basée sur une seule chaîne de caractères pour l'ensemble de la mémoire tampon conviendrait probablement. Je pense que le Bloc-notes fait cela - vous avez déjà remarqué à quel point l'insertion de texte dans un gros fichier est plus lente ?

Le fait d'avoir une chaîne par ligne dans une table de hachage semble être un bon compromis. Cela rendrait la navigation vers une ligne particulière et l'effacement/collage efficaces sans trop de complexité.

Si vous souhaitez mettre en œuvre une fonction d'annulation, vous aurez besoin d'une représentation qui vous permette de revenir aux versions précédentes sans avoir à stocker 30 copies de l'ensemble du fichier pour 30 modifications, même si, là encore, cela conviendrait probablement si le fichier était suffisamment petit.

Answer 5

La méthode la plus simple consiste à utiliser une classe de tampon de chaîne de caractères fournie par le langage. Même un simple tableau d'objets char ferait l'affaire à la rigueur.

L'ajout, le remplacement et la recherche de texte sont alors relativement rapides. D'autres opérations sont bien sûr potentiellement plus longues, l'insertion d'une séquence de caractères au début de la mémoire tampon étant l'une des actions les plus coûteuses.

Cependant, cela peut être parfaitement acceptable en termes de performances pour un cas d'utilisation simple.

Si le coût des insertions et des suppressions est particulièrement important, je serais tenté d'optimiser en créant une classe de tampon qui maintiendrait en interne une liste d'objets tampons. Toute action (à l'exception d'un simple remplacement) qui ne se produirait pas à la fin d'un tampon existant entraînerait la division du tampon concerné au point correspondant, de sorte que le tampon pourrait être modifié à sa fin. Cependant, l'enveloppe extérieure conserverait la même interface qu'un simple tampon, de sorte que je n'aurais pas à réécrire, par exemple, mon action de recherche.

Bien sûr, cette approche simple aboutirait rapidement à un tampon extrêmement fragmenté, et j'envisagerais d'avoir une sorte de règle pour fusionner les tampons lorsque c'est nécessaire, ou pour différer la division d'un tampon dans le cas, par exemple, de l'insertion d'un seul caractère. Peut-être que la règle serait que je n'ai jamais que deux tampons internes au maximum, et que je les fusionne avant d'en créer un nouveau - ou lorsque quelque chose me demande une vue de tout le tampon à la fois. Je n'en suis pas sûr.

En fait, je commencerais simplement, mais j'accèderais au tampon mutable par le biais d'une interface soigneusement choisie, et je jouerais avec l'implémentation interne si le profilage m'en montrait le besoin.

Cependant, je définitivement ne commencerait pas avec des objets immuables de type String !