[2026/9/30]

[Astro] #158 AST Inspector — Tree-sitter WASMで構文木を覗く（Queryとインクリメンタルパースの可視化付き）

はじめに

前回（#157）は、HarfBuzz の WASM でフォントの中身を覗くツールを作りました。

[Astro] #157 Font Inspector — HarfBuzz WASMでフォントの中身を覗く（TrueTypeヒンティングVMの逆アセンブラ付き） // PROTOCOL.LAIN

HarfBuzz（harfbuzzjs）をWASMで動かし、フォントファイルの中身をブラウザだけで覗けるツールを作りました。

lain-lab.com

今回は AST Inspector です。

前回は TrueType 命令の逆アセンブラを手で書きました。機械語を「読める形」に戻す作業です。今回はその逆方向で、人間が書いたソースコードを、コンピューターが扱える木の形（構文木）にする側を覗きます。

使うのは Tree-sitter です。Neovim、Zed、Helix、GitHub のコード表示などで、シンタックスハイライトやコードの折りたたみを担当しているパーサーです。もともとは GitHub の Atom エディタのために作られました。WASM 版の web-tree-sitter があるので、ブラウザでそのまま動きます。

CS 講座で「字句解析 → 構文解析」の話をするとき、実物の構文木を触れる道具が欲しかった、というのも動機のひとつです。

GitHub - tree-sitter/tree-sitter: An incremental parsing system for programming tools

An incremental parsing system for programming tools.

github.com

完成画面

AST Inspector — 構文木とソースの連動

AST Inspector — 構文エラー（ERROR / MISSING）

AST Inspector — Query プレイグラウンド

AST Inspector — インクリメンタルパース（再利用 / 新規の色分け）

操作動画

画面は、左がコードエディタ、右がタブ（Tree / S式 / Query）です。

できることは次のとおりです。

JavaScript / Python / C のコードをその場でパース（ファイルを開くと拡張子から言語を判別）
構文木の表示（名前付きノードのみ / 全ノードの切り替え）、S 式での表示とコピー
ツリーの行にホバーするとソースの該当範囲が光る。カーソル位置から該当ノードへジャンプ
構文エラーの表示（ERROR は波線、MISSING は縦線）
Query の実行とマッチ箇所の表示、プリセット
同梱の highlights.scm を使ったシンタックスハイライト
インクリメンタルパースの可視化（再利用されたノード / 作り直されたノード / 編集範囲 / 構造が変わった範囲）

構成

いつもどおり、ページは Astro、処理は public/ に置いた素の JS です。

my-astro-project/
├─ src/pages/
│   └─ ast-inspector.astro          UI と CSS（BaseLayout で包む）
└─ public/
    ├─ ast-inspector/
    │   └─ ast-inspector.js          本体（約 1,000 行）
    └─ libs/
        └─ tree-sitter/
            ├─ web-tree-sitter.js    ランタイム（JS）
            ├─ web-tree-sitter.wasm  ランタイム（WASM）
            ├─ tree-sitter-javascript.wasm
            ├─ tree-sitter-python.wasm
            ├─ tree-sitter-c.wasm
            ├─ queries/              各文法の highlights.scm
            └─ LICENSE-*

使ったバージョンとサイズはこうなっています。

ファイル	バージョン	サイズ
web-tree-sitter.wasm	0.27.0	205KB
tree-sitter-javascript.wasm	0.25.0	402KB
tree-sitter-python.wasm	0.25.0	447KB
tree-sitter-c.wasm	0.24.1	611KB

文法は、言語を選んだときに読み込みます。最初に読むのはランタイムと 1 言語分だけです。

役割分担はこうなっています。

担当	やっていること
Tree-sitter（WASM）	パース、誤り回復、インクリメンタルパース、Query の実行、変更範囲の計算
各文法の `.wasm`	言語ごとの構文規則（パーサーの表）
`highlights.scm`（文法に同梱）	ハイライト用の Query
ast-inspector.js（自前）	画面、ツリーの描画、エディタのハイライト層、差分の計算、再利用の判定

