laburnum 1.17.0

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

//! Content hashing and content-addressed storage types.
//!
//! This module provides 128-bit content hashes using xxHash3 and efficient
//! hash map/set types optimized for content-addressed storage.
//!
//! # Content Hashing
//!
//! [`ContentHash`] provides a 128-bit hash suitable for content-addressed
//! storage. Use [`ContentHasher`] for incremental hashing of large data.
//!
//! # Content-Addressed Collections
//!
//! [`ContentHashedWriter`] collects records during a processing phase,
//! automatically computing content hashes on insert. [`ContentHashedStore`]
//! aggregates records from multiple writers for long-term storage.
//!
//! # Example
//!
//! ```ignore
//! use laburnum::{ContentHashedWriter, ContentHashedStore, Record};
//!
//! // Collect records in a writer during processing
//! let mut writer = ContentHashedWriter::new();
//! let hash = writer.insert(my_record);
//!
//! // Merge into a store for persistence
//! let mut store = ContentHashedStore::new();
//! store.merge_from(writer);
//! ```

use {
  crate::record::Record,
  serde::{
    Serialize,
    Serializer,
  },
  std::{
    collections::{
      HashMap,
      HashSet,
    },
    hash::{
      BuildHasher,
      Hash,
      Hasher,
    },
  },
  xxhash_rust::xxh3::{
    Xxh3,
    xxh3_128,
  },
};

/// A 128-bit content hash using xxHash3.
///
/// Content hashes identify records by their content rather than by location
/// or identity. Two records with identical content produce the same hash,
/// enabling deduplication and structural sharing.
///
/// # Creating Hashes
///
/// - [`ContentHash::new`] - Hash a byte slice directly
/// - [`ContentHash::from_reader`] - Hash streaming data from a reader
/// - [`ContentHash::hasher`] - Get an incremental hasher for building hashes
///
/// # Example
///
/// ```
/// use laburnum::ContentHash;
///
/// let hash = ContentHash::new(b"hello world");
///
/// // Incremental hashing
/// let mut hasher = ContentHash::hasher();
/// hasher.update(b"hello ");
/// hasher.update(b"world");
/// let incremental_hash = hasher.finalize();
///
/// assert_eq!(hash, incremental_hash);
/// ```
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct ContentHash(pub(crate) u128);

impl Hash for ContentHash {
  fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
    state.write_u128(self.0);
  }
}

impl Serialize for ContentHash {
  fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
  where
    S: Serializer,
  {
    serializer.serialize_str(&self.0.to_string())
  }
}

impl std::fmt::Display for ContentHash {
  fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
    write!(f, "{:032x}", self.0)
  }
}


impl ContentHash {
  /// A zero content hash, used as a sentinel value for blocked writes.
  pub const ZERO: ContentHash = ContentHash(0);

  /// Creates a content hash from a byte slice.
  pub fn new(data: &[u8]) -> Self {
    let hash = xxh3_128(data);
    ContentHash(hash)
  }

  /// Creates a content hash by reading all data from a reader.
  ///
  /// Reads in 8KB chunks, suitable for hashing files or streams.
  pub fn from_reader(mut reader: impl std::io::Read) -> std::io::Result<Self> {
    let mut hasher = Xxh3::new();
    let mut buffer = [0u8; 8192];

    loop {
      let n = reader.read(&mut buffer)?;
      if n == 0 {
        break;
      }
      hasher.update(&buffer[..n]);
    }

    Ok(ContentHash(hasher.digest128()))
  }

  /// Returns an incremental hasher for building content hashes.
  ///
  /// Use this when you need to hash data in multiple parts.
  pub fn hasher() -> ContentHasher {
    ContentHasher(Xxh3::new())
  }
}

/// Incremental hasher for building [`ContentHash`] values.
///
/// Use [`ContentHash::hasher()`] to create an instance, then call
/// [`update`](Self::update) to add data, and [`finalize`](Self::finalize)
/// to produce the final hash.
pub struct ContentHasher(Xxh3);

impl ContentHasher {
  /// Adds data to the hash computation.
  pub fn update(&mut self, data: &[u8]) {
    self.0.update(data);
  }

  /// Consumes the hasher and returns the final content hash.
  pub fn finalize(self) -> ContentHash {
    ContentHash(self.0.digest128())
  }
}

