numolus/app/frontend/engine/graph.ts

/**
 * Dependency graph over *all* sheets.
 *
 * Nodes are cell keys (see `keyOf` in ./types). An edge  P -> C  means
 * "cell C reads cell P" (P is a precedent of C, C is a dependent of P).
 *
 * The graph offers two things the recalculation driver needs:
 *   1. `affected(dirty)` -- every cell that must be revisited after `dirty`
 *      changed (the dirty cells plus their transitive dependents).
 *   2. `topoOrder(nodes)` -- a safe evaluation order for a set of nodes, plus
 *      the subset that sits on a dependency cycle (`#CIRC`).
 *
 * Circular references -- including cross-sheet ones -- are found by an iterative
 * DFS with white/grey/black colouring. When a back-edge to a grey node is seen,
 * every node currently on the DFS stack from that node onwards is flagged
 * circular. Flagged nodes are dropped from the returned order; the driver writes
 * `#CIRC` into them directly and their dependents pick that up through normal
 * error propagation.
 */

export class DependencyGraph {
  /** precedents: key -> set of cells it reads */
  private readonly precedents = new Map<string, Set<string>>();
  /** dependents: key -> set of cells that read it */
  private readonly dependents = new Map<string, Set<string>>();

  /** Replace the precedent set of `cell` (called after (re)parsing a formula). */
  setPrecedents(cell: string, precedents: Iterable<string>): void {
    // unlink old edges
    const old = this.precedents.get(cell);
    if (old) {
      for (const p of old) this.dependents.get(p)?.delete(cell);
    }
    // Keep a self-reference if present: `=A1` inside A1 must surface as #CIRC.
    const next = new Set(precedents);
    this.precedents.set(cell, next);
    for (const p of next) {
      let d = this.dependents.get(p);
      if (!d) this.dependents.set(p, (d = new Set()));
      d.add(cell);
    }
  }

  /** Forget a cell entirely (e.g. it became a literal or was cleared). */
  clear(cell: string): void {
    const old = this.precedents.get(cell);
    if (old) for (const p of old) this.dependents.get(p)?.delete(cell);
    this.precedents.delete(cell);
    // keep `dependents.get(cell)` -- other cells may still point here (=> #REF/0),
    // that entry is harmless and gets cleaned as those cells are re-parsed.
  }

  /** Drop every edge (used on structural rebuilds). */
  reset(): void {
    this.precedents.clear();
    this.dependents.clear();
  }

  getPrecedents(cell: string): Set<string> {
    return this.precedents.get(cell) ?? new Set();
  }
  getDependents(cell: string): Set<string> {
    return this.dependents.get(cell) ?? new Set();
  }

  /** Dirty cells + all their transitive dependents. */
  affected(dirty: Iterable<string>): Set<string> {
    const seen = new Set<string>();
    const stack = [...dirty];
    while (stack.length) {
      const k = stack.pop()!;
      if (seen.has(k)) continue;
      seen.add(k);
      const deps = this.dependents.get(k);
      if (deps) for (const d of deps) if (!seen.has(d)) stack.push(d);
    }
    return seen;
  }

  /**
   * Topologically sort `nodes` using precedent edges that stay inside `nodes`.
   * Returns the evaluation order (precedents first) and the set of nodes that
   * lie on a cycle.
   */
  topoOrder(nodes: Set<string>): { order: string[]; circular: Set<string> } {
    const WHITE = 0;
    const GREY = 1;
    const BLACK = 2;
    const color = new Map<string, number>();
    const order: string[] = [];
    const circular = new Set<string>();
    for (const n of nodes) color.set(n, WHITE);

    for (const root of nodes) {
      if (color.get(root) !== WHITE) continue;

      // iterative DFS; frame = { node, iterator over its in-scope precedents }
      const stack: Array<{ node: string; iter: Iterator<string> }> = [];
      const pathIndex = new Map<string, number>(); // node -> position on stack

      const push = (node: string) => {
        color.set(node, GREY);
        pathIndex.set(node, stack.length);
        const precs = [...this.getPrecedents(node)].filter((p) => nodes.has(p));
        stack.push({ node, iter: precs[Symbol.iterator]() });
      };
      push(root);

      while (stack.length) {
        const frame = stack[stack.length - 1];
        const step = frame.iter.next();
        if (step.done) {
          color.set(frame.node, BLACK);
          pathIndex.delete(frame.node);
          order.push(frame.node);
          stack.pop();
          continue;
        }
        const p = step.value;
        const c = color.get(p);
        if (c === WHITE) {
          push(p);
        } else if (c === GREY) {
          // back-edge -> cycle. Flag everything from p to the current frame.
          const from = pathIndex.get(p)!;
          for (let k = from; k < stack.length; k++) circular.add(stack[k].node);
        }
        // BLACK -> already settled, ignore
      }
    }

    // A node that depends on a circular node is not itself circular, but it must
    // be evaluated *after* the driver writes #CIRC. Keeping it in `order` is
    // fine; drop only the truly circular nodes.
    return { order: order.filter((n) => !circular.has(n)), circular };
  }
}