arah2/routing/scripts/build-road-graph.mjs

#!/usr/bin/env node
/*
 * build-road-graph.mjs — the D-01 engine-A graph build tool (Overpass → CSR).
 * ---------------------------------------------------------------------------
 * A MAINTAINER-TIME REPO TOOL — NOT a runtime dependency; nothing in bot/src,
 * web/src, or routing/src imports it. No deploy, test, or CI run ever executes
 * it. A maintainer (or a fork) runs it on their own machine to produce the
 * KL road-graph binary, then uploads it to their OWN R2 bucket (D-01:
 * fork-friendly, $0 — see docs/ROAD-GRAPH.md).
 *
 * Mechanically:
 *   1. The KL bbox is COMPUTED at run start from the committed corpus —
 *      @araharah/search getEntries() extremes + the golden-pairs origin
 *      coordinates ± BBOX_MARGIN_DEG — and printed (Open Q 4's mechanical
 *      pinning: the bbox tunes itself when the corpus grows; never hand-edited).
 *   2. ONE Overpass query fetches every way whose highway tag is in
 *      DRIVABLE_CLASSES (footway/cycleway/service/path NEVER enter — 06-RESEARCH
 *      Pitfall 1: an unfiltered highway=* graph is the classic CPU-budget kill).
 *   3. Ways → nodes (deduplicated by rounded coordinate) → directed edges with
 *      oneway flags, speed-derived seconds, and street-name pool ids.
 *   4. THE CH PREPROCESSING STAGE (Phase 08.1): the compacted edges feed the
 *      ONE contraction module (../src/contraction.ts — this script quantizes
 *      nothing and implements nothing itself): contractGraph runs the
 *      deterministic ordering, the overlay-only bounded witness search, and
 *      the directed shortcut emission. Any throw names the stage and its
 *      reason and exits 1 BEFORE a byte is written.
 *   5. encodeGraph (../src/graph.ts — the layout's SINGLE authority) produces
 *      the pinned ARG3 CSR binary from the edge set + the CH tables (the `ch:`
 *      input — rank + shortcut CSR with unpacking vias). COLLECT-THEN-WRITE:
 *      routing/data/kl-roadgraph.v1.bin is written ONLY after the encode and
 *      the stats gate both pass — any failure exits 1 with the previous
 *      binary untouched.
 *   6. THE STATS GATE prints nodeCount/edgeCount/bbox/CH facts (contracted
 *      nodes, shortcuts + ratio, witness searches + budget hits, CH-section
 *      bytes, build wall-clock, total bytes — D-08/D-09: MEASURED, never
 *      hoped) and enforces the D-01 envelope: outside 1-80 MB → exit 1
 *      without writing. There is NO fixed ARG3 payload ceiling (D-08): the
 *      build ships whatever contraction produces, measured.
 *
 * The binary is a BUILD ARTIFACT, not committed: routing/data/.gitignore
 * ignores *.bin — forks build + upload their own (ODbL-derived data stays out
 * of the repo; the attribution travels in docs/ROAD-GRAPH.md and the upload
 * path). The committed artifacts are this script, the docs, and the tiny
 * test mini-graph.
 *
 * Usage:
 *   node routing/scripts/build-road-graph.mjs
 *              # full build: fetch → contract (CH) → encode → gate → write
 *              #            (network fetch; the CH stage is Dijkstra-heavy —
 *              #            D-09: minutes, not hours, and the wall-clock is
 *              #            printed either way)
 *   node routing/scripts/build-road-graph.mjs --check <file>
 *              # decode an existing ARG3 binary with decodeGraph, print the
 *              # stats incl. the CH facts, exit 0/1 — NO network. --check is
 *              # a decode+facts tool for ANY valid ARG3 (the committed test
 *              # fixture included): the envelope appears as an ADVISORY line;
 *              # the ENFORCED 1-80 MB gates run in the build path, before
 *              # any write.
 *
 * Exit codes: 0 built and gated (or checked green); 1 pre-flight failure,
 * fetch failure, CH contraction/encode failure, envelope-gate failure, or
 * --check decode failure.
 */
