bazaar 3.5.2

//! Least-recently-used cache ordering engine.
//!
//! Mirrors the LRU bookkeeping of `bzrformats.lru_cache.LRUCache` /
//! `LRUSizeCache`: a doubly-linked list threads the entries from most- to
//! least-recently-used, and eviction walks from the LRU end. This core is
//! deliberately Python-agnostic — entries are identified by an opaque
//! [`NodeId`] and carry only an integer size, so the pyo3 wrapper can hold
//! the actual Python keys/values and compute sizes via a Python callable
//! while this module owns the ordering and eviction policy.

use std::collections::HashMap;

/// Opaque handle for a cache entry. The caller assigns ids (typically a
/// monotonically increasing counter) and maps them to its own keys/values.
pub type NodeId = u64;

struct Node {
    prev: Option<NodeId>,
    next: Option<NodeId>,
    /// Size contribution of this entry, as computed by the caller.
    size: usize,
}

/// LRU ordering engine with size-based eviction.
///
/// The `LRUCache` count-based variant in Python is the special case where
/// every entry has size 1 and `max_size`/`after_cleanup_size` are the entry
/// counts; the pyo3 layer uses this type for both.
#[derive(Default)]
pub struct LruOrder {
    nodes: HashMap<NodeId, Node>,
    /// Head of the list — the most recently used entry.
    most_recently_used: Option<NodeId>,
    /// Tail of the list — the least recently used entry.
    least_recently_used: Option<NodeId>,
    /// Sum of all entry sizes currently held.
    total_size: usize,
}

impl LruOrder {
    pub fn new() -> Self {
        Self::default()
    }

    /// Number of entries currently tracked.
    pub fn len(&self) -> usize {
        self.nodes.len()
    }

    pub fn is_empty(&self) -> bool {
        self.nodes.is_empty()
    }

    /// Total size of all entries (sum of per-entry sizes).
    pub fn total_size(&self) -> usize {
        self.total_size
    }

    pub fn contains(&self, id: NodeId) -> bool {
        self.nodes.contains_key(&id)
    }

    /// The current least-recently-used entry, if any.
    pub fn lru(&self) -> Option<NodeId> {
        self.least_recently_used
    }

    /// The current most-recently-used entry, if any.
    pub fn mru(&self) -> Option<NodeId> {
        self.most_recently_used
    }

    /// The id following `id` towards the least-recently-used end, if any.
    pub fn next(&self, id: NodeId) -> Option<NodeId> {
        self.nodes.get(&id).and_then(|n| n.next)
    }

    /// The id preceding `id` towards the most-recently-used end, if any.
    pub fn prev(&self, id: NodeId) -> Option<NodeId> {
        self.nodes.get(&id).and_then(|n| n.prev)
    }

    /// The entry ids in most-recently-used to least-recently-used order.
    pub fn order_mru_to_lru(&self) -> Vec<NodeId> {
        let mut out = Vec::with_capacity(self.nodes.len());
        let mut cur = self.most_recently_used;
        while let Some(id) = cur {
            out.push(id);
            cur = self.nodes.get(&id).and_then(|n| n.next);
        }
        out
    }

    /// Insert a brand-new entry at the most-recently-used position.
    ///
    /// The caller must ensure `id` is not already present (use
    /// [`LruOrder::touch`] / [`LruOrder::update_size`] for existing ids).
    pub fn insert(&mut self, id: NodeId, size: usize) {
        debug_assert!(!self.nodes.contains_key(&id));
        self.nodes.insert(
            id,
            Node {
                prev: None,
                next: None,
                size,
            },
        );
        self.total_size += size;
        self.move_to_front(id);
    }

    /// Update the recorded size of an existing entry, adjusting the total.
    pub fn update_size(&mut self, id: NodeId, size: usize) {
        if let Some(node) = self.nodes.get_mut(&id) {
            self.total_size -= node.size;
            node.size = size;
            self.total_size += size;
        }
    }

    /// Mark an existing entry as most-recently-used. No-op for unknown ids.
    pub fn touch(&mut self, id: NodeId) {
        if self.nodes.contains_key(&id) {
            self.move_to_front(id);
        }
    }

