axond 0.3.8

//! Identity: time-ordered UUIDv7 values, typed ids, and readable slugs.
//!
//! Two things are kept apart on purpose:
//!
//! - **Identity** is a [`Uuid7`]. It is assigned once, never reused, never
//!   interpreted, and never rendered to an operator as something they may edit.
//!   Every durable thing — tenants, projects, resources, revisions, mutations,
//!   audit events — is identified by one, in its own Rust type, so an id for one
//!   kind cannot be passed where another is expected or parsed from another's
//!   text form.
//! - **A slug** is a readable, tenant-scoped name. It can be renamed, it can be
//!   reused after a delete, and nothing joins on it. A manifest joins on ids
//!   precisely so a rename is not a re-creation.
//!
//! UUIDv7 rather than UUIDv4 because the leading 48 bits are a Unix
//! millisecond timestamp (RFC 9562 §5.7): ids sort in creation order, so
//! "revisions in order" is a byte comparison, and #165's Postgres index stays
//! append-mostly instead of scattering inserts across a random key space.
//! [`Uuid7Generator`] additionally makes ordering *strict* — see
//! [`Uuid7Generator::next`].
//!
//! Strict only *per generator*, though, so id order is a convenience and not the
//! authority on "which revision is newest": across a restart or a second replica
//! it degrades to wall-clock agreement. The store answers that question from
//! publication order (the oracle from its `order` vector, #165 from a sequence or
//! the transaction that assigned it), never from comparing ids.

use std::fmt;
use std::sync::Mutex;
use std::time::{SystemTime, UNIX_EPOCH};

use ring::rand::{SecureRandom, SystemRandom};

/// A UUID version 7: 48-bit big-endian Unix millisecond timestamp, version and
/// variant bits, and randomness.
///
/// Ordering is byte-lexicographic, which for this layout is timestamp order
/// first and then the intra-millisecond sequence, so `<` on two ids generated by
/// the same [`Uuid7Generator`] means "created before".
///
/// `Debug` renders the text form rather than the byte array, because an id in a
/// log line or an assertion failure is only useful if it is the same string an
/// operator can search for.
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Uuid7([u8; 16]);

impl fmt::Debug for Uuid7 {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Display::fmt(self, f)
    }
}

/// Why a UUIDv7 could not be accepted.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum InvalidUuid7 {
    #[error("`{0}` is not a hyphenated 8-4-4-4-12 UUID")]
    Shape(String),
    #[error("`{0}` contains a character that is not a lowercase hex digit")]
    Digit(String),
    #[error("UUID version is {version}, but only version 7 is accepted")]
    Version { version: u8 },
    #[error("UUID variant bits are {variant:#04b}, but only the RFC 9562 variant is accepted")]
    Variant { variant: u8 },
    #[error("timestamp {millis} does not fit the 48-bit UUIDv7 timestamp field")]
    Timestamp { millis: u64 },
    #[error("sequence {sequence} does not fit the 12-bit UUIDv7 sequence field")]
    Sequence { sequence: u16 },
}

impl Uuid7 {
    /// The number of hex digits and hyphens in the text form.
    const TEXT_LEN: usize = 36;

    /// Build an id from its parts, setting the version and variant bits.
    ///
    /// This is the only constructor that does not consult a clock, so it is what
    /// fixtures and #165's stored-row round trips use: identical parts produce
    /// identical bytes.
    pub fn from_parts(millis: u64, sequence: u16, entropy: u64) -> Result<Self, InvalidUuid7> {
        if millis >= 1 << 48 {
            return Err(InvalidUuid7::Timestamp { millis });
        }
        if sequence >= 1 << 12 {
            return Err(InvalidUuid7::Sequence { sequence });
        }
        let mut bytes = [0u8; 16];
        bytes[..6].copy_from_slice(&millis.to_be_bytes()[2..]);
        // 4-bit version 7, then the 12-bit sequence in `rand_a`.
        bytes[6] = 0x70 | ((sequence >> 8) as u8 & 0x0f);
        bytes[7] = (sequence & 0xff) as u8;
        bytes[8..].copy_from_slice(&entropy.to_be_bytes());
        // Two-bit RFC 9562 variant over the top of `rand_b`'s first byte.
        bytes[8] = (bytes[8] & 0x3f) | 0x80;
        Ok(Self(bytes))
    }

