import { sha256Canonical } from "../../schema/src/canonical.js";
import {
  MATRIX_CELL_VERSION,
  MATRIX_CELL_V1_VERSION,
  type MatrixCell,
  type JourneyRef,
} from "../../schema/src/records/context.js";
import type { CreationSource } from "../../schema/src/records/envelope.js";
import type { CoverageGap } from "../../universal/src/oracle/witnesses.js";

const DEFAULT_BROWSER_ENGINE = "chromium" as const;
type BrowserEngine = typeof DEFAULT_BROWSER_ENGINE;

const PLANNER_CREATION_SOURCE: CreationSource = {
  runId: "matrix-plan",
  component: "orchestrator",
  componentId: "matrix-planner",
};

const PARAM_SEGMENT = /(^|\/):([a-zA-Z_][a-zA-Z0-9_]*)/g;
const WILDCARD_SEGMENT = /\*/g;

export type RouteFixture = {
  params: Record<string, string>;
  label: string;
};

export type RouteSpec = {
  pattern: string;
  fixtures?: RouteFixture[];
};

export type ViewportSpec = {
  name: string;
  width: number;
  height: number;
};

export type MatrixConfig = {
  routes: RouteSpec[];
  roles: string[];
  locales: string[];
  viewports: ViewportSpec[];
  engine?: BrowserEngine;
  extraDimensions?: Record<string, string[]>;
  generation?: {
    mode: "pairwise" | "full";
    fullCrossProductFor?: string[][];
  };
};

export type MatrixPlanResult = {
  cells: MatrixCell[];
  coverageGaps: CoverageGap[];
};

export function withCellDirection(cell: MatrixCell, direction: string): MatrixCell {
  return { ...cell, state: { ...cell.state, direction } };
}

export type JourneySelectionDeclaration = {
  id: string;
  appliesTo: {
    routes: readonly string[];
    roles?: readonly string[];
    viewports?: readonly string[];
  };
};

type ResolvedRoute = {
  routeId: string;
  url: string;
  pattern: string;
};

type DimensionValue = {
  id: string;
  payload: Record<string, string>;
};

type Dimension = {
  name: string;
  values: DimensionValue[];
};

type DimensionAssignment = Record<string, string>;

function compareUnicodeScalars(left: string, right: string): number {
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    const leftCode = left.codePointAt(leftIndex);
    const rightCode = right.codePointAt(rightIndex);
    if (leftCode === undefined || rightCode === undefined) {
      break;
    }
    if (leftCode !== rightCode) {
      return leftCode < rightCode ? -1 : 1;
    }
    leftIndex += leftCode > 0xffff ? 2 : 1;
    rightIndex += rightCode > 0xffff ? 2 : 1;
  }

  return left.length - right.length;
}

function assertNonEmptyString(value: string, field: string): void {
  if (value.trim().length === 0) {
    throw new Error(`${field} must be a non-empty string`);
  }
}

function assertNonEmptyArray(values: readonly unknown[], field: string): void {
  if (values.length === 0) {
    throw new Error(`${field} must contain at least one value`);
  }
}

function assertPositiveFiniteNumber(value: number, field: string): void {
  if (!Number.isFinite(value) || value <= 0) {
    throw new Error(`${field} must be a positive finite number`);
  }
}

function validateConfig(config: MatrixConfig): void {
  assertNonEmptyArray(config.routes, "routes");
  assertNonEmptyArray(config.roles, "roles");
  assertNonEmptyArray(config.locales, "locales");
  assertNonEmptyArray(config.viewports, "viewports");

  for (const role of config.roles) {
    assertNonEmptyString(role, "roles[]");
  }
  for (const locale of config.locales) {
    assertNonEmptyString(locale, "locales[]");
  }
  for (const [index, viewport] of config.viewports.entries()) {
    assertNonEmptyString(viewport.name, `viewports[${String(index)}].name`);
    assertPositiveFiniteNumber(viewport.width, `viewports[${String(index)}].width`);
    assertPositiveFiniteNumber(viewport.height, `viewports[${String(index)}].height`);
  }

  if (config.extraDimensions !== undefined) {
    for (const [name, values] of Object.entries(config.extraDimensions)) {
      assertNonEmptyString(name, "extraDimensions key");
      assertNonEmptyArray(values, `extraDimensions.${name}`);
      for (const value of values) {
        assertNonEmptyString(value, `extraDimensions.${name}[]`);
      }
    }
  }
}

