sqry_core/cache/

policy.rs

// RKG: CODE:SQRY-CORE implements REQ:SQRY-P2-6-CACHE-EVICTION-POLICY
//! Cache eviction policy types and metrics.
//!
//! This module encapsulates the eviction/admission policies that drive
//! `CacheStorage`. Policies are responsible for tracking access patterns,
//! deciding whether new entries should be admitted, surfacing eviction events,
//! and exposing telemetry counters for CLI/debug tooling.

use crossbeam_queue::SegQueue;
use dashmap::DashMap;
use moka::policy::EvictionPolicy;
use moka::sync::Cache;
use parking_lot::Mutex;
use std::collections::VecDeque;
use std::fmt;
use std::hash::Hash;
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, AtomicU32, AtomicU64, Ordering};

/// Available cache eviction policies.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum CachePolicyKind {
    /// Default least-recently-used (current behaviour).
    #[default]
    Lru,
    /// Windowed `TinyLFU` admission with protected hot set.
    TinyLfu,
    /// Hybrid policy (LRU window + `TinyLFU` protected region).
    Hybrid,
}

impl CachePolicyKind {
    /// Parse a policy kind from a string (env/config value).
    #[must_use]
    pub fn parse(value: &str) -> Option<Self> {
        match value.trim().to_ascii_lowercase().as_str() {
            "lru" => Some(Self::Lru),
            "tiny_lfu" | "tinylfu" | "lfu" => Some(Self::TinyLfu),
            "hybrid" | "window_lfu" | "windowed_lfu" => Some(Self::Hybrid),
            _ => None,
        }
    }

    /// Human-readable representation (used in debug output).
    #[must_use]
    pub const fn as_str(self) -> &'static str {
        match self {
            Self::Lru => "lru",
            Self::TinyLfu => "tiny_lfu",
            Self::Hybrid => "hybrid",
        }
    }
}

impl fmt::Display for CachePolicyKind {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(self.as_str())
    }
}

/// Telemetry counters for eviction policies.
#[derive(Debug, Clone, Copy)]
pub struct CachePolicyMetrics {
    /// Policy used for the measurement.
    pub kind: CachePolicyKind,
    /// Number of insertions rejected by the policy (e.g., `TinyLFU` drop).
    pub lfu_rejects: usize,
    /// Number of evictions that removed a hot/protected entry.
    pub hot_evictions: usize,
    /// Number of cold LRU evictions.
    pub cold_evictions: usize,
    /// Hits served from the protected (hot) region.
    pub protected_hits: usize,
}

impl CachePolicyMetrics {
    /// Create metrics with the provided policy kind.
    #[must_use]
    pub const fn with_kind(kind: CachePolicyKind) -> Self {
        Self {
            kind,
            lfu_rejects: 0,
            hot_evictions: 0,
            cold_evictions: 0,
            protected_hits: 0,
        }
    }
}

impl Default for CachePolicyMetrics {
    fn default() -> Self {
        Self::with_kind(CachePolicyKind::Lru)
    }
}

/// Outcome of an admission attempt.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum CacheAdmission {
    /// Entry was accepted and should be inserted into the storage layer.
    Accepted,
    /// Entry was rejected by the policy (e.g., `TinyLFU` frequency too low).
    Rejected,
}

/// High-level description of an eviction performed by the policy.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum CacheEvictionKind {
    /// Protected entry (considered hot) was evicted.
    Hot,
    /// Regular entry was evicted.
    Cold,
}

/// Eviction data returned by policies.
#[derive(Debug, Clone)]
pub struct CachePolicyEviction<K> {
    /// Key that must be removed from the cache storage.
    pub key: K,
    /// Whether the eviction targeted a hot/protected entry.
    pub kind: CacheEvictionKind,
}

/// Policy abstraction consumed by caches.
pub trait CachePolicy<K>: Send + Sync
where
    K: Eq + Hash + Clone + Send + Sync + 'static,
{
    /// Policy kind (for telemetry + configuration reflection).
    fn kind(&self) -> CachePolicyKind;

    /// Decide whether an entry should be admitted.
    fn admit(&self, key: &K, weight_bytes: u64) -> CacheAdmission;

    /// Record a cache hit (returns whether the hit was served from the protected set).
    fn record_hit(&self, key: &K) -> bool;

    /// Remove policy metadata for a key (called when entries are explicitly cleared).
    fn invalidate(&self, key: &K);

    /// Drain pending eviction events generated by the policy implementation.
    fn drain_evictions(&self) -> Vec<CachePolicyEviction<K>>;

    /// Reset policy state (used when wiping the cache).
    fn reset(&self);

    /// Snapshot policy metrics.
    fn stats(&self) -> CachePolicyMetrics;
}

