graph_d 1.3.2

//! String interning for memory deduplication.
//!
//! This module provides string interning to reduce memory usage by deduplicating
//! common string values found in graph properties and metadata.

use parking_lot::RwLock;
use std::collections::HashMap;

/// A string interner that maps strings to unique integer IDs.
///
/// This allows storing references to strings using small integers instead of
/// full string data, significantly reducing memory usage for duplicate strings.
pub struct StringInterner {
    /// Map from string to ID
    string_to_id: RwLock<HashMap<String, u32>>,
    /// Map from ID to string
    id_to_string: RwLock<HashMap<u32, String>>,
    /// Next available ID
    next_id: RwLock<u32>,
    /// Maximum number of strings to intern
    max_strings: usize,
}

impl StringInterner {
    /// Create a new string interner.
    pub fn new(max_strings: usize) -> Self {
        Self {
            string_to_id: RwLock::new(HashMap::with_capacity(max_strings)),
            id_to_string: RwLock::new(HashMap::with_capacity(max_strings)),
            next_id: RwLock::new(1), // Start from 1, reserve 0 for special cases
            max_strings,
        }
    }

    /// Intern a string and return its ID.
    ///
    /// If the string is already interned, returns the existing ID.
    /// If the string is new, assigns a new ID and stores the mapping.
    pub fn intern(&self, s: &str) -> u32 {
        // Check if already interned
        {
            let string_to_id = self.string_to_id.read();
            if let Some(&id) = string_to_id.get(s) {
                return id;
            }
        }

        // Not found, need to intern
        let mut string_to_id = self.string_to_id.write();
        let mut id_to_string = self.id_to_string.write();
        let mut next_id = self.next_id.write();

        // Double-check in case another thread interned it while we were waiting
        if let Some(&id) = string_to_id.get(s) {
            return id;
        }

        // Check capacity
        if string_to_id.len() >= self.max_strings {
            // TODO: Implement eviction strategy for when we hit the limit
            // For now, we'll continue to use the last ID
            return *next_id - 1;
        }

        // Create new mapping
        let id = *next_id;
        string_to_id.insert(s.to_string(), id);
        id_to_string.insert(id, s.to_string());
        *next_id += 1;

        id
    }

    /// Get the string for a given ID.
    pub fn get(&self, id: u32) -> Option<String> {
        self.id_to_string.read().get(&id).cloned()
    }

    /// Get the ID for a given string without interning it.
    pub fn get_id(&self, s: &str) -> Option<u32> {
        self.string_to_id.read().get(s).copied()
    }

    /// Get statistics about the interner.
    pub fn stats(&self) -> InternerStats {
        let string_to_id = self.string_to_id.read();
        let total_string_bytes: usize = string_to_id.keys().map(|s| s.len()).sum();

        InternerStats {
            interned_strings: string_to_id.len(),
            max_strings: self.max_strings,
            next_id: *self.next_id.read(),
            total_string_bytes,
            hash_map_overhead: string_to_id.capacity() * std::mem::size_of::<(String, u32)>(),
        }
    }

    /// Clear all interned strings.
    pub fn clear(&self) {
        self.string_to_id.write().clear();
        self.id_to_string.write().clear();
        *self.next_id.write() = 1;
    }

    /// Estimate memory savings from interning.
    pub fn estimate_savings(&self) -> MemorySavings {
        let stats = self.stats();
        let string_to_id = self.string_to_id.read();

        // Calculate how much memory would be used without interning
        let mut total_references = 0;
        let mut total_deduplicated_bytes = 0;

        for (string, _id) in string_to_id.iter() {
            // In a real implementation, we'd track how many times each string is referenced
            // For now, we'll estimate based on common patterns
            let estimated_references = match string.len() {
                0..=10 => 5,  // Short strings like "name", "id" used frequently
                11..=20 => 3, // Medium strings used moderately
                _ => 2,       // Long strings used less frequently
            };

            total_references += estimated_references;
            total_deduplicated_bytes += string.len() * (estimated_references - 1);
        }

        MemorySavings {
            total_references,
            bytes_saved: total_deduplicated_bytes,
            overhead_bytes: stats.total_string_bytes + stats.hash_map_overhead,
            net_savings: total_deduplicated_bytes.saturating_sub(stats.hash_map_overhead),
        }
    }
}

