- Ein Einblick in den Prozess, eine eigene Textdatenstruktur zu entwickeln, um einen eigenen Texteditor zu bauen.
- Texteditoren sind aufgrund verschiedenster Funktionen wie dem Bearbeiten riesiger Dateien, Multi-Cursor sowie Undo/Redo sehr schwer strukturell umzusetzen.
- Daraus ergeben sich die folgenden Anforderungen an die Datenstruktur.
- effizientes Einfügen/Löschen
- effizientes Undo/Redo
- Unterstützung für UTF-8-Kodierung
- effiziente Bearbeitung mit mehreren Cursorn
- Gap Buffer ist einfach zu implementieren, macht aber Undo und Multi-Cursor-Funktionen sehr schwer umsetzbar.
- Rope ist effizient, weil große Dateien in kleine Teile zerlegt und bearbeitet werden können, aber für die Undo-Funktion entsteht viel Overhead, und der Speicherverbrauch kann stärker steigen als erwartet.
- Piece Table ist eine so effiziente Struktur, dass sie sogar in Microsoft Word verwendet wurde, aber bei vielen Bearbeitungen sinkt die Leistung, und für Undo kann der Speicherverbrauch steigen.
- Piece Tree ist die beste Datenstruktur für Texteditoren, die das VSCode-Team implementiert hat, um alle oben genannten Nachteile zu beheben.
- Sie vereint nur die Vorteile von Rope und Piece Table.
- Da zur Verbindung der Fragmente ein RB Tree verwendet wird, bleibt sie auch bei vielen Bearbeitungen effizient.
- Allerdings ist die vom VSCode-Team implementierte Version keine unveränderliche Datenstruktur und hat deshalb bei Undo eine gewisse Ineffizienz.
- Daher wurde beschlossen, einen neuen Piece Tree zu implementieren, der durch Unveränderlichkeit alle Probleme löst.
- Da ein traditioneller RB Tree nicht unveränderlich gemacht werden kann, begann die Implementierung mit Bezug auf den unveränderlichen RB Tree von Bartosz Milewski.
- Die Unterschiede zur vom VSCode-Team implementierten Struktur sind wie folgt.
- Da ein Editor nur selten das Carriage-Return-Zeichen berücksichtigen muss, wird CRLF nicht separat gespeichert.
- Für das Debugging wurde eine API hinzugefügt, mit der sich der gesamte Buffer in einer iteratorähnlichen Form prüfen lässt.
- Da die Datenstruktur unveränderlich ist, sind Undo/Redo sehr einfach.
- Das Implementieren der Löschfunktion war am schwierigsten, wurde aber schließlich erfolgreich abgeschlossen.
- Die neu entwickelte Datenstruktur wurde unter dem Namen fredbuf veröffentlicht.
2 Kommentare
Oh! Vielen Dank. Was für wertvolle Informationen! Seit ich angefangen habe, Emacs richtig zu nutzen, interessiere ich mich immer mehr für Texteditoren an sich. Ich werde mir auch das Original in Ruhe ansehen! :-)
Vielen Dank für die ausführliche Zusammenfassung. Ich habe mich auch schon einmal gefragt, wie die Datenstrukturen eines Texteditors implementiert werden, und offenbar kommen dafür solche Datenstrukturen zum Einsatz.