Tree-sitter とは

Tree-sitter は、文法の定義（grammar.js）からパーサーを生成するパーサージェネレーターです。生成されるのは LR 系のパーサーで、文法に曖昧なところがあると GLR で複数の解釈を並行して進めます。

コンパイラ用のパーサーと違うのは、エディタで使うことを前提にしている点です。

壊れたコードでも止まらない：書きかけのコードは、ほぼ常に構文エラーを含んでいます。エラーの箇所を ERROR ノードとして木に残し、残りは普通にパースします
インクリメンタル：1 文字打つたびにファイル全体を読み直すのではなく、前回の木を取っておいて、変わった場所の周りだけ作り直します

ちなみに、エディタの「自動修正」や「未定義の変数」の警告は、Tree-sitter ではなく LSP（Language Server）の担当です。tsserver、pyright、clangd のような言語サーバーは、型やスコープまで解析しています。実際のエディタは、

Tree-sitter：キー入力のたびに一瞬で構文を把握する（速さと壊れた入力への強さ）
LSP：少し遅れて意味を解析し、エラーや修正案を出す（正確さ）

という二段構えになっていることが多いです。

web-tree-sitter の使い方

// ast-inspector.js
import { Parser, Language } from '/libs/tree-sitter/web-tree-sitter.js';

await Parser.init({ locateFile: (name) => '/libs/tree-sitter/' + name });
const parser = new Parser();

const JavaScript = await Language.load('/libs/tree-sitter/tree-sitter-javascript.wasm');
parser.setLanguage(JavaScript);

const tree = parser.parse('let x = 1 +;');
console.log(tree.rootNode.toString());
// (program (lexical_declaration (variable_declarator name: (identifier) value: (number)) (ERROR)))

rootNode.toString() は、木を S 式で返します。S 式タブは、これにインデントを付けて表示しているだけです。

0.25 以降は API が変わっている

ネットにある記事の多くは、Parser.Language.load() や require('web-tree-sitter') をそのまま Parser として使う書き方です。0.25 以降は { Parser, Language } の名前付き export になっていて、古い書き方はそのままでは動きません。

もうひとつ、ランタイムの WASM のファイル名が tree-sitter.wasm から web-tree-sitter.wasm に変わっています。locateFile でパスを指定するときに気をつけてください。

WASM は自作しなかった

最初は文法の .wasm を自分でビルドするつもりでした。ところが、公式の npm パッケージ（tree-sitter-javascript など）には、ビルド済みの .wasm が同梱されていました。ABI 15 で、0.27 のランタイムからそのまま読めます。

注意が必要なのは、複数の言語の .wasm をまとめて配っている非公式パッケージです。公式 README にも、古い dynamic linking 形式でビルドされた .wasm は、パーサーの ABI が対応範囲内でも新しい web-tree-sitter では読めない、と書かれています。公式パッケージを使うか、tree-sitter build --wasm で自分でビルドするのが安全です。

構文木を描く

ツリーの走査には TreeCursor を使います。node.children で子を配列として取るより、カーソルを動かす方が速く、ノードのオブジェクトも作らずに済みます。

// ast-inspector.js（renderTree の一部）
const cursor = tree.walk();
const visit = (parent, depth) => {
  do {
    const type = cursor.nodeType;               // 'function_declaration' など
    const field = cursor.currentFieldName;      // 'name' / 'body' など
    const named = cursor.nodeIsNamed;           // false なら '(' や 'return' のような記号
    // ... 行を作って parent に追加 ...
    if (cursor.gotoFirstChild()) {
      visit(container, depth + 1);
      cursor.gotoParent();
    }
  } while (cursor.gotoNextSibling());
};
visit(fragment, 0);
cursor.delete();                                // WASM 側のメモリを解放

ノードには 2 種類あります。

種類	例	表示
名前付きノード（named）	`identifier`、`binary_expression`	緑
無名ノード（anonymous）	`"("`、`"return"`、`"+"`	灰色、引用符付き