function validateJourneyDeclarations(
  journeys: readonly JourneySelectionDeclaration[],
): void {
  const ids = new Set<string>();
  for (const journey of journeys) {
    assertNonEmptyString(journey.id, "journeys[].id");
    if (ids.has(journey.id)) {
      throw new Error(`duplicate journey id: ${journey.id}`);
    }
    ids.add(journey.id);

    assertNonEmptyArray(journey.appliesTo.routes, "journeys[].appliesTo.routes");
    for (const route of journey.appliesTo.routes) {
      assertNonEmptyString(route, "journeys[].appliesTo.routes[]");
    }
    for (const role of journey.appliesTo.roles ?? []) {
      assertNonEmptyString(role, "journeys[].appliesTo.roles[]");
    }
    for (const viewport of journey.appliesTo.viewports ?? []) {
      assertNonEmptyString(viewport, "journeys[].appliesTo.viewports[]");
    }
  }
}

function validateJourneyViewportNames(
  journeys: readonly JourneySelectionDeclaration[],
  configuredViewports: readonly ViewportSpec[],
): void {
  const configured = new Set(configuredViewports.map((viewport) => viewport.name));
  for (const journey of journeys) {
    for (const viewport of journey.appliesTo.viewports ?? []) {
      if (!configured.has(viewport)) {
        throw new Error(`unknown viewport in journey declaration: ${viewport}`);
      }
    }
  }
}

function isDynamicPattern(pattern: string): boolean {
  PARAM_SEGMENT.lastIndex = 0;
  WILDCARD_SEGMENT.lastIndex = 0;
  return PARAM_SEGMENT.test(pattern) || WILDCARD_SEGMENT.test(pattern);
}

function listDynamicSegments(pattern: string): string[] {
  const segments: string[] = [];
  for (const match of pattern.matchAll(/(^|\/):([a-zA-Z_][a-zA-Z0-9_]*)/g)) {
    const paramName = match[2];
    if (paramName !== undefined) {
      segments.push(paramName);
    }
  }
  if (pattern.includes("*")) {
    segments.push("*");
  }
  return segments;
}

function unresolvedRouteGap(pattern: string): CoverageGap {
  return {
    reason: "unproven-precondition",
    witnessKind: "precondition",
    failedPrecondition: `route-fixture:${pattern}`,
  };
}

function requireParam(params: Record<string, string>, key: string): string {
  const value = params[key];
  if (value === undefined || value.trim().length === 0) {
    throw new Error(`fixture params missing required route segment "${key}"`);
  }
  return value;
}

function resolveRouteUrl(pattern: string, params: Record<string, string>): string {
  const required = listDynamicSegments(pattern);
  for (const segment of required) {
    requireParam(params, segment);
  }

  let resolved = pattern;
  resolved = resolved.replace(
    /(^|\/):([a-zA-Z_][a-zA-Z0-9_]*)/g,
    (_match, prefix, name: string) => `${String(prefix)}${requireParam(params, name)}`,
  );
  if (pattern.includes("*")) {
    resolved = resolved.replace(/\*/g, () => requireParam(params, "*"));
  }

  if (isDynamicPattern(resolved)) {
    throw new Error(`route resolution left unresolved segments in "${resolved}"`);
  }

  return resolved;
}

function routeIdFor(pattern: string, fixtureLabel?: string): string {
  return sha256Canonical(
    fixtureLabel === undefined
      ? { kind: "route", pattern }
      : { kind: "route", pattern, fixtureLabel },
  );
}