impl std::hash::Hasher for ContentHasher {
  fn finish(&self) -> u64 {
    self.0.digest()
  }

  fn write(&mut self, bytes: &[u8]) {
    self.0.update(bytes);
  }
}

/// A no-op hasher for [`ContentHash`] keys in hash maps.
///
/// Since [`ContentHash`] is already a high-quality hash, this hasher simply
/// XORs the high and low 64 bits to produce a u64 for the hash table.
#[derive(Default)]
pub struct ContentHashHasher(u64);

impl Hasher for ContentHashHasher {
  #[inline(always)]
  fn finish(&self) -> u64 {
    self.0
  }

  #[inline(always)]
  fn write(&mut self, _bytes: &[u8]) {
    debug_assert!(
      false,
      "ContentHashHasher only accepts write_u128; \
       a HashMap lookup will silently miss in release builds"
    );
  }

  #[inline(always)]
  fn write_u128(&mut self, i: u128) {
    self.0 = (i as u64) ^ ((i >> 64) as u64);
  }
}

/// [`BuildHasher`] for creating [`ContentHashHasher`] instances.
///
/// Use this with `HashMap` or `HashSet` when the key type is [`ContentHash`].
#[derive(Clone, Debug, Default)]
pub struct ContentHashState;

impl BuildHasher for ContentHashState {
  type Hasher = ContentHashHasher;

  #[inline(always)]
  fn build_hasher(&self) -> Self::Hasher {
    ContentHashHasher::default()
  }
}

/// A [`HashMap`] optimized for [`ContentHash`] keys.
pub type ContentHashMap<V> = HashMap<ContentHash, V, ContentHashState>;

/// A [`HashSet`] optimized for [`ContentHash`] values.
pub type ContentHashSet = HashSet<ContentHash, ContentHashState>;

/// Extension trait providing `new()` and `with_capacity()` for [`ContentHashMap`].
pub trait ContentHashMapExt {
  /// Creates an empty map.
  fn new() -> Self;
  /// Creates an empty map with the specified capacity.
  fn with_capacity(capacity: usize) -> Self;
}

impl<V> ContentHashMapExt for ContentHashMap<V> {
  #[inline(always)]
  fn new() -> Self {
    Self::with_hasher(ContentHashState)
  }

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

/// Extension trait providing `new()` and `with_capacity()` for [`ContentHashSet`].
pub trait ContentHashSetExt {
  /// Creates an empty set.
  fn new() -> Self;
  /// Creates an empty set with the specified capacity.
  fn with_capacity(capacity: usize) -> Self;
}

impl ContentHashSetExt for ContentHashSet {
  #[inline(always)]
  fn new() -> Self {
    Self::with_hasher(ContentHashState)
  }

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

/// Collects records during a processing phase, computing content hashes on insert.
///
/// `ContentHashedWriter` is designed for collecting records produced by a single
/// processing task (e.g., parsing one file). It computes the content hash
/// automatically when inserting records and deduplicates by hash.
///
/// After processing, merge the writer's contents into a [`ContentHashedStore`]
/// for aggregation with records from other writers.
///
/// # Example
///
/// ```ignore
/// let mut writer = ContentHashedWriter::new();
///
/// // Insert records; hash is computed automatically
/// let hash1 = writer.insert(record1);
/// let hash2 = writer.insert(record2);
///
/// // Duplicate content produces same hash, not stored twice
/// let hash1_again = writer.insert(record1_copy);
/// assert_eq!(hash1, hash1_again);
///
/// // Merge into store
/// store.merge_from(writer);
/// ```
pub struct ContentHashedWriter<R> {
  records: ContentHashMap<R>,
}

impl<R: Record> ContentHashedWriter<R> {
  /// Creates an empty writer.
  pub fn new() -> Self {
    Self {
      records: ContentHashMap::new(),
    }
  }

  /// Creates an empty writer with the specified capacity.
  pub fn with_capacity(capacity: usize) -> Self {
    Self {
      records: ContentHashMap::with_capacity(capacity),
    }
  }

  /// Inserts a record, computing its content hash and returning it.
  ///
  /// If a record with the same hash already exists, the existing record
  /// is kept and the new record is discarded.
  pub fn insert(&mut self, record: R) -> ContentHash {
    let hash = record.content_hash();
    self.records.entry(hash).or_insert(record);
    hash
  }