import { existsSync, mkdirSync, readFileSync, statSync, writeFileSync } from "node:fs";
import { dirname, resolve } from "node:path";
import { fileURLToPath } from "node:url";

const here = dirname(fileURLToPath(import.meta.url)); // routing/scripts
const CORPUS_PATH = resolve(here, "..", "test", "fixtures", "golden-pairs.json");
const OUT_PATH = resolve(here, "..", "data", "kl-roadgraph.v1.bin");

/* ————— named constants (no inline magic) ————— */

const OVERPASS_ENDPOINT = "https://overpass-api.de/api/interpreter";
/** Overpass server-side budget; matches the client fetch timeout. */
const REQUEST_TIMEOUT_MS = 300_000;
const USER_AGENT = "araharah-roadgraph/1.0 (build-time KL road graph; repo: araharah)";
/** D-01 envelope ceiling — a larger binary must NOT be written (shrink the
 *  class filter or the bbox instead). */
const MAX_BINARY_BYTES = 80 * 1024 * 1024;
/** How far the computed bbox extends beyond the committed corpus extremes. */
const BBOX_MARGIN_DEG = 0.05;
/** Node dedup granularity: 1e-6 deg ≈ 0.11 m — far under GPS noise. */
const COORD_ROUND_DECIMALS = 6;
/** drivable classes ONLY (06-RESEARCH Pitfall 1): footway/cycleway/service/
 *  path are deliberately absent — a walking path must never enter a road
 *  search. The *_link classes are LOAD-BEARING (measured 2026-10-24): they
 *  are the interchange ramps tying motorway/trunk/primary into the surface
 *  network. Without them the graph FRAGMENTS — 7.7% of nodes sat in severed
 *  motorway islands and golden corpus pairs resolved "unreachable" because
 *  an endpoint snapped onto an isolated fragment.
 *
 * A1 MITIGATION LADDER HISTORY (measure-route-cpu.mjs is the arbiter):
 *   2026-10-24 full 13-class linked graph (311k nodes):  p95 38.4 ms, ALL
 *     corpus pairs route — connectivity correct, CPU over budget.
 *   2026-10-24 ladder step (a) — drop tertiary+residential (127k nodes):
 *     p95 17.8 ms BUT 12/25 pairs (incl. 8/15 golden corpus pairs) became
 *     UNREACHABLE — the dropped classes were the fine mesh tying landmarks
 *     to the arterial network. REJECTED on correctness (D-03: an honest
 *     router-pending for half the product's destinations is not a smaller
 *     graph, it is a broken one). REVERTED to the full 13-class set.
 *   Ladder step (b) — bidirectional A*: sound, no worse, better on short
 *     product routes; kept until superseded.
 *   Ladder step (c) — Workers Paid — breaks the $0 law and requires user
 *     sign-off; it is NOT applied in this script.
 *   Ladder rung (c2) — EXECUTED in Phase 8 (build-time ALT tables): the
 *     CPU verdict measured over budget; the c3 degradation class stayed.
 *   Ladder lever (Phase 08.1) — Contraction Hierarchies: THIS script's CH
 *     preprocessing stage (step 4 below) replaces steering with structure.
 *     The verdict lives in measure-route-cpu.mjs's history and the budget
 *     record — the class retires only on a passing measurement (D-01). */
const ACTIVE_CLASSES = new Set([
  "motorway",
  "trunk",
  "primary",
  "secondary",
  "tertiary",
  "residential",
  "unclassified",
  "living_street",
  "motorway_link",
  "trunk_link",
  "primary_link",
  "secondary_link",
  "tertiary_link",
]);
/** Class speed defaults (km/h) when a way carries no parsable maxspeed. */
const CLASS_SPEED_KMH = {
  motorway: 100,
  trunk: 80,
  primary: 60,
  secondary: 50,
  tertiary: 40,
  residential: 30,
  unclassified: 30,
  living_street: 20,
};
/** Motorway link ramps inherit a near-parent speed via these links. */
const LINK_CLASS_SPEED_KMH = {
  motorway_link: 60,
  trunk_link: 60,
  primary_link: 50,
  secondary_link: 40,
  tertiary_link: 40,
};
/** ENFORCED floor — an at/below-1 MB "KL road graph" is a broken build (D-01).
 *  The floor and the ceiling above are the ONLY byte gates: the ARG3 payload
 *  itself is measured-first (D-08) — no pre-committed CH payload ceiling. */
