22 KiB
phase, plan, type, wave, depends_on, files_modified, autonomous, requirements, must_haves
| phase | plan | type | wave | depends_on | files_modified | autonomous | requirements | must_haves | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 08-alt-landmark-preprocessing-routing-backend-v2 | 02 | execute | 2 |
|
|
true |
|
|
Purpose: the binary this plan defines is what the build (08-04), the ALT potentials (08-03), and the real-graph campaign (08-05) all consume.
Output: routing/src/landmark.ts, ARG2 routing/src/graph.ts, extended G-suite, regenerated mini-graph.bin (+ frozen mini-graph-arg1.bin as the rejection vector).
<execution_context> @$HOME/.config/opencode/get-shit-done/workflows/execute-plan.md @$HOME/.config/opencode/get-shit-done/templates/summary.md </execution_context>
@.planning/PROJECT.md @.planning/STATE.md @.planning/phases/08-alt-landmark-preprocessing-routing-backend-v2/08-CONTEXT.md @.planning/phases/08-alt-landmark-preprocessing-routing-backend-v2/08-RESEARCH.md @.planning/phases/08-alt-landmark-preprocessing-routing-backend-v2/08-PATTERNS.mdCurrent header (64 B): magic u32 @0 = 0x41524731; version u32 @4 = 1; nodeCount @8; edgeCount @12; nameCount @16; namePoolLen @20; bbox 4×f64 @24..55; maxSpeedKmh f32 @56; pad @60..63. NOTE: the RESEARCH doc's "@52 maxSpeedKmh" is a doc drift — the CODE truth is @56 (view.getFloat32(56, true)). ARG2 places its new fields where the pad was.
Sections (relative order unchanged): lat f64[N], lng f64[N], edgeStart u32[N+1], edgeTarget u32[E], edgeFlags u8[E], edgeSeconds f32[E] (4-byte aligned start), edgeNameId u32[E], nameOffset u32[names+1], namePool u8[pool].
Existing exports/consts: GRAPH_MAGIC = 0x41524731, GRAPH_VERSION = 1, UNNAMED_NAME_ID = 0xffffffff, decodeGraph(buffer): RoadGraph | null, encodeGraph(input: GraphInput): ArrayBuffer (throws via fail() on malformed input), private layoutFor(...): Layout { lat, lng, ..., total }.
Decode laws carried forward: buffer.byteLength < HEADER_SIZE → null; magic/version mismatch → null; buffer.byteLength !== lay.total → null BEFORE any view allocation.
export const LANDMARK_QUANTUM_S = 0.1; // the ĉ unit (header field default; doc'd fork knob)
export const LANDMARK_MAX_QUANTA = 65000; // u16 headroom below the 0xFFFF sentinel
export interface LandmarkInput {
nodeCount: number;
edges: Array<{ from: number; to: number; seconds: number; flags: number }>; // flags bit0 = oneway-reverse: relaxed by NO direction
quantumS: number; // named-callers pass LANDMARK_QUANTUM_S
}
export const LANDMARK_SENTINEL = 0xffff;
/** Deterministic farthest-point selection over the ĉ metric. */
export function farthestPointAnchors(input: LandmarkInput, count: number, opts?: { coverageFraction?: number }): Uint32Array;
/** Integer ĉ-metric Dijkstras: returns { to: Uint16Array (L·N), from: Uint16Array (L·N) } (row-major: [ℓ*N + v]). */
export function landmarkTables(input: LandmarkInput, anchors: Uint32Array): { to: Uint16Array; from: Uint16Array };
/** Per-anchor coverage audit (fraction of nodes with non-sentinel to-entry), for the build's assert. */
export function landmarkCoverage(to: Uint16Array, anchors: Uint32Array, nodeCount: number): number[];
Mechanics (concrete): build forward + reversed CSR internally (nodeCount+1 row pointers; reversed skips nothing — flags semantics: bit0 edges are traversed by the REVERSED direction only in the reverse set... mirror exactly the A1 test-local Dijkstra law: an edge u→v with flags bit0 CLEAR is relaxed in the forward pass FROM v in the reversed graph, and NEVER in the unreversed mirror — the keyword: oneway-reverse edges are traversable only backwards). ĉ(u,v) = Math.floor(seconds / quantumS) (floor keeps the surrogate ≤ the live edge). Integer Dijkstra with a binary heap over Int32 quanta labels; unvisited-finite-only relaxation; 0xFFFF frozen as unreachable. Coverage via a per-anchor reachable-count / nodeCount. Throwing path: any final label or intermediate > LANDMARK_MAX_QUANTA → throw new Error("landmarkTables: quantized distance <d> exceeds <MAX> (raise landmarkQuantumS)”). Determinism: anchor greed starts at the first degree-≥2 candidate by node id; ties broken by lower node id; the greedy loop reuses each picked anchor's forward pass to maintain the per-node min-distance field (≈2L total passes, not 3L).
RED: write routing/test/landmark.test.mjs covering the cases (hand-computed expectations on a 5-node path graph + the 5×5-grid mini graph shape from the fixture builder) BEFORE implementing; run RED; then implement; then GREEN + npm run routing:typecheck.
export PATH="$HOME/.nvm/versions/node/v24.18.0/bin:$PATH" && npm run routing:test 2>&1 | tail -3 && npm run routing:typecheck && echo "LANDMARK-CORE-GREEN"
<acceptance_criteria>
- routing/test/landmark.test.mjs exists, committed, all cases passing (runner reports 0 failed).
- grep -c "Math.random" routing/src/landmark.ts === 0 (determinism law).
- grep -c "0xffff" routing/src/landmark.ts ≥ 2 (sentinel used, not invented per-callsite).
- grep -c "Math.floor" routing/src/landmark.ts ≥ 1 (the ĉ floor rule, exact placement documented in Pattern 2).
- typecheck clean; no imports outside node builtins/types in the module.
</acceptance_criteria>
Deterministic anchors + exact integer ĉ tables + sentinel/overflow laws proven on hand-computed vectors.
GRAPH_MAGIC = 0x41524732("ARG2");GRAPH_VERSION = 2;HEADER_SIZE = 72(comment: 72 % 8 == 0 keeps f64 views 8-byte aligned).- Layout: after the ARG1 field order — landmarkCount u32 @60 (the old pad), landmarkQuantumS f32 @64, reserved u32 @68 (written 0, asserted-decode-0 OPTIONAL — recommend accepting any value there, the field is unused). Sections start @72 (ARG1 relative structure preserved, each offset shifted +8).
- Suffix in layoutFor:
const toTable = align4(namePool + namePoolLen); const fromTable = toTable + 2*L*N; const landmarkNodes = fromTable + 2*L*N; const total = landmarkNodes + 4*L;(u16 × dual families × L×N bytes + u32 anchors; alignment pad before toTable via& ~3; decode/encode use identical arithmetic — singlelayoutForgainslandmarkCount+quantumparams or reads stored fields). RoadGraphgains fields:landmarkCount: number; landmarkQuantumS: number; landmarkTo: Uint16Array; landmarkFrom: Uint16Array; landmarkNodes: Uint32Array;decodeGraph: read L @60 and quantum @64;if (L === 0) return null(comment cites D-01/A5); extend the exact-size check to the suffix BEFORE allocation; allocate u16/u32 zero-copy views; magic/version laws unchanged in shape (v1 bytes now fail the version check — THE D-01 one-path law; comment cites the router-pending coverage).GraphInputgains REQUIREDlandmarks: { quantumS: number; nodes: ArrayLike<number>; to: Uint16Array; from: Uint16Array }— encode loud-validates lengths (L = nodes.length; to/from lengths === L·N; every node id < nodeCount; quantumS finite > 0; fail() otherwise). Bulk writes: follow the file's existing section-write pattern for the u16/u32 views so decode's zero-copy views read back exactly (endianness discipline identical to the existing f32/f64 sections).- RED: extend routing/test/graph.test.mjs first (new cases appended with the doc-index comment updated; keep the case-harness
loadGraph()lazy-import pattern), run RED, then implement GREEN.
Doc-comment update at the module head: ARG2 layout table (72-byte header field offsets, suffix order), the D-01 fail-honest law, the sentinel (0xFFFF is DATA — never validated away).
export PATH="$HOME/.nvm/versions/node/v24.18.0/bin:$PATH" && npm run routing:test 2>&1 | tail -3 && npm run routing:typecheck && echo "ARG2-CODEC-GREEN"
<acceptance_criteria>
- npm run routing:test green INCLUDING the new G-cases (runner output 0 failed); the G-case doc-index header lists them.
- tamper-vector grep: grep -c "setUint32(4" routing/test/graph.test.mjs ≥ 1 (version tamper present) and the landmarkCount=0 + oversized-L cases exist (grep -c "landmarkCount" ≥ 4).
- grep -n "0x41524731" routing/src/graph.ts returns ZERO code hits (may appear only in a comment naming the retired magic); 0x41524732 is THE constant.
- Header-72 arithmetic: grep HEADER_SIZE = 72 ≥ 1; grep -n "getFloat32(56" routing/src/graph.ts still exactly 1 (the untouched ARG1 field).
- typecheck clean; RoadGraph's five new fields grep-findable.
</acceptance_criteria>
One codec, one version (2): ARG2 encodes/decodes with tables; every non-ARG2 input class decodes null before allocation; G7/G8 re-pinned.
Then update the ONLY remaining encodeGraph v1-shaped runtime call sites so the FULL battery is green in THIS plan (the required-landmarks law makes them fail loudly otherwise): bot/test/webhook.test.mjs (both corridor builders, encodeGraph calls at lines ~499 and ~509) and bot/test/guidance-cron.test.mjs (~252) — each computes tiny tables via farthestPointAnchors + landmarkTables from @araharah/routing's ../../src/landmark.ts and passes the landmarks block. (Call-site updating, NOT a second encode function — anti-pattern respected.)
Then re-run the full verification battery: the committed fixture is now ARG2 — every existing test that consumes mini-graph.bin must stay green (G7 re-pin, snap suite, A-suite via astar.test's fixture load, loader-env). Verify mini-graph-arg1.bin still decodes to null via the new G3 case (task 2 wired it).
NOTE: routeAstar still runs haversine potentials here (ALT lands in Plan 08-03) — that coexistence is deliberate; A-suite greenness at this commit proves the codec change alone is behavior-neutral to the search.
export PATH="$HOME/.nvm/versions/node/v24.18.0/bin:$PATH" && node routing/test/fixtures/build-mini-graph.mjs && npm run routing:test 2>&1 | tail -3 && npm test -w bot 2>&1 | tail -2 && npm run routing:typecheck && npm run bot:typecheck && echo "FULL-BATTERY-GREEN"
<acceptance_criteria>
- node routing/test/fixtures/build-mini-graph.mjs exits 0 and prints the landmark stats; mini-graph.bin regenerated (git diff shows content change, same path).
- git status shows mini-graph-arg1.bin unchanged bytes from Plan 08-01 (cmp vs its committed version passes — it is NOT regenerated).
- npm run routing:test AND npm test -w bot AND both typechecks fully green at this commit (the corridor/cron encodeGraph call sites now pass the landmarks block).
- grep law: grep -Lc "landmarms\|landmarks" bot/test/webhook.test.mjs bot/test/guidance-cron.test.mjs shows both files contain landmarks: (grep -c "landmarks: {" ≥ 1 in each).
</acceptance_criteria>
Committed fixture is ARG2 through the one encode authority with a tiny landmark set; the frozen ARG1 vector stays byte-identical; the full routing + bot battery is green.
<threat_model>
Trust Boundaries
| Boundary | Description |
|---|---|
| R2 binary → decodeGraph | the graph binary is HOSTILE INPUT at the Worker boundary (V5); the codec is the gate |
| build input → encodeGraph | maintainer-time JSON/graph input; loud failure is the correct posture (T-06-03 shape) |
STRIDE Threat Register
| Threat ID | Category | Component | Disposition | Mitigation Plan |
|---|---|---|---|---|
| T-08-01 | Tampering/DoS | decodeGraph | mitigate | exact-size arithmetic extended over the u16 suffix BEFORE any view allocation — a monster landmarkCount header on a tiny buffer rejects on arithmetic (grep-able test proves it); landmarkCount=0 rejected (no silent-degradation layout) |
| T-08-02 | Tampering | decodeGraph version law | mitigate | ARG1 bytes → null → router-pending (D-01; one decode path, no v1 branch); committed mini-graph-arg1.bin is the standing rejection vector |
| T-08-03 | Information disclosure | codec module | accept | pure module law preserved (no logging/storage/network); T-06-05 unchanged |
| T-08-04 | DoS | encodeGraph | mitigate | resource-exhaustion malformed input fails loudly with named encodeGraph: errors before any allocation work |
| </threat_model> |
<success_criteria> ARG2 is the single, fail-honest, exact-size-validated layout; the landmarkTables/farthestPointAnchors core exists once (pure, deterministic, integer-exact); every synthetic/future graph encodes landmark tables through the one authority; nothing else about decode or search behavior changed at this commit (A-suite green on haversine potentials over the ARG2 fixture). </success_criteria>
After completion, create `.planning/phases/08-alt-landmark-preprocessing-routing-backend-v2/08-02-SUMMARY.md`