/// Statistics about string interning performance.
#[derive(Debug, Clone)]
pub struct InternerStats {
    /// Number of unique strings interned
    pub interned_strings: usize,
    /// Maximum capacity
    pub max_strings: usize,
    /// Next ID to be assigned
    pub next_id: u32,
    /// Total bytes used by interned strings
    pub total_string_bytes: usize,
    /// Memory overhead from hash map storage
    pub hash_map_overhead: usize,
}

impl InternerStats {
    /// Calculate utilization ratio (0.0 - 1.0).
    pub fn utilization(&self) -> f64 {
        self.interned_strings as f64 / self.max_strings as f64
    }

    /// Check if the interner is nearly full.
    pub fn is_nearly_full(&self) -> bool {
        self.utilization() > 0.9
    }
}

/// Memory savings analysis from string interning.
#[derive(Debug, Clone)]
pub struct MemorySavings {
    /// Total number of string references in the system
    pub total_references: usize,
    /// Bytes saved through deduplication
    pub bytes_saved: usize,
    /// Memory overhead from interning infrastructure
    pub overhead_bytes: usize,
    /// Net memory savings (saved - overhead)
    pub net_savings: usize,
}

impl MemorySavings {
    /// Calculate the compression ratio achieved.
    pub fn compression_ratio(&self) -> f64 {
        if self.total_references == 0 {
            1.0
        } else {
            (self.bytes_saved + self.overhead_bytes) as f64 / self.overhead_bytes as f64
        }
    }

    /// Check if interning is providing net benefits.
    pub fn is_beneficial(&self) -> bool {
        self.bytes_saved > self.overhead_bytes
    }
}

/// A specialized interner for common graph database strings.
///
/// This interner pre-populates with common property names and values
/// found in typical graph databases.
pub struct GraphStringInterner {
    /// Main interner
    interner: StringInterner,
    /// Pre-defined common strings
    common_strings: Vec<&'static str>,
}

impl GraphStringInterner {
    /// Create a new graph string interner with common pre-loaded strings.
    pub fn new(max_strings: usize) -> Self {
        let common_strings = vec![
            // Common property names
            "id",
            "name",
            "type",
            "value",
            "label",
            "properties",
            "created_at",
            "updated_at",
            "timestamp",
            "version",
            "source",
            "target",
            "weight",
            "distance",
            "cost",
            // Common property values
            "true",
            "false",
            "null",
            "undefined",
            "active",
            "inactive",
            "pending",
            "complete",
            "failed",
            "public",
            "private",
            "internal",
            "external",
            // Common relationship types
            "CONNECTS",
            "CONTAINS",
            "BELONGS_TO",
            "REFERENCES",
            "FOLLOWS",
            "FRIEND_OF",
            "MEMBER_OF",
            "PART_OF",
            "HAS",
            "OWNS",
            "MANAGES",
            "USES",
            "DEPENDS_ON",
        ];

        let interner = StringInterner::new(max_strings);

        // Pre-intern common strings
        for &s in &common_strings {
            interner.intern(s);
        }

        Self {
            interner,
            common_strings,
        }
    }

    /// Intern a string (delegates to the main interner).
    pub fn intern(&self, s: &str) -> u32 {
        self.interner.intern(s)
    }

    /// Get a string by ID (delegates to the main interner).
    pub fn get(&self, id: u32) -> Option<String> {
        self.interner.get(id)
    }

    /// Get interner statistics.
    pub fn stats(&self) -> InternerStats {
        self.interner.stats()
    }

    /// Get memory savings analysis.
    pub fn savings(&self) -> MemorySavings {
        self.interner.estimate_savings()
    }

    /// Check if a string is one of the pre-loaded common strings.
    pub fn is_common_string(&self, s: &str) -> bool {
        self.common_strings.contains(&s)
    }

    /// Get all pre-loaded common strings.
    pub fn common_strings(&self) -> &[&'static str] {
        &self.common_strings
    }
}