    /// Accept raw bytes, rejecting anything that is not a UUIDv7.
    ///
    /// Used when reading a stored id back: a row holding a v4 (or a zeroed
    /// column) is a corrupt row, not an id, and must not be silently carried
    /// into a manifest.
    pub fn from_bytes(bytes: [u8; 16]) -> Result<Self, InvalidUuid7> {
        let version = bytes[6] >> 4;
        if version != 7 {
            return Err(InvalidUuid7::Version { version });
        }
        let variant = bytes[8] >> 6;
        if variant != 0b10 {
            return Err(InvalidUuid7::Variant { variant });
        }
        Ok(Self(bytes))
    }

    pub const fn as_bytes(&self) -> &[u8; 16] {
        &self.0
    }

    /// The embedded creation time, in Unix milliseconds.
    pub fn timestamp_millis(&self) -> u64 {
        let mut millis = [0u8; 8];
        millis[2..].copy_from_slice(&self.0[..6]);
        u64::from_be_bytes(millis)
    }

    /// The 12-bit intra-millisecond sequence.
    pub fn sequence(&self) -> u16 {
        u16::from(self.0[6] & 0x0f) << 8 | u16::from(self.0[7])
    }

    /// Parse the lowercase hyphenated text form.
    ///
    /// Lowercase only, and hyphenated only: one text form means the text form
    /// can be compared and used as a map key without normalizing first.
    pub fn parse(text: &str) -> Result<Self, InvalidUuid7> {
        if text.len() != Self::TEXT_LEN
            || text.as_bytes()[8] != b'-'
            || text.as_bytes()[13] != b'-'
            || text.as_bytes()[18] != b'-'
            || text.as_bytes()[23] != b'-'
        {
            return Err(InvalidUuid7::Shape(text.to_owned()));
        }
        let mut bytes = [0u8; 16];
        let mut digits = text.bytes().filter(|byte| *byte != b'-');
        for byte in &mut bytes {
            let (high, low) = (digits.next(), digits.next());
            let (Some(high), Some(low)) = (high, low) else {
                return Err(InvalidUuid7::Shape(text.to_owned()));
            };
            let nibble = |digit: u8| match digit {
                b'0'..=b'9' => Some(digit - b'0'),
                b'a'..=b'f' => Some(digit - b'a' + 10),
                _ => None,
            };
            let (Some(high), Some(low)) = (nibble(high), nibble(low)) else {
                return Err(InvalidUuid7::Digit(text.to_owned()));
            };
            *byte = high << 4 | low;
        }
        Self::from_bytes(bytes)
    }
}

impl fmt::Display for Uuid7 {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for (index, byte) in self.0.iter().enumerate() {
            if matches!(index, 4 | 6 | 8 | 10) {
                f.write_str("-")?;
            }
            write!(f, "{byte:02x}")?;
        }
        Ok(())
    }
}

/// A source of strictly increasing UUIDv7 values.
///
/// RFC 9562 permits, but does not require, monotonicity within a millisecond.
/// The control plane requires it: a revision chain whose ids can tie is a chain
/// whose order depends on a tiebreaker somewhere else. So the generator holds
/// the last `(millisecond, sequence)` it issued and
///
/// - advances the sequence when the clock has not moved,
/// - carries into the next millisecond when the 12-bit sequence is exhausted,
/// - and keeps issuing from the last millisecond it used when the clock moves
///   *backwards* (NTP steps, virtualized clocks), rather than issuing an id that
///   sorts before one it already returned.
pub struct Uuid7Generator {
    random: SystemRandom,
    last: Mutex<(u64, u16)>,
}

impl Uuid7Generator {
    const MAX_SEQUENCE: u16 = (1 << 12) - 1;
    /// The largest value the 48-bit timestamp field holds.
    const MAX_MILLIS: u64 = (1 << 48) - 1;

    pub fn new() -> Self {
        Self {
            random: SystemRandom::new(),
            last: Mutex::new((0, 0)),
        }
    }

