arah2/routing/test/graph.test.mjs

#!/usr/bin/env node
/*
 * graph.test.mjs — the CSR road-graph binary codec gates (G1–G11).
 * ------------------------------------------------------------------
 * RED first (plan 06-01 task 1): every decode-bearing case fails while
 * routing/src/graph.ts does not exist (lazy-import pattern — each case
 * reports its own ERR_MODULE_NOT_FOUND, the fixture-source.test.mjs style).
 * Re-pinned by Phase 08.1 plan 01 task 2: the layout version bumped to
 * ARG3 — the CH-carrying layout. One decode path, one search path:
 * anything that is not exactly an ARG3 graph decodes to null (the D-01
 * fail-honest family) — the committed mini-graph-arg1.bin / (task 3)
 * mini-graph-arg2.bin files are the standing rejection vectors.
 *
 * The binary layout is PINNED by 06-01 + 08-02 + Phase 08.1 (plans 04/07
 * depend on the base; Phase 11 will download the same bytes):
 * little-endian CSR — header (magic/version/counts/bbox/maxSpeed +
 * chShortcutCount u32 @60, reserved u32 @64/@68) ++ f64 lat ++ lng ++
 * u32 edgeStart[n+1] ++ u32 targets ++ u8 flags ++ f32 seconds ++
 * u32 nameIds ++ u32 nameOffsets[m+1] ++ u8 name pool ++ u32 chRank[n]
 * ++ u32 shortcutStart[n+1] ++ u32 shortcutTarget[S] ++ f32
 * shortcutSeconds[S] ++ u32 shortcutVia[S].
 * The header stays 72 bytes so the f64 node arrays are 8-byte aligned —
 * zero-copy TypedArray views REQUIRE aligned offsets (an unaligned
 * Float64Array constructor throws RangeError in every engine). The CH
 * suffix starts at the first 4-byte boundary after the name pool.
 *
 *   G1  round-trip          — encodeGraph → decodeGraph restores coords,
 *                             targets, flags, weights, names, bbox AND the
 *                             CH fields (rank + shortcut CSR) exactly
 *   G2  bad magic -> null   — T-06-03 fail-honest (0xdeadbeef)
 *   G3  bad version -> null — ARG1 fixture bytes -> null (D-01 one-path
 *                             law); version 1, 2 and 4 tampers -> null
 *                             (the accepted version is 3)
 *   G4  committed fixture   — mini-graph.bin (ARG3) is 25 nodes / 80
 *                             edges / rank 25 / >= 1 shortcut; the frozen
 *                             mini-graph-arg2.bin decodes to null (D-12)
 *   G4  truncated/hostile -> null — byte-length ≠ header-declared size
 *                             (incl. huge-count header on a tiny buffer,
 *                             T-06-03b: size check BEFORE view allocation)
 *   G5  zero-copy views     — the views' .buffer IS the input buffer;
 *                             flipping an input byte flips the decoded view
 *   G6  name pool           — nameAt(0) === "Jalan Mini 1";
 *                             nameAt(UNNAMED_NAME_ID) === undefined
 *   G7  committed fixture   — mini-graph.bin (ARG3, regenerated through
 *                             the ONE encode authority) decodes: 25 nodes,
 *                             80 edges, 3 names, maxSpeed 60, exactly ONE
 *                             oneway flag, a total-order rank, >= 1
 *                             upward shortcut; the frozen ARG2 vector
 *                             decodes to null
 *   G8  exported constants  — GRAPH_MAGIC === 0x41524733, GRAPH_VERSION === 3
 *   G9  table round-trip    — the CH fields restore exactly; the CH arrays
 *                             are zero-copy views over the input buffer
 *   G10 encode validation   — malformed ch input throws NAMED
 *                             encodeGraph: errors (no silent clamp, T-08-04)
 *   G11 decode rejection    — chShortcutCount = 0 -> null even when the
 *                             size matches (an ARG3 with no CH is not a
 *                             road graph — A5); monster chShortcutCount on
 *                             a tiny buffer -> null by arithmetic BEFORE
 *                             allocation (T-08.1-01)
 *
 * Run:  npm run routing:test   (exit 0 = all green)
 */
import { strict as assert } from "node:assert";
import { readFileSync } from "node:fs";
import path from "node:path";
import { fileURLToPath } from "node:url";
import { test } from "./harness.mjs";

const here = path.dirname(fileURLToPath(import.meta.url)); // routing/test

// Lazy module load — missing module => per-case ERR_MODULE_NOT_FOUND (RED).
let graphPromise = null;
function loadGraph() {
  if (!graphPromise) graphPromise = import("../src/graph.ts");
  return graphPromise;
}

/** Decode helper: bytes -> exact ArrayBuffer copy (Buffer pools are larger). */
function toArrayBuffer(buf) {
  return buf.buffer.slice(buf.byteOffset, buf.byteOffset + buf.byteLength);
}

/* ————— synthetic 3-node graph (the round-trip vector) ————— */

/**
 * Hand-built CH block for the 3-node synthetic (rank of length 3,
 * shortcutStart of length 4, ONE shortcut so the round-trip is
 * meaningful). The shortcut 0->2 (via 1) is upward against this rank:
 * rank(from)=1 > rank(via)=0 and rank(to)=2 > 0 — the same law
 * contractGraph guarantees. (contractGraph over the 3 synthetic edges
 * itself emits no shortcut — the 1->2 mirror is bit0-blocked — so the
 * hand block is the codec's round-trip vector, exactly the plan's
 * option B.)
 */
function syntheticCh() {
  return {
    rank: Uint32Array.of(1, 0, 2),
    shortcutStart: Uint32Array.of(0, 1, 1, 1),
    shortcutTarget: Uint32Array.of(2),
    shortcutSeconds: Float32Array.of(12),
    shortcutVia: Uint32Array.of(1),
  };
}

function syntheticInput() {
  return {
    lat: [3.15, 3.1505, 3.151],
    lng: [101.69, 101.6905, 101.691],
    edges: [
      { from: 0, to: 1, seconds: 4, nameId: 0 },
      { from: 1, to: 0, seconds: 4 }, // unnamed (nameId -> UNNAMED_NAME_ID)
      { from: 1, to: 2, seconds: 8, flags: 1, nameId: 1 }, // oneway-reverse marker
    ],
    names: ["Jalan Mini 1", "Jalan Mini 2"],
    maxSpeedKmh: 60,
    // ARG3 CH block (Phase 08.1): REQUIRED — an ARG3 with no CH is not a
    // road graph. Hand-built, upward, one shortcut; see syntheticCh().
    ch: syntheticCh(),
  };
}

/* ————— G1–G8 ————— */

test("G1 round-trip — encodeGraph -> decodeGraph restores coords, targets, flags, weights, names, bbox, and the CH tables exactly", async () => {
  const { encodeGraph, decodeGraph } = await loadGraph();
  const input = syntheticInput();
  const ch = input.ch;
  const buf = encodeGraph(input);
  assert.ok(buf instanceof ArrayBuffer, "encodeGraph returns an ArrayBuffer");
  const g = decodeGraph(buf);
  assert.ok(g, "a well-formed buffer decodes non-null");
  assert.equal(g.nodeCount, 3);
  assert.equal(g.edgeCount, 3);
  assert.equal(g.nameCount, 2);
  assert.deepEqual([...g.lat], input.lat, "lat round-trips exactly (f64)");
  assert.deepEqual([...g.lng], input.lng, "lng round-trips exactly (f64)");
  // edges grouped by `from` ascending: node0 -> [e0], node1 -> [e1, e2], node2 -> []
  assert.deepEqual([...g.edgeStart], [0, 1, 3, 3], "CSR row pointers");
  assert.deepEqual([...g.edgeTarget], [1, 0, 2], "edge targets round-trip");
  assert.deepEqual([...g.edgeFlags], [0, 0, 1], "flags round-trip (bit0 oneway-reverse)");
  assert.deepEqual([...g.edgeSeconds], [4, 4, 8], "weights round-trip (f32)");
  assert.deepEqual([...g.edgeNameId], [0, 0xffffffff, 1], "name ids round-trip (unnamed sentinel)");
  assert.deepEqual(
    g.bbox,
    { minLat: 3.15, minLng: 101.69, maxLat: 3.151, maxLng: 101.691 },
    "bbox derived from the nodes at encode time",
  );
  assert.equal(g.maxSpeedKmh, 60);
  // ARG3 CH fields round-trip (task 2's re-pin).
  assert.equal(g.chShortcutCount, 1, "the header carries the shortcut count");
  assert.equal(g.chRank.length, 3, "chRank length equals nodeCount");
  assert.equal(g.shortcutStart.length, 4, "shortcutStart length equals nodeCount + 1");
  assert.equal(g.shortcutTarget.length, g.chShortcutCount, "target length equals chShortcutCount");
  assert.equal(g.shortcutSeconds.length, g.chShortcutCount, "seconds length equals chShortcutCount");
  assert.equal(g.shortcutVia.length, g.chShortcutCount, "via length equals chShortcutCount");
  assert.deepEqual([...g.chRank], [...ch.rank], "rank values match the input exactly");
  assert.deepEqual([...g.shortcutTarget], [...ch.shortcutTarget], "shortcut targets match");
  assert.deepEqual([...g.shortcutSeconds], [...ch.shortcutSeconds], "shortcut seconds match");
  assert.deepEqual([...g.shortcutVia], [...ch.shortcutVia], "shortcut vias match");
});

