PyCG sharding: Jedi planner + adaptive decomposition of runaways#49
Merged
Merged
Conversation
Sharding lets PyCG (level 2) scale past its ~500-file ceiling by analysing
the project in independent pieces. The existing scheme shards one-per-package
with a flat file-count ceiling, which is blind to call coupling: it severs
heavily-interacting modules (their cross-shard edges become ghost nodes PyCG
never resolves) and drops oversized packages wholesale.
Add a coupling-aware planner that partitions the module-dependency graph
*derived from the Jedi call graph already computed at level 1*:
1. project Jedi callable->callable edges onto a weighted module DiGraph;
2. condense strongly-connected components (import cycles become atomic and
are never split across shards);
3. cluster with Louvain so tightly-coupled modules co-compute;
4. enforce the per-shard file budget (re-partition oversized communities,
then merge/first-fit-pack the remainder to recover edges and cut count).
The reported cut_ratio (fraction of Jedi edge weight crossing shard
boundaries) is an upper bound on PyCG edges lost to sharding; on a synthetic
worst case it drops from 0.55 (per-package) to 0.03.
Wire it into PyCG behind --pycg-shard-strategy {jedi,package} (default jedi).
Because planner shards are arbitrary file sets rather than directories, each
runs through a temporary symlink mini-project (_shard_symlink_root) so PyCG's
own package-root bound confines analysis to the shard and emits
project-relative edge names with no prefix rewrite.
Thread the level-1 Jedi edges through core -> _get_pycg_call_graph ->
build_call_graph_edges to feed the planner. Ray parallelism falls back to
sequential under the jedi strategy for now.
Add test/test_shard_planner.py (graph projection, SCC atomicity, budget,
single-assignment, cut-ratio vs naive, determinism).
Materialise each planned file-set shard as a symlink mini-project up front (the trees must outlive their remote tasks), submit one Ray task per shard, and collect against a single wall-clock deadline (Ray workers can't use SIGALRM, so the timeout is enforced at the orchestrator, mirroring _build_sharded_ray). Symlink trees are cleaned up once the batch completes. Factor _materialize_shard_root out of the _shard_symlink_root context manager so both the sequential and Ray paths share tree construction. Under --ray the jedi strategy now parallelises instead of falling back to sequential.
PyModule.module_name is only the file stem (py_file.stem), which collides heavily across a real project — every __init__.py, models.py, views.py shares a name. Keying the partition graph by module_name collapsed all same-stem files into a single node and, via the last-wins module_name->file_path map, silently dropped every colliding file but one from the shards. Observed on odoo: a 1028-file symbol table produced a graph of only 399 nodes (4 fat shards), so ~600 files were never handed to PyCG. Key graph nodes by file_path (unique) instead; carry module_name as a node attribute for readable reporting. plan_shards now emits file-path shards directly (no name->file remap) with a parallel module_shards name view. Add a regression test asserting every file lands in exactly one shard under stem collisions, and update graph tests for file-keyed nodes.
…n-tree deps Two robustness fixes for level-2 PyCG, motivated by odoo divergence analysis. 1. max_iter cap (--pycg-max-iter, default 50). PyCG runs its PostProcessor fixpoint with max_iter=-1 (until convergence). Its abstract domain is field-sensitive access paths with no k-limiting/widening, so on heavy metaclass/mixin code the def set balloons (measured: 23 odoo ORM files -> 7.3k defs pass 0, 8.4k pass 1) and convergence may need many O(defs^2) passes. Capping passes returns a sound-but-incomplete graph and guarantees termination even with --pycg-shard-timeout 0 (which previously hung forever on a single diverging shard). Threaded through _run_pycg_batch and the Ray worker. Note: the wall-clock timeout is still the guard for shards whose individual passes exceed it. 2. Dependency exclusion. PyCG bounds analysis to its package dir via "if mod_dir not in mod.__file__". The whole-project path used package=project_dir, but an in-tree .codeanalyzer venv / site-packages lives under project_dir, so PyCG followed imports into dependencies and exploded. Run the whole-project path inside a symlink mini-project (as the shards already do) whose root mirrors only the SKIP_DIRS-filtered source, so deps resolve outside mod_dir and stay ghost nodes. Add test/test_pycg_sharding.py (max_iter threading; in-tree dep stays a ghost and its internals are never analysed).
A uniform shard ceiling forces a global choice: small shards everywhere (high cut, low recall) just to tame the few that diverge. Instead, start coarse and re-shard only the shards that time out. Algorithm: plan shards with SCC + Louvain at the ceiling, run each through PyCG, and treat any timed-out shard as a runaway. Re-partition that runaway's files alone at half the budget and re-run. Repeat down to a floor (10 files). Files that still diverge at the floor, or form an atomic cycle that will not split, fall back to Jedi-only coverage. Refactor the planned executor into a reusable primitive that returns (edges, runaways), used by both the sequential and Ray paths, and drive it from an adaptive loop. Odoo benchmark (1028 modules, level 2, Ray): 22210 PyCG edges, up from 17149 for the best uniform ceiling, with only 20 of 1028 files irreducible. Cost is wall time (about 12.7 min) since rounds run in sequence. Add a unit test driving the adaptive loop with a stubbed runner.
rahlk
added a commit
that referenced
this pull request
Jun 27, 2026
…deql Merge pull request #49 from codellm-devkit/feat/jedi-shard-planner
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Shards PyCG (level 2) by Jedi module coupling instead of a flat file count, then recovers shards that diverge by re-sharding them.
How sharding works now:
Why: a uniform ceiling forces every shard small (severs many edges) just to tame the few that diverge. Starting coarse keeps the cut low, and only the shards that time out get split.
Telemetry (benchmark app: Odoo, 1028 modules, level 2, Ray). PyCG edges recovered:
Adaptive recovers 22210 edges (+30% over the best uniform run), and loses only 20 of 1028 files instead of a whole 100-file shard.
Also in this branch:
Caveats: