syntaxai/tdd.md · main · src / b32_graph_depth_polyglot.ts

// b32 — logic: §5 graphDepth metric for polyglot dependency graphs.
// Pure function, no I/O. Given a directed graph as nodes + edges,
// returns the longest path length using memoised DFS. Cycles are
// bounded (back-edge target treated as terminal of depth 1) so the
// function always terminates with a finite number, mirroring
// b32_sama_v2_metrics.ts's computeGraphDepth.
//
// Module-granularity note (per /sama/v2 §5 operational and the v2.1
// dialects at /sama/v2#6a-v21-dialects-provisional): the TS metric
// works at FILE level because in TS one module ≈ one file. The
// natural cross-language analog is per-language: Go's unit is the
// PACKAGE DIRECTORY (multiple .go files in one directory all live in
// the same package and share imports); Rust's unit is the CRATE
// (Cargo workspace member). The depth measured here is the longest
// chain of dependency relationships at each language's natural unit.
// This semantic is documented in the adapter source comments
// (c14_go_graph_depth.ts, c14_rust_graph_depth.ts) and surfaced in
// the audit page hand-traces.
//
// Consumed by the two adapters which feed it a pre-built {nodes,
// edges} pair, keeping this module pure and unit-testable.

export interface Graph {
  // List of node identifiers (deduplicated by the adapter before
  // calling). For Go: package-directory repo-relative paths. For
  // Rust: workspace-crate names. The helper does not care which.
  nodes: ReadonlyArray<string>;
  // Directed edges as [from, to]. The helper is forgiving: edges
  // referencing nodes not in `nodes` are silently ignored (they
  // can't extend a path through nodes the caller did not declare).
  edges: ReadonlyArray<readonly [string, string]>;
}

export interface GraphDepthResult {
  nodeCount: number;
  edgeCount: number;
  depth: number;
}

export const computeGraphDepth = (graph: Graph): GraphDepthResult => {
  const nodeSet = new Set(graph.nodes);
  if (nodeSet.size === 0) {
    return { nodeCount: 0, edgeCount: 0, depth: 0 };
  }

  // Adjacency (only edges that connect declared nodes).
  const adj = new Map<string, string[]>();
  for (const n of nodeSet) adj.set(n, []);
  let edgeCount = 0;
  for (const [from, to] of graph.edges) {
    if (!nodeSet.has(from) || !nodeSet.has(to)) continue;
    adj.get(from)!.push(to);
    edgeCount++;
  }

  // Memoised DFS for longest path. Cycle handling matches
  // b32_sama_v2_metrics.ts: a re-entered node returns depth 1 so the
  // recursion terminates with a finite value (the Law check would
  // flag a cycle separately; the metric still has to emit a number).
  const memo = new Map<string, number>();
  const visiting = new Set<string>();

  const depthFrom = (node: string): number => {
    const cached = memo.get(node);
    if (cached !== undefined) return cached;
    if (visiting.has(node)) return 1;
    visiting.add(node);
    let best = 1;
    for (const next of adj.get(node) ?? []) {
      const d = depthFrom(next) + 1;
      if (d > best) best = d;
    }
    visiting.delete(node);
    memo.set(node, best);
    return best;
  };

  let max = 0;
  for (const n of nodeSet) {
    const d = depthFrom(n);
    if (d > max) max = d;
  }

  return {
    nodeCount: nodeSet.size,
    edgeCount,
    depth: max,
  };
};