Skip to content

fix(processor): bound dependency-cycle detection #1103

Description

@doublewhy

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 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.
  • PR fix(runtime): close control-plane, timeout, and scheduler failure-handling gaps #1086 currently bundles the same processor correction with unrelated runtime work; this issue supports an independent reviewable successor.

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 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

  1. Do nothing / evidence only. Rejected because a valid deep acyclic graph can abort planning without a typed diagnostic.
  2. Increase Python's recursion limit. Rejected because it is process-global, interpreter-dependent, and trades a deterministic model limit for C-stack risk.
  3. 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.
  4. 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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions