import type { Page } from "playwright";
import type { MatrixCell } from "../../../schema/src/records/context.js";
import { awaitSettled, type SettleOptions } from "../../../playwright/src/settled.js";
import type {
  JitterEnvelope,
  MeasuredLayoutAxis,
  MeasuredLayoutEdge,
  MeasuredLayoutGraph,
  MeasuredLayoutLogicalEdgeOffsets,
  MeasuredLayoutNode,
  MeasuredLayoutProbe,
  MeasuredLayoutRect,
  MeasuredLayoutSettledState,
  MeasuredLayoutViewport,
} from "./types.js";
import { MEASURED_LAYOUT_DETECTOR_VERSION } from "./types.js";

export type MeasuredLayoutGraphInstrumentation = {
  comparisons: number;
};

export type MeasuredLayoutGraphInput = {
  cellId: string;
  viewport: MeasuredLayoutViewport;
  nodes: MeasuredLayoutNode[];
  interveningPaintedNodeIdentities?: Record<string, string[]>;
  instrumentation?: MeasuredLayoutGraphInstrumentation;
};

type ProbeSample = Omit<MeasuredLayoutGraphInput, "cellId">;

function compareText(left: string, right: string): number {
  return left.localeCompare(right);
}

function finite(value: number, name: string): number {
  if (!Number.isFinite(value)) {
    throw new Error(`${name} must be finite`);
  }
  return value;
}

function validRect(rect: MeasuredLayoutRect, name: string): void {
  finite(rect.x, `${name}.x`);
  finite(rect.y, `${name}.y`);
  finite(rect.width, `${name}.width`);
  finite(rect.height, `${name}.height`);
  if (rect.width < 0 || rect.height < 0) {
    throw new Error(`${name} dimensions must be non-negative`);
  }
}

function validateNode(node: MeasuredLayoutNode): void {
  if (node.identity.length === 0 || node.structuralSignature.length === 0) {
    throw new Error("measured layout node identity is corrupt");
  }
  validRect(node.borderBox, `${node.identity}.borderBox`);
  validRect(node.contentBox, `${node.identity}.contentBox`);
  if (node.childUnionBox !== null) validRect(node.childUnionBox, `${node.identity}.childUnionBox`);
  if (node.visibility.visible && (node.visibility.zeroArea || node.borderBox.width === 0 || node.borderBox.height === 0)) {
    throw new Error("visible measured layout node has zero area");
  }
}

function perpendicularOverlap(left: MeasuredLayoutRect, right: MeasuredLayoutRect, axis: MeasuredLayoutAxis): number {
  const horizontal = axis === "x" || axis === "horizontal" || axis === "inline";
  const start = horizontal ? Math.max(left.y, right.y) : Math.max(left.x, right.x);
  const end = horizontal ? Math.min(left.y + left.height, right.y + right.height) : Math.min(left.x + left.width, right.x + right.width);
  return Math.max(0, end - start);
}

function clearance(source: MeasuredLayoutNode, target: MeasuredLayoutNode, axis: "x" | "y"): number {
  if (axis === "y") return target.borderBox.y - (source.borderBox.y + source.borderBox.height);
  return source.direction === "rtl"
    ? source.borderBox.x - (target.borderBox.x + target.borderBox.width)
    : target.borderBox.x - (source.borderBox.x + source.borderBox.width);
}

function logicalOffsets(node: MeasuredLayoutNode, viewport: MeasuredLayoutViewport): MeasuredLayoutLogicalEdgeOffsets {
  const rect = node.borderBox;
  return node.direction === "rtl"
    ? {
        logicalStart: viewport.clientWidth - (rect.x + rect.width),
        logicalEnd: rect.x,
        blockStart: rect.y,
        blockEnd: viewport.clientHeight - (rect.y + rect.height),
      }
    : {
        logicalStart: rect.x,
        logicalEnd: viewport.clientWidth - (rect.x + rect.width),
        blockStart: rect.y,
        blockEnd: viewport.clientHeight - (rect.y + rect.height),
      };
}

function edge(
  source: MeasuredLayoutNode,
  target: MeasuredLayoutNode,
  relation: MeasuredLayoutEdge["relation"],
  axis: MeasuredLayoutAxis,
  layoutOrder: number,
  viewport: MeasuredLayoutViewport,
): MeasuredLayoutEdge {
  const measuredAxis = axis === "y" || axis === "vertical" || axis === "block" ? "y" : "x";
  return {
    source: source.identity,
    target: target.identity,
    relation,
    axis,
    layoutOrder,
    signedClearance: clearance(source, target, measuredAxis),
    perpendicularOverlap: perpendicularOverlap(source.borderBox, target.borderBox, measuredAxis),
    logicalEdgeOffsets: logicalOffsets(source, viewport),
    interveningPaintedNodeIdentities: [],
  };
}