/// Configuration data required to build a policy implementation.
#[derive(Debug, Clone, Copy)]
pub struct CachePolicyConfig {
    /// Policy variant to instantiate.
    pub kind: CachePolicyKind,
    /// Maximum number of bytes available to the cache.
    pub max_bytes: u64,
    /// Fraction of the budget reserved for the protected window.
    pub window_ratio: f32,
}

impl CachePolicyConfig {
    /// Create a new config descriptor.
    #[must_use]
    pub fn new(kind: CachePolicyKind, max_bytes: u64, window_ratio: f32) -> Self {
        Self {
            kind,
            max_bytes,
            window_ratio,
        }
    }
}

/// Build the appropriate policy implementation for the supplied configuration.
#[must_use]
pub fn build_cache_policy<K>(config: &CachePolicyConfig) -> Arc<dyn CachePolicy<K>>
where
    K: Eq + Hash + Clone + Send + Sync + 'static,
{
    match config.kind {
        CachePolicyKind::Lru => Arc::new(LruPolicy::new()),
        CachePolicyKind::TinyLfu | CachePolicyKind::Hybrid => Arc::new(TinyLfuPolicy::new(config)),
    }
}

/// No-op policy for classic LRU behaviour.
struct LruPolicy;

impl LruPolicy {
    fn new() -> Self {
        Self
    }
}

impl<K> CachePolicy<K> for LruPolicy
where
    K: Eq + Hash + Clone + Send + Sync + 'static,
{
    fn kind(&self) -> CachePolicyKind {
        CachePolicyKind::Lru
    }

    fn admit(&self, _key: &K, _weight_bytes: u64) -> CacheAdmission {
        CacheAdmission::Accepted
    }

    fn record_hit(&self, _key: &K) -> bool {
        false
    }

    fn invalidate(&self, _key: &K) {}

    fn drain_evictions(&self) -> Vec<CachePolicyEviction<K>> {
        Vec::new()
    }

    fn reset(&self) {}

    fn stats(&self) -> CachePolicyMetrics {
        CachePolicyMetrics::with_kind(CachePolicyKind::Lru)
    }
}

/// Event emitted by the `TinyLFU` metadata cache when an entry is removed.
#[derive(Debug)]
struct PolicyVictim<K> {
    key: K,
}

#[derive(Debug)]
struct ProtectedEntry {
    weight: u32,
    hits: AtomicU32,
    protected: AtomicBool,
}

impl ProtectedEntry {
    fn new(weight: u32) -> Self {
        Self {
            weight,
            hits: AtomicU32::new(0),
            protected: AtomicBool::new(false),
        }
    }
}

#[derive(Default)]
struct PolicyMetricCounters {
    lfu_rejects: AtomicU64,
    hot_evictions: AtomicU64,
    cold_evictions: AtomicU64,
    protected_hits: AtomicU64,
}

impl PolicyMetricCounters {
    fn snapshot(&self, kind: CachePolicyKind) -> CachePolicyMetrics {
        fn u64_to_usize(value: u64) -> usize {
            usize::try_from(value).unwrap_or(usize::MAX)
        }

        CachePolicyMetrics {
            kind,
            lfu_rejects: u64_to_usize(self.lfu_rejects.load(Ordering::Relaxed)),
            hot_evictions: u64_to_usize(self.hot_evictions.load(Ordering::Relaxed)),
            cold_evictions: u64_to_usize(self.cold_evictions.load(Ordering::Relaxed)),
            protected_hits: u64_to_usize(self.protected_hits.load(Ordering::Relaxed)),
        }
    }

    fn reset(&self) {
        self.lfu_rejects.store(0, Ordering::Relaxed);
        self.hot_evictions.store(0, Ordering::Relaxed);
        self.cold_evictions.store(0, Ordering::Relaxed);
        self.protected_hits.store(0, Ordering::Relaxed);
    }
}

