[BIG PROJECT] 識別子の抽出をバンドル時解析 + 内容ハッシュキャッシュへ移行する検討

[TwoSquirrels]

構想

識別子・実装先の抽出を、登録時 (生ソースの tree-sitter 解析 → tags.json) からバンドル時 (プリプロセス出力の解析 + 内容ハッシュキャッシュ) へ移す。

1. プリプロセス出力を linemarker で出所ごとに束ね直し、非維持ライブラリのファイル片を再構成する (追跡機構は linemarker::Tracker として既存)。
2. 各ファイル片の sha256 をキーに解析キャッシュを引く。ヒットすれば定義識別子・実装先をそのまま使い、ミスした片だけ tree-sitter で解析してキャッシュに書く。
3. 以降の逆引き・-M・削除は現行と同じ。

得られるもの

• X-macro 対応: 展開後を見るため、マクロが生成した名前が見える。compatibility.md のサポート外条件が 1 つ消え、マクロ定義名が識別子として登録される #92 (マクロ名の無意味な登録) も無意味化する。
• #ifdef の正確化: 実際のフラグで採用された分岐の名前だけを見る (現行は両分岐を安全側に登録)。
• library update と変更検知の概念的消滅: 解析キャッシュは内容ハッシュキーなので陳腐化せず、「ライブラリが変更された」エラーも update の打ち忘れも存在しなくなる。library update (全件) が最初の失敗で中断し、後続ライブラリが更新されない #81 (update の中断)・verify のハッシュ検証範囲が広すぎ、無関係なライブラリの破損で全バンドルが止まる #79 (検証範囲) も無意味化する。
• 登録 (library add) は消えず、-I パスとダミー生成だけの軽い操作に痩せる。tags.json の files/implements/hash が不要になる (スキーマ v3)。

解決しないもの