function resolveRoutes(routes: RouteSpec[]): {
  resolved: ResolvedRoute[];
  coverageGaps: CoverageGap[];
} {
  const resolved: ResolvedRoute[] = [];
  const coverageGaps: CoverageGap[] = [];

  for (const route of routes) {
    assertNonEmptyString(route.pattern, "routes[].pattern");

    if (!isDynamicPattern(route.pattern)) {
      resolved.push({
        routeId: routeIdFor(route.pattern),
        url: route.pattern,
        pattern: route.pattern,
      });
      continue;
    }

    if (route.fixtures === undefined || route.fixtures.length === 0) {
      coverageGaps.push(unresolvedRouteGap(route.pattern));
      continue;
    }

    for (const fixture of route.fixtures) {
      assertNonEmptyString(fixture.label, "fixtures[].label");
      const url = resolveRouteUrl(route.pattern, fixture.params);
      resolved.push({
        routeId: routeIdFor(route.pattern, fixture.label),
        url,
        pattern: route.pattern,
      });
    }
  }

  coverageGaps.sort((left, right) => {
    if (left.reason !== right.reason) {
      return compareUnicodeScalars(left.reason, right.reason);
    }
    if (
      left.reason === "unproven-precondition" &&
      right.reason === "unproven-precondition"
    ) {
      return compareUnicodeScalars(
        left.failedPrecondition,
        right.failedPrecondition,
      );
    }
    return 0;
  });

  resolved.sort((left, right) => compareUnicodeScalars(left.routeId, right.routeId));

  return { resolved, coverageGaps };
}

function buildDimensions(
  config: MatrixConfig,
  routes: ResolvedRoute[],
): Dimension[] {
  const engine = config.engine ?? DEFAULT_BROWSER_ENGINE;
  const dimensions: Dimension[] = [
    {
      name: "route",
      values: routes.map((route) => ({
        id: route.routeId,
        payload: {
          routeId: route.routeId,
          url: route.url,
          pattern: route.pattern,
        },
      })),
    },
    {
      name: "role",
      values: config.roles.map((role) => ({ id: role, payload: { role } })),
    },
    {
      name: "locale",
      values: config.locales.map((locale) => ({ id: locale, payload: { locale } })),
    },
    {
      name: "viewport",
      values: config.viewports.map((viewport) => ({
        id: `${String(viewport.width)}x${String(viewport.height)}`,
        payload: {
          viewportName: viewport.name,
          viewportWidth: String(viewport.width),
          viewportHeight: String(viewport.height),
        },
      })),
    },
    {
      name: "engine",
      values: [{ id: engine, payload: { engine } }],
    },
  ];

  if (config.extraDimensions !== undefined) {
    for (const name of Object.keys(config.extraDimensions).sort(compareUnicodeScalars)) {
      const values = config.extraDimensions[name];
      if (values === undefined) {
        continue;
      }
      dimensions.push({
        name,
        values: values.map((value) => ({
          id: value,
          payload: { [name]: value },
        })),
      });
    }
  }

  return dimensions;
}

function pairKey(
  leftDimension: string,
  leftValue: string,
  rightDimension: string,
  rightValue: string,
): string {
  if (leftDimension === rightDimension) {
    return `${leftDimension}\0${leftValue}\0${leftValue}`;
  }
  if (compareUnicodeScalars(leftDimension, rightDimension) <= 0) {
    return `${leftDimension}\0${leftValue}\0${rightDimension}\0${rightValue}`;
  }
  return `${rightDimension}\0${rightValue}\0${leftDimension}\0${leftValue}`;
}

function cartesianAssignments(dimensions: Dimension[]): DimensionAssignment[] {
  if (dimensions.length === 0) {
    return [{}];
  }

  const sorted = [...dimensions].sort((left, right) =>
    compareUnicodeScalars(left.name, right.name),
  );

  let assignments: DimensionAssignment[] = [{}];
  for (const dimension of sorted) {
    const next: DimensionAssignment[] = [];
    for (const assignment of assignments) {
      for (const value of dimension.values) {
        next.push({ ...assignment, [dimension.name]: value.id });
      }
    }
    assignments = next;
  }

  return assignments.sort((left, right) =>
    compareUnicodeScalars(serializeAssignment(left), serializeAssignment(right)),
  );
}

function serializeAssignment(assignment: DimensionAssignment): string {
  return Object.keys(assignment)
    .sort(compareUnicodeScalars)
    .map((name) => `${name}=${assignment[name] ?? ""}`)
    .join("|");
}