function axisForSiblings(parent: MeasuredLayoutNode | undefined): "x" | "y" {
  if (parent?.flexGridTopology.kind === "flex") {
    return parent.flexGridTopology.flexDirection?.startsWith("column") ? "y" : "x";
  }
  return "y";
}

function layoutOrder(nodes: MeasuredLayoutNode[], axis: "x" | "y", direction: "ltr" | "rtl" = "ltr"): MeasuredLayoutNode[] {
  return [...nodes].sort((left, right) => {
    const physical = axis === "x" ? left.borderBox.x - right.borderBox.x : left.borderBox.y - right.borderBox.y;
    const primary = axis === "x" && direction === "rtl" ? -physical : physical;
    if (primary !== 0) return primary;
    const secondary = axis === "x" ? left.borderBox.y - right.borderBox.y : left.borderBox.x - right.borderBox.x;
    if (secondary !== 0) return secondary;
    return compareText(left.identity, right.identity);
  });
}

function directSiblings(nodes: MeasuredLayoutNode[], byIdentity: Map<string, MeasuredLayoutNode>, viewport: MeasuredLayoutViewport): MeasuredLayoutEdge[] {
  const childrenByParent = new Map<string, MeasuredLayoutNode[]>();
  for (const node of nodes) {
    if (node.parent === null) continue;
    const children = childrenByParent.get(node.parent) ?? [];
    children.push(node);
    childrenByParent.set(node.parent, children);
  }
  const edges: MeasuredLayoutEdge[] = [];
  for (const [parentIdentity, children] of [...childrenByParent.entries()].sort(([left], [right]) => compareText(left, right))) {
    const parent = byIdentity.get(parentIdentity);
    const axis = axisForSiblings(parent);
    const ordered = layoutOrder(children, axis, parent?.direction ?? children[0]?.direction ?? "ltr");
    for (let index = 1; index < ordered.length; index += 1) {
      const source = ordered[index - 1];
      const target = ordered[index];
      if (source === undefined || target === undefined) throw new Error("measured layout sibling order is corrupt");
      edges.push(edge(source, target, "sibling", axis, index - 1, viewport));
    }
  }
  return edges;
}

function directContains(nodes: MeasuredLayoutNode[], byIdentity: Map<string, MeasuredLayoutNode>, viewport: MeasuredLayoutViewport): MeasuredLayoutEdge[] {
  return nodes
    .filter((node) => node.parent !== null && byIdentity.has(node.parent))
    .sort((left, right) => compareText(left.identity, right.identity))
    .map((node, index) => {
      const parent = node.parent === null ? undefined : byIdentity.get(node.parent);
      if (parent === undefined) throw new Error("measured layout containment edge is corrupt");
      return edge(parent, node, "contains", "block", index, viewport);
    });
}

type SweepCandidate = {
  node: MeasuredLayoutNode;
  primaryEnd: number;
};

class SweepIntervalIndex {
  private readonly local: Array<SweepCandidate | undefined>;
  private readonly aggregate: Array<SweepCandidate | undefined>;

  constructor(
    private readonly bucketCount: number,
    private readonly instrumentation: MeasuredLayoutGraphInstrumentation | undefined,
  ) {
    const capacity = Math.max(1, bucketCount * 4);
    this.local = Array.from({ length: capacity });
    this.aggregate = Array.from({ length: capacity });
  }

  update(start: number, end: number, candidate: SweepCandidate): void {
    this.updateRange(1, 0, this.bucketCount, start, end, candidate);
  }

  best(start: number, end: number): SweepCandidate | undefined {
    return this.queryRange(1, 0, this.bucketCount, start, end, undefined);
  }

  private better(left: SweepCandidate | undefined, right: SweepCandidate | undefined): SweepCandidate | undefined {
    if (left === undefined) return right;
    if (right === undefined) return left;
    if (this.instrumentation !== undefined) this.instrumentation.comparisons += 1;
    if (left.primaryEnd !== right.primaryEnd) return left.primaryEnd > right.primaryEnd ? left : right;
    return compareText(left.node.identity, right.node.identity) <= 0 ? left : right;
  }

  private updateRange(
    treeIndex: number,
    segmentStart: number,
    segmentEnd: number,
    rangeStart: number,
    rangeEnd: number,
    candidate: SweepCandidate,
  ): void {
    if (rangeStart <= segmentStart && segmentEnd <= rangeEnd) {
      this.local[treeIndex] = this.better(this.local[treeIndex], candidate);
      this.aggregate[treeIndex] = this.better(this.aggregate[treeIndex], candidate);
      return;
    }
    const middle = Math.floor((segmentStart + segmentEnd) / 2);
    if (rangeStart < middle) this.updateRange(treeIndex * 2, segmentStart, middle, rangeStart, rangeEnd, candidate);
    if (rangeEnd > middle) this.updateRange(treeIndex * 2 + 1, middle, segmentEnd, rangeStart, rangeEnd, candidate);
    this.aggregate[treeIndex] = this.better(
      this.local[treeIndex],
      this.better(this.aggregate[treeIndex * 2], this.aggregate[treeIndex * 2 + 1]),
    );
  }

