# Valhalla Routing Engine Pure Rust Rewrite (`valhalla-rs`)
## Comprehensive Architectural Specification and Phased Migration Plan

**Date:** July 27, 2026  
**Target Repository:** `https://gitdab.com/andodeki/nigig-org.git`  
**Reference C++ Engine:** Valhalla Routing Engine (`https://github.com/valhalla/valhalla.git`)  
**Target Application:** `nigig-rider` (Makepad UI Framework Riding App) & `nigig-map`

---

## 1. Executive Summary & Strategic Objectives

The goal of this initiative is to execute a complete, idiomatic, zero-copy Pure Rust rewrite of the **Valhalla Routing Engine** (`valhalla-rs`), eliminating all C++ foreign function interfaces (FFI), heavy C++ dependencies (`libcurl`, `sqlite3`, `boost`, `GEOS`, `rapidjson`), and native toolchain complexities.

By rewriting Valhalla into native Rust and integrating it with the **Makepad UI Framework** in `nigig-org`, we achieve:
1. **Cross-Platform Portability:** Single codebase compiling natively to Android, iOS, Linux, macOS, Windows, and WebAssembly (WASM).
2. **Memory Safety & High Concurrency:** Thread-safe parallel graph search (A*, Bidirectional A*, Isochrones) and zero-cost lock-free tile memory mapping (`memmap2`).
3. **Direct Makepad UI Integration:** Seamless render-loop coupling with `nigig-map` for sub-millisecond route line tessellation, real-time GPS map-matching (`robius-location`), and turn-by-turn navigation HUD rendering in `nigig-rider`.
4. **Isolated Testability:** Full test harness covering unit tests (crate-level), integration tests (golden request/response and C++ differential testing), and interactive Makepad UI tests.

---

## 2. Codebase Audit & C++ Module Mapping

Valhalla's C++ codebase is modularized into distinct libraries. The table below maps every C++ Valhalla subsystem to its corresponding Rust crate in the new `valhalla-rs` workspace:

| C++ Valhalla Subsystem | Description & Responsibilities | Pure Rust Crate (`valhalla-rs`) | Core Dependencies |
| :--- | :--- | :--- | :--- |
| **midgard** | Spatial geometry, bounding boxes, polylines, 7D tiles, distance approximators | `valhalla-core` (`midgard`) | `geo`, `rstar`, `glam` / `dvec2` |
| **baldr** | Graph tile formats, headers, DirectedEdge, NodeInfo, AccessRestrictions, TurnLanes | `valhalla-core` (`baldr`) | `zerocopy`, `bytemuck`, `memmap2`, `bitflags` |
| **sif** | Dynamic costing models (Auto, Bicycle, Pedestrian, Truck, Transit), edge filters | `valhalla-cost` | `serde`, `smallvec` |
| **loki** | Location search, candidate edge snapping, reachability checks, route request validation | `valhalla-search` | `rstar`, `valhalla-core`, `valhalla-cost` |
| **thor** | Pathfinding algorithms (A*, Bidi A*, MultiModal, Isochrones, Time-Distance Matrix) | `valhalla-path` | `petgraph`, `priority-queue`, `rayon` |
| **meili** | HMM Map Matching, Viterbi trace search, candidate emission/transition cost | `valhalla-match` | `nalgebra` / `ndarray`, `valhalla-core` |
| **odin** | Maneuver construction, turn-by-turn directions, voice narratives, multi-locale formatting | `valhalla-narrative` | `unic-langid`, `fluent`, `serde_json` |
| **skadi** | Elevation sampling, DEM/HGT tile parsing | `valhalla-elevation` | `tokio` / `blocking`, `byteorder` |
| **mjolnir** | OSM PBF parsing, graph builder, shortcut builder, transit ingestion, tile compiler | `valhalla-builder` | `osmpbf`, `rusqlite`, `flate2`, `zstd` |
| **tyr** | High-level Service Actor, JSON/Protobuf request parsing and serializer | `valhalla-service` | `prost`, `serde_json`, `tokio` |
| **N/A (New)** | Makepad UI integration, route tessellation overlay, guidance HUD widgets | `valhalla-makepad` | `makepad-widgets`, `nigig-map`, `robius-location` |

---

## 3. Core Technical Innovations in `valhalla-rs`

### 3.1 Zero-Copy Bit-Packed GraphTile Memory Mapping
C++ Valhalla relies on fixed-size structs with bit-fields (`DirectedEdge`, `NodeInfo`, `GraphHeader`) memory-mapped directly from disk. In Rust:
- We use `#[repr(C, packed)]` combined with `zerocopy::FromBytes` / `zerocopy::AsBytes` or safe bit-masking getter methods.
- `memmap2::Mmap` is used to load GraphTiles instantaneously without heap allocation.
- Dynamic attributes (`EdgeInfo`, street names, sign text) use offset-based relative offsets within tile buffers, avoiding pointer swizzling.

