* Check for circular dependencies between blocks.
(dag: BlockDependencyDag, blockMap: Map<string, BlockInfo>)
| 323 | * Check for circular dependencies between blocks. |
| 324 | */ |
| 325 | function checkCircularDependencies(dag: BlockDependencyDag, blockMap: Map<string, BlockInfo>): LintIssue[] { |
| 326 | const issues: LintIssue[] = [] |
| 327 | |
| 328 | // Build adjacency list |
| 329 | const graph = new Map<string, Set<string>>() |
| 330 | for (const edge of dag.edges) { |
| 331 | const deps = graph.get(edge.from) ?? new Set() |
| 332 | deps.add(edge.to) |
| 333 | graph.set(edge.from, deps) |
| 334 | } |
| 335 | |
| 336 | // Find cycles using DFS |
| 337 | const visited = new Set<string>() |
| 338 | const recursionStack = new Set<string>() |
| 339 | const cycleBlocks = new Set<string>() |
| 340 | |
| 341 | function dfs(nodeId: string, path: string[]): void { |
| 342 | visited.add(nodeId) |
| 343 | recursionStack.add(nodeId) |
| 344 | |
| 345 | const neighbors = graph.get(nodeId) ?? new Set() |
| 346 | for (const neighbor of neighbors) { |
| 347 | if (!visited.has(neighbor)) { |
| 348 | dfs(neighbor, [...path, nodeId]) |
| 349 | } else if (recursionStack.has(neighbor)) { |
| 350 | // Found a cycle - mark all nodes in the cycle |
| 351 | const cycleStart = path.indexOf(neighbor) |
| 352 | if (cycleStart !== -1) { |
| 353 | for (let i = cycleStart; i < path.length; i++) { |
| 354 | cycleBlocks.add(path[i]) |
| 355 | } |
| 356 | } |
| 357 | cycleBlocks.add(neighbor) |
| 358 | cycleBlocks.add(nodeId) |
| 359 | } |
| 360 | } |
| 361 | |
| 362 | recursionStack.delete(nodeId) |
| 363 | } |
| 364 | |
| 365 | for (const node of dag.nodes) { |
| 366 | if (!visited.has(node.id)) { |
| 367 | dfs(node.id, []) |
| 368 | } |
| 369 | } |
| 370 | |
| 371 | // Report cycle issues |
| 372 | for (const blockId of cycleBlocks) { |
| 373 | const info = blockMap.get(blockId) |
| 374 | if (!info) continue |
| 375 | |
| 376 | issues.push({ |
| 377 | severity: 'error', |
| 378 | code: 'circular-dependency', |
| 379 | message: 'Block is part of a circular dependency', |
| 380 | blockId, |
| 381 | blockLabel: info.label, |
| 382 | notebookName: info.notebookName, |