const MIN_BINARY_BYTES = 1 * 1024 * 1024;

const mb = (b) => `${(b / (1024 * 1024)).toFixed(1)} MB`;

function fail(message) {
  console.error(`build-road-graph: ${message}`);
  process.exit(1);
}

/* ————— --check mode: decode + CH facts, no network ————— */

const checkIdx = process.argv.indexOf("--check");
if (checkIdx !== -1) {
  const file = process.argv[checkIdx + 1];
  if (file === undefined) fail("--check requires a file path");
  if (!existsSync(file)) fail(`--check: file not found: ${file}`);
  const { decodeGraph } = await import("../src/graph.ts");
  const buffer = readFileSync(file);
  const graph = decodeGraph(buffer.buffer.slice(buffer.byteOffset, buffer.byteOffset + buffer.byteLength));
  if (graph === null) fail(`--check: ${file} is NOT a valid ARG3 CSR binary (decodeGraph null)`);
  const size = statSync(file).size;
  // ARG3 CH facts (Phase 08.1): read straight off the decoded views — the
  // SAME ONE codec module decoded the bytes; NO network.
  console.log(
    `--check ${file}\n` +
      `  nodeCount: ${graph.nodeCount}\n` +
      `  edgeCount: ${graph.edgeCount}\n` +
      `  nameCount: ${graph.nameCount}\n` +
      `  maxSpeedKmh: ${graph.maxSpeedKmh}\n` +
      `  bbox: [${graph.bbox.minLat}, ${graph.bbox.minLng}, ${graph.bbox.maxLat}, ${graph.bbox.maxLng}]\n` +
      `  bytes: ${size}\n` +
      `  chShortcutCount: ${graph.chShortcutCount}\n` +
      `  shortcut ratio: ${(graph.chShortcutCount / graph.nodeCount).toFixed(2)} per node\n` +
      `  chRank length: ${graph.chRank.length}`,
  );
  // Advisory only (see the usage note): --check serves any valid ARG3, the
  // committed test fixture included. The ENFORCED gates run in the build path.
  if (size > MAX_BINARY_BYTES || size <= MIN_BINARY_BYTES) {
    console.log(
      `  envelope advisory: ${mb(size)} sits outside the 1-80 MB D-01 envelope a built KL metro graph lands in (advisory only)`,
    );
  }
  process.exit(0);
}

/* ————— inputs ————— */

const { encodeGraph } = await import("../src/graph.ts");
const { haversineM } = await import("../src/geo.ts");

if (!existsSync(CORPUS_PATH)) fail(`corpus not found: ${CORPUS_PATH}`);
const corpus = JSON.parse(readFileSync(CORPUS_PATH, "utf8"));
const { getEntries } = await import("@araharah/search/src/gazetteer.ts");

/* The committed corpus defines the area engine A must route (Open Q 4):
 * gazetteer extremes cover the search surface; golden-pair origins/destinations
 * are gazetteer landmarks themselves — both are unioned so a future corpus
 * extension widens the graph mechanically. */
