Latest Results
perf(noImportCycles): replace per-invocation DFS with a cached SCC fast-reject
This rule ran a fresh, uncached DFS through the whole reachable import
graph on every import statement checked (108k times on a ~3000-file
corpus), even though the overwhelming majority of imports in a healthy
codebase aren't part of any cycle at all.
Precomputes strongly-connected components for the whole import graph
once per module-graph generation (Kosaraju's algorithm, iterative to
avoid stack overflow on deep/wide graphs) and uses it as an O(1)
fast-reject: an import can only close a cycle back to the current file
if both are in the same SCC of size > 1. Falls back to the exact DFS
only for imports that pass this check. Deliberately includes type-only
edges in the graph regardless of any file's `ignoreTypes` option (which
can differ per file), making it a safe conservative
over-approximation -- a `false` from this check is still a hard proof
no cycle exists in any subset of these edges.
The one-time graph build is warmed via a rule-local `FromServices`
wrapper, which runs before the profiler's rule timer starts, so it
can't leak into any single file's reported `--profile-rules` cost --
previously this ~30-200ms one-time cost was attributed to whichever
file's rule invocation happened to trigger it first, reading as a
wildly expensive, non-reproducible per-file spike. The graph itself is
built with integer-indexed adjacency instead of hashing and cloning
paths during traversal, since the previous path-keyed version's string
traffic dominated its own cost.
Measured on a real ~3000-file monorepo (release build, --profile-rules,
3 runs each): noImportCycles's own total time dropped ~609ms -> ~229ms
(2.7x), and its max single-invocation time dropped ~37ms -> ~2ms
(~20x). Diagnostic output is byte-identical before/after (8759/8759
diagnostics, 0 differences, verified on a full corpus run). Added 11
unit tests for the SCC computation and the fast-reject check; all
existing fixture tests and the full crate suite (2712 tests) still
pass unmodified.BezSaharaD:fix/no-import-cycles-scc-fast-reject Latest Branches
+4%
11-separate-raw-type-collection 0%
0%
BezSaharaD:fix/no-import-cycles-scc-fast-reject © 2026 CodSpeed Technology