mgrs-convert 0.1.0

//! The MGRS cell type: letter tables, formatting, and parsing.
//!
//! Letter tables follow NGA TM 8358.1, the AA scheme, with the UPS tables and
//! the band row windows fixed against the stage-0 oracle capture and proven by
//! the exhaustive lattice tests.
//!
//! Mechanism M1 lives here: the parser holds no i32. Digit values accumulate
//! in i64, where the precision-11 maximum, under 10^12, sits far below both
//! i64::MAX and 2^53. This module denies `clippy::arithmetic_side_effects`, so
//! every integer operation is a checked, saturating, or Euclidean method.

#![deny(clippy::arithmetic_side_effects)]

use core::fmt;
use core::str::FromStr;

use crate::error::{Error, ParseErrorKind};
use crate::grid;
use crate::latlon::LatLon;
use crate::precision::Precision;
use crate::utmups::UtmUps;

/// UTM latitude band letters, index = band index + 10.
const BAND_LETTERS: &str = "CDEFGHJKLMNPQRSTUVWX";
/// Row letters, one 2,000 km cycle.
const ROW_LETTERS: &str = "ABCDEFGHJKLMNPQRSTUV";
/// Column letter sets by zone number mod 3 (zone 1 uses A to H).
const COL_SETS: [&str; 3] = ["STUVWXYZ", "ABCDEFGH", "JKLMNPQR"];

/// UPS column letters per polar zone letter: (zone letter, first 100 km column
/// index, letters). Captured from the oracle lattice at stage 0.
const UPS_COLS: [(u8, i64, &str); 4] = [
    (b'Y', 13, "RSTUXYZ"),
    (b'Z', 20, "ABCFGHJ"),
    (b'A', 8, "JKLPQRSTUXYZ"),
    (b'B', 20, "ABCFGHJKLPQR"),
];
/// UPS row letters, north cap: rows 13 to 26.
const UPS_N_ROWS: (i64, &str) = (13, "ABCDEFGHJKLMNP");
/// UPS row letters, south cap: rows 8 to 31.
const UPS_S_ROWS: (i64, &str) = (8, "ABCDEFGHJKLMNPQRSTUVWXYZ");

/// Accepted absolute row window per band, index = band index + 10. Rows one
/// outside a window are accepted only through [`row_exception`]. Fixed against
/// the stage-0 acceptance matrix and replayed by the rowband golden test.
const BAND_ROW_WINDOW: [(i64, i64); 20] = [
    (-90, -81), // C
    (-80, -72), // D
    (-71, -63), // E
    (-63, -54), // F
    (-54, -45), // G
    (-45, -36), // H
    (-36, -27), // J
    (-27, -18), // K
    (-18, -9),  // L
    (-9, -1),   // M
    (0, 8),     // N
    (8, 17),    // P
    (17, 26),   // Q
    (26, 35),   // R
    (35, 44),   // S
    (44, 53),   // T
    (53, 62),   // U
    (62, 70),   // V
    (71, 79),   // W
    (80, 94),   // X
];

fn letter_at(table: &str, pos: i64) -> u8 {
    usize::try_from(pos)
        .ok()
        .and_then(|i| table.as_bytes().get(i))
        .copied()
        .unwrap_or(b'?')
}

fn pos_of(table: &str, c: u8) -> Option<i64> {
    table
        .bytes()
        .position(|b| b == c)
        .and_then(|p| i64::try_from(p).ok())
}

/// A letter that exists in the MGRS alphabets: ASCII uppercase minus `I` and `O`.
fn is_mgrs_letter(c: u8) -> bool {
    c.is_ascii_uppercase() && c != b'I' && c != b'O'
}

/// Row-letter cycle shift: even zones are offset by half a cycle.
fn row_shift(zone: u8) -> i64 {
    if zone.rem_euclid(2) == 0 {
        5
    } else {
        0
    }
}

fn band_window(ib: i64) -> (i64, i64) {
    usize::try_from(ib.saturating_add(10))
        .ok()
        .and_then(|i| BAND_ROW_WINDOW.get(i))
        .copied()
        .unwrap_or((0, 0))
}