  private queryRange(
    treeIndex: number,
    segmentStart: number,
    segmentEnd: number,
    rangeStart: number,
    rangeEnd: number,
    inherited: SweepCandidate | undefined,
  ): SweepCandidate | undefined {
    const bestHere = this.better(inherited, this.local[treeIndex]);
    if (rangeStart <= segmentStart && segmentEnd <= rangeEnd) {
      return this.better(bestHere, this.aggregate[treeIndex]);
    }
    const middle = Math.floor((segmentStart + segmentEnd) / 2);
    let result: SweepCandidate | undefined;
    if (rangeStart < middle) result = this.queryRange(treeIndex * 2, segmentStart, middle, rangeStart, rangeEnd, bestHere);
    if (rangeEnd > middle) {
      result = this.better(result, this.queryRange(treeIndex * 2 + 1, middle, segmentEnd, rangeStart, rangeEnd, bestHere));
    }
    return result;
  }
}

function sweepAdjacency(
  nodes: MeasuredLayoutNode[],
  axis: "x" | "y",
  viewport: MeasuredLayoutViewport,
  instrumentation: MeasuredLayoutGraphInstrumentation | undefined,
): MeasuredLayoutEdge[] {
  const ordered = layoutOrder(nodes, axis);
  const perpendicularCoordinates = [...new Set(nodes.flatMap((node) => axis === "x"
    ? [node.borderBox.y, node.borderBox.y + node.borderBox.height]
    : [node.borderBox.x, node.borderBox.x + node.borderBox.width]))].sort((left, right) => left - right);
  const coordinateIndex = new Map(perpendicularCoordinates.map((coordinate, index) => [coordinate, index]));
  const bucketCount = Math.max(0, perpendicularCoordinates.length - 1);
  const index = new SweepIntervalIndex(bucketCount, instrumentation);
  const range = (node: MeasuredLayoutNode): [number, number] => {
    const start = axis === "x" ? node.borderBox.y : node.borderBox.x;
    const end = start + (axis === "x" ? node.borderBox.height : node.borderBox.width);
    const startIndex = coordinateIndex.get(start);
    const endIndex = coordinateIndex.get(end);
    if (startIndex === undefined || endIndex === undefined || endIndex <= startIndex) throw new Error("measured layout sweep coordinates are corrupt");
    return [startIndex, endIndex];
  };
  const primaryStart = (node: MeasuredLayoutNode): number => axis === "x" ? node.borderBox.x : node.borderBox.y;
  const primaryEnd = (node: MeasuredLayoutNode): number => primaryStart(node) + (axis === "x" ? node.borderBox.width : node.borderBox.height);
  const edges: MeasuredLayoutEdge[] = [];

  const closing = [...nodes].sort((left, right) =>
    primaryEnd(left) - primaryEnd(right) || compareText(left.identity, right.identity),
  );
  let closed = 0;
  for (const current of ordered) {
    const sweepLine = primaryStart(current);
    while (closed < closing.length) {
      const pending = closing[closed];
      if (pending === undefined || primaryEnd(pending) > sweepLine) break;
      const [pendingStart, pendingEnd] = range(pending);
      index.update(pendingStart, pendingEnd, { node: pending, primaryEnd: primaryEnd(pending) });
      closed += 1;
    }
    const [start, end] = range(current);
    const candidate = index.best(start, end);
    if (candidate !== undefined) edges.push(edge(candidate.node, current, "region-adjacent", axis, edges.length, viewport));
  }
  return edges;
}

function sameTrackEdges(nodes: MeasuredLayoutNode[], viewport: MeasuredLayoutViewport): MeasuredLayoutEdge[] {
  const groups = new Map<string, MeasuredLayoutNode[]>();
  for (const node of nodes) {
    const parent = node.parent;
    const topology = node.flexGridTopology;
    if (parent === null || topology.kind !== "grid" || topology.gridRow === null || topology.gridColumn === null) continue;
    const key = `${parent}|${String(topology.gridRow)}`;
    const group = groups.get(key) ?? [];
    group.push(node);
    groups.set(key, group);
  }
  const edges: MeasuredLayoutEdge[] = [];
  for (const [, group] of [...groups.entries()].sort(([left], [right]) => compareText(left, right))) {
    const ordered = layoutOrder(group, "x", group[0]?.direction ?? "ltr");
    for (let index = 1; index < ordered.length; index += 1) {
      const source = ordered[index - 1];
      const target = ordered[index];
      if (source === undefined || target === undefined) throw new Error("measured layout track order is corrupt");
      edges.push(edge(source, target, "same-track", "x", index - 1, viewport));
    }
  }
  return edges;
}