struct TinyLfuPolicy<K>
where
    K: Eq + Hash + Clone + Send + Sync + 'static,
{
    kind: CachePolicyKind,
    cache: Cache<K, u32>,
    victims: Arc<SegQueue<PolicyVictim<K>>>,
    protected: DashMap<K, Arc<ProtectedEntry>>,
    protected_order: Mutex<VecDeque<K>>,
    protected_budget: u64,
    protected_bytes: AtomicU64,
    metrics: PolicyMetricCounters,
    promotion_threshold: u32,
}

impl<K> TinyLfuPolicy<K>
where
    K: Eq + Hash + Clone + Send + Sync + 'static,
{
    fn new(config: &CachePolicyConfig) -> Self {
        let victims = Arc::new(SegQueue::<PolicyVictim<K>>::new());
        let victims_clone = Arc::clone(&victims);
        let max_bytes = config.max_bytes.max(1);
        let eviction_policy = match config.kind {
            CachePolicyKind::Lru => EvictionPolicy::lru(),
            CachePolicyKind::TinyLfu | CachePolicyKind::Hybrid => EvictionPolicy::tiny_lfu(),
        };

        let cache = Cache::builder()
            .max_capacity(max_bytes)
            .eviction_policy(eviction_policy)
            .weigher(|_, weight: &u32| *weight)
            .eviction_listener(move |key: Arc<K>, _weight: u32, cause| {
                if cause.was_evicted() {
                    victims_clone.push(PolicyVictim {
                        key: (*key).clone(),
                    });
                }
            })
            .build();

        let window_ratio = clamp_ratio(config.window_ratio);
        let protected_budget = scale_u64_by_ratio(max_bytes, window_ratio).max(1);

        Self {
            kind: config.kind,
            cache,
            victims,
            protected: DashMap::new(),
            protected_order: Mutex::new(VecDeque::new()),
            protected_budget,
            protected_bytes: AtomicU64::new(0),
            metrics: PolicyMetricCounters::default(),
            promotion_threshold: 3,
        }
    }

    fn clamp_weight(weight_bytes: u64) -> u32 {
        u32::try_from(weight_bytes).unwrap_or(u32::MAX).max(1)
    }

    fn promote(&self, key: K, entry: &ProtectedEntry) {
        if entry.protected.swap(true, Ordering::Relaxed) {
            return;
        }

        self.protected_bytes
            .fetch_add(u64::from(entry.weight), Ordering::Relaxed);
        self.protected_order.lock().push_back(key);
        self.rebalance_protected_budget();
    }

    fn demote_key(&self, key: &K) {
        if let Some(entry) = self.protected.get(key)
            && entry.protected.swap(false, Ordering::Relaxed)
        {
            self.protected_bytes
                .fetch_sub(u64::from(entry.weight), Ordering::Relaxed);
        }
    }

    fn rebalance_protected_budget(&self) {
        while self.protected_bytes.load(Ordering::Relaxed) > self.protected_budget {
            let Some(next) = self.protected_order.lock().pop_front() else {
                break;
            };
            self.demote_key(&next);
        }
    }

    fn handle_eviction(&self, victim: PolicyVictim<K>) -> CachePolicyEviction<K> {
        if let Some((_, entry)) = self.protected.remove(&victim.key) {
            if entry.protected.swap(false, Ordering::Relaxed) {
                self.metrics.hot_evictions.fetch_add(1, Ordering::Relaxed);
                self.protected_bytes
                    .fetch_sub(u64::from(entry.weight), Ordering::Relaxed);
                CachePolicyEviction {
                    key: victim.key,
                    kind: CacheEvictionKind::Hot,
                }
            } else {
                self.metrics.cold_evictions.fetch_add(1, Ordering::Relaxed);
                CachePolicyEviction {
                    key: victim.key,
                    kind: CacheEvictionKind::Cold,
                }
            }
        } else {
            self.metrics.cold_evictions.fetch_add(1, Ordering::Relaxed);
            CachePolicyEviction {
                key: victim.key,
                kind: CacheEvictionKind::Cold,
            }
        }
    }
}

