ロープサイエンス 第11回 – 実践的な構文ハイライト（2017）

2023 年 4 月 23日

この投稿では、構文ハイライトの増分アルゴリズムを紹介します。
主に遅延時間で測定される性能は非常に良好ですが、メモリ使用量や電力消費も低く抑えられています。コード量は多くなくても、分析自体は微妙で洗練されています。好きなコードエディタなら、ぜひ採用することでほぼ確実に恩恵を受けるでしょう。

教育的観点から見ると、この投稿は「単純な関数型プログラム」を増分アルゴリズムへ体系的に変換するケーススタディも提供します。入力に対してデルタ（差分）を取り、出力にもデルタを返すように設計されており、そのデルタを適用するとフル関数を最初から実行した結果と同じになります。この種のアルゴリズムは xi エディタの中枢であり、大きなファイルでもほぼ瞬時に応答できるようになっています。

構文ハイライト関数

多くの構文ハイライト方式（TextMate / Sublime / Atom など）は、以下のシグネチャを基本操作として採用しています（擬似 Rust）：

fn syntax(previous_state, line) -> (next_state, spans);

「state」は通常有限状態のスタック―すなわちプッシュダウンオートマトンです。こうしたオートマトンは多くの文法を表現でき、実際に LR パーサーを扱うには行に 1 トークンだけ追加で見通し（look‑ahead）を持たせれば十分です。

構文関数自体についてはここでは詳しく掘り下げません。以下で説明するアルゴリズムは、この枠組み内で完全に汎用的です。

バッチアルゴリズム

ファイル全体に構文ハイライトを適用する最も単純な方法は、開始から終了まで各行に

syntax

let mut state = State::initial();
for line in input_file.lines() {
    let (new_state, spans) = syntax(state, line);
    output.render(line, spans);
    state = new_state;
}

このアルゴリズムはシンプルで、メモリも最小限（1 行のテキスト＋構文関数に必要な状態だけ）です。ファイルを初回ロードしたときや、静的にドキュメントファイルを生成するときに有用です。

今回の投稿では、正しさの仕様としても機能します。すべての高度な最適化は結局同じ結果を出力する必要があります。

ランダムアクセスとキャッシュ

バッチモードで処理しているわけではなく、ウィンドウ内でランダムにスクロールしながら表示しているケースを考えてみましょう。ファイル全体のスパン（ハイライト情報）をすべて保持せずに、リアルタイムでハイライトを計算したいときです（これらは圧縮しても入力テキストと同程度のサイズになることがあります）。

単純な関数型プログラム：

fn get_state(file, line_number) -> state {
    file.iter_lines(0, line_number).fold(
        State::initial(),
        |state, line| syntax(state, line).state
    )
}

fn get_spans(file, line_number) -> spans {
    let state = get_state(file, line_number);
    syntax(state, file.get_line(line_number)).spans
}

は、ファイルの先頭付近ではうまく機能しますが、1 行あたり (O(n))、全体で (O(n^2)) です。中間結果

get_state

しかし、メモ化はメモリコストがかかります。1 行ごとに 1 ワード（状態）を保持する必要があります。極めて大きなファイルではより良い妥協策が求められます。

典型的な速度／空間トレードオフは、

get_state

get_state

このようなキャッシュ（置換戦略など）の調整は後述します。

変更の処理

編集されたファイルに対してもインタラクティブにハイライトを行いたい場合、既存のキャッシュエントリが無効になる可能性があります。キャッシュエントリ ((line_number, state)) を「有効」と定義するには、その状態が

get_state(line_number)

/*

キャッシュに「フロンティア」（frontier）というセットを追加します。フロンティアは無効になり得るエントリの集合です。以下の不変式が常に成り立ちます：

有効でかつフロンティアに入っていないキャッシュエントリについて、次のエントリも有効である。

この不変式から重要な性質が導けます：最初のフロンティア要素までのすべての行は有効です。フロンティアが空なら、キャッシュ全体が有効です。この不変式は編集後に平均 (O(1)) 時間で回復できます。

1 行だけを変更した場合

最も近い以前のキャッシュエントリをフロンティアへ追加します。任意領域を置き換える場合は、その領域内に開始行があるすべてのエントリを削除します。挿入・削除後は、後続行番号を適宜調整します。

微細再検証アルゴリズム

フロンティアから最初の要素 (line_number, state) を取り出す。
syntax(state, file.get_line(line_number)) → new_state を評価する。
もし line_number+1 がキャッシュに無い、またはその状態が new_state と異なる場合
    (line_number+1, new_state) をキャッシュへ挿入し、そのフロンティア要素を新しいエントリへ移動。
そうでない場合
    このフロンティア要素を削除する。

キャッシュエントリ（例：除外）がフロンティアにあるときは、前のエントリへフロンティアを移動します。

フロンティアの表現

最初のフロンティア要素だけを保持しようという誘惑がありますが、すべてのフロンティアエントリを維持すると大きなメリットがあります。例えばファイル中でコメントが開く／閉じるときに、一度無効になった位置を再利用できるようになるため、波及を早期に止められます。フロンティアをセットとして保持するオーバーヘッドは小さく、レイテンシや電力消費の改善が顕著です。

キャッシュの調整

アクセスパターン

対話型セッションでは主に 3 種類のアクセスパターンがあります：

1. 順序的 – 初期ファイルロードやコメント変更後の波及。キャッシュはほとんど役に立たず、計算自体が必要です。
2. 局所的 – 小規模領域（約 1 画面分）内での編集。極小デルタを望み、エントリ間ギャップをゼロまたは最小限に保ちます。
3. ランダム – 珍だが可能なランダムアクセス。最悪ケースで (O(n/m)) を目指します。

これらの混合比率がキャッシュ調整の方向性を決定します。

キャッシュ性能

従来のキャッシュ指標はヒット率ですが、ここではミス時に発生するギャップの長さがコストです。目的はそのギャップを最小化することです。LRU は順序的処理の後で大きなギャップを残すため劣ります。ランダム除外は純粋に順序的作業には有効ですが、最悪ケースではギャップが大きくなります。

「最小ギャップ」ポリシーはランダムアクセスで最大ギャップ（(2n/m)）を最適化しますが、局所編集時にキャッシュが最近追加された行近辺に固定されてしまいます。ハイブリッドアプローチがより効果的です：少数 (k) のランダム候補を探査し、その中でギャップが最小のものを選びます。実験上、(k=5) がすべてのパターンでバランスが良く、(k) を増やすとメリットは薄れ、局所アクセスが悪化します。

キャッシュサイズと表現

典型的な作業セット（約 1,000 行）に対してギャップを小さく保つには十分なエントリ数が必要です。最も単純なのは密集ベクターで、削除や行番号調整は (O(m)) ですが定数が良いです。B‑木や平衡木のように複雑な構造を使うと余計なオーバーヘッドになります。

最大 10 k エントリという固定サイズでほぼ最適な結果が得られます。

実装状態とまとめ

アルゴリズムはまだ完全には実装されていません（シミュレーションのみ）。しかし設計から期待できる点は次の通りです：

• 極小デルタ：変更箇所だけを再計算します。
• 控えめなメモリ使用量：キャッシュ行 1 行あたり 1 ワード（状態）程度。
• シンプルなコード・データ構造：実装が容易です。

今後の課題は、厳密な解析と関連文献の調査です。Colin Rofls に感謝します。彼とのプラグインに関するキャッシュ議論が多くのアイデアを刺激しました。