test("G2 bad magic -> null — a tampered header never half-decodes (T-06-03)", async () => {
  const { encodeGraph, decodeGraph } = await loadGraph();
  const buf = encodeGraph(syntheticInput());
  const tampered = buf.slice(0);
  new DataView(tampered).setUint32(0, 0xdeadbeef, true);
  assert.equal(decodeGraph(tampered), null, "wrong magic -> null, never a throw");
});

test("G3 bad version -> null — ARG1 fixture bytes refuse; version 1, 2 and 4 tampers to null (D-01 one-path law)", async () => {
  const { encodeGraph, decodeGraph } = await loadGraph();
  // The frozen rejection vectors: REAL ARG1 bytes decode to null — the
  // Phase 6 router-pending state covers every pre-ARG3 binary (D-01).
  // There is exactly one decode path; no v1/v2 fallback branch exists.
  // (mini-graph-arg2.bin — the frozen ARG2-era bytes, D-12 — is pinned in
  // the committed-fixture cases G4/G7; the version-2 tamper here covers
  // the same law in memory.)
  const arg1 = toArrayBuffer(readFileSync(path.join(here, "fixtures", "mini-graph-arg1.bin")));
  assert.equal(decodeGraph(arg1), null, "ARG1 bytes -> null, never a throw or a fallback decode");
  const buf = encodeGraph(syntheticInput());
  const v1 = buf.slice(0);
  new DataView(v1).setUint32(4, 1, true);
  assert.equal(decodeGraph(v1), null, "version 1 -> null");
  const v2 = buf.slice(0);
  new DataView(v2).setUint32(4, 2, true);
  assert.equal(decodeGraph(v2), null, "version 2 -> null (ARG2 is a rejection vector — D-07)");
  const v4 = buf.slice(0);
  new DataView(v4).setUint32(4, 4, true);
  assert.equal(decodeGraph(v4), null, "version 4 -> null (the accepted version is 3)");
});

test("G4 committed ARG3 fixture — 25 nodes / 80 edges / rank 25 / >=1 shortcut; the preserved ARG2 vector decodes to null", async () => {
  const { decodeGraph, GRAPH_MAGIC, GRAPH_VERSION } = await loadGraph();
  // The committed ground truth, read as bytes: ARG3 header fields only.
  const bin = readFileSync(path.join(here, "fixtures", "mini-graph.bin"));
  assert.equal(bin.readUInt32LE(0), GRAPH_MAGIC, "the committed fixture is ARG3-magic");
  assert.equal(bin.readUInt32LE(4), GRAPH_VERSION, "the committed fixture is version 3");
  assert.equal(bin.readUInt32LE(8), 25, "25 nodes");
  assert.equal(bin.readUInt32LE(12), 80, "80 directed edges");
  assert.ok(bin.readUInt32LE(60) >= 1, "the committed hierarchy carries at least one shortcut");
  // Decoding sees the rank table's length too.
  const g = decodeGraph(toArrayBuffer(bin));
  assert.ok(g, "the committed fixture decodes as ARG3");
  assert.equal(g.chRank.length, 25, "one rank per node");
  assert.equal(g.chShortcutCount, bin.readUInt32LE(60), "the header count agrees with the decoded graph");
  // The preserved ARG2-era bytes (frozen before this fixture's
  // regeneration — D-12) decode to null: one decode path, no fallback.
  const arg2 = toArrayBuffer(readFileSync(path.join(here, "fixtures", "mini-graph-arg2.bin")));
  assert.equal(decodeGraph(arg2), null, "ARG2 bytes -> null (the D-07 rejection vector)");
});