  /// Returns a reference to the record with the given hash, if present.
  pub fn get(&self, hash: &ContentHash) -> Option<&R> {
    self.records.get(hash)
  }

  /// Returns `true` if the writer contains a record with the given hash.
  pub fn contains(&self, hash: &ContentHash) -> bool {
    self.records.contains_key(hash)
  }

  /// Returns the number of records in the writer.
  pub fn len(&self) -> usize {
    self.records.len()
  }

  /// Returns `true` if the writer contains no records.
  pub fn is_empty(&self) -> bool {
    self.records.is_empty()
  }

  /// Returns an iterator over hash-record pairs.
  pub fn iter(&self) -> impl Iterator<Item = (&ContentHash, &R)> {
    self.records.iter()
  }
}

impl<R: Record> IntoIterator for ContentHashedWriter<R> {
  type Item = (ContentHash, R);
  type IntoIter = std::collections::hash_map::IntoIter<ContentHash, R>;

  fn into_iter(self) -> Self::IntoIter {
    self.records.into_iter()
  }
}

impl<R: Record> Default for ContentHashedWriter<R> {
  fn default() -> Self {
    Self::new()
  }
}

/// Aggregates records from multiple writers for long-term storage.
///
/// `ContentHashedStore` is the central repository for content-addressed records.
/// It aggregates records from multiple [`ContentHashedWriter`] instances,
/// deduplicating by content hash. Records with the same hash are stored once.
///
/// # Example
///
/// ```ignore
/// let mut store = ContentHashedStore::new();
///
/// // Merge from multiple writers (e.g., from parallel processing)
/// store.merge_from(writer1);
/// store.merge_from(writer2);
///
/// // Look up records by hash
/// if let Some(record) = store.get(&hash) {
///     // use record
/// }
///
/// // Clean up with retain
/// store.retain(|hash, record| is_still_needed(hash, record));
/// ```
pub struct ContentHashedStore<R> {
  records: ContentHashMap<R>,
}

impl<R: Record> ContentHashedStore<R> {
  /// Creates an empty store.
  pub fn new() -> Self {
    Self {
      records: ContentHashMap::new(),
    }
  }

  /// Creates an empty store with the specified capacity.
  pub fn with_capacity(capacity: usize) -> Self {
    Self {
      records: ContentHashMap::with_capacity(capacity),
    }
  }

  /// Merges all records from a writer into this store.
  ///
  /// Consumes the writer. Records with hashes already in the store are
  /// skipped (the existing record is kept). Returns the number of records
  /// processed (including duplicates).
  pub fn merge_from(&mut self, writer: ContentHashedWriter<R>) -> usize {
    let mut count = 0;
    for (hash, record) in writer {
      if self.records.entry(hash).or_insert(record).content_hash() == hash {
        count += 1;
      }
    }
    count
  }

  /// Inserts a record with a pre-computed hash.
  ///
  /// Returns `true` if the record was inserted, `false` if a record with
  /// the same hash already existed (in which case the store is unchanged).
  pub fn insert_with_hash(&mut self, hash: ContentHash, record: R) -> bool {
    use std::collections::hash_map::Entry;
    match self.records.entry(hash) {
      Entry::Occupied(_) => false,
      Entry::Vacant(entry) => {
        entry.insert(record);
        true
      }
    }
  }

  /// Returns a reference to the record with the given hash, if present.
  pub fn get(&self, hash: &ContentHash) -> Option<&R> {
    self.records.get(hash)
  }

  /// Returns `true` if the store contains a record with the given hash.
  pub fn contains(&self, hash: &ContentHash) -> bool {
    self.records.contains_key(hash)
  }

  /// Returns the number of records in the store.
  pub fn len(&self) -> usize {
    self.records.len()
  }

  /// Returns `true` if the store contains no records.
  pub fn is_empty(&self) -> bool {
    self.records.is_empty()
  }

  /// Returns an iterator over hash-record pairs.
  pub fn iter(&self) -> impl Iterator<Item = (&ContentHash, &R)> {
    self.records.iter()
  }

