All docs

Task DAG — cycle detection, readiness, next-actionable queue

Task DAG — cycle detection, readiness, next-actionable queue

Modules:

  • packages/core/src/dag/cycle.ts — pure DFS, no side effects.
  • packages/core/src/dag/dependencies.ts — addDependency/removeDependency/recomputeReadiness/recomputeDownstream.
  • packages/core/src/dag/actionable.ts — getNextActionable.

Edge orientation

task_dependencies row (task_id, depends_on_task_id, kind) means `task_id` depends on `depends_on_task_id`.

We never use ambiguous "X→Y" notation in code or commit messages; always say "X depends on Y" or "Y is a prerequisite of X".

Cycle detection

Adding "X depends on Y" closes a cycle iff Y already transitively depends on X. The check is:

  1. Load every edge in the plan (cheap — plans are small, single-digit to low-hundreds).
  2. Build adjacency forward[task] = task.depends_on_ids.
  3. DFS from Y looking for X; if reached, the path is the cycle.

This is the single place that decides whether an edge is safe to insert. task_dependencies_no_self (DB CHECK) catches the self-loop case as a safety net.

Plan size limit: we currently expect ≤ 1000 tasks per plan; at that scale in-memory DFS finishes in a millisecond. If a use case ever pushes past that, the same API can be backed by a recursive CTE without changing callers.

Readiness rules

dep kindopen whencounts as open for readiness?
hardprerequisite ∉ {done, cancelled}yes — blocks the dependent
soft(always treated as closed)no — informational only

A task is ready ⇔ it has zero open hard deps and its current state is blocked. A task is blocked ⇔ it has at least one open hard dep and its current state is ready.

recomputeReadiness(taskIds) is idempotent: a task already in the right state is skipped (no event, no audit). It only flips blocked ↔ ready; tasks in {claimed, in_progress, needs_review, done, cancelled} are left alone, because those states have stronger invariants that downstream actions (heartbeat, verifier, review resolution) preserve.

Automatic downstream propagation

The task repo wires recomputeDownstream(completedTaskId) into:

  • completeTask — but only when the outcome is done (kind=none auto-pass).

needs_review outcomes wait for resolveReview('approve').

  • cancelTask — a cancelled prerequisite no longer blocks.
  • resolveReview('approve') — the human approval is what finally closes the dep.

No callers need to remember to recompute manually; the propagation is invariant.

getNextActionable

Read-only. Returns ready tasks for an org, sorted by (priority ASC, created_at ASC), with optional filters:

filterbehaviour
planIdrestrict to a single plan
repositoryIdrestrict to tasks linked to that repo
priorityLteinclusive upper bound (smaller number = higher prio)
priorityGteinclusive lower bound
limitclamped to [1, 100], default 20

Excludes:

  • Plans whose status != 'active' (drafts, proposed, archived).
  • Soft-deleted tasks (deleted_at IS NOT NULL).
  • Tasks not in ready (claimed/in_progress/needs_review/done/cancelled).

When includeReferences: true, the function does a single follow-up query to attach task_knowledge rows with kind='references' per task — keeps the renderer out of an N+1 trap. Hybrid semantic pre-fetch (title + description vector search) is layered on top in task 20; this module only does the structural part.

What this module does NOT do

  • MCP wrapping (get_next_actionable JSON-RPC tool) — task 27.
  • Knowledge semantic search — task 20.
  • Cycle detection for plan_template_edges — handled by the same wouldCycle shape

once we instantiate templates (task 22 brings template DAGs into the runtime model).