hedl-core 2.0.0

// Dweve HEDL - Hierarchical Entity Data Language
//
// Copyright (c) 2025 Dweve IP B.V. and individual contributors.
//
// SPDX-License-Identifier: Apache-2.0
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License in the LICENSE file at the
// root of this repository or at: http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Arena allocator requires unsafe for performance-critical pointer operations.
// Safety invariants are documented at each unsafe block.
#![allow(unsafe_code)]

//! String interning for deduplication of repeated strings.
//!
//! String interning is a critical optimization for HEDL parsing because:
//! - Type names are repeated thousands of times (e.g., "Person" in 10,000 nodes)
//! - Schema columns are duplicated across rows
//! - Small identifiers appear frequently
//!
//! By storing each unique string once in an arena and using lightweight
//! references everywhere else, we achieve:
//! - Massive memory savings (70KB → 7 bytes for 10,000 "Person" strings)
//! - Pointer equality for fast comparison
//! - Better cache locality (strings clustered in memory)

use bumpalo::Bump;
use std::collections::HashMap;
use std::hash::{Hash, Hasher};
use std::ptr::NonNull;

/// String interner using arena storage for deduplication.
///
/// Stores each unique string once in the arena and returns zero-cost
/// references ([`InternedString`]) that can be copied freely.
///
/// # Performance Characteristics
///
/// - **Intern**: O(1) amortized (hash table lookup + arena allocation)
/// - **Comparison**: O(1) pointer equality (no string comparison needed)
/// - **Memory**: Stores each unique string exactly once
/// - **Deduplication**: Automatic - identical strings share storage
///
/// # Safety
///
/// All interned strings are lifetime-bounded to the arena. The interner
/// ensures that:
/// - String bytes remain valid for the arena's lifetime
/// - No dangling pointers (enforced by Rust's lifetime system)
/// - UTF-8 validity is preserved (verified on insertion)
///
/// # Examples
///
/// ```ignore
/// use bumpalo::Bump;
/// use hedl_core::lex::arena::StringInterner;
///
/// let arena = Bump::new();
/// let mut interner = StringInterner::new(&arena);
///
/// // Intern some strings
/// let s1 = interner.intern("Person");
/// let s2 = interner.intern("Person");
/// let s3 = interner.intern("Team");
///
/// // Same string -> same reference
/// assert_eq!(s1.as_ptr(), s2.as_ptr());
/// assert_ne!(s1.as_ptr(), s3.as_ptr());
///
/// // Fast comparison via pointer equality
/// assert_eq!(s1, s2);
/// assert_ne!(s1, s3);
///
/// // Convert back to &str
/// assert_eq!(s1.as_str(), "Person");
/// assert_eq!(s3.as_str(), "Team");
/// ```
pub struct StringInterner<'arena> {
    /// Arena for string storage
    arena: &'arena Bump,
    /// Map from string content to interned reference
    map: HashMap<&'arena str, InternedString>,
}

impl<'arena> StringInterner<'arena> {
    /// Create a new string interner backed by the given arena.
    ///
    /// # Examples
    ///
    /// ```ignore
    /// use bumpalo::Bump;
    /// use hedl_core::lex::arena::StringInterner;
    ///
    /// let arena = Bump::new();
    /// let interner = StringInterner::new(&arena);
    /// ```
    pub fn new(arena: &'arena Bump) -> Self {
        Self {
            arena,
            map: HashMap::new(),
        }
    }

    /// Create a new interner with a specified capacity.
    ///
    /// Pre-allocates the hash table to avoid resizing during parsing.
    ///
    /// # Examples
    ///
    /// ```ignore
    /// use bumpalo::Bump;
    /// use hedl_core::lex::arena::StringInterner;
    ///
    /// let arena = Bump::new();
    /// // Expect ~1000 unique strings
    /// let interner = StringInterner::with_capacity(&arena, 1000);
    /// ```
    pub fn with_capacity(arena: &'arena Bump, capacity: usize) -> Self {
        Self {
            arena,
            map: HashMap::with_capacity(capacity),
        }
    }

