andodeki/nigig-org
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions 6
nigig-org/REVIEWS/VALHALLA_COMPLETE_PORT_EXECUTION_PLAN.md

9.9 KiB
Raw Permalink Blame History

Valhalla Routing Engine Complete 1:1 Pure Rust Port (valhalla-rs)

Comprehensive Execution Plan for Remaining Subsystems & Feature Gaps

Date: July 27, 2026
Target Repository: https://gitdab.com/andodeki/nigig-org.git (crates/apps/valhalla/*)
Reference C++ Engine: Valhalla Routing Engine (https://github.com/valhalla/valhalla.git)
Objective: Bridge the remaining ~25% feature gap to achieve 100% 1:1 functional, algorithmic, and data parity with C++ Valhalla.

1. Subsystem Gap Analysis & Target Architecture

To transition from the current 75% operational foundation to a 100% complete 1:1 production port, six dedicated completion tranches have been defined:

  ┌────────────────────────────────────────────────────────────────────────┐
  │                   VALHALLA 1:1 PORT COMPLETION ROADMAP                 │
  │                                                                        │
  │  TRANCHE 1: Complex Turn Restrictions & Time Domains (baldr/thor)     │
  │  TRANCHE 2: Multi-Level Hierarchy Transition Edges (tilehierarchy)  │
  │  TRANCHE 3: Historical & Predictive Traffic Profile Tables (baldr)   │
  │  TRANCHE 4: GTFS Public Transit & MultiModal A* Engine (thor/sif)      │
  │  TRANCHE 5: Direct Native OSM PBF Binary Stream Decoder (mjolnir)     │
  │  TRANCHE 6: Multi-Language Narrative & Voice Localization (odin)       │
  └────────────────────────────────────────────────────────────────────────┘

2. Detailed Technical Execution Plan by Tranche

Tranche 1: Complex Turn Restrictions & Time-Dependent Restrictions

  • Reference C++ Headers: valhalla/baldr/complexrestriction.h, valhalla/baldr/accessrestriction.h, valhalla/baldr/timedomain.h, valhalla/mjolnir/complexrestrictionbuilder.h
  • Target Crate: valhalla-core & valhalla-path

Technical Implementation Details:

  1. Data Model (valhalla-core::baldr::complexrestriction):
    • Implement ComplexRestriction struct reading from complex_restriction_forward_offset and complex_restriction_reverse_offset in GraphTileHeader.
    • Multi-edge sequence tracking: from_edge, via_edges list, and to_edge.
    • TimeDomain bitmask parser: day of week, hours of day, conditional vehicle mode masks (e.g., "No left turn between 07:00–09:00 for non-buses").
  2. Search Integration (valhalla-path::astar):
    • Maintain restriction_idx on EdgeLabel.
    • During A^* edge expansion, check if the current edge sequence matches an active ComplexRestriction. If matched and time condition applies, prune the expansion path.
  3. Unit & Integration Test Strategy:
    • Port unit tests from valhalla/test/complexrestriction.cc and valhalla/test/datetime.cc.

Tranche 2: Multi-Level Hierarchy Transition Edges & Level Hopping

  • Reference C++ Headers: valhalla/baldr/tilehierarchy.h, valhalla/mjolnir/hierarchybuilder.h, valhalla/sif/hierarchylimits.h
  • Target Crate: valhalla-core & valhalla-path

Technical Implementation Details:

  1. Hierarchy Level Specification (valhalla-core::baldr::tilehierarchy):
    • Level 0: Highway / Interstate network (4.0^\circ \times 4.0^\circ tiles).
    • Level 1: Arterial road network (1.0^\circ \times 1.0^\circ tiles).
    • Level 2: Local street network (0.25^\circ \times 0.25^\circ tiles).
  2. Transition Edge Handling (valhalla-path::astar):
    • Implement TransitionEdge state handling: Upward transitions (Level 2 -> Level 1 -> Level 0) during initial search expansion, and Downward transitions (Level 0 -> Level 1 -> Level 2) as destination search frontier approaches.
    • HierarchyLimits: Adaptive search radius thresholds preventing search from dropping down to local level during long-distance interstate searches (>500\text{km}).
  3. Performance Impact:
    • Accelerates continent-scale route search latency from 300\text{ms} down to <15\text{ms}.
  4. Unit & Integration Test Strategy:
    • Port unit tests from valhalla/test/tilehierarchy.cc and valhalla/test/hierarchylimits.cc.

Tranche 3: Historical & Predictive Traffic Profile Tables

  • Reference C++ Headers: valhalla/baldr/predictedspeeds.h, valhalla/mjolnir/add_predicted_speeds.h, valhalla/baldr/traffictile.h
  • Target Crate: valhalla-core & valhalla-cost

Technical Implementation Details:

  1. Predicted Speed Table Parser (valhalla-core::baldr::predictedspeeds):
    • Read from predictedspeeds_offset in GraphTileHeader.
    • Each entry contains 5-minute time bucket speed profiles (288 buckets per day, 7 days a week).
  2. Dynamic Cost Integration (valhalla-cost::autocost):
    • Evaluate departure time timestamp: calculate bucket_index = (day_of_week * 288) + (seconds_since_midnight / 300).
    • Retrieve predicted speed for bucket_index and override static free-flow speed in AutoCost::edge_cost().
  3. Unit & Integration Test Strategy:
    • Port unit tests from valhalla/test/predictedspeeds.cc and valhalla/test/predictive_traffic.cc.

Tranche 4: GTFS Public Transit Engine & MultiModal A*

  • Reference C++ Headers: valhalla/baldr/transitstop.h, transitdeparture.h, transitroute.h, transitschedule.h, valhalla/thor/multimodal_astar.h, valhalla/sif/transitcost.h
  • Target Crate: valhalla-core, valhalla-cost, valhalla-path

Technical Implementation Details:

  1. Transit Data Models (valhalla-core::baldr::transit):
    • TransitStop: Platform, station, in/egress location, stop name.
    • TransitDeparture: Schedule departure time, trip ID, route ID, headsign.
    • TransitRoute & TransitSchedule: Service calendar and GTFS route definitions.
  2. Transit Costing & Search (valhalla-cost::transitcost & valhalla-path::multimodal_astar):
    • TransitCost: Waiting time penalty, transfer penalty, mode change penalty (pedestrian \leftrightarrow transit).
    • MultiModalAStar: Time-dependent schedule expansion finding shortest multi-modal trips (Walk \to Bus \to Walk \to Train \to Walk).
  3. Unit & Integration Test Strategy:
    • Port unit tests from valhalla/test/transitstop.cc, transitdeparture.cc, servicedays.cc, and multimodal_astar.cc.

Tranche 5: Direct Native OSM PBF Binary Stream Decoder

  • Reference C++ Headers: valhalla/mjolnir/pbfgraphparser.h, pbfadminparser.h
  • Target Crate: valhalla-builder

Technical Implementation Details:

  1. PBF Stream Reader (valhalla-builder::pbf_reader):
    • Use Pure Rust osmpbf crate to decode BlobHeader, Blob, and PrimitiveBlock chunks directly from raw .osm.pbf file streams.
    • Parallel node/way processing via rayon worker pool.
  2. Graph Tile Partitioning:
    • Extract nodes (lat, lon, tags), ways (highway, maxspeed, access, oneway, surface, bridge, tunnel, turnlanes), and relations (complex turn restrictions, route relations).
    • Group entities by GraphId tile bounding boxes and compile directly into binary .gti GraphTiles via GraphTileCompiler.
  3. Unit & Integration Test Strategy:
    • Port unit tests from valhalla/test/graphparser.cc and valhalla/test/graphbuilder.cc.

Tranche 6: Multi-Language Narrative & Voice Localization Engine

  • Reference C++ Headers: valhalla/odin/narrative_dictionary.h, verbal_text_formatter.h, locales/*.json
  • Target Crate: valhalla-narrative

Technical Implementation Details:

  1. Narrative Dictionary (valhalla-narrative::dictionary):
    • Port Valhalla's ICU narrative JSON dictionaries (locales/en-US.json, locales/sw-KE.json, locales/fr-FR.json, locales/es-ES.json).
    • Instruction templates for turn maneuvers, roundabout exits, highway merges, and destination arrival.
  2. Verbal Text Formatter (valhalla-narrative::verbal):
    • Phonetic text formatting for text-to-speech (TTS) voice instruction strings (e.g. Swahili: "Baada ya mita mia mbili, pinda kulia kwenye Barabara kuu ya Uhuru").
  3. Unit & Integration Test Strategy:
    • Port unit tests from valhalla/test/narrative_dictionary.cc and valhalla/test/verbal_text_formatter.cc.

3. Milestones & Delivery Schedule

Tranche Deliverables & Scope Target Crate Estimated Complexity Target Timeline
Tranche 1 Complex Turn Restrictions & TimeDomains valhalla-core, valhalla-path Medium Weeks 1–2
Tranche 2 Multi-Level Hierarchy Transitions & Level Hopping valhalla-core, valhalla-path High Weeks 3–4
Tranche 3 Historical & Predictive Traffic Profile Lookup Tables valhalla-core, valhalla-cost Medium Weeks 5–6
Tranche 4 GTFS Public Transit Models & MultiModal A* valhalla-core, valhalla-cost, valhalla-path High Weeks 7–8
Tranche 5 Direct Native .osm.pbf Reader & Compiler valhalla-builder Medium Weeks 9–10
Tranche 6 Multi-Language Narrative & Voice Formatter (Swahili/French/etc) valhalla-narrative Low Weeks 11–12

4. Verification & Quality Assurance Governance

  1. Unit Testing Ratchet: Every new tranche must add isolated unit tests under src/ passing TEST_TARGET=valhalla ./tools/test-rust-clean.sh.
  2. Differential Parity Ratchet (valhalla-diff): Outputs must be verified against C++ Valhalla daemon outputs for complex queries (multi-level routes, GTFS transit, time-dependent traffic) with strict assertions:
    • Polyline decoding match: \le 1\times 10^{-5}\text{ deg}
    • Duration match: \le 1\%
    • Distance match: \le 1\text{m}
  3. Zero Security Warnings: All code must remain clean under cargo fmt --check and cargo clippy --all-targets -- -D warnings.