[Enhancement] Upgrade dependency tracking with junction table and validation

[tomsmith8]

Problem

Task dependencies are currently stored as a JSON array (dependsOnTaskIds: String[]) with shallow validation, creating several scalability and correctness issues:

Current Limitations

1. No transitive circular dependency detection

   • Only checks self-reference (line 364 in tickets.ts): if (data.dependsOnTaskIds.includes(taskId))
   • Only checks direct circular (A→B, B→A) (lines 394-406)
   • Doesn't detect transitive circular (A→B→C→A) which creates deadlocks

2. Poor query performance

   • Finding "all tasks that depend on X" requires full table scan
   • WHERE dependsOnTaskIds @> ARRAY[$1]::text[] doesn't use indexes
   • PostgreSQL JSON array operators are fast but not as fast as proper foreign keys

3. No dependency graph analysis

   • Can't compute critical path
   • Can't find all transitively blocked tasks
   • Can't visualize dependency depth or breadth

Current Implementation

Database: /prisma/schema.prisma

model Task {
  dependsOnTaskIds String[]  // JSON array, no indexes
}

Validation: /src/services/roadmap/tickets.ts (lines 358-410)

// Simple checks only
if (data.dependsOnTaskIds.includes(taskId)) {
  throw new Error("A task cannot depend on itself");
}

// Direct circular only
const existingDependents = await db.task.findMany({
  where: {
    id: { in: data.dependsOnTaskIds },
    dependsOnTaskIds: { has: taskId },
  },
});
if (existingDependents.length > 0) {
  throw new Error("Circular dependency detected");
}

Proposed Solution

Phase 1: Add junction table (non-breaking)

Database Migration:

CREATE TABLE task_dependencies (
  task_id TEXT NOT NULL REFERENCES tasks(id) ON DELETE CASCADE,
  depends_on_task_id TEXT NOT NULL REFERENCES tasks(id) ON DELETE CASCADE,
  created_at TIMESTAMP NOT NULL DEFAULT NOW(),
  PRIMARY KEY (task_id, depends_on_task_id)
);

CREATE INDEX idx_task_deps_task ON task_dependencies(task_id);
CREATE INDEX idx_task_deps_depends_on ON task_dependencies(depends_on_task_id);

Prisma Schema:

model Task {
  id               String   @id @default(cuid())
  dependsOnTaskIds String[] // Keep for backwards compat
  
  // New: explicit relations via junction table
  dependencies     TaskDependency[] @relation("TaskDependencies")
  dependents       TaskDependency[] @relation("DependentTasks")
}

model TaskDependency {
  taskId           String
  dependsOnTaskId  String
  createdAt        DateTime @default(now())
  
  task             Task @relation("TaskDependencies", fields: [taskId], references: [id], onDelete: Cascade)
  dependsOnTask    Task @relation("DependentTasks", fields: [dependsOnTaskId], references: [id], onDelete: Cascade)
  
  @@id([taskId, dependsOnTaskId])
  @@index([taskId])
  @@index([dependsOnTaskId])
}

Write to both: Keep array field populated for backwards compatibility, use junction table for queries.

Phase 2: Add circular dependency validation

// New file: /src/services/roadmap/dependency-validation.ts

async function detectCircularDependency(
  taskId: string,
  dependsOnTaskIds: string[]
): Promise<string[]> {
  // DFS to find cycles
  const visited = new Set<string>();
  const recursionStack = new Set<string>();
  const cycle: string[] = [];

  async function dfs(currentTaskId: string, path: string[]): Promise<boolean> {
    if (recursionStack.has(currentTaskId)) {
      // Found cycle
      const cycleStart = path.indexOf(currentTaskId);
      return path.slice(cycleStart).concat(currentTaskId);
    }
    
    if (visited.has(currentTaskId)) return false;
    
    visited.add(currentTaskId);
    recursionStack.add(currentTaskId);
    path.push(currentTaskId);

    // Get dependencies via junction table (fast)
    const deps = await db.taskDependency.findMany({
      where: { taskId: currentTaskId },
      select: { dependsOnTaskId: true },
    });

    for (const dep of deps) {
      const cycleFound = await dfs(dep.dependsOnTaskId, [...path]);
      if (cycleFound) return cycleFound;
    }

    recursionStack.delete(currentTaskId);
    return false;
  }

  for (const depId of dependsOnTaskIds) {
    const cycleFound = await dfs(depId, [taskId]);
    if (cycleFound) return cycleFound;
  }

  return [];
}

Phase 3: Enable graph queries

// Get all transitively blocked tasks
async function getBlockedTasks(taskId: string): Promise<string[]> {
  const result = await db.$queryRaw`
    WITH RECURSIVE blocked AS (
      SELECT depends_on_task_id AS task_id
      FROM task_dependencies
      WHERE task_id = ${taskId}
      
      UNION
      
      SELECT td.depends_on_task_id
      FROM task_dependencies td
      INNER JOIN blocked b ON td.task_id = b.task_id
    )
    SELECT task_id FROM blocked;
  `;
  return result.map(r => r.task_id);
}

// Get critical path
async function getCriticalPath(featureId: string): Promise<Task[]> {
  // Topological sort + longest path algorithm
  // Returns tasks in order of dependency depth
}

Success Criteria

• Junction table created and indexed
• Circular dependency detection prevents A→B→C→A cycles
• Query "all tasks depending on X" completes in <100ms
• Critical path computation implemented
• All existing functionality works (backwards compatible)

Code References

• /src/services/roadmap/tickets.ts - updateTicket dependency validation (lines 358-410)
• /prisma/schema.prisma - Task model
• /src/components/features/DependencyGraph/ - Graph visualization component

Effort Estimate

2-3 weeks

• Junction table migration: 2-3 days
• Circular dependency validation: 3-4 days
• Graph query functions: 3-4 days
• Testing and optimization: 3-4 days

Priority

Medium - Not blocking current scale, but needed before power users create complex dependency graphs.