function computeBbox() {
  let minLat = Infinity;
  let minLng = Infinity;
  let maxLat = -Infinity;
  let maxLng = -Infinity;
  const absorb = (lat, lng) => {
    if (!Number.isFinite(lat) || !Number.isFinite(lng)) fail(`non-finite coordinate in corpus: (${lat}, ${lng})`);
    if (lat < minLat) minLat = lat;
    if (lat > maxLat) maxLat = lat;
    if (lng < minLng) minLng = lng;
    if (lng > maxLng) maxLng = lng;
  };
  for (const entry of getEntries()) absorb(entry.lat, entry.lng);
  for (const pair of corpus.pairs) absorb(pair.origin.lat, pair.origin.lng);
  const gazetteerById = new Map(getEntries().map((e) => [e.id, e]));
  for (const pair of corpus.pairs) {
    const dest = gazetteerById.get(pair.destinationId);
    if (dest === undefined) fail(`pair ${pair.pairId}: destinationId "${pair.destinationId}" is not a gazetteer entry`);
    absorb(dest.lat, dest.lng);
  }
  return {
    minLat: minLat - BBOX_MARGIN_DEG,
    minLng: minLng - BBOX_MARGIN_DEG,
    maxLat: maxLat + BBOX_MARGIN_DEG,
    maxLng: maxLng + BBOX_MARGIN_DEG,
  };
}

const bbox = computeBbox();
console.log(
  `bbox (corpus extremes ± ${BBOX_MARGIN_DEG} deg): ` +
    `[${bbox.minLat.toFixed(4)}, ${bbox.minLng.toFixed(4)}, ${bbox.maxLat.toFixed(4)}, ${bbox.maxLng.toFixed(4)}]`,
);

/* ————— the Overpass fetch (ONE request, drivable classes only) ————— */

const CLASSES_RE = "^(" + [...ACTIVE_CLASSES].join("|") + ")$";
const query =
  `[out:json][timeout:${Math.floor(REQUEST_TIMEOUT_MS / 1000)}];` +
  `way["highway"~"${CLASSES_RE}"](${bbox.minLat},${bbox.minLng},${bbox.maxLat},${bbox.maxLng});` +
  `out geom;`;

console.log(`fetching ways from ${OVERPASS_ENDPOINT} (this can take minutes)…`);
let payload = null;
try {
  const res = await fetch(OVERPASS_ENDPOINT, {
    method: "POST",
    headers: { "User-Agent": USER_AGENT, "Content-Type": "application/x-www-form-urlencoded" },
    body: `data=${encodeURIComponent(query)}`,
    signal: AbortSignal.timeout(REQUEST_TIMEOUT_MS),
  });
  if (!res.ok) fail(`Overpass returned HTTP ${res.status}`);
  payload = await res.json();
} catch (err) {
  fail(`Overpass fetch failed: ${err.message}`);
}
const ways = Array.isArray(payload?.elements) ? payload.elements.filter((el) => el.type === "way") : [];
if (ways.length === 0) fail("Overpass returned no drivable ways — bbox or endpoint problem");

/* ————— ways → deduplicated nodes → directed edges ————— */

const round6 = (v) => Math.round(v * 1e6) / 1e6;
/** "lat,lng" (rounded) → node id. Identical coordinates ARE the same OSM node. */
const nodeIdByCoord = new Map();
const latOut = [];
const lngOut = [];
function internNode(lat, lng) {
  const key = `${round6(lat)},${round6(lng)}`;
  const hit = nodeIdByCoord.get(key);
  if (hit !== undefined) return hit;
  const id = latOut.length;
  nodeIdByCoord.set(key, id);
  latOut.push(round6(lat));
  lngOut.push(round6(lng));
  return id;
}

/** name → pool id (dense, insertion-ordered). */
const nameIds = new Map();
function internName(name) {
  const hit = nameIds.get(name);
  if (hit !== undefined) return hit;
  const id = nameIds.size;
  nameIds.set(name, id);
  return id;
}

const rawEdges = [];
let onewayCount = 0;
let unnamedCount = 0;
let maxSeenKmh = 0;

function effectiveKmh(highway, maxspeedTag) {
  // First integer in the tag wins ("50", "50 mph", "50 knots" all lead with
  // the number). "none"/variable/messy tags fall back to the class default.
  const parsed = maxspeedTag === undefined ? NaN : parseInt(String(maxspeedTag), 10);
  const classDefault = CLASS_SPEED_KMH[highway] ?? LINK_CLASS_SPEED_KMH[highway] ?? 30;
  const kmh = Number.isFinite(parsed) && parsed > 0 && parsed <= 160 ? parsed : classDefault;
  if (kmh > maxSeenKmh) maxSeenKmh = kmh;
  return kmh;
}