    /// Remove an entry, returning its recorded size. No-op (returns `None`)
    /// for unknown ids.
    pub fn remove(&mut self, id: NodeId) -> Option<usize> {
        let node = self.nodes.remove(&id)?;
        let (prev, next, size) = (node.prev, node.next, node.size);
        match prev {
            Some(p) => {
                if let Some(pn) = self.nodes.get_mut(&p) {
                    pn.next = next;
                }
            }
            None => self.most_recently_used = next,
        }
        match next {
            Some(n) => {
                if let Some(nn) = self.nodes.get_mut(&n) {
                    nn.prev = prev;
                }
            }
            None => self.least_recently_used = prev,
        }
        self.total_size -= size;
        Some(size)
    }

    /// Evict least-recently-used entries until `total_size <=
    /// after_cleanup`, returning the evicted ids in eviction (LRU-first)
    /// order. Mirrors `LRUCache.cleanup` / `LRUSizeCache.cleanup`.
    pub fn evict_until(&mut self, after_cleanup: usize) -> Vec<NodeId> {
        let mut evicted = Vec::new();
        while self.total_size > after_cleanup {
            match self.least_recently_used {
                Some(id) => {
                    self.remove(id);
                    evicted.push(id);
                }
                None => break,
            }
        }
        evicted
    }

    /// Remove every entry, returning the ids in LRU-first order (the order
    /// `LRUCache.clear` removes them in).
    pub fn drain_lru(&mut self) -> Vec<NodeId> {
        let mut out = Vec::new();
        while let Some(id) = self.least_recently_used {
            self.remove(id);
            out.push(id);
        }
        out
    }