### 3.2 Lock-Free Graph Tile Cache & Tile Reader
- Graph tiles are indexed by 64-bit `GraphId` (level, tile_id, element_index).
- A lock-free LRU cache (`dashmap` + custom ring buffer eviction) handles tile access across concurrent worker threads during pathfinding.

### 3.3 Zero-Allocation Pathfinding Queue
- `valhalla-path` implements a double-bucket priority queue (`DoubleBucketQueue`) for A* search, eliminating heap re-allocations during Dijkstra / A* expansions.

---

## 4. Comprehensive Testing Strategy

To guarantee 100% equivalence and stability, the rewrite employs a **3-Tier Testing Architecture**:

```
 ┌────────────────────────────────────────────────────────────────────────┐
 │                      TIER 1: UNIT TESTS (Cargo)                        │
 │  • Crate-isolated math, geometry, tile parsing, cost functions        │
 └──────────────────────────────────┬─────────────────────────────────────┘
                                    │
 ┌──────────────────────────────────▼─────────────────────────────────────┐
 │                 TIER 2: INTEGRATION & DIFFERENTIAL TESTS               │
 │  • C++ Valhalla vs Rust Valhalla Golden Parity Checks                  │
 │  • Pinpoint route tests (Nairobi PBF & sample datasets)                │
 └──────────────────────────────────┬─────────────────────────────────────┘
                                    │
 ┌──────────────────────────────────▼─────────────────────────────────────┐
 │                TIER 3: MAKEPAD UI & INTERACTIVE WIDGET TESTS           │
 │  • Headless & GUI event simulation in nigig-rider / nigig-map          │
 │  • Route tessellation, gesture panning, live GPS re-routing HUD        │
 └────────────────────────────────────────────────────────────────────────┘
```

### 4.1 Tier 1: Unit Tests (Crate-Level Isolation)
- **Geometry & Math (`valhalla-core`):** Porting tests from `valhalla/test/pointll.cc`, `aabb2.cc`, `polyline2.cc`, `distanceapproximator.cc`.
- **Graph Tile Parsing (`valhalla-core`):** Porting `graphtile.cc`, `graphid.cc`, `directededge.cc`, `nodeinfo.cc`.
- **Costing (`valhalla-cost`):** Porting cost calculation logic for auto, bicycle, pedestrian under varied speeds, surface types, grade penalties, and turning restrictions.
- **Test Runner Integration:** Works with `nigig-org/tools/test-rust-clean.sh` for isolated, clean execution in CI.

### 4.2 Tier 2: Integration & Differential Parity Tests
- **Golden Request Suite:** Utilizing Valhalla's `test/pinpoints` test cases (e.g. `instructions`, `turn_lanes`).
- **C++ Differential Harness (`valhalla-diff`):**
  1. Input: Sample OSM graph (e.g., Nairobi, Kenya PBF extract).
  2. Action: Issue identical JSON route requests (`/route`, `/matrix`, `/trace_attributes`) to C++ Valhalla daemon and `valhalla-rs`.
  3. Assertion: Verify exact route shape (polyline decode match within 1e-5 degrees), travel duration match (within 1% threshold), distance match (exact meters), maneuver counts, and turn instructions.

### 4.3 Tier 3: Makepad UI & Interactive Integration Tests
- **Route Line Tessellation Verification:** Test `nigig-map`'s `RenderPass` to ensure route geometries tessellate into vertex/index buffers cleanly without GPU spikes or visual gaps.
- **Interactive Gesture Simulation:** Test origin/destination pin dropping, route calculation trigger, and dynamic route line recalculation on drag.
- **Simulated GPS Guidance Loop (`nigig-rider`):**
  - Inject simulated `robius-location` GPS points along a path.
  - Test `valhalla-match` (Viterbi) snapping driver position to route edge.
  - Test off-route detection threshold (> 25 meters deviation) and auto-reroute dispatch in < 50ms.

---

## 5. Integration Architecture in `nigig-org`