function alignmentEdges(nodes: MeasuredLayoutNode[], viewport: MeasuredLayoutViewport): MeasuredLayoutEdge[] {
  const ordered = [...nodes].sort((left, right) => {
    const leftStart = logicalOffsets(left, viewport).logicalStart;
    const rightStart = logicalOffsets(right, viewport).logicalStart;
    return leftStart - rightStart || compareText(left.identity, right.identity);
  });
  const edges: MeasuredLayoutEdge[] = [];
  for (let index = 1; index < ordered.length; index += 1) {
    const previous = ordered[index - 1];
    const current = ordered[index];
    if (previous === undefined || current === undefined) throw new Error("measured layout alignment order is corrupt");
    if (logicalOffsets(previous, viewport).logicalStart === logicalOffsets(current, viewport).logicalStart) {
      edges.push(edge(previous, current, "aligned", "inline", index - 1, viewport));
    }
  }
  return edges;
}


function graphVisibleNodes(nodes: ProbeSample["nodes"]): ProbeSample["nodes"] {
  return visibleNodesInCaptureOrder(nodes)
    .sort((left, right) => compareText(left.identity, right.identity));
}

function visibleNodesInCaptureOrder(nodes: ProbeSample["nodes"]): ProbeSample["nodes"] {
  return nodes.filter((node) => node.visibility.visible && !node.visibility.zeroArea && node.borderBox.width > 0 && node.borderBox.height > 0);
}

export function buildMeasuredLayoutGraph(input: MeasuredLayoutGraphInput): MeasuredLayoutGraph {
  if (input.instrumentation !== undefined) input.instrumentation.comparisons = 0;
  if (input.cellId.length === 0 || input.viewport.clientWidth <= 0 || input.viewport.clientHeight <= 0 || input.viewport.width !== input.viewport.clientWidth) {
    throw new Error("measured layout graph input is corrupt");
  }
  if (input.viewport.scrollX !== 0 || input.viewport.scrollY !== 0) {
    throw new Error("measured layout graph must be captured at rest");
  }
  const identities = new Set<string>();
  const nodes = graphVisibleNodes(input.nodes)
    .map((node) => ({ ...node, textLineRects: [...node.textLineRects] }));
  for (const node of nodes) {
    validateNode(node);
    if (identities.has(node.identity)) throw new Error(`duplicate measured layout node: ${node.identity}`);
    identities.add(node.identity);
  }
  const byIdentity = new Map(nodes.map((node) => [node.identity, node]));
  const edges = [
    ...directSiblings(nodes, byIdentity, input.viewport),
    ...directContains(nodes, byIdentity, input.viewport),
    ...sweepAdjacency(nodes, "x", input.viewport, input.instrumentation),
    ...sweepAdjacency(nodes, "y", input.viewport, input.instrumentation),
    ...sameTrackEdges(nodes, input.viewport),
    ...alignmentEdges(nodes, input.viewport),
  ].filter((candidate) => {
    if (candidate.relation !== "region-adjacent") return true;
    const key = `${candidate.source}|${candidate.target}|${candidate.axis}`;
    return Object.hasOwn(input.interveningPaintedNodeIdentities ?? {}, key)
      && input.interveningPaintedNodeIdentities?.[key]?.length === 0;
  })
    .map((candidate) => ({
      ...candidate,
      interveningPaintedNodeIdentities: [...(input.interveningPaintedNodeIdentities?.[`${candidate.source}|${candidate.target}|${candidate.axis}`] ?? [])].sort(compareText),
    }))
    .sort((left, right) =>
    compareText(left.relation, right.relation)
    || compareText(left.axis, right.axis)
    || compareText(left.source, right.source)
    || compareText(left.target, right.target)
    || left.layoutOrder - right.layoutOrder,
  );
  return {
    version: MEASURED_LAYOUT_DETECTOR_VERSION,
    cellId: input.cellId,
    coordinateSpace: "css-pixels",
    normalizedAtRest: true,
    viewport: input.viewport,
    nodes,
    edges,
  };
}

function numericLeaves(value: unknown, path = ""): Map<string, number> {
  const result = new Map<string, number>();
  if (typeof value === "number") {
    if (!Number.isFinite(value)) throw new Error(`measured layout sample has a non-finite numeric field at ${path}`);
    result.set(path, value);
  } else if (Array.isArray(value)) {
    value.forEach((entry, index) => {
      for (const [key, number] of numericLeaves(entry, `${path}[${String(index)}]`).entries()) result.set(key, number);
    });
  } else if (value !== null && typeof value === "object") {
    for (const [key, entry] of Object.entries(value)) {
      for (const [childPath, number] of numericLeaves(entry, path.length === 0 ? key : `${path}.${key}`).entries()) result.set(childPath, number);
    }
  }
  return result;
}

