smart_package_tracker/id/

generator.rs

//! Configurable tracking-ID generation.

use alloc::string::{String, ToString};

use super::checksum;
use super::TrackingId;
use crate::error::{Error, Result};

/// Longest prefix we accept. Prefixes exist to make IDs recognisable to
/// humans, not to carry data.
const MAX_PREFIX_LEN: usize = 16;
/// Below this, collisions are guaranteed at trivial volumes.
const MIN_ENTROPY_BITS: u16 = 16;
/// Above this the barcode gets impractically wide for no benefit.
const MAX_ENTROPY_BITS: u16 = 512;

/// A generator must never mint an ID that [`TrackingId::parse`] would reject.
/// The widest policy is the longest prefix, the separator, every entropy
/// character and a check character; if that ever outgrows the format's length
/// limit, this fails the build rather than the round trip.
const _: () = {
    let separator = 1;
    let check_character = 1;
    let widest = MAX_PREFIX_LEN + separator + (MAX_ENTROPY_BITS as usize) / 4 + check_character;
    assert!(
        widest <= super::MAX_LEN,
        "the widest IdGenerator policy must still parse as a TrackingId"
    );
};

/// Which check character, if any, to append to generated IDs.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[non_exhaustive]
pub enum Checksum {
    /// No check character. The ID body is entropy only.
    #[default]
    None,
    /// ISO/IEC 7064 MOD 37,36 check character appended to the body.
    ///
    /// Catches all single-character substitutions and all adjacent
    /// transpositions — the two dominant scanner-misread and typo modes.
    Iso7064Mod37_36,
}

/// Generates [`TrackingId`]s according to a fixed policy.
///
/// # Choosing an entropy width
///
/// IDs are random, so duplicates follow the birthday bound: with `n` IDs drawn
/// from a space of `N = 2^bits`, the chance that at least two collide is
/// approximately `1 - e^(-n²/2N)`.
///
/// | Entropy | Body | 1% collision risk at | 50% collision risk at |
/// |---------|------|----------------------|-----------------------|
/// | 32 bits | 8 hex chars  | ~9,000 IDs       | ~77,000 IDs       |
/// | 48 bits | 12 hex chars | ~2.4 million     | ~20 million       |
/// | 64 bits | 16 hex chars | ~610 million     | ~5.1 billion      |
///
/// The default is 32 bits, which reproduces the familiar `PKG-9ED9285C` shape.
/// **For production systems that will ever issue more than a few thousand IDs,
/// configure 64 bits.** Widening later is a data migration; choosing it now is
/// a one-line change.
///
/// Randomness alone cannot guarantee uniqueness at any width. A durable system
/// should still enforce a unique constraint at the storage layer and retry on
/// conflict.
///
/// # Examples
///
/// ```
/// # #[cfg(feature = "os-rng")]
/// # fn main() -> Result<(), smart_package_tracker::Error> {
/// use smart_package_tracker::{Checksum, IdGenerator};
///
/// let generator = IdGenerator::builder()
///     .prefix("PKG")
///     .entropy_bits(64)
///     .checksum(Checksum::Iso7064Mod37_36)
///     .build()?;
///
/// let id = generator.generate()?;
/// assert!(id.as_str().starts_with("PKG-"));
/// assert_eq!(id.body().len(), 17); // 16 hex characters + 1 check character
/// generator.validate(&id)?;
/// # Ok(())
/// # }
/// # #[cfg(not(feature = "os-rng"))]
/// # fn main() {}
/// ```
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct IdGenerator {
    prefix: String,
    entropy_bits: u16,
    checksum: Checksum,
}

impl Default for IdGenerator {
    /// `PKG-` + 32 bits of entropy, no check character — the `PKG-9ED9285C`
    /// format. See the type-level docs before using this in production.
    fn default() -> Self {
        Self {
            prefix: "PKG".to_string(),
            entropy_bits: 32,
            checksum: Checksum::None,
        }
    }
}

