hamelin_lib 0.9.4

//! String and type interner for memory-efficient storage.
//!
//! The interner deduplicates strings and types by storing each unique value only once,
//! returning `Arc` handles that share the same underlying allocation.
//!
//! This implementation is thread-safe and can be shared across threads via `Arc<Interner>`.

use std::collections::HashSet;
use std::hash::{Hash, Hasher};
use std::sync::{Arc, RwLock};

use crate::types::array::Array;
use crate::types::function::Function;
use crate::types::map::Map;
use crate::types::range::Range;
use crate::types::struct_type::Struct;
use crate::types::tuple::Tuple;
use crate::types::Type;

/// Wrapper around Arc<str> that implements Hash/Eq based on string content.
/// This allows us to look up by &str in a HashSet<InternedString>.
#[derive(Debug, Clone)]
struct InternedString(Arc<str>);

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

impl PartialEq for InternedString {
    fn eq(&self, other: &Self) -> bool {
        self.0.as_ref() == other.0.as_ref()
    }
}

impl Eq for InternedString {}

impl std::borrow::Borrow<str> for InternedString {
    fn borrow(&self) -> &str {
        self.0.as_ref()
    }
}

/// Wrapper around Arc<Type> that implements Hash/Eq based on type content.
/// This allows us to look up by &Type in a HashSet<InternedType>.
#[derive(Debug, Clone)]
struct InternedType(Arc<Type>);

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

impl PartialEq for InternedType {
    fn eq(&self, other: &Self) -> bool {
        self.0.as_ref() == other.0.as_ref()
    }
}

impl Eq for InternedType {}

impl std::borrow::Borrow<Type> for InternedType {
    fn borrow(&self) -> &Type {
        self.0.as_ref()
    }
}

/// A thread-safe interner that deduplicates strings and types for memory efficiency.
///
/// Each unique string/type is stored once, and subsequent calls to `intern()`/`intern_type()`
/// with the same value return a clone of the existing `Arc`.
#[derive(Debug, Default)]
pub struct Interner {
    strings: RwLock<HashSet<InternedString>>,
    types: RwLock<HashSet<InternedType>>,
}

// Lock poisoning means another thread panicked — propagate the panic.
impl Interner {
    /// Create a new empty interner.
    pub fn new() -> Self {
        Self {
            strings: RwLock::new(HashSet::new()),
            types: RwLock::new(HashSet::new()),
        }
    }

    /// Intern a string, returning a shared reference.
    ///
    /// If the string has been interned before, returns a clone of the
    /// existing `Arc<str>`. Otherwise, allocates a new `Arc<str>` and
    /// stores it for future lookups.
    pub fn intern(&self, s: &str) -> Arc<str> {
        // Fast path: check if already interned with read lock
        {
            let strings = self.strings.read().expect("interner lock poisoned");
            if let Some(existing) = strings.get(s) {
                return existing.0.clone();
            }
        }

        // Slow path: acquire write lock and insert
        let mut strings = self.strings.write().expect("interner lock poisoned");

        // Double-check after acquiring write lock (another thread may have inserted)
        if let Some(existing) = strings.get(s) {
            return existing.0.clone();
        }

        // Not found - allocate once and store
        let arc: Arc<str> = Arc::from(s);
        strings.insert(InternedString(arc.clone()));
        arc
    }

    /// Intern a type, returning a shared `Arc<Type>`.
    ///
    /// Recursively interns all child types bottom-up, so identical sub-types
    /// (e.g. the `String` inside `Array(String)`) share the same allocation.
    /// If the entire type has been interned before, returns the existing `Arc<Type>`.
    pub fn intern_type(&self, t: Type) -> Arc<Type> {
        self.intern_type_arc(Arc::new(t))
    }

    /// Intern a type that is already behind an `Arc`.
    ///
    /// This is the core recursive implementation. By accepting `Arc<Type>`,
    /// compound type children (which are stored as `Arc<Type>`) can be passed
    /// directly without unwrapping and deep-cloning.
    fn intern_type_arc(&self, arc: Arc<Type>) -> Arc<Type> {
        let interned = match arc.as_ref() {
            // Unit types — no children to recurse into; intern the Arc as-is
            Type::Binary
            | Type::Boolean
            | Type::Interval
            | Type::CalendarInterval
            | Type::Int
            | Type::Double
            | Type::Rows
            | Type::String
            | Type::Timestamp
            | Type::Unknown
            | Type::Decimal(_)
            | Type::Variant => return self.intern_type_inner_arc(arc),

            // Compound types — rebuild with interned children
            Type::Array(arr) => {
                let elem = self.intern_type_arc(arr.element_type.clone());
                Array { element_type: elem }.into()
            }
            Type::Map(map) => {
                let key = self.intern_type_arc(map.key_type.clone());
                let val = self.intern_type_arc(map.value_type.clone());
                Map {
                    key_type: key,
                    value_type: val,
                }
                .into()
            }
            Type::Range(range) => {
                let of = self.intern_type_arc(range.of.clone());
                Range { of }.into()
            }
            Type::RangeInclusive(range) => {
                let of = self.intern_type_arc(range.of.clone());
                Type::RangeInclusive(Range { of })
            }
            Type::Tuple(tuple) => {
                let elements = tuple
                    .elements
                    .iter()
                    .map(|e| self.intern_type_arc(e.clone()))
                    .collect();
                Tuple { elements }.into()
            }
            Type::Function(func) => {
                let params = func
                    .params
                    .iter()
                    .map(|p| self.intern_type_arc(p.clone()))
                    .collect();
                let ret = self.intern_type_arc(func.return_type.clone());
                Function {
                    params,
                    return_type: ret,
                }
                .into()
            }
            Type::Struct(s) => {
                let fields: Vec<_> = s
                    .iter_arc()
                    .map(|(k, v)| (k.clone(), self.intern_type_arc(v.clone())))
                    .collect();
                Struct::from_arc_iter(fields).into()
            }
        };

        self.intern_type_inner(interned)
    }

