feat(dag): Cycle & Deadlock Detection for Interdependent Contract Plans

[sdageltc]

Summary & Motivation

In letitloop, complex goals are planned as a Directed Acyclic Graph (DAG) of contracts with depends_on: ["task_a", "task_b"]. If an LLM planner accidentally generates cyclic dependencies (e.g. Task A depends on Task B, which depends on Task A) or references non-existent task IDs, the supervisor can stall in an unresolved WAITING state without clear user diagnostics.

---

Proposed Improvements

1. Topological Plan Validator (orchestrator/dag_validator.py):
   • Executes Tarjan's or Kahn's algorithm on plan.contracts during plan creation and resume.
   • Detects:
     • Direct cycles (A -> B -> A)
     • Indirect multi-node cycles (A -> B -> C -> A)
     • Dangling dependencies (referencing task IDs not defined in the plan)
     • Self-referential dependencies (A -> A)
2. Actionable CLI Diagnostics:
   • If a cycle is detected, print a formatted ASCII cycle trace: Cycle detected: task_auth -> task_db -> task_auth and prompt the planner to auto-repair the plan before execution begins.

---

Key Files

• orchestrator/planner.py
• orchestrator/supervisor.py
• tests/test_dag_validator.py

---

Acceptance Criteria

• Rejects cyclic and invalid contract DAGs before any worker is dispatched.
• Produces human-readable cycle traces.
• Includes comprehensive unit tests with various graph topologies (diamonds, linear, disjoint trees, cyclic).