200 lines
19 KiB
Markdown
200 lines
19 KiB
Markdown
---
|
||
phase: 06-turn-by-turn-guidance-live-driving
|
||
plan: 04
|
||
subsystem: routing
|
||
tags: [engine-a, road-graph, overpass, csr-binary, r2, worker-router, api-route, http-source, bearer-gate, bidirectional-astar, cpu-gate, a1-escalation, fork-contract, odbL]
|
||
|
||
# Dependency graph
|
||
requires:
|
||
- phase: 06-turn-by-turn-guidance-live-driving/01
|
||
provides: "the pinned CSR binary codec (encodeGraph/decodeGraph — the layout's single authority), snapToGraph, routeAstar, deriveSteps, the committed mini-graph fixture"
|
||
- phase: 06-turn-by-turn-guidance-live-driving/03
|
||
provides: "the Bearer-claim posture in webhook.ts (getClaimByToken gate to mirror), the envelope service, bot/package.json's @araharah/routing dep"
|
||
- phase: 05-routing-route-display/01
|
||
provides: "the RoutingSource seam + RouteResult shape engine-A's client backend plugs beneath"
|
||
provides:
|
||
- "routing/scripts/build-road-graph.mjs — the D-01 maintainer tool: corpus-derived bbox, drivable-class Overpass extract (WITH *_link ramps), pinned-CSR encode, enforced 1-80 MB gate + advisory band, --check mode"
|
||
- "routing/data/kl-roadgraph.v1.bin (BUILT, gitignored artifact): 311,325 nodes / 677,068 directed edges / 21,467 names / 14.7 MB, all landmarks in one strongly-connected component"
|
||
- "routing/src/http-source.ts — createHttpRoutingSource: web's RoutingSource backend #2 (slug-guard-first, fail-honest on throw/non-200/malformed/null, defensive RouteResult validation)"
|
||
- "bot/src/routing/worker-router.ts — handleRoute + loadGraph: Bearer-claim-gated /api/route, per-env isolate memo (1 R2 GET per cold isolate, shared with the 06-07 cron), V5 bbox validation, 200-null on every miss class, ONE best route"
|
||
- "bot/wrangler.jsonc r2_buckets ROAD_GRAPH (first R2 binding; GE5 still exactly ONE kv_namespaces) + config.ts ROAD_GRAPH: R2Bucket"
|
||
- "bot/test/route-privacy.test.mjs re-pin: RP1 = claim-bound local routing (no fetch/proxy, no routing hosts, arm wired to the claim-deriving module), RP2 = workspace allowlist @araharah/{search,routing}/* subpaths only"
|
||
- "routing/scripts/upload-road-graph.mjs + measure-route-cpu.mjs + docs/ROAD-GRAPH.md — the fork contract (build → check → upload → deploy, ODbL attribution, envelope law, CPU-gate decision table)"
|
||
- "routing/src/astar.ts — routeAstar is BIDIRECTIONAL (BH, Ikeda potentials, reverse-CSR WeakMap): provably optimal (A1 625-pair sweep), the A1 ladder step (b) deliverable"
|
||
affects: [06-05 web wiring (createHttpRoutingSource + router-pending UI), 06-07 cron (loadGraph import), phase-6 real-drive gate (CPU budget), v1 exit (the A1 escalation decision)]
|
||
|
||
# Tech tracking
|
||
tech-stack:
|
||
added: [] # zero new runtime dependencies — wrangler R2 is platform, scripts shell the existing CLI
|
||
patterns:
|
||
- "per-isolate graph memo: module-scope WeakMap keyed on env — 1 R2 GET per cold isolate, never reset, cron+fetch share it via loadGraph"
|
||
- "BH bidirectional A*: opposite potentials p_f=(h_f-h_b)/2 make both reductions feasible and the meet-sum constant; alternation is a work knob (heap-size balanced), the stop rule carries optimality"
|
||
- "reverse-CSR per-graph WeakMap (the snap-grid LAW 1 pattern) — in-edges without touching the pinned binary layout"
|
||
- "gate-repin law exercised twice: A7 (06-01 named 06-04 as createHttpRoutingSource's owner) and RP1/RP2 (06-04's own surface), each re-pinned in the change that invalidated them"
|
||
- "budget gates print their measurement (BA9 law) — the CPU gate prints per-route ms + p95 + unreachable probes separately"
|
||
|
||
key-files:
|
||
created:
|
||
- routing/scripts/build-road-graph.mjs
|
||
- routing/scripts/upload-road-graph.mjs
|
||
- routing/scripts/measure-route-cpu.mjs
|
||
- routing/src/http-source.ts
|
||
- bot/src/routing/worker-router.ts
|
||
- bot/test/route-privacy.test.mjs (rewritten re-pin)
|
||
- routing/test/http-source.test.mjs
|
||
- docs/ROAD-GRAPH.md
|
||
- routing/data/.gitignore
|
||
modified:
|
||
- routing/src/index.ts (backend #2 LIVE export + ladder note)
|
||
- routing/src/astar.ts (bidirectional BH + reverse CSR + peekKey)
|
||
- routing/test/astar.test.mjs (A7 re-pin)
|
||
- bot/src/webhook.ts (/api/route arm)
|
||
- bot/src/config.ts (ROAD_GRAPH: R2Bucket)
|
||
- bot/wrangler.jsonc (r2_buckets + law comment)
|
||
- bot/test/webhook.test.mjs (RT1-RT11 block)
|
||
|
||
key-decisions:
|
||
- "The drivable class set includes the five *_link ramp classes — measured NOT optional: without them the graph fragments into motorway islands (7.7% of nodes severed; golden corpus pairs 'unreachable'). Footway/cycleway/service/path remain excluded (Pitfall 1)."
|
||
- "A1 CPU gate FAILS honestly and is ESCALATED: the linked 311k-node graph measured p95 38-93 ms against the 8 ms budget; ladder (a) (drop tertiary/residential) hit 17.8 ms but severed 12/25 pairs — rejected on D-03 correctness and reverted; ladder (b) (bidirectional BH) is sound (A1 equivalence green) but net-zero (the potential split halves each side's steering, cancelling the halved radius); (c) needs a maintainer decision: Workers Paid vs layout-v2 ALT landmarks (still $0 at runtime) vs free-plan-with-honest-degradation."
|
||
- "routeAstar is now bidirectional BH and stays: provably optimal (A1 exhaustive 625-pair Dijkstra equivalence re-proven), no worse on the p95 route class, better on short product routes; the reverse CSR rides a per-graph WeakMap so the pinned binary layout is untouched."
|
||
- "worker-router's graph memo is a module-scope WeakMap keyed on env — the plan's `graphP ??=` law in its per-env-safe form ('or equivalent' per the acceptance criteria): identical production semantics (one R2 GET per cold isolate, never reset, shared with the cron arm) and test-safe."
|
||
- "/api/route unknown destinationId answers 200 null (not 404) — the null contract crosses HTTP so the client's router-pending state has exactly one shape (D-03); off-slug ids are 400 (shape-level malformed, the guidance-envelope posture)."
|
||
- "The happy-path test routes against a purpose-built corridor graph (encodeGraph) because no gazetteer destination lies inside the committed mini-graph bbox; the mini-graph still carries the rejection + honest-null classes via fs."
|
||
|
||
patterns-established:
|
||
- "Maintainer graph-pipeline shell: build → check → upload → measure, each a standalone #!/usr/bin/env node tool with named constants, collect-then-write, and a printed verdict"
|
||
- "The R2 fork contract: bucket name in wrangler.jsonc, object key pinned in worker-router.ts, scripts agree by constant — forks change one name in two places"
|
||
|
||
requirements-completed: [GUID-02] # engine side complete (real rerouting surface live behind the Bearer gate); the A1 CPU escalation rides this requirement — see Deviations/escalation
|
||
|
||
# Metrics
|
||
duration: 47min
|
||
completed: 2026-10-24
|
||
---
|
||
|
||
# Phase 6 Plan 4: Engine-A Server Surface — Road Graph, R2, /api/route, Backend #2 Summary
|
||
|
||
**Engine A's server surface is REAL: a 14.7 MB KL road graph built reproducibly from Overpass (311k nodes, all landmarks one component), a Bearer-gated `/api/route` that routes arbitrary current positions with named turn steps behind an isolate-memoized R2 load, the client's `createHttpRoutingSource` backend #2, RP1/RP2 re-pinned — and the phase's top risk (A1) measured honestly: the free-plan CPU gate FAILS and is escalated with the full ladder evidence.**
|
||
|
||
## Performance
|
||
|
||
- **Duration:** ~47 min
|
||
- **Started:** 2026-10-24T05:15:50Z
|
||
- **Completed:** 2026-10-24T06:03:40Z
|
||
- **Tasks:** 3/3 (task 2 TDD RED→GREEN)
|
||
- **Files:** 14 (9 created, 5 modified)
|
||
|
||
## Accomplishments
|
||
|
||
- **The D-01 build tool exists and the real graph is built** (task 1): `build-road-graph.mjs` derives the bbox mechanically from the committed corpus (gazetteer + golden pairs ± 0.05°, printed), fetches ONE Overpass extract of the drivable classes, dedups nodes by rounded coordinate, encodes through `encodeGraph` (the layout's single authority), and gates: enforced >1 MB ≤80 MB, advisory 30–80 MB band (printed: 14.7 MB below band — review prompt per plan). `--check` re-decodes and re-prints the verdict offline. Artifact: `routing/data/kl-roadgraph.v1.bin` (gitignored, fork-rebuildable), 311,325 nodes / 677,068 directed edges / 21,467 street names / max 110 km/h.
|
||
- **The routing oracle is live and closed** (task 2): `POST /api/route` derives identity from the Bearer claim (401 class, category-only logs), caps bodies at 4096 (413), type+range-validates the origin against `graph.bbox` BEFORE any graph work (400), and answers **200 null** on every miss class — unknown destination, snap miss, disconnected pair, absent graph, corrupt binary — the D-03 router-pending contract crossing HTTP unchanged. The happy path returns ONE `engine-a` option with `deriveSteps`' named/kind-bearing steps and the day-one `cumulativeDistanceM`. Bot suite: RT1–RT11 + H1–H8, RED→GREEN.
|
||
- **The client seam has backend #2** (task 2): `createHttpRoutingSource({endpoint, bearer, fetchImpl})` — slug-guard first, Authorization only when the injected getter holds a token, fail-honest on throw/non-200/malformed/null-body, defensive RouteResult validation (destination match, options 1..3, finite numbers, cumulative 1:1 with points). Exported from `routing/src/index.ts`; A7 re-pinned (06-01's comment named this plan as the owner).
|
||
- **The negative-space gates were re-pinned by the change that invalidated them** (task 2): RP1 now demands claim-bound LOCAL routing (getClaimByToken in worker-router.ts, zero `fetch(`, no routing hostnames, every `/api/route` mention wired to the claim-deriving module); RP2 allowlists `@araharah/search/*` + `@araharah/routing/*` subpath-with-extension imports only; GE5 (exactly ONE kv_namespaces) still green beside the first `r2_buckets` binding.
|
||
- **The fork contract is scripted and documented** (task 3): `upload-road-graph.mjs` (wrangler shell + pre-flight + round-trip verify hint), `measure-route-cpu.mjs` (the printed gate), `docs/ROAD-GRAPH.md` (build→check→upload→deploy, ODbL attribution, envelope law, the CPU-gate decision table).
|
||
- **A1 was measured, not hoped — and the ladder was executed to its decision point** (task 3, see Deviations + escalation below).
|
||
|
||
## Task Commits
|
||
|
||
1. **task 1: road-graph build tool + real KL graph**
|
||
- `d51fd8b` feat(06-04): road-graph build tool — Overpass extract → pinned CSR binary with the D-01 stats gate
|
||
2. **task 2: http-source + worker-router + /api/route + RP re-pins (TDD)**
|
||
- `0abe64e` test(06-04): failing http-source suite H1-H8 + /api/route block RT1-RT11 + RP1/RP2 re-pin (RED)
|
||
- `020eb92` feat(06-04): /api/route engine-A arm + http-source backend #2 — Bearer-gated, honest-null, RP re-pinned (GREEN)
|
||
3. **task 3: R2 upload + CPU measurement gate + the A1 ladder executed**
|
||
- `ea9584d` feat(06-04): R2 upload + A*-CPU measurement gate + the A1 ladder executed to its decision point
|
||
|
||
## Files Created/Modified
|
||
|
||
See frontmatter `key-files`. The graph binary itself is a gitignored artifact by design (D-01: forks build their own).
|
||
|
||
## Decisions Made
|
||
|
||
See `key-decisions`. The three with teeth: `*_link` classes are load-bearing (fragmentation measured); the A1 gate is honestly failing and escalated with evidence; the graph memo is the per-env WeakMap form of the plan's `graphP ??=` law.
|
||
|
||
## Deviations from Plan
|
||
|
||
### Auto-fixed Issues
|
||
|
||
**1. [Rule 1 - Bug] The graph fragmented: `*_link` road classes were missing from the drivable set**
|
||
- **Found during:** task 3 (the CPU measurement exposed it — corpus pairs "unreachable", 7.7% of nodes in severed motorway islands)
|
||
- **Fix:** added motorway/trunk/primary/secondary/tertiary `_link` classes (Overpass regex + way filter + speed table); rebuilt: every landmark snaps into one 305k-node strongly-connected component. Also corrected the enforced floor from 1 KB to the plan's 1 MB.
|
||
- **Files modified:** routing/scripts/build-road-graph.mjs
|
||
- **Commit:** ea9584d
|
||
|
||
**2. [Rule 1 - Bug] The first bidirectional A* had two soundness bugs, both caught by the 06-01 gates**
|
||
- **Found during:** task 3 ladder (b) GREEN — A1 (625-pair Dijkstra equivalence) and A2 (oneway law) went RED
|
||
- **Issue:** the backward branch scanned `u`'s OUT-edges as in-edges (phantom arcs — A1 caught a 6.66s "path" against Dijkstra's 26.67s); then the reduction signs were mirrored-infeasible on both sides (correct paths via the constant meet-sum, but the searches wandered — 19,504 settles with ONE meet probe)
|
||
- **Fix:** per-graph reverse CSR (WeakMap, the snap-grid LAW 1 pattern) for in-edges; reductions in the standard feasible form (`c + p_f(u) − p_f(v)` forward, `c + p_b(u) − p_b(v)` backward); alternation balanced by heap size after measuring that raw-top comparison starves the backward side 19501:3
|
||
- **Files modified:** routing/src/astar.ts
|
||
- **Commit:** ea9584d
|
||
|
||
### The A1 Escalation (plan-directed stop-and-surface — NOT silently closed)
|
||
|
||
The plan's must-have "p95 inside the 10 ms free-plan budget" is **NOT MET**. Measured on the real linked graph (25-pair gate, warm isolate, hrtime around `routeAstar`; run-to-run variance on this box ≈ 2x, best observed p95 ≈ 35-40 ms):
|
||
|
||
| Ladder step | Result |
|
||
|---|---|
|
||
| full graph, unidirectional | p95 ≈ 38 ms — FAIL |
|
||
| (a) drop tertiary/residential | p95 ≈ 18 ms — FAIL **and** 12/25 pairs unreachable (severed the landmark-to-arterial mesh) — rejected on D-03 correctness, reverted |
|
||
| (b) bidirectional BH (shipped) | p95 ≈ 38 ms — FAIL: the potential split halves each side's steering, cancelling the halved radius. Kept: sound, no worse, better on short routes |
|
||
| (c) **DECISION REQUIRED** | Workers Paid ($5/mo, breaks $0) · layout-v2 ALT landmark graph (build-time preprocessing, $0 runtime) · accept free-plan with honest degradation (long reroutes → 1102 → client's fail-honest null → router-pending) |
|
||
|
||
Short product routes (2–8 km — the common reroute) measured 2–8 ms: inside budget. The failures concentrate on 20–30 km cross-metro routes.
|
||
|
||
### Test-side fixes during GREEN (executor bugs, not plan deviations)
|
||
|
||
- The R2 fake initially handed `decodeGraph` a Node Buffer (a view, not an ArrayBuffer) — every graph case degraded honest-null; fixed to an exact ArrayBuffer copy. The corridor fake then needed an `instanceof ArrayBuffer` branch (encodeGraph's product IS an ArrayBuffer).
|
||
|
||
## Known Stubs
|
||
|
||
None. All exports are fully wired. Two honest gaps by design: the R2 bucket is not yet created (account-level activation — the phase's user_setup item, below), and long-route CPU exceeds the free-plan budget (escalated, documented, degrading honestly).
|
||
|
||
## Threat Surface Scan
|
||
|
||
No new surface beyond the plan's `<threat_model>`: `/api/route` is the planned boundary (T-06-01 Bearer-claim 401 class tested; T-06-01b V5 bbox 400 before compute, unknown-dest short-circuit, ONE route — alternatives prohibited; T-06-03 corrupt/absent binary → null; T-06-04 category-only `[route] rejected: <category>` logs asserted verbatim in RT1–RT3). RP1's new positive-space form (no `fetch(` in worker-router, no routing hosts in bot/src) guards the fork surface. The upload script is maintainer-surface only (shells wrangler; never imported by runtime code). No threat flags.
|
||
|
||
## Issues Encountered
|
||
|
||
- **A concurrent writer modified `routing/scripts/build-road-graph.mjs` between my build run and my task-1 commit** — commit `d51fd8b` contains a coherent variant implementation I did not author (my in-session draft's output strings differ from the committed file's). I did not discover the author. Handling: treated the committed variant as the base of record, verified every subsequent edit before staging (`grep` before each `git add`), and re-verified task-2 files at HEAD are my versions (they are). No further interference was observed after 13:28 local. Flagging for the orchestrator in case another session is active on this tree.
|
||
- **Run-to-run CPU variance ≈ 2x** on this machine (p95 37.7 ms vs 93.6 ms for identical code+input across runs) — shared-box load. The escalation conclusion is robust (best-case is still ~5x over budget).
|
||
- **kl-tower→kl-sentral measures "unreachable"**: both landmarks sit in the giant undirected component, but the snap can land on a one-way sink node (the D-05 law: snapping ignores direction; A* enforces it) → directed dead end → honest 200 null. Production UX consideration (retry from the segment's other endpoint) belongs to 06-05's client wiring; noted here so the real-drive gate isn't surprised.
|
||
|
||
## User Setup Required (the phase's cloudflare-r2 item)
|
||
|
||
1. **Enable R2 on the Cloudflare account** (one-time, dashboard-only): Cloudflare dashboard → **R2 → Get started** (requires billing verification — the free tier itself is $0). Wrangler is authenticated but the API answers `code: 10042 "Please enable R2 through the Cloudflare Dashboard"`.
|
||
2. **Create the bucket**: `npx wrangler r2 bucket create araharah-graphs` (or any name — must match `bot/wrangler.jsonc`'s `ROAD_GRAPH.bucket_name`).
|
||
3. **Upload**: `node routing/scripts/upload-road-graph.mjs`, then verify with the round-trip command it prints.
|
||
Forks: the same three steps are `docs/ROAD-GRAPH.md`.
|
||
|
||
## Next Phase Readiness
|
||
|
||
- **06-05 (web wiring)**: `createHttpRoutingSource` is exported and tested — wire the ladder (fixture → engine-a) in `web/src`, and the router-pending state now has a real trigger (200-null on miss + fail-honest on transport error). The one-way-sink retry idea (above) lands here.
|
||
- **06-07 (cron)**: import `loadGraph` from `worker-router.ts` — the SAME per-isolate memo serves both arms (RT10 proves one R2 GET across requests).
|
||
- **The real-drive gate**: budget expectations are now measured facts — short reroutes fit the free plan; cross-metro routes do not (see the escalation).
|
||
- **The A1 decision** (c1/c2/c3) blocks nothing in the remaining phase plans but must be settled before v1 exit; the verifier should treat GUID-02's engine side as delivered-with-escalation.
|
||
|
||
---
|
||
*Phase: 06-turn-by-turn-guidance-live-driving*
|
||
*Completed: 2026-10-24*
|
||
|
||
## Self-Check: PASSED
|
||
|
||
- All 10 created/modified artifacts verified on disk (3 scripts, http-source, worker-router, 2 test files, re-pinned gates, fork docs, gitignore) + the built graph binary (14,749,343 B, `--check` green).
|
||
- All 4 plan commits verified in git log: d51fd8b, 0abe64e (RED), 020eb92 (GREEN), ea9584d — task 2's RED→GREEN gate sequence intact.
|
||
- `npm run routing:test`: 65 passed / 0 failed (A1's 625-pair Dijkstra-equivalence sweep green on the bidirectional A*). `npm test -w bot`: 103 passed / 0 failed (RT1–RT11, GE5 one-kv-namespace, re-pinned RP1/RP2). `routing:typecheck` + `bot:typecheck` clean.
|
||
- STATE.md and ROADMAP.md untouched (their working-tree modifications predate this session — orchestrator-owned writes); only this SUMMARY force-added.
|
||
- Honest gaps recorded, not papered over: the A1 CPU gate FAILS (escalated with ladder evidence, above); the R2 bucket awaits account-level activation (user_setup).
|
||
|
||
## A1 DECISION (maintainer, 2026-10-24)
|
||
|
||
**c3 now, c2 next milestone.** Short product reroutes (2–8 km) run 2–8 ms — inside the
|
||
free plan's 8 ms budget; cross-metro routes (20–30 km, p95 38–93 ms) degrade honestly
|
||
to the router-pending state (engine's 1102 CPU-exhaust path → fail-honest null → the
|
||
designed pending card). Workers Paid (c1) rejected — $0 mandate. ALT landmark
|
||
preprocessing (c2) is the committed upgrade lever for the NEXT milestone (fixes long
|
||
routes while staying $0). The verifier treats GUID-02's engine side as delivered with
|
||
this documented degradation class.
|
||
|
||
R2 activation still pending user dashboard click (code 10042) — non-blocking for
|
||
06-07/06-08; /api/route serves honest nulls until the graph uploads.
|