コードを1文字変えたとき、IDEの中では何が起きているのか

最近、OSSとして commiter という、Gitの差分からコミットメッセージを自動生成するCLIを開発しています。

開発中、「diffをただの文字列ではなく、コードの構造として捉えられないか？」と考えました。行頭の + や - を正規表現で追うだけでは、関数のシグネチャが変わったのか、内部の変数1個が変わっただけなのかを判定するのに限界を感じたからです。

そこで普段使っているIDEの仕組みからヒントを得ました。IDEはコードの変更を視覚化するだけでなく、関数や変数、構文といった構造も認識しています。その仕組みを追っていく中で出会ったのが、エディタ向け構文解析ライブラリの Tree-sitter（ツリーシッター）でした。

そして調べてみると、Tree-sitterにはもう一つ面白い仕組みがありました。

1文字コードを変更しても、すべてを最初から解析し直さない。

今回は、その Incremental Parsing（増分構文解析）についての”眠れなくなるお話”です。

1. なぜ通常の構文解析はタイピングに耐えられないのか

エディタでコードを書いているとき、シンタックスハイライトやエラー表示は、キーを叩くたびにほぼリアルタイムで追従しますよね。当たり前の体験ですが、構文解析の視点から考えると、これはかなり過酷な要求です。

一般的なコンパイラや従来のパーサージェネレータ（BisonやANTLRなど）は、ファイル全体を一括処理する バッチ処理 を前提に作られています。先頭から字句解析（レキシング）し、構文規則にしたがって木構造を組み上げるため、ファイルサイズ (N) に対して少なくとも (O(N)) の時間がかかります。

数千行を超えるファイルでは、1回のパースに数十〜数百ミリ秒を要します。人間のタイピング速度は毎秒何打鍵にもなるため、1文字打つたびに全体をスキャンし直していては、メインスレッドが追いつかず入力がカクついてしまいます。

私たちがエディタで求めているのは「ファイル全体の再解析」ではなく、「打ち込んだ1文字が、既存の構文木のどこに影響したか」を最小コストで反映することなんですよね。この要求に応えるために設計されたのが、Tree-sitterの増分構文解析です。

2. ASTではなく具象構文木（CST）を扱う理由 — エディタのための基本設計

Tree-sitterは、テキストエディタや開発ツール向けに作られた高速な構文解析ライブラリです。Neovim、Helix、GitHubのコード検索基盤などで標準採用されており、タイピング中にリアルタイムで構文木を更新し続けることに特化しています。

Tree-sitterの設計思想を決定づけているのが、構文木としてASTではなく CST（Concrete Syntax Tree / 具象構文木）を採用している点です。

コンパイラや静的解析でよく使われる AST（抽象構文木）は、意味的な構造だけを抽出した木構造です。空白、コメント、セミコロン、括弧などは意味に影響しないため削ぎ落とされます。実行コードを生成するコンパイラにとっては、不要な情報を捨てるASTが合理的です。

しかし、エディタにとっては話が逆です。エディタが扱うのは「テキスト」そのものであり、カーソル位置も編集操作も、すべて画面上のバイトオフセット（行と列）で指定されます。空白や記号を捨ててしまうと、「120バイト目で文字を打ったとき、それが構文木のどのノードに当たるのか」を正確に逆引きできません。

CSTは、インデントの空白やカンマ、コメントに至るまで、すべての文字を葉ノード（Leaf Node）としてツリーに保持します。ソースコードのバイト列と構文木の全ノードを厳密に1対1で対応づけることで、テキストの編集操作とツリーの構造更新をダイレクトに同期させています。

3. 仕組み1 — 変更箇所をツリーに教える「Tree Edit」

Incremental Parsingの処理は、いきなり再解析から始まるわけではありません。編集が発生した瞬間に、まず既存の構文木へ「ここがこのように変わりました」という差分情報を教え込みます。これが Tree Edit（ts_tree_edit）です。

エディタはTree-sitterに対して、次の3つの位置情報を渡します。

start_byte（編集が始まったバイト位置）
old_end_byte（編集前のテキストで、変更・削除された範囲の末尾バイト位置）
new_end_byte（編集後のテキストで、新しく挿入された範囲の末尾バイト位置）

※実際のC言語API（TSInputEdit）では、バイト位置と行・列座標（TSPoint）をセットで渡します。

たとえば const x = 10; の 10 を 100 に書き換えた場合、10バイト目から旧末尾（12バイト目）までの2バイトが削除され、新末尾（13バイト目）までの3バイトが挿入された、という情報が渡されます。Gitのdiffで行ごとの増減を見る感覚とは違い、文字単位の絶対座標として差分を捉えるのが特徴です。

ts_tree_edit を呼ぶと、Tree-sitterは古い構文木に対して位置の補正を行います。概念としては「編集箇所以降にあるノードの位置情報を、差分配分だけ後ろへずらす」操作です。ただし、内部では各ノードが直前のノードからの相対的な余白（padding）と自身の長さ（size）を保持しているため、ツリー全体を走査せず、変更経路の余白だけを局所的に更新します。

