//! Parser caching system for memoization.
//!
//! This module provides the caching strategy used by parsers to avoid redundant parsing work.
//! The [`ParsingCache`] trait allows pluggable cache implementations, while concrete types
//! like [`BasicCache`] and [`NoCache`] provide different memory/performance trade-offs.
//!
//! The cache uses `(parser_id, input_position)` tuples as keys, storing both the parsed
//! result and the final position after parsing. This enables parsers to skip work when
//! the same parser is applied at the same input position multiple times.

use std::{any::Any, collections::BTreeMap};

/// Implementors of this trait can be used as the cache that is
/// plugged in to the [`Parser`](crate::Parser) trait.
pub trait ParsingCache {
    fn lookup<T>(&self, parser_id: u64, idx: u64) -> Option<(T, u64)>
    where
        T: Any + Clone;

    fn record<T>(&mut self, parser_id: u64, idx: u64, value: T, after: u64)
    where
        T: Any + Clone;
}

/// This is a simple cache which retains everything added to it until
/// the entire cache is discarded. It's appropriate for the common
/// case, but since it does not perform any eviction it will
/// eventually run out of memory if you use it for a large enough
/// input.
pub type BasicCache = BTreeMap<(u64, u64), (Box<dyn Any>, u64)>;

impl ParsingCache for BasicCache {
    fn lookup<T>(&self, parser_id: u64, idx: u64) -> Option<(T, u64)>
    where
        T: Any + Clone,
    {
        let key = (parser_id, idx);
        self.get(&key)
            .and_then(|(v, a)| v.downcast_ref().map(|v: &T| (v.clone(), *a)))
    }

    fn record<T>(&mut self, parser_id: u64, idx: u64, value: T, after: u64)
    where
        T: Any + Clone,
    {
        self.insert((parser_id, idx), (Box::new(value), after));
    }
}

/// This 'cache' does not in fact cache anything, so using it for the
/// parser cache disables caching entirely. This will not change the
/// end result of parsing any given input, but it will result in a
/// loss of speed in exchange for lower memory requirements.
pub struct NoCache;

impl ParsingCache for NoCache {
    fn lookup<T>(&self, _parser_id: u64, _idx: u64) -> Option<(T, u64)>
    where
        T: Any + Clone,
    {
        None
    }

