laburnum 1.17.3

// Copyright Two Neutron Stars Incorporated and contributors
// SPDX-License-Identifier: BlueOak-1.0.0

//! Identifier handling: a 128-bit tagged identity token.
//!
//! An [`Ident`] is a uniform 16-byte value that either stores a short
//! identifier verbatim (inline) or a truncated cryptographic hash. It is paired
//! with a [`Span`] into the source rope rather than interning text in a table,
//! so memory is bounded by live source. See ADR0012.
//!
//! # Design Pattern: Spans Instead of Strings
//!
//! - Store `Ident` (16-byte identity) + `Span` together (usually as
//!   `SpannedIdent`).
//! - The identity provides fast equality comparison.
//! - The span lets you retrieve the original identifier text when needed:
//!   `span.text(&span_cache, &source.reify_content().unwrap())`.
//!
//! `Ident` never projects to text. Inlining is an identity encoding, not a
//! text-recovery feature; recovering the source text always goes through the
//! `Span`.
//!
//! # Encoding
//!
//! The most significant bit of byte 15 is the tag: `0` = inline, `1` = hashed.
//!
//! - **Inline (≤ 15 bytes):** the bytes sit in bytes `0..n` (zero-padded), and
//!   byte 15 holds the tag (0), three zero spare bits, and the length in its low
//!   nibble. Distinct short identifiers cannot collide.
//! - **Hashed (> 15 bytes, or content-derived):** BLAKE3 of the input, with the
//!   first 127 bits kept and the tag bit forced to 1.
//!
//! Inline and hashed values occupy disjoint subspaces (the tag bit differs), so
//! no inline ident can ever equal a hashed ident. The all-zero value is
//! [`Ident::NONE`].
use {
  crate::{LaburnumError, Span},
  std::{
    fmt,
    hash::{BuildHasher, Hash, Hasher},
  },
};

/// SplitMix64 finalizer — strong avalanche with high-bit diffusion.
#[inline]
const fn splitmix64(mut z: u64) -> u64 {
  z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
  z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
  z ^ (z >> 31)
}

/// Golden-ratio odd constant, used to perturb folded lanes.
const GOLDEN: u64 = 0x9e3779b97f4a7c15;

/// A 128-bit identifier token.
///
/// Either inlines a short identifier (≤ 15 bytes) verbatim or holds a 127-bit
/// BLAKE3 truncation. The canonical form is the 16 bytes; equality, ordering,
/// and hashing operate on that byte array, so the representation is portable
/// across architectures. See the module docs and ADR0012 for the encoding.
#[derive(
  Clone,
  Copy,
  PartialEq,
  Eq,
  PartialOrd,
  Ord,
  serde::Serialize,
  serde::Deserialize,
)]
pub struct Ident([u8; 16]);

pub type IdentHashSet = std::collections::HashSet<Ident, IdentHashState>;
pub type IdentHashMap<V> = std::collections::HashMap<Ident, V, IdentHashState>;

impl Ident {
  /// The reserved "absent" identifier.
  ///
  /// All-zero. Structurally reserved: a non-empty inline ident has length ≥ 1
  /// in byte 15, and a hashed ident forces the tag bit, so byte 15 is nonzero in
  /// both cases. Only empty input produces all-zero, and an empty identifier is
  /// by definition "none", so no real ident equals `NONE`.
  pub const NONE: Self = Self([0u8; 16]);

  /// Inline-encode bytes known to be ≤ 15 long. Internal helper.
  const fn inline_unchecked(bytes: &[u8]) -> Self {
    let mut out = [0u8; 16];
    let n = bytes.len();
    let mut i = 0;
    while i < n {
      out[i] = bytes[i];
      i += 1;
    }
    // Byte 15: tag = 0 (inline), spare bits = 0, length in the low nibble.
    out[15] = n as u8;
    Self(out)
  }

  /// Build a hashed-mode ident from a BLAKE3 digest: keep 127 bits, force the
  /// tag.
  pub(crate) const fn from_digest(digest: &[u8; 32]) -> Self {
    let mut out = [0u8; 16];
    let mut i = 0;
    while i < 15 {
      out[i] = digest[i];
      i += 1;
    }
    out[15] = (digest[15] & 0x7f) | 0x80;
    Self(out)
  }

