Repository navigation
L2 call graph is nondeterministic run-to-run (PyCG fixpoint under --pycg-max-iter) #99
Description
PROBLEM
Two back-to-back runs of canpy -i test/fixtures/whole_applications/requests -a 4 --no-ray with fresh caches produce different call graphs: 1027 vs 1057 edges. Every divergent edge carries prov:["pycg"]. Example instability: the same call resolving to requests.compat.MutableMapping.get in one run and collections.abc.MutableMapping.get in the other.
Separately, --ray vs --no-ray disagree on Jedi type inference for external symbols (e.g. pytest.main(...) inferred int in-process vs ExitCode in the Ray worker), shifting ~12 call-graph edges and ~35 param edges on the same fixture — the worker's interpreter environment resolves stubs differently than the parent process.
Observed 2026-07-14 on feat/v2-stage5-docs-release @ 3d39bbf during the stage-5 release gates (determinism gate: same-flags output must be byte-identical).
LIKELY MECHANISM
PyCG's fixpoint is capped (--pycg-max-iter, default 50) and its iteration order over the access-path domain is not stabilized, so a capped run stops at a different frontier each time. The cap itself is a documented sound-but-incomplete trade-off (CHANGELOG 0.3.0); the run-to-run variance is not.
IMPACT
- The v2 determinism gate cannot pass at L2+ as specified.
- Downstream monotonicity/superset comparisons across runs are noisy.
- Not a regression from the schema-v2 work — PyCG landed in 0.3.0 and the behavior predates the v2 chain. Shipping 0.4.0 with this as a known-limitation release note is defensible; fixing it means stabilizing PyCG's iteration order (sorted worklists) or emitting only the converged subset.
REPRO
canpy -i test/fixtures/whole_applications/requests -a 2 --no-ray -c /tmp/c1 -o /tmp/o1
canpy -i test/fixtures/whole_applications/requests -a 2 --no-ray -c /tmp/c2 -o /tmp/o2
diff <(jq -S .application.call_graph /tmp/o1/analysis.json) <(jq -S .application.call_graph /tmp/o2/analysis.json)
Activity
rahlk commentedon Jul 15, 2026
Status after PR #101 — all systematic sources fixed; one environmental residue remains.
Root causes found and closed:
--pycg-max-iter) iterates hash-ordered sets keyed on module/access-path strings; an unpinned per-interpreter seed shifted the frontier arbitrarily — observed 1,527 vs 4,712 edges on identical input. The CLI now re-execs once withPYTHONHASHSEED=0(export the var to opt out/override); Ray workers get the pinned seed via the runtime env.mkdtemp, and PyCG state keys on absolute module paths — a fresh random suffix changed the analysis input every run. The root is now content-derived (sha1 of project + shard files) with a sidecar flock so concurrent analyses of one project serialize instead of clobbering each other.call_graphinherited backend iteration order. Both are canonically sorted._IOBase | BufferedRandom | TextIOWrapper) resolved to a different member per run (we took whichever candidate came first). Candidates are now tie-broken deterministically, andNoneTypeis filtered from return-type candidates (Jedi flaps between yielding{NoneType}and{}for the None arm of anOptional).Verified by repeated
-a 2runs on the requests fixture: byte-identical except, intermittently, one field —resolve_proxies'senviron_proxies.get(...)return_type— whose inference requires compiled introspection through jedi's helper subprocess; when that subprocess hiccups (it is load/OOM-sensitive and jedi degrades silently), the field is absent for that run. That residue is environmental and upstream (jedi), not fixable by seeding or ordering; leaving this issue open, rescoped to it. Regression gate in the suite:test_l2_runs_are_byte_identical.rahlk commentedon Jul 16, 2026
Fixed by PR #101 (commit ae2df74), released in v1.0.1 (2026-07-15). All four nondeterminism sources are closed: PYTHONHASHSEED pinned for PyCG's fixpoint, content-derived PyCG project root, sorted entry points + canonically ordered call_graph, and deterministic Jedi tie-breaking. Guarded by
test_l2_runs_are_byte_identicaland the #87 audit gate — both verified green today on main @ 16e765a.