14. chunker は時計ではなく入力の形で縛る

Status: accepted
Date: 2026-09-03
Deciders: project owner
対象: v1.3.0

背景と問題

コードの chunker が持っていた上限は 1 つだけだった — 1 MiB を超えるソースファイルは拒む (ADR-0012 がそれ以外をどう扱うかを書いている)。この上限が数えるのはバイト数であり、効く入力は大きくない。

定義がどのスコープに属するかを求めるには、そのノードから構文木の root まで登る必要があり、tree-sitter の Node::parent は保持されたポインタではなく探索である。この walk は定義ごとに繰り返されるので、定義が深く入れ子になったファイルは深さを二重に払い、合計は深さの三乗で伸びる。mod a{ を 1000 回並べて閉じ括弧を付けた 1 行のファイルは 10 KB 未満で、index に 64 秒かかった。500 段なら 8 秒、125 段なら 0.3 秒。何もこれを拒まなかった — 上限がバイト数しか見ておらず、このファイルは 1 MiB に対して誤差だからである。

これは「遅いファイル」より悪い。rebuild_index は embedder と DB を実行の間ずっと保持するので、こういうファイルが 1 本ある KB は、その実行が終わるまでサーバへの全リクエストが止まる。KB は必ずしも検索する本人が書いたものではない。

問い: コストがサイズの関数でない chunker は、何で縛るのか。

決定の要因

上限はコストを払う前に効かなければならない。払った後では意味がない
同じファイルを 2 台のマシンで index したら、同じ chunk にならなければならない。 chunk は索引そのものであり、違いは「遅い答え」ではなく「違う答え」になる
上限に掛かったファイルも検索可能であること。ADR-0012 は「ファイルは parse できてもできなくても、持っているバイトをすべて索引に出す」と約束している
何を数えるにせよ、実在のコードが遠く及ばない量であること。推測ではなく実測で決める

検討した選択肢

壁時計の予算。parse や tags query が超過したら打ち切る。tree-sitter は口を用意している (ParseOptions の progress callback、TagsContext::generate_tags の cancellation flag)
構文木の深さの上限。parse 後・tags query 前に測る
スコープ walk 自体の上限 — 定義が属してよい祖先の数 — を walk の最中に見る
ファイルを拒む。バイト上限と同じ扱い

決定

選択肢 3 を採用し、超過時は拒否 (4) ではなく degrade する。定義は祖先 64 個までの位置に居てよい。walk は歩数を数え、上限を超えた最初の定義でそのファイルの定義単位 chunk 化を終える。以降そのファイルは行単位で chunk 化され (定義が覆わない範囲が既にそうなっているのと同じ形)、parse:too-deep を付ける。

なぜ時計ではないのか (選択肢 1)。秒数の予算は索引を「それを作ったマシンの関数」にしてしまう。同じファイルが速いマシンでは定義 chunk に、負荷の高いマシンでは行 chunk になり、KB 側は何も変わっていないのに再 index で答えが変わる。groove は同じ理由で connection graph の壁時計予算を一度退けている。口は使えるが、出てくるものが再現しない。

なぜ木ではなくスコープ walk なのか (選択肢 2)。どちらも入力の性質なので再現性は同じ。違うのは効かないときのコストである。木の深さを測るには全ファイルの全ノードを歩く必要があり、このリポジトリ自身の 62 ファイルで 174 ms かかった (parse 424 ms / tags query 882 ms に対して)。既に走っている walk の中で歩数を数えるならインクリメント 1 回で済む。加えて scope walk こそが実際に爆発する当人なので、「どの代理指標なら十分近いか」という議論が要らない。

なぜ 64 なのか。選んだのではなく測った: このリポジトリの全ソースをパースして最長の walk を記録すると 8 (main.rs)。同じファイル群の構文木の最大の深さは 32 で、これは選択肢 2 が超えなければならなかった数 — 2 つの量は交換可能ではないという証拠でもある。64 は実在コードに 8 倍の余地を残す。

なぜ拒否ではなく degrade なのか (選択肢 4)。拒否は 1 行で済み、その後の per-file skip は既にある。しかし ADR-0012 は「ファイルは持っているバイトをすべて出す」と約束しており、 深く入れ子なだけのファイルは読める — 構造を解く価値が無くても、本文はクエリに答える。プレーンテキスト parser への fallback も選べない: あれは 1 ファイル 1 chunk を作るもので、コード chunker はまさにその形を避けるために存在する。

結果として

上限を超えたファイルは内容を保ち、定義メタデータを失う (symbol_kind も見出しもスコープ context も無い)。document に付く parse:too-deep が、それを黙らせずに検索から見えるようにする
parse:too-deep は parse:degraded とは別のタグである。後者は「grammar がファイルの一部を読めなかった」、前者は「読めたが groove が chunk 化を降りた」
この上限は設定ではなく定数。コード parser の他の上限が定数なのと同じ理由で、病的なファイルへの防御を弱めるだけのキーは surface に見合わない
本リリース前に作られた索引は、内容が変わっていないファイルについては古い chunk を保つ (変わっていない内容は再 chunk されないため)。groove index --force で作り直す
この上限が触らない病的な形がある: 通常の深さで定義が数万個あるファイル。そちらのコストは scope walk ではなく tags query が支配し、1 MiB の上限で有界である

補足

chunker は grooveseek/src/parser/code/ にある。上記の計測は release ビルドで、 2 本のバイナリを 1 台のマシンで交互に回して取った (生成した fixture への groove index --force)。そうやって取らないと、ビルドが違うだけで数字が 3 割動く。