for (const way of ways) {
  const highway = way.tags?.highway;
  if (typeof highway !== "string" || !ACTIVE_CLASSES.has(highway)) continue;
  const geometry = way.geometry;
  if (!Array.isArray(geometry) || geometry.length < 2) continue;
  const kmh = effectiveKmh(highway, way.tags?.maxspeed);
  const nameId = typeof way.tags?.name === "string" && way.tags.name.length > 0 ? internName(way.tags.name) : undefined;
  if (nameId === undefined) unnamedCount += 1;
  // Oneway law: yes/1/true → forward only (reverse gets flags bit0);
  // -1 → reverse only (forward gets flags bit0); anything else bidirectional.
  const oneway = String(way.tags?.oneway ?? "").toLowerCase();
  const forwardOnly = oneway === "yes" || oneway === "1" || oneway === "true";
  const reverseOnly = oneway === "-1";
  if (forwardOnly || reverseOnly) onewayCount += 1;

  let from = internNode(geometry[0].lat, geometry[0].lon);
  for (let i = 1; i < geometry.length; i++) {
    const to = internNode(geometry[i].lat, geometry[i].lon);
    if (to !== from) {
      const meters = haversineM(
        { lat: latOut[from], lng: lngOut[from] },
        { lat: latOut[to], lng: lngOut[to] },
      );
      const seconds = meters / (kmh / 3.6);
      // forward direction: blocked when the way is reverse-only
      rawEdges.push({ from, to, seconds, flags: reverseOnly ? 1 : 0, nameId });
      // reverse direction: blocked when the way is forward-only (bit0 set —
      // stays visible to snapping, never traversed by the search)
      rawEdges.push({ from: to, to: from, seconds, flags: forwardOnly ? 1 : 0, nameId });
    }
    from = to;
  }
}

/* Degree-0 cleanup: a node that lost every segment (collapsed self-loops) is
 * dead weight — compact the id space so the search and the snap grid never
 * scan it. */
const degree = new Uint32Array(latOut.length);
for (const edge of rawEdges) {
  degree[edge.from] += 1;
  degree[edge.to] += 1;
}
const remap = new Int32Array(latOut.length).fill(-1);
const cLat = [];
const cLng = [];
for (let i = 0; i < latOut.length; i++) {
  if (degree[i] > 0) {
    remap[i] = cLat.length;
    cLat.push(latOut[i]);
    cLng.push(lngOut[i]);
  }
}
const edges = rawEdges
  .map((e) => ({ from: remap[e.from], to: remap[e.to], seconds: e.seconds, flags: e.flags, nameId: e.nameId }))
  .filter((e) => e.from >= 0 && e.to >= 0);
const droppedNodes = latOut.length - cLat.length;
if (cLat.length === 0 || edges.length === 0) fail("the extract produced an empty graph — refusing to write");

/* ————— CH preprocessing stage (Phase 08.1): the hierarchy through the ONE module —————
 *
 * This script quantizes nothing and implements nothing itself: the graph's
 * edges feed ../src/contraction.ts (contractGraph — ordering + contraction +
 * the overlay-only bounded witness search + shortcut CSR emission). There is
 * no second CH implementation here (single-authority law). The stage and the
 * encode share one wall-clock measurement (D-09: the number prints either
 * way — an over-run is an honest measurement, not a hidden failure), and any
 * throw names the stage and exits 1 BEFORE a byte is written (T-08.1-10:
 * the previous binary survives every build failure — collect-then-write).
 */

const { contractGraph } = await import("../src/contraction.ts");