  /// Mint a const identifier from a string, inline-only.
  ///
  /// Compile-errors if the string exceeds 15 bytes, or if it begins with `$`
  /// (reserved for laburnum-internal partitions). This is the public const entry
  /// point used by `declare_partition!` / `known_idents!`.
  #[cfg(any(test, feature = "ident_constructor"))]
  pub const fn new_const(s: &str) -> Self {
    let bytes = s.as_bytes();
    assert!(
      bytes.len() <= 15,
      "Ident::new_const: identifier exceeds 15 bytes (only short keys may be const)"
    );
    assert!(
      bytes.is_empty() || bytes[0] != b'$',
      "Ident::new_const: a leading `$` is reserved for laburnum-internal partitions"
    );
    Self::inline_unchecked(bytes)
  }

  /// Mint a const first-party partition-key identifier, inline-only.
  ///
  /// Compile-errors if the key exceeds 15 bytes. In debug builds, also asserts
  /// the key begins with `$` (the reserved internal-partition sigil).
  pub(crate) const fn new_const_internal(s: &str) -> Self {
    let bytes = s.as_bytes();
    assert!(
      bytes.len() <= 15,
      "Ident::new_const_internal: key exceeds 15 bytes"
    );
    debug_assert!(
      !bytes.is_empty() && bytes[0] == b'$',
      "Ident::new_const_internal: first-party partition keys must begin with `$`"
    );
    Self::inline_unchecked(bytes)
  }

  /// Mint an identifier from a string. Crate-internal, runtime.
  ///
  /// Inlines if ≤ 15 bytes, otherwise hashes with BLAKE3. The blessed minting
  /// sites inside laburnum (lexer, path interning, key derivation) call this.
  pub(crate) fn new_internal(s: &str) -> Self {
    Self::from_input(s.as_bytes())
  }

  fn from_input(bytes: &[u8]) -> Self {
    if bytes.len() <= 15 {
      Self::inline_unchecked(bytes)
    } else {
      Self::from_digest(blake3::hash(bytes).as_bytes())
    }
  }

  /// Mint an identifier from a string (runtime).
  ///
  /// Gated on the `ident_constructor` feature: only crates that genuinely mint
  /// identifiers (a language's `*-known-idents` crate, the lexer, and test code)
  /// enable it. For const partition keys use [`Ident::new_const`].
  #[cfg(any(test, feature = "ident_constructor"))]
  pub fn new(s: &str) -> Self {
    Self::new_internal(s)
  }



  /// Whether this is the reserved absent identifier ([`Ident::NONE`]).
  pub const fn is_none(self) -> bool {
    let mut i = 0;
    while i < 16 {
      if self.0[i] != 0 {
        return false;
      }
      i += 1;
    }
    true
  }

  /// Const-context byte equality (derived `==` is not `const`).
  pub const fn const_eq(self, other: Self) -> bool {
    let (a, b) = (self.0, other.0);
    let mut i = 0;
    while i < 16 {
      if a[i] != b[i] {
        return false;
      }
      i += 1;
    }
    true
  }

  /// The canonical 16-byte form.
  pub const fn to_bytes(self) -> [u8; 16] {
    self.0
  }

  /// The two little-endian `u64` lanes, for hashing.
  #[inline]
  const fn lanes(self) -> (u64, u64) {
    let b = self.0;
    (
      u64::from_le_bytes([b[0], b[1], b[2], b[3], b[4], b[5], b[6], b[7]]),
      u64::from_le_bytes([
        b[8], b[9], b[10], b[11], b[12], b[13], b[14], b[15],
      ]),
    )
  }
}

impl fmt::Debug for Ident {
  fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    let (lo, hi) = self.lanes();
    write!(f, "Ident({hi:016x}{lo:016x})")
  }
}

impl fmt::Display for Ident {
  // Opaque: an Ident does not render to its source text. The hex form is a
  // stable identity rendering for diagnostics that have no Span in hand.
  fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    let (lo, hi) = self.lanes();
    write!(f, "{hi:016x}{lo:016x}")
  }
}

impl Hash for Ident {
  #[inline]
  fn hash<H: Hasher>(&self, state: &mut H) {
    let (lo, hi) = self.lanes();
    state.write_u64(lo);
    state.write_u64(hi);
  }
}

impl<T: Hash> From<Vec<T>> for Ident {
  fn from(vec: Vec<T>) -> Self {
    let mut hasher = crate::hash::content::ContentHasher::new();
    for item in &vec {
      item.hash(&mut hasher);
    }
    hasher.finish_ident()
  }
}

impl<T: Hash> From<&'_ [T]> for Ident {
  fn from(slice: &'_ [T]) -> Self {
    let mut hasher = crate::hash::content::ContentHasher::new();
    for item in slice {
      item.hash(&mut hasher);
    }
    hasher.finish_ident()
  }
}