/// The four column-restricted corner cells one row outside a band window,
/// symmetric between the hemispheres, captured from the stage-0 acceptance
/// matrix (they match GeographicLib's published exceptions).
fn row_exception(cand: i64, ib: i64, col: i64) -> bool {
    let sband = if ib >= 0 {
        ib
    } else {
        ib.saturating_add(1).saturating_neg()
    };
    let srow = if cand >= 0 {
        cand
    } else {
        cand.saturating_add(1).saturating_neg()
    };
    let c0 = col.saturating_sub(1); // 0..=7
    let scol = if c0 <= 3 {
        c0
    } else {
        7_i64.saturating_sub(c0)
    };
    match (srow, sband) {
        (70, 8) => scol >= 2,
        (71, 7) => scol <= 2,
        (79, 9) => scol >= 1,
        (80, 8) => scol <= 1,
        _ => false,
    }
}

/// An MGRS cell, only constructible through the validated paths
/// [`LatLon::to_mgrs`], [`UtmUps::to_mgrs`], and [`str::parse`], so `Display`
/// is total.
///
/// A cell is discrete: `Eq` and `Hash` allow deduplication, and the string form
/// through `Display` and `FromStr` is the serialization.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Mgrs {
    /// 0 for UPS.
    zone: u8,
    north: bool,
    /// Band letter C..X for UTM, or polar zone letter A, B, Y, Z for UPS.
    band: u8,
    /// 100 km column index: easting / 100 km. UTM 1..=8, UPS 8..=31.
    col: i64,
    /// Absolute row index: equator-relative northing / 100 km for UTM
    /// (-90..=94), plain northing / 100 km for UPS (8..=31).
    row: i64,
    /// Easting digits, 0 .. 10^p. i64 by mechanism M1.
    e_digits: i64,
    /// Northing digits, 0 .. 10^p.
    n_digits: i64,
    precision: Precision,
}

impl Mgrs {
    /// The digit-pair count of this reference.
    pub fn precision(&self) -> Precision {
        self.precision
    }

    /// The center of this cell: the southwest corner plus half a cell in each
    /// axis. A corner seeker subtracts half a cell, 10^(5-p)/2 metres, from
    /// each axis of the result.
    pub fn to_utmups(&self) -> UtmUps {
        let p = self.precision.get();
        let e = grid::cell_center_axis(self.col, self.e_digits, p);
        let n = grid::cell_center_axis(self.row, self.n_digits, p);
        if self.zone == 0 {
            UtmUps::raw(0, self.north, e, n)
        } else {
            UtmUps::raw(
                self.zone,
                self.north,
                e,
                grid::frame_northing(n, self.north),
            )
        }
    }

    /// The geodetic coordinate of the cell center.
    ///
    /// ```
    /// use mgrs_convert::Mgrs;
    /// let cell: Mgrs = "18TWL8566411315".parse()?;
    /// let p = cell.to_latlon();
    /// assert!((p.lat() - 40.748333).abs() < 1e-5);
    /// # Ok::<(), mgrs_convert::Error>(())
    /// ```
    pub fn to_latlon(&self) -> LatLon {
        self.to_utmups().to_latlon()
    }

    fn square_letters(&self) -> (u8, u8) {
        if self.zone == 0 {
            let col = UPS_COLS
                .iter()
                .find(|(b, _, _)| *b == self.band)
                .map(|&(_, base, table)| letter_at(table, self.col.saturating_sub(base)))
                .unwrap_or(b'?');
            let (rbase, rtable) = if self.north { UPS_N_ROWS } else { UPS_S_ROWS };
            (col, letter_at(rtable, self.row.saturating_sub(rbase)))
        } else {
            let set = COL_SETS
                .get(usize::from(self.zone.rem_euclid(3)))
                .copied()
                .unwrap_or("");
            let col = letter_at(set, self.col.saturating_sub(1));
            let row = letter_at(
                ROW_LETTERS,
                self.row.saturating_add(row_shift(self.zone)).rem_euclid(20),
            );
            (col, row)
        }
    }
}