const names = [...nameIds.keys()];
// The module's input shape — projected ONCE (no nameId: the CH overlay runs
// on { from, to, seconds, flags }; encodeGraph re-groups the full edges itself).
const chEdges = edges.map((e) => ({ from: e.from, to: e.to, seconds: e.seconds, flags: e.flags }));

const buildT0 = process.hrtime.bigint();
let ch;
let buffer;
try {
  ch = contractGraph({ nodeCount: cLat.length, edges: chEdges });
  buffer = encodeGraph({
    lat: cLat,
    lng: cLng,
    edges,
    names,
    maxSpeedKmh: maxSeenKmh,
    ch: {
      rank: ch.rank,
      shortcutStart: ch.shortcutStart,
      shortcutTarget: ch.shortcutTarget,
      shortcutSeconds: ch.shortcutSeconds,
      shortcutVia: ch.shortcutVia,
    },
  });
} catch (err) {
  fail(`CH preprocessing stage failed: ${err.message}`);
}
const buildMs = Number(process.hrtime.bigint() - buildT0) / 1e6;
const bytes = buffer.byteLength;

/* ————— stats print (measured, BEFORE the gates — a gate refusal still
 *       leaves every number on the terminal) + the D-01 envelope gate ————— */

console.log(
  `graph stats:\n` +
    `  nodeCount: ${cLat.length}${droppedNodes > 0 ? ` (${droppedNodes} degree-0 dropped)` : ""}\n` +
    `  edgeCount: ${edges.length} directed\n` +
    `  nameCount: ${names.length} (${unnamedCount} unnamed ways → UNNAMED sentinel)\n` +
    `  oneway ways: ${onewayCount}\n` +
    `  maxSpeedKmh: ${maxSeenKmh}\n` +
    `  bbox: [${bbox.minLat.toFixed(4)}, ${bbox.minLng.toFixed(4)}, ${bbox.maxLat.toFixed(4)}, ${bbox.maxLng.toFixed(4)}]\n` +
    `  binary size: ${mb(bytes)} (${bytes} B)`,
);

// The CH facts (D-08/D-09): shortcut economy, witness behavior, section
// bytes, wall-clock, total bytes — the measured payload, never a forecast.
console.log(
  `CH stats (contraction through the ONE module):\n` +
    `  contracted nodes: ${cLat.length}\n` +
    `  shortcuts: ${ch.stats.shortcutCount} (${ch.stats.ratioPerNode.toFixed(2)} per node)\n` +
    `  witness searches: ${ch.stats.witnessSearches} (${ch.stats.witnessBudgetHits} hit the settle budget)\n` +
    `  chRank bytes: ${4 * cLat.length}\n` +
    `  shortcut bytes: ${12 * ch.stats.shortcutCount}\n` +
    `  build wall-clock: ${buildMs.toFixed(0)} ms\n` +
    `  total binary: ${mb(bytes)} (${bytes} B)`,
);

// THE ENFORCED GATE (D-01): outside the 1-80 MB envelope → exit 1 WITHOUT writing.
if (bytes > MAX_BINARY_BYTES) {
  fail(`binary is ${mb(bytes)} — over the ${mb(MAX_BINARY_BYTES)} D-01 envelope. ` +
    `Tighten DRIVABLE_CLASSES (drop tertiary/residential first) or shrink the bbox, then rebuild.`);
}
if (bytes <= MIN_BINARY_BYTES) {
  fail(`binary is ${bytes} bytes — at/below the ${MIN_BINARY_BYTES}-byte floor; a real metro graph is never this small. ` +
    `Verify the Overpass query actually returned ways, then rebuild.`);
}

/* ————— collect-then-write (the committed/previous binary survives failures) ————— */

mkdirSync(dirname(OUT_PATH), { recursive: true });
writeFileSync(OUT_PATH, Buffer.from(buffer));
console.log(`wrote ${OUT_PATH} — ${mb(bytes)}, ${cLat.length} nodes, ${edges.length} edges, ${ch.stats.shortcutCount} shortcuts`);
console.log("next: node routing/scripts/upload-road-graph.mjs   # push the binary to your R2 bucket");
process.exit(0);