/// A reference-counted string that can be either interned or owned.
///
/// This provides an efficient way to store strings that might be duplicated
/// while allowing for strings that are unique to be stored directly.
#[derive(Debug, Clone)]
pub enum InternedString {
    /// Reference to an interned string
    Interned(u32),
    /// Owned string for unique values
    Owned(String),
}

impl InternedString {
    /// Create an interned string reference.
    pub fn interned(id: u32) -> Self {
        Self::Interned(id)
    }

    /// Create an owned string.
    pub fn owned(s: String) -> Self {
        Self::Owned(s)
    }

    /// Resolve to the actual string value using the provided interner.
    pub fn resolve(&self, interner: &StringInterner) -> Option<String> {
        match self {
            Self::Interned(id) => interner.get(*id),
            Self::Owned(s) => Some(s.clone()),
        }
    }

    /// Get the memory footprint of this string reference.
    pub fn memory_footprint(&self) -> usize {
        match self {
            Self::Interned(_) => std::mem::size_of::<u32>(),
            Self::Owned(s) => std::mem::size_of::<String>() + s.capacity(),
        }
    }
}

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

    #[test]
    fn test_string_interner() {
        let interner = StringInterner::new(100);

        // Intern some strings
        let id1 = interner.intern("hello");
        let id2 = interner.intern("world");
        let id3 = interner.intern("hello"); // Duplicate

        // Same string should get same ID
        assert_eq!(id1, id3);
        assert_ne!(id1, id2);

        // Retrieve strings
        assert_eq!(interner.get(id1), Some("hello".to_string()));
        assert_eq!(interner.get(id2), Some("world".to_string()));
        assert_eq!(interner.get(999), None);

        // Check stats
        let stats = interner.stats();
        assert_eq!(stats.interned_strings, 2);
        assert!(stats.total_string_bytes > 0);
    }

    #[test]
    fn test_graph_string_interner() {
        let interner = GraphStringInterner::new(1000);

        // Common strings should already be interned
        let id1 = interner.intern("name");
        let id2 = interner.intern("name"); // Should be same ID
        assert_eq!(id1, id2);

        // Check if it's recognized as common
        assert!(interner.is_common_string("name"));
        assert!(!interner.is_common_string("some_unique_property"));

        let stats = interner.stats();
        assert!(stats.interned_strings >= interner.common_strings().len());
    }

    #[test]
    fn test_interned_string() {
        let interner = StringInterner::new(100);
        let id = interner.intern("test");

        let interned = InternedString::interned(id);
        let owned = InternedString::owned("unique".to_string());

        assert_eq!(interned.resolve(&interner), Some("test".to_string()));
        assert_eq!(owned.resolve(&interner), Some("unique".to_string()));

        // Check memory footprints
        assert_eq!(interned.memory_footprint(), 4); // u32
        assert!(owned.memory_footprint() > 4); // String overhead + capacity
    }

    #[test]
    fn test_memory_savings() {
        let interner = StringInterner::new(100);

        // Intern some strings multiple times (simulating duplicates)
        for _ in 0..10 {
            interner.intern("name");
            interner.intern("type");
            interner.intern("value");
        }

        let savings = interner.estimate_savings();
        assert!(savings.bytes_saved > 0);
        assert!(savings.total_references > 0);
    }

    #[test]
    fn test_interner_capacity() {
        let interner = StringInterner::new(2); // Very small capacity

        let id1 = interner.intern("first");
        let id2 = interner.intern("second");
        let id3 = interner.intern("third"); // Should hit capacity limit

        assert_ne!(id1, id2);
        // id3 should reuse the last ID due to capacity limit
        assert_eq!(id3, id2);
    }

    #[test]
    fn test_interner_stats() {
        let interner = StringInterner::new(100);

        interner.intern("test1");
        interner.intern("test2");
        interner.intern("longer_string_for_testing");

        let stats = interner.stats();
        assert_eq!(stats.interned_strings, 3);
        assert!(stats.total_string_bytes >= 30); // Rough estimate
        assert!(!stats.is_nearly_full());
        assert!(stats.utilization() < 0.1);
    }
}