Kosshi が大規模なアウトラインを扱う仕組み

Kosshi は すべてを 1 つのアウトラインに まとめる設計を採っています。 ファイルを分けず、プロジェクトも日記もタスクも同じアウトラインに置く。 この使い方をしていると、中身は数千行、数万行と育っていきます。

Kosshi は入力と描画にネイティブのフレームワークを使用しています。 しかし、アウトラインが大きくなると、それだけでは足りません。 操作のたびにすべての行を調べ直さない仕組みも必要です。

この記事では、アウトラインが育っても操作を軽快に保つために、 Kosshi が内部でどのような処理をしているかを説明します。

行数が増えると重くなる処理

文字を入力したり、行を折りたたんだりするたびに、 Kosshi は画面に出す行を選び、行の位置を更新します。 この処理が短い時間で終われば、画面は滑らかに反応します。

問題になるのは、行数に比例して時間がかかる処理が混ざっている場合です。

たとえば「画面の上から 3 行目はどれか」を求めるのに、 素朴に作るとアウトラインの先頭から 「これは折りたたまれているから飛ばす」「次は見える、1 行目」「次も見える、2 行目」 と順番に数えることになります。 行数が 2 倍になれば時間も 2 倍、10 倍なら 10 倍かかる。 プログラミングではこの性質を O(n) と書きます（n は行数）。

1 行あたりの処理がごく短くても、全行を調べる処理は、 アウトラインが育つほど時間がかかります。 小さなアウトラインでは気にならなかった処理も、行数が増えると、 画面のカクつきや入力への反応の遅れとして現れます。

Kosshi は大規模なアウトラインを使った性能テストで、 このように行数とともに時間が増える処理を見つけています。

重要なのは、一つひとつの処理を少しずつ速くすることだけではありません。 操作のたびに全行を調べる処理そのものを減らすことです。

画面に見えるのは一部だけ

アウトラインにはいくつかの性質があります。

• ズームインして、興味のある部分だけを表示することが多い
• 折りたたみで、関係ない子孫を非表示にできる
• 画面に一度に表示できるのはアウトラインの一部だけ

大規模なアウトラインを開いていても、 画面に映っているのはごく一部です。 残りは折りたたまれているか、スクロール位置から外れているか、ズームの外にある。 Kosshi は画面に見えている範囲を中心に描き、 折りたたみやズームで隠れている部分はまとめて飛ばします。 何かを編集したときも、アウトライン全体ではなく、 その変更に関係する部分を中心に更新します。

そのためには、必要な行を素早く見つけられる仕組みが必要です。

SumTree で必要な行を素早く探す

画面に見える部分だけを描くには、 スクロール位置にどの行が来るのかを素早く見つける必要があります。 毎回先頭から 1 行ずつ数えていては、アウトラインが大きくなるほど時間がかかります。

Kosshi はこのために、SumTree という内部の索引を使っています。 本の目次から目的の章へ飛べるのと同じように、 SumTree は行をいくつものまとまりに分け、目的の場所までのまとまりを飛ばして進めます。 各まとまりには行数や画面上の高さも記録されているため、 中の行を一つずつ確認する必要がありません。

SumTree という呼び方は、コードエディタ Zed にならっています¹。 Kosshi は同種の構造をアウトライナー向けに応用しています。

まとまり単位で飛ばす

SumTree は、画面に見えているアウトラインの階層とは別のものです。 利用者がその存在を意識することはありません。 アプリの内部で、たくさんの行を素早く扱うために使われています。

図で示すと以下の通りです。

たとえば、アウトラインのずっと下にある行を探すとき、 先頭から順に数える代わりに、目的の行を含まないまとまりを丸ごと飛ばします。 大きなまとまりから小さなまとまりへ絞り込むことで、目的の行へたどり着きます。

アウトラインの行数が大きく増えても、 探す手間が同じ割合で増えないのは、この仕組みがあるためです。

折りたたみとズームへの応用

折りたたみとズームでは、表示対象が一度に大きく変わります。

親の下に 10,000 行ぶら下がっていたとします。 素朴な作りだと、 折りたたみの瞬間に 10,000 行を 1 行ずつ「見えない」状態にする処理が走ります。 行数が多いほど、待ち時間も長くなります。

Kosshi は、その親の下にある行を一つの範囲として見つけ、まとめて画面から外します。 その後ろに続く、関係のない行を一つずつ更新する必要はありません。 展開するときは、実際に画面へ戻る行を必要な分だけ追加します。

ズームでも同じように、選択した枝の外側をまとめて飛ばします。 画面から遠い行は、最初から高さを一つずつ正確に測りません。 スクロールして近づいた行だけを正確に測って描きます。

数え直さずに済む情報

まとまりごとに記録した情報は、行を探す以外にも役立ちます。 Kosshi は、まとまりの中にある行数や完了済みの行数、画面上の高さなどを持っています。

行を編集したときは、関係するまとまりの情報だけを更新します。 そのため、件数や位置が必要になるたびに、 アウトライン全体を最初から数え直す必要がありません。

利用者からは見えない仕組みですが、 大きなアウトラインでも操作を軽快に保つための土台になっています。