  /// Retains only the records for which the predicate returns `true`.
  pub fn retain<F>(&mut self, predicate: F)
  where
    F: FnMut(&ContentHash, &mut R) -> bool,
  {
    self.records.retain(predicate);
  }

  /// Returns an iterator over all content hashes in the store.
  pub fn hashes(&self) -> impl Iterator<Item = &ContentHash> {
    self.records.keys()
  }
}

impl<R: Record> Default for ContentHashedStore<R> {
  fn default() -> Self {
    Self::new()
  }
}

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

  #[derive(Debug, Clone, PartialEq, Eq)]
  struct TestRecord {
    id: u32,
    value: String,
  }

  impl Record for TestRecord {
    fn content_hash(&self) -> ContentHash {
      let mut hasher = ContentHash::hasher();
      hasher.update(&self.id.to_le_bytes());
      hasher.update(self.value.as_bytes());
      hasher.finalize()
    }
  }

  #[test]
  fn test_content_hash_map_new() {
    let map: ContentHashMap<i32> = ContentHashMap::new();
    assert!(map.is_empty());
  }

  #[test]
  fn test_content_hash_map_with_capacity() {
    let map: ContentHashMap<i32> = ContentHashMap::with_capacity(100);
    assert!(map.capacity() >= 100);
  }

  #[test]
  fn test_content_hash_set_new() {
    let set: ContentHashSet = ContentHashSet::new();
    assert!(set.is_empty());
  }

  #[test]
  fn test_content_hash_set_with_capacity() {
    let set: ContentHashSet = ContentHashSet::with_capacity(100);
    assert!(set.capacity() >= 100);
  }

  #[test]
  fn test_writer_insert_and_retrieve() {
    let mut writer = ContentHashedWriter::new();
    let record = TestRecord {
      id: 1,
      value: "test".to_string(),
    };
    let hash = writer.insert(record.clone());

    assert_eq!(writer.len(), 1);
    assert!(!writer.is_empty());
    assert!(writer.contains(&hash));

    let retrieved = writer.get(&hash).unwrap();
    assert_eq!(retrieved.id, 1);
    assert_eq!(retrieved.value, "test");
  }

  #[test]
  fn test_writer_insert_computes_hash() {
    let mut writer = ContentHashedWriter::new();
    let record = TestRecord {
      id: 42,
      value: "hello".to_string(),
    };
    let expected_hash = record.content_hash();
    let returned_hash = writer.insert(record);

    assert_eq!(returned_hash, expected_hash);
  }

  #[test]
  fn test_writer_duplicate_insert_keeps_first() {
    let mut writer = ContentHashedWriter::new();
    let record1 = TestRecord {
      id: 1,
      value: "test".to_string(),
    };
    let record2 = TestRecord {
      id: 1,
      value: "test".to_string(),
    };

    let hash1 = writer.insert(record1);
    let hash2 = writer.insert(record2);

    assert_eq!(hash1, hash2);
    assert_eq!(writer.len(), 1);
  }

  #[test]
  fn test_writer_iter() {
    let mut writer = ContentHashedWriter::new();
    writer.insert(TestRecord {
      id: 1,
      value: "a".to_string(),
    });
    writer.insert(TestRecord {
      id: 2,
      value: "b".to_string(),
    });

    let count = writer.iter().count();
    assert_eq!(count, 2);
  }

  #[test]
  fn test_writer_into_iterator() {
    let mut writer = ContentHashedWriter::new();
    writer.insert(TestRecord {
      id: 1,
      value: "a".to_string(),
    });
    writer.insert(TestRecord {
      id: 2,
      value: "b".to_string(),
    });

    let items: Vec<_> = writer.into_iter().collect();
    assert_eq!(items.len(), 2);
  }

  #[test]
  fn test_writer_default() {
    let writer: ContentHashedWriter<TestRecord> = ContentHashedWriter::default();
    assert!(writer.is_empty());
  }

  #[test]
  fn test_store_new() {
    let store: ContentHashedStore<TestRecord> = ContentHashedStore::new();
    assert!(store.is_empty());
    assert_eq!(store.len(), 0);
  }

