はじめに
「関数ひとつ変えたとき、その影響はどこまで及ぶのか？」
この問いに正確に答えることは、数学的に不可能であることが証明されている。この「不可能性」がどこから来るのか、現実のツールはどう折り合いをつけているのか、そしてChromiumクラスの巨大C++コードベースでなぜ特に困難なのかに興味をもった.
この記事の背景
ソフトウェア開発において「この関数を修正したら、どこに影響が及ぶか」を特定する作業 「影響範囲調査」 は、あらゆるコードレビューやリファクタリングの前提となる。
この調査には 2つの方向 がある。プログラムスライシングという技法で言えば、Forward Slice とBackward Slice だ。
Forward Slice は、変更した文を起点に「この変更はどこに影響するか」をデータの流れに沿って前方に追跡する。たとえばcalculate()の戻り値の計算方法を変更したとき、その戻り値を受け取るdisplayTotal()やsendInvoice()が正しく動き続けるかを確認する必要がある。変更の影響波及を追う方向だ。
Backward Slice は逆方向で、ある文を起点に「この値はどこから来たのか」をデータの流れを遡って追跡する。calculate()の内部ロジックを変えたとき、loadConfig()やfetchRate()から受け取る入力の形式・型・値域について、新しいロジックが暗黙に仮定していることが実際に成り立っているかを確認する必要がある。変更の前提条件を検証する方向だ。
つまり、関数ひとつの変更に対して「前提は壊れていないか」（Backward）と「影響は波及しないか」（Forward）の両方向を調査する必要がある。本稿ではこのうちForward Sliceの自動化に焦点を当てるが、両方向が不可欠である。
作成した clangd-cli コマンド では、影響範囲調査を以下のように分業している。
-
データ収集（自動化済）：clangd-cli の
investigateコマンドが、clangdのLSP APIを通じて呼び出しグラフ・型階層・仮想関数ディスパッチ等の構造情報を一括取得する - Forward Slice判定（LLMが担当）：取得した各呼び出し元について、影響が実際に伝播するかどうかをLLMがコードを読んで判定する
何故に全自動で Forward Slice判定ができずLLMに担当させているのか？
Forward Sliceの判定も自動化できないのか？
答えは「理論的に完全な自動化は不可能であり、実用的な近似にも深刻な障壁がある」だ。以下、その理由を掘り下げていく。
自動化できている部分：「誰が誰を呼んでいるか」
すでに自動化されている部分を次の通りだ。clangd-cliのinvestigate コマンドは、clangdのLSP APIを通じて以下の構造情報を一括で取得する。
- ルート関数のcallers（BFS再帰探索による呼び出し元の網羅的取得）
- ルート関数のcallees（呼び出し先一覧）
- 仮想関数ディスパッチ（base method、dispatch callers、sibling overrides）
- 型階層（supertypes / subtypes）
- 各直接呼び出し元のhover情報（シグネチャ）とcallees
これらはすべて「誰が誰を呼んでいるか」という構造的な接続関係であり、clangdのインデックスから機械的に取得できる。
ここで注目すべきは、investigate コマンドが callers（呼び出し元）とcallees（呼び出し先）の両方を取得している点だ。callersはForward Slice（「この関数の変更は誰に影響するか」）の起点であり、calleesはBackward Slice（「この関数は何に依存しているか」）の起点である。双方向の構造情報を一括取得することで、LLMが両方向のスライス判定を実行できる。
1. ルート関数の callers（BFS 再帰探索）
ルート関数 processRequest() を起点に、呼び出し元を幅優先探索（BFS）で再帰的に辿ります。depth 1 で直接の呼び出し元を取得し、それらをキューに入れてさらに depth 2, 3… と展開していくことで、エントリポイント（main() など）に至るまでの全呼び出し経路を網羅的に取得します。
2. ルート関数の callees（呼び出し先一覧）
ルート関数の本体を解析し、関数内で呼び出しているすべての関数をソースコード上の出現順に抽出します。各呼び出しには行番号が付与されます。callers とは逆方向のトラバースです。
3. 仮想関数ディスパッチ
clangd は仮想メソッドの呼び出しを3つの視点で解析します。dispatch callers はベースポインタ・参照経由で仮想呼び出ししている箇所、base method は仮想メソッドの宣言元、sibling overrides は同じメソッドをオーバーライドしている派生クラスの一覧です。実行時にどの実装が呼ばれうるかを静的解析で網羅します。
4. 型階層（supertypes / subtypes）
注目している型（RequestHandler）を中心に、上方向には継承元・実装インターフェース（supertypes）を、下方向には派生クラス（subtypes）を展開します。多重継承やインターフェース実装も含めたツリー構造が得られます。
5. 各直接呼び出し元の hover 情報（シグネチャ）と callees
図1の callers 探索で「handleEvent() と runCommand() が processRequest() を呼んでいる」という事実はわかりました。しかし名前だけでは、それぞれが何者で、どういう処理の流れの中で呼んでいるのかまでは見えません。
2つの追加調査
そこで各呼び出し元に対して2つの追加調査を行います。1つ目は hover によるシグネチャ取得です。たとえば void handleEvent(Event& e) と返ってくれば、「イベントを受け取って処理する関数だ」とわかります。2つ目はその呼び出し元自身の callees 展開です。handleEvent() の callees が validate() → processRequest() なら、「バリデーションの後に呼んでいる」という流れが読み取れます。
この情報から何がわかるか
たとえば handleEvent() 経由ではバリデーション済みのデータが渡されているのに対し、runCommand() 経由ではパース済みだがバリデーションされていないデータが渡されている、といった呼び出し元ごとの前提条件の違いが見えてきます。これがわかると、バグの切り分け（「バリデーションを通っていない runCommand() 経由が怪しい」）やリファクタリング時の影響分析（「validate() を呼んでいる handleEvent() 側にも影響が出るか」）に使えます。
🔸：ルート関数への呼び出し箇所（照合ポイント）
clangd の本来の用途と今回の使い方
もともと clangd のこれらの機能は、IDE 上で人間の開発者がコードをナビゲーションするための対話的な補助ツールです。VS Code 等で「Call Hierarchy を表示」すると呼び出し元・呼び出し先のツリーが表示され、hover はマウスを重ねるとシグネチャがポップアップする、あの機能です。人間が目で見て、頭の中で「この呼び出し元はバリデーション済みだな」と解釈する前提で設計されています。
今回の使い方は、その LSP API をプログラム的に叩いて構造データを収集し、人間の代わりに LLM に解釈させている点が異なります。ただし「変更の影響範囲を調査する」という目的自体は、人間が IDE で Call Hierarchy を使う理由と同じです。つまり clangd は LLM からの利用を想定していませんが、目的を転用しているわけではなく、同じ目的を人間の手作業から LLM による自動化に置き換えているということです。
clangd が返すのはシグネチャや callees リストといった構造データだけであり、そこから「前提条件が異なる」「影響範囲はここまで」といった意味的な解釈を行うのは LLM の役割です。
自動化できない部分：「影響は実際に伝播するのか」
問題は次のステップになる。investigate コマンドが「関数AはBを呼んでいる」と教えてくれても、修正の影響がB経由で実際に伝播するかは、別の判断が必要になる。
具体例を見てみよう。
int caller() {
int result = foo.calculate(); // ← investigateはここを見つける
int b = result * 2; // resultがbに伝播（Forward Slice判定が必要）
network.send(b); // bがsendに渡される → 影響伝播あり
logger.log("done"); // resultと無関係 → 影響なし
}
clangdは「callerがcalculateを呼んでいる」ことは教えてくれるが、戻り値がcaller内部でどう使われるかは教えてくれない。これはclangdの品質の問題ではなく、LSP仕様に関数内データフローを公開するプロトコルがそもそも定義されていないためだ。
この判定をさらに詳しく見ると、3つのステップに分かれる。
ステップ1：データ依存の追跡
callerのコードを読み、修正メソッドの戻り値がどの変数に代入され、どの文で使用され、どの関数に渡されるかを追跡する。
ステップ2：制御依存の追跡
修正の影響を受ける値が条件分岐（if文やswitch文）の条件式に使われている場合、その分岐先の両方を影響範囲に含める必要がある。
ステップ3：関数境界の漏洩チェック
各callerについて、影響が関数外に「漏洩」するかを判定する。漏洩経路は5つある
- 戻り値
- メンバ変数への書き込み
- 参照/ポインタ引数への書き込み
- グローバル/静的変数への書き込み
- コールバック/observerの発火
漏洩が検出された場合、さらに上位のcallerに対してステップ1〜3を再帰的に繰り返す。この一連の判定が「Forward Slice」であり、現在はLLMがコードを読んで実行している。
なぜ完全な自動化が数学的に不可能なのか
先の説明だけ聞くと自動化できそうな気がするのだが、これがそれほど簡単なものではない。
Riceの定理：1953年に証明された壁
Forward Sliceの完全な自動化が不可能であることは、数学的に証明されている。これはHenry Gordon Riceが1953年に証明したRiceの定理（Rice, 1953. "Classes of Recursively Enumerable Sets and Their Decision Problems." Transactions of the American Mathematical Society, Vol. 74, No. 2, pp. 358-366）から導かれる。
Riceの定理を平たく言えばこうだ。
「このプログラムは○○な振る舞いをするか？」という質問が、YesのものもNoのものもあるなら、それを全自動で正しく判定するプログラムは作れない。
Forward Sliceでやりたいのは、「ある行で作った値が、プログラム中のどの行に影響を与えるか」を突き止めることです。これを正確にやるには、たとえばこんなことを判定しなければなりません：
- あるif文の分岐は、実際に通るのか？
- あるループは、何回まわるのか？そもそも終わるのか？
「このループは終わるのか」はまさに停止問題そのものです。そして停止問題は「自明でない振る舞いの性質」の一例なので、Riceの定理により自動判定できません。Forward Sliceを完全に正確に行うには、こうした判定が必要になるため、完全な自動化は原理的に不可能になる。
具体的に何が決定できないか
C++で静的に（プログラムを実行せずに）決定できないケース
void example(Base* p, int userInput) {
int a = foo.calculate();
// (1) 実行時にしか分からない分岐
if (userInput > 0) {
send(a); // 実行されるか？入力次第
}
// (2) 実行時にしか分からないディスパッチ
p->process(a); // どの実装が呼ばれるか？実行時の型次第
// (3) 実行時にしか分からないポインタ
int* ptr = array[userInput];
*ptr = a; // どのメモリに書いているか？入力次第
}
(1)ではuserInputの値がわからない限りsend(a)が実行されるか決定できない
(2)ではpの実行時型がわからない限りどのオーバーライドが呼ばれるか決定できない
(3)ではuserInputの値がわからない限りポインタの指す先が決定できない
これらはC++特有の問題ではなく、チューリング完全なすべてのプログラミング言語に共通する本質的限界だ。
近似の2つの方向：「見落としゼロ」か「過剰検出ゼロ」か
完全なForward Sliceが不可能であるなら、すべての実用的手法は近似にならざるを得ない。ここで決定的に重要なのは、近似の方向だ。
Sound（健全）な近似
実際の影響範囲を必ず包含する方向に近似する。つまり偽陽性（過剰検出：実際には影響がないのに「影響あり」と報告する）はあるが、偽陰性（見落とし：実際に影響があるのに「影響なし」と報告する）はゼロを保証する。
Complete（完全）近似
逆方向で、報告されたものは必ず実際に影響があることを保証する。偽陰性（見落とし）はあり得るが、偽陽性（過剰検出）はゼロ。
Riceの定理の帰結として、SoundとCompleteを同時に達成することは不可能だ。影響範囲調査においては見落としが最も危険（リリース後にバグとして顕在化する）であるため、sound（見落としゼロ）の方向が望ましい。
Soundなツールは「全部入り」なので見落としはないが、余計なものが混じる。LLMは見落としも誤検出もあり、どちらの方向に間違えるか予測できない。
「ほぼ健全（Soundy）」という選択
理論と実務の間に横たわるギャップを考える必要がでてくる。
2015年にLivshits, Sridharan, Smaragdakisら10名の研究者が発表した論文 In Defense of Soundiness: A Manifesto は、次のようなことを主張している。
「we are not aware of a single realistic whole-program analysis tool (e.g., tools widely used for bug detection, refactoring assistance, programming automation, etc.) that does not purposely make unsound choices.」
私たちは、現実的な単一の全体プログラム解析ツール（たとえば、バグ検出、リファクタリング支援、プログラミング自動化などで広く使われているツール）で、意図的に不健全（unsound）な選択を一切行わないものを、これまで認識していません。
彼らはこの状態を 「soundy（ほぼ健全）」 と名付けています。
全ての実行経路を網羅する完全な健全性が重視されてきましたが、現実の複雑な言語機能（JavaのリフレクションやJSのevalなど）を厳密に扱うと、解析の精度や効率が著しく低下するという課題がありました。著者らは、基本的には健全でありつつも、特定の扱いにくい機能のみを意図的に近似します。
C++ではなぜ特に困難なのか
コンパイラは答えを「知っている」かもしれない
clang はコンパイル時に、AST → CFG → データフロー解析 → 最適化 → コード生成という過程でデータフローを把握している。Forward Slice に必要な情報はコンパイラの内部に存在する。
Sound（見落としゼロ）を目指すとC++では何が起きるか
Sound（偽陰性ゼロ）な Forward Slice は、C++に対しても 原理的には 構築可能のようだ。しかしC++の言語特性が 過大近似を爆発的に増大 させ現実的ではない。
Soundな解析は「分からないものは安全側に倒す」方針を取る。たとえば「このポインタがどこを指すか分からない」場合、「プログラム中のどのメモリでも指しうる」と仮定する。C++では以下の要因により「分からない」ケースが頻出し、この過大近似が雪だるま式に膨らむ。
生ポインタとポインタ演算
*(p + offset)が指す先を静的に限定できない。
reinterpret_cast / void*
型安全性の保証がない型変換は、型ベースのエイリアス解析（TBAA: Type-Based Alias Analysis）を破壊する。
unionとプレースメントnew
同じメモリ領域を異なる型で解釈できるunionや、任意のメモリ位置にオブジェクトを構築できるプレースメントnewは、ポインタ解析の基本的な前提（オブジェクトは個別のメモリ空間に割り当てられ、生涯を通じて単一の型を持つ）を崩す。
テンプレート実体化
テンプレートはコンパイル時にコード量を爆発的に増大させる。解析対象のコードが文字通り何倍にも膨らむ。
多重継承＋仮想関数
仮想ディスパッチ先の候補が多くなり、ポインタ解析の精度が低い場合、あらゆるオーバーライドが候補として残る。
マクロ
テキスト置換による非構造的なコード変形であり、マクロ展開後のコードに対する解析は、ソースコード上の推論と大きく乖離する。
インラインアセンブリ
もはや解析不能
例外処理。
try-catchによる非局所的な制御フローの跳躍は、Forward Sliceが追跡すべきパスの数を爆発させる。
結果として、C++でsound（見落としゼロ）なForward Sliceを実行すると、プログラムのほぼ全体が影響範囲として報告される。「全部影響あります」では調査として役に立たない。
精度を上げるには計算量が爆発する
Forward Sliceの精度は、その基盤となるポインタ解析（Points-to Analysis） の精度に完全に依存する。「変数xの値がどこに流れるか」を追跡するには、「ポインタpがどのメモリを指しているか」を知る必要があるからだ。Wikipediaの "Pointer analysis" の項目にもあるとおり、完全に正確なポインタ解析は決定不能であり、実用的な手法はすべて近似である。
ポインタ解析には精度とスケーラビリティのトレードオフがある。
Steensgaardの解析（単一化ベース）
ほぼ線形時間O(n)で動作し、巨大なコードベースにもスケールする。しかし精度が粗く、ポインタが一度でも同じ場所に代入されると、それらが指し得る対象を全部マージしてしまう。Forward Sliceの入力としては「ほぼ全体が影響範囲」という結果になりやすい。
Andersenの解析（包含制約ベース）
精度が高いがO(n³)の計算量を持ち、大規模コードベースではスケールしない。
フロー感度あり＋コンテキスト感度ありの解析はさらに精密だが、計算量は指数関数的に爆発する。
つまり、精度を上げようとすれば計算が終わらなくなり、スケーラビリティを優先すれば精度が崩壊する。このジレンマはC++に限らず、すべての言語に存在するが、C++の言語特性がこの問題を極端に悪化させる。
数千万行のC++からなるChromium
現実の巨大C++コードベースで考える。
Chromiumブラウザのコードベースは、コメントと空行を除いて 数千万行のソースコード からなる。C++がコードベースの半分以上を占め、BlinkレンダリングエンジンとV8 JavaScriptエンジン、HTTPプロトコル実装、内部キャッシュシステム、拡張API、UIの大部分がC++で書かれている。
Googleですら全プログラム解析を日常的に実行していない
Chromiumの規模感を理解するために、Googleの静的解析に関する実態を見てみよう。
"Lessons from Building Static Analysis Tools at Google"ではは、Google内部の静的解析の現状を教えてくれる。
"Google does not have infrastruc-ture support to run interprocedural or whole-program analysis at Google scale, nor does it use advanced static analysis techniques (such as separa-tion logic7) at scale."
Googleは、Google規模で手続き間（interprocedural）解析や全プログラム解析を実行するインフラ支援を持っていないし、高度な静的解析技術（例えばseparation logic）を大規模には使用していない。
GoogleはGoogle規模で手続き間（interprocedural）解析や全プログラム解析を実行するためのインフラ支援を持っておらず、分離論理（separation logic）のような高度な静的解析技術を大規模には使用していない。
Googleで広く展開されている静的解析は、比較的一般でシンプルなものが主流です、すべてのコードは単一の巨大なリポジトリに格納されており、コード全体にわたる解析を実装するのは非常に困難になっている。
高度な解析システムの実装が優先されてこなかった理由として、以下の点が挙げられています。
莫大な初期投資:
大規模な解析を実行するためのインフラへの先行投資が法外なものになるため
誤検知率を減らすための労力:
開発者に無視されないツールを作るためには、解析チームが研究用のアナライザーの誤検知率を大幅に下げる技術を開発するか、表示されるエラーを厳しく制限する仕組みを作る必要があるため
シンプルなツールによる高い費用対効果:
複雑なチェックは費用対効果を見積もること自体に高い初期コストがかかる一方で、実装すべき「シンプル」なアナライザーはまだ数多く残されており、それらだけでもすでに高い有用性が実証されているため
。
ただし全く使われていないわけではなく、一部のチームは特定の限られたドメイン（Androidアプリなど）において、プロジェクト固有の解析フレームワークを用いて手続き間解析を行っているケースは存在しているとのこと。
さらに、PhASARフレームワークの博士論文 "Scaling Static Whole-Program Analysis to Modern C and C++ Software Development"（Schubert, 2023, University of Paderborn）は、この状況をより広い視点で確認している。
Googleはコードベースへの全コミットに対して高コストな手続き間（全プログラム）解析を実行することを断念している。代わりに、コード変更をまとめて1日の終わりにバッチスタイルで全プログラム解析を実行している。
同論文はさらに踏み込んで、「C/C++を対象とする深い意味論的静的解析のスケーラブルなフレームワークは、実質的に存在しない」と結論づけている。
Forward Sliceは手続き間データフロー解析の一形態であり、まさにこの「Googleですら実行できていない」カテゴリに該当する。
Chromiumプロジェクト自身の経験
Chromiumプロジェクトの開発者メーリングリスト（chromium-dev）での議論も、この現実を裏付けている。
静的解析に関する議論で、2016年にChromium開発者は次のように報告している。「以前はCoverityを使っていたが、偽陽性が多すぎた。Bruceの/analyze botは時々バグを見つけるが、これも偽陽性が多い。Clang Static Analyzerは一時期動いていたが、これも偽陽性が多い」。
別の開発者は、clang-tidyをChromiumのコードベースに適用するための作業を進めていることを報告しつつ、コンパイルデータベースの問題が主要な障壁であると述べている。
既存ツールはこの問題をどう扱うか？
Forward Sliceを自動化できるのだろうか。主要な静的解析ツールを Claude が調査した結果を参考として以下にまとめる。 あくまで参考である。
Coverity
Coverityはバグ検出を目的とした商用静的解析ツールで、手続き間データフロー解析を中核技術とする。ポインタエイリアス・仮想関数ディスパッチ・テンプレート実体化を含めた精密な追跡を行い、null dereference、resource leak、buffer overflow等を検出する。
しかし、Coverityの設計目標は「既知のバグパターンの検出」であり、「任意の関数を起点としたForward Sliceの結果を出力する」というインターフェースは提供していない。検出したバグのレポートに付随する「汚染経路（taint path）」としてデータフロー追跡の結果が断片的に見えるが、汎用のForward Sliceクエリとしては使えない。
前述のとおり、Chromiumプロジェクトでは偽陽性の多さから運用が中断された経緯がある。
CodeQL
GitHub/Semmle社のCodeQLは、ソースコードからリレーショナルデータベースを構築し、Datalog風のクエリ言語でデータフロー・制御フローを問い合わせるツールだ。taint trackingクエリを記述することで、Forward Sliceに近い解析を実行できる。CodeQLの公式ドキュメントによれば、ローカルデータフロー（関数内）とグローバルデータフロー（関数間）の両方をサポートし、taint trackingではデータ値が厳密に保存されないステップ（例：y = x + 1でxのtaintがyに伝播する）も追跡できる。
現存するツールの中で最も柔軟なアプローチだが、実用上の制約は大きい。
source/sinkの事前指定が必須
CodeQLの公式トレーニング資料が明確に述べているとおり、「ローカルデータフローはデータベース内の全関数に対して計算可能だが、グローバルデータフローはパス数が指数関数的に大きくなるため不可能」である。そのため、クエリ作成者がソース（汚染源）とシンク（検出対象）を指定し、探索空間を限定する必要がある。「任意の起点からすべての到達可能文を列挙する」という汎用Forward Sliceを、sourceをany()に設定して実行しようとする試みは、GitHubのCodeQL Discussions #6239で実際に試みられ、期待通りに動作しなかった。
C++のエイリアス処理に既知の制限がある
GitHub CodeQL Discussions #9863では、C++のポインタエイリアシング存在下でtaintが消失するケースが報告されている。CodeQLの開発者自身が「IRデータフローライブラリは相反する優先事項を持っている可能性があり、容易に変更できるとは限らない」と回答している。
構造体ポインタを介したtaint伝播に制限がある
GitHub CodeQL Issues #7053では、構造体ポインタを関数間で渡した際にフィールドのtaintが追跡できないケースが報告されている。
加えて、影響範囲調査用のカスタムクエリの設計・実装・チューニングは非自明な作業であり、プロジェクト固有の知識が必要になる。
Clang Static Analyzer
clangのASTとCFG上でパス感度あり（path-sensitive）のシンボリック実行を行う。カスタムチェッカーをC++ APIを使って書けばデータフロー情報に直接アクセスできるが、チェッカー開発は非自明な作業である。
最大の実用上の制約はパス爆発（path explosion） だ。プログラム中の分岐点が増えるほど探索すべきパスの数が指数関数的に増大し、解析が打ち切られる。Chromiumの公式ドキュメント（"The Clang Static Analyzer," chromium.googlesource.com）でも、Clang Static Analyzerは利用可能であるが、有効なチェッカーはcore、cplusplus、deadcodeの3スイート（それ以外は偽陽性やプラットフォーム不一致のため除外）に限定されていると記されている。
Joern
ソースコードをCPG（Code Property Graph：AST＋CFG＋PDGの統合グラフ）に変換し、グラフクエリでスライスを実行できる。CPG上でデータ依存・制御依存をたどるクエリを書けばForward Sliceに相当する解析が可能だ。ただし、C++対応の成熟度はJava/JavaScript対応より低い。
CppDepend / Understand
関数レベルの依存グラフを出力可能だが、文レベルのデータフローは限定的。Forward Sliceに必要な粒度の解析は提供していない。
ツール比較のまとめ
| ツール | 内部データフロー解析 | 汎用Forward Slice API | C++対応 |
|---|---|---|---|
| Coverity | あり（手続き間） | なし（バグ検出用のみ） | あり |
| CodeQL | あり（taint tracking） | 部分的（source/sink指定が必須） | あり（制限あり） |
| Clang Static Analyzer | あり（パス感度） | なし（チェッカー開発が必要） | あり |
| Joern | あり（CPGクエリ） | あり（クエリ開発が必要） | あり（成熟度低） |
| CppDepend / Understand | 部分的（関数レベル） | なし | あり |
| clangd | コンパイラ内部では実行 | なし（LSP未公開） | あり |
これが現行のmainブランチのドキュメントですね。ここからリンクされている関連ドキュメントも確認させてください。現行のmainブランチのドキュメントを一通り確認できました。先ほどの章を、この最新ドキュメントベースで書き直します。
Chromiumの実例
プログラムスライシングの限界
統合テストレベルでは、プロセス間通信・非同期処理・共有状態などコード上の依存グラフでは捉えきれない経路で影響が伝播する。forward sliceで「何に影響するか」を求めても、実行時の状態やタイミングに依存する影響は静的解析の範囲外になる。
Chromiumのテスト構造
Chromiumの公式ドキュメント（Testing in Chromium）によると、Chromiumには目的の異なる複数のテストがある。
- gtest ： 関数やクラスなど小さな単位の動作を検証する単体テスト
- Browser Tests ： ブラウザ全体を起動して機能の連携を検証する統合テスト
- Web Tests ： Webページの表示（レンダリング）が正しいかを検証するテスト
- Fuzzer Tests ： ランダムな入力を与えてセキュリティ上の問題を見つけるテスト
これらはWindows、Mac、Linux、Androidなど複数のプラットフォームで実行される。
この中で統合テストに相当するBrowser Testsは特に重い。公式ドキュメントによると、1台のマシンで全件実行すると1時間以上かかることもある。当然、「影響のあるテストだけに絞って実行したい」という動機が生まれる。
しかしChromiumの開発方針では、すべてのテストは 他のテストに依存せず、単独で安定した結果を返すべき(hermeticかつstable) とされている。つまり、テスト同士が独立していることが前提の設計になっている。
裏を返すと、テスト同士が独立しているからこそ、「どのテストを選ぶか」ではなく「全部を並列で速く回す」というアプローチが取れる。テストの数が多いという問題は、テストを減らすのではなく、インフラ（大量のマシンによる並列実行）で解決するという方針である。
CQ(Commit Queue)の多層戦略：絞るのではなく段階的に広げる
CQは「Commit Queue」の略で、コード変更（CL）をリポジトリに取り込む前に自動でテストを実行する仕組みのこと。GitHubでいえば、Pull Requestをマージする前にCI（GitHub Actionsなど）が自動で走る仕組みに相当する。ただしChromiumのCQは、テストが通ったらそのままコミットまで自動で行うところまで含む。
現行のCQドキュメントには、4つのモードが定義されている。
-
Dry-Run（CQ+1）
限定的なテストセットを実行し、結果を報告する。CL(Changelist)開発中に繰り返し使うことを想定 -
Full-Run（CQ+2）
Dry-Runと同じテストを実行し、リグレッションがなければコミットする -
Mega-CQ Dry-Run
通常のCQモードよりはるかに多くのテストを実行する。通常のモードは素早いターンアラウンドを優先した限定的なテストセットで、大部分のリグレッションは捕捉するがすべてではない。Mega CQはサイクルタイムに関係なくほぼすべてのリグレッションを捕捉することを目指す -
Mega-CQ Full-Run
Mega-CQ Dry-Runと同じテストを実行し、すべて通ればコミットする
ここで重要なのは、「どのテストが影響を受けるか」を精密に解析して最小セットを選ぶのではなく、時間的制約に応じてテスト範囲を段階的に広げるという設計であることだ。
CLは「Changelist」とは
GitHubに馴染みがある人向けに言えば、Pull Request（PR）とほぼ同じものと考えれば良い。Chromiumが使っているコードレビューシステム（Gerrit）では、PRではなくCLという用語を使う。
CQの実行構造：「全部回して、失敗を振り分ける」
CQがCLを受け取ると、以下の流れでテストが実行される
1. コンパイルと並列実行
CLに影響を受ける可能性のあるテストスイートがすべてコンパイルされる。各テストスイートはシャード（分割単位）に切り分けられ、Swarming（Chromiumが使用しているタスク分散実行システム）を通じて複数のマシンで同時に実行される。
2. 失敗の原因を自動で切り分ける
すべてのテストが通ればそのまま成功となる。問題は失敗が出たときだ。Chromiumの規模では、失敗の原因は3つ考えられる。
- このCLがテストを壊した（本物のバグ）
- テスト自体が不安定で、たまたま失敗した（フレーキーテスト）
- CL以前から壊れていた（tip-of-treeの問題）
CQはこの3つを消去法で切り分ける。
まず、失敗したシャードをそのままもう一度実行する。ここで成功すれば、最初の失敗はフレーキーだったと判断して無視する。
リトライでも失敗した場合は、次にCLを取り除いた状態（変更前のコード）で同じテストを実行する。これでも失敗するなら、そのテストはCLとは無関係にもともと壊れていると判断し、やはり無視する。
CLなしでは成功するのにCLありでは2回とも失敗する場合のみ、「このCLが原因」と判定し、CQを失敗にする。
3. なぜこの仕組みが必要か
CQドキュメントによると、Chromiumには約20,000件のフレーキーテストが存在する。リトライの仕組みがなければ、事実上どのCLもCQを通過できない。
ここでのポイントは、Chromiumが「どのテストを実行するか」の精度を上げることではなく、「テストは広く実行した上で、失敗の原因を自動判定するロジック」で品質を担保しているということだ。影響範囲を正確に絞り込めなくても、実行結果の判定が賢ければ開発は回る。
Swarning
SwarningとはGoogleが開発したタスク分散実行システムで、テストの実行を、 大量のマシンに自動で振り分けて並列に走らせる仕組みを実現する。
フレーキーテスト（flaky test）の規模感
現行CQドキュメントには具体的な数字も記載されている。
CQにはおよそ 20,000件 のフレーキーテストが存在しており、リトライなしでは事実上どのCLもCQを通過できない。
この数字は、「全部回す」戦略を取る場合にフレーキーテスト管理がいかに不可避かを端的に示している。フレーキーテストの追跡には LUCI Analysis が使われており、対処方法が記載されている。
フレーキーテスト（flaky test）
フレーキーテストとは同じコードに対して、あるときは成功し、あるときは失敗するテストのことです。
発生する理由
テストの結果が「コードの正しさ」以外のものに影響されている。よくある原因は、処理のタイミング（非同期処理が終わる前に結果を見てしまう）、テストの実行順序（前のテストが残したゴミデータに影響される）、ネットワークやディスクなど外部の状態（たまたま遅かった、たまたまビジーだった）、といったものだ。
問題点
一番困るのは「テスト結果を信じられなくなる」ことだ。
テストが失敗したとき、普通は「コードにバグがある」と判断する。しかし、フレーキーテストがあると「どうせまた気まぐれでしょ」と思うようになる。そうなると、本物のバグによる失敗まで見逃す。
Chromiumでは特に深刻だ
Chromiumは「テストを絞るより全部回す」という戦略を取っている。数万件のテストを毎回実行するので、仮にフレーキー率が0.1%でも、毎回数十件の「嘘の失敗」が出ることになる。Chromiumでは失敗したテストを自動でリトライする仕組みや、フレーキーテストを検出して統計的に追跡する専用ツール（Findit）が開発されている。「全部回す」戦略は、フレーキーテスト管理とセットでなければ成立しない。
まとめ
コード変更の影響範囲を完全に自動追跡することは、1953年にRiceが証明した数学的事実により、原理的に不可能だ。すべての実用的手法は近似であり、その近似の方向（見落としゼロを優先するか、過剰検出ゼロを優先するか）が解析の性質を決定する。
C++ではポインタ演算、テンプレート、マクロ、多重継承、例外処理等の言語特性が近似の爆発を引き起こし、sound（見落としゼロ）な解析は「プログラム全体が影響範囲」という実質無意味な結果を返す。実用的なツールはsoundnessを意図的に妥協しており、Livshitsらが2015年に指摘したように、これは例外ではなく業界標準だ。
Chromium規模（3,600万行）のコードベースでは、スケーラビリティの壁が言語特性の壁に加わる。Googleですら手続き間・全プログラム解析を日常的には実行していない。この制約はC++に限らず、JavaやGoであってもChromium規模では深刻な問題となる。