impl IdGenerator {
    /// Start building a generator with a custom policy.
    pub fn builder() -> IdGeneratorBuilder {
        IdGeneratorBuilder::default()
    }

    /// The prefix placed before the separator.
    pub fn prefix(&self) -> &str {
        &self.prefix
    }

    /// Bits of randomness in each generated ID.
    pub fn entropy_bits(&self) -> u16 {
        self.entropy_bits
    }

    /// The configured check-character scheme.
    pub fn checksum(&self) -> Checksum {
        self.checksum
    }

    /// Number of hex characters of entropy in the body.
    fn entropy_chars(&self) -> usize {
        self.entropy_bits as usize / 4
    }

    /// Number of random bytes needed per ID.
    pub fn entropy_bytes(&self) -> usize {
        (self.entropy_bits as usize).div_ceil(8)
    }

    /// Total body length, including any check character.
    fn body_len(&self) -> usize {
        self.entropy_chars() + usize::from(self.checksum != Checksum::None)
    }

    /// Generate an ID using the operating system's cryptographic RNG.
    ///
    /// Requires the `os-rng` feature (enabled by default). Without it, use
    /// [`generate_from_entropy`](Self::generate_from_entropy).
    ///
    /// # Errors
    ///
    /// Returns [`Error::Entropy`] if the OS entropy source is unavailable.
    /// This crate never silently falls back to a weaker source.
    #[cfg(feature = "os-rng")]
    pub fn generate(&self) -> Result<TrackingId> {
        let mut bytes = alloc::vec![0u8; self.entropy_bytes()];
        getrandom::fill(&mut bytes).map_err(|e| Error::Entropy(e.to_string()))?;
        self.generate_from_entropy(&bytes)
    }

    /// Generate an ID from caller-supplied entropy.
    ///
    /// Useful for deterministic tests, for reproducing an ID from stored
    /// bytes, or when the entropy comes from an HSM or a database sequence
    /// rather than the OS.
    ///
    /// # Errors
    ///
    /// Returns [`Error::InsufficientEntropy`] if fewer than
    /// [`entropy_bytes`](Self::entropy_bytes) bytes are supplied. Extra bytes
    /// are ignored.
    pub fn generate_from_entropy(&self, bytes: &[u8]) -> Result<TrackingId> {
        let needed = self.entropy_bytes();
        if bytes.len() < needed {
            return Err(Error::InsufficientEntropy {
                needed,
                got: bytes.len(),
            });
        }

        let mut body = String::with_capacity(self.body_len());
        for byte in &bytes[..needed] {
            body.push(hex_upper(byte >> 4));
            body.push(hex_upper(byte & 0x0f));
        }
        // An entropy width that is not a whole number of bytes leaves one
        // extra nibble; drop it.
        body.truncate(self.entropy_chars());

        if self.checksum == Checksum::Iso7064Mod37_36 {
            let check = checksum::compute(&body)
                .expect("body is uppercase hexadecimal, a subset of the alphabet");
            body.push(check);
        }

        let mut raw = String::with_capacity(self.prefix.len() + 1 + body.len());
        raw.push_str(&self.prefix);
        raw.push(super::SEPARATOR);
        raw.push_str(&body);

        Ok(TrackingId(raw))
    }

