codenexus 0.4.0-rc.2

// Copyright (c) 2026 Kirky.X🌠
// SPDX-License-Identifier: MIT

//! LSP `textDocument/references` result cache.
//!
//! Caches `Vec<lsp_types::Location>` results keyed by `(uri, line, column)`
//! for up to `TTL` (default 5 minutes). Bounds memory with an LRU policy
//! (default 1000 entries). Time is injectable via the [`Clock`] trait so
//! tests can fast-forward without `thread::sleep`.
//!
//! # Design
//!
//! - **Lazy TTL expiration**: expired entries are evicted on read rather
//!   than via a background sweeper — keeps the cache lock-free of timers
//!   and avoids a dedicated reaper thread.
//! - **LRU via `VecDeque`**: O(n) `retain` on eviction is acceptable
//!   because `n ≤ capacity` (default 1000) and evictions are infrequent
//!   relative to `get`/`insert` on hot keys.
//! - **Mock clock injection**: [`ReferencesCache::with_clock`] accepts any
//!   `Arc<dyn Clock>`, enabling deterministic TTL tests in milliseconds.
//!
//! # Feature gating
//!
//! Compiles only under the `lsp` cargo feature (same as the rest of
//! `crate::lsp`).

use std::collections::{HashMap, HashSet, VecDeque};
use std::sync::{Arc, Mutex};
use std::time::{Duration, Instant};

use lsp_types::Location;

/// Default cache TTL: 5 minutes.
pub const DEFAULT_TTL: Duration = Duration::from_secs(300);

/// Default LRU capacity.
pub const DEFAULT_CAPACITY: usize = 1_000;

/// Abstract time source so tests can fast-forward without sleeping.
///
/// Production code uses [`SystemClock`].
///
/// # Implementor safety contract
///
/// `now()` is invoked while [`ReferencesCache`] holds its internal `Mutex`
/// guard. Implementations **must not** acquire any lock that could be held
/// by code path that itself waits on the cache mutex — doing so would
/// deadlock. The shipped [`SystemClock`] (calls `Instant::now`, lock-free)
/// satisfies this contract. Custom `Clock` implementations must
/// document their locking behavior.
pub trait Clock: Send + Sync {
    /// Returns the current instant.
    fn now(&self) -> Instant;
}

/// Real-time clock backed by [`Instant::now`].
#[derive(Debug, Default, Clone, Copy)]
pub struct SystemClock;

impl Clock for SystemClock {
    fn now(&self) -> Instant {
        Instant::now()
    }
}

/// Cache key: `(uri, line, column)` — the mandated triple.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct CacheKey {
    /// File URI (`file://...`) exactly as the LSP server sees it.
    pub uri: String,
    /// 0-based line number (LSP `Position.line` convention).
    pub line: u32,
    /// 0-based column / character offset (LSP `Position.character`).
    pub column: u32,
}

impl CacheKey {
    /// Creates a new cache key from the raw `(uri, line, column)` triple.
    #[must_use]
    pub fn new(uri: String, line: u32, column: u32) -> Self {
        Self { uri, line, column }
    }
}

/// LRU + TTL cache for `textDocument/references` results.
///
/// Thread-safe via internal `Mutex`. Capacity-bounded by LRU eviction
/// (oldest-accessed entry removed when capacity exceeded). TTL is checked
/// lazily on read — expired entries are removed and treated as misses.
///
/// # Examples
///
/// ```
/// use codenexus::lsp::{CacheKey, ReferencesCache};
/// use lsp_types::{Location, Position, Range, Uri};
/// use std::str::FromStr;
///
/// let cache = ReferencesCache::new();
/// let key = CacheKey::new("file:///tmp/x.rs".to_string(), 5, 10);
/// let loc = Location {
///     uri: Uri::from_str("file:///tmp/x.rs").unwrap(),
///     range: Range {
///         start: Position { line: 5, character: 0 },
///         end: Position { line: 5, character: 10 },
///     },
/// };
/// cache.insert(key.clone(), vec![loc.clone()]);
/// let got = cache.get(&key).expect("entry present");
/// assert_eq!(got.len(), 1);
/// ```
pub struct ReferencesCache {
    inner: Mutex<CacheInner>,
    clock: Arc<dyn Clock>,
    ttl: Duration,
    capacity: usize,
}