function mergeFullCrossGroups(groups: string[][]): string[][] {
  const parent = new Map<string, string>();

  function find(name: string): string {
    const current = parent.get(name);
    if (current === undefined) {
      parent.set(name, name);
      return name;
    }
    if (current !== name) {
      const root = find(current);
      parent.set(name, root);
      return root;
    }
    return name;
  }

  function union(left: string, right: string): void {
    parent.set(find(left), find(right));
  }

  for (const group of groups) {
    if (group.length === 0) {
      continue;
    }
    const [first, ...rest] = group;
    if (first === undefined) {
      continue;
    }
    for (const name of rest) {
      union(first, name);
    }
  }

  const grouped = new Map<string, string[]>();
  for (const name of parent.keys()) {
    const root = find(name);
    const bucket = grouped.get(root) ?? [];
    bucket.push(name);
    grouped.set(root, bucket);
  }

  return [...grouped.values()]
    .map((group) => group.sort(compareUnicodeScalars))
    .filter((group) => group.length > 0)
    .sort((left, right) => compareUnicodeScalars(left.join("\0"), right.join("\0")));
}

function buildCompositeDimension(
  dimensionNames: string[],
  dimensionsByName: Map<string, Dimension>,
): Dimension {
  const members = dimensionNames.map((name) => {
    const dimension = dimensionsByName.get(name);
    if (dimension === undefined) {
      throw new Error(`unknown dimension in fullCrossProductFor: ${name}`);
    }
    return dimension;
  });

  const values: DimensionValue[] = [];
  for (const assignment of cartesianAssignments(members)) {
    const payload: Record<string, string> = {};
    const idParts: string[] = [];
    for (const name of dimensionNames) {
      const member = dimensionsByName.get(name);
      if (member === undefined) {
        throw new Error(`missing composite value for dimension ${name}`);
      }
      const valueId = assignment[name];
      if (valueId === undefined) {
        throw new Error(`missing composite assignment for dimension ${name}`);
      }
      const value = member.values.find((entry) => entry.id === valueId);
      if (value === undefined) {
        throw new Error(`missing composite value for dimension ${name}`);
      }
      idParts.push(`${name}=${value.id}`);
      Object.assign(payload, value.payload);
    }
    values.push({
      id: idParts.join("|"),
      payload,
    });
  }

  return {
    name: dimensionNames.join("+"),
    values,
  };
}

function applyFullCrossProductFor(
  dimensions: Dimension[],
  fullCrossProductFor: string[][] | undefined,
): Dimension[] {
  if (fullCrossProductFor === undefined || fullCrossProductFor.length === 0) {
    return dimensions;
  }

  const dimensionsByName = new Map(dimensions.map((dimension) => [dimension.name, dimension]));
  for (const group of fullCrossProductFor) {
    for (const name of group) {
      if (!dimensionsByName.has(name)) {
        throw new Error(`unknown dimension in fullCrossProductFor: ${name}`);
      }
    }
  }

  const mergedGroups = mergeFullCrossGroups(fullCrossProductFor).filter(
    (group) => group.length > 1,
  );
  if (mergedGroups.length === 0) {
    return dimensions;
  }

  const consumed = new Set<string>();
  const composites: Dimension[] = [];
  for (const group of mergedGroups) {
    composites.push(buildCompositeDimension(group, dimensionsByName));
    for (const name of group) {
      consumed.add(name);
    }
  }

  const remaining = dimensions.filter((dimension) => !consumed.has(dimension.name));
  return [...remaining, ...composites].sort((left, right) =>
    compareUnicodeScalars(left.name, right.name),
  );
}

function uncoveredPairsForDimension(
  assignments: DimensionAssignment[],
  dimension: Dimension,
  priorDimensions: Dimension[],
): Set<string> {
  const uncovered = new Set<string>();
  for (const prior of priorDimensions) {
    for (const priorValue of prior.values) {
      for (const value of dimension.values) {
        uncovered.add(pairKey(prior.name, priorValue.id, dimension.name, value.id));
      }
    }
  }

  for (const assignment of assignments) {
    for (const prior of priorDimensions) {
      const priorValue = assignment[prior.name];
      const dimensionValue = assignment[dimension.name];
      if (priorValue === undefined || dimensionValue === undefined) {
        continue;
      }
      uncovered.delete(pairKey(prior.name, priorValue, dimension.name, dimensionValue));
    }
  }

  return uncovered;
}

