You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
dependency_cycles() performs a linear Tarjan traversal, but its depth-first walk is recursive. Recursion depth therefore tracks the longest dependency path, so sufficiently deep valid graphs raise RecursionError before the planner can return an order or a cycle diagnostic. The defect is unbounded call-stack consumption, not repeated whole-graph traversal.
This is a RUN-303 reference-processor reliability gap. It does not change SDL dependency meaning or the published plan contracts.
2. Existing Surface Audit
raes_processor.semantics.planner.dependency_graph() owns normalization and excludes unknown dependency references.
dependency_cycles() owns strongly connected component detection and canonical cycle ordering.
resource_dependency_cycles() adapts compiled resources to that shared semantic function.
raes_processor.planner.ordering._ordering_cycle_diagnostics() preserves domain-specific diagnostic codes, addresses, and messages.
topological_dependency_order() is already iterative, but it cannot replace SCC detection because it identifies residual nodes without preserving the existing component diagnostics.
The authoring validator has separate feature-cycle validation; moving planner resource semantics there would be a downstream-incomplete fix.
The RUN-303 formal planner specification, published plan schemas, parser aliases, SDL models, runtime lifecycle consumers, and generated contracts require no change.
RUN-303 owns shared planning, ordering, refresh, and applicability semantics. The canonical implementation family is implementations/python/packages/raes_processor/semantics/planner.py, with planner adaptation in planner/ordering.py, formal boundaries in specs/formal/planner/dependency-ordering.md, and regression coverage in test_semantics_planner.py and test_runtime_planner.py.
The correction extends that family. It does not introduce a second dependency graph, validator, cycle model, or diagnostic surface.
4. Literature and Practice
Tarjan's strongly connected component algorithm is a linear graph algorithm: Robert Tarjan, “Depth-First Search and Linear Graph Algorithms,” SIAM Journal on Computing 1(2), 1972, https://doi.org/10.1137/0201010. Python documents its recursion limit as protection against C-stack overflow, so increasing or depending on that process-global bound is not a portable graph-size policy: https://docs.python.org/3/library/sys.html#sys.getrecursionlimit.
An explicit DFS frame stack preserves Tarjan's index, low-link, and component-stack invariants while moving authored-depth consumption from the interpreter call stack to ordinary bounded-by-input data structures.
5. Alternatives
Do nothing / evidence only. Rejected because a valid deep acyclic graph can abort planning without a typed diagnostic.
Increase Python's recursion limit. Rejected because it is process-global, interpreter-dependent, and trades a deterministic model limit for C-stack risk.
Use only the existing topological sort. Rejected because residual nodes do not preserve the established strongly connected components, self-cycle handling, or deterministic diagnostic grouping.
Iterative Tarjan traversal over the existing normalized graph. Chosen because it preserves outputs and O(V + E) work while removing recursion proportional to dependency depth.
6. Chosen Architecture
Drive the existing Tarjan traversal with explicit (node, remaining-dependencies) frames. Continue to use the current normalized graph, canonical resource identity ordering, component stack, wrappers, and planner diagnostics. Unknown references remain excluded, self-cycles remain reportable, and no schema or public API changes.
7. Documentation Defense
Add a focused preflight note that records the stack-safety defect, canonical ownership boundary, compatibility claims, rejected alternatives, and verification boundary. Extend RUN-303 traceability to the issue, implementation, note, and tests. No ADR amendment is needed because the normative dependency semantics and observable diagnostics remain unchanged.
8. Verification Plan
Differentially compare the iterative implementation with a deliberately simple recursive Tarjan oracle over dense generated graphs.
Cover self-cycles, multi-node and overlapping components, unknown references, mapping/edge insertion order, and deterministic output.
Exercise an acyclic chain beyond Python recursion depth and a large cycle without a wall-clock threshold.
Run relevant planner/runtime regressions, branch-instrumented changed-code coverage, Ruff, repository policy, requirement governance, and the canonical verification graph.
1. Gap Claim
dependency_cycles()performs a linear Tarjan traversal, but its depth-first walk is recursive. Recursion depth therefore tracks the longest dependency path, so sufficiently deep valid graphs raiseRecursionErrorbefore the planner can return an order or a cycle diagnostic. The defect is unbounded call-stack consumption, not repeated whole-graph traversal.This is a RUN-303 reference-processor reliability gap. It does not change SDL dependency meaning or the published plan contracts.
2. Existing Surface Audit
raes_processor.semantics.planner.dependency_graph()owns normalization and excludes unknown dependency references.dependency_cycles()owns strongly connected component detection and canonical cycle ordering.resource_dependency_cycles()adapts compiled resources to that shared semantic function.raes_processor.planner.ordering._ordering_cycle_diagnostics()preserves domain-specific diagnostic codes, addresses, and messages.topological_dependency_order()is already iterative, but it cannot replace SCC detection because it identifies residual nodes without preserving the existing component diagnostics.3. Lineage and Precedent
RUN-303 owns shared planning, ordering, refresh, and applicability semantics. The canonical implementation family is
implementations/python/packages/raes_processor/semantics/planner.py, with planner adaptation inplanner/ordering.py, formal boundaries inspecs/formal/planner/dependency-ordering.md, and regression coverage intest_semantics_planner.pyandtest_runtime_planner.py.The correction extends that family. It does not introduce a second dependency graph, validator, cycle model, or diagnostic surface.
4. Literature and Practice
Tarjan's strongly connected component algorithm is a linear graph algorithm: Robert Tarjan, “Depth-First Search and Linear Graph Algorithms,” SIAM Journal on Computing 1(2), 1972, https://doi.org/10.1137/0201010. Python documents its recursion limit as protection against C-stack overflow, so increasing or depending on that process-global bound is not a portable graph-size policy: https://docs.python.org/3/library/sys.html#sys.getrecursionlimit.
An explicit DFS frame stack preserves Tarjan's index, low-link, and component-stack invariants while moving authored-depth consumption from the interpreter call stack to ordinary bounded-by-input data structures.
5. Alternatives
6. Chosen Architecture
Drive the existing Tarjan traversal with explicit
(node, remaining-dependencies)frames. Continue to use the current normalized graph, canonical resource identity ordering, component stack, wrappers, and planner diagnostics. Unknown references remain excluded, self-cycles remain reportable, and no schema or public API changes.7. Documentation Defense
Add a focused preflight note that records the stack-safety defect, canonical ownership boundary, compatibility claims, rejected alternatives, and verification boundary. Extend RUN-303 traceability to the issue, implementation, note, and tests. No ADR amendment is needed because the normative dependency semantics and observable diagnostics remain unchanged.
8. Verification Plan