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

Text Editor: Data Structures – averylaird.com

1998年、Charles Crowleyという人がテキストエディタの実装で使われるデータ構造を研究した論文を出している

He concluded that – from a basis of speed, simplicity, and structure – the piece table was the leading method.

ただpiece tableの実装は複雑で、心がくじけそうになるのも確かだと述べているので、がんばりましょう。


この記事に対する指摘。

Text Editor: Data Structures | Hacker News

  • まずxi editorの作者がコメントをしている。実装にropeを使っている、たしかに単純ではないが、一回作れば実装など気にせず使い回せるのでこれでいいと思っている。もっともgap bufferはシンプルさでは圧勝といえるだろう。あとCrowleyの論文はropeについては考察してない。piece tableについても言及しているが、何を言っているか理解できなかった。
  • 別のコメント。そもそもmemcpy()/memove()は現代的なマシンならGB/sという速度で動く。なので、配列でテキストを保持するのは最悪ではない。テキストエディタのデータ構造を考えるは後回しで構わない。

neru.md

XNUカーネルのソースが公開

XNUはOS XiOSでつか使われているDarwin OSの一部、とのこと。

apple/darwin-xnu: The Darwin Kernel (mirror)


redditではこのコミットログが人気コメントとなっている。

-# vim turds
+# vim swap files
 *~
 *.swp

.gitignoreに書かれた"vim turd"(vimのクソ)というコメントである。やっぱswpファイル邪魔って思うよね…

Apple open-sources iOS kernel : programming

しかしコミットメッセージがまともでないので全くコードに降りていく気持ちになれない。

Microというテキストエディタについて

Micro - Home

Microは、Golangで書かれたターミナルベースのテキストエディタである。モダンなターミナルの機能を最大限利用している、プラグインマネージャが最初から入っている、依存性のない静的バイナリ、といった特徴が謳われている。

主にUnix系OSで使われる、nanoという単純なエディタがあるが、その後発を狙っている(ネーミングからしてまんまだが)。

しかし、microの面白いところは別にあると私は考える。

このエディタ、コードベースが非常に小さいのである。

clocでカウントすると全体で12673行。ただし、runtime.goというファイルが3100行程度あり、これはほとんどボイラープレートなので無視してよい。読むべきコードは1万行弱だ。機能もよく分離されており、実装は愚直で非常に読みやすい*1。これは教育的なエディタなのだ。

もっとも、このコード読めそう…!と私に思わせてくれた背景にはkiloという1000行で書かれたCエディタを写経しているから、というのがあると思う。kiloは標準以外のライブラリへの依存関係を排除していたが(ncurseすらなし)、microはターミナルの描画管理にtcellというライブラリを使っている。精読を行う上ではtcellの使い方を理解できるかがキモだろう。


1000行程度のプログラムがきっちり読めるようになってきた。今度は1万行程度のプログラムを読めるのではないかと思えてきた。いまはまだ登山口から頂上を見上げているだけだが、少し楽しい場所に向かっていると思う。

*1:もっとも、筆者はGolangを知らないので今は雰囲気で読んでいる