• 自己完結性の限界はそのまま。namespace ラッパーのファイル片は namespace mylib {\n} に再構成されて名前ゼロのまま消えるし、関数分割も壊れたまま。compatibility.md の大半は有効で、書き換わるのは X-macro の節だけ。
• 自由関数の演算子だけのファイルも従来どおり救えない (特殊コメントで定義識別子・実装先を明示できるようにする #95 の特殊コメント案の意義は残る)。

実測 (WSL2, Intel Core 7 240H, release ビルド, Nyaan's Library 405 ヘッダー)

項目	時間
現行のバンドル 1 回 (8 include の解答)	~0.09–0.10 s
ファイル片の tree-sitter 解析: 現実的な解答 (展開後 35 KB・12 片)	+0.02 s
同: 全部 include テンプレの上限 (911 ファイル・1.8 MB)	+1.1–1.6 s
linemarker の束ね直し (上限ケース)	~10 ms
ファイル片の sha256 (上限ケース、キャッシュキー計算)	~2 ms
参考: 現行の登録 1 回 (405 ヘッダー)	1.68 s

• キャッシュ無しの素朴なバンドル時解析は、看板ユースケース (全部 include テンプレ) で毎回 +1 秒超となり不成立。
• キャッシュ有りなら、温かいバンドルの追加コストは上限ケースでも ~12 ms (束ね直し + ハッシュ)。ライブラリを触った直後の 1 回だけ解析を払う — 現行の「登録時に償却」と同じ償却構造を、明示的な update なしで実現できる。

論点

• キャッシュの置き場所と世代管理 ($LOCAL 配下。内容ハッシュキーは伸び続けるので、ファイルパスをキーにハッシュを添える形にすれば自然に上書きされて有界になる)。
• 展開はフラグに依存するため、同じヘッダーでもバンドルごとに別フラグメントになり得る (それで正しい。キャッシュはフラグ違いを別エントリとして持つだけ)。
• include ガードの無いファイルが同一バンドル内で複数回展開された場合、出所ごとの連結で名前は和集合になる (過剰検出側なので安全)。
• spec・architecture・compatibility の大幅改訂を伴う。tags.json スキーマ v3。実装規模的にメジャーバージョン (v3.0.0) 級。
• 現行設計の正当化 (「列挙を登録時に行うのはホットパスへの償却のため」) は、この issue の帰結が出るまでの間も architecture.md に明文化しておく価値がある。

🤖 Generated with Claude Code

[TwoSquirrels]

キャッシュ設計をメインターゲットのシナリオ (Nyaan's Library 405 ヘッダー全 include のテンプレ、使うのは一部) でプロトタイプ実験した。その実測と、そこから派生した方針の検討を記録する (以下は検討の記録であり、確定した決定ではない)。

実測 (WSL2, Intel Core 7 240H, release ビルド)

キャッシュ無しの毎バンドル追加コスト (束ね直し + 実物 identifiers.rs 移植での解析):

ケース	束ね直し	tree-sitter 解析	合計
全部入りテンプレ (405 ヘッダー、片 1.0 MB)	17 ms	411〜433 ms	~0.44 s
普通の解答 (8 include、片 31 KB)	7 ms	~15 ms	~0.02 s

• ファイル片をパス単位で連結すると重複排除 (911 片 → 408 片) を兼ねるため、本文の見積もり (+1.1〜1.6 s) より大幅に軽い。
• 比較対象として、同じ全部入りテンプレを直接コンパイルすると -O2 で 11.1 秒。-O0 で 10.0 秒、コード生成も最適化もしない -fsyntax-only でも 10.0 秒 (この内訳の意味は末尾の「副産物」を参照)。8 include の解答は -O2 で 3.0 秒。

判断基準の提案: 絶対値ではなくコンパイル時間との比率

解析時間もコンパイル時間も「include されたコード量 × CPU の遅さ」にほぼ比例するため、両者の比率はハードウェアやライブラリ規模を変えてもほぼ一定に保たれる。したがって「低スペックな PC で巨大ライブラリを複数使ったら何秒になるか」を場合分けする必要はなく、比率で実用性を判断できる。

ワークフロー	バンドル頻度	解析 / コンパイル比
提出時にバンドルする使い方	1 問 1〜2 回	~4% (0.44 s / 11.1 s)
毎回のローカルコンパイル前にバンドルし、コンパイル時間を削減する使い方	1 問数十回	~15% (0.44 s / 縮小後 3.0 s)

キャッシュの方針案: v3 の初期実装では持たない

提出時のみの使い方では 4% で不要は自明。コンパイル前バンドルでも 15% で許容範囲と考え、解析結果のキャッシュは v3 の初期実装に含めない案を推す。

当初はファイルパスごとに複数世代のハッシュと解析結果を持つ設計 ($LOCAL/libraries/<id>/analysis_cache.json、相対パス → [{hash, identifiers}] の LRU) を作って実測したが、この細粒度は過剰と見直した。理由: キャッシュが最も効いてほしい「コンパイル前バンドル」の反復では、解答だけが変わりライブラリのファイル片は 1 バイトも変わらない。したがって「全ファイル片の結合ハッシュ 1 個をキーに、解析結果全体を 1 個保存する」だけの全体メモ化 (実装 ~30 行) で、この用途のヒット率は 100% になる。細粒度設計が全体メモ化に勝つのは「ライブラリを編集した直後」「コンパイラや問題を切り替えた直後」の 1 回に 0.4 秒得するだけで、割に合わない。

導入するとしても 3 段階を提案する: (1) v3 はキャッシュ無しで実装する。(2) コンパイル前バンドル用途の需要が実際に出たら、全体メモ化を足す。(3) 解析時間がコンパイル時間の 2 割を超える実例が出たら、初めて細粒度設計を再検討する。キャッシュは正しさに影響しない純粋な最適化なので、後から足しても何も壊れない。

将来の設計材料として、プロトタイプ実験で得た知見も残す:

• キャッシュを足す場合の設計原則は「純粋なキャッシュ」: 失われても・壊れても・古くても、遅くなるだけで結果は間違わない (内容ハッシュがキーなので、ヒット = 正しいが構造的に保証される)。したがって読めないキャッシュは黙って捨てて作り直し、書き込みは一時ファイル + rename、並行実行はロック無しの last-writer-wins、形式変更はバージョン番号 1 つの不一致で全捨て、で足りる。エラー処理・ロック・移行をこの性質に甘えて全部省けることが最大の利点で、update-check のキャッシュと同じ哲学。
• 105〜192 KB の JSON キャッシュの read+parse は 1〜1.6 ms (serde_json で足りる。バイナリ形式は不要)。ファイル片の sha256 は 1.0 MB で 1.4 ms。
• 同じヘッダーの展開結果が変わる主因はコンパイラの切替 (g++ → clang++ で 98% のファイル片が変化)。-D マクロや -std の変更では、Nyaan's Library の場合 1 片も変化しなかった。
• ヘッダーを 1 ファイル編集したとき、展開結果が変わるのは編集したファイルの片だけで、他の片への波及はなかった。
• キャッシュとは別の高速化手段として、ファイル片ごとの解析は互いに独立なので並列化でも cold を縮められる。ただし想定すべき低スペック機はコア数も少ないため、反復用途の根本対策にはならず、あくまで補完。
• 「bundle/ は純粋関数に保ち IO は commands/ に置く」という architecture.md の方針とキャッシュ IO は、受け口がキャッシュを値として読んで渡し、純粋核が (解析結果, 新エントリ) を返し、受け口が書き戻す形で両立できる。
• 実験環境 (Nyaan's Library の clone、全 405 ヘッダーを include するテンプレート、計測用クレート) は手元に保持しており、再実験できる。

移行の設計上の意味 (実装時に architecture.md へ反映する)

• この移行の本質は不変条件の置き換えである。現行は「tags.json がライブラリ実体と同期している」ことを library update というユーザーの操作で保証し、乖離をハッシュ検証で検出してエラーにしている。移行後は逆引き情報を毎回実体 (プリプロセス出力) から導出するため、同期という概念自体が消え、検証・エラー・回復の機構ごと不要になる。状態を検証するのではなく、状態が正しさに影響しない構造にする、という種類の単純化。
• architecture.md に記録した非対称「ユーザーの内容が変わった (ハッシュ不一致) は確認させ、risundle の形式が変わった (スキーマ不一致) は黙って直す」は、前半の出番そのものが消える。
• UX の帰結: ユーザーのメンタルモデルが「ライブラリの変更の反映は常に自動」に単純化する。cheatsheet の「ライブラリを触ったらやること」節は丸ごと不要になり、「ライブラリが変更された」エラーと関連警告も消えるため、ユーザーが遭遇するメッセージの総量が減る。

発展: 登録という概念ごと解消し、library サブコマンドを廃止する方向

識別子・ハッシュが消えた後の登録の中身を精査すると、残りも全て「実体から再生成できる導出物」か「ただの名前付け」であり、登録という概念自体を解消できる。この方向を有力案とする。

• ダミーツリー (維持指定したライブラリの #include を展開させないための空ファイル群) は、ライブラリのファイルパス一覧から機械的に導出できる。バンドル時に実体を走査 (405 ファイルの readdir は数 ms) して照合し、ズレていれば作り直す遅延キャッシュに降格できる。生成自体も 405 ファイルで ~0.1 秒 (Linux 実測)。

• std の認識コンパイラ集合は、キャッシュ化すると消えるどころか設計が良くなる。現行が全コンパイラのシステム include を 1 つのダミーツリーへ統合しているのは、登録時にはどのコンパイラでバンドルするか分からないから (architecture.md 記載) だが、遅延生成ならバンドル時点で使うコンパイラが判明しているため、コンパイラ実体パスをキーにそのコンパイラ専用のダミーツリーをキャッシュすればよい。和集合も add-std も tags.json の compilers も概念ごと消える。「std は初回バンドル時に自動登録」という既存動作が、この遅延生成の先例になっている。

• すると最後に残る状態は**「ライブラリ ID → インクルードパス」の辞書 1 つだけ**になる。これはコマンドで隠れた $LOCAL を操作する (命令的) 代わりに、設定ファイルに書く (宣言的) 形にできる:

  [libraries]
  mylib = "~/cp/library"
  ac-library = "~/ac-library"

• これで library add/add-std/delete/update/list は全て不要になり、library サブコマンド自体を廃止できる (show -v の識別子表示だけは別の確認手段を用意する。後述の論点 3)。隠れた状態が無くなり「設定ファイルを見れば全部分かる」ようになるため、設定を宣言的な全量指定とする既存の設計方針とも揃う。

この方向の論点:

• パスはマシン依存だがプロジェクトの .risundlerc.toml はリポジトリにコミットされるため、マシングローバルな設定層 (例: ~/.config/risundle/) の導入が要る。「最も近い設定ファイル 1 つだけを使いマージしない」という現行の設定解決の原則に、層をどう位置づけるか。
• クイックスタートが「コマンド 1 回」から「設定ファイルに数行書く」に変わる。docs は全面改訂になる。
• [BIG PROJECT] 識別子の抽出をバンドル時解析 + 内容ハッシュキャッシュへ移行する検討 #105 と同時にやるか、後続の Issue に切るか。ただし [BIG PROJECT] 識別子の抽出をバンドル時解析 + 内容ハッシュキャッシュへ移行する検討 #105 の実装を登録概念前提で固めないよう、設計だけは先にこちらへ向けておく。

実装前に詰める残りの論点

1. データフローの再設計 — 現行のバンドルは開始時に tags.json を読むだけで逆引き情報が揃うが、移行後はプリプロセスの後にファイル片の解析を挟んでから逆引きに進む形になる。この解析をどのモジュールが担うか (identifiers.rs は登録専用でなくなるため library/ から bundle/ 側へ移る、など) の再設計が要る。
2. CLI の再設計 — library サブコマンド廃止の詳細。廃止に伴い、library update と「ライブラリが変更された」エラー、検証スキップ用の -n/--no-check (スキップすべき検証自体が消える) も消える。互換のための移行案内 (旧コマンドを打ったときの誘導) をどうするか。
3. 識別子情報の確認手段 — 現行は library show -v で「どのファイルがどの識別子を定義しているか」を確認でき、tree-shaking の結果が想定と違うときのデバッグに使える (cheatsheet にも記載)。show ごと消えるため、代替の確認手段 (バンドル時に判断根拠を出すオプション等) が要る。
4. コンパイラオプション依存の明文化 — 現行はプリプロセス前のソースを解析するため #ifdef の全分岐の識別子を拾うが、移行後は実際に採用された分岐だけを見る。その結果、同じ解答でもコンパイラやオプション次第で tree-shaking の結果が変わるようになる。正確になる方向の変化だが、spec と compatibility 文書への明文化が要る。
5. ローカルヘッダー内でしか使われないライブラリ依存が tree-shaking で消える #60 をスコープに含めるかの判断 — 現行の「解答が使う識別子」の検出対象は解答ファイル自身の行だけで、登録していないローカルヘッダーの中でだけライブラリを使うと依存が検出されない (ローカルヘッダー内でしか使われないライブラリ依存が tree-shaking で消える #60)。移行後はプリプロセス出力全体が手元にあるため、検出対象をローカルヘッダー由来の行まで広げれば ローカルヘッダー内でしか使われないライブラリ依存が tree-shaking で消える #60 も同時に修正できる見込みがある。含めるかどうかで上記 1 の設計が変わるため、先に決める。

このほか、出荷の形 (v3.0.0 として一括で置き換えるか、束ね直し → 解析の移行 → 登録概念の解消 → 仕様と文書の改訂、のように PR を分けるか) と、README のベンチマーク節の書き直し (「ライブラリ規模によらずほぼ一定」は移行後は成り立たない。現行も全部入りテンプレではプリプロセスだけで ~0.8 秒かかっており、厳密には一定でない) も残っている。

副産物: コンパイル前バンドルは構造的に有効な第 2 の価値提案

「毎回のローカルコンパイル前にバンドルし、コンパイル時間を削減する」使い方 (実測では 11.1 秒 → 3.0 秒) は、提出サイズ削減に次ぐ第 2 の価値提案になり得る。cheatsheet の公式レシピ候補。

この削減がコンパイラの進化で代替されない理由も、実測から言える。「コンパイラは最適化で DCE (デッドコード除去) を持つのに、なぜ使われないコードを含むだけでコンパイルがこれほど遅くなるのか」という疑問への答えである。

• 実測の内訳が示すとおり、コンパイル時間の 9 割はフロントエンド (構文解析 + 意味解析) で消える: -O2 11.1 秒に対し、コード生成も最適化もしない -fsyntax-only が 10.0 秒。DCE は最適化パス (フロントエンドの後段) の住人で、IR から死んだコードを刈って「出力から消す」ことはできても、「読んで理解するコスト」は減らせない。DCE が節約し得るのは -O2 と -fsyntax-only の差、約 1 秒の世界に限られる。
• そしてコンパイラは「使われないコードを読み飛ばす」ことが原理的にできない。#include はテキスト結合であり、翻訳単位の全コードが 1 つの意味空間に入るため、後のどの行が前のどの宣言を参照するかは全部読むまで分からない。一見無関係なクラス定義も、ADL で拾われる演算子オーバーロード・テンプレート特殊化・暗黙変換の候補として他のコードの意味を変え得る (オーバーロード解決の候補集合は翻訳単位全体から集まるので、宣言を 1 つ飛ばしただけで別の関数が選ばれ得る)。さらに static_assert・constexpr 評価・静的初期化子のように「使われなくても実行される」意味解析もある。つまり到達可能性の判定自体が全量の意味解析を要求する。
• したがって「読む前に捨てる」ことができるのは、ソースのレイヤーで刈る道具 — まさに tree-shaking — だけである。この隙間は C++ の言語モデルに由来する構造的なもので、コンパイラの実装が進化しても消えない (C++ modules が普及すれば別だが、競プロのジャッジ環境には当分来ない)。

🤖 Generated with Claude Code