どのくらい速いか

2万メソッド(約2万行)を持つ1つの巨大なクラスを生成し、パースにかかる時間を測った。

bench.py
import time
from ts_common import parser
lines = [b"class Big {"]
for i in range(20000):
    lines.append(b"  void m%d(int x) { if (x > 0) { System.out.println(x); } }" % i)
lines.append(b"}")
src = b"\n".join(lines)
t = time.perf_counter()
tree = parser.parse(src)
first = time.perf_counter() - t
pos = src.index(b"m10000")
from tree_sitter import Point
row = src[:pos].count(b"\n")
col = pos - src.rfind(b"\n", 0, pos) - 1
new = src[:pos] + b"n" + src[pos+1:]
tree.edit(start_byte=pos, old_end_byte=pos+1, new_end_byte=pos+1,
          start_point=Point(row, col), old_end_point=Point(row, col+1), new_end_point=Point(row, col+1))
t = time.perf_counter()
parser.parse(new, tree)
second = time.perf_counter() - t
print(f"{len(lines)} lines full={first*1000:.0f}ms incremental={second*1000:.1f}ms")
実行結果
20002 lines full=185ms incremental=37.5ms

手元の環境(2コアの Linux VM、Python 3.10)で、2万行のファイル1つの全体パースが 0.2 秒弱だった。一般的な業務システムの Java ファイルは数百行なので、1ファイルあたり数ミリ秒 と考えてよい。数千ファイルのリポジトリでも、パースそのものより、ファイルの読み込みや Python 側の処理(Query の結果をたどる部分)のほうが時間を使う。

💡 Query を毎回作らない

Query(JAVA, "...") の作成は、パターンをコンパイルするぶん重い処理だ。PART 05・06 のスクリプトでは、Query をモジュールの先頭で1回だけ作り、ファイルごとには QueryCursor だけを作っている。ループの中で Query を作ると、それだけで何倍も遅くなる。

並列化する

ファイルごとの処理は独立しているので、プロセスを分けて並列に動かせる。Parser や Node はプロセス間で受け渡せない(pickle できない)ので、ファイルのパスだけを渡し、各プロセスの中でパースして、結果はただのタプルや辞書で返す のがコツだ。PART 06 の check() をそのまま再利用できる。

parallel.py
import sys
from concurrent.futures import ProcessPoolExecutor
from pathlib import Path
from lint import check            # PART 06 の check() を再利用

def check_file(path):
    return list(check(Path(path)))   # 各プロセスで ts_common の parser が作られる

if __name__ == "__main__":
    files = [str(p) for p in Path(sys.argv[1]).rglob("*.java")]
    with ProcessPoolExecutor() as pool:
        results = pool.map(check_file, files, chunksize=50)
        rows = [row for rs in results for row in rs]
    print(f"{len(files)} files, {len(rows)} findings")
実行結果
2 files, 3 findings

Windows ではプロセスの起動方式の都合で、if __name__ == "__main__": の中に並列処理を書かないとエラーになる。ts_common.py の parser はモジュールの読み込み時に作られるので、各プロセスに1つずつ用意される。

増分パース

tree-sitter はエディタのために作られたので、ソースの一部を書き換えたとき、前の木を再利用して変わった部分だけを解析し直す ことができる。手順は「古い木に編集内容を伝える(tree.edit())」「古い木を添えて新しいソースをパースする」の2段階だ。

incremental.py
from tree_sitter import Point
from ts_common import parser

old_src = b"class A { int add(int x) { return x; } }"
tree = parser.parse(old_src)

# "add" を "plus" に書き換える(バイト位置 14〜17)
start = old_src.index(b"add")
new_src = old_src[:start] + b"plus" + old_src[start + 3:]

tree.edit(
    start_byte=start, old_end_byte=start + 3, new_end_byte=start + 4,
    start_point=Point(0, start), old_end_point=Point(0, start + 3),
    new_end_point=Point(0, start + 4),
)
new_tree = parser.parse(new_src, tree)        # 古い木を渡すと差分だけ再解析

method = new_tree.root_node.named_children[0].child_by_field_name("body").named_children[0]
print(method.child_by_field_name("name").text)
実行結果
b'plus'

先ほどの bench.py では、2万行のうち1文字を書き換えて増分パースした時間も測っている。全体パースの約5分の1で済んでいる。

ただ、ここまで作ってきたような バッチで一度解析して終わり のツールでは、増分パースを使う場面はほとんどない。効いてくるのは、ファイルの変更を監視して結果を更新し続ける常駐型のツールや、エディタの拡張機能を作るときだ。そういう用途もある、と覚えておけば十分である。