impl<K> CachePolicy<K> for TinyLfuPolicy<K>
where
    K: Eq + Hash + Clone + Send + Sync + 'static,
{
    fn kind(&self) -> CachePolicyKind {
        self.kind
    }

    fn admit(&self, key: &K, weight_bytes: u64) -> CacheAdmission {
        let weight = Self::clamp_weight(weight_bytes);
        self.cache.insert(key.clone(), weight);
        self.cache.run_pending_tasks();

        self.protected
            .entry(key.clone())
            .or_insert_with(|| Arc::new(ProtectedEntry::new(weight)));

        if self.cache.contains_key(key) {
            CacheAdmission::Accepted
        } else {
            self.metrics.lfu_rejects.fetch_add(1, Ordering::Relaxed);
            self.protected.remove(key);
            CacheAdmission::Rejected
        }
    }

    fn record_hit(&self, key: &K) -> bool {
        let _ = self.cache.get(key);
        if let Some(entry) = self.protected.get(key) {
            let hits = entry.hits.fetch_add(1, Ordering::Relaxed) + 1;
            if hits >= self.promotion_threshold {
                self.promote(key.clone(), &entry);
            }
            if entry.protected.load(Ordering::Relaxed) {
                self.metrics.protected_hits.fetch_add(1, Ordering::Relaxed);
                return true;
            }
        }
        false
    }

    fn invalidate(&self, key: &K) {
        if let Some((_, entry)) = self.protected.remove(key)
            && entry.protected.swap(false, Ordering::Relaxed)
        {
            self.protected_bytes
                .fetch_sub(u64::from(entry.weight), Ordering::Relaxed);
        }
        self.cache.invalidate(key);
        self.cache.run_pending_tasks();
    }

    fn drain_evictions(&self) -> Vec<CachePolicyEviction<K>> {
        self.cache.run_pending_tasks();
        let mut victims = Vec::new();
        while let Some(event) = self.victims.pop() {
            victims.push(self.handle_eviction(event));
        }
        victims
    }

    fn reset(&self) {
        self.cache.invalidate_all();
        self.cache.run_pending_tasks();
        while self.victims.pop().is_some() {}
        self.protected.clear();
        self.protected_order.lock().clear();
        self.protected_bytes.store(0, Ordering::Relaxed);
        self.metrics.reset();
    }

    fn stats(&self) -> CachePolicyMetrics {
        self.metrics.snapshot(self.kind())
    }
}

fn clamp_ratio(ratio: f32) -> f32 {
    if ratio.is_nan() || !ratio.is_finite() {
        0.20
    } else {
        ratio.clamp(0.05, 0.95)
    }
}

