Scintillaのデータ設計
Scintillaは、Notepad++やTortoiseSVNなど、かなりいろいろなプロジェクトから利用されている、有名なテキストエディタコンポーネントである。テキストエディタ設計の中身が気になってソースを見ながら調べてたんだけど、データの構造の部分が見えてきたのでまとめておく。
一般的なテキストエディタ設計の話は、GreenPadの作者の方のページに大変いい感じでまとまっている。ポイントは、それなりに頻繁に挿入削除がある巨大なデータを、効率よく処理できるかというところにある（と思われる）。
テキストのデータ構造
Scintillaではテキストやスタイルの情報は、GapBufferと呼ばれているデータ構造に格納されている。GapBufferについてはわりと多くの解説があるのでここでは詳しくは述べない（w.l.o.g.などを参照）。ScintillaではGapBufferという名前ではなくSplitVectorという名前のクラスになっている（ソースファイルはSplitVector.h）。SplitVectorの実装は、意外だったのだけどかなりシンプルで、例えば先のリンク先で書いてあったような削除時の最適化などの工夫みたいなものはない。シンプルさを特徴にしているからというのもありそうだが、Scintillaベースのエディタで大きなファイルを編集しても、動作が引っ掛かるようなことはないので、このような実装で十分なのかもしれない。SplitVectorについてはあまり説明することもないので、主要なメンバ変数が意味しているものを把握するためのの図を作って示す。真ん中の破線部分がGapである。以下のようにデータが入っている先頭部分の長さがpart1Length、データ全体の長さがlengthBody、Gapの長さがgapLength、バッファ全体の長さがsizeとなっている。
行数の管理方法
行数の管理方法もエディタデータ設計のポイントで、Scintillaではテキストと同じようにSplitVector(GapBuffer)を用いている。ただ面白いのは、テキストの変更のたびに起こる書き換えの範囲を少なくするための工夫がなされているところである。
まず、行数管理のデータでは、行がバッファのどの範囲になっているかということを示す。図はテキストが「abcd(改行)efg」となっているときのデータバッファと行数管理バッファのイメージである。行数管理バッファの1つめは常に0が入る。次に、1行目のテキスト文字列が「abcd(改行)」となっているので、4文字＋改行コード2バイトで6バイトとなり、6がバッファの2つめに入る。そして、2行目は3文字なので3バイトとなり、3がバッファの最後に入っている。また、図ではGap位置も描かれているのだが、Gap位置は編集順序によって異なるものであることに注意していだきたい。
このようなデータでは、修正があったときに変更があった行数以降の数値を全て書き換えなければいけないという問題がある。例えば、上の例では1行目に1バイト追加したときは、行数管理バッファの位置2と3両方を変更しなければならない。行数管理バッファは行数と同じ長さになるので、行数が多いファイルでは行の先頭の文字列を更新することのコストが高くなってしまう。
このような問題の対処として、Scintillaでは行数に変更があった位置と変更量をキャッシュするという手法を用いている。
Scintillaでは行数を管理するために、SplitVectorのバッファ（body）をメンバに持つPartitioningというクラスが存在する（ソースファイルはPartitioning.h）。Partitioningクラスは、bodyの他に変更をキャッシュとして、変更位置をあらわすstepPartionと変更量をあらわすstepLengthという2つの整数変数メンバを持っている。以降で、stepPartitionとstepLengthがどのように行数の更新処理を効率化してるか示す。
まず最初の挿入時。挿入前ではstepPartitionとstepLengthは両方とも0になっている。以下のように2行目に1文字追加したとすると、stepPartitionに2が代入され、stepLengthには1が代入される。
この段階ではbodyは全く書き換えず、2行目以降のバイト数を見るときに全て1足すことで、仮想的にbodyが変更されているように見なす。キャッシュがなければbodyの位置3以降を全て書き換えなかればならないところをbodyの変更に関してはゼロにすることが出来るようになっている。ここで、ただキャッシュしてるだけならば、次の変更などですぐにキャッシュの反映が必要になりあまり効果が得られないようにも見える。しかし、もちろんそうではなく、次の更新の位置によっては更新の分量を実際に少なくすることが出来る。
例えば次の変更が、4行目への1文字追加だとする。この変更がキャッシュされた結果を考えると、stepPartitionが4、つまり4行目以降がキャッシュの適用範囲になるはずである。ここで、この範囲が、今のキャッシュの適用範囲（2行目以降）の一部になっていることに注意する。つまり、同じ範囲に関しては次のstepPartitionで示されることになるので、stepLengthにさえ値を反映させれば、bodyを変更することなく済ますことが可能となる。
また、逆に、次の変更のstepPartitionで示される範囲の一部が前回の範囲になる場合は、前回と今回のstepPartitionの間のbodyの値からstepLengthを引き、次のstepLengthに反映することで、更新範囲を変えることが出来る（ソースではBackStep関数）。以下の図で示す。
ただし、これは必ずしもbodyを更新する量を減らす訳ではないためと思われるが、前回と今回のstepPartitionの位置の差が、全体の長さの10分の1以下の時だけにしてるようだ。また、以上の例は挿入の場合で書いたが、削除の場合でも同様になる（stepLengthには負の値が足される）。