    /// Insert or look up a fully-built type in the cache.
    fn intern_type_inner(&self, t: Type) -> Arc<Type> {
        self.intern_type_inner_arc(Arc::new(t))
    }

    /// Insert or look up a fully-built type that is already behind an `Arc`.
    fn intern_type_inner_arc(&self, arc: Arc<Type>) -> Arc<Type> {
        // Fast path: read lock
        {
            let types = self.types.read().expect("interner lock poisoned");
            if let Some(existing) = types.get(arc.as_ref()) {
                return existing.0.clone();
            }
        }

        // Slow path: write lock
        let mut types = self.types.write().expect("interner lock poisoned");

        if let Some(existing) = types.get(arc.as_ref()) {
            return existing.0.clone();
        }

        types.insert(InternedType(arc.clone()));
        arc
    }

    /// Returns the number of unique strings interned.
    pub fn len(&self) -> usize {
        self.strings.read().expect("interner lock poisoned").len()
    }

    /// Returns true if no strings have been interned.
    pub fn is_empty(&self) -> bool {
        self.strings
            .read()
            .expect("interner lock poisoned")
            .is_empty()
    }

    /// Returns the number of unique types interned.
    pub fn type_count(&self) -> usize {
        self.types.read().expect("interner lock poisoned").len()
    }
}

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

    #[test]
    fn test_intern_returns_same_arc() {
        let interner = Interner::new();

        let a1 = interner.intern("hello");
        let a2 = interner.intern("hello");

        // Should be the same Arc (pointer equality)
        assert!(Arc::ptr_eq(&a1, &a2));
    }

    #[test]
    fn test_intern_different_strings() {
        let interner = Interner::new();

        let a = interner.intern("hello");
        let b = interner.intern("world");

        // Different strings should have different Arcs
        assert!(!Arc::ptr_eq(&a, &b));
        assert_eq!(&*a, "hello");
        assert_eq!(&*b, "world");
    }

    #[test]
    fn test_intern_count() {
        let interner = Interner::new();

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

        interner.intern("a");
        assert_eq!(interner.len(), 1);

        interner.intern("b");
        assert_eq!(interner.len(), 2);

        // Interning same string again doesn't increase count
        interner.intern("a");
        assert_eq!(interner.len(), 2);
    }

    #[test]
    fn test_intern_type_returns_same_arc() {
        let interner = Interner::new();

        let t1 = interner.intern_type(Type::String);
        let t2 = interner.intern_type(Type::String);

        assert!(Arc::ptr_eq(&t1, &t2));
    }

    #[test]
    fn test_intern_type_different_types() {
        let interner = Interner::new();

        let t1 = interner.intern_type(Type::String);
        let t2 = interner.intern_type(Type::Int);

        assert!(!Arc::ptr_eq(&t1, &t2));
    }

    #[test]
    fn test_intern_type_compound_shares_children() {
        let interner = Interner::new();

        // Intern Array(String) — should also intern String
        let arr = interner.intern_type(Array::new(Type::String).into());
        let string = interner.intern_type(Type::String);

        // The String inside the Array should be pointer-equal to the standalone String
        if let Type::Array(a) = arr.as_ref() {
            assert!(Arc::ptr_eq(&a.element_type, &string));
        } else {
            panic!("expected Array type");
        }
    }

    #[test]
    fn test_intern_type_count() {
        let interner = Interner::new();

        assert_eq!(interner.type_count(), 0);

        interner.intern_type(Type::String);
        assert_eq!(interner.type_count(), 1);

        // Same type again
        interner.intern_type(Type::String);
        assert_eq!(interner.type_count(), 1);

        // Array(String) adds one more (the Array itself; String already cached)
        interner.intern_type(Array::new(Type::String).into());
        assert_eq!(interner.type_count(), 2);
    }
}