test("G4 truncated + hostile-size buffer -> null — exact byte-size check BEFORE any view allocation (T-06-03b)", async () => {
  const { encodeGraph, decodeGraph } = await loadGraph();
  const buf = encodeGraph(syntheticInput());
  assert.equal(
    decodeGraph(buf.slice(0, buf.byteLength - 1)),
    null,
    "one byte short -> null (truncated)",
  );
  assert.equal(decodeGraph(new ArrayBuffer(0)), null, "empty buffer -> null");
  assert.equal(decodeGraph(new ArrayBuffer(16)), null, "sub-header buffer -> null");
  // Hostile header: valid magic/version but a huge nodeCount on a tiny buffer —
  // the size mismatch rejects it before any allocation (T-06-03b).
  const hostile = new ArrayBuffer(72);
  const dv = new DataView(hostile);
  const { GRAPH_MAGIC, GRAPH_VERSION } = await loadGraph();
  dv.setUint32(0, GRAPH_MAGIC, true);
  dv.setUint32(4, GRAPH_VERSION, true);
  dv.setUint32(8, 1_000_000, true); // declares a million nodes…
  assert.equal(decodeGraph(hostile), null, "huge-count header on a tiny buffer -> null, no allocation");
});

test("G5 zero-copy views — the views' .buffer IS the input buffer; flipping an input byte flips the view", async () => {
  const { encodeGraph, decodeGraph } = await loadGraph();
  const buf = encodeGraph(syntheticInput()).slice(0);
  const g = decodeGraph(buf);
  assert.ok(g, "decode succeeds");
  assert.equal(g.lat.buffer, buf, "lat is a VIEW over the input buffer (zero-copy)");
  assert.equal(g.edgeSeconds.buffer, buf, "edgeSeconds is a VIEW over the input buffer");
  assert.equal(g.chRank.buffer, buf, "chRank is a VIEW over the input buffer (CH zero-copy)");
  // The padded header ends at byte 72 — the first lat byte. Flip it.
  const dv = new DataView(buf);
  const before = g.lat[0];
  dv.setUint8(72, dv.getUint8(72) ^ 0xff);
  assert.notEqual(g.lat[0], before, "mutating the input buffer flips the decoded view");
});

test("G6 name pool — nameAt(0) resolves the first pool name; the unnamed sentinel resolves undefined", async () => {
  const { encodeGraph, decodeGraph, UNNAMED_NAME_ID } = await loadGraph();
  const g = decodeGraph(encodeGraph(syntheticInput()));
  assert.ok(g, "decode succeeds");
  assert.equal(g.nameAt(0), "Jalan Mini 1", "nameId 0 -> the first pool name");
  assert.equal(g.nameAt(1), "Jalan Mini 2");
  assert.equal(g.nameAt(UNNAMED_NAME_ID), undefined, "UNNAMED_NAME_ID -> undefined");
  assert.equal(g.nameAt(999), undefined, "out-of-range id -> undefined");
});