fn scale_u64_by_ratio(value: u64, ratio: f32) -> u64 {
    let scaled = {
        #[allow(clippy::cast_precision_loss)]
        {
            (value as f64) * f64::from(ratio)
        }
    };
    if !scaled.is_finite() || scaled <= 0.0 {
        return 0;
    }
    let capped = {
        #[allow(clippy::cast_precision_loss)]
        {
            scaled.min(u64::MAX as f64)
        }
    };
    #[allow(
        clippy::cast_possible_truncation,
        clippy::cast_precision_loss,
        clippy::cast_sign_loss
    )]
    {
        capped.round() as u64
    }
}

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

    // CachePolicyKind tests
    #[test]
    fn test_cache_policy_kind_parse_lru() {
        assert_eq!(CachePolicyKind::parse("lru"), Some(CachePolicyKind::Lru));
        assert_eq!(CachePolicyKind::parse("LRU"), Some(CachePolicyKind::Lru));
        assert_eq!(
            CachePolicyKind::parse("  lru  "),
            Some(CachePolicyKind::Lru)
        );
    }

    #[test]
    fn test_cache_policy_kind_parse_tiny_lfu() {
        assert_eq!(
            CachePolicyKind::parse("tiny_lfu"),
            Some(CachePolicyKind::TinyLfu)
        );
        assert_eq!(
            CachePolicyKind::parse("tinylfu"),
            Some(CachePolicyKind::TinyLfu)
        );
        assert_eq!(
            CachePolicyKind::parse("lfu"),
            Some(CachePolicyKind::TinyLfu)
        );
        assert_eq!(
            CachePolicyKind::parse("LFU"),
            Some(CachePolicyKind::TinyLfu)
        );
    }

    #[test]
    fn test_cache_policy_kind_parse_hybrid() {
        assert_eq!(
            CachePolicyKind::parse("hybrid"),
            Some(CachePolicyKind::Hybrid)
        );
        assert_eq!(
            CachePolicyKind::parse("window_lfu"),
            Some(CachePolicyKind::Hybrid)
        );
        assert_eq!(
            CachePolicyKind::parse("windowed_lfu"),
            Some(CachePolicyKind::Hybrid)
        );
        assert_eq!(
            CachePolicyKind::parse("HYBRID"),
            Some(CachePolicyKind::Hybrid)
        );
    }

    #[test]
    fn test_cache_policy_kind_parse_invalid() {
        assert_eq!(CachePolicyKind::parse("unknown"), None);
        assert_eq!(CachePolicyKind::parse(""), None);
        assert_eq!(CachePolicyKind::parse("fifo"), None);
    }

    #[test]
    fn test_cache_policy_kind_as_str() {
        assert_eq!(CachePolicyKind::Lru.as_str(), "lru");
        assert_eq!(CachePolicyKind::TinyLfu.as_str(), "tiny_lfu");
        assert_eq!(CachePolicyKind::Hybrid.as_str(), "hybrid");
    }

    #[test]
    fn test_cache_policy_kind_default() {
        assert_eq!(CachePolicyKind::default(), CachePolicyKind::Lru);
    }

    #[test]
    fn test_cache_policy_kind_display() {
        assert_eq!(format!("{}", CachePolicyKind::Lru), "lru");
        assert_eq!(format!("{}", CachePolicyKind::TinyLfu), "tiny_lfu");
        assert_eq!(format!("{}", CachePolicyKind::Hybrid), "hybrid");
    }

    #[test]
    fn test_cache_policy_kind_eq() {
        assert_eq!(CachePolicyKind::Lru, CachePolicyKind::Lru);
        assert_ne!(CachePolicyKind::Lru, CachePolicyKind::TinyLfu);
    }

    #[test]
    fn test_cache_policy_kind_clone() {
        let kind = CachePolicyKind::TinyLfu;
        let cloned = kind;
        assert_eq!(kind, cloned);
    }

    // CachePolicyMetrics tests
    #[test]
    fn test_cache_policy_metrics_with_kind() {
        let metrics = CachePolicyMetrics::with_kind(CachePolicyKind::TinyLfu);
        assert_eq!(metrics.kind, CachePolicyKind::TinyLfu);
        assert_eq!(metrics.lfu_rejects, 0);
        assert_eq!(metrics.hot_evictions, 0);
        assert_eq!(metrics.cold_evictions, 0);
        assert_eq!(metrics.protected_hits, 0);
    }

    #[test]
    fn test_cache_policy_metrics_default() {
        let metrics = CachePolicyMetrics::default();
        assert_eq!(metrics.kind, CachePolicyKind::Lru);
        assert_eq!(metrics.lfu_rejects, 0);
    }

    // CacheAdmission tests
    #[test]
    fn test_cache_admission_eq() {
        assert_eq!(CacheAdmission::Accepted, CacheAdmission::Accepted);
        assert_ne!(CacheAdmission::Accepted, CacheAdmission::Rejected);
    }

    // CacheEvictionKind tests
    #[test]
    fn test_cache_eviction_kind_eq() {
        assert_eq!(CacheEvictionKind::Hot, CacheEvictionKind::Hot);
        assert_ne!(CacheEvictionKind::Hot, CacheEvictionKind::Cold);
    }

    // CachePolicyConfig tests
    #[test]
    fn test_cache_policy_config_new() {
        let config = CachePolicyConfig::new(CachePolicyKind::TinyLfu, 1024 * 1024, 0.2);
        assert_eq!(config.kind, CachePolicyKind::TinyLfu);
        assert_eq!(config.max_bytes, 1024 * 1024);
        assert!((config.window_ratio - 0.2).abs() < f32::EPSILON);
    }

    // clamp_ratio tests
    #[test]
    fn test_clamp_ratio_normal() {
        assert!((clamp_ratio(0.5) - 0.5).abs() < f32::EPSILON);
        assert!((clamp_ratio(0.2) - 0.2).abs() < f32::EPSILON);
    }

    #[test]
    fn test_clamp_ratio_too_low() {
        // Below 0.05 clamps to 0.05
        assert!((clamp_ratio(0.01) - 0.05).abs() < f32::EPSILON);
        assert!((clamp_ratio(0.0) - 0.05).abs() < f32::EPSILON);
    }

    #[test]
    fn test_clamp_ratio_too_high() {
        // Above 0.95 clamps to 0.95
        assert!((clamp_ratio(0.99) - 0.95).abs() < f32::EPSILON);
        assert!((clamp_ratio(1.0) - 0.95).abs() < f32::EPSILON);
    }

    #[test]
    fn test_clamp_ratio_nan() {
        // NaN defaults to 0.20
        assert!((clamp_ratio(f32::NAN) - 0.20).abs() < f32::EPSILON);
    }

    #[test]
    fn test_clamp_ratio_infinity() {
        // Infinity defaults to 0.20
        assert!((clamp_ratio(f32::INFINITY) - 0.20).abs() < f32::EPSILON);
        assert!((clamp_ratio(f32::NEG_INFINITY) - 0.20).abs() < f32::EPSILON);
    }

    // scale_u64_by_ratio tests
    #[test]
    fn test_scale_u64_by_ratio_normal() {
        assert_eq!(scale_u64_by_ratio(1000, 0.5), 500);
        assert_eq!(scale_u64_by_ratio(100, 0.1), 10);
    }

    #[test]
    fn test_scale_u64_by_ratio_zero_value() {
        assert_eq!(scale_u64_by_ratio(0, 0.5), 0);
    }

    #[test]
    fn test_scale_u64_by_ratio_zero_ratio() {
        assert_eq!(scale_u64_by_ratio(1000, 0.0), 0);
    }

    #[test]
    fn test_scale_u64_by_ratio_negative_ratio() {
        // Negative ratio returns 0
        assert_eq!(scale_u64_by_ratio(1000, -0.5), 0);
    }

    #[test]
    fn test_scale_u64_by_ratio_nan() {
        // NaN ratio returns 0
        assert_eq!(scale_u64_by_ratio(1000, f32::NAN), 0);
    }

    #[test]
    fn test_scale_u64_by_ratio_rounding() {
        // 1000 * 0.33 = 330.0 (rounds to 330)
        assert_eq!(scale_u64_by_ratio(1000, 0.33), 330);
        // 1000 * 0.335 = 335.0 (rounds to 335)
        assert_eq!(scale_u64_by_ratio(1000, 0.335), 335);
    }

    // LruPolicy tests
    #[test]
    fn test_lru_policy_kind() {
        let policy: Arc<dyn CachePolicy<String>> =
            build_cache_policy(&CachePolicyConfig::new(CachePolicyKind::Lru, 1024, 0.2));
        assert_eq!(policy.kind(), CachePolicyKind::Lru);
    }

    #[test]
    fn test_lru_policy_always_admits() {
        let policy: Arc<dyn CachePolicy<String>> =
            build_cache_policy(&CachePolicyConfig::new(CachePolicyKind::Lru, 1024, 0.2));
        assert_eq!(
            policy.admit(&"key".to_string(), 100),
            CacheAdmission::Accepted
        );
    }

    #[test]
    fn test_lru_policy_record_hit_returns_false() {
        let policy: Arc<dyn CachePolicy<String>> =
            build_cache_policy(&CachePolicyConfig::new(CachePolicyKind::Lru, 1024, 0.2));
        // LRU policy doesn't track protected hits
        assert!(!policy.record_hit(&"key".to_string()));
    }

    #[test]
    fn test_lru_policy_drain_evictions_empty() {
        let policy: Arc<dyn CachePolicy<String>> =
            build_cache_policy(&CachePolicyConfig::new(CachePolicyKind::Lru, 1024, 0.2));
        assert!(policy.drain_evictions().is_empty());
    }

    #[test]
    fn test_lru_policy_stats() {
        let policy: Arc<dyn CachePolicy<String>> =
            build_cache_policy(&CachePolicyConfig::new(CachePolicyKind::Lru, 1024, 0.2));
        let stats = policy.stats();
        assert_eq!(stats.kind, CachePolicyKind::Lru);
        assert_eq!(stats.lfu_rejects, 0);
    }

    // TinyLfuPolicy tests
    #[test]
    fn test_tiny_lfu_policy_kind() {
        let policy: Arc<dyn CachePolicy<String>> =
            build_cache_policy(&CachePolicyConfig::new(CachePolicyKind::TinyLfu, 1024, 0.2));
        assert_eq!(policy.kind(), CachePolicyKind::TinyLfu);
    }

    #[test]
    fn test_hybrid_policy_kind() {
        let policy: Arc<dyn CachePolicy<String>> =
            build_cache_policy(&CachePolicyConfig::new(CachePolicyKind::Hybrid, 1024, 0.2));
        assert_eq!(policy.kind(), CachePolicyKind::Hybrid);
    }

    #[test]
    fn test_tiny_lfu_policy_admit_and_stats() {
        let policy: Arc<dyn CachePolicy<String>> = build_cache_policy(&CachePolicyConfig::new(
            CachePolicyKind::TinyLfu,
            10240,
            0.2,
        ));

        // Admit a key
        let result = policy.admit(&"test_key".to_string(), 100);
        // Result depends on internal TinyLFU admission decision
        assert!(result == CacheAdmission::Accepted || result == CacheAdmission::Rejected);

        // Stats should track the operation
        let stats = policy.stats();
        assert_eq!(stats.kind, CachePolicyKind::TinyLfu);
    }

    #[test]
    fn test_tiny_lfu_policy_reset() {
        let policy: Arc<dyn CachePolicy<String>> = build_cache_policy(&CachePolicyConfig::new(
            CachePolicyKind::TinyLfu,
            10240,
            0.2,
        ));

        policy.admit(&"key1".to_string(), 100);
        policy.admit(&"key2".to_string(), 100);

        // Reset clears everything
        policy.reset();

        let stats = policy.stats();
        assert_eq!(stats.lfu_rejects, 0);
        assert_eq!(stats.hot_evictions, 0);
        assert_eq!(stats.cold_evictions, 0);
        assert_eq!(stats.protected_hits, 0);
    }

    #[test]
    fn test_tiny_lfu_policy_invalidate() {
        let policy: Arc<dyn CachePolicy<String>> = build_cache_policy(&CachePolicyConfig::new(
            CachePolicyKind::TinyLfu,
            10240,
            0.2,
        ));

        let key = "test_key".to_string();
        policy.admit(&key, 100);
        policy.invalidate(&key);
        // Should not panic and key should be removed
    }

    // build_cache_policy tests
    #[test]
    fn test_build_cache_policy_lru() {
        let config = CachePolicyConfig::new(CachePolicyKind::Lru, 1024, 0.2);
        let policy: Arc<dyn CachePolicy<String>> = build_cache_policy(&config);
        assert_eq!(policy.kind(), CachePolicyKind::Lru);
    }

    #[test]
    fn test_build_cache_policy_tiny_lfu() {
        let config = CachePolicyConfig::new(CachePolicyKind::TinyLfu, 1024, 0.2);
        let policy: Arc<dyn CachePolicy<String>> = build_cache_policy(&config);
        assert_eq!(policy.kind(), CachePolicyKind::TinyLfu);
    }

    #[test]
    fn test_build_cache_policy_hybrid() {
        let config = CachePolicyConfig::new(CachePolicyKind::Hybrid, 1024, 0.2);
        let policy: Arc<dyn CachePolicy<String>> = build_cache_policy(&config);
        assert_eq!(policy.kind(), CachePolicyKind::Hybrid);
    }

    // PolicyMetricCounters tests (via snapshot)
    #[test]
    fn test_policy_metric_counters_snapshot() {
        let counters = PolicyMetricCounters::default();
        counters.lfu_rejects.store(5, Ordering::Relaxed);
        counters.hot_evictions.store(3, Ordering::Relaxed);
        counters.cold_evictions.store(10, Ordering::Relaxed);
        counters.protected_hits.store(100, Ordering::Relaxed);

        let snapshot = counters.snapshot(CachePolicyKind::TinyLfu);
        assert_eq!(snapshot.kind, CachePolicyKind::TinyLfu);
        assert_eq!(snapshot.lfu_rejects, 5);
        assert_eq!(snapshot.hot_evictions, 3);
        assert_eq!(snapshot.cold_evictions, 10);
        assert_eq!(snapshot.protected_hits, 100);
    }

    #[test]
    fn test_policy_metric_counters_reset() {
        let counters = PolicyMetricCounters::default();
        counters.lfu_rejects.store(5, Ordering::Relaxed);
        counters.reset();
        assert_eq!(counters.lfu_rejects.load(Ordering::Relaxed), 0);
    }

    // CachePolicyEviction tests
    #[test]
    fn test_cache_policy_eviction_clone() {
        let eviction = CachePolicyEviction {
            key: "test".to_string(),
            kind: CacheEvictionKind::Hot,
        };
        let cloned = eviction.clone();
        assert_eq!(cloned.key, "test");
        assert_eq!(cloned.kind, CacheEvictionKind::Hot);
    }

    // ProtectedEntry tests
    #[test]
    fn test_protected_entry_new() {
        let entry = ProtectedEntry::new(100);
        assert_eq!(entry.weight, 100);
        assert_eq!(entry.hits.load(Ordering::Relaxed), 0);
        assert!(!entry.protected.load(Ordering::Relaxed));
    }
}