callstack__agent-device/scripts/depgraph/model.ts

// Dependency-graph analysis model — pure functions over the layering gate's edge model.
//
// The graph is deliberately derived from `scripts/layering/model.ts` rather than a
// third-party extractor: the gate's file set (production `src/**/*.ts`, tests excluded),
// zone partition, edge kinds (value/type-only/dynamic), and cycle definition are already
// the repo's source of truth. A second extractor with its own resolution rules would
// visualize a graph the gate does not enforce.

import {
  backEdgePair,
  classifyZone,
  findValueImportCycles,
  targetDagZone,
  typeInversionPair,
  type ResolvedImportEdge,
} from '../layering/model.ts';

export type EdgeKind = 'value' | 'type' | 'dynamic';

export type GraphEdge = {
  from: string;
  to: string;
  kind: EdgeKind;
  line: number;
  /** Set when this edge is a ranked-spine back-edge (`R5`), as `from-zone -> to-zone`. */
  backEdge: string | null;
  /** Set when this edge is a type-only spine inversion (`R6`), as `from-zone -> to-zone`. */
  typeInversion: string | null;
  /** True when the same pair is also reachable through a longer path of the same weight class. */
  redundant: boolean;
};

export type GraphNode = {
  id: string;
  zone: string;
  /** First two path segments — a finer cluster than the zone, used for layout gravity. */
  loc: number;
  fanIn: number;
  fanOut: number;
  /** Index into `GraphData.cycles`, or -1. */
  cycle: number;
};

export type ZoneEdge = {
  from: string;
  to: string;
  count: number;
  valueCount: number;
  backEdge: boolean;
};

export type GraphCycle = {
  path: string[];
  /** `value` cycles are gate-rejected (R4); the others are gate-invisible by design. */
  kind: EdgeKind;
};

export type GraphData = {
  nodes: GraphNode[];
  edges: GraphEdge[];
  zones: { id: string; classification: string; files: number; loc: number }[];
  zoneEdges: ZoneEdge[];
  cycles: GraphCycle[];
};


function countLines(source: string): number {
  let lines = 1;
  for (let index = 0; index < source.length; index++) {
    if (source[index] === '\n') lines++;
  }
  return lines;
}

function edgeKind(edge: ResolvedImportEdge): EdgeKind {
  if (edge.dynamic) return 'dynamic';
  if (edge.typeOnly) return 'type';
  return 'value';
}

/**
 * Deduplicate parsed import edges down to one edge per (from, to) pair, keeping the
 * strongest kind. A file that imports both a type and a value from the same module has one
 * dependency on it, and the value import is what constrains layering and cold-start.
 */
export function collapseEdges(edges: readonly ResolvedImportEdge[]): GraphEdge[] {
  const strength: Record<EdgeKind, number> = { type: 0, dynamic: 1, value: 2 };
  const byPair = new Map<string, GraphEdge>();
  for (const edge of edges) {
    if (edge.file === edge.target) continue;
    const key = `${edge.file}${edge.target}`;
    const kind = edgeKind(edge);
    const existing = byPair.get(key);
    if (existing && strength[existing.kind] >= strength[kind]) continue;
    byPair.set(key, {
      from: edge.file,
      to: edge.target,
      kind,
      line: edge.line,
      backEdge: backEdgePair(edge),
      typeInversion: typeInversionPair(edge),
      redundant: false,
    });
  }
  return [...byPair.values()].sort(
    (left, right) => left.from.localeCompare(right.from) || left.to.localeCompare(right.to),
  );
}

/**
 * Value-edge adjacency. Both the redundancy pass and the level computation walk the same
 * subgraph — the one R4 guarantees is a DAG — so they share its construction rather than each
 * rebuilding it.
 */
function valueSuccessors(edges: readonly GraphEdge[]): Map<string, string[]> {
  const successors = new Map<string, string[]>();
  for (const edge of edges) {
    if (edge.kind !== 'value') continue;
    const list = successors.get(edge.from) ?? [];
    list.push(edge.to);
    successors.set(edge.from, list);
  }
  return successors;
}

/**
 * Mark edges removable without changing reachability: `a -> b` is redundant when `b` is
 * still reachable from `a` through a path of length >= 2. These are the "you already
 * depend on this transitively" edges — the cheap simplification candidates.
 *
 * Reachability is computed over value edges only, because a type-only or dynamic edge is
 * not interchangeable with a static value dependency.
 */
export function markRedundantEdges(edges: GraphEdge[]): void {
  const successors = valueSuccessors(edges);

  for (const edge of edges) {
    if (edge.kind !== 'value') continue;
    const seen = new Set<string>([edge.from]);
    // Seed with the one-hop neighbours other than `to`, so the search only ever finds
    // `to` at distance >= 2.
    const queue = (successors.get(edge.from) ?? []).filter((next) => next !== edge.to);
    for (const next of queue) seen.add(next);
    let index = 0;
    while (index < queue.length) {
      const current = queue[index++]!;
      for (const next of successors.get(current) ?? []) {
        if (next === edge.to) {
          edge.redundant = true;
          index = queue.length;
          break;
        }
        if (seen.has(next)) continue;
        seen.add(next);
        queue.push(next);
      }
    }
  }
}

