1/**
2 * Compute the strongly-connected components of a directed graph.
3 *
4 * Components are emitted in Tarjan completion order — the reverse
5 * topological order of the condensation, so a component appears before
6 * every component that has an edge into it.
7 *
8 * Implementation is iterative Tarjan's algorithm to avoid blowing the JS
9 * call stack on very wide graphs.
10 */
11export const stronglyConnectedComponents = (
12 nodes: Iterable<string>,
13 successors: (node: string) => Iterable<string>,
14): string[][] => {
15 const output: string[][] = [];
16
17 let index = 0;
18 const indexOf = new Map<string, number>();
19 const lowlink = new Map<string, number>();
20 const onStack = new Set<string>();
21 const stack: string[] = [];
22
23 type Frame = { node: string; children: string[]; childIdx: number };
24 const callStack: Frame[] = [];
25
26 const startNode = (node: string) => {
27 indexOf.set(node, index);
28 lowlink.set(node, index);
29 index += 1;
30 stack.push(node);
31 onStack.add(node);
32 callStack.push({ node, children: [...successors(node)], childIdx: 0 });
33 };
34
35 for (const root of nodes) {
36 if (indexOf.has(root)) continue;
37 startNode(root);
38
39 while (callStack.length > 0) {
40 const frame = callStack[callStack.length - 1];
41 if (frame.childIdx < frame.children.length) {
42 const child = frame.children[frame.childIdx];
43 frame.childIdx += 1;
44 if (!indexOf.has(child)) {
45 startNode(child);
46 continue;
47 }
48 if (onStack.has(child)) {
49 lowlink.set(
50 frame.node,
51 Math.min(lowlink.get(frame.node)!, indexOf.get(child)!),
52 );
53 }
54 continue;
55 }
56
57 // All children processed: maybe close an SCC.
58 if (lowlink.get(frame.node) === indexOf.get(frame.node)) {
59 const scc: string[] = [];
60 for (;;) {
61 const w = stack.pop()!;
62 onStack.delete(w);
63 scc.push(w);
64 if (w === frame.node) break;
65 }
66 output.push(scc);
67 }
68
69 // Pop frame and propagate lowlink up to the parent.
70 callStack.pop();
71 const parent = callStack[callStack.length - 1];
72 if (parent) {
73 const cur = lowlink.get(parent.node)!;
74 const childLow = lowlink.get(frame.node)!;
75 if (childLow < cur) lowlink.set(parent.node, childLow);
76 }
77 }
78 }
79
80 return output;
81};
82
83/**
84 * Compute the set of graph nodes that participate in a dependency cycle.
85 *
86 * A node is considered "in a cycle" iff it sits in a strongly-connected
87 * component (SCC) of size > 1, or has a self-edge (size-1 SCC that loops
88 * back to itself).
89 */
90export const findCycleMembers = (
91 edges: Record<string, readonly string[]>,
92): Set<string> => {
93 const cycleMembers = new Set<string>();
94 for (const scc of stronglyConnectedComponents(
95 Object.keys(edges),
96 (node) => edges[node] ?? [],
97 )) {
98 if (scc.length > 1) {
99 for (const fqn of scc) cycleMembers.add(fqn);
100 } else {
101 // Size-1 SCC: only counts as a cycle if it has a self-edge.
102 const only = scc[0];
103 if ((edges[only] ?? []).includes(only)) {
104 cycleMembers.add(only);
105 }
106 }
107 }
108 return cycleMembers;
109};