    /// Check that `id` was produced by this generator's policy.
    ///
    /// Verifies the prefix, the body length, that the entropy characters are
    /// uppercase hexadecimal, and the check character. Note that this cannot
    /// prove provenance — it only rules out IDs that this policy could never
    /// have produced.
    ///
    /// # Errors
    ///
    /// Returns [`Error::IdPolicyMismatch`] describing the first failure.
    pub fn validate(&self, id: &TrackingId) -> Result<()> {
        if id.prefix() != self.prefix {
            return Err(Error::IdPolicyMismatch {
                reason: alloc::format!(
                    "expected prefix `{}`, found `{}`",
                    self.prefix,
                    id.prefix()
                ),
            });
        }

        let body = id.body();
        if body.len() != self.body_len() {
            return Err(Error::IdPolicyMismatch {
                reason: alloc::format!(
                    "expected a {}-character body, found {}",
                    self.body_len(),
                    body.len()
                ),
            });
        }

        // The generator only ever emits `0-9A-F` here, so anything else could
        // not have come from this policy. The check character is drawn from the
        // wider 36-character alphabet and is verified separately below.
        if let Some(bad) = body[..self.entropy_chars()]
            .chars()
            .find(|c| !c.is_ascii_digit() && !matches!(c, 'A'..='F'))
        {
            return Err(Error::IdPolicyMismatch {
                reason: alloc::format!("body must be uppercase hexadecimal, found `{bad}`"),
            });
        }

        if self.checksum == Checksum::Iso7064Mod37_36 && !checksum::verify(body) {
            return Err(Error::IdPolicyMismatch {
                reason: "check character does not match the body".to_string(),
            });
        }

        Ok(())
    }
}

fn hex_upper(nibble: u8) -> char {
    debug_assert!(nibble < 16);
    b"0123456789ABCDEF"[nibble as usize] as char
}

/// Builder for [`IdGenerator`].
#[derive(Debug, Clone)]
pub struct IdGeneratorBuilder {
    prefix: String,
    entropy_bits: u16,
    checksum: Checksum,
}

impl Default for IdGeneratorBuilder {
    fn default() -> Self {
        let d = IdGenerator::default();
        Self {
            prefix: d.prefix,
            entropy_bits: d.entropy_bits,
            checksum: d.checksum,
        }
    }
}

impl IdGeneratorBuilder {
    /// Set the prefix. Must be 1–16 characters of `A-Z` or `0-9`.
    pub fn prefix(mut self, prefix: impl Into<String>) -> Self {
        self.prefix = prefix.into();
        self
    }

    /// Set the entropy width in bits. Must be a multiple of 4 (one hex
    /// character) between 16 and 512.
    pub fn entropy_bits(mut self, bits: u16) -> Self {
        self.entropy_bits = bits;
        self
    }

    /// Set the check-character scheme.
    pub fn checksum(mut self, checksum: Checksum) -> Self {
        self.checksum = checksum;
        self
    }