test("G7 committed ARG3 fixture — decodes to 25 nodes / 80 edges / 3 names / a real hierarchy, maxSpeed 60, ONE oneway", async () => {
  const { decodeGraph } = await loadGraph();
  const bin = toArrayBuffer(readFileSync(path.join(here, "fixtures", "mini-graph.bin")));
  assert.ok(bin.byteLength > 1000, `the committed fixture is substantial (${bin.byteLength} B)`);
  const g = decodeGraph(bin);
  assert.ok(g, "the committed fixture decodes cleanly (ARG3 — regenerated through the ONE encode authority, task 3)");
  assert.equal(g.nodeCount, 25, "5x5 grid");
  assert.equal(g.edgeCount, 80, "20 H + 20 V segments, both directions");
  assert.equal(g.nameCount, 3, "Jalan Mini 1 / Jalan Mini 2 / Jalan Persiaran Mini");
  assert.equal(g.nameAt(0), "Jalan Mini 1");
  assert.equal(g.nameAt(2), "Jalan Persiaran Mini");
  assert.equal(g.maxSpeedKmh, 60, "the perimeter speed class is the header max");
  // bbox of the hand-built grid (lat 3.1500–3.1520, lng 101.6900–101.6920)
  assert.deepEqual(g.bbox, { minLat: 3.15, minLng: 101.69, maxLat: 3.152, maxLng: 101.692 });
  let flagged = 0;
  for (let e = 0; e < g.edgeCount; e++) if ((g.edgeFlags[e] & 1) !== 0) flagged++;
  assert.equal(flagged, 1, "exactly ONE oneway-reverse edge in the whole fixture");
  // both speed classes present: perimeter ~55.6 m / 16.67 ≈ 3.3 s; interior ≈ 6.7 s
  let sawFast = false;
  let sawSlow = false;
  for (let e = 0; e < g.edgeCount; e++) {
    if (g.edgeSeconds[e] < 5) sawFast = true;
    if (g.edgeSeconds[e] > 5) sawSlow = true;
  }
  assert.ok(sawFast && sawSlow, "both speed classes (60 and 30 km/h) exist in the weights");
  // ARG3 CH laws (Phase 08.1, D-12): the fixture regenerates THROUGH the
  // encode authority with the tiny real contraction stage (S = 41 on the
  // 5x5 grid — the healthy ~1.6/node band).
  assert.equal(g.chRank.length, 25, "one rank per node");
  assert.equal(g.shortcutStart.length, 26, "CSR row pointers: nodeCount + 1");
  assert.equal(g.shortcutTarget.length, g.chShortcutCount, "shortcut CSR lengths agree with the header");
  assert.equal(g.shortcutSeconds.length, g.chShortcutCount, "shortcut seconds length agrees");
  assert.equal(g.shortcutVia.length, g.chShortcutCount, "shortcut via length agrees");
  assert.ok(g.chShortcutCount >= 1, "the committed hierarchy carries at least one shortcut");
  // Rank is a total order (Pitfall 9) and the shortcuts are upward.
  assert.equal(new Set(g.chRank).size, 25, "ranks are DISTINCT");
  for (let u = 0; u < g.nodeCount; u++) {
    for (let s = g.shortcutStart[u]; s < g.shortcutStart[u + 1]; s++) {
      const via = g.shortcutVia[s];
      assert.ok(g.chRank[u] > g.chRank[via] && g.chRank[g.shortcutTarget[s]] > g.chRank[via], `shortcut ${u}->${g.shortcutTarget[s]} is upward against via ${via}`);
    }
  }
  // The preserved ARG2-era bytes decode to null (D-12's rejection vector).
  const arg2 = toArrayBuffer(readFileSync(path.join(here, "fixtures", "mini-graph-arg2.bin")));
  assert.equal(decodeGraph(arg2), null, "ARG2 bytes -> null (the D-07 rejection vector)");
});

test("G8 exported constants — GRAPH_MAGIC === 0x41524733 ('ARG3'), GRAPH_VERSION === 3", async () => {
  const mod = await loadGraph();
  assert.equal(mod.GRAPH_MAGIC, 0x41524733);
  assert.equal(mod.GRAPH_VERSION, 3);
  assert.equal(mod.UNNAMED_NAME_ID, 0xffffffff);
});

test("G9 table round-trip — the CH fields restore exactly; the CH arrays are zero-copy views", async () => {
  const { encodeGraph, decodeGraph } = await loadGraph();
  const ch = syntheticCh();
  const buf = encodeGraph({ ...syntheticInput(), ch }).slice(0);
  const g = decodeGraph(buf);
  assert.ok(g, "decode succeeds");
  assert.equal(g.chShortcutCount, 1, "chShortcutCount === S");
  assert.deepEqual([...g.chRank], [...ch.rank], "chRank restores exactly");
  assert.deepEqual([...g.shortcutStart], [...ch.shortcutStart], "shortcutStart restores exactly");
  assert.deepEqual([...g.shortcutTarget], [...ch.shortcutTarget], "shortcutTarget restores exactly");
  assert.deepEqual([...g.shortcutSeconds], [...ch.shortcutSeconds], "shortcutSeconds restores exactly");
  assert.deepEqual([...g.shortcutVia], [...ch.shortcutVia], "shortcutVia restores exactly");
  assert.equal(g.chRank.buffer, buf, "chRank is a zero-copy view");
  assert.equal(g.shortcutStart.buffer, buf, "shortcutStart is a zero-copy view");
  assert.equal(g.shortcutTarget.buffer, buf, "shortcutTarget is a zero-copy view");
  assert.equal(g.shortcutSeconds.buffer, buf, "shortcutSeconds is a zero-copy view");
  assert.equal(g.shortcutVia.buffer, buf, "shortcutVia is a zero-copy view");
});