    /// The next id: strictly greater than every id this generator has returned.
    ///
    /// A wildly wrong host clock degrades to a saturated timestamp rather than a
    /// panic: issuing ids is on the publication path, and a machine whose clock
    /// reads the year 10889 should still be able to record a mutation.
    pub fn next(&self) -> Uuid7 {
        let now = SystemTime::now()
            .duration_since(UNIX_EPOCH)
            .map_or(0, |since| {
                u64::try_from(since.as_millis()).unwrap_or(Self::MAX_MILLIS)
            })
            .min(Self::MAX_MILLIS);
        let (millis, sequence) = {
            let mut last = self.last.lock().expect("uuid generator is not poisoned");
            let (last_millis, last_sequence) = *last;
            let next = if now > last_millis {
                (now, 0)
            } else if last_sequence < Self::MAX_SEQUENCE {
                (last_millis, last_sequence + 1)
            } else {
                // Saturating rather than wrapping: at the end of the
                // representable range ids stop advancing, which is a
                // degradation, where wrapping would hand out an id that sorts
                // before ones already issued.
                (last_millis.saturating_add(1).min(Self::MAX_MILLIS), 0)
            };
            *last = next;
            next
        };
        let mut entropy = [0u8; 8];
        self.random
            .fill(&mut entropy)
            .expect("system random generator must be available");
        Uuid7::from_parts(millis, sequence, u64::from_be_bytes(entropy))
            .expect("timestamp and sequence are clamped to their fields above")
    }
}

impl Default for Uuid7Generator {
    fn default() -> Self {
        Self::new()
    }
}

impl fmt::Debug for Uuid7Generator {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("Uuid7Generator")
    }
}

/// Declare a typed id: a distinct Rust type over a [`Uuid7`] with a prefixed
/// text form.
///
/// The prefix is what makes the *text* form typed as well as the Rust form:
/// `ten_…` cannot be parsed as a project id, so an id pasted into the wrong
/// admin field is a parse error rather than a lookup that finds nothing (or,
/// worse, finds something).
macro_rules! typed_id {
    ($(#[$doc:meta])* $name:ident, $prefix:literal) => {
        $(#[$doc])*
        #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
        pub struct $name(Uuid7);

        /// Renders the prefixed text form, so a `Debug`-formatted structure
        /// carries ids an operator can search for.
        impl fmt::Debug for $name {
            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
                fmt::Display::fmt(self, f)
            }
        }

        impl $name {
            /// The text-form prefix that distinguishes this id from every other.
            pub const PREFIX: &'static str = $prefix;

            pub const fn new(id: Uuid7) -> Self {
                Self(id)
            }

            pub const fn uuid(&self) -> Uuid7 {
                self.0
            }

            /// Parse the prefixed text form.
            pub fn parse(text: &str) -> Result<Self, InvalidId> {
                let uuid = text.strip_prefix(Self::PREFIX).ok_or_else(|| InvalidId::Prefix {
                    expected: Self::PREFIX,
                    found: text.to_owned(),
                })?;
                Ok(Self(Uuid7::parse(uuid)?))
            }
        }

        impl fmt::Display for $name {
            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
                write!(f, "{}{}", Self::PREFIX, self.0)
            }
        }
    };
}

/// Why a typed id could not be parsed.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum InvalidId {
    #[error("`{found}` is not prefixed `{expected}`, so it identifies something else")]
    Prefix {
        expected: &'static str,
        found: String,
    },
    #[error(transparent)]
    Uuid(#[from] InvalidUuid7),
}

typed_id!(
    /// A tenant: the isolation boundary every scoped resource hangs from.
    TenantId,
    "ten_"
);
typed_id!(
    /// A project inside a tenant.
    ProjectId,
    "prj_"
);
typed_id!(
    /// A durable resource, independent of which of its versions is referenced.
    ResourceId,
    "res_"
);
typed_id!(
    /// A published revision of desired state.
    RevisionId,
    "rev_"
);
typed_id!(
    /// One administrative mutation, whatever number of resources it touched.
    MutationId,
    "mut_"
);
typed_id!(
    /// One audit event.
    AuditEventId,
    "aud_"
);

/// A readable, scope-unique name for a resource.
///
/// Deliberately restrictive and ASCII-only: a slug appears in URLs, config, log
/// lines, and operator conversation, so two slugs must be equal or unequal
/// without reference to Unicode equivalence. Case is normalized down at parse
/// time, so `Prod` and `prod` are the same name rather than two names that look
/// alike.
///
/// A slug is *not* identity. Renaming a resource keeps its [`ResourceId`], and
/// nothing in a manifest joins on the slug.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Slug(String);

/// Why a slug was refused.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum InvalidSlug {
    #[error("a slug must not be empty")]
    Empty,
    #[error("slug `{slug}` is {length} characters, over the {max}-character limit")]
    TooLong {
        slug: String,
        length: usize,
        max: usize,
    },
    #[error(
        "slug `{slug}` contains `{character}`; only ASCII letters, digits, `-`, and `_` are allowed"
    )]
    Character { slug: String, character: char },
    #[error("slug `{slug}` must start and end with a letter or digit")]
    Boundary { slug: String },
    #[error("slug `{slug}` looks like an id; ids are not names")]
    IdLike { slug: String },
}

