geometry.js

function pathId(path) {
  return path.length === 0 ? "root" : path.join(".");
}

/** Deterministically lay out an authored traversal tree without a graph engine. */
function layoutTraversalStructure(structure, options = {}) {
  const horizontalGap = options.horizontalGap ?? 190;
  const verticalGap = options.verticalGap ?? 112;
  const margin = options.margin ?? 110;
  const nodes = [];
  const edges = [];
  let leafOrdinal = 0;
  let maximumDepth = 0;

  function visit(element, depth, parentId, ordinal) {
    maximumDepth = Math.max(maximumDepth, depth);
    const id = element.kind === "traversal-structure" ? "root" : pathId(element.path);
    const children = element.children ?? [];
    const childPositions = children.map((child, childOrdinal) =>
      visit(child, depth + 1, id, childOrdinal)
    );
    const x = childPositions.length > 0
      ? (childPositions[0] + childPositions.at(-1)) / 2
      : margin + leafOrdinal++ * horizontalGap;
    const y = margin / 2 + depth * verticalGap;
    nodes.push({
      id,
      kind: element.kind,
      path: element.path ?? [],
      pointer: element.pointer,
      title: element.title,
      resolved: element.resolved,
      provenance: element.provenance,
      span: element.span,
      x,
      y,
      depth
    });
    if (parentId) {
      edges.push({
        id: `${parentId}->${id}`,
        from: parentId,
        to: id,
        ordinal
      });
    }
    return x;
  }

  visit(structure, 0, undefined, 0);
  const orderedNodes = nodes.sort((left, right) =>
    left.depth - right.depth || left.x - right.x
  );
  return {
    kind: "traversal-geometry",
    nodes: orderedNodes,
    edges,
    width: Math.max(760, margin * 2 + Math.max(1, leafOrdinal - 1) * horizontalGap),
    height: margin + (maximumDepth + 1) * verticalGap,
    pointerCount: structure.pointerCount,
    groupCount: structure.groupCount,
    depth: structure.depth
  };
}

module.exports = { layoutTraversalStructure };