152 lines
9.9 KiB
Markdown
152 lines
9.9 KiB
Markdown
# 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`.
|