nigig-org/VALHALLA_RUST_REWRITE_PLAN.md

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/:

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

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