Python: bound shared CFG node reachability through basic blocks - #22699

Summary

This draft prevents semmle.python.controlflow.internal.Cfg::ControlFlowNode.strictlyReaches from materializing a large transitive closure over individual CFG nodes. It computes cross-block reachability through the shared BasicBlock graph and uses node indices only within one block.

The PR has exactly two commits:

1. add a direct inline-expectation shared-CFG reachability contract test;
2. rewrite node reachability through BasicBlocks.

There are currently no production callers of this private shared-CFG method. This is a preventative peak-cardinality/memory guardrail, not a recovery of #21925's current fleet regression and not a demonstrated throughput optimization. No DCA was launched.

Shared-library use

The implementation uses the shared BasicBlock.Make support for canonical BasicBlock partitioning, cached node-to-block membership, and cached immediate BasicBlock successors.

The shared BasicBlock API does not currently expose a canonical pairwise reachability predicate. The Python facade therefore defines BasicBlock.strictlyReaches as the transitive closure of the shared immediate-successor relation. codeql.controlflow.ControlFlowReachability is a higher-level SSA/guard reachability analysis, not a replacement for generic BasicBlock-pair reachability.

The implementation adds no broad QL cache for the complete block-pair closure. The node wrapper remains inline so caller bindings can specialize the block closure.

Inline-only correctness contract

The fixture uses only standard inline expectation comments. There are no marker calls and no pair/truth whitelist in QL.

Fixture identifiers follow one generic structural convention:

reachability_<case>_source
reachability_<case>_destination  # $ reaches=<case>

or, for a negative relation:

reachability_<case>_destination = ...  # $ not-reaches=<case>

The QL query generically pairs store NameNodes whose identifiers share the same <case>, invokes shared-CFG source.strictlyReaches(destination), and emits the actual reaches or not-reaches tuple at the destination location. InlineExpectationsTest performs the repository-standard missing/spurious comparison against the comments; the generated expected file is empty when the contract holds.

Coverage includes:

• forward and reverse ordering within one BasicBlock;
• both branch arms reaching a join;
• branch siblings not reaching each other;
• a loop backedge and loop exit;
• non-reachability across distinct scopes.

The focused test passes before and after. Exact decoded output is unchanged (CSV SHA-256 6bc0907e8f5ea1c0aeb7c301999be9ba2749eb8241fcf0ec2788830935754b2a), and codeql bqrs diff reports zero left-only and zero right-only rows for both cold and prewarmed controls. Full cold BQRS hashes differ only in metadata: before 2d4a8606a542a39c23d3e6762b162830d73c80d0b13f07350d953f510535f329, after 230bec3cec1afcfba27e2d51c44bf75a16ec7d5d6c584da7f6343c9c43e5b225.

Performance-measurement cache discipline

Cold baseline and candidate measurements used separate, fresh evaluator caches and isolated database copies. No evaluator cache directory was shared between revisions.

The BasicBlock-prewarmed comparison was a separate lifecycle control. Each revision first populated its own isolated cache with the same shared-CFG BasicBlock workload, then ran the inline-expectation node query against that same-revision cache. This distinguishes cold whole-query behavior from marginal behavior after the common block infrastructure exists; it does not let one revision inherit cache state from the other.

Exact local performance evidence

Measured with CodeQL CLI 2.26.3, isolated fresh databases and compilation/evaluation caches, serial evaluation (-j1 -M8192 --tuple-counting --keep-full-cache). Timing is secondary and shown only for transparency.

Cold direct query

Shared-CFG BasicBlock reachability prewarmed

The prewarm itself is deterministic-work identical on both commits: 21,605 joined tuples, 765 pipelines, 805 materializations, 20 CACHACA hits, maximum predicate result 285, and maximum pipeline cardinality 286.

The rewrite removes the broad node-level materialization and bounds peak predicate cardinality. However, both cold and prewarmed controls show slightly higher joined-tuple, pipeline, materialization, and compiled-plan totals. Earlier bounded scaling controls with the same semantic pair contract likewise found no deterministic-work crossover even as the raw node closure grew much faster; the inline-only redesign preserves that conclusion in fresh cold and reuse controls.

Accordingly, this draft is framed only as preventative API design and cardinality containment—not as a demonstrated performance win.

Validation

• focused inline-only test passes on commit 1 and commit 2;
• 8/8 focused/shared-CFG tests pass;
• cold and prewarmed outputs are exact;
• QL formatting passes;
• git diff --check passes;
• exactly two commits over 0aad85c9e2bbbfc2b78935a8a98c1177b764dbb7;
• no DCA was launched.