vyre-driver 0.4.1

//! N5 substrate: spec-cache eviction policy with frequency × recency
//! heat decay.
//!
//! F1/F3 cache compiled pipelines by `SpecCacheKey` but never evict.
//! Long-running daemons (surgec scanning hundreds of repos in
//! sequence) accumulate dead entries that pin VRAM-resident
//! pipelines. This module owns the *decision*: given a list of
//! cache entry stats and a capacity, return which entries to drop.
//!
//! The score is `hit_count / (1 + age_seconds / DECAY_HALF_LIFE_S)` —
//! a hot, recent entry stays; a cold, old entry leaves. Pure
//! arithmetic; the actual cache surgery lives in the F1/F3 cache
//! modules and is the consumer's responsibility.

/// Half-life (seconds) for the heat decay term. Entries older than
/// this lose half their hit-count weight; doubled, lose three
/// quarters; etc. Tuned for surgec scan workloads where a "warm"
/// entry is one used in the last few minutes of a long sweep.
pub const DECAY_HALF_LIFE_S: f64 = 300.0;

/// Per-entry stats the eviction policy needs. Caller (the F1/F3
/// cache layer) keeps these alongside each entry and passes a
/// snapshot when capacity pressure triggers.
#[derive(Debug, Clone, Copy)]
pub struct CacheEntryStats {
    /// Stable identifier for the entry (cache slot index, hash,
    /// SpecCacheKey index, etc). Pure pass-through — the policy
    /// only uses it to name which entries to evict.
    pub id: u64,
    /// Total hits since the entry was inserted.
    pub hit_count: u32,
    /// Wall-clock time (seconds since epoch or any monotonic clock)
    /// the entry was last hit. Same clock reference as
    /// `current_time_s`.
    pub last_hit_time_s: f64,
}

impl CacheEntryStats {
    /// Heat score: high = keep, low = evict. Combines frequency
    /// (hit_count) with recency via exponential half-life decay.
    #[must_use]
    pub fn heat(&self, current_time_s: f64) -> f64 {
        let age = (current_time_s - self.last_hit_time_s).max(0.0);
        let decay_factor = 0.5_f64.powf(age / DECAY_HALF_LIFE_S);
        f64::from(self.hit_count) * decay_factor
    }
}

/// Decide which entry IDs to evict given a fixed capacity. Returns
/// the IDs in eviction order (lowest heat first); caller drops
/// until under capacity.
///
/// Entries with identical heat (e.g. two cold entries with the same
/// `hit_count` and `last_hit_time_s`) are evicted in input order
/// for determinism — bench reproducibility matters here.
#[must_use]
pub fn entries_to_evict(
    entries: &[CacheEntryStats],
    capacity: usize,
    current_time_s: f64,
) -> Vec<u64> {
    if entries.len() <= capacity {
        return Vec::new();
    }
    let mut ranked: Vec<(usize, &CacheEntryStats, f64)> = entries
        .iter()
        .enumerate()
        .map(|(idx, e)| (idx, e, e.heat(current_time_s)))
        .collect();
    let compare = |a: &(usize, &CacheEntryStats, f64), b: &(usize, &CacheEntryStats, f64)| {
        a.2.partial_cmp(&b.2)
            .unwrap_or(std::cmp::Ordering::Equal)
            .then_with(|| a.0.cmp(&b.0))
    };
    let evict_count = entries.len() - capacity;
    if evict_count < ranked.len() {
        ranked.select_nth_unstable_by(evict_count, compare);
    }
    ranked[..evict_count].sort_by(compare);
    ranked
        .into_iter()
        .take(evict_count)
        .map(|(_, e, _)| e.id)
        .collect()
}

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

    fn entry(id: u64, hits: u32, last_hit: f64) -> CacheEntryStats {
        CacheEntryStats {
            id,
            hit_count: hits,
            last_hit_time_s: last_hit,
        }
    }

    #[test]
    fn under_capacity_evicts_nothing() {
        let entries = vec![entry(1, 10, 100.0), entry(2, 5, 200.0)];
        assert!(entries_to_evict(&entries, 10, 300.0).is_empty());
    }

    #[test]
    fn cold_entry_evicted_before_hot_one() {
        let entries = vec![
            entry(1, 100, 290.0), // very recent, very hot
            entry(2, 1, 0.0),     // ancient, cold
        ];
        let evict = entries_to_evict(&entries, 1, 300.0);
        assert_eq!(evict, vec![2], "ancient cold entry evicted first");
    }

    #[test]
    fn equal_heat_evicts_in_input_order() {
        let entries = vec![
            entry(1, 10, 100.0),
            entry(2, 10, 100.0),
            entry(3, 10, 100.0),
        ];
        let evict = entries_to_evict(&entries, 1, 200.0);
        assert_eq!(evict, vec![1, 2], "tied heat → first two by input order");
    }

    #[test]
    fn frequency_dominates_recency_at_equal_age() {
        let entries = vec![
            entry(1, 1000, 100.0), // ancient but very hit
            entry(2, 1, 100.0),    // ancient and rarely hit
        ];
        let evict = entries_to_evict(&entries, 1, 1000.0);
        assert_eq!(evict, vec![2]);
    }

    #[test]
    fn recency_dominates_frequency_at_equal_hits() {
        // Both have 10 hits; one was 5 minutes ago, one was 1 hour ago.
        let entries = vec![
            entry(1, 10, 0.0),    // 1 hour ago
            entry(2, 10, 3300.0), // 5 minutes ago
        ];
        let evict = entries_to_evict(&entries, 1, 3600.0);
        assert_eq!(evict, vec![1], "older entry of same hit-count evicts first");
    }

    #[test]
    fn heat_decays_with_age() {
        let e = entry(0, 100, 0.0);
        let fresh = e.heat(0.0);
        let half_life = e.heat(DECAY_HALF_LIFE_S);
        let two_half_lives = e.heat(2.0 * DECAY_HALF_LIFE_S);
        assert!((fresh - 100.0).abs() < 1e-9);
        assert!((half_life - 50.0).abs() < 1e-9);
        assert!((two_half_lives - 25.0).abs() < 1e-9);
    }
}