fold/docs/research/single-pass-graph-design.md

Single-pass graph building — design spec

Status: accepted (README-documented; backlog #1) Owner: fold optimization loop (round 4+), operator-confirmed option 2. Guard rails: docs/research/optimization-loop-2026-07-30.md (measure-first, gates never weakened), the finding-fingerprint + gold gates, and the wall/RSS baselines.

Goal

Eliminate the second full per-scan parse. Today a source scan parses every TU twice — once to build the project call graph (call_graph_ms 18.8s on the fold self-scan), once to run detectors — because the detector pass consumes the graph (cross-TU candidate expansion + summary priming). The portability-safe fix is one parse per TU; the graph comes from that same parse.

Current sequence (scan_runner.cpp runClangDetectorsOnShard)

1. primeCrossTUProperties — third ClangTool parse, only when div-by-zero/null-deref/int-overflow/oob are enabled (no-op on the fold manifest).
2. assembleProjectCallGraph — full re-parse of all TUs → call_graph (graph_security_candidates = cross-TU-expanded candidate set).
3. Detector pass — second full parse, runs every detector; the security walk consults graph_security_candidates, and summary priming uses the graph for SCC-ordered passes.

Why it cannot be folded naively

The candidate-expansion closure needs the complete cross-TU graph, which exists only after every TU is parsed. Running detectors in the very parse that builds the graph therefore works only for graph-independent detectors. Graph- dependent detectors (security candidate expansion; summary priming) demand, in the deferred phase, either (A) kept ASTs (~210MB/AST — infeasible at 8 TUs), or (B) re-materializing the walk input from persisted IR.

(B) is the chosen shape: encode functions to fold IR once, keep the lightweight records, discard ASTs, run the closure, then walk candidates from the stored IR without a re-parse.

Seams

Existing	Change
collectCallGraphEdges(ctx, local_graph) (source_call_graph.cpp)	already runs on a live clang::ASTContext; in-pass graph contribution is the same call + graphToContribution — no re-parse
SecurityWalker / detectors encode via encodeExpr + visitor hooks on the AST	the deferred walk must run on serialized FunctionIR (see fold/ir, serialize.cpp, FunctionSummary) instead of the live AST
graph_security_candidates + securityCandidateFunctions	unchanged consumer; its input (merged graph) is available only post-pass
primeSymbolicSummaries SCC order	unchanged consumer; needs the post-pass graph

Slice plan (each lands behind the gates; fingerprints exact)

• S0 (measure, no behavior change) — confirm the 18.8s is ClangTool parse vs edge/merge, and measure the IR size for all fold-manifest functions (bounds the memory for kept-IR). If per-function IR is ~KB-scale, (B) fits in tens of MB.
• S1 (neutral plumbing) — a --single-pass-graph flag, default off; no behavior change.
• S2 — collect graph contributions in the detector pass (S1 gate on), retire the assembleProjectCallGraph re-parse for the no-index path when contributions cover the shard's files.
• S3 — defer the graph-dependent security candidate expansion + summary priming to the post-pass closure; walk from serialized IR.
• S4 — fold primeCrossTUProperties into the same parse for the div/null-deref/overflow/oob corpora.

Each slice: focused tests → full suite → fold + yams eval (fingerprints 0fec78e5… / 247523c5… EXACT, gold precision/recall 1.0, wall/RSS baselines) → checkpoint.