impl fmt::Display for Mgrs {
    /// Uppercase, no separators, zone as two digits. Total by construction:
    /// no `unwrap`, no `expect`, no assertion.
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if self.zone > 0 {
            write!(f, "{:02}", self.zone)?;
        }
        let (col, row) = self.square_letters();
        write!(f, "{}{}{}", self.band as char, col as char, row as char)?;
        let width = usize::from(self.precision.get());
        if width > 0 {
            write!(f, "{:0width$}", self.e_digits)?;
            write!(f, "{:0width$}", self.n_digits)?;
        }
        Ok(())
    }
}

/// Forward construction from a validated geodetic coordinate. Total: every
/// valid latitude and longitude is inside the MGRS grid, and the band letter
/// comes from the input latitude (mechanism M5).
pub(crate) fn from_latlon(ll: LatLon, precision: Precision) -> Mgrs {
    let (zone, north, e, n) = ll.utmups_parts();
    if zone == 0 {
        let (e, n) = grid::ups_nudge(north, e, n);
        make_ups(north, e, n, precision)
    } else {
        let (e, n) = grid::utm_nudge(north, e, n);
        make_utm(zone, north, grid::band_index(ll.lat()), e, n, precision)
    }
}

/// Fallible construction from a grid coordinate: the transfer ring outside the
/// strict MGRS coverage gets `Err(OutsideMgrsExtent)` (mechanism M2).
pub(crate) fn from_utmups(u: UtmUps, precision: Precision) -> Result<Mgrs, Error> {
    let outside = Error::OutsideMgrsExtent {
        easting: u.easting(),
        northing: u.northing(),
    };
    if u.zone() == 0 {
        let (e, n) = grid::ups_extent(u.is_north(), u.easting(), u.northing()).ok_or(outside)?;
        Ok(make_ups(u.is_north(), e, n, precision))
    } else {
        let (e, n) = grid::utm_extent(u.is_north(), u.easting(), u.northing()).ok_or(outside)?;
        // The band comes from the exact latitude of the nudged coordinate,
        // never from a northing fold table (mechanism M5).
        let lat = UtmUps::raw(u.zone(), u.is_north(), e, n).latlon_parts().0;
        Ok(make_utm(
            u.zone(),
            u.is_north(),
            grid::band_index(lat),
            e,
            n,
            precision,
        ))
    }
}

fn make_utm(zone: u8, north: bool, ib: i64, e: f64, n_frame: f64, precision: Precision) -> Mgrs {
    let (col, off_e) = grid::axis_fields(e);
    let (row_frame, off_n) = grid::axis_fields(n_frame);
    let row = row_frame.saturating_sub(if north { 0 } else { 100 });
    // The band must agree with the row's hemisphere. The two can only disagree
    // on the equator seam, where a subnormal latitude underflows the band
    // computation; the row, computed from the northing, is the ground truth
    // there.
    let ib = if row < 0 { ib.min(-1) } else { ib.max(0) };
    let band = letter_at(BAND_LETTERS, ib.saturating_add(10));
    Mgrs {
        zone,
        // The cell's hemisphere is canonical, from its own row, not from the
        // input frame: a transfer coordinate 100 km across the equator names
        // a cell in the other hemisphere, and parse must agree with format.
        north: row >= 0,
        band,
        // The clamps cannot move any value that passed the extent check,
        // which compares in the same frame `axis_fields` truncates, so the
        // derived indices are already in range. They keep construction total
        // without a panic path.
        col: col.clamp(1, 8),
        row: row.clamp(-90, 94),
        e_digits: grid::digits_at(off_e, precision.get()),
        n_digits: grid::digits_at(off_n, precision.get()),
        precision,
    }
}

fn make_ups(north: bool, e: f64, n: f64, precision: Precision) -> Mgrs {
    let (col, off_e) = grid::axis_fields(e);
    let (row, off_n) = grid::axis_fields(n);
    let (lo, hi) = if north { (13, 26) } else { (8, 31) };
    let east_half = e >= 2_000_000.0;
    let band = match (north, east_half) {
        (true, true) => b'Z',
        (true, false) => b'Y',
        (false, true) => b'B',
        (false, false) => b'A',
    };
    Mgrs {
        zone: 0,
        north,
        band,
        col: col.clamp(lo, hi),
        row: row.clamp(lo, hi),
        e_digits: grid::digits_at(off_e, precision.get()),
        n_digits: grid::digits_at(off_n, precision.get()),
        precision,
    }
}