/// Extended Ident methods that require Laburnum types.
pub trait IdentExt {
  /// Mint an identifier from a string with span info for errors.
  fn try_new_with_span(s: &str, span: Span) -> Result<Ident, LaburnumError>;
}

impl IdentExt for Ident {
  fn try_new_with_span(s: &str, _span: Span) -> Result<Ident, LaburnumError> {
    Ok(Ident::new_internal(s))
  }
}

// -- Map hashing --------------------------------------------------------------

/// The map [`BuildHasher`] for `Ident` keys.
///
/// `Ident` carries low-entropy bytes for short inline identifiers, so the
/// finalizer must diffuse into the high bits (hashbrown's control byte and
/// DashMap's shard index both come from the top bits). It folds each `u64` lane
/// through [`splitmix64`].
#[derive(Clone)]
pub struct IdentHasher {
  state: u64,
}

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

impl IdentHasher {
  pub const fn new() -> Self {
    Self { state: 0 }
  }
}

impl Hasher for IdentHasher {
  #[inline]
  fn write_u64(&mut self, value: u64) {
    self.state =
      splitmix64(self.state ^ splitmix64(value.wrapping_add(GOLDEN)));
  }

  #[inline]
  fn write(&mut self, bytes: &[u8]) {
    // Fold byte-by-byte; the hot path (`Ident`) uses `write_u64` directly.
    for &byte in bytes {
      self.state =
        splitmix64(self.state ^ (byte as u64).wrapping_add(GOLDEN));
    }
  }

  #[inline]
  fn finish(&self) -> u64 {
    splitmix64(self.state)
  }
}

/// `BuildHasher` for [`IdentHasher`].
#[derive(Clone, Debug, Default)]
pub struct IdentHashState;

impl BuildHasher for IdentHashState {
  type Hasher = IdentHasher;

  #[inline]
  fn build_hasher(&self) -> Self::Hasher {
    IdentHasher::new()
  }
}

/// A convenience extension trait to enable [`HashSet::new`] for hash sets that
/// use [`IdentHashState`].
pub trait HashSetExt {
  /// Creates an empty `HashSet`.
  fn new() -> Self;

  /// Creates an empty `HashSet` with at least the specified capacity.
  fn with_capacity(capacity: usize) -> Self;
}

impl<T> HashSetExt for std::collections::HashSet<T, IdentHashState> {
  #[inline]
  fn new() -> Self {
    Self::with_hasher(IdentHashState)
  }

  #[inline]
  fn with_capacity(capacity: usize) -> Self {
    Self::with_capacity_and_hasher(capacity, IdentHashState)
  }
}

/// A convenience extension trait to enable [`HashMap::new`] for hash maps that
/// use [`IdentHashState`].
pub trait HashMapExt {
  /// Creates an empty `HashMap`.
  fn new() -> Self;

  /// Creates an empty `HashMap` with at least the specified capacity.
  fn with_capacity(capacity: usize) -> Self;
}

impl<K, V> HashMapExt for std::collections::HashMap<K, V, IdentHashState> {
  #[inline]
  fn new() -> Self {
    Self::with_hasher(IdentHashState)
  }

  #[inline]
  fn with_capacity(capacity: usize) -> Self {
    Self::with_capacity_and_hasher(capacity, IdentHashState)
  }
}

#[cfg(test)]
mod tests {
  use {super::*, std::collections::HashSet};

  fn tag(ident: Ident) -> u8 {
    ident.to_bytes()[15] & 0x80
  }

  #[test]
  fn inline_determinism_and_equivalence() {
    assert_eq!(Ident::new("a"), Ident::new("a"));
    assert_eq!(Ident::new("hello"), Ident::new("hello"));
    assert_ne!(Ident::new("a"), Ident::new("A"));
    assert_ne!(Ident::new("Hello"), Ident::new("hello"));
    // Short idents are inline (tag bit clear).
    assert_eq!(tag(Ident::new("hello")), 0);
    assert_eq!(tag(Ident::new("a_15_byte_strin")), 0);
  }

  #[test]
  fn inline_encodes_bytes_verbatim() {
    let ident = Ident::new("count");
    let bytes = ident.to_bytes();
    assert_eq!(&bytes[0..5], b"count");
    assert_eq!(bytes[15], 5); // tag 0, length 5
    // unused bytes zeroed
    assert!(bytes[5..15].iter().all(|&b| b == 0));
  }