impl Slug {
    pub const MAX_LEN: usize = 63;

    /// The prefixes an id uses, which a slug may therefore not use.
    const ID_PREFIXES: &'static [&'static str] = &[
        TenantId::PREFIX,
        ProjectId::PREFIX,
        ResourceId::PREFIX,
        RevisionId::PREFIX,
        MutationId::PREFIX,
        AuditEventId::PREFIX,
    ];

    pub fn parse(input: &str) -> Result<Self, InvalidSlug> {
        if input.is_empty() {
            return Err(InvalidSlug::Empty);
        }
        if input.chars().count() > Self::MAX_LEN {
            return Err(InvalidSlug::TooLong {
                slug: input.to_owned(),
                length: input.chars().count(),
                max: Self::MAX_LEN,
            });
        }
        let lowered = input.to_ascii_lowercase();
        if let Some(character) = lowered
            .chars()
            .find(|c| !(c.is_ascii_alphanumeric() || *c == '-' || *c == '_'))
        {
            return Err(InvalidSlug::Character {
                slug: input.to_owned(),
                character,
            });
        }
        let boundaries_are_alphanumeric = lowered
            .chars()
            .next()
            .is_some_and(|c| c.is_ascii_alphanumeric())
            && lowered
                .chars()
                .next_back()
                .is_some_and(|c| c.is_ascii_alphanumeric());
        if !boundaries_are_alphanumeric {
            return Err(InvalidSlug::Boundary {
                slug: input.to_owned(),
            });
        }
        if Self::ID_PREFIXES
            .iter()
            .any(|prefix| lowered.starts_with(prefix))
        {
            return Err(InvalidSlug::IdLike {
                slug: input.to_owned(),
            });
        }
        Ok(Self(lowered))
    }

    pub fn as_str(&self) -> &str {
        &self.0
    }
}