function categoricalStructure(value: unknown): unknown {
  if (typeof value === "number") return ["number"];
  if (typeof value === "string") return ["string", value];
  if (typeof value === "boolean") return ["boolean", value];
  if (value === null) return ["null"];
  if (value === undefined) return ["undefined"];
  if (Array.isArray(value)) return ["array", ...value.map(categoricalStructure)];
  if (typeof value === "object") {
    return ["object", ...Object.entries(value)
      .sort(([left], [right]) => compareText(left, right))
      .map(([key, entry]) => [key, categoricalStructure(entry)])];
  }
  throw new Error("measured layout sample contains an unsupported field");
}

function jitterEnvelope(first: ProbeSample, second: ProbeSample): JitterEnvelope {
  const firstIdentities = first.nodes.map((node) => node.identity);
  const secondIdentities = second.nodes.map((node) => node.identity);
  if (JSON.stringify(firstIdentities) !== JSON.stringify(secondIdentities)) {
    throw new Error("measured layout repeated samples have different node identity order");
  }
  const canonicalFirst = { ...first, nodes: graphVisibleNodes(first.nodes) };
  const canonicalSecond = { ...second, nodes: graphVisibleNodes(second.nodes) };
  if (JSON.stringify(categoricalStructure(canonicalFirst)) !== JSON.stringify(categoricalStructure(canonicalSecond))) {
    throw new Error("measured layout repeated samples have different categorical structure");
  }
  const firstValues = numericLeaves(canonicalFirst);
  const secondValues = numericLeaves(canonicalSecond);
  const firstPaths = [...firstValues.keys()].sort(compareText);
  const secondPaths = [...secondValues.keys()].sort(compareText);
  if (JSON.stringify(firstPaths) !== JSON.stringify(secondPaths)) {
    throw new Error("measured layout repeated samples have different numeric fields");
  }
  const maxDeltaByField: Record<string, number> = {};
  for (const path of firstPaths) {
    const value = firstValues.get(path);
    const comparison = secondValues.get(path);
    if (value === undefined || comparison === undefined) throw new Error("measured layout repeated sample fields are corrupt");
    maxDeltaByField[path] = Math.abs(value - comparison);
  }
  return { sampleCount: 2, maxDeltaByField };
}

type PaintedRegionSamplingRequest = {
  key: string;
  source: string;
  target: string;
  axis: "x" | "y";
  points: Array<{ x: number; y: number }>;
};

function paintedRegionSamplingRequests(sample: ProbeSample): PaintedRegionSamplingRequest[] {
  const nodes = sample.nodes.filter((node) =>
    node.visibility.visible
    && !node.visibility.zeroArea
    && node.borderBox.width > 0
    && node.borderBox.height > 0,
  );
  const byIdentity = new Map(nodes.map((node) => [node.identity, node]));
  return (["x", "y"] as const).flatMap((axis) =>
    sweepAdjacency(nodes, axis, sample.viewport, undefined).map((candidate) => {
      const source = byIdentity.get(candidate.source);
      const target = byIdentity.get(candidate.target);
      if (source === undefined || target === undefined) throw new Error("measured layout adjacency candidate is corrupt");
      const overlapStart = axis === "x"
        ? Math.max(source.borderBox.y, target.borderBox.y)
        : Math.max(source.borderBox.x, target.borderBox.x);
      const overlapEnd = axis === "x"
        ? Math.min(source.borderBox.y + source.borderBox.height, target.borderBox.y + target.borderBox.height)
        : Math.min(source.borderBox.x + source.borderBox.width, target.borderBox.x + target.borderBox.width);
      const primary = axis === "x"
        ? (source.borderBox.x + source.borderBox.width + target.borderBox.x) / 2
        : (source.borderBox.y + source.borderBox.height + target.borderBox.y) / 2;
      const overlapLength = overlapEnd - overlapStart;
      const deviceScaleFactor = sample.viewport.deviceScaleFactor;
      if (!Number.isFinite(deviceScaleFactor) || deviceScaleFactor <= 0) {
        throw new Error("measured layout viewport has an invalid device scale factor");
      }
      const pointCount = Math.max(1, Math.ceil(overlapLength * deviceScaleFactor));
      const points = Array.from({ length: pointCount }, (_, index) => {
        const projection = overlapStart + overlapLength * (index + 0.5) / pointCount;
        return axis === "x" ? { x: primary, y: projection } : { x: projection, y: primary };
      });
      return {
        key: `${candidate.source}|${candidate.target}|${axis}`,
        source: candidate.source,
        target: candidate.target,
        axis,
        points,
      };
    }),
  ).sort((left, right) => compareText(left.key, right.key));
}

