sailfork / t3code-github / .repos/ alchemy-effect/ packages/ alchemy/ src/ Util/ scc.ts

/**
 * Compute the strongly-connected components of a directed graph.
 *
 * Components are emitted in Tarjan completion order — the reverse
 * topological order of the condensation, so a component appears before
 * every component that has an edge into it.
 *
 * Implementation is iterative Tarjan's algorithm to avoid blowing the JS
 * call stack on very wide graphs.
 */
export const stronglyConnectedComponents = (
  nodes: Iterable<string>,
  successors: (node: string) => Iterable<string>,
): string[][] => {
  const output: string[][] = [];

  let index = 0;
  const indexOf = new Map<string, number>();
  const lowlink = new Map<string, number>();
  const onStack = new Set<string>();
  const stack: string[] = [];

  type Frame = { node: string; children: string[]; childIdx: number };
  const callStack: Frame[] = [];

  const startNode = (node: string) => {
    indexOf.set(node, index);
    lowlink.set(node, index);
    index += 1;
    stack.push(node);
    onStack.add(node);
    callStack.push({ node, children: [...successors(node)], childIdx: 0 });
  };

  for (const root of nodes) {
    if (indexOf.has(root)) continue;
    startNode(root);

    while (callStack.length > 0) {
      const frame = callStack[callStack.length - 1];
      if (frame.childIdx < frame.children.length) {
        const child = frame.children[frame.childIdx];
        frame.childIdx += 1;
        if (!indexOf.has(child)) {
          startNode(child);
          continue;
        }
        if (onStack.has(child)) {
          lowlink.set(frame.node, Math.min(lowlink.get(frame.node)!, indexOf.get(child)!));
        }
        continue;
      }

      // All children processed: maybe close an SCC.
      if (lowlink.get(frame.node) === indexOf.get(frame.node)) {
        const scc: string[] = [];
        for (;;) {
          const w = stack.pop()!;
          onStack.delete(w);
          scc.push(w);
          if (w === frame.node) break;
        }
        output.push(scc);
      }

      // Pop frame and propagate lowlink up to the parent.
      callStack.pop();
      const parent = callStack[callStack.length - 1];
      if (parent) {
        const cur = lowlink.get(parent.node)!;
        const childLow = lowlink.get(frame.node)!;
        if (childLow < cur) lowlink.set(parent.node, childLow);
      }
    }
  }

  return output;
};

/**
 * Compute the set of graph nodes that participate in a dependency cycle.
 *
 * A node is considered "in a cycle" iff it sits in a strongly-connected
 * component (SCC) of size > 1, or has a self-edge (size-1 SCC that loops
 * back to itself).
 */
export const findCycleMembers = (edges: Record<string, readonly string[]>): Set<string> => {
  const cycleMembers = new Set<string>();
  for (const scc of stronglyConnectedComponents(Object.keys(edges), (node) => edges[node] ?? [])) {
    if (scc.length > 1) {
      for (const fqn of scc) cycleMembers.add(fqn);
    } else {
      // Size-1 SCC: only counts as a cycle if it has a self-edge.
      const only = scc[0];
      if ((edges[only] ?? []).includes(only)) {
        cycleMembers.add(only);
      }
    }
  }
  return cycleMembers;
};