"CUO topological walk of `depends_on` chain — orchestrates multi-step skill invocations with composite audit row + per-step sub-rows"

§1 — Description (BCP-14 normative)

The CUO service MUST ship chain walker at services/cuo/src/chain/ with topo sort + cycle detect + composite audit + sub-rows per step, 6 memory audit kinds.

1. MUST validate chain_status against closed enum per DEC-2341.

1. MUST sort topologically at topological_sorter.rs::sort(skills_with_deps) per DEC-2340:

• Build DAG from depends_on edges
• Kahn's algorithm or DFS topo
• Return ordered list of skills

1. MUST detect cycles at cycle_detector.rs::has_cycle(graph) per DEC-2342 — reject plan if true.

1. MUST walk at walker.rs::walk(plan) per DEC-2340:

• Execute skills in topo order
• Capture per-step sub-row (skill_id, started_at, completed_at, status, result)
• Update composite row status

1. MUST define tables at migration 0004: ```sql CREATE TABLE cuo_chain_walks ( chain_id UUID PRIMARY KEY, tenant_id UUID NOT NULL, run_id UUID NOT NULL, plan_jsonb JSONB NOT NULL, status TEXT NOT NULL DEFAULT 'planning' CHECK (status IN ('planning','executing','completed','failed','partial_rolled_back')), started_at TIMESTAMPTZ NOT NULL DEFAULT now(), completed_at TIMESTAMPTZ, failure_reason TEXT, trace_id CHAR(32), created_at TIMESTAMPTZ NOT NULL DEFAULT now() ); ALTER TABLE cuo_chain_walks ENABLE ROW LEVEL SECURITY; CREATE POLICY chain_rls ON cuo_chain_walks USING (tenant_id = current_setting('auth.tenant_id')::uuid) WITH CHECK (tenant_id = current_setting('auth.tenant_id')::uuid); REVOKE UPDATE, DELETE ON cuo_chain_walks FROM cyberos_app; GRANT UPDATE (status, completed_at, failure_reason) ON cuo_chain_walks TO cyberos_app;

CREATE TABLE cuo_chain_steps ( step_id UUID PRIMARY KEY, tenant_id UUID NOT NULL, chain_id UUID NOT NULL REFERENCES cuo_chain_walks(chain_id), step_order INT NOT NULL, skill_id TEXT NOT NULL, status TEXT NOT NULL DEFAULT 'pending' CHECK (status IN ('pending','running','completed','failed','skipped')), started_at TIMESTAMPTZ, completed_at TIMESTAMPTZ, result_jsonb JSONB, failure_reason TEXT, UNIQUE (chain_id, step_order) ); ALTER TABLE cuo_chain_steps ENABLE ROW LEVEL SECURITY; CREATE POLICY steps_rls ON cuo_chain_steps USING (tenant_id = current_setting('auth.tenant_id')::uuid) WITH CHECK (tenant_id = current_setting('auth.tenant_id')::uuid); REVOKE UPDATE, DELETE ON cuo_chain_steps FROM cyberos_app; GRANT UPDATE (status, started_at, completed_at, result_jsonb, failure_reason) ON cuo_chain_steps TO cyberos_app; ```

1. MUST expose endpoints: ``text POST /v1/cuo/chains (CDO submits skills_with_deps) GET /v1/cuo/chains/{id} (status + steps) ``

1. MUST emit 6 memory audit kinds per DEC-2344. PII per TASK-MEMORY-111: result_jsonb SHA256.

1. MUST thread trace_id from plan → step → composite → audit.

1. MUST NOT execute chain with cycle per DEC-2342.

1. MUST NOT mutate prior step row per DEC-2343 (REVOKE UPDATE except status cols).

§2 — Why this design

Why topo sort (DEC-2340)? Enforces depends_on order; prerequisites complete before dependents.

Why cycle detect (DEC-2342)? Cycles = infinite loops; must fail at plan time.

Why composite + sub-rows (DEC-2340)? Composite for chain-level summary; sub-rows for per-step debugging.

§3 — API contract

Sample chain plan:

POST /v1/cuo/chains
{
  "skills": [
    {"skill_id": "auth.user_lookup", "depends_on": []},
    {"skill_id": "calendar.list_events", "depends_on": ["auth.user_lookup"]},
    {"skill_id": "email.send", "depends_on": ["calendar.list_events"]}
  ]
}

Response:

{
  "chain_id": "uuid",
  "status": "completed",
  "steps": [
    {"step_order": 0, "skill_id": "auth.user_lookup", "status": "completed"},
    {"step_order": 1, "skill_id": "calendar.list_events", "status": "completed"},
    {"step_order": 2, "skill_id": "email.send", "status": "completed"}
  ]
}

§4 — Acceptance criteria

1. chain_status enum cardinality 5. 2. Topo sort correct order. 3. Cycle detection rejects. 4. Per-step sub-row. 5. Composite audit row. 6. 6 memory audit kinds emitted. 7. PII scrubbed (result SHA256). 8. RLS denies cross-tenant. 9. Trace_id preserved. 10. Append-only via REVOKE except status cols. 11. UNIQUE(chain_id, step_order). 12. Step failure → chain status updated. 13. Step status enum cardinality 5. 14. CDO-only chain submit. 15. Subsequent steps skipped on failure (no rollback yet — TASK-CUO-105). 16. Plan JSON validated. 17. Empty skills list → 400. 18. Cycle test catches A→B→A. 19. Multiple paths handled (diamond DAG). 20. Per-step skill_id from TASK-SKILL-001 registry.

§5 — Verification

#[tokio::test]
async fn topo_sort_correct() {
    let skills = vec![
        ("c", vec!["b"]),
        ("a", vec![]),
        ("b", vec!["a"]),
    ];
    let sorted = topological_sorter::sort(&skills).unwrap();
    assert_eq!(sorted, vec!["a", "b", "c"]);
}

#[tokio::test]
async fn cycle_detection_rejects() {
    let skills = vec![
        ("a", vec!["b"]),
        ("b", vec!["a"]),
    ];
    let r = topological_sorter::sort(&skills);
    assert!(r.is_err());
}

#[tokio::test]
async fn step_failure_updates_chain() {
    let ctx = TestContext::with_3_step_chain_step_2_fails().await;
    ctx.run_chain(ctx.chain_id).await;
    let c = ctx.fetch_chain(ctx.chain_id).await;
    assert_eq!(c.status, "failed");
    let steps = ctx.fetch_steps(ctx.chain_id).await;
    assert_eq!(steps[1].status, "failed");
    assert_eq!(steps[2].status, "skipped");
}

// 5.4..5.10

§7 — Dependencies

Upstream: TASK-CUO-101. Downstream: TASK-CUO-105 (rollback on failure). Cross-module: TASK-CUO-102 (checkpoint integration), TASK-SKILL-001 (skill registry), TASK-MEMORY-111 (PII).

§10 — Failure modes

§11 — Implementation notes

• §11.1 Topo sort via Kahn's algorithm; cycle detection via in-degree check.
• §11.2 Walker runs steps sequentially v1; parallel walks (independent branches) future enhancement.
• §11.3 memory audit body: chain_id, step_order, skill_id, status; result SHA256.
• §11.4 Step failure → no further steps; TASK-CUO-105 handles rollback in next task.
• §11.5 Plan JSONB stored verbatim for replay.

End of TASK-CUO-104 spec.