function firstDimensionValue(dimension: Dimension): DimensionValue {
  const value = dimension.values[0];
  if (value === undefined) {
    throw new Error(`dimension ${dimension.name} must contain at least one value`);
  }
  return value;
}

function fillAssignment(
  seed: DimensionAssignment,
  dimensions: Dimension[],
  overrides: DimensionAssignment,
): DimensionAssignment {
  const assignment: DimensionAssignment = { ...seed };
  for (const dimension of dimensions) {
    const override = overrides[dimension.name];
    if (override !== undefined) {
      assignment[dimension.name] = override;
      continue;
    }
    if (assignment[dimension.name] === undefined) {
      assignment[dimension.name] = firstDimensionValue(dimension).id;
    }
  }
  return assignment;
}

function generatePairwise(dimensions: Dimension[]): DimensionAssignment[] {
  if (dimensions.length === 0) {
    return [{}];
  }

  const sorted = [...dimensions].sort((left, right) =>
    compareUnicodeScalars(left.name, right.name),
  );

  if (sorted.length === 1) {
    const only = sorted[0];
    if (only === undefined) {
      return [{}];
    }
    return only.values.map((value) => ({ [only.name]: value.id }));
  }

  const [first, second, ...rest] = sorted;
  if (first === undefined || second === undefined) {
    return [{}];
  }

  let assignments: DimensionAssignment[] = [];
  for (const firstValue of first.values) {
    for (const secondValue of second.values) {
      assignments.push({
        [first.name]: firstValue.id,
        [second.name]: secondValue.id,
      });
    }
  }

  const processed: Dimension[] = [first, second];
  for (const dimension of rest) {
    assignments = assignments.map((assignment, index) => {
      const rotated = dimension.values[index % dimension.values.length];
      if (rotated === undefined) {
        throw new Error(`dimension ${dimension.name} must contain at least one value`);
      }
      return {
        ...assignment,
        [dimension.name]: rotated.id,
      };
    });

    let uncovered = uncoveredPairsForDimension(assignments, dimension, processed);
    const sortedUncovered = [...uncovered].sort(compareUnicodeScalars);
    for (const key of sortedUncovered) {
      const parts = key.split("\0");
      const leftDimension = parts[0];
      const leftValue = parts[1];
      if (leftDimension === undefined || leftValue === undefined) {
        continue;
      }
      const rightDimension = parts[2] ?? leftDimension;
      const rightValue = parts[3] ?? leftValue;
      const overrides: DimensionAssignment =
        leftDimension === dimension.name
          ? { [leftDimension]: leftValue, [rightDimension]: rightValue }
          : { [rightDimension]: rightValue, [leftDimension]: leftValue };

      const seed = assignments[0] ?? {};
      assignments.push(fillAssignment(seed, sorted, overrides));
      uncovered = uncoveredPairsForDimension(assignments, dimension, processed);
    }

    processed.push(dimension);
  }

  const unique = new Map<string, DimensionAssignment>();
  for (const assignment of assignments) {
    unique.set(serializeAssignment(assignment), assignment);
  }

  return [...unique.values()].sort((left, right) =>
    compareUnicodeScalars(serializeAssignment(left), serializeAssignment(right)),
  );
}

function generateAssignments(
  dimensions: Dimension[],
  mode: "pairwise" | "full",
): DimensionAssignment[] {
  if (mode === "full") {
    return cartesianAssignments(dimensions);
  }
  return generatePairwise(dimensions);
}

function cellIdentityPayload(input: {
  routeId: string;
  role: string;
  locale: string;
  viewport: { width: number; height: number; deviceScaleFactor: number };
  engine: string;
  state: Record<string, string>;
  journeys?: JourneyRef[];
}): Record<string, unknown> {
  const stateEntries = Object.keys(input.state)
    .sort(compareUnicodeScalars)
    .flatMap((key) => {
      const value = input.state[key];
      return value === undefined ? [] : ([[key, value]] as const);
    });

  return {
    routeId: input.routeId,
    role: input.role,
    locale: input.locale,
    viewport: input.viewport,
    engine: input.engine,
    state: Object.fromEntries(stateEntries),
    ...(input.journeys === undefined ? {} : { journeys: input.journeys }),
  };
}

