//! Caches of rendered output keyed by what the output depends on (hub spec
//! §16.3): the BLAKE3 of the content and of anything else that changes the
//! result, such as a Markdown file's link bases or a file's name, which
//! picks its syntax. Bounded by the bytes they hold; the least recently
//! used entries go first.

use std::collections::HashMap;
use std::sync::{Arc, Mutex};

pub struct Lru<V> {
    inner: Mutex<Inner<V>>,
}

struct Inner<V> {
    budget: usize,
    used: usize,
    tick: u64,
    hits: u64,
    misses: u64,
    map: HashMap<[u8; 32], (u64, Arc<V>, usize)>,
}

/// Something whose size counts against a cache's budget.
pub trait Weigh {
    fn weight(&self) -> usize;
}

impl Weigh for String {
    fn weight(&self) -> usize {
        self.len() + 32
    }
}

impl Weigh for Vec<String> {
    fn weight(&self) -> usize {
        self.iter().map(|s| s.len() + 24).sum::<usize>() + 32
    }
}

/// The key for a set of parts: BLAKE3 of each part's length and bytes.
pub fn key(parts: &[&[u8]]) -> [u8; 32] {
    let mut h = blake3::Hasher::new();
    for p in parts {
        h.update(&(p.len() as u64).to_le_bytes());
        h.update(p);
    }
    *h.finalize().as_bytes()
}

impl<V: Weigh> Lru<V> {
    pub fn new(budget: usize) -> Lru<V> {
        Lru { inner: Mutex::new(Inner { budget, used: 0, tick: 0, hits: 0, misses: 0, map: HashMap::new() }) }
    }

    /// The cached value for `key`, or `make()` stored and returned. `make`
    /// runs without the lock held, so a slow render blocks nobody.
    pub fn get_or(&self, key: [u8; 32], make: impl FnOnce() -> V) -> Arc<V> {
        {
            let mut g = self.inner.lock().unwrap_or_else(|p| p.into_inner());
            g.tick += 1;
            let tick = g.tick;
            if let Some(entry) = g.map.get_mut(&key) {
                entry.0 = tick;
                let v = entry.1.clone();
                g.hits += 1;
                return v;
            }
            g.misses += 1;
        }
        let value = Arc::new(make());
        let weight = value.weight();
        let mut g = self.inner.lock().unwrap_or_else(|p| p.into_inner());
        if weight > g.budget / 4 {
            return value; // too big to be worth keeping
        }
        g.tick += 1;
        let tick = g.tick;
        if let Some(old) = g.map.insert(key, (tick, value.clone(), weight)) {
            g.used -= old.2;
        }
        g.used += weight;
        while g.used > g.budget {
            let Some((&oldest, _)) = g.map.iter().min_by_key(|(_, e)| e.0) else { break };
            if let Some(e) = g.map.remove(&oldest) {
                g.used -= e.2;
            }
        }
        value
    }

    /// (hits, misses, bytes held).
    pub fn stats(&self) -> (u64, u64, usize) {
        let g = self.inner.lock().unwrap_or_else(|p| p.into_inner());
        (g.hits, g.misses, g.used)
    }
}

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

    #[test]
    fn hits_misses_and_eviction() {
        let c: Lru<String> = Lru::new(400);
        let mut runs = 0;
        for _ in 0..3 {
            c.get_or(key(&[b"a"]), || {
                runs += 1;
                "x".repeat(50)
            });
        }
        assert_eq!(runs, 1, "rendered once");
        assert_eq!(c.stats().0, 2);
        // Filling past the budget drops the least recently used.
        c.get_or(key(&[b"b"]), || "y".repeat(90));
        c.get_or(key(&[b"a"]), || unreachable!());
        c.get_or(key(&[b"c"]), || "z".repeat(90));
        c.get_or(key(&[b"d"]), || "w".repeat(90));
        assert!(c.stats().2 <= 400);
        let mut again = false;
        c.get_or(key(&[b"b"]), || {
            again = true;
            String::new()
        });
        assert!(again, "b was the least recently used and went first");
        // Something larger than a quarter of the budget is not kept.
        c.get_or(key(&[b"huge"]), || "h".repeat(200));
        let mut rerun = false;
        c.get_or(key(&[b"huge"]), || {
            rerun = true;
            String::new()
        });
        assert!(rerun);
        // Parts are length-framed: ("ab","c") and ("a","bc") differ.
        assert_ne!(key(&[b"ab", b"c"]), key(&[b"a", b"bc"]));
    }
}