struct CacheInner {
    entries: HashMap<CacheKey, (Instant, Vec<Location>)>,
    /// LRU ordering: front = most recently used, back = least recently used.
    lru: VecDeque<CacheKey>,
    /// Reverse index: `uri → set of keys with that uri`.
    ///
    /// `invalidate_uri` was previously O(N) over all
    /// entries (filter + clone each matching key). With this reverse index
    /// it is O(K) where K is the number of entries for that uri (typically
    /// 1-10 for a single file). Maintained in lock-step with `entries` and
    /// `lru` on every insert / evict / lazy-expire.
    by_uri: HashMap<String, HashSet<CacheKey>>,
}

impl ReferencesCache {
    /// Default LRU capacity (1000 entries).
    pub const DEFAULT_CAPACITY: usize = DEFAULT_CAPACITY;

    /// Default TTL (5 minutes).
    pub const DEFAULT_TTL: Duration = DEFAULT_TTL;

    /// Creates a cache with system clock, default TTL (5 min) and default
    /// capacity (1000).
    #[must_use]
    pub fn new() -> Self {
        Self::with_clock(
            Arc::new(SystemClock),
            Self::DEFAULT_TTL,
            Self::DEFAULT_CAPACITY,
        )
    }

    /// Creates a cache with a custom clock (for tests), TTL, and capacity.
    ///
    /// # Panics
    ///
    /// Panics if `capacity == 0` (a zero-capacity cache can never hold
    /// anything and is almost certainly a caller bug).
    #[must_use]
    pub fn with_clock(clock: Arc<dyn Clock>, ttl: Duration, capacity: usize) -> Self {
        assert!(capacity > 0, "ReferencesCache capacity must be > 0");
        let cap_hint = capacity.min(1024);
        Self {
            inner: Mutex::new(CacheInner {
                entries: HashMap::with_capacity(cap_hint),
                lru: VecDeque::with_capacity(cap_hint),
                by_uri: HashMap::with_capacity(cap_hint),
            }),
            clock,
            ttl,
            capacity,
        }
    }

    /// Creates a cache with the real system clock, given TTL and capacity.
    ///
    /// Convenience for callers that want a plain bounded TTL cache without
    /// clock injection; tests use short TTLs with the real clock where
    /// `thread::sleep` overshoot makes expiry deterministic.
    #[must_use]
    pub fn with_ttl_capacity(ttl: Duration, capacity: usize) -> Self {
        Self::with_clock(Arc::new(SystemClock), ttl, capacity)
    }

    /// Looks up `key` in the cache. Returns `Some` only if the entry exists
    /// AND has not expired (age <= TTL). Expired entries are evicted on read
    /// (lazy expiration).
    pub fn get(&self, key: &CacheKey) -> Option<Vec<Location>> {
        let mut guard = self.inner.lock().expect("cache mutex poisoned");
        let now = self.clock.now();
        let ttl = self.ttl;

        let stored_at = match guard.entries.get(key) {
            Some((stored_at, _)) => *stored_at,
            None => return None,
        };

        if now.duration_since(stored_at) > ttl {
            // Lazy expiration: evict on read. Keep `by_uri` in sync.
            guard.entries.remove(key);
            guard.lru.retain(|k| k != key);
            remove_from_by_uri(&mut guard.by_uri, key);
            return None;
        }

        // Move to front (most recently used).
        guard.lru.retain(|k| k != key);
        guard.lru.push_front(key.clone());

        guard.entries.get(key).map(|(_, locs)| locs.clone())
    }