function selectJourneyRefs(
  pattern: string,
  role: string,
  viewportName: string,
  journeys: readonly JourneySelectionDeclaration[],
): JourneyRef[] {
  return journeys.flatMap((journey) => {
    if (!journey.appliesTo.routes.includes(pattern)) {
      return [];
    }
    if (journey.appliesTo.roles !== undefined && !journey.appliesTo.roles.includes(role)) {
      return [];
    }
    if (
      journey.appliesTo.viewports !== undefined &&
      !journey.appliesTo.viewports.includes(viewportName)
    ) {
      return [];
    }
    return [{ id: journey.id }];
  });
}

function assignmentValue(
  assignment: DimensionAssignment,
  dimensions: Dimension[],
  name: string,
): string | undefined {
  if (assignment[name] !== undefined) {
    return assignment[name];
  }

  for (const dimension of dimensions) {
    if (!dimension.name.includes("+")) {
      continue;
    }
    const compositeValueId = assignment[dimension.name];
    if (compositeValueId === undefined) {
      continue;
    }
    const compositeValue = dimension.values.find((value) => value.id === compositeValueId);
    const payloadValue = compositeValue?.payload[name];
    if (payloadValue !== undefined) {
      return payloadValue;
    }
  }

  return undefined;
}

function buildCell(
  assignment: DimensionAssignment,
  dimensionsByName: Map<string, Dimension>,
  planningDimensions: Dimension[],
  journeys: readonly JourneySelectionDeclaration[],
): MatrixCell {
  const routeDimension = dimensionsByName.get("route");
  if (routeDimension === undefined) {
    throw new Error("route dimension is required");
  }

  const routeValueId = assignment.route;
  if (routeValueId === undefined) {
    throw new Error("assignment missing route dimension");
  }
  const routeValue = routeDimension.values.find((value) => value.id === routeValueId);
  if (routeValue === undefined) {
    throw new Error(`unknown route assignment: ${routeValueId}`);
  }

  const role = assignmentValue(assignment, planningDimensions, "role");
  const locale = assignmentValue(assignment, planningDimensions, "locale");
  const viewportAssignment = assignmentValue(assignment, planningDimensions, "viewport");
  const engineAssignment = assignmentValue(assignment, planningDimensions, "engine");
  if (role === undefined || locale === undefined || viewportAssignment === undefined) {
    throw new Error("assignment missing required browser dimensions");
  }

  const viewportDimension = dimensionsByName.get("viewport");
  if (viewportDimension === undefined) {
    throw new Error("viewport dimension is required");
  }
  const viewportValue = viewportDimension.values.find(
    (value) => value.id === viewportAssignment,
  );
  if (viewportValue === undefined) {
    throw new Error(`unknown viewport assignment: ${viewportAssignment}`);
  }

  const engine = engineAssignment ?? DEFAULT_BROWSER_ENGINE;

  const state: Record<string, string> = { engine };
  for (const [name, dimension] of dimensionsByName.entries()) {
    if (
      name === "route" ||
      name === "role" ||
      name === "locale" ||
      name === "viewport" ||
      name === "engine"
    ) {
      continue;
    }
    const valueId = assignment[name];
    if (valueId === undefined) {
      continue;
    }
    const value = dimension.values.find((entry) => entry.id === valueId);
    if (value === undefined) {
      throw new Error(`unknown assignment for dimension ${name}: ${valueId}`);
    }
    for (const [key, payloadValue] of Object.entries(value.payload)) {
      if (key === "routeId" || key === "url" || key === "pattern") {
        continue;
      }
      if (
        key === "viewportName" ||
        key === "viewportWidth" ||
        key === "viewportHeight"
      ) {
        continue;
      }
      state[key] = payloadValue;
    }
  }

  for (const dimension of planningDimensions) {
    if (!dimension.name.includes("+")) {
      continue;
    }
    const compositeValueId = assignment[dimension.name];
    if (compositeValueId === undefined) {
      continue;
    }
    const compositeValue = dimension.values.find((value) => value.id === compositeValueId);
    if (compositeValue === undefined) {
      continue;
    }
    for (const [key, payloadValue] of Object.entries(compositeValue.payload)) {
      if (
        key === "routeId" ||
        key === "url" ||
        key === "pattern" ||
        key === "viewportName" ||
        key === "viewportWidth" ||
        key === "viewportHeight" ||
        key === "role" ||
        key === "locale" ||
        key === "engine"
      ) {
        continue;
      }
      state[key] = payloadValue;
    }
  }

  const viewport = {
    width: Number(viewportValue.payload.viewportWidth),
    height: Number(viewportValue.payload.viewportHeight),
    deviceScaleFactor: 1,
  };

  const routeId = routeValue.payload.routeId;
  const url = routeValue.payload.url;
  const pattern = routeValue.payload.pattern;
  if (routeId === undefined || url === undefined || pattern === undefined) {
    throw new Error("resolved route payload is incomplete");
  }

  const viewportName = viewportValue.payload.viewportName;
  if (viewportName === undefined) {
    throw new Error("viewport payload missing viewportName");
  }

  const journeyRefs = selectJourneyRefs(pattern, role, viewportName, journeys);

  const identity = cellIdentityPayload({
    routeId,
    role,
    locale,
    viewport,
    engine,
    state,
    ...(journeyRefs.length === 0 ? {} : { journeys: journeyRefs }),
  });

  const cell = {
    id: sha256Canonical({ kind: "matrix-cell", ...identity }),
    creationSource: PLANNER_CREATION_SOURCE,
    routeId,
    route: pattern,
    url,
    role,
    locale,
    viewport,
    state,
    actions: [],
    seed: "",
  };

  if (journeyRefs.length === 0) {
    return { ...cell, schemaVersion: MATRIX_CELL_V1_VERSION };
  }
  return { ...cell, schemaVersion: MATRIX_CELL_VERSION, journeys: journeyRefs };
}

