andodeki
fbadab88a6
Some checks failed
Payment domain and storage / isolated-payment-tests (push) Has been cancelled
202 lines
13 KiB
Markdown
202 lines
13 KiB
Markdown
# 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).
|