  #[test]
  fn test_store_merge_from_writer() {
    let mut writer = ContentHashedWriter::new();
    let hash1 = writer.insert(TestRecord {
      id: 1,
      value: "a".to_string(),
    });
    let hash2 = writer.insert(TestRecord {
      id: 2,
      value: "b".to_string(),
    });

    let mut store = ContentHashedStore::new();
    let count = store.merge_from(writer);

    assert_eq!(count, 2);
    assert_eq!(store.len(), 2);
    assert!(store.contains(&hash1));
    assert!(store.contains(&hash2));
  }

  #[test]
  fn test_store_merge_duplicate_keeps_first() {
    let mut writer1 = ContentHashedWriter::new();
    let hash = writer1.insert(TestRecord {
      id: 1,
      value: "first".to_string(),
    });

    let mut store = ContentHashedStore::new();
    store.merge_from(writer1);

    let mut writer2 = ContentHashedWriter::new();
    writer2.insert(TestRecord {
      id: 1,
      value: "first".to_string(),
    });

    let count = store.merge_from(writer2);
    assert_eq!(count, 1);
    assert_eq!(store.len(), 1);

    let record = store.get(&hash).unwrap();
    assert_eq!(record.value, "first");
  }

  #[test]
  fn test_store_insert_with_hash() {
    let mut store = ContentHashedStore::new();
    let record = TestRecord {
      id: 1,
      value: "test".to_string(),
    };
    let hash = record.content_hash();

    let inserted = store.insert_with_hash(hash, record);
    assert!(inserted);
    assert_eq!(store.len(), 1);

    let duplicate = TestRecord {
      id: 1,
      value: "test".to_string(),
    };
    let inserted_again = store.insert_with_hash(hash, duplicate);
    assert!(!inserted_again);
    assert_eq!(store.len(), 1);
  }

  #[test]
  fn test_store_retain() {
    let mut writer = ContentHashedWriter::new();
    writer.insert(TestRecord {
      id: 1,
      value: "keep".to_string(),
    });
    writer.insert(TestRecord {
      id: 2,
      value: "remove".to_string(),
    });
    writer.insert(TestRecord {
      id: 3,
      value: "keep".to_string(),
    });

    let mut store = ContentHashedStore::new();
    store.merge_from(writer);
    assert_eq!(store.len(), 3);

    store.retain(|_, r| r.value == "keep");
    assert_eq!(store.len(), 2);
  }

  #[test]
  fn test_store_hashes() {
    let mut writer = ContentHashedWriter::new();
    let hash1 = writer.insert(TestRecord {
      id: 1,
      value: "a".to_string(),
    });
    let hash2 = writer.insert(TestRecord {
      id: 2,
      value: "b".to_string(),
    });

    let mut store = ContentHashedStore::new();
    store.merge_from(writer);

    let hashes: Vec<_> = store.hashes().collect();
    assert_eq!(hashes.len(), 2);
    assert!(hashes.contains(&&hash1));
    assert!(hashes.contains(&&hash2));
  }

  #[test]
  fn test_store_default() {
    let store: ContentHashedStore<TestRecord> = ContentHashedStore::default();
    assert!(store.is_empty());
  }

  #[test]
  fn test_empty_writer_behavior() {
    let writer: ContentHashedWriter<TestRecord> = ContentHashedWriter::new();
    assert!(writer.is_empty());
    assert_eq!(writer.len(), 0);
    assert_eq!(writer.iter().count(), 0);

    let nonexistent_hash = ContentHash::new(b"nonexistent");
    assert!(!writer.contains(&nonexistent_hash));
    assert!(writer.get(&nonexistent_hash).is_none());
  }

  #[test]
  fn test_empty_store_behavior() {
    let store: ContentHashedStore<TestRecord> = ContentHashedStore::new();
    assert!(store.is_empty());
    assert_eq!(store.len(), 0);
    assert_eq!(store.iter().count(), 0);

    let nonexistent_hash = ContentHash::new(b"nonexistent");
    assert!(!store.contains(&nonexistent_hash));
    assert!(store.get(&nonexistent_hash).is_none());
  }

  #[test]
  fn test_merge_empty_writer() {
    let writer: ContentHashedWriter<TestRecord> = ContentHashedWriter::new();
    let mut store = ContentHashedStore::new();
    let count = store.merge_from(writer);

    assert_eq!(count, 0);
    assert!(store.is_empty());
  }
}