  #[test]
  fn boundary_15_inline_16_hashed() {
    let fifteen = "abcdefghijklmno"; // 15 bytes
    let sixteen = "abcdefghijklmnop"; // 16 bytes
    assert_eq!(fifteen.len(), 15);
    assert_eq!(sixteen.len(), 16);
    assert_eq!(tag(Ident::new(fifteen)), 0, "15 bytes must inline");
    assert_eq!(tag(Ident::new(sixteen)), 0x80, "16 bytes must hash");
    // hashed is deterministic
    assert_eq!(Ident::new(sixteen), Ident::new(sixteen));
    assert_ne!(Ident::new(sixteen), Ident::new("abcdefghijklmnoq"));
  }

  #[test]
  fn cross_mode_disjoint() {
    // An inline ident can never equal a hashed ident (tag bit differs).
    let inline = Ident::new("short");
    let hashed = Ident::new("a_long_identifier_over_fifteen_bytes");
    assert_eq!(tag(inline), 0);
    assert_eq!(tag(hashed), 0x80);
    assert_ne!(inline, hashed);
  }

  #[test]
  fn none_is_structurally_reserved() {
    assert!(Ident::NONE.is_none());
    assert_eq!(Ident::new(""), Ident::NONE);
    // No non-empty ident is NONE.
    assert!(!Ident::new("a").is_none());
    assert!(!Ident::new("a_long_identifier_over_fifteen_bytes").is_none());
  }

  #[test]
  fn canonical_length_field_prevents_prefix_collision() {
    // "ab" (length 2) must not equal a 2-byte prefix of "abc" (length 3).
    assert_ne!(Ident::new("ab"), Ident::new("abc"));
    assert_ne!(Ident::new("a"), Ident::new("aa"));
  }

  #[test]
  fn new_const_matches_runtime() {
    const C: Ident = Ident::new_const("clients");
    assert_eq!(C, Ident::new("clients"));
    const INTERNAL: Ident = Ident::new_const_internal("$clients");
    assert_eq!(INTERNAL, Ident::new("$clients"));
  }

  #[test]
  fn content_finalizer_is_deterministic_and_hashed() {
    let a: Ident = vec![1u64, 2, 3].into();
    let b: Ident = vec![1u64, 2, 3].into();
    let c: Ident = vec![1u64, 2, 4].into();
    assert_eq!(a, b);
    assert_ne!(a, c);
    assert_eq!(tag(a), 0x80, "content-derived idents are hashed mode");
  }

  #[test]
  fn map_hashing_distributes() {
    // Sanity: short low-entropy idents do not all collapse to one bucket.
    let mut set: IdentHashSet = HashSet::with_hasher(IdentHashState);
    for name in ["i", "j", "x", "n", "self", "len", "count", "tmp"] {
      assert!(set.insert(Ident::new(name)));
    }
    assert_eq!(set.len(), 8);
  }

  #[test]
  fn mixer_diffuses_into_high_bits() {
    // hashbrown's control byte and DashMap's shard index both read the top
    // bits, so short low-entropy idents must spread across them rather than
    // pinning one shard.
    let state = IdentHashState;
    let mut top_bits = HashSet::new();
    for name in [
      "i", "j", "x", "n", "a", "b", "c", "d", "self", "len", "count", "tmp",
      "idx", "key", "val", "out",
    ] {
      let hash = state.hash_one(Ident::new(name));
      top_bits.insert(hash >> 57); // top 7 bits
    }
    assert!(
      top_bits.len() > 8,
      "mixer failed to diffuse into the high bits ({} distinct top-bit groups)",
      top_bits.len()
    );
  }

  #[test]
  fn const_eq_matches_eq() {
    const A: Ident = Ident::new_const("count");
    const B: Ident = Ident::new_const("count");
    const C: Ident = Ident::new_const("other");
    const _: () = assert!(A.const_eq(B));
    const _: () = assert!(!A.const_eq(C));
    assert_eq!(A.const_eq(B), A == B);
    assert_eq!(A.const_eq(C), A == C);
  }


  #[test]
  fn inline_byte15_is_canonical() {
    for s in ["", "a", "count", "abcdefghijklmno"] {
      let b15 = Ident::new(s).to_bytes()[15];
      assert_eq!(b15 & 0x80, 0, "inline tag bit must be clear");
      assert_eq!(b15 >> 4, 0, "byte 15 tag/spare bits (4-7) must be zero");
      assert_eq!(b15 as usize, s.len(), "low nibble is the length");
    }
  }

  #[test]
  fn none_usable_as_map_key() {
    let mut map: IdentHashMap<u32> =
      std::collections::HashMap::with_hasher(IdentHashState);
    map.insert(Ident::NONE, 1);
    map.insert(Ident::new("a"), 2);
    assert_eq!(map.get(&Ident::NONE), Some(&1));
    assert_eq!(map.len(), 2);
  }
}