他の言語への応用

このシリーズのコードで Java に固有なのは、文法パッケージとノード型の名前 だけだ。Parser・Query・QueryCursor・TreeCursor の使い方は、どの言語でも変わらない。

Python
import tree_sitter_python as tspython      # pip install tree-sitter-python
from tree_sitter import Language, Parser, Query, QueryCursor

PY = Language(tspython.language())
tree = Parser(PY).parse(b"def hello(name):\n    print(name)\n")
q = Query(PY, "(function_definition name: (identifier) @fn)")
print([n.text for n in QueryCursor(q).captures(tree.root_node)["fn"]])   # [b'hello']
  • 公式・主要な文法:Python・JavaScript・TypeScript・Go・C・C++・C#・Rust・Ruby・PHP・Bash・JSON などは tree-sitter-○○ の名前で pip から入る
  • まとめて入れる:tree-sitter-language-pack を使うと、百数十の言語を get_parser("python") のように名前で呼び出せる。対応言語の多いリポジトリを横断して調べるときに便利だ
  • COBOL など:COBOL・PL/I・RPG のような業務系言語は、コミュニティが作った文法が GitHub で公開されているものがある。pip のパッケージがない場合は、tree-sitter CLI で文法からパーサーをビルドする必要がある。方言(固定形式・各社の拡張)への対応度は文法によって差が大きいので、実際のソースで has_error の割合を確かめてから採用したい

当サイトの 可視化 / COBOL シリーズでは、COBOL のソースを正規表現と正規化の組み合わせで扱っている。文法が手に入る言語なら tree-sitter、文法がない・方言が強い言語なら正規化+パターン、という使い分けになる。

限界と、乗り換えるタイミング

tree-sitter の限界は、PART 01 で書いたとおり 型と参照を解決しない ことに尽きる。PART 05 で入れた「変数の宣言から型を推定する」工夫でも、次のようなケースには届かない。

届かないケース例必要になる情報
メソッドチェーン・式のレシーバーreq.getItems().isEmpty()メソッドの戻り値の型
オーバーロードsend(String) と send(Mail) のどちらか引数の型
継承・インターフェースrepository.save() の実装クラスはどれか型の階層・DI の設定
ライブラリの型System.out、List.of()依存 JAR・JDK のクラス情報
var・ラムダ・メソッド参照var x = factory.create();型推論

これらが 漏れなく 必要になったら、型解決のできるツールに乗り換えどきだ。

ツール向いている場面
JavaParser + Symbol SolverJava のコードで解析ツールを書く。依存 JAR を指定すれば呼び出し先をメソッドのシグネチャまで解決できる
Eclipse JDT(ASTParser・バインディング)IDE と同等の精度が必要。Eclipse プラグインや既存の JDT 資産がある
Spoon型付きのモデルで解析し、そのまま書き換え(自動リファクタリング)までしたい
バイトコード解析(ASM・jdeps など)ソースがない、またはビルド済み JAR の実際の依存を知りたい

実務では、まず tree-sitter で全体を素早く棚卸しして当たりを付け、正確さが必要な範囲だけを型解決のできるツールで深掘りする、という二段構えがうまくいきやすい。ビルド環境を整えるのに何日もかかる古いシステムほど、この順番が効いてくる。

シリーズのふりかえり

回身についたこと作ったもの
PART 01tree-sitter の特徴と、JavaParser などとの使い分け―
PART 02導入と最初のパース、bytes で扱う理由、Shift_JIS 対応ts_common.py
PART 03ノード型・フィールド・名前なしノード・ERROR/MISSINGdump_tree.py
PART 04Query の書き方、captures と matches、述語query_basic.py ほか
PART 05宣言と呼び出しの抽出、変数の型の推定extract_deps.py・to_mermaid.py
PART 06Query と走査を組み合わせたルール、CI への組み込みlint.py
PART 07速度・並列化・増分パース・他言語・限界parallel.py

導入チェックリスト

  • tree-sitter と文法パッケージのバージョンを固定した
  • ソースの文字コード(UTF-8 / Shift_JIS)をそろえて読んでいる
  • Query はモジュールの先頭で1回だけ作っている
  • has_error のファイルを結果の中で区別している
  • 型の推定が「推定」であることを、結果を使う人に伝えている
  • 正確さが必要な範囲は、型解決のできるツールで確かめる段取りにしている

✅ シリーズを読み終えたら…

抽出したデータを図にしたくなったら「可視化 / Java」へ。Class 関連図・Method Call Graph・3D マップ・CRUD 図の作り方を扱っている。

→ シリーズ目次に戻る