### 5.1 Workspace Structure in `nigig-org`
Add pure crates under `crates/valhalla/`:
```text
nigig-org/
├── Cargo.toml (workspace members update)
├── crates/
│   ├── valhalla/
│   │   ├── core/           # Geometry, GraphTile, GraphReader
│   │   ├── cost/           # Auto, Bicycle, Pedestrian costing
│   │   ├── search/         # Location snapping, Loki candidates
│   │   ├── path/           # Thor A*, Bidi A*, Matrix
│   │   ├── match/          # Meili HMM / Viterbi map matching
│   │   ├── narrative/      # Odin maneuvers & guidance
│   │   ├── service/        # Actor API, JSON parser
│   │   └── makepad/        # Makepad widget, route render overlay
│   ├── apps/
│   │   ├── map/            # nigig-map (renders MVT tiles + valhalla route overlay)
│   │   └── nigig-rider/    # Riding app UI (book, track, driver dispatch HUD)
```

### 5.2 Flow Diagram: `nigig-rider` Navigation Pipeline

```
  [User Pin Drop / Search]
            │
            ▼
    [valhalla-service Actor] ─── (Locate candidate edges in GraphTile)
            │
            ▼
    [valhalla-path (Bidi A*)] ─── (Search tiles in memory/disk mmap)
            │
            ▼
    [valhalla-narrative] ────── (Build TripDirections & Maneuvers)
            │
            ▼
 ┌─────────────────────────────────────────────────────────────┐
 │                     MAKEPAD UI LAYER                        │
 │                                                             │
 │  1. `nigig-map`: Convert polylines -> GPU tessellated mesh  │
 │  2. `nigig-rider`: Render Step-by-Step HUD & ETA Card       │
 │  3. `robius-location` Stream -> `valhalla-match` (Viterbi)  │
 └─────────────────────────────────────────────────────────────┘
```

---

## 6. Phased Implementation Roadmap

### Phase 1: Foundation & Core Data Structures (`valhalla-core`)
- **Deliverables:**
  - `valhalla-core` crate with `PointLL`, `Polyline`, `GraphId`, `GraphHeader`, `NodeInfo`, `DirectedEdge`, `EdgeInfo`.
  - Zero-copy GraphTile deserializer reading existing C++ Valhalla binary tiles.
  - Unit tests ported from `graphtile.cc`, `graphid.cc`, `directededge.cc`.
- **Target Timeline:** Weeks 1–2

### Phase 2: Costing Models & Pathfinding Engine (`valhalla-cost` + `valhalla-path`)
- **Deliverables:**
  - `valhalla-cost` implementing `AutoCost`, `BicycleCost`, `PedestrianCost`.
  - `valhalla-path` implementing `DoubleBucketQueue`, Unidirectional A*, Bidirectional A*, and Time-Distance Matrix.
  - Unit & Integration tests using sample `test/data` graph tiles.
- **Target Timeline:** Weeks 3–4

### Phase 3: Search, Map Matching & Guidance (`valhalla-search`, `valhalla-match`, `valhalla-narrative`)
- **Deliverables:**
  - `valhalla-search` candidate edge snapping (`rstar` spatial index).
  - `valhalla-match` HMM Viterbi trace matching.
  - `valhalla-narrative` turn-by-turn maneuver builder and English/Swahili voice string formatter.
  - Integration parity test suite comparing results against C++ Valhalla daemon outputs.
- **Target Timeline:** Weeks 5–6

### Phase 4: Makepad UI Bridge & `nigig-rider` Integration (`valhalla-makepad`)
- **Deliverables:**
  - `valhalla-makepad` widget bridge.
  - Route polyline GPU tessellation overlay in `nigig-map`.
  - Integration with `nigig-rider/src/rider_frame/pages/book.rs` and `track.rs`.
  - Automated Makepad UI tests for route planning, pin dropping, and live GPS tracking.
- **Target Timeline:** Weeks 7–8

### Phase 5: Tile Builder (`valhalla-builder`) & Performance Optimization
- **Deliverables:**
  - OSM PBF graph builder in Pure Rust (`osmpbf` + `rusqlite`).
  - Shortcut edge generator (Contraction Hierarchies / Multi-level hierarchy).
  - Benchmark suite (`criterion.rs`) verifying < 5ms routing latency for mobile networks.
- **Target Timeline:** Weeks 9–10

---

## 7. Verification & Compliance Checklist

- [x] Valhalla C++ repository cloned and analyzed (`valhalla/`).
- [x] Target repository `nigig-org` cloned and inspected (`nigig-rider`, `nigig-map`, `workflow.md`).
- [x] Pure Rust architecture defined with zero C++ dependencies.
- [x] 3-tier testing strategy specified (Unit, Integration Parity, Makepad UI).
- [x] Pure domain crate testing workflow aligned with `tools/test-rust-clean.sh`.
- [x] Strict adherence to `workflow.md` (no hardcoded secrets, focused commits, clean workspace).