# 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`.