callstack__agent-device/scripts/depgraph/layout.ts

// Deterministic build-time graph layouts.
//
// Both layouts are computed here, in Node, and shipped as coordinates. The viewer never
// runs a physics simulation: a phone renders a static point set with pan/zoom instead of
// spending its battery re-deriving one, and two people looking at the same graph see the
// same picture.

import type { GraphData, GraphEdge, GraphNode } from './model.ts';

export type Point = { x: number; y: number };

/** mulberry32 — small, seeded, and stable across Node versions. */
function seededRandom(seed: number): () => number {
  let state = seed >>> 0;
  return () => {
    state = (state + 0x6d2b79f5) >>> 0;
    let t = Math.imul(state ^ (state >>> 15), 1 | state);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

/**
 * 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 = 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);
  }

  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;
}

type Body = { x: number; y: number; vx: number; vy: number; mass: number };

type QuadNode = {
  cx: number;
  cy: number;
  size: number;
  mass: number;
  massX: number;
  massY: number;
  body: Body | null;
  children: (QuadNode | null)[] | null;
};

function makeQuad(cx: number, cy: number, size: number): QuadNode {
  return { cx, cy, size, mass: 0, massX: 0, massY: 0, body: null, children: null };
}

function quadrantOf(quad: QuadNode, body: Body): number {
  return (body.x > quad.cx ? 1 : 0) + (body.y > quad.cy ? 2 : 0);
}

function childQuad(quad: QuadNode, index: number): QuadNode {
  const half = quad.size / 2;
  const offsetX = index % 2 === 0 ? -half / 2 : half / 2;
  const offsetY = index < 2 ? -half / 2 : half / 2;
  return makeQuad(quad.cx + offsetX, quad.cy + offsetY, half);
}

function insertBody(quad: QuadNode, body: Body, depth = 0): void {
  quad.mass += body.mass;
  quad.massX += body.x * body.mass;
  quad.massY += body.y * body.mass;

  if (quad.children === null && quad.body === null) {
    quad.body = body;
    return;
  }

  // Bail out of subdividing pathological ties (identical coordinates) instead of
  // recursing until the stack gives up.
  if (depth > 48) return;

  if (quad.children === null) {
    const existing = quad.body!;
    quad.body = null;
    quad.children = [null, null, null, null];
    const index = quadrantOf(quad, existing);
    quad.children[index] = childQuad(quad, index);
    insertBody(quad.children[index]!, existing, depth + 1);
  }

  const index = quadrantOf(quad, body);
  quad.children[index] ??= childQuad(quad, index);
  insertBody(quad.children[index]!, body, depth + 1);
}

function applyRepulsion(quad: QuadNode, body: Body, strength: number, theta: number): void {
  if (quad.mass === 0) return;
  const centerX = quad.massX / quad.mass;
  const centerY = quad.massY / quad.mass;
  let dx = body.x - centerX;
  let dy = body.y - centerY;
  let distanceSq = dx * dx + dy * dy;

  if (quad.body === body && quad.children === null) return;

  if (quad.children !== null && quad.size * quad.size > theta * theta * distanceSq) {
    for (const child of quad.children) {
      if (child) applyRepulsion(child, body, strength, theta);
    }
    return;
  }

  if (distanceSq < 0.01) {
    // Deterministic nudge so coincident bodies still separate.
    dx = 0.1;
    dy = 0.1;
    distanceSq = 0.02;
  }
  const force = (strength * body.mass * quad.mass) / distanceSq;
  const distance = Math.sqrt(distanceSq);
  body.vx += (dx / distance) * force;
  body.vy += (dy / distance) * force;
}

type GroupPlacement = { center: Point; radius: number };

/**
 * Phase one of the cluster layout: place the ~56 folder groups relative to each other by
 * how much they import from each other. Laying out the aggregate first is what makes the
 * file-level result read as separate islands; a single flat simulation over 892 nodes
 * converges to one hairball no matter how the constants are tuned.
 */
function placeGroups(graph: GraphData): Map<string, GroupPlacement> {
  const sizes = new Map<string, number>();
  for (const node of graph.nodes) sizes.set(node.group, (sizes.get(node.group) ?? 0) + 1);
  const groups = [...sizes.keys()].sort();

  const weights = new Map<string, number>();
  const groupOf = new Map(graph.nodes.map((node) => [node.id, node.group]));
  for (const edge of graph.edges) {
    const from = groupOf.get(edge.from);
    const to = groupOf.get(edge.to);
    if (!from || !to || from === to) continue;
    const key = from < to ? `${from}${to}` : `${to}${from}`;
    weights.set(key, (weights.get(key) ?? 0) + (edge.kind === 'value' ? 1 : 0.4));
  }

  const random = seededRandom(0xc0ffee);
  const bodies = new Map<string, Body>();
  groups.forEach((group, index) => {
    const angle = (index / groups.length) * Math.PI * 2;
    const spread = 900 + random() * 200;
    bodies.set(group, {
      x: Math.cos(angle) * spread,
      y: Math.sin(angle) * spread,
      vx: 0,
      vy: 0,
      mass: Math.sqrt(sizes.get(group)!),
    });
  });

  const links = [...weights].map(([key, weight]) => {
    const [from, to] = key.split('');
    return { from: bodies.get(from!)!, to: bodies.get(to!)!, weight };
  });
  const maxWeight = Math.max(1, ...links.map((link) => link.weight));

  for (let step = 0; step < 1200; step++) {
    const cooling = 1 - step / 1200;
    for (const body of bodies.values()) {
      for (const other of bodies.values()) {
        if (other === body) continue;
        const dx = body.x - other.x;
        const dy = body.y - other.y;
        const distanceSq = Math.max(dx * dx + dy * dy, 1);
        const force = (26000 * body.mass * other.mass) / distanceSq;
        const distance = Math.sqrt(distanceSq);
        body.vx += (dx / distance) * force;
        body.vy += (dy / distance) * force;
      }
    }

    for (const link of links) {
      // Normalising by the heaviest link keeps `daemon/handlers` from collapsing onto
      // `kernel` purely because it has the most imports.
      const pull = 0.05 * Math.sqrt(link.weight / maxWeight);
      const dx = link.to.x - link.from.x;
      const dy = link.to.y - link.from.y;
      link.from.vx += dx * pull;
      link.from.vy += dy * pull;
      link.to.vx -= dx * pull;
      link.to.vy -= dy * pull;
    }

    for (const body of bodies.values()) {
      body.vx -= body.x * 0.004;
      body.vy -= body.y * 0.004;
      const speed = Math.hypot(body.vx, body.vy);
      const maxSpeed = 60 * cooling + 2;
      const scale = speed > maxSpeed ? maxSpeed / speed : 1;
      body.x += body.vx * scale;
      body.y += body.vy * scale;
      body.vx *= 0.75;
      body.vy *= 0.75;
    }
  }

  const radiusOf = (group: string): number => 26 + Math.sqrt(sizes.get(group)!) * 13;

  // Radial equalization. The simulation gets the angular arrangement right — related
  // folders end up adjacent — but a group with few cross-folder imports has nothing
  // holding it in, so raw distances leave isolated islands stranded off-canvas. Keep each
  // group's bearing and redistribute distance evenly over a disc big enough to hold every
  // island.
  const meanX = groups.reduce((sum, group) => sum + bodies.get(group)!.x, 0) / groups.length;
  const meanY = groups.reduce((sum, group) => sum + bodies.get(group)!.y, 0) / groups.length;
  const spread = Math.sqrt(groups.reduce((sum, group) => sum + radiusOf(group) ** 2, 0)) * 2.1;
  const byDistance = [...groups].sort((left, right) => {
    const distance = (group: string): number =>
      Math.hypot(bodies.get(group)!.x - meanX, bodies.get(group)!.y - meanY);
    return distance(left) - distance(right);
  });

  const placements = new Map<string, GroupPlacement>();
  byDistance.forEach((group, index) => {
    const body = bodies.get(group)!;
    const angle = Math.atan2(body.y - meanY, body.x - meanX);
    const distance = spread * Math.sqrt((index + 0.35) / byDistance.length);
    placements.set(group, {
      center: { x: Math.cos(angle) * distance, y: Math.sin(angle) * distance },
      radius: radiusOf(group),
    });
  });
  return placements;
}

/**
 * Phase two: files settle inside their group's disc under Barnes-Hut repulsion and their
 * own dependencies, anchored to the group centre placed by phase one. Folders therefore
 * read as islands whose distance from each other means something, while hubs still sit
 * where their edges pull them.
 */
export function clusterLayout(graph: GraphData): Map<string, Point> {
  const placements = placeGroups(graph);
  const random = seededRandom(0x5eed);
  const bodies = new Map<string, Body>();
  const anchors = new Map<string, Point>();

  for (const node of graph.nodes) {
    const placement = placements.get(node.group)!;
    const angle = random() * Math.PI * 2;
    const distance = Math.sqrt(random()) * placement.radius;
    bodies.set(node.id, {
      x: placement.center.x + Math.cos(angle) * distance,
      y: placement.center.y + Math.sin(angle) * distance,
      vx: 0,
      vy: 0,
      // Heavier hubs settle in the middle of their neighbourhood rather than being
      // flung around by it.
      mass: 1 + Math.sqrt(node.fanIn + node.fanOut),
    });
    anchors.set(node.id, placement.center);
  }

  const springs = graph.edges.map((edge) => ({
    from: bodies.get(edge.from)!,
    to: bodies.get(edge.to)!,
    // Type-only and dynamic edges pull less: they are weaker coupling, and letting them
    // dominate the picture hides the static value structure.
    weight: edge.kind === 'value' ? 1 : 0.3,
    // Cross-group edges pull weakly — phase one already accounted for them, and letting
    // them pull at full strength would drag files out of their own island.
    scale: anchors.get(edge.from) === anchors.get(edge.to) ? 1 : 0.18,
  }));

  const iterations = 500;
  for (let step = 0; step < iterations; step++) {
    const cooling = 1 - step / iterations;

    let extent = 1;
    for (const body of bodies.values()) {
      extent = Math.max(extent, Math.abs(body.x), Math.abs(body.y));
    }
    const root = makeQuad(0, 0, extent * 2.2);
    for (const body of bodies.values()) insertBody(root, body);
    for (const body of bodies.values()) applyRepulsion(root, body, 150, 0.9);

    for (const spring of springs) {
      const dx = spring.to.x - spring.from.x;
      const dy = spring.to.y - spring.from.y;
      const force = 0.006 * spring.weight * spring.scale;
      spring.from.vx += dx * force;
      spring.from.vy += dy * force;
      spring.to.vx -= dx * force;
      spring.to.vy -= dy * force;
    }

    for (const [id, body] of bodies) {
      const anchor = anchors.get(id)!;
      // The anchor is the only long-range force on a file, so nothing can be flung out
      // of frame by an unlucky repulsion step.
      body.vx += (anchor.x - body.x) * 0.045;
      body.vy += (anchor.y - body.y) * 0.045;
      const speed = Math.hypot(body.vx, body.vy);
      const maxSpeed = 22 * cooling + 1;
      const scale = speed > maxSpeed ? maxSpeed / speed : 1;
      body.x += body.vx * scale;
      body.y += body.vy * scale;
      body.vx *= 0.8;
      body.vy *= 0.8;
    }
  }

  return new Map([...bodies].map(([id, body]) => [id, { x: body.x, y: body.y }]));
}

/**
 * Layered layout: x is the node's DAG height over value edges (sinks left, entrypoints
 * right), y is relaxed by barycenter iterations so edges run as straight as possible.
 * Reading right-to-left in this view is what a layering violation looks like.
 */
export function layeredLayout(graph: GraphData, levels: Map<string, number>): Map<string, Point> {
  const rowGap = 17;
  const byLevel = new Map<number, GraphNode[]>();
  for (const node of graph.nodes) {
    const level = levels.get(node.id) ?? 0;
    const list = byLevel.get(level) ?? [];
    list.push(node);
    byLevel.set(level, list);
  }

  // Aim for a roughly square drawing: the tallest column sets the height, so spacing the
  // columns by height/levels keeps the whole thing framable on a phone in one gesture.
  const tallest = Math.max(...[...byLevel.values()].map((nodes) => nodes.length));
  const columnGap = Math.max(180, (tallest * rowGap) / Math.max(byLevel.size, 1));

  const positions = new Map<string, Point>();
  for (const [level, nodes] of byLevel) {
    // Seed each column grouped by folder so the relaxation starts from something
    // structurally sensible rather than alphabetical noise.
    const ordered = [...nodes].sort(
      (left, right) => left.group.localeCompare(right.group) || left.id.localeCompare(right.id),
    );
    ordered.forEach((node, index) => {
      positions.set(node.id, {
        x: level * columnGap,
        y: (index - (ordered.length - 1) / 2) * rowGap,
      });
    });
  }

  const neighbours = new Map<string, string[]>();
  for (const edge of graph.edges) {
    for (const [a, b] of [
      [edge.from, edge.to],
      [edge.to, edge.from],
    ]) {
      const list = neighbours.get(a!) ?? [];
      list.push(b!);
      neighbours.set(a!, list);
    }
  }

  for (let pass = 0; pass < 40; pass++) {
    for (const [, nodes] of byLevel) {
      for (const node of nodes) {
        const linked = neighbours.get(node.id) ?? [];
        if (linked.length === 0) continue;
        let sum = 0;
        for (const other of linked) sum += positions.get(other)?.y ?? 0;
        const target = sum / linked.length;
        const current = positions.get(node.id)!;
        current.y += (target - current.y) * 0.35;
      }
      // Re-separate within the column: sort by the relaxed y, then enforce the row gap so
      // barycentering cannot collapse a column into one overlapping stack.
      const ordered = [...nodes].sort(
        (left, right) => positions.get(left.id)!.y - positions.get(right.id)!.y,
      );
      let previous = -Infinity;
      for (const node of ordered) {
        const point = positions.get(node.id)!;
        point.y = Math.max(point.y, previous + rowGap);
        previous = point.y;
      }
      const midpoint =
        (positions.get(ordered[0]!.id)!.y + positions.get(ordered[ordered.length - 1]!.id)!.y) / 2;
      for (const node of ordered) positions.get(node.id)!.y -= midpoint;
    }
  }

  return positions;
}