1  import type { BoardTask } from '@/types'
  2  
  3  interface DagResult {
  4    valid: boolean
  5    cycle?: string[]
  6  }
  7  
  8  /**
  9   * Validate that adding `proposedBlockedBy` to `taskId` would not create a cycle
 10   * in the task dependency graph. Uses DFS to check if `taskId` is reachable from
 11   * any of its proposed blockers (which would mean a cycle).
 12   */
 13  export function validateDag(
 14    tasks: Record<string, BoardTask>,
 15    taskId: string,
 16    proposedBlockedBy: string[],
 17  ): DagResult {
 18    // Build adjacency: task -> tasks it is blocked by (its dependencies)
 19    // We temporarily add the proposed edges: taskId is blocked by proposedBlockedBy
 20    // A cycle exists if we can reach taskId by following blockedBy edges from any
 21    // of the proposed blockers.
 22  
 23    // DFS from each proposed blocker, following existing blockedBy edges.
 24    // If we reach taskId, we have a cycle.
 25    for (const startId of proposedBlockedBy) {
 26      if (startId === taskId) {
 27        return { valid: false, cycle: [taskId, taskId] }
 28      }
 29  
 30      const visited = new Set<string>()
 31      const path: string[] = []
 32      const found = dfs(tasks, startId, taskId, visited, path)
 33      if (found) {
 34        // path contains the route from startId to taskId
 35        // The full cycle is: taskId -> startId -> ... -> taskId
 36        return { valid: false, cycle: [taskId, ...path] }
 37      }
 38    }
 39  
 40    return { valid: true }
 41  }
 42  
 43  /**
 44   * DFS through the blockedBy graph starting from `current`, looking for `target`.
 45   * Returns true if target is found, and populates `path` with the route.
 46   */
 47  function dfs(
 48    tasks: Record<string, BoardTask>,
 49    current: string,
 50    target: string,
 51    visited: Set<string>,
 52    path: string[],
 53  ): boolean {
 54    if (visited.has(current)) return false
 55    visited.add(current)
 56    path.push(current)
 57  
 58    const task = tasks[current]
 59    if (!task) {
 60      path.pop()
 61      return false
 62    }
 63  
 64    const blockers = Array.isArray(task.blockedBy) ? task.blockedBy : []
 65    for (const blockerId of blockers) {
 66      if (blockerId === target) {
 67        path.push(blockerId)
 68        return true
 69      }
 70      if (dfs(tasks, blockerId, target, visited, path)) {
 71        return true
 72      }
 73    }
 74  
 75    path.pop()
 76    return false
 77  }
 78  
 79  /**
 80   * After a task completes, find all tasks that were blocked by it and check
 81   * if all their blockers are now done. If so, auto-queue them.
 82   * Returns the IDs of tasks that were unblocked.
 83   */
 84  export function cascadeUnblock(
 85    tasks: Record<string, BoardTask>,
 86    completedTaskId: string,
 87  ): string[] {
 88    const completedTask = tasks[completedTaskId]
 89    if (!completedTask || completedTask.status !== 'completed') return []
 90  
 91    const unblocked: string[] = []
 92    const blockedIds = Array.isArray(completedTask.blocks) ? completedTask.blocks : []
 93  
 94    for (const blockedId of blockedIds) {
 95      const blocked = tasks[blockedId]
 96      if (!blocked) continue
 97      // Only auto-queue tasks that are in backlog (waiting on dependencies)
 98      if (blocked.status !== 'backlog') continue
 99  
100      const deps = Array.isArray(blocked.blockedBy) ? blocked.blockedBy : []
101      const allDone = deps.every((depId) => {
102        const dep = tasks[depId]
103        return dep?.status === 'completed'
104      })
105  
106      if (allDone) {
107        // Populate upstream results from completed blockers
108        blocked.upstreamResults = deps.map((depId) => {
109          const dep = tasks[depId]
110          return {
111            taskId: depId,
112            taskTitle: dep?.title || depId,
113            agentId: dep?.agentId || null,
114            resultPreview: dep?.result ? dep.result.slice(0, 800) : null,
115          }
116        })
117        blocked.status = 'queued'
118        blocked.queuedAt = Date.now()
119        blocked.updatedAt = Date.now()
120        unblocked.push(blockedId)
121      }
122    }
123  
124    return unblocked
125  }