/**
 * Cycles over an edge subset that includes weaker edge kinds. `findValueImportCycles`
 * covers the gate's R4 scope (static value edges); passing type-only and dynamic edges
 * through the same detector surfaces the cycles the gate deliberately does not reject —
 * still design signal, because a type-only cycle means two modules co-define one contract.
 */
export function collectCycles(edges: readonly ResolvedImportEdge[]): GraphCycle[] {
  const asValue = (subset: readonly ResolvedImportEdge[]): ResolvedImportEdge[] =>
    subset.map((edge) => ({ ...edge, dynamic: false, typeOnly: false }));

  const valuePaths = findValueImportCycles(edges);
  const valueKeys = new Set(valuePaths.map(cycleKey));
  const cycles: GraphCycle[] = valuePaths.map((path) => ({ path, kind: 'value' }));

  const staticEdges = edges.filter((edge) => !edge.dynamic);
  for (const path of findValueImportCycles(asValue(staticEdges))) {
    if (valueKeys.has(cycleKey(path))) continue;
    valueKeys.add(cycleKey(path));
    cycles.push({ path, kind: 'type' });
  }

  for (const path of findValueImportCycles(asValue(edges))) {
    if (valueKeys.has(cycleKey(path))) continue;
    valueKeys.add(cycleKey(path));
    cycles.push({ path, kind: 'dynamic' });
  }

  return cycles;
}

/** Rotation-independent identity for a cycle path, so the same loop is not reported twice. */
function cycleKey(path: readonly string[]): string {
  const members = [...new Set(path)].sort();
  return members.join('');
}

export function buildGraph(
  sources: ReadonlyMap<string, string>,
  edges: readonly ResolvedImportEdge[],
): GraphData {
  const collapsed = collapseEdges(edges);
  markRedundantEdges(collapsed);
  const cycles = collectCycles(edges);

  const cycleByFile = new Map<string, number>();
  for (let index = 0; index < cycles.length; index++) {
    for (const file of cycles[index]!.path) {
      if (!cycleByFile.has(file)) cycleByFile.set(file, index);
    }
  }

  const nodes = new Map<string, GraphNode>();
  for (const [file, source] of sources) {
    nodes.set(file, {
      id: file,
      zone: targetDagZone(file),
      loc: countLines(source),
      fanIn: 0,
      fanOut: 0,
      cycle: cycleByFile.get(file) ?? -1,
    });
  }

  for (const edge of collapsed) {
    const from = nodes.get(edge.from);
    const to = nodes.get(edge.to);
    if (from) from.fanOut++;
    if (to) to.fanIn++;
  }

  const zoneEdges = new Map<string, ZoneEdge>();
  for (const edge of collapsed) {
    const from = nodes.get(edge.from)?.zone;
    const to = nodes.get(edge.to)?.zone;
    if (!from || !to || from === to) continue;
    const key = `${from}${to}`;
    const existing = zoneEdges.get(key) ?? {
      from,
      to,
      count: 0,
      valueCount: 0,
      backEdge: false,
    };
    existing.count++;
    if (edge.kind === 'value') existing.valueCount++;
    if (edge.backEdge) existing.backEdge = true;
    zoneEdges.set(key, existing);
  }

  const zoneStats = new Map<string, { files: number; loc: number }>();
  for (const node of nodes.values()) {
    const stats = zoneStats.get(node.zone) ?? { files: 0, loc: 0 };
    stats.files++;
    stats.loc += node.loc;
    zoneStats.set(node.zone, stats);
  }

  return {
    nodes: [...nodes.values()].sort((left, right) => left.id.localeCompare(right.id)),
    edges: collapsed,
    zones: [...zoneStats]
      .map(([id, stats]) => ({
        id,
        classification: classifyZone(id),
        files: stats.files,
        loc: stats.loc,
      }))
      .sort((left, right) => right.loc - left.loc),
    zoneEdges: [...zoneEdges.values()].sort(
      (left, right) =>
        right.count - left.count ||
        left.from.localeCompare(right.from) ||
        left.to.localeCompare(right.to),
    ),
    cycles,
  };
}

/**
 * Longest distance from each node to a sink over value edges. The layering gate rejects
 * production value-import cycles (R4), so that subgraph is a DAG and the height is
 * well-defined; the `visiting` guard only exists so a future cycle degrades instead of
 * overflowing the stack.
 */
export function computeLevels(
  nodes: readonly GraphNode[],
  edges: readonly GraphEdge[],
): Map<string, number> {
  const successors = valueSuccessors(edges);

  const levels = new Map<string, number>();
  const visiting = new Set<string>();

  const height = (id: string): number => {
    const cached = levels.get(id);
    if (cached !== undefined) return cached;
    if (visiting.has(id)) return 0;
    visiting.add(id);
    let best = 0;
    for (const next of successors.get(id) ?? []) {
      best = Math.max(best, height(next) + 1);
    }
    visiting.delete(id);
    levels.set(id, best);
    return best;
  };

  for (const node of nodes) height(node.id);
  return levels;
}