/**
 * vector-cortex/prompt-dag/validator.ts — stable Kahn topological order + DAG
 * digest (VC5A, task 2).
 *
 * The validator owns the ONE authoritative sequence a prompt is rendered in.
 * Determinism is the whole point: the same DAG must yield byte-identical order
 * across runs, platforms and input permutations, so the zero-indegree frontier
 * is drained by an explicit sort key, NEVER by map/object iteration order
 * (CONTRACTS §PromptDagV1):
 *
 *   key = (span.startSeq ?? MAX, syntheticOrdinal ?? 0, id bytes)
 *
 * Only ORDERING edges (`precedes`, `depends`, `tool-pair`) constrain the sort.
 * A `contradicts` edge is an exclusivity relation, not an ordering one: treating
 * it as an ordering constraint would manufacture phantom cycles between two
 * mutually exclusive claims that are never co-selected anyway.
 *
 * Rejections owned here:
 *   - `DAG_CYCLE`             — Kahn drains fewer nodes than exist;
 *   - `DAG_REVERSED_PRECEDES` — a `precedes` edge pointing backward against
 *                               source order (the source stream is the truth;
 *                               a backward claim is a corrupt edge).
 *
 * Pure/deterministic: no storage, no console, no network (PREVENT-PI-004).
 */

import { createHash } from "node:crypto";

import type {
  DagEdge,
  DagFailureCode,
  DagNode,
  DagValidation,
  PromptDagV1,
} from "./types.js";

/** Edge kinds that impose an ORDER. `contradicts` is exclusivity, not order. */
const ORDERING_KINDS: ReadonlySet<DagEdge["kind"]> = new Set([
  "precedes",
  "depends",
  "tool-pair",
]);

/**
 * The Kahn queue sort key. Spanned nodes order by `startSeq`; synthetics have no
 * span and sort AFTER every spanned node (hence the MAX sentinel), then by
 * `syntheticOrdinal`, then by id bytes for a total order.
 */
function queueKeyCompare(a: DagNode, b: DagNode): number {
  const aSeq = a.span?.startSeq;
  const bSeq = b.span?.startSeq;
  if (aSeq !== undefined && bSeq !== undefined) {
    if (aSeq !== bSeq) return aSeq < bSeq ? -1 : 1;
  } else if (aSeq !== undefined) {
    return -1; // spanned nodes precede synthetics (which have no seq)
  } else if (bSeq !== undefined) {
    return 1;
  }
  // Contract key: (startSeq, syntheticOrdinal, id bytes) — byte OFFSET is NOT a
  // tie-break, so two equal-seq nodes resolve purely by id bytes.
  const aOrd = a.syntheticOrdinal ?? 0;
  const bOrd = b.syntheticOrdinal ?? 0;
  if (aOrd !== bOrd) return aOrd < bOrd ? -1 : 1;
  return a.id < b.id ? -1 : a.id > b.id ? 1 : 0;
}

/** Whether `from` precedes `to` in SOURCE order (used for reversed-precedes). */
function isSourceBackward(from: DagNode, to: DagNode): boolean {
  const f = from.span;
  const t = to.span;
  if (f === undefined || t === undefined) return false; // synthetics: no claim
  if (f.startSeq !== t.startSeq) return f.startSeq > t.startSeq;
  return f.startByte > t.startByte;
}

/**
 * Validate a DAG and return its STABLE Kahn topological order (task 2).
 *
 * Kahn with a deterministic frontier: compute indegrees over ordering edges
 * only, seed the frontier with every zero-indegree node sorted by the queue key,
 * then repeatedly take the SMALLEST-key node, emit it, and decrement its
 * successors. Because the frontier is re-sorted on every insertion the emitted
 * order is a pure function of the graph — no iteration-order dependence.
 */