function preserveJourneyViewportCoverage(
  cells: MatrixCell[],
  viewports: readonly ViewportSpec[],
  journeys: readonly JourneySelectionDeclaration[],
  routePatterns: ReadonlyMap<string, string>,
): MatrixCell[] {
  const complete = new Map(cells.map((cell) => [cell.id, cell]));

  for (const cell of cells) {
    const pattern = routePatterns.get(cell.routeId);
    if (pattern === undefined) {
      continue;
    }

    for (const viewport of viewports) {
      const journeyRefs = selectJourneyRefs(pattern, cell.role, viewport.name, journeys);
      if (journeyRefs.length === 0) {
        continue;
      }

      const nextViewport = { width: viewport.width, height: viewport.height, deviceScaleFactor: 1 };
      const identity = cellIdentityPayload({
        routeId: cell.routeId,
        role: cell.role,
        locale: cell.locale,
        viewport: nextViewport,
        engine: cell.state.engine ?? DEFAULT_BROWSER_ENGINE,
        state: cell.state,
        journeys: journeyRefs,
      });
      const id = sha256Canonical({ kind: "matrix-cell", ...identity });
      if (complete.has(id)) {
        continue;
      }
      complete.set(id, {
        ...cell,
        id,
        viewport: nextViewport,
        schemaVersion: MATRIX_CELL_VERSION,
        journeys: journeyRefs,
      });
    }
  }

  return [...complete.values()];
}

export function planMatrix(
  config: MatrixConfig,
  journeys: readonly JourneySelectionDeclaration[] = [],
): MatrixPlanResult {
  validateConfig(config);
  validateJourneyDeclarations(journeys);
  validateJourneyViewportNames(journeys, config.viewports);

  const { resolved, coverageGaps } = resolveRoutes(config.routes);
  if (resolved.length === 0) {
    return { cells: [], coverageGaps };
  }

  const baseDimensions = buildDimensions(config, resolved);
  const dimensions = applyFullCrossProductFor(
    baseDimensions,
    config.generation?.fullCrossProductFor,
  );
  const mode = config.generation?.mode ?? "pairwise";
  const assignments = generateAssignments(dimensions, mode);
  const dimensionsByName = new Map(baseDimensions.map((dimension) => [dimension.name, dimension]));

  const routePatterns = new Map(resolved.map((route) => [route.routeId, route.pattern]));
  const cells = preserveJourneyViewportCoverage(
    assignments.map((assignment) => buildCell(assignment, dimensionsByName, dimensions, journeys)),
    config.viewports,
    journeys,
    routePatterns,
  )
    .sort((left, right) => compareUnicodeScalars(left.id, right.id));

  return { cells, coverageGaps };
}