    /// Validate the settings and build the generator.
    ///
    /// # Errors
    ///
    /// Returns [`Error::InvalidIdConfig`] if the prefix or entropy width is
    /// out of range.
    pub fn build(self) -> Result<IdGenerator> {
        if self.prefix.is_empty() {
            return Err(Error::InvalidIdConfig(
                "prefix must not be empty".to_string(),
            ));
        }
        // Charset first: `len()` counts bytes, so a multi-byte prefix would
        // otherwise be reported as too long rather than as containing a
        // character that is not allowed at all.
        if let Some(bad) = self.prefix.chars().find(|c| !super::is_body_char(*c)) {
            return Err(Error::InvalidIdConfig(alloc::format!(
                "prefix must consist of `A-Z` and `0-9`, found `{bad}`"
            )));
        }
        if self.prefix.len() > MAX_PREFIX_LEN {
            return Err(Error::InvalidIdConfig(alloc::format!(
                "prefix must be at most {MAX_PREFIX_LEN} characters, got {}",
                self.prefix.len()
            )));
        }
        if self.entropy_bits % 4 != 0 {
            return Err(Error::InvalidIdConfig(alloc::format!(
                "entropy_bits must be a multiple of 4, got {}",
                self.entropy_bits
            )));
        }
        if !(MIN_ENTROPY_BITS..=MAX_ENTROPY_BITS).contains(&self.entropy_bits) {
            return Err(Error::InvalidIdConfig(alloc::format!(
                "entropy_bits must be between {MIN_ENTROPY_BITS} and {MAX_ENTROPY_BITS}, got {}",
                self.entropy_bits
            )));
        }

        Ok(IdGenerator {
            prefix: self.prefix,
            entropy_bits: self.entropy_bits,
            checksum: self.checksum,
        })
    }
}

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

    #[test]
    fn default_reproduces_the_documented_format() {
        let g = IdGenerator::default();
        let id = g
            .generate_from_entropy(&[0x9e, 0xd9, 0x28, 0x5c])
            .expect("four bytes is enough for 32 bits");
        assert_eq!(id.as_str(), "PKG-9ED9285C");
        assert_eq!(id.prefix(), "PKG");
        assert_eq!(id.body(), "9ED9285C");
        g.validate(&id).expect("self-consistent");
    }

    #[test]
    fn generation_is_deterministic_for_fixed_entropy() {
        let g = IdGenerator::default();
        let a = g.generate_from_entropy(&[1, 2, 3, 4]).unwrap();
        let b = g.generate_from_entropy(&[1, 2, 3, 4]).unwrap();
        assert_eq!(a, b);
        assert_eq!(a.as_str(), "PKG-01020304");
    }

    #[test]
    fn checksum_round_trips_and_is_validated() {
        let g = IdGenerator::builder()
            .checksum(Checksum::Iso7064Mod37_36)
            .build()
            .unwrap();
        let id = g.generate_from_entropy(&[0x9e, 0xd9, 0x28, 0x5c]).unwrap();
        assert_eq!(id.body().len(), 9);
        assert!(id.body().starts_with("9ED9285C"));
        g.validate(&id).unwrap();
    }

    #[test]
    fn validate_rejects_a_corrupted_check_character() {
        let g = IdGenerator::builder()
            .checksum(Checksum::Iso7064Mod37_36)
            .build()
            .unwrap();
        let id = g.generate_from_entropy(&[0x9e, 0xd9, 0x28, 0x5c]).unwrap();

        // Flip one character of the entropy; the check character no longer fits.
        let corrupted = TrackingId::parse(&id.as_str().replace("9ED", "9EE")).unwrap();
        assert!(g.validate(&corrupted).is_err());
    }

    #[test]
    fn validate_rejects_a_body_the_policy_could_not_have_produced() {
        // Right prefix, right length, but the generator only ever emits
        // `0-9A-F` — a body of `Z`s can only be corruption or a forgery.
        let g = IdGenerator::default();
        let err = g
            .validate(&TrackingId::parse("PKG-ZZZZZZZZ").unwrap())
            .unwrap_err();
        assert!(matches!(err, Error::IdPolicyMismatch { .. }), "got {err:?}");

        g.validate(&TrackingId::parse("PKG-9ED9285C").unwrap())
            .expect("hexadecimal bodies are still accepted");
    }

    #[test]
    fn validate_still_accepts_a_non_hex_check_character() {
        // The check character comes from the 36-character alphabet, so it may
        // fall outside `0-9A-F` while the entropy before it does not.
        let g = IdGenerator::builder()
            .checksum(Checksum::Iso7064Mod37_36)
            .build()
            .unwrap();
        for seed in 0u8..32 {
            let id = g.generate_from_entropy(&[seed; 4]).unwrap();
            g.validate(&id)
                .unwrap_or_else(|e| panic!("{id} should validate: {e}"));
        }
    }

    #[test]
    fn a_multibyte_prefix_is_reported_as_a_charset_error() {
        // Six characters, but 18 bytes: the length check counts bytes, so
        // running it first would report "at most 16 characters, got 18" for a
        // prefix whose real problem is that none of it is allowed.
        let prefix = "\u{4e2d}\u{6587}\u{4e2d}\u{6587}\u{4e2d}\u{6587}";
        assert_eq!(prefix.chars().count(), 6);
        assert_eq!(prefix.len(), 18);

        let err = IdGenerator::builder().prefix(prefix).build().unwrap_err();
        let message = alloc::format!("{err}");
        assert!(
            message.contains("`A-Z` and `0-9`"),
            "expected a charset error, got: {message}"
        );
    }

    #[test]
    fn validate_rejects_a_foreign_prefix() {
        let g = IdGenerator::default();
        let other = TrackingId::parse("BOX-9ED9285C").unwrap();
        assert!(g.validate(&other).is_err());
    }

    #[test]
    fn wider_entropy_produces_a_longer_body() {
        let g = IdGenerator::builder().entropy_bits(64).build().unwrap();
        assert_eq!(g.entropy_bytes(), 8);
        let id = g.generate_from_entropy(&[0xff; 8]).unwrap();
        assert_eq!(id.body(), "FFFFFFFFFFFFFFFF");
    }

    #[test]
    fn non_byte_aligned_entropy_truncates_cleanly() {
        let g = IdGenerator::builder().entropy_bits(20).build().unwrap();
        assert_eq!(g.entropy_bytes(), 3);
        let id = g.generate_from_entropy(&[0xab, 0xcd, 0xef]).unwrap();
        assert_eq!(id.body(), "ABCDE");
    }

    #[test]
    fn insufficient_entropy_is_an_error_not_a_panic() {
        let g = IdGenerator::builder().entropy_bits(64).build().unwrap();
        assert!(matches!(
            g.generate_from_entropy(&[0; 4]),
            Err(Error::InsufficientEntropy { needed: 8, got: 4 })
        ));
    }

    #[test]
    fn builder_rejects_bad_configuration() {
        assert!(IdGenerator::builder().prefix("").build().is_err());
        assert!(IdGenerator::builder().prefix("pkg").build().is_err());
        assert!(IdGenerator::builder().prefix("PKG-X").build().is_err());
        assert!(IdGenerator::builder().entropy_bits(18).build().is_err());
        assert!(IdGenerator::builder().entropy_bits(8).build().is_err());
        assert!(IdGenerator::builder().entropy_bits(1024).build().is_err());
    }

    #[test]
    fn the_widest_policy_still_parses_as_a_tracking_id() {
        // The generator's limits and the format's length limit were chosen
        // independently; at 512 bits the ID used to come out longer than
        // `TrackingId::parse` would accept, so an ID could be minted and then
        // rejected on the way back out of storage.
        let g = IdGenerator::builder()
            .prefix("ABCDEFGHIJKLMNOP") // MAX_PREFIX_LEN
            .entropy_bits(MAX_ENTROPY_BITS)
            .checksum(Checksum::Iso7064Mod37_36)
            .build()
            .expect("the widest policy must be buildable");

        let id = g.generate_from_entropy(&[0xab; 64]).unwrap();
        assert_eq!(id.body().len(), 129); // 128 hex characters + check character

        let round_tripped = TrackingId::parse(id.as_str())
            .unwrap_or_else(|e| panic!("the widest policy must round trip: {e}"));
        assert_eq!(id, round_tripped);
        g.validate(&round_tripped).unwrap();
    }

    #[test]
    #[cfg(feature = "os-rng")]
    fn every_supported_entropy_width_round_trips() {
        for bits in [MIN_ENTROPY_BITS, 32, 64, 128, 256, 480, MAX_ENTROPY_BITS] {
            let g = IdGenerator::builder().entropy_bits(bits).build().unwrap();
            let id = g.generate().unwrap();
            let parsed = TrackingId::parse(id.as_str())
                .unwrap_or_else(|e| panic!("{bits} bits produced an unparseable id: {e}"));
            assert_eq!(id, parsed);
        }
    }

    #[test]
    #[cfg(feature = "os-rng")]
    fn os_entropy_produces_distinct_well_formed_ids() {
        let g = IdGenerator::builder().entropy_bits(64).build().unwrap();
        let a = g.generate().unwrap();
        let b = g.generate().unwrap();
        assert_ne!(a, b, "64-bit ids should not repeat in two draws");
        g.validate(&a).unwrap();
        g.validate(&b).unwrap();
    }
}