Repository navigation
Commit 318aed9
Rewrite resolver as two-phase iterative algorithm
Replace the mutually recursive _resolve_partial/_dereference cycle
with a two-phase design that uses zero Python call-stack recursion:
Phase 1 (Discovery): BFS over the spec collecting all $ref sites,
fetching raw target values, and building the dependency graph.
Cycle detection uses proper DFS white/gray/black coloring so
diamond patterns are correctly distinguished from actual cycles.
Phase 2 (Resolution): Kahn's topological sort processes targets
leaves-first. Forward deps are simple lookups into the resolved
map. Recursive deps (back-edges) are unrolled inside-out up to
recursion_limit times with no call-stack involvement.
This eliminates CWE-674 (Uncontrolled Recursion): deep linear
$ref chains and high recursion_limit values no longer overflow
Python's C stack. A 5000-deep chain resolves in ~330ms instead
of crashing at depth ~500.
Also adds deep-chain and recursive-ref stress tests to the
profiling script.
Co-authored-by: Cursor AI <[email protected]>
Co-authored-by: Anthropic Claude Opus 4.6 <[email protected]>1 parent 616381f commit 318aed9
2 files changed
Lines changed: 448 additions & 103 deletions
0 commit comments