export async function captureMeasuredLayoutProbe(
  page: Page,
  cell: Pick<MatrixCell, "id">,
  settleOptions: SettleOptions = { timeoutMs: 5_000 },
): Promise<MeasuredLayoutProbe> {
  const normalized = await page.evaluate(() => {
    if (window.scrollX !== 0 || window.scrollY !== 0) window.scrollTo(0, 0);
    return { scrollX: window.scrollX, scrollY: window.scrollY };
  });
  if (normalized.scrollX !== 0 || normalized.scrollY !== 0) {
    throw new Error("measured layout capture could not normalize scroll origin");
  }
  const settled = await awaitSettled(page, settleOptions);
  const rest = await page.evaluate(() => ({ scrollX: window.scrollX, scrollY: window.scrollY }));
  const settledState: MeasuredLayoutSettledState = {
    atRest: rest.scrollX === 0 && rest.scrollY === 0,
    scrollX: rest.scrollX,
    scrollY: rest.scrollY,
    signal: settled.signal,
    timedOut: settled.timedOut,
    phases: { ...settled.phases, normalizedAtRest: rest.scrollX === 0 && rest.scrollY === 0 ? 1 : 0 },
  };
  if (settledState.timedOut || !settledState.atRest) {
    throw new Error("measured layout capture could not settle at scroll origin");
  }

  const sample = (): Promise<ProbeSample> => page.evaluate(() => {
    type Rect = { x: number; y: number; width: number; height: number };
    const rect = (value: DOMRect): Rect => ({ x: value.x, y: value.y, width: value.width, height: value.height });
    const cssNumber = (value: string): number => Number.parseFloat(value) || 0;
    const identity = (element: Element): string => {
      if (element.id.length > 0) return `#${element.id}`;
      if (element === document.documentElement) return "html:root";
      const parts: string[] = [];
      let current: Element | null = element;
      while (current !== null && current !== document.documentElement) {
        const siblingIndex = Array.from(current.parentElement?.children ?? []).indexOf(current) + 1;
        parts.push(`${current.tagName.toLowerCase()}:nth-child(${String(siblingIndex)})`);
        current = current.parentElement;
      }
      return parts.reverse().join(">");
    };
    const structuralSignature = (element: Element): string => {
      const component = element.getAttribute("data-component");
      return `${element.tagName.toLowerCase()}|${element.getAttribute("role") ?? ""}|${component ?? ""}|${[...element.classList].sort().join(".")}`;
    };
    const childUnion = (element: Element): Rect | null => {
      const rects = Array.from(element.children)
        .filter((child) => {
          const childRect = child.getBoundingClientRect();
          const style = getComputedStyle(child);
          return childRect.width > 0 && childRect.height > 0 && style.display !== "none" && style.visibility !== "hidden";
        })
        .map((child) => child.getBoundingClientRect());
      if (rects.length === 0) return null;
      const left = Math.min(...rects.map((child) => child.left));
      const top = Math.min(...rects.map((child) => child.top));
      const right = Math.max(...rects.map((child) => child.right));
      const bottom = Math.max(...rects.map((child) => child.bottom));
      return { x: left, y: top, width: right - left, height: bottom - top };
    };
    const contentBox = (box: DOMRect, style: CSSStyleDeclaration): Rect => ({
      x: box.x + cssNumber(style.borderLeftWidth) + cssNumber(style.paddingLeft),
      y: box.y + cssNumber(style.borderTopWidth) + cssNumber(style.paddingTop),
      width: Math.max(0, box.width - cssNumber(style.borderLeftWidth) - cssNumber(style.borderRightWidth) - cssNumber(style.paddingLeft) - cssNumber(style.paddingRight)),
      height: Math.max(0, box.height - cssNumber(style.borderTopWidth) - cssNumber(style.borderBottomWidth) - cssNumber(style.paddingTop) - cssNumber(style.paddingBottom)),
    });
    const parseRadius = (value: string): { horizontal: number; vertical: number } => {
      const values = value.split("/").map((part) => cssNumber(part.trim()));
      const horizontal = values[0] ?? 0;
      return { horizontal, vertical: values[1] ?? horizontal };
    };
    const flexLine = (element: Element, style: CSSStyleDeclaration): number | null => {
      const parent = element.parentElement;
      if (parent === null || getComputedStyle(parent).display !== "flex") return null;
      const siblings = Array.from(parent.children).filter((candidate) => getComputedStyle(candidate).display !== "none");
      const value = style.flexDirection.startsWith("column") ? element.getBoundingClientRect().left : element.getBoundingClientRect().top;
      return [...new Set(siblings.map((candidate) => style.flexDirection.startsWith("column") ? candidate.getBoundingClientRect().left : candidate.getBoundingClientRect().top))].sort((left, right) => left - right).indexOf(value);
    };
    const compositeIdentity = (element: Element): string | null => {
      const composite = element.closest("[data-component], button, input, select, textarea, [role='tab'], [role='group']");
      return composite === null ? null : identity(composite);
    };
    const gridLine = (value: string): number | null => {
      const match = value.trim().match(/^-?\d+$/);
      return match === null ? null : Number(match[0]);
    };
    const gridSpan = (start: string, end: string): number | null => {
      const span = end.trim().match(/^span\s+(\d+)$/);
      if (span !== null) return Number(span[1]);
      // grid-column-end: auto contributes a single track per CSS Grid placement.
      if (end.trim() === "auto") return 1;
      const startLine = gridLine(start);
      const endLine = gridLine(end);
      return startLine === null || endLine === null || endLine <= startLine ? null : endLine - startLine;
    };
    const gridTopologyByParent = new WeakMap<Element, { count: number; widths: number[]; gaps: number[] }>();
    const measuredGridTopology = (parent: Element, style: CSSStyleDeclaration): { count: number; widths: number[]; gaps: number[] } => {
      const cached = gridTopologyByParent.get(parent);
      if (cached !== undefined) return cached;
      const direction = style.direction === "rtl" ? "rtl" : "ltr";
      const tracks = Array.from(parent.children)
        .filter((child) => {
          const box = child.getBoundingClientRect();
          const childStyle = getComputedStyle(child);
          return childStyle.display !== "none" && childStyle.visibility !== "hidden" && box.width > 0 && box.height > 0;
        })
        .map((child) => {
          const box = child.getBoundingClientRect();
          const childStyle = getComputedStyle(child);
          return {
            start: direction === "rtl" ? -box.right : box.left,
            end: direction === "rtl" ? -box.left : box.right,
            width: box.width,
            column: gridLine(childStyle.gridColumnStart),
            span: gridSpan(childStyle.gridColumnStart, childStyle.gridColumnEnd),
          };
        })
        .sort((left, right) => left.start - right.start || left.end - right.end || left.width - right.width);
      const singleTrackByColumn = new Map<number, { start: number; end: number; width: number }>();
      for (const track of tracks) {
        if (track.column !== null && track.span === 1 && !singleTrackByColumn.has(track.column)) {
          singleTrackByColumn.set(track.column, track);
        }
      }
      const measuredTracks = singleTrackByColumn.size > 0
        ? [...singleTrackByColumn.entries()].sort(([left], [right]) => left - right).map(([, track]) => track)
        : tracks.filter((track, index, all) => {
          const previous = all[index - 1];
          return previous === undefined || track.start !== previous.start || track.end !== previous.end;
        });
      const value = {
        count: measuredTracks.length,
        widths: measuredTracks.map((track) => track.width),
        gaps: measuredTracks.slice(1).map((track, index) => {
          const previous = measuredTracks[index];
          if (previous === undefined) throw new Error("measured grid track order is corrupt");
          return track.start - previous.end;
        }),
      };
      gridTopologyByParent.set(parent, value);
      return value;
    };
    const nodes = Array.from(document.querySelectorAll("*")).map((element) => {
      const style = getComputedStyle(element);
      const box = element.getBoundingClientRect();
      const visible = style.display !== "none" && style.visibility !== "hidden" && style.opacity !== "0" && box.width > 0 && box.height > 0;
      const parent = element.parentElement;
      const parentStyle = parent === null ? null : getComputedStyle(parent);
      const gridTopology = parent !== null && parentStyle?.display === "grid"
        ? measuredGridTopology(parent, parentStyle)
        : null;
      const matrix = style.transform === "none" ? null : Array.from(new DOMMatrixReadOnly(style.transform).toFloat64Array());
      const transformed = matrix !== null && !(matrix[1] === 0 && matrix[4] === 0);
      const range = document.createRange();
      range.selectNodeContents(element);
      const lineRects = Array.from(range.getClientRects()).filter((line) => line.width > 0 && line.height > 0);
      const intrinsic = element instanceof HTMLImageElement && element.naturalWidth > 0 && element.naturalHeight > 0 ? element.naturalWidth / element.naturalHeight : null;
      const svgRoot = element.closest("svg");
      return {
        identity: identity(element),
        structuralSignature: structuralSignature(element),
        componentIdentity: element.getAttribute("data-component"),
        stateSignature: `${element.getAttribute("data-state") ?? ""}|${element.getAttribute("aria-expanded") ?? ""}|${element.getAttribute("aria-selected") ?? ""}`,
        parent: parent === null ? null : identity(parent),
        containingBlock: parent === null ? null : identity(parent),
        compositeAncestor: compositeIdentity(element),
        svgRoot: svgRoot === null ? null : identity(svgRoot),
        borderBox: rect(box),
        contentBox: contentBox(box, style),
        childUnionBox: childUnion(element),
        visibility: { display: style.display, visibility: style.visibility, opacity: cssNumber(style.opacity), visible, zeroArea: box.width === 0 || box.height === 0 },
        position: style.position,
        viewportPinned: style.position === "fixed" || style.position === "sticky",
        direction: style.direction === "rtl" ? "rtl" as const : "ltr" as const,
        writingMode: style.writingMode,
        transform: { css: style.transform, matrix, axisAligned: !transformed, normalized: style.transform === "none" },
        borderWidths: { top: cssNumber(style.borderTopWidth), right: cssNumber(style.borderRightWidth), bottom: cssNumber(style.borderBottomWidth), left: cssNumber(style.borderLeftWidth) },
        borderRadii: { topLeft: parseRadius(style.borderTopLeftRadius), topRight: parseRadius(style.borderTopRightRadius), bottomRight: parseRadius(style.borderBottomRightRadius), bottomLeft: parseRadius(style.borderBottomLeftRadius) },
        flexGridTopology: {
          kind: parentStyle?.display === "grid" ? "grid" as const : parentStyle?.display === "flex" ? "flex" as const : "none" as const,
          flexDirection: parentStyle?.display === "flex" ? parentStyle.flexDirection : null,
          flexWrap: parentStyle?.display === "flex" ? parentStyle.flexWrap : null,
          flexLine: flexLine(element, parentStyle ?? style),
          flexOrder: parentStyle?.display === "flex" ? cssNumber(style.order) : null,
          gridRow: parentStyle?.display === "grid" ? gridLine(style.gridRowStart) : null,
          gridColumn: parentStyle?.display === "grid" ? gridLine(style.gridColumnStart) : null,
          gridRowSpan: parentStyle?.display === "grid" ? gridSpan(style.gridRowStart, style.gridRowEnd) : null,
          gridColumnSpan: parentStyle?.display === "grid" ? gridSpan(style.gridColumnStart, style.gridColumnEnd) : null,
          gridTrackCount: gridTopology?.count ?? null,
          gridTrackWidths: gridTopology?.widths ?? [],
          gridTrackGaps: gridTopology?.gaps ?? [],
        },
        scrollContainerState: { isScrollContainer: style.overflowX !== "visible" || style.overflowY !== "visible", overflowX: style.overflowX, overflowY: style.overflowY, scrollX: element.scrollLeft, scrollY: element.scrollTop, scrollWidth: element.scrollWidth, scrollHeight: element.scrollHeight, clientWidth: element.clientWidth, clientHeight: element.clientHeight },
        textLineRects: lineRects.map((line, lineIndex) => ({ lineIndex, rect: rect(line), baseline: line.bottom })),
        intrinsicAspectRatio: intrinsic,
      };
    });
    return {
      viewport: { width: document.documentElement.clientWidth, height: document.documentElement.clientHeight, clientWidth: document.documentElement.clientWidth, clientHeight: document.documentElement.clientHeight, deviceScaleFactor: window.devicePixelRatio, scrollX: window.scrollX, scrollY: window.scrollY },
      nodes,
    };
  });

  const first = await sample();
  const second = await sample();
  if (first.viewport.scrollX !== 0 || first.viewport.scrollY !== 0 || second.viewport.scrollX !== 0 || second.viewport.scrollY !== 0) {
    throw new Error("measured layout capture moved away from scroll origin");
  }
  const samplingRequests = paintedRegionSamplingRequests(first);
  const interveningPaintedNodeIdentities = await page.evaluate((requests) => {
    const identity = (element: Element): string => {
      if (element.id.length > 0) return `#${element.id}`;
      if (element === document.documentElement) return "html:root";
      const parts: string[] = [];
      let current: Element | null = element;
      while (current !== null && current !== document.documentElement) {
        const siblingIndex = Array.from(current.parentElement?.children ?? []).indexOf(current) + 1;
        parts.push(`${current.tagName.toLowerCase()}:nth-child(${String(siblingIndex)})`);
        current = current.parentElement;
      }
      return parts.reverse().join(">");
    };
    const elementsByIdentity = new Map(
      Array.from(document.querySelectorAll("*")).map((element) => [identity(element), element]),
    );
    const evidence: Record<string, string[]> = {};
    for (const request of requests) {
      const source = elementsByIdentity.get(request.source);
      const target = elementsByIdentity.get(request.target);
      const allPointsInViewport = request.points.every((point) =>
        point.x >= 0
        && point.y >= 0
        && point.x < document.documentElement.clientWidth
        && point.y < document.documentElement.clientHeight,
      );
      if (source === undefined || target === undefined || !allPointsInViewport) continue;
      const painted = request.points.flatMap((point) => document.elementsFromPoint(point.x, point.y))
        .filter((element) =>
          element !== source
          && element !== target
          && !element.contains(source)
          && !element.contains(target)
          && !source.contains(element)
          && !target.contains(element),
        )
        .map(identity);
      evidence[request.key] = [...new Set(painted)].sort();
    }
    return evidence;
  }, samplingRequests);
  const firstVisible = { ...first, nodes: visibleNodesInCaptureOrder(first.nodes) };
  const secondVisible = { ...second, nodes: visibleNodesInCaptureOrder(second.nodes) };
  return {
    measuredLayoutGraph: buildMeasuredLayoutGraph({ cellId: cell.id, ...firstVisible, interveningPaintedNodeIdentities }),
    jitterEnvelope: jitterEnvelope(firstVisible, secondVisible),
    settledState,
  };
}