Yeachan-Heo/oh-my-codex · error · Error

Team DAG contains a cycle

Error message

Team DAG contains a cycle

What it means

topologicalSort implements Kahn's algorithm over the team dependency DAG; if the number of emitted nodes is less than the total node count, at least one node never reached indegree 0, which only happens when the dependency graph has a cycle. The error means the decomposition (depends_on edges) is not a valid DAG.

Source

Thrown at src/team/repo-aware-decomposition.ts:136

  const outgoing = new Map<string, string[]>();
  for (const node of nodes) {
    for (const dep of node.depends_on ?? []) {
      indegree.set(node.id, (indegree.get(node.id) ?? 0) + 1);
      outgoing.set(dep, [...(outgoing.get(dep) ?? []), node.id]);
    }
  }
  const ready = nodes.filter((node) => (indegree.get(node.id) ?? 0) === 0);
  const sorted: TeamDagNode[] = [];
  while (ready.length > 0) {
    ready.sort((a, b) => (inputIndex.get(a.id) ?? 0) - (inputIndex.get(b.id) ?? 0));
    const node = ready.shift()!;
    sorted.push(node);
    for (const next of outgoing.get(node.id) ?? []) {
      indegree.set(next, (indegree.get(next) ?? 0) - 1);
      if ((indegree.get(next) ?? 0) === 0) ready.push(byId.get(next)!);
    }
  }
  if (sorted.length !== nodes.length) throw new Error('Team DAG contains a cycle');
  return sorted;
}

function firstReadyLaneCount(nodes: TeamDagNode[]): number {
  const ready = nodes.filter((node) => (node.depends_on?.length ?? 0) === 0);
  if (ready.length === 0) return 1;
  const conflictGroups = new Set<string>();
  let noFileCount = 0;
  for (const node of ready) {
    const files = node.filePaths ?? [];
    if (files.length === 0) {
      noFileCount += 1;
      continue;
    }
    conflictGroups.add(files.map(normalizePath).sort().join('|'));
  }
  return Math.max(1, conflictGroups.size + noFileCount);
}

View on GitHub (pinned to 3ad79a8a6f)

Solutions

1. Run a cycle check (DFS or Kahn) on depends_on before calling topologicalSort and report the cycle path
2. Fix or remove the circular depends_on entries in the decomposition
3. If decompositions are machine-generated, add a post-generation validation step that rejects cycles

Example fix

// before
const sorted = topologicalSort(nodes);
// after
function findCycle(nodes) { /* DFS with rec-stack, returns cycle ids or null */ }
const cycle = findCycle(nodes);
if (cycle) throw new Error(`cyclic dependency: ${cycle.join(' -> ')}`);
const sorted = topologicalSort(nodes);

function assertAcyclic(nodes: TeamDagNode[]): void {
  const state = new Map<string, 0|1|2>();
  const dfs = (id: string, stack: string[]) => {
    const s = state.get(id); if (s === 2) return; if (s === 1) throw new Error('cycle: ' + [...stack, id].join('->'));
    state.set(id, 1);
    for (const n of nodes.find(x => x.id === id)?.depends_on ?? []) dfs(n, [...stack, id]);
    state.set(id, 2);
  };
  nodes.forEach(n => dfs(n.id, []));
}

try { topologicalSort(nodes); } catch (e) { if (e instanceof Error && e.message === 'Team DAG contains a cycle') { /* surface offending edges to user */ } throw e; }

When it happens

Trigger: Passing TeamDagNode[] where A depends_on B, B depends_on C, and C depends_on A (direct cycle), or a self-dependency node.depends_on containing its own id.

Common situations: LLM-generated task decompositions that create mutually-dependent tasks; user-authored DAG specs with circular references; duplicate ids causing edges that resolve back onto themselves.

Related errors

• blocked_dependency:${(claim.dependencies ?? []).join(',')}

AI-assisted analysis of Yeachan-Heo/oh-my-codex@3ad79a8a6f (2026-08-27). Data as JSON: /api/errors/27f890009129ca15. Report an issue: GitHub.