「named のみ」にチェックを入れると、無名ノードを隠します。いわゆる抽象構文木（AST）に近い見た目になります。外すと、括弧やキーワードまで全部入った具象構文木（CST）になります。Tree-sitter が作っているのは、実は後者です。

name: や left: はフィールド名です。「この子ノードは親から見て何の役割か」を表していて、Query でも使います。

descendantForIndex() / namedDescendantForIndex() を使うと、ソース上の位置から一番深いノードを引けます。エディタのカーソル位置からツリーへのジャンプは、これで実装しています。

インデックスは UTF-16 単位

作っていて気づいたことがあります。web-tree-sitter が返す startIndex / endIndex と、位置の column は、UTF-16 のコード単位で数えられています。

const s = 'const a = "日本語😀"; let b = 2;';
const t = parser.parse(s);
// string ノード: startIndex 10, endIndex 17
s.slice(10, 17);   // → '"日本語😀"'  そのまま切り出せる

日本語 は 3 単位、😀 はサロゲートペアで 2 単位です。JS の文字列も UTF-16 なので、String.prototype.slice() にそのまま渡せます。

C の API はバイト単位（UTF-8 のバイト数）です。Web 版は、JS の文字列を UTF-16 のまま渡しているので、返ってくる位置も UTF-16 になっています。バイト数に直す処理を書かずに済みました。

エディタのハイライト層

エディタは textarea です。文字色を透明にした textarea の背面に、同じ文字列を描いた pre を重ねています。色やハイライトは pre の側で付けます。

重なるハイライトは、シンタックスの色、ERROR の波線、Query のマッチ、ホバー中の範囲、編集範囲、構造変化と、最大 6 種類あります。最初は範囲の境目で区切ってから区間ごとに該当する範囲を探していましたが、ハイライト対象が数千個になると重くなります。そこで、文字ごとに「シンタックスの色番号」と「フラグのビット」を持つ配列を作り、同じ値が続く区間をまとめて span にする方式にしました。

// 文字ごとの値 = (シンタックスの色番号 << 5) | フラグ
const F_ERROR = 1, F_FOCUS = 2, F_MATCH = 4, F_EDIT = 8, F_CHANGED = 16;
const keyAt = (i) => (synIds[i] << 5) | flags[i];
// keyAt(i) が変わる位置で span を切る

幅ゼロのノード（後述の MISSING）は、幅 0 で左に線を引いた span を差し込んで表しています。

構文エラーの見え方

Tree-sitter は、エラーを 2 種類のノードで表します。

ノード	意味	例
`ERROR`	文法に合わない部分をまとめたもの	`let x = 1 +;` の `+;` 周辺
`MISSING`	本来あるはずのトークンを補ったもの（幅ゼロ）	`function f(a {` の `)`

function f(a { と書くと、ツリーには MISSING ) が出て、parameters の終わりに幅ゼロで挿入されます。閉じ括弧を 1 つ補えば文法が通る、とパーサーが判断したわけです。

関数の閉じ } を消した場合は、MISSING } がファイルの最後に出ます。どこで閉じ忘れたかまでは推測せず、「最後まで閉じていない」と判断するからです。

Python のインデントエラーは出ない

Python で、for の中身の行を左端まで戻してみました。

for i in range(3):
s.push(i ** 2)       # インデントを消した

CPython なら IndentationError: expected an indented block です。ところが、AST Inspector では errors が 0 のままでした。ツリーをよく見ると、for の中身が body: block [12:18–12:18] という幅ゼロの空ブロックになっています。「for の中身は空で、s.push はその次の文」とパースされたわけです。

tree-sitter-python の文法では、ブロックは「文が 0 個以上」と定義されているので、空のブロックも文法上は正しいことになります。「中身が 1 つ以上必要」というのは CPython 自身のパーサーが課している制約で、Tree-sitter はそこまで見ていません。

Tree-sitter は、壊れた入力でも止まらずに読むために、本物の言語より少し緩い文法（言語の上位集合）を受理するように作られています。どこまでを構文解析でチェックして、どこからを後の段階（意味解析）に任せるか、という境界の話の、分かりやすい実例になっていると思います。