    /// Inserts `key -> locations` with the current timestamp. Evicts the
    /// least-recently-used entry if at capacity. Overwrites existing value
    /// (and refreshes timestamp + LRU position) if `key` already present.
    pub fn insert(&self, key: CacheKey, locations: Vec<Location>) {
        let mut guard = self.inner.lock().expect("cache mutex poisoned");
        let now = self.clock.now();

        if guard.entries.contains_key(&key) {
            // Refresh: remove from LRU, will re-push front below.
            // `by_uri` already contains this key (inserted on first insert),
            // so no reverse-index update needed here.
            guard.lru.retain(|k| k != &key);
        } else if guard.entries.len() >= self.capacity {
            // Evict LRU (back of deque). Keep `by_uri` in sync.
            if let Some(evicted) = guard.lru.pop_back() {
                remove_from_by_uri(&mut guard.by_uri, &evicted);
                guard.entries.remove(&evicted);
            }
        }

        // Update reverse index: uri → set of keys.
        guard
            .by_uri
            .entry(key.uri.clone())
            .or_default()
            .insert(key.clone());
        guard.entries.insert(key.clone(), (now, locations));
        guard.lru.push_front(key);
    }

    /// Invalidates all entries for `uri` (called when `textDocument/didChange`
    /// fires for that file). Returns the number of entries evicted.
    ///
    /// O(K) where K is the number of entries for
    /// `uri` (typically 1-10 for a single file), instead of O(N) over the
    /// entire cache. Backed by the `by_uri` reverse index.
    pub fn invalidate_uri(&self, uri: &str) -> usize {
        let mut guard = self.inner.lock().expect("cache mutex poisoned");
        let keys = match guard.by_uri.remove(uri) {
            Some(set) => set,
            None => return 0,
        };
        let count = keys.len();
        for key in keys {
            guard.entries.remove(&key);
            guard.lru.retain(|k| k != &key);
        }
        count
    }

    /// Returns the current number of entries (including any expired ones
    /// not yet lazily evicted).
    pub fn len(&self) -> usize {
        self.inner
            .lock()
            .expect("cache mutex poisoned")
            .entries
            .len()
    }

    /// Returns `true` if the cache currently holds zero entries.
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Returns the configured TTL.
    pub const fn ttl(&self) -> Duration {
        self.ttl
    }

    /// Returns the configured capacity.
    pub const fn capacity(&self) -> usize {
        self.capacity
    }
}

impl Default for ReferencesCache {
    fn default() -> Self {
        Self::new()
    }
}