    /// Intern a string, storing it in the arena if not already present.
    ///
    /// Returns a lightweight reference that can be copied freely. If the string
    /// was already interned, returns the existing reference (deduplication).
    ///
    /// # Performance
    ///
    /// - **Hit** (already interned): O(1) hash table lookup
    /// - **Miss** (new string): O(n) for copying n bytes + O(1) insertion
    ///
    /// # Examples
    ///
    /// ```ignore
    /// # use bumpalo::Bump;
    /// # use hedl_core::lex::arena::StringInterner;
    /// let arena = Bump::new();
    /// let mut interner = StringInterner::new(&arena);
    ///
    /// let s1 = interner.intern("Person");
    /// let s2 = interner.intern("Person"); // Reuses s1's storage
    ///
    /// assert_eq!(s1.as_ptr(), s2.as_ptr());
    /// ```
    pub fn intern(&mut self, s: &str) -> InternedString {
        // Fast path: already interned
        if let Some(&interned) = self.map.get(s) {
            return interned;
        }

        // Slow path: copy string bytes to arena
        // SAFETY: We copy the bytes into the arena, which guarantees:
        // - The bytes remain valid for 'arena lifetime
        // - The bytes are UTF-8 (s is &str, so already validated)
        // - The pointer is non-null (arena allocations never return null)
        let arena_bytes = self.arena.alloc_slice_copy(s.as_bytes());
        let interned = InternedString {
            ptr: NonNull::new(arena_bytes.as_ptr() as *mut u8)
                .expect("arena allocation is non-null"),
            len: s.len(),
        };

        // Convert arena bytes to &'arena str for the hash map key
        // SAFETY: We just copied valid UTF-8 bytes, so this is safe
        let arena_str = unsafe {
            std::str::from_utf8_unchecked(std::slice::from_raw_parts(
                interned.ptr.as_ptr(),
                interned.len,
            ))
        };

        self.map.insert(arena_str, interned);
        interned
    }

    /// Get the number of unique strings currently interned.
    ///
    /// # Examples
    ///
    /// ```ignore
    /// # use bumpalo::Bump;
    /// # use hedl_core::lex::arena::StringInterner;
    /// let arena = Bump::new();
    /// let mut interner = StringInterner::new(&arena);
    ///
    /// assert_eq!(interner.len(), 0);
    /// interner.intern("hello");
    /// assert_eq!(interner.len(), 1);
    /// interner.intern("hello"); // Duplicate
    /// assert_eq!(interner.len(), 1);
    /// interner.intern("world");
    /// assert_eq!(interner.len(), 2);
    /// ```
    pub fn len(&self) -> usize {
        self.map.len()
    }

    /// Returns true if no strings have been interned.
    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    /// Get memory usage statistics.
    ///
    /// Returns (unique_strings, total_bytes_stored, deduplication_ratio).
    /// The deduplication ratio is an estimate based on average string length.
    pub fn stats(&self) -> InternerStats {
        let unique_count = self.map.len();
        let total_bytes = self.map.keys().map(|s| s.len()).sum();

        InternerStats {
            unique_strings: unique_count,
            total_bytes_stored: total_bytes,
        }
    }
}

/// Statistics for string interner performance analysis.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct InternerStats {
    /// Number of unique strings interned
    pub unique_strings: usize,
    /// Total bytes stored (sum of all unique string lengths)
    pub total_bytes_stored: usize,
}

/// Interned string reference (zero-cost abstraction).
///
/// This is a lightweight reference to a string stored in an arena. It can be
/// copied freely and compared by pointer equality for maximum performance.
///
/// # Memory Layout
///
/// - Size: 16 bytes (8-byte pointer + 8-byte length)
/// - Alignment: 8 bytes
/// - Copy: yes (implements Copy)
///
/// # Lifetime
///
/// The string data is valid for as long as the arena that allocated it.
/// Rust's lifetime system prevents dangling references.
///
/// # Examples
///
/// ```ignore
/// # use bumpalo::Bump;
/// # use hedl_core::lex::arena::StringInterner;
/// let arena = Bump::new();
/// let mut interner = StringInterner::new(&arena);
///
/// let s = interner.intern("hello");
/// assert_eq!(s.as_str(), "hello");
/// assert_eq!(s.len(), 5);
///
/// // Can be copied freely
/// let s2 = s;
/// assert_eq!(s, s2);
/// ```
#[derive(Copy, Clone)]
pub struct InternedString {
    /// Pointer to the first byte of the string in the arena
    ptr: NonNull<u8>,
    /// Length of the string in bytes
    len: usize,
}

