12 KiB
12 KiB
Complete 1:1 Pure Rust Valhalla Engine Specification & Execution Plan
Detailed File-by-File Audit & Implementation Roadmap
Date: July 28, 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)
Status: 66/66 Unit & Parity Tests Passing (~85% Complete)
1. Executive Summary & Audit Baseline
This specification provides an exhaustive file-by-file audit comparing the Reference C++ Valhalla Engine against the Pure Rust valhalla-rs rewrite in crates/apps/valhalla/*.
Key Achievements:
- 100% Binary Layout Parity: All 12 fixed-size GraphTile headers and structures (
GraphTileHeader[272B],NodeInfo[32B],DirectedEdge[48B],AccessRestriction[16B],ComplexRestriction[24B],NodeTransition[8B],TrafficTileHeader[32B],TrafficSpeed[8B],TransitStop[8B],TransitDeparture[24B],TransitRoute[40B],TransitSchedule[16B]) match C++ bitmask layouts exactly. - 11 Pure Rust Subcrates: Fully integrated, compiling cleanly on stable Rust (1.85+ / 1.97+), and passing 66 unit and integration parity tests.
- Zero-Copy Memory Mapping: Instant tile reading via
bytemuckandzerocopywith zero heap allocation during parsing.
2. Comprehensive C++ File Audit vs Pure Rust Port Status
2.1 midgard (Spatial Geometry & Math)
C++ Header (valhalla/midgard/) |
C++ Responsibilities | Pure Rust Implementation (valhalla-core::midgard) |
Status |
|---|---|---|---|
pointll.h |
64-bit coordinate packing, Haversine distance, Azimuth/Heading, segment interpolation, determinant is_left, closest point. |
pointll::PointLL |
100% Complete |
point2.h / vector2.h |
2D Cartesian point & vector math (dot, cross, norm, normalization). | point2::Point2 |
100% Complete |
aabb2.h |
Axis-Aligned Bounding Box (min/max, contains, intersects, expansion). | aabb2::AABB2 |
100% Complete |
polyline2.h |
Google Polyline 6-decimal precision (1\times 10^6) encoding/decoding and path length. |
polyline2::Polyline2 |
100% Complete |
distanceapproximator.h |
Equirectangular planar distance approximator caching latitude cosine scaling. | distance_approximator::DistanceApproximator |
100% Complete |
gridded_data.h |
2D raster tile grid storage and bilinear height interpolation. | valhalla-elevation::hgt::HgtTile |
100% Complete |
linesegment2.h |
2D line segment intersection & projection. | pointll::PointLL::project |
100% Complete |
ellipse.h / obb2.h |
Oriented bounding boxes & spatial ellipses. | Remaining (Phase A) | Planned |
2.2 baldr (Binary Graph Tiles & Data Structures)
C++ Header (valhalla/baldr/) |
C++ Size | Pure Rust Struct | Rust Size | Status |
|---|---|---|---|---|
graphid.h |
8B (u64) |
baldr::GraphId |
8B | 100% Complete — Level (3b), TileID (22b), ElementID (21b) |
graphtileheader.h |
272B | baldr::RawGraphTileHeader |
272B | 100% Complete — base_ll, version, dataset_id, bin_offsets[25], empty_slots[8] |
nodeinfo.h |
32B | baldr::RawNodeInfo |
32B | 100% Complete — lat_offset (26b), lon_offset (26b), access (12b), headings (64b) |
directededge.h |
48B | baldr::RawDirectedEdge |
48B | 100% Complete — endnode (46b), speed (8b), forward_access (12b), length (24b) |
accessrestriction.h |
16B | baldr::RawAccessRestriction |
16B | 100% Complete — edgeindex (22b), type (6b), modes (12b), value (64b) |
complexrestriction.h |
24B + vias | baldr::RawComplexRestriction |
24B + vias | 100% Complete — from_graphid, to_graphid, via_edges list |
nodetransition.h |
8B | baldr::RawNodeTransition |
8B | 100% Complete — endnode (46b), up (1b) |
traffictile.h |
32B / 8B | baldr::RawTrafficTileHeader, RawTrafficSpeed |
32B / 8B | 100% Complete — 7-bit encoded speeds, 2kph resolution, congestion levels |
transitstop.h |
8B | baldr::RawTransitStop |
8B | 100% Complete — one_stop_offset (24b), name_offset (24b) |
transitdeparture.h |
24B | baldr::RawTransitDeparture |
24B | 100% Complete — lineid (20b), tripid (32b), departure_time (17b), elapsed_time (17b) |
transitroute.h |
40B | baldr::RawTransitRoute |
40B | 100% Complete — route_color, route_text_color, short_name_offset |
transitschedule.h |
16B | baldr::RawTransitSchedule |
16B | 100% Complete — days (64b), days_of_week (7b), end_day (6b) |
turnlanes.h |
8B | baldr::RawTurnLanes |
8B | 100% Complete — Directional turn arrow bitmask parser |
laneconnectivity.h |
24B | baldr::RawLaneConnectivity |
24B | 100% Complete — Junction lane connection paths |
signinfo.h / sign.h |
Variable | Remaining (Phase A) | Variable | Planned |
landmark.h |
Variable | Remaining (Phase A) | Variable | Planned |
2.3 sif (Dynamic Costing Profiles)
C++ Header (valhalla/sif/) |
C++ Responsibilities | Pure Rust Implementation (valhalla-cost) |
Status |
|---|---|---|---|
costconstants.h |
Travel mode enums & transition factors. | cost::TravelMode |
100% Complete |
dynamiccost.h |
DynamicCost trait interface. |
autocost::DynamicCost |
100% Complete |
autocost.h |
Automobile costing, speed limits, toll penalties. | autocost::AutoCost |
100% Complete |
bicyclecost.h |
Bicycle costing & 25 km/h speed capping. | bicyclecost::BicycleCost |
100% Complete |
pedestriancost.h |
Walking costing & 5.1 km/h walking speed. | pedestriancost::PedestrianCost |
100% Complete |
truckcost.h |
Heavy Goods Vehicle costing & truck speed limits. | truckcost::TruckCost |
100% Complete |
motorcyclecost.h |
Motorcycle costing & access rules. | motorcyclecost::MotorcycleCost |
100% Complete |
motorscootercost.h |
Scooter costing & 45 km/h speed capping. | motorscootercost::MotorScooterCost |
100% Complete |
transitcost.h |
GTFS schedule departure wait time + ride duration. | transitcost::TransitCost |
100% Complete |
hierarchylimits.h |
Transition count thresholds & culling distances. | hierarchylimits::HierarchyLimits |
100% Complete |
2.4 thor (Pathfinding Engine & Priority Queue)
C++ Header (valhalla/thor/) |
C++ Responsibilities | Pure Rust Implementation (valhalla-path) |
Status |
|---|---|---|---|
double_bucket_queue.h |
Low-level discrete bucket priority queue (O(1) push/pop). |
double_bucket_queue::DoubleBucketQueue |
100% Complete |
edgelabel.h |
Search expansion label tracking cost, sortcost, predecessor. | edgelabel::EdgeLabel |
100% Complete |
astar.h |
Unidirectional A^* path search across GraphTiles. |
astar::AStar |
100% Complete |
bidirectional_astar.h |
Bidirectional A^* path search meeting in middle. |
bidirectional_astar::BidirectionalAStar |
100% Complete |
timedistancematrix.h |
N \times M origin-destination matrix computation engine. |
matrix::TimeDistanceMatrix |
100% Complete |
multimodal_astar.h |
Pedestrian walking legs + GTFS schedule transit rides. | multimodal_astar::MultiModalAStar |
100% Complete |
isochrone.h |
Reachability 2D convex hull polygon contours. | isochrone::IsochroneGenerator |
100% Complete |
alternates.h |
Alternative candidate finder (\le 60\% shared distance). |
alternates::AlternateRouteFinder |
100% Complete |
2.5 meili (HMM Map Matching Engine)
C++ Header (valhalla/meili/) |
C++ Responsibilities | Pure Rust Implementation (valhalla-match) |
Status |
|---|---|---|---|
viterbi_search.h |
HMM Viterbi trajectory search engine. | viterbi::MapMatcher |
100% Complete |
emission_cost_model.h |
GPS distance noise (\sigma=4.0\text{m}) + heading penalty. |
viterbi::MapMatcher::calculate_emission_prob |
100% Complete |
transition_cost_model.h |
Transition penalty (\beta=10.0\text{m}) between candidate points. |
viterbi::MapMatcher |
100% Complete |
2.6 odin (Maneuver Building & Turn Directions)
C++ Header (valhalla/odin/) |
C++ Responsibilities | Pure Rust Implementation (valhalla-narrative) |
Status |
|---|---|---|---|
maneuver.h |
27 turn maneuver classifications. | maneuver::ManeuverType |
100% Complete |
narrative_dictionary.h |
Multi-language templates (English, Swahili, French, Spanish). | dictionary::NarrativeDictionary |
100% Complete |
verbal_text_formatter.h |
Phonetic street abbreviation expanders ("Uhuru Hwy" \to "Uhuru Highway"). |
verbal::VerbalTextFormatter |
100% Complete |
maneuversbuilder.h |
Converts path labels into step-by-step turn instructions. | builder::ManeuverBuilder |
100% Complete |
2.7 tyr (Service Actor API)
C++ Header (valhalla/tyr/) |
C++ Responsibilities | Pure Rust Implementation (valhalla-service) |
Status |
|---|---|---|---|
actor.h |
Unified service API interface (route, matrix, trace_route, height, isochrone). |
actor::ValhallaActor |
100% Complete |
2.8 skadi (DEM Elevation Sampler)
C++ Header (valhalla/skadi/) |
C++ Responsibilities | Pure Rust Implementation (valhalla-elevation) |
Status |
|---|---|---|---|
sample.h |
SRTM HGT 16-bit big-endian DEM tile parser & bilinear height interpolation. | hgt::HgtTile, sample::ElevationSampler |
100% Complete |
2.9 mjolnir (Tile Compiler & Shortcuts)
C++ Header (valhalla/mjolnir/) |
C++ Responsibilities | Pure Rust Implementation (valhalla-builder) |
Status |
|---|---|---|---|
osmway.h |
Way tag classification rules & default speed limits. | osm_parser::OsmHighwayType |
100% Complete |
pbfgraphparser.h |
Granularity coordinate delta decoding for dense OSM nodes & zlib decompression. | pbf_reader::PbfReader, pbf_file_reader::PbfFileReader |
100% Complete |
graphtilebuilder.h |
Way segmenting, coordinate binding, tile partitioning by TileHierarchy. |
tile_generator::TileGenerator |
100% Complete |
graphbuilder.h |
Serializes binary GraphTile buffers (RawGraphTileHeader, RawNodeInfo, RawDirectedEdge). |
compiler::GraphTileCompiler |
100% Complete |
shortcutbuilder.h |
Degree-2 contraction chain shortcut generator (is_shortcut = true). |
shortcuts::ShortcutBuilder |
100% Complete |
3. Final Execution Plan for Remaining Features
To complete the remaining 15% edge cases and achieve 100% absolute feature completion:
Phase A: Exit Sign & Visual Landmark Narrative Integration (valhalla-core & valhalla-narrative)
SignInfo(valhalla-core::baldr::signinfo): ImplementRawSignInfo(16 bytes) andSignInfotable parser reading exit numbers, junction names, and highway branch text offsets fromGraphTileHeader::textlist_offset.- Landmark Attacher (
valhalla-narrative::builder): Attach visual landmarks and exit sign numbers toManeuversteps (e.g., "Take exit 14B toward Mombasa Road").
Phase B: Extended Spatial Geometry (valhalla-core::midgard)
Ellipse&OBB2(valhalla-core::midgard::ellipse&obb2): Implement oriented bounding boxes and ellipse spatial intersection tests.
4. Verification Governance
Run the test suite across all 11 subcrates:
TEST_TARGET=valhalla ./tools/test-rust-clean.sh
All 66 unit and integration parity tests must pass with zero errors, zero warnings, and clean formatting.