/// Removes `key` from the `by_uri` reverse index. If the uri's key-set
/// becomes empty, the uri entry itself is removed to keep `by_uri` compact.
///
/// This is a free function (not a method on `ReferencesCache`) because it
/// operates on the `CacheInner`'s `by_uri` field directly, which is only
/// accessible while holding the inner `Mutex` guard. Keeping it out of the
/// `impl` block makes it clear that no locking is performed here — the
/// caller must already hold the guard.
fn remove_from_by_uri(by_uri: &mut HashMap<String, HashSet<CacheKey>>, key: &CacheKey) {
    let mut empty = false;
    if let Some(set) = by_uri.get_mut(&key.uri) {
        set.remove(key);
        empty = set.is_empty();
    }
    if empty {
        by_uri.remove(&key.uri);
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use lsp_types::{Position, Range, Uri};
    use std::str::FromStr;

    fn loc(line: u32) -> Location {
        Location {
            uri: Uri::from_str("file:///tmp/x.rs").unwrap(),
            range: Range {
                start: Position { line, character: 0 },
                end: Position { line, character: 5 },
            },
        }
    }

    #[test]
    fn new_uses_defaults() {
        let c = ReferencesCache::new();
        assert_eq!(c.ttl(), Duration::from_secs(300));
        assert_eq!(c.capacity(), 1_000);
        assert!(c.is_empty());
    }

    #[test]
    fn insert_then_get_returns_value() {
        let c = ReferencesCache::new();
        let key = CacheKey::new("file:///tmp/x.rs".into(), 5, 10);
        c.insert(key.clone(), vec![loc(5)]);
        assert_eq!(c.len(), 1);
        let got = c.get(&key).expect("entry present");
        assert_eq!(got.len(), 1);
        assert_eq!(got[0].range.start.line, 5);
    }

    #[test]
    fn get_missing_returns_none() {
        let c = ReferencesCache::new();
        let key = CacheKey::new("file:///tmp/x.rs".into(), 5, 10);
        assert!(c.get(&key).is_none());
    }

    #[test]
    fn entry_hits_within_ttl_and_expires_after_ttl() {
        // Short TTL + real clock (replaces the old MockClock::advance):
        // thread::sleep only ever overshoots, so the post-sleep age strictly
        // exceeds the TTL — deterministic expiry without a mock clock. The
        // within-TTL hit half covers the old `age == ttl is fresh` boundary
        // from the fresh side.
        let c = ReferencesCache::with_ttl_capacity(Duration::from_millis(50), 100);
        let key = CacheKey::new("file:///tmp/x.rs".into(), 5, 10);
        c.insert(key.clone(), vec![loc(5)]);
        assert!(c.get(&key).is_some(), "fresh entry must hit within TTL");

        std::thread::sleep(Duration::from_millis(80));
        assert!(c.get(&key).is_none(), "entry must miss once past the TTL");
    }

    #[test]
    fn lru_eviction_when_capacity_exceeded() {
        let c = ReferencesCache::with_ttl_capacity(Duration::from_secs(600), 2);
        let k1 = CacheKey::new("file:///tmp/a.rs".into(), 1, 1);
        let k2 = CacheKey::new("file:///tmp/b.rs".into(), 2, 2);
        let k3 = CacheKey::new("file:///tmp/c.rs".into(), 3, 3);

        c.insert(k1.clone(), vec![loc(1)]);
        c.insert(k2.clone(), vec![loc(2)]);
        // k1 and k2 present; capacity=2. Insert k3 → evict LRU (k1, since k2
        // was just inserted after k1).
        c.insert(k3.clone(), vec![loc(3)]);

        assert!(c.get(&k1).is_none(), "k1 should have been LRU-evicted");
        assert!(c.get(&k2).is_some());
        assert!(c.get(&k3).is_some());
        assert_eq!(c.len(), 2);
    }

    #[test]
    fn lru_refresh_on_get_prevents_eviction() {
        let c = ReferencesCache::with_ttl_capacity(Duration::from_secs(600), 2);
        let k1 = CacheKey::new("file:///tmp/a.rs".into(), 1, 1);
        let k2 = CacheKey::new("file:///tmp/b.rs".into(), 2, 2);
        let k3 = CacheKey::new("file:///tmp/c.rs".into(), 3, 3);

        c.insert(k1.clone(), vec![loc(1)]);
        c.insert(k2.clone(), vec![loc(2)]);
        // Access k1 to make it MRU; k2 becomes LRU.
        let _ = c.get(&k1);
        c.insert(k3.clone(), vec![loc(3)]);

        assert!(c.get(&k1).is_some(), "k1 was refreshed, should survive");
        assert!(c.get(&k2).is_none(), "k2 was LRU, should be evicted");
        assert!(c.get(&k3).is_some());
    }

    #[test]
    fn invalidate_uri_removes_all_entries_for_file() {
        let c = ReferencesCache::new();
        c.insert(CacheKey::new("file:///tmp/x.rs".into(), 1, 1), vec![loc(1)]);
        c.insert(
            CacheKey::new("file:///tmp/x.rs".into(), 5, 10),
            vec![loc(5)],
        );
        c.insert(CacheKey::new("file:///tmp/y.rs".into(), 1, 1), vec![loc(1)]);

        let evicted = c.invalidate_uri("file:///tmp/x.rs");
        assert_eq!(evicted, 2);
        assert_eq!(c.len(), 1, "y.rs entry must survive");
    }

    #[test]
    fn invalidate_uri_no_match_returns_zero() {
        let c = ReferencesCache::new();
        c.insert(CacheKey::new("file:///tmp/x.rs".into(), 1, 1), vec![loc(1)]);
        assert_eq!(c.invalidate_uri("file:///tmp/other.rs"), 0);
        assert_eq!(c.len(), 1);
    }

    #[test]
    fn invalidate_uri_after_eviction_keeps_other_uris() {
        // 手写实现（保留版）的索引与存活条目一致：LRU 逐出 k1 时其索引
        // 条目一并移除（oxcache 路径的「索引宽口径」随该路径回退作废，
        // 收敛记录见 specmark changes/selfdev-lib-adoption-r1 design.md
        // D3 补充-最终裁定）。invalidate_uri 的计数口径=该 uri 的存活键。
        let c = ReferencesCache::with_ttl_capacity(Duration::from_secs(600), 2);
        let k1 = CacheKey::new("file:///tmp/x.rs".into(), 1, 1);
        let k2 = CacheKey::new("file:///tmp/x.rs".into(), 2, 2);
        c.insert(k1.clone(), vec![loc(1)]);
        c.insert(k2.clone(), vec![loc(2)]);
        // Insert a third key for a different uri → evicts k1 (LRU), and its
        // index entry is reclaimed with it.
        let k3 = CacheKey::new("file:///tmp/y.rs".into(), 3, 3);
        c.insert(k3.clone(), vec![loc(3)]);
        assert!(c.get(&k1).is_none(), "k1 should have been LRU-evicted");

        let evicted = c.invalidate_uri("file:///tmp/x.rs");
        assert_eq!(evicted, 1, "only live key k2 remains in the x.rs index");
        assert!(c.get(&k2).is_none(), "k2 cleared by invalidate_uri");
        assert!(c.get(&k3).is_some(), "y.rs entry must survive");
        assert_eq!(
            c.invalidate_uri("file:///tmp/x.rs"),
            0,
            "reverse index must be cleared after invalidation"
        );
    }

    #[test]
    fn invalidate_uri_after_expiry_clears_index() {
        // Expiry is lazy (on read) in the retained implementation: the get
        // below reclaims k1 from entries AND index; k2's index entry is
        // removed by invalidate_uri itself. The index never outlives the
        // live entries it describes.
        let c = ReferencesCache::with_ttl_capacity(Duration::from_millis(50), 100);
        let k1 = CacheKey::new("file:///tmp/x.rs".into(), 1, 1);
        let k2 = CacheKey::new("file:///tmp/x.rs".into(), 2, 2);
        c.insert(k1.clone(), vec![loc(1)]);
        c.insert(k2.clone(), vec![loc(2)]);
        std::thread::sleep(Duration::from_millis(80));
        assert!(c.get(&k1).is_none(), "k1 should be expired");

        let evicted = c.invalidate_uri("file:///tmp/x.rs");
        assert_eq!(
            evicted, 1,
            "k1 already reclaimed by the lazy-expiring get; k2 removed here"
        );
        assert_eq!(c.len(), 0);
    }

    #[test]
    fn insert_overwrites_existing_key() {
        let c = ReferencesCache::new();
        let key = CacheKey::new("file:///tmp/x.rs".into(), 5, 10);
        c.insert(key.clone(), vec![loc(5)]);
        c.insert(key.clone(), vec![loc(5), loc(6)]);
        assert_eq!(c.len(), 1, "overwrite must not grow cache");
        let got = c.get(&key).expect("entry present");
        assert_eq!(got.len(), 2);
    }

    #[test]
    #[should_panic(expected = "capacity must be > 0")]
    fn zero_capacity_panics() {
        let _ = ReferencesCache::with_ttl_capacity(Duration::from_secs(60), 0);
    }
}