sipha_memo/

lib.rs

//! Memoization support for packrat parsing.
//!
//! This module provides memoization tables for caching parse results at specific
//! positions, enabling packrat parsing which can handle left-recursive grammars
//! and improve performance for ambiguous grammars.

use std::collections::HashMap;

use sipha_core::traits::{NodeId, RuleId, TokenKind};
use sipha_error::ParseError;

/// Memo entry storing a cached parse result.
#[derive(Clone, Debug)]
pub enum MemoEntry<K: TokenKind, R: RuleId, N: NodeId> {
    /// Successful parse result.
    Success {
        /// The resulting node.
        node: N,
        /// Number of tokens consumed.
        consumed: usize,
    },
    /// Failed parse (with error).
    Failure {
        /// The parse error.
        error: ParseError<K, R>,
        /// Number of tokens consumed before failure.
        consumed: usize,
    },
}

/// Memoization table for packrat parsing.
///
/// This table caches parse results keyed by (rule_id, position) pairs.
/// When the same rule is parsed at the same position, the cached result
/// is returned instead of re-parsing.
///
/// # When to Use
///
/// Use `MemoTable` when:
/// - Parsing left-recursive grammars (required)
/// - Parsing ambiguous grammars (improves performance)
/// - Parsing large inputs with repeated patterns
/// - Optimizing parser performance
///
/// # Usage
///
/// ```rust
/// use sipha_memo::MemoTable;
/// use sipha_tree::RawNodeId;
///
/// let mut memo: MemoTable<Token, Rule, RawNodeId> = MemoTable::new();
///
/// // Store successful parse
/// memo.store_success(Rule::Expr, 0, RawNodeId(42), 5);
///
/// // Retrieve cached result
/// if let Some(entry) = memo.get(Rule::Expr, 0) {
///     match entry {
///         MemoEntry::Success { node, consumed } => {
///             // Use cached result
///         }
///         MemoEntry::Failure { error, consumed } => {
///             // Use cached failure
///         }
///     }
/// }
/// ```
///
/// # Performance
///
/// - **Memory**: ~64 bytes per cache entry
/// - **Lookup**: O(1) average case
/// - **Storage**: O(n) where n is number of unique (rule, position) pairs
///
/// # Enabling in Parser
///
/// Enable memoization when creating `ParserState`:
///
/// ```rust
/// let mut state = ParserState::new(&tokens, &mut arena, true, ());
/// //                                                    ^^^
/// //                                              Enable memoization
/// ```
pub struct MemoTable<K: TokenKind, R: RuleId, N: NodeId> {
    /// Cache mapping (rule_id, position) -> MemoEntry
    cache: HashMap<(R, usize), MemoEntry<K, R, N>>,
    /// Whether memoization is enabled.
    enabled: bool,
}

impl<K: TokenKind, R: RuleId, N: NodeId> MemoTable<K, R, N> {
    /// Create a new empty memo table.
    pub fn new() -> Self {
        Self {
            cache: HashMap::new(),
            enabled: true,
        }
    }

    /// Create a new memo table with memoization disabled.
    pub fn disabled() -> Self {
        Self {
            cache: HashMap::new(),
            enabled: false,
        }
    }

    /// Enable or disable memoization.
    pub fn set_enabled(&mut self, enabled: bool) {
        self.enabled = enabled;
        if !enabled {
            self.clear();
        }
    }

    /// Check if memoization is enabled.
    pub fn is_enabled(&self) -> bool {
        self.enabled
    }

    /// Look up a cached result for a rule at a specific position.
    pub fn get(&self, rule_id: R, position: usize) -> Option<&MemoEntry<K, R, N>> {
        if !self.enabled {
            return None;
        }
        self.cache.get(&(rule_id, position))
    }

    /// Store a successful parse result in the cache.
    pub fn store_success(&mut self, rule_id: R, position: usize, node: N, consumed: usize) {
        if !self.enabled {
            return;
        }
        self.cache
            .insert((rule_id, position), MemoEntry::Success { node, consumed });
    }

    /// Store a failed parse result in the cache.
    pub fn store_failure(
        &mut self,
        rule_id: R,
        position: usize,
        error: ParseError<K, R>,
        consumed: usize,
    ) {
        if !self.enabled {
            return;
        }
        self.cache
            .insert((rule_id, position), MemoEntry::Failure { error, consumed });
    }

    /// Clear all cached entries.
    pub fn clear(&mut self) {
        self.cache.clear();
    }

    /// Get the number of cached entries.
    pub fn len(&self) -> usize {
        self.cache.len()
    }

    /// Check if the cache is empty.
    pub fn is_empty(&self) -> bool {
        self.cache.is_empty()
    }

    /// Get statistics about memoization performance.
    ///
    /// Returns a struct containing cache hit/miss information and
    /// memory usage estimates.
    pub fn statistics(&self) -> MemoStatistics {
        let total_entries = self.cache.len();
        let success_count = self
            .cache
            .values()
            .filter(|entry| matches!(entry, MemoEntry::Success { .. }))
            .count();
        let failure_count = total_entries - success_count;

        MemoStatistics {
            total_entries,
            success_count,
            failure_count,
            enabled: self.enabled,
        }
    }
}

/// Statistics about memoization performance.
#[derive(Clone, Debug)]
pub struct MemoStatistics {
    /// Total number of cached entries.
    pub total_entries: usize,
    /// Number of successful parse results cached.
    pub success_count: usize,
    /// Number of failed parse results cached.
    pub failure_count: usize,
    /// Whether memoization is currently enabled.
    pub enabled: bool,
}

impl MemoStatistics {
    /// Get the hit rate as a percentage (0.0 to 100.0).
    ///
    /// Note: This is a simplified metric. In practice, you'd track
    /// actual hits vs misses during parsing.
    pub fn estimated_memory_bytes(&self) -> usize {
        // Rough estimate: each entry is ~64 bytes (rule_id + position key + entry overhead)
        self.total_entries * 64
    }
}

impl<K: TokenKind, R: RuleId, N: NodeId> Default for MemoTable<K, R, N> {
    fn default() -> Self {
        Self::new()
    }
}

/// Prelude module containing commonly used types.
pub mod prelude {
    pub use crate::{MemoEntry, MemoTable};
}

#[cfg(test)]
mod tests {
    use super::*;
    use sipha_core::traits::TokenKind;
    use sipha_tree::RawNodeId;

    #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
    #[allow(dead_code)]
    enum TestToken {
        A,
    }

    impl TokenKind for TestToken {
        fn is_trivia(&self) -> bool {
            false
        }
    }

    #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
    enum TestRule {
        Expr,
    }

    #[test]
    fn test_memo_basic() {
        let mut memo: MemoTable<TestToken, TestRule, RawNodeId> = MemoTable::new();
        memo.store_success(TestRule::Expr, 0, RawNodeId(0), 5);
        assert_eq!(memo.len(), 1);
        assert!(memo.get(TestRule::Expr, 0).is_some());
    }
}