    fn record<T>(&mut self, _parser_id: u64, _idx: u64, _value: T, _after: u64)
    where
        T: Any + Clone,
    {
    }
}

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

    #[test]
    fn test_basic_cache_record_and_lookup() {
        let mut cache = BasicCache::new();

        cache.record::<String>(9, 4, "hello".to_string(), 5);

        let result = cache.lookup::<String>(9, 4);
        assert_eq!(result, Some(("hello".to_string(), 5)));
    }

    #[test]
    fn test_basic_cache_miss() {
        let cache = BasicCache::new();

        let result = cache.lookup::<String>(3, 3);
        assert_eq!(result, None);
    }

    #[test]
    fn test_basic_cache_type_isolation() {
        let mut cache = BasicCache::new();

        cache.record::<String>(4, 0, "hello".to_string(), 5);
        cache.record::<String>(5, 0, "world".to_string(), 5);

        let result1 = cache.lookup::<String>(4, 0);
        let result2 = cache.lookup::<String>(5, 0);

        assert_eq!(result1, Some(("hello".to_string(), 5)));
        assert_eq!(result2, Some(("world".to_string(), 5)));
    }

    #[test]
    fn test_basic_cache_position_isolation() {
        let mut cache = BasicCache::new();

        cache.record::<String>(1, 0, "hello".to_string(), 5);
        cache.record::<String>(1, 10, "world".to_string(), 15);

        let result1 = cache.lookup::<String>(1, 0);
        let result2 = cache.lookup::<String>(1, 10);
        let result3 = cache.lookup::<String>(1, 5);

        assert_eq!(result1, Some(("hello".to_string(), 5)));
        assert_eq!(result2, Some(("world".to_string(), 15)));
        assert_eq!(result3, None);
    }

    #[test]
    fn test_basic_cache_different_value_types() {
        let mut cache = BasicCache::new();

        cache.record::<String>(1, 0, "hello".to_string(), 5);
        cache.record::<i32>(1, 1, 42, 2);
        cache.record::<Vec<u8>>(1, 2, vec![1, 2, 3], 3);

        let result1 = cache.lookup::<String>(1, 0);
        let result2 = cache.lookup::<i32>(1, 1);
        let result3 = cache.lookup::<Vec<u8>>(1, 2);

        assert_eq!(result1, Some(("hello".to_string(), 5)));
        assert_eq!(result2, Some((42, 2)));
        assert_eq!(result3, Some((vec![1, 2, 3], 3)));
    }

    #[test]
    fn test_basic_cache_overwrite() {
        let mut cache = BasicCache::new();

        cache.record::<String>(1, 0, "hello".to_string(), 5);
        cache.record::<String>(1, 0, "world".to_string(), 10);

        let result = cache.lookup::<String>(1, 0);
        assert_eq!(result, Some(("world".to_string(), 10)));
    }

    #[test]
    fn test_basic_cache_multiple_entries() {
        let mut cache = BasicCache::new();

        for i in 0..100 {
            cache.record::<i32>(1, i, i as i32 * 2, i + 1);
        }

        for i in 0..100 {
            let result = cache.lookup::<i32>(1, i);
            assert_eq!(result, Some((i as i32 * 2, i + 1)));
        }
    }

    #[test]
    fn test_basic_cache_clone_values() {
        let mut cache = BasicCache::new();

        let original = vec![1, 2, 3, 4, 5];
        cache.record::<Vec<i32>>(1, 0, original.clone(), 5);

        let result1 = cache.lookup::<Vec<i32>>(1, 0);
        let result2 = cache.lookup::<Vec<i32>>(1, 0);

        assert_eq!(result1, Some((original.clone(), 5)));
        assert_eq!(result2, Some((original, 5)));
    }

    #[test]
    fn test_no_cache_always_misses() {
        let mut cache = NoCache;

        cache.record::<String>(1, 0, "hello".to_string(), 5);

        let result = cache.lookup::<String>(1, 0);
        assert_eq!(result, None);
    }

    #[test]
    fn test_no_cache_multiple_operations() {
        let mut cache = NoCache;

        for i in 0..10 {
            cache.record::<i32>(1, i, i as i32, i + 1);
        }

        for i in 0..10 {
            let result = cache.lookup::<i32>(1, i);
            assert_eq!(result, None);
        }
    }

    #[test]
    fn test_cache_with_zero_positions() {
        let mut cache = BasicCache::new();

        cache.record::<String>(1, 0, "start".to_string(), 0);
        cache.record::<String>(1, 0, "same".to_string(), 0);

        let result = cache.lookup::<String>(1, 0);
        assert_eq!(result, Some(("same".to_string(), 0)));
    }

    #[test]
    fn test_cache_with_large_positions() {
        let mut cache = BasicCache::new();

        let large_pos = u64::MAX - 1;
        cache.record::<String>(1, large_pos, "large".to_string(), u64::MAX);

        let result = cache.lookup::<String>(1, large_pos);
        assert_eq!(result, Some(("large".to_string(), u64::MAX)));
    }

    #[test]
    fn test_cache_type_safety() {
        let mut cache = BasicCache::new();

        cache.record::<String>(1, 0, "hello".to_string(), 5);

        let result = cache.lookup::<i32>(1, 0);
        assert_eq!(result, None);

        let result = cache.lookup::<String>(1, 0);
        assert_eq!(result, Some(("hello".to_string(), 5)));
    }

    #[test]
    fn test_cache_empty_string() {
        let mut cache = BasicCache::new();

        cache.record::<String>(1, 0, String::new(), 0);

        let result = cache.lookup::<String>(1, 0);
        assert_eq!(result, Some((String::new(), 0)));
    }

    #[test]
    fn test_cache_complex_types() {
        let mut cache = BasicCache::new();

        let complex_value = (vec![1, 2, 3], "hello".to_string(), Some(42));
        cache.record::<_>(1, 0, complex_value.clone(), 10);

        let result = cache.lookup::<(Vec<i32>, String, Option<i32>)>(1, 0);
        assert_eq!(result, Some((complex_value, 10)));
    }
}