impl InternedString {
    /// Convert to a string slice.
    ///
    /// This is a zero-cost operation that returns a &str with the same
    /// lifetime constraints as the interned string.
    ///
    /// # Examples
    ///
    /// ```ignore
    /// # use bumpalo::Bump;
    /// # use hedl_core::lex::arena::StringInterner;
    /// let arena = Bump::new();
    /// let mut interner = StringInterner::new(&arena);
    ///
    /// let s = interner.intern("hello");
    /// assert_eq!(s.as_str(), "hello");
    /// ```
    pub fn as_str(&self) -> &str {
        // SAFETY: The interner guarantees:
        // - ptr and len were created from valid UTF-8
        // - The arena keeps the bytes alive
        // - We never mutate the bytes after creation
        // SAFETY: Pointer was allocated via Box::into_raw and has not been freed
        unsafe {
            std::str::from_utf8_unchecked(std::slice::from_raw_parts(self.ptr.as_ptr(), self.len))
        }
    }

    /// Get the length of the string in bytes.
    pub fn len(&self) -> usize {
        self.len
    }

    /// Returns true if the string is empty.
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Get a pointer to the first byte (for pointer equality comparison).
    pub fn as_ptr(&self) -> *const u8 {
        self.ptr.as_ptr()
    }

    // Note: to_string() is provided by Display trait implementation below
}

// Pointer equality for fast comparison
impl PartialEq for InternedString {
    fn eq(&self, other: &Self) -> bool {
        // Fast path: pointer equality (same string in arena)
        if self.ptr == other.ptr && self.len == other.len {
            return true;
        }

        // Slow path: content comparison (shouldn't happen if both are interned)
        self.as_str() == other.as_str()
    }
}

impl Eq for InternedString {}

// Hash based on pointer for fast hash table operations
impl Hash for InternedString {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // Hash the pointer, not the content (faster)
        self.ptr.hash(state);
        self.len.hash(state);
    }
}

impl std::fmt::Debug for InternedString {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{:?}", self.as_str())
    }
}

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

// Allow comparing InternedString with &str
impl PartialEq<str> for InternedString {
    fn eq(&self, other: &str) -> bool {
        self.as_str() == other
    }
}

impl PartialEq<&str> for InternedString {
    fn eq(&self, other: &&str) -> bool {
        self.as_str() == *other
    }
}