test("G10 encode validation — malformed ch input throws NAMED encodeGraph: errors (T-08-04, no silent clamp)", async () => {
  const { encodeGraph } = await loadGraph();
  const base = syntheticInput();
  const mangle = (over) => ({ ...base, ch: { ...base.ch, ...over } });
  const cases = [
    ["ch block missing", { ...base, ch: undefined }],
    ["rank length != nodeCount", mangle({ rank: Uint32Array.of(1, 0) })],
    ["shortcutStart length != nodeCount+1", mangle({ shortcutStart: Uint32Array.of(0, 1, 1) })],
    ["target length != S (via disagrees)", mangle({ shortcutVia: Uint32Array.of() })],
    ["seconds length != S (target disagrees)", mangle({ shortcutSeconds: Float32Array.of() })],
    ["via id >= nodeCount", mangle({ shortcutVia: Uint32Array.of(7) })],
    ["via id negative-ish (huge)", mangle({ shortcutTarget: Uint32Array.of(0xffff_ffff), shortcutVia: Uint32Array.of(0xffff_ffff) })],
    ["non-finite shortcut seconds", mangle({ shortcutSeconds: Float32Array.of(Number.NaN) })],
    ["negative shortcut seconds", mangle({ shortcutSeconds: Float32Array.of(-1) })],
  ];
  for (const [label, input] of cases) {
    assert.throws(() => encodeGraph(input), /^Error: encodeGraph: /, `${label} -> named encodeGraph: error`);
  }
});

test("G11 decode rejection — chShortcutCount 0 -> null even when the size matches; monster count -> null by arithmetic (T-08.1-01)", async () => {
  const { encodeGraph, decodeGraph, GRAPH_MAGIC, GRAPH_VERSION } = await loadGraph();
  const buf = encodeGraph(syntheticInput());
  const zeroed = buf.slice(0);
  new DataView(zeroed).setUint32(60, 0, true);
  assert.equal(decodeGraph(zeroed), null, "chShortcutCount = 0 -> null (no CH-less ARG3 — A5)");
  // A CONSISTENT CH-less buffer (byte size exactly matches the S=0 ARG3
  // layout: header + base sections + align4(namePoolEnd) + chRank[n] +
  // shortcutStart[n+1]) still refuses — the law is the count itself, not
  // a size mismatch.
  const n = 1;
  const lay = 72 + 8 * n + 8 * n + 4 * (n + 1) + 4 * 1 + 4 * n + 4 * (n + 1); // = 112: header + lat + lng + edgeStart[2] + nameOffset[1] + chRank[1] + shortcutStart[2]; no shortcut payload
  const bare = new ArrayBuffer(lay);
  const dv = new DataView(bare);
  dv.setUint32(0, GRAPH_MAGIC, true);
  dv.setUint32(4, GRAPH_VERSION, true);
  dv.setUint32(8, n, true);
  dv.setUint32(12, 0, true); // edgeCount
  dv.setUint32(16, 0, true); // nameCount
  dv.setUint32(20, 0, true); // namePoolLen
  dv.setUint32(60, 0, true); // chShortcutCount = 0
  assert.equal(decodeGraph(bare), null, "an exactly-sized CH-less ARG3 -> null");
  // Monster header: S = 2,000,000 on a tiny buffer — the exact-size
  // arithmetic rejects BEFORE any typed-array allocation (a null return,
  // never a RangeError).
  const monster = buf.slice(0);
  new DataView(monster).setUint32(60, 2_000_000, true);
  assert.equal(decodeGraph(monster), null, "monster chShortcutCount on a tiny buffer -> null, no allocation");
});