    /// Unlink `id` from its current position and splice it in at the head.
    fn move_to_front(&mut self, id: NodeId) {
        if self.most_recently_used == Some(id) {
            return;
        }
        // Unlink from current position (if it is currently linked).
        let (prev, next) = {
            let node = &self.nodes[&id];
            (node.prev, node.next)
        };
        if let Some(p) = prev {
            if let Some(pn) = self.nodes.get_mut(&p) {
                pn.next = next;
            }
        }
        if let Some(n) = next {
            if let Some(nn) = self.nodes.get_mut(&n) {
                nn.prev = prev;
            }
        }
        if self.least_recently_used == Some(id) {
            self.least_recently_used = prev;
        }
        // Splice in at the head.
        let old_head = self.most_recently_used;
        {
            let node = self.nodes.get_mut(&id).unwrap();
            node.prev = None;
            node.next = old_head;
        }
        if let Some(h) = old_head {
            if let Some(hn) = self.nodes.get_mut(&h) {
                hn.prev = Some(id);
            }
        }
        self.most_recently_used = Some(id);
        if self.least_recently_used.is_none() {
            self.least_recently_used = Some(id);
        }
    }
}

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

    #[test]
    fn insert_and_order() {
        let mut o = LruOrder::new();
        o.insert(1, 1);
        o.insert(2, 1);
        o.insert(3, 1);
        assert_eq!(o.len(), 3);
        // LRU is the first inserted.
        assert_eq!(o.lru(), Some(1));
        // Touch 1 -> it is no longer LRU.
        o.touch(1);
        assert_eq!(o.lru(), Some(2));
    }

    #[test]
    fn evict_until_size() {
        let mut o = LruOrder::new();
        o.insert(1, 5);
        o.insert(2, 6);
        o.insert(3, 7);
        assert_eq!(o.total_size(), 18);
        o.touch(2); // make 2 newer than 1 and 3? no: order is 3(mru),2,1(lru) after touch
                    // order now: 2, 3, 1 (lru)
        let evicted = o.evict_until(10);
        // remove LRU-first until <= 10: remove 1 (size5 ->13), remove 3 (->? )
        assert!(o.total_size() <= 10);
        assert!(!evicted.is_empty());
    }

    #[test]
    fn remove_adjusts_size_and_links() {
        let mut o = LruOrder::new();
        o.insert(10, 13);
        assert_eq!(o.total_size(), 13);
        assert_eq!(o.remove(10), Some(13));
        assert_eq!(o.total_size(), 0);
        assert!(o.is_empty());
        assert_eq!(o.lru(), None);
    }

    #[test]
    fn update_size_tracks_total() {
        let mut o = LruOrder::new();
        o.insert(1, 3);
        o.update_size(1, 8);
        assert_eq!(o.total_size(), 8);
    }

    #[test]
    fn drain_lru_order() {
        let mut o = LruOrder::new();
        o.insert(1, 1);
        o.insert(2, 1);
        o.insert(3, 1);
        // LRU-first: 1, 2, 3
        assert_eq!(o.drain_lru(), vec![1, 2, 3]);
        assert!(o.is_empty());
    }

    #[test]
    fn mru_tracks_most_recent_insert() {
        let mut o = LruOrder::new();
        assert_eq!(o.mru(), None);
        o.insert(1, 1);
        o.insert(2, 1);
        assert_eq!(o.mru(), Some(2));
        o.touch(1);
        assert_eq!(o.mru(), Some(1));
    }

    #[test]
    fn order_mru_to_lru_lists_all_entries() {
        let mut o = LruOrder::new();
        o.insert(1, 1);
        o.insert(2, 1);
        o.insert(3, 1);
        // Most recently inserted first.
        assert_eq!(o.order_mru_to_lru(), vec![3, 2, 1]);
        o.touch(1);
        assert_eq!(o.order_mru_to_lru(), vec![1, 3, 2]);
    }

    #[test]
    fn next_and_prev_walk_the_chain() {
        let mut o = LruOrder::new();
        o.insert(1, 1);
        o.insert(2, 1);
        o.insert(3, 1);
        // Chain MRU->LRU is 3, 2, 1.
        assert_eq!(o.next(3), Some(2));
        assert_eq!(o.next(2), Some(1));
        assert_eq!(o.next(1), None);
        assert_eq!(o.prev(1), Some(2));
        assert_eq!(o.prev(2), Some(3));
        assert_eq!(o.prev(3), None);
        // Unknown ids have no neighbours.
        assert_eq!(o.next(99), None);
        assert_eq!(o.prev(99), None);
    }

    #[test]
    fn contains_reflects_membership() {
        let mut o = LruOrder::new();
        o.insert(7, 1);
        assert!(o.contains(7));
        assert!(!o.contains(8));
        o.remove(7);
        assert!(!o.contains(7));
    }

    #[test]
    fn update_size_unknown_id_is_noop() {
        let mut o = LruOrder::new();
        o.insert(1, 4);
        o.update_size(99, 100);
        assert_eq!(o.total_size(), 4);
    }

    #[test]
    fn touch_unknown_id_is_noop() {
        let mut o = LruOrder::new();
        o.insert(1, 1);
        o.insert(2, 1);
        o.touch(99);
        // Order unchanged: 2 is still MRU, 1 still LRU.
        assert_eq!(o.mru(), Some(2));
        assert_eq!(o.lru(), Some(1));
    }

    #[test]
    fn remove_unknown_id_returns_none() {
        let mut o = LruOrder::new();
        o.insert(1, 5);
        assert_eq!(o.remove(99), None);
        assert_eq!(o.total_size(), 5);
        assert_eq!(o.len(), 1);
    }

    #[test]
    fn evict_until_removes_exact_lru_entries() {
        let mut o = LruOrder::new();
        o.insert(1, 5);
        o.insert(2, 6);
        o.insert(3, 7);
        // Order MRU->LRU is 3, 2, 1. Evict until total_size <= 10:
        // remove 1 (->13), remove 2 (->7). 3 stays.
        let evicted = o.evict_until(10);
        assert_eq!(evicted, vec![1, 2]);
        assert_eq!(o.total_size(), 7);
        assert_eq!(o.order_mru_to_lru(), vec![3]);
    }

    #[test]
    fn evict_until_already_under_target_removes_nothing() {
        let mut o = LruOrder::new();
        o.insert(1, 3);
        let evicted = o.evict_until(10);
        assert!(evicted.is_empty());
        assert_eq!(o.total_size(), 3);
    }

    #[test]
    fn update_size_then_evict_uses_new_size() {
        let mut o = LruOrder::new();
        o.insert(1, 1);
        o.update_size(1, 9);
        assert_eq!(o.total_size(), 9);
        let evicted = o.evict_until(5);
        assert_eq!(evicted, vec![1]);
        assert!(o.is_empty());
    }
}