export function validatePromptDag(dag: PromptDagV1): DagValidation {
  const codes: DagFailureCode[] = [];
  const byId = new Map<string, DagNode>();
  for (const n of dag.nodes) byId.set(n.id, n);

  const indegree = new Map<string, number>();
  for (const n of dag.nodes) indegree.set(n.id, 0);
  const successors = new Map<string, string[]>();

  for (const e of dag.edges) {
    if (!ORDERING_KINDS.has(e.kind)) continue;
    const from = byId.get(e.from);
    const to = byId.get(e.to);
    if (from === undefined || to === undefined) {
      if (!codes.includes("DAG_MISSING_ENDPOINT")) codes.push("DAG_MISSING_ENDPOINT");
      continue;
    }
    // A `precedes` edge asserts source order; a backward assertion is corrupt.
    if (e.kind === "precedes" && isSourceBackward(from, to)) {
      if (!codes.includes("DAG_REVERSED_PRECEDES")) codes.push("DAG_REVERSED_PRECEDES");
    }
    const list = successors.get(e.from);
    if (list === undefined) successors.set(e.from, [e.to]);
    else list.push(e.to);
    indegree.set(e.to, (indegree.get(e.to) ?? 0) + 1);
  }

  if (codes.length > 0) return { ok: false, codes };

  // ── Stable Kahn drain ──────────────────────────────────────────────────────
  const frontier: DagNode[] = dag.nodes.filter((n) => (indegree.get(n.id) ?? 0) === 0);
  frontier.sort(queueKeyCompare);

  const order: string[] = [];
  while (frontier.length > 0) {
    const next = frontier.shift();
    if (next === undefined) break;
    order.push(next.id);
    // Successors are drained in sorted id order so equal-key insertions into the
    // frontier are themselves deterministic.
    const succ = [...(successors.get(next.id) ?? [])].sort((a, b) =>
      a < b ? -1 : a > b ? 1 : 0,
    );
    for (const s of succ) {
      const remaining = (indegree.get(s) ?? 0) - 1;
      indegree.set(s, remaining);
      if (remaining !== 0) continue;
      const node = byId.get(s);
      if (node === undefined) continue;
      frontier.push(node);
      frontier.sort(queueKeyCompare);
    }
  }

  // Fewer emitted than present ⇒ at least one node never reached indegree zero.
  if (order.length !== dag.nodes.length) return { ok: false, codes: ["DAG_CYCLE"] };

  return { ok: true, order };
}

/**
 * Deterministic SHA-256 identity of a DAG, binding a plan to the exact structure
 * it was selected over. Hashing covers node ids/kinds/payload digests/spans and
 * every edge, in the DAG's canonical order — so mutating a node's payload or
 * moving an edge changes the digest and invalidates any plan pinned to it.
 *
 * Node TOKEN COUNTS are deliberately NOT part of this digest: they are a planner
 * input, not DAG structure. The plan manifest digest (`planManifestDigest`)
 * covers them instead, which is what makes the acceptance test's post-plan token
 * mutation detectable as `PLN_MANIFEST_DIGEST_MISMATCH`.
 */
export function dagDigest(dag: PromptDagV1): string {
  const h = createHash("sha256");
  h.update(dag.schema);
  h.update(" ");
  h.update(dag.sessionId);
  h.update(" ");
  h.update(String(dag.sourceHighWater));
  for (const n of dag.nodes) {
    h.update("");
    h.update(n.id);
    h.update(" ");
    h.update(n.kind);
    h.update(" ");
    h.update(n.payloadDigest);
    h.update(" ");
    h.update(String(n.syntheticOrdinal ?? 0));
    if (n.span !== undefined) {
      h.update(" ");
      h.update(
        `${n.span.sessionId}:${n.span.startSeq}:${n.span.endSeq}:${n.span.startByte}:${n.span.endByte}:${n.span.digest}`,
      );
    }
    for (const inc of [...n.incompatibleWith].sort()) {
      h.update(" ");
      h.update(inc);
    }
  }
  for (const e of dag.edges) {
    h.update("");
    h.update(`${e.from} ${e.to} ${e.kind}`);
  }
  return h.digest("hex");
}