自作テキストエディタ(OTZEditorコントロール)の行管理方法

さくさくエディタの作者さんの記事を読んで、テキストの持ち方を改めて考えてみたんですがテキストを保持する方法として「配列」、「双方向リスト」、「ギャップバッファ」が一般的とのこと。自作エディタは何なのか？って話です。う～ん。よくわからないです。こんなやつが作っています…。

 で、どう持ってんの？

論理行の持ち方

最初に論理行とは改行文字まで区切られた文字のことです。自作エディタというか、OTZEditorコントロールは改行で区切られる1行を改行も含めて StringBuilder で保持しています。

そして、その行を List に追加して管理しています。というか実装当初から無知すぎてこの方法でしか考えていませんでした。 StringBuilder もバッファが足らなくなったら拡張するっぽいので、ある意味ギャップバッファになるんでしょうか…。

Listは行の特定は高速ですが、行追加や行削除は遅いと言われています。これは行追加すると追加行以降のインデックスを更新する必要があるからです。そのため、テキストを100万行持っていて1行目に追加する場合は遅いですが、逆に100万1行目に追加する場合は更新する行が少ないため高速です。

物理行の持ち方

次に物理行が画面上に表示している行のことのようです。折り返している行は物理行になります。ただ、私は逆で物理行が改行単位で、論理行が画面と思っているんでいつも混乱します。

ほとんどのエディタは折り返した時点でテキストも折り返しているんでしょうか？そのへんが分からなくてこっちは、めちゃくちゃ悩みました。

多分、全行折り返すとめちゃくちゃ遅くなりそうだったので、最初から差分で折り返すことを考えました。最終的にテキストの持ち方は下記になりました。

例えば、下記のようなテキストを画面の右端で折り返した場合についてです。

1行目：あいうえおかきくけこさしすせそ
2行目：たちつてと

折り返していないときは論理行(Lines)だけにデータがあって、折り返すと画面に表示している行だけ物理行(WrapLines)を作るようにしています。そして画面に表示する時は物理行に保持している折り返し情報を使って論理行を表示しています。この方法でかなり高速に折り返すことができました。1行32万文字の場合を除いてね。

テキストエディタを作成すると、とにかく無駄な処理を無くして実装しないと使い物にならないことを痛感します。キー入力やマウス操作で直ぐに次の動作に入るのでとにかく高速に実装しないといけないですね。1画面の表示領域にテキストをいかに差分で無駄なく表示するかの実装がすごく難しいです。

毎回、1画面を全描画できるようなマシンスペックになればかなり楽に実装できそうなんですけどね。

余談

折り返しの実装はかなりのエディタを参考にしましたが、特にやばいのは世界最速エディタです。どのエディタなのかは察してください。

多分このエディタは行番号を物理行座標で表示することができるので折り返しタイミングで全行折り返してるんだと思うのですが、その速度がやばいんです。例えば1000万行(1.2GB)のファイルを開いたとします。するとまず、この時点でそのファイルを開けないエディタが出てきます。いちよー自作エディタは開くことはできました。めっちゃ遅いけどね。

そして、折り返すじゃないですか。さすがに一瞬では折り返せないんですが、1000万行でもギリギリ待てるくらい(5秒ぐらい)で折り返してきます。ウィンドウサイズ変更もサイズを変更してから折り返してるんで、サイズ変更時にもっさりしません。そして、お待たせ！どやっ？って感じで返ってきます。

いやー、やばいでしょ？どー実装してんの？ってくらい最適化されてるんだと思いますね。ほんと。ちなみに自作エディタで1000万行を折り返したら無理！って感じでずーーーーと返ってこないと思います。

論理座標と物理座標の問題

自作エディタでは行を折り返していない場合、論理座標でキャレットを移動しています。そして、折り返している場合は物理座標でキャレットの移動を実現しています。

ここで問題が発生します。折り返した場合のやり直し(Undoね)などの情報はどー持ってんの？ってことです。折り返していない場合、論理座標でやり直し情報は持っていますので、折り返すと物理座標に変換する必要が出てきます。

ここでも悩みましたね。やり直し情報も論理座標から物理座標に変換する必要があんのかってね。
そもそも変換なんかしたら、内部のロジックはめちゃくちゃになりそうでした。

で、どうしたん？

もーね、内部では論理座標だけで持つようにしました。折り返している場合は物理座標なんで論理座標に変換してやり直し情報を保持するようにしました。こーすることでやり直し情報を更新する必要はなくなりました。

今度は論理座標から物理座標へ変換の問題が…。

物理座標から論理座標の変換って物理行(WrapLines)で直ぐにわかります。でもね、その逆の論理座標から物理座標って今回の仕様だと分からないんですよね。

例えば、論理座標のX=10でY=500だとします。論理行は500行目(正確には499ね)ってのはわかるんですが、単純に物理行の500行目を参照しても、その行が500行目じゃない可能性があります。折り返してるからね。

で、どうしたん？

ここも悩みましたね。毎回頭から物理行を検索したらわかるんですが、もーそれじゃ遅いんで使い物になりません。なので二分探索で検索するようにしました。頭から検索した場合と二分探索のだと20倍ぐらい差がありました(うろ覚え…)

まとめ

こんな感じでOTZEditorコントールは行管理しています。肝心なList<StringBuilder>の速度が書けなかったんですが別の記事で紹介したいと思います。その他のテキスト管理方法も試すことができたらまた記事にしたいと思います。最後にさくさくエディタの作者さんの記事を紹介して終わりにします。