Query

Query は、構文木を検索するための言語です。S 式でノードの形を書き、取り出したいノードに @名前 を付けます。

; 呼び出される関数名（メソッド呼び出しはプロパティ名）
(call_expression
  function: [
    (identifier) @call
    (member_expression property: (property_identifier) @call)
  ])

[ ... ] はどれか 1 つ、(_) は任意のノード、name: はフィールドの指定です。サンプルの JS に実行すると、fib、fib、map、fib、log、join の 6 か所が取れます。

#eq? や #match? の述語で、ノードの文字列を条件にもできます。

; 16 進リテラルだけ（C）
((number_literal) @hex
  (#match? @hex "^0[xX]"))

実行はこれだけです。

import { Query } from '/libs/tree-sitter/web-tree-sitter.js';

const query = new Query(language, source);         // 0.25 以降はコンストラクタ
const matches = query.matches(tree.rootNode, { matchLimit: 10000 });
// [{ patternIndex, captures: [{ name: 'call', node }, ...] }, ...]

Query の書き間違いは QueryError として投げられます。エラーオブジェクトに index（ソース上の位置）が入っているので、行と列に直して表示しています。

2行3列: Bad field name 'functin'

Query タブでは、マッチしたノードをエディタで黄色い下線、ツリーで @call のバッジとして表示します。コードを編集すると、再パースのたびに Query も実行し直します。

シンタックスハイライトは Query でできている

各文法のパッケージには、queries/highlights.scm というファイルが入っています。中身はただの Query です。

; tree-sitter-javascript の highlights.scm（先頭）
(identifier) @variable
(property_identifier) @property
(function_declaration
  name: (identifier) @function)
...

これを実行して、キャプチャ名（@keyword、@function、@string など）ごとに色を付けると、シンタックスハイライトになります。キャプチャ名が VS Code や Neovim のテーマと同じ語彙なので、見た目も自然とそれっぽくなります。CodeMirror などのエディタライブラリを入れずに済みました。

プリセットの「highlights.scm（同梱）」を選ぶと、色付けに使っている Query そのものが Query タブに出ます。

重なったときの優先順位

1 つのノードに複数のキャプチャが付くことがあります。class Foo の Foo を調べると、こうなっていました。

variable:Foo      patternIndex 0
constructor:Foo   patternIndex 11

先頭の (identifier) @variable がまず全部の識別子を拾い、後ろのより具体的なパターンが constructor で上書きする前提の書き方です。そこで、

範囲が狭い（内側の）キャプチャを優先
範囲が同じなら、後に書かれたパターンを優先

という規則で塗っています。実装は、広い範囲から順に塗って、狭い範囲で上書きするだけです。

caps.sort((a, b) => (b.end - b.start) - (a.end - a.start) || a.pattern - b.pattern);
for (const c of caps) ids.fill(c.id, c.start, c.end);

インクリメンタルパース

ここからが本題です。

仕組み

エディタで 1 文字打つたびに、次の 3 ステップを踏みます。

// 1. 前回のテキストと今のテキストの差分を求める
const edit = computeEdit(lastText, text);

// 2. 古い木に「どこがどう変わったか」を教える
tree.edit(edit);

// 3. 古い木を渡して再パースする
const newTree = parser.parse(text, tree);

差分は、前後から一致する部分を削っていくだけの単純なものです。入力のデバウンス中に何文字か打たれても、それらをまとめて 1 つの連続した編集として扱えます。

function computeEdit(oldText, newText) {
  let start = 0;
  while (start < min && oldText.charCodeAt(start) === newText.charCodeAt(start)) start++;
  let oldEnd = oldText.length, newEnd = newText.length;
  while (oldEnd > start && newEnd > start &&
         oldText.charCodeAt(oldEnd - 1) === newText.charCodeAt(newEnd - 1)) { oldEnd--; newEnd--; }
  return {
    startIndex: start, oldEndIndex: oldEnd, newEndIndex: newEnd,
    startPosition: positionAt(newText, start),       // { row, column }（UTF-16）
    oldEndPosition: positionAt(oldText, oldEnd),
    newEndPosition: positionAt(newText, newEnd),
  };
}

tree.edit() を呼ぶと、編集位置より後ろのノードの位置がずらされます。パーサーは、編集範囲に触れていない部分木をそのまま新しい木に組み込みます。

正しく差分を渡せているかは、インクリメンタルで作った木と、同じテキストを全体パースした木の S 式を比べて、完全に一致することで確かめました。

再利用されたノードの見分け方

どのノードが使い回されたかは、API で直接は分かりません。そこで、ノード ID を使いました。

const prevIds = collectIds(oldTree);   // tree.edit() の後で、古い木の全ノード ID を集める
const newTree = parser.parse(text, oldTree);
// 新しい木を走査して、prevIds にない ID のノード = 作り直されたノード

web-tree-sitter のノード ID は、中身の部分木を指すポインタです。使い回された部分木は同じポインタなので、ID も変わりません。同じテキストを全体パースし直すと、ID はすべて新しくなります。これで、再利用されたかどうかを判定できます。

ID を集めるのは、tree.edit() の後にしています。edit() で位置がずれたノードはコピーされることがあるので、パーサーが実際に見るのは edit 後の木だからです。

画面では、作り直されたノードをツリーでオレンジ、今回の編集範囲をエディタで青い背景にしています。Tree タブの上には、

再利用 103 / 120 (86%) ・ 構造変化 1 範囲 ・ 全体パースなら 0.13 ms

のように、再利用の割合と、比較用に全体パースした場合の時間を出しています。

見つけたこと 1：getChangedRanges は「構文の差分」

oldTree.getChangedRanges(newTree) は、2 つの木で変わった範囲を返す API です。エディタでは、ハイライトを塗り直す範囲を決めるのに使われます。

ところが、n < 2 を n < 20 に書き換えても、返ってくる範囲は 0 個でした。

これは、この API が返すのが「構文構造が変わった範囲」だからです。number が number のままで中身の文字が変わっただけなら、構造は同じなので含まれません。文を 1 つ足すと、初めて 1 範囲になります。

テキストの差分（青い背景）と構文の差分（オレンジの破線）は別物、ということが、並べて表示すると一目で分かります。

見つけたこと 2：再利用の粒度は意外と粗い

関数とその下の宣言の間に、let abc = 123; を 1 行足してみました。

表示	ノード
オレンジ（作り直し）	足した `lexical_declaration` 一式、`program`、先頭の `comment`
通常色（使い回し）	関数 `fib` 全体、下の `const results` の宣言

再利用は 103 / 120（86%）でした。関係ない関数はまるごと使い回されています。

一方で、ファイル先頭の comment まで作り直されています。ルートの program は子が 1 つ増えるので作り直しが必要ですが、comment は編集位置から離れています。Node.js で同じ操作を直接試しても結果は同じだったので、表示の不具合ではなく Tree-sitter の実際の挙動です。トップレベルの文の並びを管理している隠しノードが組み直されるせいだと思いますが、理由までは追えていません。

逆に細かいところもありました。let de = 456; を let def = 456; に直したときは、作り直されたのが lexical_declaration、variable_declarator、name: identifier だけで、同じ行の value: number 456 は使い回されていました。部分木単位で再利用しているのがよく分かります。

見つけたこと 3：構文エラーは高くつく

let を lat と打ち間違えて、lat de = 456; にしてみました。この行は ERROR を含む expression_statement になり、再利用は 53 / 128（41%）まで落ちました。

エラーの行だけでなく、その下の const results の宣言までオレンジになっています。パーサーがエラーから回復するために前後を読み直すので、作り直しの範囲が広がるわけです。let に直すと、再利用は 88% に戻り、オレンジも引きました。

正しいコードを足すなら影響は局所で済むのに、エラーが入ると大きく広がる。書きかけのコードは常にエラーを含んでいるので、エディタにとっては誤り回復の質がそのまま速さに効いてくる、ということだと思います。

速さについて

サンプルは 10 行程度なので、パース時間はインクリメンタルで 0.05ms、全体でも 0.13ms 程度です。この規模では差を体感できません。インクリメンタルパースが効いてくるのは、数千行のファイルを 1 文字ずつ編集するような場面です。今回は速さの比較よりも、どこが使い回されているかを見せるのを目的にしています。

ハマりどころ

1. Astro で CSS が古いまま残る（3 回）

前回（#157）と同じ問題に、今回は 3 回当たりました。Query を足したとき、インクリメンタルパースを足したとき、BaseLayout に組み込んだときです。

どれも、HTML と JS は新しくなっているのに、DevTools で見ると CSS だけが前の版のままでした。BaseLayout に入れたときは、Layout 対応前の .ai-app { height: 100vh } と :root の変数が残っていて、ページがナビゲーションの下に潜り込んでいました。

.astro の <style is:global> を大きく書き換えると、開発サーバーが古いスタイルを掴んだままになるようです。どれも npm run dev の再起動で直りました。前回のように CSS を public/ に出してしまうのが確実ですが、今回はファイルを増やさずに、このページの CSS を触ったら再起動する、で済ませています。

is:global にしているのは、ツリーの行や Query の結果が、JS が後から作る要素だからです。Astro のスコープ付きスタイルは、Astro がビルド時に出力した要素にしか効きません。クラス名は ai- / hl- / syn- の接頭辞で閉じて、CSS 変数も :root ではなく .ai-app に置いて、他のページに漏れないようにしています。

2. また `hidden` が効かない

インクリメンタルパースの情報バーが、編集する前から凡例だけ表示されていました。前回と同じで、CSS の display: flex が hidden 属性の display: none を上書きしていたのが原因です。.ai-inc-bar[hidden] { display: none; } を足しました。

3. 埋め込みモードのフックは `.app`

BaseLayout には、ホーム画面のウィンドウから ?embed 付きで開いたときに、上下の余白を消すルールがあります。

html.is-embed .app { margin-top: 0 !important; margin-bottom: 0 !important; height: 100vh !important; }

これが .app を対象にしているので、コンテナを class="app ai-app" にしました。他のツールと同じクラス名に合わせておかないと、埋め込みのときに余白が残ります。

4. 空行でファイル全体が光る

カーソル位置からノードを探すと、空行やファイル末尾ではルートの program が選ばれます。そのままハイライトすると、エディタ全体に背景色が付いてしまいます。ルートのときはハイライトしないようにしました。

クレジットとライセンス

Tree-sitter / web-tree-sitter（MIT License）— Max Brunsfeld、Amaan Qureshi ほか Tree-sitter 開発者 github.com/tree-sitter/tree-sitter
tree-sitter-javascript / tree-sitter-python / tree-sitter-c（MIT License）— Tree-sitter 開発者 github.com/tree-sitter/tree-sitter-javascript github.com/tree-sitter/tree-sitter-python github.com/tree-sitter/tree-sitter-c
シンタックスハイライトの Query（highlights.scm）は、各文法のリポジトリに含まれているものをそのまま使っています。

おわりに

前回は機械語を手で読み下す側、今回はソースコードを木にする側でした。Tree-sitter は、壊れたコードでも止まらず、1 文字ごとに木を部分的に作り直す、という「エディタのためのパーサー」です。その裏側を色分けして眺めてみると、再利用の粒度が思ったより粗かったり、エラー 1 つで作り直しの範囲が一気に広がったりと、実際に動かさないと分からないことがいくつも見つかりました。

「Tree-sitter は言語より緩い文法を受理する」「getChangedRanges はテキストではなく構文の差分」あたりは、CS 講座で構文解析と意味解析の境目を説明するときに、そのまま使えそうです。

次は、各文法に入っている locals.scm（変数の定義と参照を拾う Query）を使ったスコープ解析をやってみたいと思います。ただ、locals.scm が同梱されているのは JavaScript だけでした。もうひとつ、Z80 アセンブリの文法を自分で WASM にビルドして、エミュレーター側の話とつなげるのも面白そうです。