umsh_regiondb/
lib.rs

1//! Reader and lookup for the UMSH geographic region database.
2//!
3//! A `.regiondb` answers one question: given a position, which UMSH regions
4//! should a repeater there normally be configured to accept? All of the hard
5//! geography — nearest-airport partitions, commercial-service classification,
6//! metropolitan boundaries, jurisdiction boundaries, manual corrections —
7//! happens in the build, in `tools/regiondb-build/`. Nothing in this crate
8//! knows how any of it was derived, and the radio knows even less: it is
9//! handed ordinary region strings through the existing repeater configuration
10//! path.
11//!
12//! Only core geometry is stored. A region's expansion margin — the overlap
13//! that lets a repeater near a border serve both sides — is a distance
14//! resolved at lookup time by the sampled-dilation rule in [`sampling`]: the
15//! position itself and a fixed pattern of points around it are tested against
16//! the core polygons, and a hit on any of them is membership. A hit on the
17//! position itself is a core match; on any other sample, an expanded match.
18//!
19//! ```no_run
20//! # fn main() -> Result<(), umsh_regiondb::RegionDbError> {
21//! use umsh_regiondb::RegionDb;
22//!
23//! let database = RegionDb::open("world.regiondb")?;
24//! let result = database.lookup_codes(42.1946, -122.7095)?;
25//! for region in &result.radio_regions {
26//!     println!("{} {}", region.name, region.code);
27//! }
28//! # Ok(())
29//! # }
30//! ```
31//!
32//! The file itself is an ordinary SQLite database, and every implementation
33//! that reads one — this crate, the Python builder, and eventually the
34//! browser — must return identical results for identical positions. That is
35//! not left to good intentions: `regions/tests/conformance.json` is replayed
36//! by all of them, and the geometry codec, grid arithmetic, and sample
37//! pattern here are written to match their Python counterparts operation for
38//! operation.
39
40#![deny(missing_docs)]
41
42pub mod blob;
43pub mod morton;
44pub mod sampling;
45
46use std::collections::{HashMap, HashSet};
47use std::path::Path;
48
49use rusqlite::{Connection, OpenFlags};
50use umsh_core::RegionCode;
51
52pub use blob::GeometryError;
53pub use morton::MortonError;
54
55/// The database format this crate implements.
56pub const FORMAT_VERSION: i64 = 1;
57
58/// Anything that can go wrong opening or querying a region database.
59#[derive(Debug)]
60pub enum RegionDbError {
61    /// The underlying SQLite call failed.
62    Sqlite(rusqlite::Error),
63    /// The file declares a format version this crate does not implement.
64    UnsupportedFormat {
65        /// Version the file claims.
66        found: i64,
67        /// Highest version this crate understands.
68        supported: i64,
69    },
70    /// The file is not a region database at all.
71    NotARegionDatabase,
72    /// The database needs the R-tree candidate path and this SQLite build
73    /// has no R-tree module.
74    MissingSpatialIndex,
75    /// A geometry blob could not be decoded.
76    Geometry(GeometryError),
77    /// A position could not be placed on the lookup grid.
78    Position(MortonError),
79}
80
81impl core::fmt::Display for RegionDbError {
82    fn fmt(&self, formatter: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
83        match self {
84            Self::Sqlite(error) => write!(formatter, "region database error: {error}"),
85            Self::UnsupportedFormat { found, supported } => write!(
86                formatter,
87                "region database declares format version {found}; this build understands \
88                 up to {supported}"
89            ),
90            Self::NotARegionDatabase => write!(formatter, "file is not a region database"),
91            Self::MissingSpatialIndex => write!(
92                formatter,
93                "database has no lookup cache and this SQLite build has no R-tree module"
94            ),
95            Self::Geometry(error) => write!(formatter, "region geometry: {error}"),
96            Self::Position(error) => write!(formatter, "lookup position: {error}"),
97        }
98    }
99}
100
101impl std::error::Error for RegionDbError {}
102
103impl From<rusqlite::Error> for RegionDbError {
104    fn from(error: rusqlite::Error) -> Self {
105        Self::Sqlite(error)
106    }
107}
108
109impl From<GeometryError> for RegionDbError {
110    fn from(error: GeometryError) -> Self {
111        Self::Geometry(error)
112    }
113}
114
115impl From<MortonError> for RegionDbError {
116    fn from(error: MortonError) -> Self {
117        Self::Position(error)
118    }
119}
120
121/// Whether a position falls in a region's own area or only in its expansion
122/// margin.
123#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
124pub enum Membership {
125    /// The position itself is inside the region.
126    Core,
127    /// Only the sampled margin reaches the region — the position is near it,
128    /// within the region's expansion distance.
129    Expanded,
130}
131
132/// One semantic region covering a position.
133#[derive(Clone, Debug, PartialEq)]
134pub struct RegionMatch {
135    /// Database row id.
136    pub region_id: u32,
137    /// Namespaced identifier, such as `iata-airport:SFO`.
138    pub region_key: String,
139    /// Namespace alone. Tooling only; never transmitted.
140    pub namespace: String,
141    /// Code within the namespace.
142    pub code: String,
143    /// The string a radio is configured with.
144    pub radio_name: String,
145    /// Canonical UMSH region code for [`Self::radio_name`].
146    pub wire_code: RegionCode,
147    /// Which layer produced this region.
148    pub layer: String,
149    /// Presentation order relative to other matches.
150    pub priority: i64,
151    /// Core or expanded.
152    pub membership: Membership,
153    /// Position of the generating site, for the layers that have one.
154    pub site: Option<(f64, f64)>,
155    /// Preference order for the suggested default region, if eligible.
156    pub default_rank: Option<i64>,
157}
158
159/// A region as the radio sees it: a name and its 2-byte code.
160#[derive(Clone, Debug, PartialEq, Eq)]
161pub struct RadioRegion {
162    /// The configured region string.
163    pub name: String,
164    /// Its canonical code.
165    pub code: RegionCode,
166}
167
168/// The result of a lookup.
169#[derive(Clone, Debug, PartialEq)]
170pub struct RegionLookup {
171    /// Latitude that was looked up.
172    pub latitude: f64,
173    /// Longitude that was looked up.
174    pub longitude: f64,
175    /// Every semantic match, in presentation order. Empty unless the lookup
176    /// asked for detail.
177    pub matches: Vec<RegionMatch>,
178    /// The deduplicated list suitable for a repeater's region filter.
179    pub radio_regions: Vec<RadioRegion>,
180    /// A narrow region suggested for the packet default tag, if any applies.
181    pub suggested_default_region: Option<RadioRegion>,
182    /// The data release this answer came from.
183    pub dataset_version: String,
184}
185
186#[derive(Clone, Debug)]
187struct RegionRow {
188    region_id: u32,
189    namespace: String,
190    code: String,
191    radio_name: String,
192    wire_code: RegionCode,
193    layer: String,
194    priority: i64,
195    default_rank: Option<i64>,
196    expansion_m: i64,
197    site: Option<(f64, f64)>,
198}
199
200impl RegionRow {
201    fn region_key(&self) -> String {
202        format!("{}:{}", self.namespace, self.code)
203    }
204}
205
206/// An opened region database.
207pub struct RegionDb {
208    connection: Connection,
209    regions: HashMap<u32, RegionRow>,
210    metadata: HashMap<String, String>,
211    format_version: i64,
212    has_lookup_ranges: bool,
213}
214
215impl RegionDb {
216    /// Open a database read-only.
217    pub fn open(path: impl AsRef<Path>) -> Result<Self, RegionDbError> {
218        let connection = Connection::open_with_flags(
219            path,
220            OpenFlags::SQLITE_OPEN_READ_ONLY | OpenFlags::SQLITE_OPEN_URI,
221        )?;
222        Self::from_connection(connection)
223    }
224
225    fn from_connection(connection: Connection) -> Result<Self, RegionDbError> {
226        let format_version: i64 =
227            connection.query_row("PRAGMA user_version", [], |row| row.get(0))?;
228        if format_version < 1 {
229            return Err(RegionDbError::NotARegionDatabase);
230        }
231        if format_version > FORMAT_VERSION {
232            return Err(RegionDbError::UnsupportedFormat {
233                found: format_version,
234                supported: FORMAT_VERSION,
235            });
236        }
237
238        let metadata = connection
239            .prepare("SELECT key, value FROM metadata")?
240            .query_map([], |row| {
241                Ok((row.get::<_, String>(0)?, row.get::<_, String>(1)?))
242            })?
243            .collect::<Result<HashMap<_, _>, _>>()?;
244
245        let regions = connection
246            .prepare(
247                "SELECT id, namespace, code, radio_name, wire_code, layer, priority, \
248                 default_rank, expansion_m, site_lon, site_lat FROM regions",
249            )?
250            .query_map([], |row| {
251                let code: String = row.get(2)?;
252                // A stored radio name is the exception: it exists only where
253                // the wire string differs from the code, which today means
254                // custom regions.
255                let radio_name: Option<String> = row.get(3)?;
256                let longitude: Option<f64> = row.get(9)?;
257                let latitude: Option<f64> = row.get(10)?;
258                Ok(RegionRow {
259                    region_id: row.get::<_, i64>(0)? as u32,
260                    namespace: row.get(1)?,
261                    radio_name: radio_name.unwrap_or_else(|| code.clone()),
262                    code,
263                    wire_code: RegionCode::from_u16(row.get::<_, i64>(4)? as u16),
264                    layer: row.get(5)?,
265                    priority: row.get(6)?,
266                    default_rank: row.get(7)?,
267                    expansion_m: row.get(8)?,
268                    site: longitude.zip(latitude),
269                })
270            })?
271            .map(|row| row.map(|row| (row.region_id, row)))
272            .collect::<Result<HashMap<_, _>, _>>()?;
273
274        let has_lookup_ranges: bool = connection
275            .query_row("SELECT 1 FROM lookup_ranges LIMIT 1", [], |_| Ok(()))
276            .map(|_| true)
277            .or_else(|error| match error {
278                rusqlite::Error::QueryReturnedNoRows => Ok(false),
279                other => Err(other),
280            })?;
281
282        // Without the cache every lookup goes through the R-tree, and a
283        // SQLite built without that module fails only then, as an opaque
284        // "no such module: rtree" from deep inside a query. Probing here
285        // turns that into a named error at the one moment a caller is
286        // prepared to handle one. An empty table is fine — it is the
287        // module that is being tested, not the data.
288        if !has_lookup_ranges {
289            match connection.query_row("SELECT 1 FROM effective_rtree LIMIT 1", [], |_| Ok(())) {
290                Ok(()) | Err(rusqlite::Error::QueryReturnedNoRows) => {}
291                Err(rusqlite::Error::SqliteFailure(_, Some(message)))
292                    if message.contains("no such module") =>
293                {
294                    return Err(RegionDbError::MissingSpatialIndex);
295                }
296                Err(other) => return Err(other.into()),
297            }
298        }
299
300        Ok(Self {
301            connection,
302            regions,
303            metadata,
304            format_version,
305            has_lookup_ranges,
306        })
307    }
308
309    /// The database format version.
310    pub fn format_version(&self) -> i64 {
311        self.format_version
312    }
313
314    /// The geographic data release, such as `2026.08.1`.
315    pub fn dataset_version(&self) -> &str {
316        self.metadata
317            .get("dataset_version")
318            .map(String::as_str)
319            .unwrap_or("unknown")
320    }
321
322    /// Raw metadata, including source attribution and the content hash.
323    pub fn metadata(&self) -> &HashMap<String, String> {
324        &self.metadata
325    }
326
327    /// How many regions the database holds.
328    pub fn region_count(&self) -> usize {
329        self.regions.len()
330    }
331
332    /// Look up a position, returning only what a repeater needs.
333    pub fn lookup_codes(
334        &self,
335        latitude: f64,
336        longitude: f64,
337    ) -> Result<RegionLookup, RegionDbError> {
338        self.lookup(latitude, longitude, false)
339    }
340
341    /// Look up a position, keeping every semantic match for display.
342    pub fn lookup_detailed(
343        &self,
344        latitude: f64,
345        longitude: f64,
346    ) -> Result<RegionLookup, RegionDbError> {
347        self.lookup(latitude, longitude, true)
348    }
349
350    fn lookup(
351        &self,
352        latitude: f64,
353        longitude: f64,
354        detailed: bool,
355    ) -> Result<RegionLookup, RegionDbError> {
356        // Validate the position before any path can silently accept it.
357        self.quantize(latitude, longitude)?;
358        let memberships = self.memberships(latitude, longitude)?;
359        let matches = self.build_matches(memberships);
360
361        let radio_regions = radio_regions(&matches);
362        let suggested = suggested_default(&matches, latitude, longitude);
363        Ok(RegionLookup {
364            latitude,
365            longitude,
366            matches: if detailed { matches } else { Vec::new() },
367            radio_regions,
368            suggested_default_region: suggested,
369            dataset_version: self.dataset_version().to_owned(),
370        })
371    }
372
373    /// Answer with the sampled test against every region, ignoring both the
374    /// lookup cache and the R-tree.
375    ///
376    /// The cache and the candidate filter are optimizations over the same
377    /// core polygons, never a second source of truth, and this is how the
378    /// build proves it.
379    pub fn lookup_exhaustive(
380        &self,
381        latitude: f64,
382        longitude: f64,
383    ) -> Result<RegionLookup, RegionDbError> {
384        self.quantize(latitude, longitude)?;
385        let mut memberships: HashMap<u32, Membership> = HashMap::new();
386        for region_id in self.regions.keys().copied() {
387            if let Some(membership) = self.membership(region_id, latitude, longitude)? {
388                memberships.insert(region_id, membership);
389            }
390        }
391        let matches = self.build_matches(memberships);
392        let radio_regions = radio_regions(&matches);
393        let suggested = suggested_default(&matches, latitude, longitude);
394        Ok(RegionLookup {
395            latitude,
396            longitude,
397            matches,
398            radio_regions,
399            suggested_default_region: suggested,
400            dataset_version: self.dataset_version().to_owned(),
401        })
402    }
403
404    fn build_matches(&self, memberships: HashMap<u32, Membership>) -> Vec<RegionMatch> {
405        let mut matches = Vec::with_capacity(memberships.len());
406        for (region_id, membership) in memberships {
407            let Some(row) = self.regions.get(&region_id) else {
408                continue;
409            };
410            matches.push(RegionMatch {
411                region_id: row.region_id,
412                region_key: row.region_key(),
413                namespace: row.namespace.clone(),
414                code: row.code.clone(),
415                radio_name: row.radio_name.clone(),
416                wire_code: row.wire_code,
417                layer: row.layer.clone(),
418                priority: row.priority,
419                membership,
420                site: row.site,
421                default_rank: row.default_rank,
422            });
423        }
424        matches.sort_by(|first, second| {
425            first
426                .priority
427                .cmp(&second.priority)
428                .then(first.membership.cmp(&second.membership))
429                .then_with(|| first.region_key.cmp(&second.region_key))
430        });
431        matches
432    }
433
434    fn quantize(&self, latitude: f64, longitude: f64) -> Result<(i32, i32), RegionDbError> {
435        Ok((
436            blob::to_e6(morton::normalize_longitude(longitude)?),
437            blob::to_e6(morton::check_latitude(latitude)?),
438        ))
439    }
440
441    /// Whether one position lands in a region's core geometry.
442    fn core_hit(
443        &self,
444        region_id: u32,
445        latitude: f64,
446        longitude: f64,
447    ) -> Result<bool, RegionDbError> {
448        let (longitude_e6, latitude_e6) = self.quantize(latitude, longitude)?;
449        let mut statement = self.connection.prepare_cached(
450            "SELECT geometry, min_lon, min_lat, max_lon, max_lat FROM geometry_parts \
451             WHERE region_id = ?1 ORDER BY id",
452        )?;
453        let mut rows = statement.query([i64::from(region_id)])?;
454        while let Some(row) = rows.next()? {
455            let min_lon: f64 = row.get(1)?;
456            let min_lat: f64 = row.get(2)?;
457            let max_lon: f64 = row.get(3)?;
458            let max_lat: f64 = row.get(4)?;
459            // The stored bounds are the part's own quantized extent, so a
460            // point outside them cannot lie on its boundary either.
461            if longitude_e6 < blob::to_e6(min_lon)
462                || longitude_e6 > blob::to_e6(max_lon)
463                || latitude_e6 < blob::to_e6(min_lat)
464                || latitude_e6 > blob::to_e6(max_lat)
465            {
466                continue;
467            }
468            let payload: Vec<u8> = row.get(0)?;
469            if blob::point_in_rings(&blob::decode(&payload)?, longitude_e6, latitude_e6) {
470                return Ok(true);
471            }
472        }
473        Ok(false)
474    }
475
476    /// Sampled-dilation membership: core, expanded, or not a member.
477    fn membership(
478        &self,
479        region_id: u32,
480        latitude: f64,
481        longitude: f64,
482    ) -> Result<Option<Membership>, RegionDbError> {
483        let expansion = self
484            .regions
485            .get(&region_id)
486            .map(|row| row.expansion_m)
487            .unwrap_or(0);
488        for (index, (sample_lat, sample_lon)) in
489            sampling::sample_positions(latitude, longitude, expansion)
490                .into_iter()
491                .enumerate()
492        {
493            if self.core_hit(region_id, sample_lat, sample_lon)? {
494                return Ok(Some(if index == 0 {
495                    Membership::Core
496                } else {
497                    Membership::Expanded
498                }));
499            }
500        }
501        Ok(None)
502    }
503
504    /// The fast path: cached ranges when present, the R-tree otherwise.
505    fn memberships(
506        &self,
507        latitude: f64,
508        longitude: f64,
509    ) -> Result<HashMap<u32, Membership>, RegionDbError> {
510        if !self.has_lookup_ranges {
511            return self.rtree_memberships(latitude, longitude);
512        }
513
514        let key = morton::key(latitude, longitude)?;
515        let mut statement = self.connection.prepare_cached(
516            "SELECT end_key, base_set_id, candidate_region_ids FROM lookup_ranges \
517             WHERE start_key <= ?1 ORDER BY start_key DESC LIMIT 1",
518        )?;
519        let row = statement
520            .query_row([i64::from(key)], |row| {
521                Ok((
522                    row.get::<_, i64>(0)?,
523                    row.get::<_, i64>(1)?,
524                    row.get::<_, Option<Vec<u8>>>(2)?,
525                ))
526            })
527            .ok();
528
529        let mut memberships = HashMap::new();
530        let Some((end_key, base_set_id, candidates)) = row else {
531            return Ok(memberships);
532        };
533        if i64::from(key) > end_key {
534            return Ok(memberships);
535        }
536
537        let payload: Option<Vec<u8>> = self
538            .connection
539            .prepare_cached("SELECT region_ids FROM region_sets WHERE id = ?1")?
540            .query_row([base_set_id], |row| row.get(0))
541            .ok();
542        // Base-set regions are known members of the whole cell, but core
543        // versus expanded is still a property of the exact position.
544        for region_id in payload
545            .as_deref()
546            .map(decode_region_ids)
547            .unwrap_or_default()
548        {
549            let membership = self
550                .membership(region_id, latitude, longitude)?
551                .unwrap_or(Membership::Expanded);
552            memberships.insert(region_id, membership);
553        }
554        if let Some(candidates) = candidates {
555            for region_id in decode_region_ids(&candidates) {
556                if let Some(membership) = self.membership(region_id, latitude, longitude)? {
557                    memberships.insert(region_id, membership);
558                }
559            }
560        }
561        Ok(memberships)
562    }
563
564    /// Candidates from the padded R-tree boxes, then the sampled test.
565    ///
566    /// Boxes are stored padded by each region's expansion distance and may
567    /// extend past ±180; querying the longitude at all three wrappings is
568    /// what keeps a position on one side of the antimeridian able to see a
569    /// region whose padded box hangs over from the other side.
570    fn rtree_memberships(
571        &self,
572        latitude: f64,
573        longitude: f64,
574    ) -> Result<HashMap<u32, Membership>, RegionDbError> {
575        let (longitude_e6, latitude_e6) = self.quantize(latitude, longitude)?;
576        let lon = blob::from_e6(longitude_e6);
577        let lat = blob::from_e6(latitude_e6);
578
579        let mut candidates: HashSet<u32> = HashSet::new();
580        let mut statement = self.connection.prepare_cached(
581            "SELECT DISTINCT p.region_id FROM effective_rtree r \
582             JOIN geometry_parts p ON p.id = r.part_id \
583             WHERE r.min_lon <= ?1 AND r.max_lon >= ?1 \
584               AND r.min_lat <= ?2 AND r.max_lat >= ?2",
585        )?;
586        for wrapped in [lon - 360.0, lon, lon + 360.0] {
587            let mut rows = statement.query((wrapped, lat))?;
588            while let Some(row) = rows.next()? {
589                candidates.insert(row.get::<_, i64>(0)? as u32);
590            }
591        }
592
593        let mut memberships = HashMap::new();
594        for region_id in candidates {
595            if let Some(membership) = self.membership(region_id, latitude, longitude)? {
596                memberships.insert(region_id, membership);
597            }
598        }
599        Ok(memberships)
600    }
601}
602
603/// Decode a set of region ids stored as varint gaps.
604fn decode_region_ids(data: &[u8]) -> Vec<u32> {
605    let mut identifiers = Vec::new();
606    let mut value: u64 = 0;
607    let mut shift = 0u32;
608    let mut current: u64 = 0;
609    for byte in data {
610        value |= u64::from(byte & 0x7F) << shift;
611        if byte & 0x80 != 0 {
612            shift += 7;
613            continue;
614        }
615        current += value;
616        identifiers.push(current as u32);
617        value = 0;
618        shift = 0;
619    }
620    identifiers
621}
622
623/// Collapse semantic matches onto the list a radio would be given.
624///
625/// Two matches that encode identically are one region as far as the radio is
626/// concerned — the airport and metro senses of `SFO`, say — so the first in
627/// policy order takes the slot.
628fn radio_regions(matches: &[RegionMatch]) -> Vec<RadioRegion> {
629    let mut seen = HashSet::new();
630    let mut out = Vec::new();
631    for entry in matches {
632        if seen.insert(entry.wire_code) {
633            out.push(RadioRegion {
634                name: entry.radio_name.clone(),
635                code: entry.wire_code,
636            });
637        }
638    }
639    out
640}
641
642/// Choose the region to suggest as the packet default.
643///
644/// Only the IATA-derived layers are eligible, and a core match beats an
645/// expanded one from the same layer. Country and state regions are
646/// deliberately never chosen: they are large enough that tagging a flood with
647/// one would broaden its scope far past what an operator setting up a
648/// repeater intends.
649fn suggested_default(
650    matches: &[RegionMatch],
651    latitude: f64,
652    longitude: f64,
653) -> Option<RadioRegion> {
654    matches
655        .iter()
656        .filter(|entry| entry.default_rank.is_some())
657        .min_by(|first, second| {
658            first
659                .default_rank
660                .cmp(&second.default_rank)
661                .then(first.membership.cmp(&second.membership))
662                .then_with(|| {
663                    site_distance(first, latitude, longitude)
664                        .total_cmp(&site_distance(second, latitude, longitude))
665                })
666                .then_with(|| first.region_key.cmp(&second.region_key))
667        })
668        .map(|entry| RadioRegion {
669            name: entry.radio_name.clone(),
670            code: entry.wire_code,
671        })
672}
673
674/// Great-circle distance to a match's generating site, for breaking ties among
675/// overlapping expansion margins.
676///
677/// A sphere is enough here: this only ever orders two candidates that are both
678/// within a hundred kilometers, and the ellipsoidal correction is far too small
679/// to change which is nearer — and, unlike a geodesic, every implementation
680/// reproduces it with plain arithmetic.
681fn site_distance(entry: &RegionMatch, latitude: f64, longitude: f64) -> f64 {
682    let Some((site_longitude, site_latitude)) = entry.site else {
683        return f64::INFINITY;
684    };
685    let (lat1, lat2) = (latitude.to_radians(), site_latitude.to_radians());
686    let delta_lat = lat2 - lat1;
687    let delta_lon = (site_longitude - longitude).to_radians();
688    let haversine =
689        (delta_lat / 2.0).sin().powi(2) + lat1.cos() * lat2.cos() * (delta_lon / 2.0).sin().powi(2);
690    2.0 * haversine.sqrt().asin() * sampling::EARTH_RADIUS_M
691}
umsh_regiondb/lib.rs

umsh_regiondb/
lib.rs