あわせて、編集範囲と交差するノードやその親に has_changes フラグを立てます。この時点では、まだ文法解析を一切行っていません。 各ノードのオフセットをスライドさせ、「ここは編集の影響を受けたエリアだ」と目印をつけることで、構文解析器が動く土台を整えています。

4. 仕組み2 — 構文解析器が「部分木をまるごと再利用する」流れ

Tree Editで位置を調整したら、構文解析器（パーサー）を走らせます。

Tree-sitterのパーサーは、入力を先頭から読み進めながらボトムアップで構文木を組み上げる LRパーサー（正確には文法の曖昧性を並行探索できる GLRパーサー）を基盤にしています。通常のLRパーサーは、次のトークンをスタックに積む shift と、規則にマッチしたトークン列を親ノードにまとめる reduce を繰り返してツリーを組み立てます。

Tree-sitterが高速なのは、入力として生のテキスト（トークン）を読むだけでなく、古い構文木の未変更な部分木（Subtree）そのものを1つの入力単位として受け取れる 点にあります。

パーサーがコードを解析していく際、現在位置と一致するノードが古いツリーに存在するかを確認します。もしそのノードに has_changes フラグがなく、現在のパーサーステート（文脈）と矛盾しなければ、配下のコードを1文字ずつパースするのをやめ、そのノードを 丸ごと1つの塊として shift します。これが Subtree Reuse（部分木の再利用）です。

たとえば1000行あるファイルで、200行目にある関数の変数名を1箇所書き換えたとします。1〜199行目の関数群は古いツリーから巨大な部分木としてそのまま shift され、一瞬で新しいツリーに組み込まれます。変更のあった200行目周辺だけが子ノードへと展開（break down）されてトークン単位で再解析され、文脈が再び安定すると、201〜1000行目の関数群も再び部分木として丸ごと再利用されます。

最初から解析し直せば (O(N)) かかる処理が、変更箇所の探索と前後の部分木の結合だけで済むため、実質的に (O(\log N)) や局所的なコストで完了するわけです。

5. なぜ構文エラーの途中でも壊れないのか — 局所的なエラー耐性

Incremental Parsingを実用的なエディタで成立させるには、エラー耐性（Error Recovery）も欠かせません。タイピング中のコードは、関数の引数を追加している瞬間や括弧を開いた直後など、文法的には9割以上の時間「壊れて」います。

function calculateTotal(price: number,

従来のパーサーであれば「予期しないトークン」としてパースを中断してしまいます。エディタでこれが発生すると、1文字打つたびにハイライトが消え、入力が完了するまで支援機能が全滅してしまいます。

Tree-sitterはこの問題を、局所的なエラーノードの挿入 で解決しています。文法に合致しないトークンに遭遇しても処理を中断せず、次の戦略で木構造を維持します。

トークンのスキップ: 余計な文字を ERROR ノードとして隔離し、読み飛ばす
トークンの補完: 閉じ括弧など、あるべきトークンを仮想的に補完して reduce を進める
エラーの局所化: 不正な範囲だけを最小限の ERROR ノードで囲み、前後の正常なブロック（親ノードや後続の関数）は健全なツリーとして保護する

不完全な引数部分だけを ERROR としてマークし、他の健全な関数は壊さずそのまま残す。このエラー耐性があるからこそ、未完成なコードをタイピングしている最中でも、編集箇所の周辺以外は古い部分木を安全に再利用し続けられます。

6. まとめ — 差分を構造として捉える面白さ

エディタでキーボードを叩いた瞬間に画面が反応し、関数が認識され、ハイライトが追従する。この当たり前の快適さの裏側には、地道で精巧なアルゴリズムの積み重ねがあることが分かってもらえたのではないでしょうか。

CST: 空白や記号を含む全文字位置を構文木と厳密に同期させる
Tree Edit: 編集箇所のオフセットを局所的にシフトし、変更箇所に目印をつける
Subtree Reuse: 影響のない構文ブロックを丸ごと新しいツリーへ組み込む
局所的なエラー耐性: タイピング途中の壊れた構文でもツリーを破綻させずに維持する

こうした仕組みが組み合わさることで、1文字の変更のたびに全体を解析し直す必要がなくなります。

冒頭で触れた commiter の開発でも、構文解析の視点を通すと、Gitの差分は単なるテキストの増減ではなく、「構文木という大きな構造体の中の、どのノードがどう変化したか」という立体的な情報に見えてきます。

私たちが毎日何気なく使っている開発ツールの足元には、こうした興味深い仕組みが動いています。普段使っているツールの「当たり前」を一歩掘り下げて中身を覗いてみるのは、エンジニアリングを感じられる最高に面白い瞬間だなと感じます。

WebGL粒子アニメーションのGC最適化についての記事もあわせて読んでみてください。