impl FromStr for Mgrs {
    type Err = Error;

    /// Parses an MGRS reference: ASCII only, outer whitespace trimmed, case
    /// folded. Precision is derived from the digit count, and odd counts or
    /// counts above 22 are rejected before any digit is read.
    fn from_str(s: &str) -> Result<Mgrs, Error> {
        parse_mgrs(s)
    }
}

fn parse_mgrs(s: &str) -> Result<Mgrs, Error> {
    use ParseErrorKind as K;
    let t = s.trim_matches(|c: char| c.is_ascii_whitespace());
    if t.is_empty() {
        return Err(Error::Parse(K::Empty));
    }
    if !t.is_ascii() {
        return Err(Error::Parse(K::NonAsciiOrWhitespace));
    }
    let bytes = t.as_bytes();
    if bytes.iter().any(|b| b.is_ascii_whitespace()) {
        return Err(Error::Parse(K::NonAsciiOrWhitespace));
    }

    // Zone: up to two leading digits, 1 to 60. "08" is accepted.
    let zone_len = bytes.iter().take_while(|b| b.is_ascii_digit()).count();
    if zone_len > 2 {
        return Err(Error::Parse(K::BadZoneNumber));
    }
    let zone: u8 = {
        let mut z: u8 = 0;
        for b in bytes.iter().take(zone_len) {
            z = z.saturating_mul(10).saturating_add(b.saturating_sub(b'0'));
        }
        if zone_len > 0 && !(1..=60).contains(&z) {
            return Err(Error::Parse(K::BadZoneNumber));
        }
        z
    };

    // Band letter for UTM, polar zone letter for UPS.
    let mut letters = bytes.iter().skip(zone_len);
    let band = match letters.next() {
        Some(b) => b.to_ascii_uppercase(),
        None => return Err(Error::Parse(K::BadBandLetter)),
    };
    if zone > 0 {
        if pos_of(BAND_LETTERS, band).is_none() {
            return Err(Error::Parse(K::BadBandLetter));
        }
    } else if !matches!(band, b'A' | b'B' | b'Y' | b'Z') {
        return Err(Error::Parse(K::BadBandLetter));
    }

    // Two 100 km square letters.
    let (col_c, row_c) = match (letters.next(), letters.next()) {
        (None, _) => return Err(Error::Parse(K::GridZoneOnly)),
        (Some(_), None) => return Err(Error::Parse(K::BadSquareLetters)),
        (Some(c), Some(r)) => (c.to_ascii_uppercase(), r.to_ascii_uppercase()),
    };
    if !col_c.is_ascii_alphabetic() || !row_c.is_ascii_alphabetic() {
        return Err(Error::Parse(K::BadSquareLetters));
    }

    // Digit block: even length, at most 22, digits only.
    let digits = bytes.get(zone_len.saturating_add(3)..).unwrap_or(&[]);
    if let Some(_bad) = digits.iter().find(|b| !b.is_ascii_digit()) {
        return Err(Error::Parse(K::TrailingInput));
    }
    if digits.len() > 22 {
        return Err(Error::Parse(K::TooManyDigits));
    }
    if digits.len().rem_euclid(2) != 0 {
        return Err(Error::Parse(K::OddDigitCount));
    }
    let half = digits.len().div_euclid(2);
    let precision = Precision::new(half as u8).map_err(|_| Error::Parse(K::TooManyDigits))?;
    // Mechanism M1: i64 accumulation. Eleven digits stay under 10^12, far
    // below i64::MAX and 2^53; the checked ops keep the fold total anyway.
    let accumulate = |ds: &[u8]| -> Result<i64, Error> {
        ds.iter()
            .try_fold(0_i64, |acc, b| {
                acc.checked_mul(10)?
                    .checked_add(i64::from(b.saturating_sub(b'0')))
            })
            .ok_or(Error::Parse(K::TooManyDigits))
    };
    let e_digits = accumulate(digits.get(..half).unwrap_or(&[]))?;
    let n_digits = accumulate(digits.get(half..).unwrap_or(&[]))?;

    if zone > 0 {
        // Column letter must belong to this zone's set.
        let set = COL_SETS
            .get(usize::from(zone.rem_euclid(3)))
            .copied()
            .unwrap_or("");
        let col = match pos_of(set, col_c) {
            Some(p) => p.saturating_add(1),
            None if is_mgrs_letter(col_c) => {
                return Err(Error::Parse(K::SquareZoneMismatch));
            }
            None => return Err(Error::Parse(K::BadSquareLetters)),
        };
        // Row letter resolves against the band's row window.
        let row_pos = match pos_of(ROW_LETTERS, row_c) {
            Some(p) => p,
            None => return Err(Error::Parse(K::BadSquareLetters)),
        };
        let ib = pos_of(BAND_LETTERS, band)
            .map(|p| p.saturating_sub(10))
            .unwrap_or(0);
        let residue = row_pos.saturating_sub(row_shift(zone)).rem_euclid(20);
        let (minrow, maxrow) = band_window(ib);
        let start = minrow.saturating_sub(1);
        let row = start.saturating_add(residue.saturating_sub(start).rem_euclid(20));
        let in_window = row >= minrow && row <= maxrow;
        if !in_window && !row_exception(row, ib, col) {
            return Err(Error::Parse(K::SquareBandMismatch));
        }
        Ok(Mgrs {
            zone,
            north: ib >= 0,
            band,
            col,
            row,
            e_digits,
            n_digits,
            precision,
        })
    } else {
        let north = matches!(band, b'Y' | b'Z');
        let col = match UPS_COLS
            .iter()
            .find(|(b, _, _)| *b == band)
            .and_then(|&(_, base, table)| pos_of(table, col_c).map(|p| base.saturating_add(p)))
        {
            Some(c) => c,
            None if is_mgrs_letter(col_c) => {
                return Err(Error::Parse(K::SquareZoneMismatch));
            }
            None => return Err(Error::Parse(K::BadSquareLetters)),
        };
        let (rbase, rtable) = if north { UPS_N_ROWS } else { UPS_S_ROWS };
        let row = match pos_of(rtable, row_c) {
            Some(p) => rbase.saturating_add(p),
            None if is_mgrs_letter(row_c) => {
                return Err(Error::Parse(K::SquareZoneMismatch));
            }
            None => return Err(Error::Parse(K::BadSquareLetters)),
        };
        Ok(Mgrs {
            zone: 0,
            north,
            band,
            col,
            row,
            e_digits,
            n_digits,
            precision,
        })
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn letter_tables_pinned() {
        // Invariant 9 adjacent: alphabet shapes.
        assert_eq!(BAND_LETTERS.len(), 20);
        assert_eq!(ROW_LETTERS.len(), 20);
        for set in COL_SETS {
            assert_eq!(set.len(), 8);
        }
        assert_eq!(UPS_N_ROWS.1.len(), 14);
        assert_eq!(UPS_S_ROWS.1.len(), 24);
        let widths: Vec<usize> = UPS_COLS.iter().map(|(_, _, t)| t.len()).collect();
        assert_eq!(widths, vec![7, 7, 12, 12]);
    }

    #[test]
    fn band_windows_cover_the_grid_contiguously() {
        // Adjacent bands abut or overlap by exactly one shared row, and the
        // whole table spans rows -90 to 94.
        for pair in BAND_ROW_WINDOW.windows(2) {
            if let [(_, hi), (lo2, _)] = pair {
                assert!(*lo2 == *hi || *lo2 == hi.saturating_add(1));
            }
        }
        assert_eq!(BAND_ROW_WINDOW.first(), Some(&(-90, -81)));
        assert_eq!(BAND_ROW_WINDOW.last(), Some(&(80, 94)));
    }
}