impl PartialEq<String> for InternedString {
    fn eq(&self, other: &String) -> bool {
        self.as_str() == other
    }
}

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

    #[test]
    fn test_intern_basic() {
        let arena = Bump::new();
        let mut interner = StringInterner::new(&arena);

        let s1 = interner.intern("hello");
        assert_eq!(s1.as_str(), "hello");
        assert_eq!(s1.len(), 5);
        assert!(!s1.is_empty());
    }

    #[test]
    fn test_intern_deduplication() {
        let arena = Bump::new();
        let mut interner = StringInterner::new(&arena);

        let s1 = interner.intern("Person");
        let s2 = interner.intern("Person");
        let s3 = interner.intern("Team");

        // Same string -> same pointer
        assert_eq!(s1.as_ptr(), s2.as_ptr());
        assert_ne!(s1.as_ptr(), s3.as_ptr());

        // Equality works
        assert_eq!(s1, s2);
        assert_ne!(s1, s3);

        // Only 2 unique strings
        assert_eq!(interner.len(), 2);
    }

    #[test]
    fn test_intern_empty_string() {
        let arena = Bump::new();
        let mut interner = StringInterner::new(&arena);

        let s = interner.intern("");
        assert_eq!(s.as_str(), "");
        assert_eq!(s.len(), 0);
        assert!(s.is_empty());
    }

    #[test]
    fn test_intern_unicode() {
        let arena = Bump::new();
        let mut interner = StringInterner::new(&arena);

        let s1 = interner.intern("hello 世界");
        let s2 = interner.intern("emoji 🚀");

        assert_eq!(s1.as_str(), "hello 世界");
        assert_eq!(s2.as_str(), "emoji 🚀");

        // Deduplication works with unicode
        let s3 = interner.intern("hello 世界");
        assert_eq!(s1.as_ptr(), s3.as_ptr());
    }

    #[test]
    fn test_intern_many_strings() {
        let arena = Bump::new();
        let mut interner = StringInterner::new(&arena);

        // Intern 1000 unique strings
        for i in 0..1000 {
            let s = format!("string_{}", i);
            interner.intern(&s);
        }

        assert_eq!(interner.len(), 1000);

        // Intern duplicates - should not increase count
        for i in 0..1000 {
            let s = format!("string_{}", i);
            interner.intern(&s);
        }

        assert_eq!(interner.len(), 1000);
    }

    #[test]
    fn test_intern_with_capacity() {
        let arena = Bump::new();
        let interner = StringInterner::with_capacity(&arena, 100);

        assert_eq!(interner.len(), 0);
        assert!(interner.is_empty());
    }

    #[test]
    fn test_interned_string_equality() {
        let arena = Bump::new();
        let mut interner = StringInterner::new(&arena);

        let s = interner.intern("test");

        // Compare with &str
        assert_eq!(s, "test");
        assert_ne!(s, "other");

        // Compare with String
        assert_eq!(s, String::from("test"));
        assert_ne!(s, String::from("other"));
    }

    #[test]
    fn test_interned_string_to_string() {
        let arena = Bump::new();
        let mut interner = StringInterner::new(&arena);

        let s = interner.intern("hello");
        let owned = s.to_string();

        assert_eq!(owned, "hello");
        assert_eq!(owned, s.as_str());
    }

    #[test]
    fn test_interned_string_copy() {
        let arena = Bump::new();
        let mut interner = StringInterner::new(&arena);

        let s1 = interner.intern("hello");
        let s2 = s1; // Copy

        assert_eq!(s1, s2);
        assert_eq!(s1.as_ptr(), s2.as_ptr());
    }

    #[test]
    fn test_interned_string_debug() {
        let arena = Bump::new();
        let mut interner = StringInterner::new(&arena);

        let s = interner.intern("test");
        let debug = format!("{:?}", s);

        assert_eq!(debug, "\"test\"");
    }

    #[test]
    fn test_interned_string_display() {
        let arena = Bump::new();
        let mut interner = StringInterner::new(&arena);

        let s = interner.intern("test");
        let display = format!("{}", s);

        assert_eq!(display, "test");
    }

    #[test]
    fn test_interner_stats() {
        let arena = Bump::new();
        let mut interner = StringInterner::new(&arena);

        interner.intern("hello"); // 5 bytes
        interner.intern("world"); // 5 bytes
        interner.intern("hello"); // duplicate

        let stats = interner.stats();
        assert_eq!(stats.unique_strings, 2);
        assert_eq!(stats.total_bytes_stored, 10);
    }

    #[test]
    fn test_massive_deduplication() {
        let arena = Bump::new();
        let mut interner = StringInterner::new(&arena);

        // Simulate parsing 10,000 nodes with type "Person"
        for _ in 0..10_000 {
            interner.intern("Person");
        }

        let stats = interner.stats();
        assert_eq!(stats.unique_strings, 1);
        assert_eq!(stats.total_bytes_stored, 6); // "Person" = 6 bytes

        // Without interning: 10,000 * 6 = 60,000 bytes
        // With interning: 6 bytes
        // Savings: 99.99%!
    }

    #[test]
    fn test_hash_consistency() {
        use std::collections::HashSet;

        let arena = Bump::new();
        let mut interner = StringInterner::new(&arena);

        let s1 = interner.intern("test");
        let s2 = interner.intern("test");

        let mut set = HashSet::new();
        set.insert(s1);

        assert!(set.contains(&s2)); // Same hash
    }
}