テキストエディタのデータ構造

• 自分だけのテキストエディタを作るために、テキスト用のデータ構造を自作していく過程。
• テキストエディタは巨大なファイルの編集や、マルチカーソル、元に戻す/やり直しなどさまざまな機能のため、その構造を作るのが非常に難しい。
• そのため、データ構造に求められる機能は次のとおり。
  • 効率的な挿入/削除
  • 効率的な undo/redo
  • UTF-8 エンコーディングを利用できること
  • 効率的なマルチカーソル編集
• Gap Buffer は実装が簡単だが、undo とマルチカーソル機能の実装が非常に難しい。
• Rope は大きなファイルを小さな単位に分割して編集できるため効率的だが、undo 機能のためにはオーバーヘッドが大きくなり、メモリ使用量も想定以上に増える可能性がある。
• Piece Table は Microsoft Word で使われたほど効率的な構造だが、編集回数が多くなると性能が低下し、undo のためにメモリ使用量が増えることがある。
• Piece Tree は上記の欠点をすべて解決するために VSCode チームが実装した、テキストエディタ向けの最良のデータ構造。
  • Rope と Piece Table の長所だけを選んで実装している。
  • 断片同士の接続に RB Tree を使っているため、編集回数が多くても依然として効率的。
  • ただし VSCode チームの実装は不変データ構造ではないため、undo 機能には多少の非効率がある。
• データ構造に不変性を追加し、すべての問題を解決した新しい Piece Tree を実装することにした。
  • 従来の RB Tree には不変性を持たせられないため、Bartosz Milewski が実装した不変 RB Tree を参考に実装を開始。
  • VSCode チームが実装した構造との違いは次のとおり。
    • エディタが Carriage Return 文字を考慮しなければならない場面は少ないため、CRLF は別途記録しない。
    • デバッグのため、バッファ全体をイテレータのような形で確認できる API を追加。
    • データ構造が不変なので、undo/redo は非常に簡単。
  • 削除機能の実装が最も難しかったが、最終的には実装に成功した。
• 新たに作成したデータ構造を fredbuf という名前で公開した。

[junghan0611]

おお、ありがとうございます。こんな貴重な情報を！ Emacsをきちんと使い始めてから、テキストエディタそのものにとても興味が湧いてきました。原文もじっくり読んでみますね！ :-)

[cosine20]

詳しく要約してくださってありがとうございます。テキストエディタのデータ構造はどう実装するのだろうかと一度は考えたことがありますが、このようなデータ構造が使われているのですね。