timefs 0.1.0

//! Bounded in-memory caches used by the Git backend.

use lru::LruCache;
use std::borrow::Borrow;
use std::hash::Hash;
use std::time::{Duration, Instant};

/// Values that can report their approximate in-memory weight.
pub(crate) trait CacheWeight {
    /// Return the approximate in-memory weight of this value in bytes.
    fn cache_weight(&self) -> usize;
}

#[derive(Debug)]
struct WeightedValue<V> {
    value: V,
    weight: usize,
}

/// An LRU cache bounded by total approximate byte weight instead of entry count.
#[derive(Debug)]
pub(crate) struct ByteLruCache<K, V>
where
    K: Hash + Eq,
{
    entries: LruCache<K, WeightedValue<V>>,
    max_weight: usize,
    current_weight: usize,
}

impl<K, V> ByteLruCache<K, V>
where
    K: Hash + Eq,
    V: CacheWeight,
{
    /// Create a cache capped to `max_weight` bytes.
    pub(crate) fn new(max_weight: usize) -> Self {
        Self {
            entries: LruCache::unbounded(),
            max_weight,
            current_weight: 0,
        }
    }

    /// Return the cached value for `key`, updating its LRU position.
    pub(crate) fn get_cloned<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
        V: Clone,
    {
        self.entries.get(key).map(|entry| entry.value.clone())
    }

    /// Insert `value` for `key`, evicting least-recently-used entries as needed.
    pub(crate) fn insert(&mut self, key: K, value: V) -> bool {
        let weight = value.cache_weight();
        if self.max_weight == 0 || weight > self.max_weight {
            return false;
        }

        if let Some((_old_key, old_value)) = self.entries.pop_entry(&key) {
            self.current_weight = self.current_weight.saturating_sub(old_value.weight);
        }

        self.entries.push(key, WeightedValue { value, weight });
        self.current_weight = self.current_weight.saturating_add(weight);
        self.evict_to_budget();
        true
    }

    /// Return the current approximate weight in bytes.
    #[cfg(test)]
    pub(crate) fn current_weight(&self) -> usize {
        self.current_weight
    }

    fn evict_to_budget(&mut self) {
        while self.current_weight > self.max_weight {
            let Some((_key, value)) = self.entries.pop_lru() else {
                break;
            };
            self.current_weight = self.current_weight.saturating_sub(value.weight);
        }
    }
}

#[derive(Debug)]
struct TimedValue<V> {
    value: V,
    expires_at: Instant,
}

/// A small LRU cache whose entries expire after a fixed TTL.
#[derive(Debug)]
pub(crate) struct TtlLruCache<K, V>
where
    K: Hash + Eq,
{
    entries: LruCache<K, TimedValue<V>>,
    ttl: Duration,
    max_entries: usize,
}

impl<K, V> TtlLruCache<K, V>
where
    K: Hash + Eq,
{
    /// Create a cache holding at most `max_entries` live entries with the given TTL.
    pub(crate) fn new(max_entries: usize, ttl: Duration) -> Self {
        Self {
            entries: LruCache::unbounded(),
            ttl,
            max_entries,
        }
    }

    /// Return the cached value for `key` when it is still fresh.
    pub(crate) fn get_cloned<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
        V: Clone,
    {
        if self
            .entries
            .peek(key)
            .is_some_and(|entry| entry.expires_at <= Instant::now())
        {
            let _ = self.entries.pop(key);
            return None;
        }

        self.entries.get(key).map(|entry| entry.value.clone())
    }

    /// Insert or refresh an entry.
    pub(crate) fn insert(&mut self, key: K, value: V) {
        if self.max_entries == 0 {
            return;
        }

        self.entries.push(
            key,
            TimedValue {
                value,
                expires_at: Instant::now() + self.ttl,
            },
        );
        self.prune_expired_lru_tail();
        while self.entries.len() > self.max_entries {
            let _ = self.entries.pop_lru();
        }
    }

    fn prune_expired_lru_tail(&mut self) {
        while self
            .entries
            .peek_lru()
            .is_some_and(|(_key, value)| value.expires_at <= Instant::now())
        {
            let _ = self.entries.pop_lru();
        }
    }
}

#[cfg(test)]
mod tests {
    use super::{ByteLruCache, CacheWeight, TtlLruCache};
    use std::thread;
    use std::time::Duration;

    #[derive(Clone, Debug, Eq, PartialEq)]
    struct Bytes(Vec<u8>);

    impl CacheWeight for Bytes {
        fn cache_weight(&self) -> usize {
            self.0.len()
        }
    }

    #[test]
    fn byte_lru_cache_evicts_to_weight_budget() {
        let mut cache = ByteLruCache::new(8);

        assert!(cache.insert(1_u8, Bytes(vec![1, 2, 3, 4])));
        assert!(cache.insert(2_u8, Bytes(vec![5, 6, 7, 8])));
        assert_eq!(cache.get_cloned(&1_u8), Some(Bytes(vec![1, 2, 3, 4])));
        assert!(cache.insert(3_u8, Bytes(vec![9, 10, 11, 12])));

        assert_eq!(cache.current_weight(), 8);
        assert_eq!(cache.get_cloned(&1_u8), Some(Bytes(vec![1, 2, 3, 4])));
        assert_eq!(cache.get_cloned(&2_u8), None);
        assert_eq!(cache.get_cloned(&3_u8), Some(Bytes(vec![9, 10, 11, 12])));
    }

    #[test]
    fn ttl_lru_cache_expires_entries() {
        let mut cache = TtlLruCache::new(8, Duration::from_millis(25));
        cache.insert(String::from("HEAD"), 42_u8);

        assert_eq!(cache.get_cloned("HEAD"), Some(42));
        thread::sleep(Duration::from_millis(35));
        assert_eq!(cache.get_cloned("HEAD"), None);
    }
}