impl fmt::Display for Slug {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(&self.0)
    }
}

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

    #[test]
    fn a_uuid7_carries_its_timestamp_and_sequence() {
        let id = Uuid7::from_parts(0x0192_3f5e_1a2b, 0x0abc, 0x0123_4567_89ab_cdef).unwrap();
        assert_eq!(id.timestamp_millis(), 0x0192_3f5e_1a2b);
        assert_eq!(id.sequence(), 0x0abc);
        assert_eq!(id.as_bytes()[6] >> 4, 7, "version bits");
        assert_eq!(id.as_bytes()[8] >> 6, 0b10, "variant bits");
    }

    #[test]
    fn the_text_form_round_trips_and_rejects_everything_else() {
        let id = Uuid7::from_parts(1_700_000_000_000, 1, 0xdead_beef_dead_beef).unwrap();
        assert_eq!(Uuid7::parse(&id.to_string()).unwrap(), id);
        assert_eq!(id.to_string().len(), Uuid7::TEXT_LEN);

        let text = id.to_string();
        assert!(matches!(
            Uuid7::parse(&text.replace('-', "")),
            Err(InvalidUuid7::Shape(_))
        ));
        assert!(matches!(
            Uuid7::parse(&text.to_uppercase()),
            Err(InvalidUuid7::Digit(_))
        ));
        // A v4 is a UUID, but it is not an id this domain issues.
        let mut v4 = *id.as_bytes();
        v4[6] = 0x40 | (v4[6] & 0x0f);
        assert!(matches!(
            Uuid7::from_bytes(v4),
            Err(InvalidUuid7::Version { version: 4 })
        ));
        assert!(matches!(
            Uuid7::from_bytes([0u8; 16]),
            Err(InvalidUuid7::Version { version: 0 })
        ));
        let mut bad_variant = *id.as_bytes();
        bad_variant[8] &= 0x3f;
        assert!(matches!(
            Uuid7::from_bytes(bad_variant),
            Err(InvalidUuid7::Variant { variant: 0b00 })
        ));
    }

    #[test]
    fn out_of_range_parts_are_refused() {
        assert!(matches!(
            Uuid7::from_parts(1 << 48, 0, 0),
            Err(InvalidUuid7::Timestamp { .. })
        ));
        assert!(matches!(
            Uuid7::from_parts(0, 1 << 12, 0),
            Err(InvalidUuid7::Sequence { .. })
        ));
    }

    #[test]
    fn generated_ids_are_strictly_increasing_even_within_one_millisecond() {
        let generator = Uuid7Generator::new();
        let ids: Vec<Uuid7> = (0..2_000).map(|_| generator.next()).collect();
        for window in ids.windows(2) {
            assert!(
                window[0] < window[1],
                "{} must sort before {}",
                window[0],
                window[1]
            );
        }
        let unique: std::collections::BTreeSet<_> = ids.iter().collect();
        assert_eq!(unique.len(), ids.len(), "ids are never reused");
    }

    #[test]
    fn a_generator_at_the_end_of_the_timestamp_range_degrades_instead_of_panicking() {
        // A host whose clock reads past the representable range must still be able
        // to issue an id: publication is the wrong place to discover a bad clock.
        let generator = Uuid7Generator::new();
        *generator.last.lock().unwrap() =
            (Uuid7Generator::MAX_MILLIS, Uuid7Generator::MAX_SEQUENCE);
        let id = generator.next();
        assert_eq!(id.timestamp_millis(), Uuid7Generator::MAX_MILLIS);
        assert_eq!(id.sequence(), 0);
    }

    #[test]
    fn ordering_follows_creation_time_then_sequence() {
        let earlier = Uuid7::from_parts(10, 5, u64::MAX).unwrap();
        let later = Uuid7::from_parts(11, 0, 0).unwrap();
        assert!(earlier < later, "the timestamp dominates the entropy");
        assert!(Uuid7::from_parts(10, 4, u64::MAX).unwrap() < earlier);
    }

    #[test]
    fn typed_ids_do_not_parse_each_others_text_form() {
        let uuid = Uuid7::from_parts(42, 0, 7).unwrap();
        let tenant = TenantId::new(uuid);
        assert_eq!(tenant.to_string(), format!("ten_{uuid}"));
        assert_eq!(TenantId::parse(&tenant.to_string()).unwrap(), tenant);
        assert!(matches!(
            ProjectId::parse(&tenant.to_string()),
            Err(InvalidId::Prefix {
                expected: "prj_",
                ..
            })
        ));
        assert!(matches!(
            TenantId::parse(&uuid.to_string()),
            Err(InvalidId::Prefix { .. })
        ));
        assert!(matches!(
            TenantId::parse("ten_not-a-uuid"),
            Err(InvalidId::Uuid(_))
        ));
        assert_eq!(tenant.uuid(), uuid);
        // A structure printed with `Debug` carries searchable ids, not bytes.
        assert_eq!(format!("{tenant:?}"), tenant.to_string());
        assert_eq!(format!("{uuid:?}"), uuid.to_string());
    }

    #[test]
    fn every_typed_id_has_its_own_prefix() {
        let prefixes: std::collections::BTreeSet<&str> =
            Slug::ID_PREFIXES.iter().copied().collect();
        assert_eq!(prefixes.len(), Slug::ID_PREFIXES.len());
    }

    #[test]
    fn slugs_are_normalized_ascii_names() {
        assert_eq!(Slug::parse("Prod-EU").unwrap().as_str(), "prod-eu");
        assert_eq!(
            Slug::parse("Prod-EU").unwrap(),
            Slug::parse("prod-eu").unwrap()
        );
        assert_eq!(Slug::parse("a").unwrap().to_string(), "a");
        assert_eq!(Slug::parse("team_1-x").unwrap().as_str(), "team_1-x");
    }

    #[test]
    fn slugs_refuse_names_that_are_not_names() {
        assert!(matches!(Slug::parse(""), Err(InvalidSlug::Empty)));
        assert!(matches!(
            Slug::parse(&"a".repeat(Slug::MAX_LEN + 1)),
            Err(InvalidSlug::TooLong { .. })
        ));
        for input in ["prod eu", "prod.eu", "prodé", "prod/eu"] {
            assert!(
                matches!(Slug::parse(input), Err(InvalidSlug::Character { .. })),
                "`{input}` must be refused"
            );
        }
        for input in ["-prod", "prod-", "_prod", "prod_"] {
            assert!(
                matches!(Slug::parse(input), Err(InvalidSlug::Boundary { .. })),
                "`{input}` must be refused"
            );
        }
        // A slug that looks like an id would make "is this a name or an id?"
        // ambiguous in every admin surface that accepts either.
        assert!(matches!(
            Slug::parse("ten_acme"),
            Err(InvalidSlug::IdLike { .. })
        ));
        assert!(Slug::parse("tenant-acme").is_ok());
    }
}