rustial_engine/

tile_cache.rs

//! # LRU tile cache
//!
//! A fixed-capacity, least-recently-used (LRU) in-memory cache for map
//! tiles.  This is the primary tile storage consumed by
//! [`TileManager`](crate::tile_manager::TileManager) during the per-frame
//! update loop.
//!
//! ## Lifecycle of a cached tile
//!
//! ```text
//!  insert_pending(id)       promote(id, data)        evict (LRU)
//!        |                        |                        |
//!        v                        v                        v
//!    +----------+            +----------+            +---------+
//!    | Pending  | ---------> | Loaded   | ---------> | removed |
//!    +----------+            +----------+            +---------+
//!        |
//!        | mark_failed(id, err)
//!        v
//!    +----------+
//!    | Failed   | ---------> | removed |
//!    +----------+            +---------+
//! ```
//!
//! 1. **Pending** -- a fetch has been issued by the tile source but the
//!    response has not arrived yet.
//! 2. **Loaded** -- the tile data (raster image) is available for
//!    rendering.
//! 3. **Failed** -- the fetch failed (network error, 404, decode error).
//!    Failed entries remain in the cache so the manager does not
//!    immediately re-request them; they will be evicted naturally by
//!    the LRU policy.
//!
//! ## Eviction policy
//!
//! When the cache is full and a new entry needs to be inserted, the
//! **least-recently-used** entry is removed -- regardless of its state
//! (Pending, Loaded, or Failed).  This means an in-flight fetch may be
//! evicted if the cache is small relative to the visible tile count;
//! the tile source will simply re-request it on the next frame.
//!
//! "Recently used" is updated by:
//! - [`insert_pending`](TileCache::insert_pending) -- appends to the
//!   back of the LRU queue.
//! - [`promote`](TileCache::promote) -- moves the entry to the back
//!   (most-recently-used position).
//!
//! [`mark_failed`](TileCache::mark_failed) does **not** touch the LRU
//! order, so failed tiles naturally drift toward eviction.
//!
//! ## Complexity
//!
//! | Operation | Time | Notes |
//! |-----------|------|-------|
//! | `get` | O(1) | HashMap lookup |
//! | `insert_pending` | O(1) amortised | HashMap insert + linked-list append |
//! | `promote` | O(1) amortised | HashMap overwrite + linked-list move-to-tail |
//! | `mark_failed` | O(1) | HashMap overwrite only (no LRU reorder) |
//! | `remove` | O(1) | HashMap remove + linked-list unlink |
//! | `touch` | O(1) | Linked-list unlink + append |
//!
//! All LRU operations are O(1) via an intrusive doubly-linked list
//! threaded through `Option<TileId>` prev/next pointers stored
//! alongside each cache entry.
//!
//! ## Thread safety
//!
//! `TileCache` is `Send + Sync` (all fields are owned, no interior
//! mutability).  The engine wraps it inside `TileManager` which is
//! itself owned by `MapState`, guarded by an `RwLock` in the facade
//! crate's `MapHandle`.
// ---------------------------------------------------------------------------

use crate::tile_source::{TileData, TileError, TileFreshness, TileResponse};
use rustial_math::TileId;
use std::collections::HashMap;
use std::time::SystemTime;

/// Fraction of total cache entries that may be occupied by pure `Pending`
/// requests before new pending inserts are rejected.
///
/// This preserves room for renderable loaded tiles during long `fly_to`
/// transitions where many transient requests can otherwise crowd out the
/// imagery already available for fallback rendering.
const PENDING_ENTRY_CAP_DIVISOR: usize = 4;

/// Minimum cache size at which the pending-entry cap is enabled.
///
/// Small caches used in unit tests or constrained scenarios keep the
/// original behaviour so the cap only activates for production-sized
/// caches where large fly-to backlogs can otherwise crowd out loaded tiles.
const PENDING_ENTRY_CAP_MIN_CACHE_SIZE: usize = 64;

// ---------------------------------------------------------------------------
// O(1) LRU ordering via intrusive doubly-linked list
// ---------------------------------------------------------------------------

/// Intrusive doubly-linked list node embedded alongside each cache entry.
///
/// `prev` and `next` are `Option<TileId>` pointers into the same
/// `HashMap`.  The list has a virtual head (`lru_head`) and tail
/// (`lru_tail`) stored on `TileCache` itself.
#[derive(Debug)]
struct LruLink {
    prev: Option<TileId>,
    next: Option<TileId>,
}

// ---------------------------------------------------------------------------
// Eviction reporting
// ---------------------------------------------------------------------------

/// A tile evicted from the cache during an insertion or promotion.
#[derive(Debug)]
pub struct EvictedTile {
    /// ID of the evicted tile.
    pub id: TileId,
    /// State the tile had at the moment of eviction.
    pub entry: TileCacheEntry,
}

/// Snapshot counts for the current cache state.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct TileCacheStats {
    /// Total entries currently retained in the cache.
    pub total_entries: usize,
    /// Entries in `Pending` state.
    pub pending_entries: usize,
    /// Entries in `Loaded` state.
    pub loaded_entries: usize,
    /// Entries in `Expired` state.
    pub expired_entries: usize,
    /// Entries in `Reloading` state.
    pub reloading_entries: usize,
    /// Entries in `Failed` state.
    pub failed_entries: usize,
    /// Entries that still have renderable payloads.
    pub renderable_entries: usize,
}

impl EvictedTile {
    /// Returns `true` if the evicted tile was still in flight.
    #[inline]
    pub fn was_pending(&self) -> bool {
        self.entry.is_pending()
    }
}

/// Result of inserting a pending tile.
#[derive(Debug, Default)]
pub struct InsertPendingResult {
    /// Whether the tile was newly inserted.
    pub inserted: bool,
    /// Tiles evicted to make room for this insertion.
    pub evicted: Vec<EvictedTile>,
}

/// Loaded tile payload retained in the cache, including freshness metadata.
#[derive(Debug, Clone)]
pub struct CachedTile {
    /// Decoded tile data.
    pub data: TileData,
    /// Freshness metadata from the source response.
    pub freshness: TileFreshness,
    /// Wall-clock time when this tile was promoted to the `Loaded` state.
    ///
    /// Used by the tile-fade system to compute the elapsed time since the
    /// tile first became renderable.  Set once during
    /// [`TileCache::promote_with_eviction`] and never mutated afterwards.
    pub loaded_at: SystemTime,
}

impl CachedTile {
    /// Return `true` when the tile is stale at `now`.
    #[inline]
    pub fn is_expired_at(&self, now: SystemTime) -> bool {
        self.freshness.is_expired_at(now)
    }

    /// Return `true` when the tile is stale right now.
    #[inline]
    pub fn is_expired(&self) -> bool {
        self.freshness.is_expired()
    }
}

/// State of a tile in the cache.
#[derive(Debug)]
pub enum TileCacheEntry {
    /// A fetch has been issued but no renderable payload exists yet.
    Pending,
    /// The tile is loaded and considered fresh.
    Loaded(CachedTile),
    /// The tile payload is stale but still renderable while refresh is pending.
    Expired(CachedTile),
    /// A refresh is in flight; the previous payload remains renderable.
    Reloading(CachedTile),
    /// The tile fetch failed. The optional cached tile remains renderable when
    /// the failure happened during refresh/revalidation.
    Failed {
        /// Human-readable error description.
        error: String,
        /// Previously retained renderable payload, if any.
        stale: Option<CachedTile>,
    },
}

impl TileCacheEntry {
    /// Returns `true` if the entry is currently pending load.
    #[inline]
    pub fn is_pending(&self) -> bool {
        matches!(self, Self::Pending)
    }

    /// Returns `true` if the entry currently has a loaded or reloadable payload.
    #[inline]
    pub fn is_loaded(&self) -> bool {
        matches!(self, Self::Loaded(_) | Self::Expired(_) | Self::Reloading(_))
    }

    /// Returns `true` if the entry is in a stale-but-renderable expired state.
    #[inline]
    pub fn is_expired(&self) -> bool {
        matches!(self, Self::Expired(_))
    }

    /// Returns `true` if the entry is actively reloading while keeping old data.
    #[inline]
    pub fn is_reloading(&self) -> bool {
        matches!(self, Self::Reloading(_))
    }

    /// Returns `true` if the entry is in a failed state.
    #[inline]
    pub fn is_failed(&self) -> bool {
        matches!(self, Self::Failed { .. })
    }

    /// Returns `true` if this entry still has renderable tile data.
    #[inline]
    pub fn is_renderable(&self) -> bool {
        self.data().is_some()
    }

    /// Return the renderable tile payload, if any.
    #[inline]
    pub fn data(&self) -> Option<&TileData> {
        self.cached_tile().map(|tile| &tile.data)
    }

    /// Return the loaded payload, if any.
    #[inline]
    pub fn cached_tile(&self) -> Option<&CachedTile> {
        match self {
            Self::Loaded(tile) | Self::Expired(tile) | Self::Reloading(tile) => Some(tile),
            Self::Failed { stale, .. } => stale.as_ref(),
            Self::Pending => None,
        }
    }

    /// Return freshness metadata for renderable entries.
    #[inline]
    pub fn freshness(&self) -> Option<&TileFreshness> {
        self.cached_tile().map(|tile| &tile.freshness)
    }

    /// Return the wall-clock time when this entry was promoted to Loaded.
    ///
    /// Returns `None` for entries that have no renderable payload.
    #[inline]
    pub fn loaded_at(&self) -> Option<SystemTime> {
        self.cached_tile().map(|tile| tile.loaded_at)
    }
}

// ---------------------------------------------------------------------------
// TileCache
// ---------------------------------------------------------------------------

/// A fixed-capacity LRU in-memory tile cache.
///
/// See the [module-level documentation](self) for eviction policy,
/// lifecycle, and complexity details.
pub struct TileCache {
    /// Primary storage: tile ID -> (entry, LRU link).
    entries: HashMap<TileId, (TileCacheEntry, LruLink)>,
    /// Head of the LRU doubly-linked list (least recently used).
    lru_head: Option<TileId>,
    /// Tail of the LRU doubly-linked list (most recently used).
    lru_tail: Option<TileId>,
    /// Maximum number of entries before eviction kicks in.
    max_entries: usize,
    /// Optional byte budget.  When set, eviction also triggers when
    /// total payload bytes exceed this limit.
    max_bytes: Option<usize>,
    /// Running total of payload bytes in the cache.
    total_bytes: usize,
}

impl TileCache {
    /// Create a new cache with the given maximum capacity.
    ///
    /// A `max_entries` of 0 is valid but degenerate -- every insertion
    /// is immediately evicted.  Typical values range from 100 (low
    /// memory) to 1000+ (large-screen / high-zoom).
    pub fn new(max_entries: usize) -> Self {
        Self {
            entries: HashMap::with_capacity(max_entries),
            lru_head: None,
            lru_tail: None,
            max_entries,
            max_bytes: None,
            total_bytes: 0,
        }
    }

    /// Create a cache with both an entry-count and a byte-budget limit.
    ///
    /// Eviction triggers when **either** limit is exceeded.
    pub fn with_byte_budget(max_entries: usize, max_bytes: usize) -> Self {
        Self {
            entries: HashMap::with_capacity(max_entries),
            lru_head: None,
            lru_tail: None,
            max_entries,
            max_bytes: Some(max_bytes),
            total_bytes: 0,
        }
    }

    // -- Queries ----------------------------------------------------------

    /// Look up a tile in the cache.
    ///
    /// Returns `None` if the tile has never been inserted or has been
    /// evicted.  Does **not** update the LRU order (read-only).
    #[inline]
    pub fn get(&self, id: &TileId) -> Option<&TileCacheEntry> {
        self.entries.get(id).map(|(entry, _)| entry)
    }

    /// Returns `true` if the tile is present (in any state).
    #[inline]
    pub fn contains(&self, id: &TileId) -> bool {
        self.entries.contains_key(id)
    }

    /// Number of entries currently in the cache.
    #[inline]
    pub fn len(&self) -> usize {
        self.entries.len()
    }

    /// Whether the cache is empty.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.entries.is_empty()
    }

    /// Maximum capacity configured at construction time.
    #[inline]
    pub fn capacity(&self) -> usize {
        self.max_entries
    }

    /// Maximum number of pure `Pending` entries permitted at once.
    #[inline]
    fn max_pending_entries(&self) -> usize {
        if self.max_entries == 0 {
            0
        } else if self.max_entries < PENDING_ENTRY_CAP_MIN_CACHE_SIZE {
            usize::MAX
        } else {
            (self.max_entries / PENDING_ENTRY_CAP_DIVISOR).max(1)
        }
    }

    /// Number of pure `Pending` entries currently retained.
    #[inline]
    fn pending_entry_count(&self) -> usize {
        self.entries
            .values()
            .filter(|(entry, _)| entry.is_pending())
            .count()
    }

    /// Total payload bytes currently tracked in the cache.
    #[inline]
    pub fn total_bytes(&self) -> usize {
        self.total_bytes
    }

    /// The byte budget, if configured.
    #[inline]
    pub fn max_bytes(&self) -> Option<usize> {
        self.max_bytes
    }

    /// Return the IDs of all pending tiles currently in the cache.
    pub fn pending_ids(&self) -> Vec<TileId> {
        self.entries
            .iter()
            .filter_map(|(id, (entry, _))| entry.is_pending().then_some(*id))
            .collect()
    }

    /// Return the IDs of all tiles that are actively pending or reloading.
    pub fn inflight_ids(&self) -> Vec<TileId> {
        self.entries
            .iter()
            .filter_map(|(id, (entry, _))| match entry {
                TileCacheEntry::Pending | TileCacheEntry::Reloading(_) => Some(*id),
                _ => None,
            })
            .collect()
    }

    /// Return the IDs of all tiles that are stale and eligible for refresh at `now`.
    pub fn expired_ids_at(&self, now: SystemTime) -> Vec<TileId> {
        self.entries
            .iter()
            .filter_map(|(id, (entry, _))| match entry {
                TileCacheEntry::Loaded(tile) if tile.is_expired_at(now) => Some(*id),
                TileCacheEntry::Expired(_) => Some(*id),
                _ => None,
            })
            .collect()
    }

    /// Return the IDs of all tiles that are stale and eligible for refresh now.
    pub fn expired_ids(&self) -> Vec<TileId> {
        self.expired_ids_at(SystemTime::now())
    }

    /// Return a state-count snapshot of the cache contents.
    pub fn stats(&self) -> TileCacheStats {
        let mut stats = TileCacheStats {
            total_entries: self.entries.len(),
            ..TileCacheStats::default()
        };

        for (entry, _) in self.entries.values() {
            match entry {
                TileCacheEntry::Pending => stats.pending_entries += 1,
                TileCacheEntry::Loaded(_) => stats.loaded_entries += 1,
                TileCacheEntry::Expired(_) => stats.expired_entries += 1,
                TileCacheEntry::Reloading(_) => stats.reloading_entries += 1,
                TileCacheEntry::Failed { .. } => stats.failed_entries += 1,
            }
            if entry.is_renderable() {
                stats.renderable_entries += 1;
            }
        }

        stats
    }

    // -- LRU linked-list helpers (O(1)) -----------------------------------

    /// Unlink a node from the doubly-linked list without removing it from
    /// the `entries` HashMap.
    fn lru_unlink(&mut self, id: &TileId) {
        let Some((_, link)) = self.entries.get(id) else { return };
        let prev = link.prev;
        let next = link.next;

        if let Some(p) = prev {
            if let Some((_, plink)) = self.entries.get_mut(&p) {
                plink.next = next;
            }
        } else {
            self.lru_head = next;
        }

        if let Some(n) = next {
            if let Some((_, nlink)) = self.entries.get_mut(&n) {
                nlink.prev = prev;
            }
        } else {
            self.lru_tail = prev;
        }

        // Clear own pointers.
        if let Some((_, link)) = self.entries.get_mut(id) {
            link.prev = None;
            link.next = None;
        }
    }

    /// Append a node (already in `entries`) to the MRU tail of the list.
    fn lru_push_back(&mut self, id: &TileId) {
        if let Some(old_tail) = self.lru_tail {
            if let Some((_, tlink)) = self.entries.get_mut(&old_tail) {
                tlink.next = Some(*id);
            }
            if let Some((_, link)) = self.entries.get_mut(id) {
                link.prev = Some(old_tail);
                link.next = None;
            }
            self.lru_tail = Some(*id);
        } else {
            // Empty list.
            if let Some((_, link)) = self.entries.get_mut(id) {
                link.prev = None;
                link.next = None;
            }
            self.lru_head = Some(*id);
            self.lru_tail = Some(*id);
        }
    }

    // -- Mutations --------------------------------------------------------

    /// Mark an existing entry as recently used (O(1)).
    ///
    /// Returns `true` if the tile was present and moved to the MRU end.
    pub fn touch(&mut self, id: &TileId) -> bool {
        if !self.entries.contains_key(id) {
            return false;
        }
        self.lru_unlink(id);
        self.lru_push_back(id);
        true
    }

    /// Insert a [`Pending`](TileCacheEntry::Pending) entry for `id` and report
    /// any evictions that occurred.
    pub fn insert_pending_with_eviction(&mut self, id: TileId) -> InsertPendingResult {
        if self.max_entries == 0 || self.entries.contains_key(&id) {
            return InsertPendingResult::default();
        }

        if self.pending_entry_count() >= self.max_pending_entries() {
            return InsertPendingResult::default();
        }

        let evicted = self.evict_if_full_for_pending_insert();
        if self.entries.len() >= self.max_entries {
            return InsertPendingResult::default();
        }
        self.entries.insert(id, (TileCacheEntry::Pending, LruLink { prev: None, next: None }));
        self.lru_push_back(&id);

        InsertPendingResult {
            inserted: true,
            evicted,
        }
    }

    /// Insert a [`Pending`](TileCacheEntry::Pending) entry for `id`.
    ///
    /// Returns `true` if the entry was newly inserted.
    pub fn insert_pending(&mut self, id: TileId) -> bool {
        self.insert_pending_with_eviction(id).inserted
    }

    /// Promote an entry to [`Loaded`](TileCacheEntry::Loaded) and move
    /// it to the most-recently-used position, reporting any evicted tiles.
    pub fn promote_with_eviction(&mut self, id: TileId, response: TileResponse) -> Vec<EvictedTile> {
        if self.max_entries == 0 {
            return Vec::new();
        }

        let byte_len = response.data.byte_len();

        let evicted = if !self.entries.contains_key(&id) {
            let evicted = self.evict_if_full();
            self.entries.insert(id, (TileCacheEntry::Pending, LruLink { prev: None, next: None }));
            self.lru_push_back(&id);
            evicted
        } else {
            // Remove old byte count before replacing.
            if let Some((old_entry, _)) = self.entries.get(&id) {
                if let Some(data) = old_entry.data() {
                    self.total_bytes = self.total_bytes.saturating_sub(data.byte_len());
                }
            }
            self.touch(&id);
            Vec::new()
        };

        self.entries.get_mut(&id).unwrap().0 = TileCacheEntry::Loaded(CachedTile {
            data: response.data,
            freshness: response.freshness,
            loaded_at: SystemTime::now(),
        });
        self.total_bytes += byte_len;

        // Byte-budget eviction: continue evicting LRU entries until we
        // are within budget.
        let mut extra_evicted = Vec::new();
        if let Some(max) = self.max_bytes {
            while self.total_bytes > max && self.entries.len() > 1 {
                if let Some(old) = self.lru_head {
                    if old == id {
                        break; // Don't evict the entry we just promoted.
                    }
                    if let Some(ev) = self.remove_and_return(old) {
                        extra_evicted.push(ev);
                    }
                } else {
                    break;
                }
            }
        }

        if extra_evicted.is_empty() {
            evicted
        } else {
            let mut all = evicted;
            all.extend(extra_evicted);
            all
        }
    }

    /// Promote an entry to [`Loaded`](TileCacheEntry::Loaded) and move
    /// it to the most-recently-used position.
    pub fn promote(&mut self, id: TileId, response: TileResponse) {
        let _ = self.promote_with_eviction(id, response);
    }

    /// Mark a loaded tile as expired while keeping it renderable.
    pub fn mark_expired(&mut self, id: TileId) -> bool {
        let Some((entry, _)) = self.entries.get_mut(&id) else {
            return false;
        };

        match entry {
            TileCacheEntry::Loaded(tile) => {
                let tile = tile.clone();
                *entry = TileCacheEntry::Expired(tile);
                true
            }
            TileCacheEntry::Expired(_) | TileCacheEntry::Reloading(_) => true,
            TileCacheEntry::Pending | TileCacheEntry::Failed { .. } => false,
        }
    }

    /// Transition a stale tile into reloading while retaining its old payload.
    pub fn start_reload(&mut self, id: TileId) -> bool {
        let transitioned = match self.entries.get_mut(&id) {
            Some((TileCacheEntry::Loaded(tile), _)) | Some((TileCacheEntry::Expired(tile), _)) => {
                let tile = tile.clone();
                self.entries.get_mut(&id).expect("entry should exist").0 = TileCacheEntry::Reloading(tile);
                true
            }
            _ => false,
        };

        if transitioned {
            self.touch(&id);
        }

        transitioned
    }

    /// Refresh the TTL of a reloading/expired entry without replacing its
    /// payload.
    ///
    /// This is the cache-side handler for `304 Not Modified` responses.
    pub fn refresh_ttl(&mut self, id: TileId, freshness: TileFreshness) -> bool {
        let Some((entry, _)) = self.entries.get_mut(&id) else {
            return false;
        };

        match entry {
            TileCacheEntry::Reloading(tile) | TileCacheEntry::Expired(tile) => {
                tile.freshness = freshness;
                let tile = tile.clone();
                *entry = TileCacheEntry::Loaded(tile);
                self.touch(&id);
                true
            }
            TileCacheEntry::Loaded(tile) => {
                tile.freshness = freshness;
                true
            }
            TileCacheEntry::Pending | TileCacheEntry::Failed { .. } => false,
        }
    }

    /// Return the revalidation hint (etag + last-modified) for a tile.
    pub fn revalidation_hint(&self, id: &TileId) -> Option<crate::tile_source::RevalidationHint> {
        let (entry, _) = self.entries.get(id)?;
        let freshness = entry.freshness()?;
        Some(crate::tile_source::RevalidationHint {
            etag: freshness.etag.clone(),
            last_modified: freshness.last_modified.clone(),
        })
    }

    /// Mark the tile as failed, preserving stale renderable payload when possible.
    pub fn mark_failed(&mut self, id: TileId, error: &TileError) {
        if let Some((entry, _)) = self.entries.get_mut(&id) {
            match entry {
                TileCacheEntry::Reloading(tile) | TileCacheEntry::Expired(tile) => {
                    let tile = tile.clone();
                    *entry = TileCacheEntry::Expired(tile);
                }
                TileCacheEntry::Loaded(_) | TileCacheEntry::Pending | TileCacheEntry::Failed { .. } => {
                    let stale = match entry {
                        TileCacheEntry::Loaded(tile) => Some(tile.clone()),
                        TileCacheEntry::Failed { stale, .. } => stale.clone(),
                        _ => None,
                    };
                    *entry = TileCacheEntry::Failed {
                        error: error.to_string(),
                        stale,
                    };
                }
            }
        }
    }

    /// Cancel an in-flight reload, demoting the entry back to `Expired`
    /// while preserving its renderable payload.
    ///
    /// Returns `true` if the entry was `Reloading` and was demoted.
    /// Has no effect on entries in any other state.
    pub fn cancel_reload(&mut self, id: &TileId) -> bool {
        let Some((entry, _)) = self.entries.get_mut(id) else {
            return false;
        };
        match entry {
            TileCacheEntry::Reloading(tile) => {
                let tile = tile.clone();
                *entry = TileCacheEntry::Expired(tile);
                true
            }
            _ => false,
        }
    }

    /// Remove a tile from the cache (O(1)).
    ///
    /// Returns `true` if the tile was present and removed.
    pub fn remove(&mut self, id: &TileId) -> bool {
        self.remove_and_return(*id).is_some()
    }

    /// Remove all entries from the cache.
    pub fn clear(&mut self) {
        for (_, (entry, _)) in self.entries.drain() {
            if let Some(data) = entry.data() {
                self.total_bytes = self.total_bytes.saturating_sub(data.byte_len());
            }
        }
        self.lru_head = None;
        self.lru_tail = None;
        self.total_bytes = 0;
    }

    // -- Internal ---------------------------------------------------------

    /// Remove a tile and return its eviction record.
    fn remove_and_return(&mut self, id: TileId) -> Option<EvictedTile> {
        self.lru_unlink(&id);
        if let Some((entry, _)) = self.entries.remove(&id) {
            if let Some(data) = entry.data() {
                self.total_bytes = self.total_bytes.saturating_sub(data.byte_len());
            }
            Some(EvictedTile { id, entry })
        } else {
            None
        }
    }

    /// Evict entries until the cache is below capacity.
    ///
    /// Prefers evicting non-loaded entries (pending, failed, expired)
    /// before loaded entries.  This protects cached tile imagery from
    /// being displaced by transient pending requests during fly-to
    /// transitions where intermediate zoom levels briefly select many
    /// tiles that will never finish loading before the camera moves on.
    fn evict_if_full(&mut self) -> Vec<EvictedTile> {
        let mut evicted = Vec::new();
        while self.entries.len() >= self.max_entries {
            // Eviction priority:
            // 1. Failed entries (disposable, no in-flight work).
            // 2. Non-pending entries via LRU (stale Loaded data from
            //    old zoom levels).
            // 3. Pending entries via LRU (last resort — cancels an
            //    in-flight HTTP request, but prevents unbounded growth).
            let victim = self.find_failed_lru()
                .or_else(|| self.find_non_pending_lru())
                .or_else(|| self.lru_head);
            if let Some(id) = victim {
                if let Some(ev) = self.remove_and_return(id) {
                    evicted.push(ev);
                }
            } else {
                break;
            }
        }
        evicted
    }

    /// Evict entries until the cache is below capacity for a new `Pending` insert.
    ///
    /// This path is more continuity-biased than the generic eviction policy:
    /// when admitting more pending work, prefer cancelling older pending work
    /// before displacing renderable entries that can still provide exact or
    /// fallback coverage.  As a last resort, the least-recently-used
    /// renderable entry is evicted so that new destinations can always
    /// make forward progress.  The pending-entry cap
    /// ([`max_pending_entries`]) prevents this from over-displacing
    /// loaded imagery during long fly-to transitions.
    fn evict_if_full_for_pending_insert(&mut self) -> Vec<EvictedTile> {
        let mut evicted = Vec::new();
        while self.entries.len() >= self.max_entries {
            let victim = self
                .find_non_renderable_lru()
                .or_else(|| self.find_pending_lru())
                .or_else(|| self.find_non_renderable_non_pending_lru())
                .or_else(|| self.lru_head);
            if let Some(id) = victim {
                if let Some(ev) = self.remove_and_return(id) {
                    evicted.push(ev);
                }
            } else {
                break;
            }
        }
        evicted
    }

    /// Walk the LRU list from head and return the first `Failed` entry.
    fn find_failed_lru(&self) -> Option<TileId> {
        let mut cursor = self.lru_head;
        while let Some(id) = cursor {
            if let Some((entry, link)) = self.entries.get(&id) {
                if entry.is_failed() {
                    return Some(id);
                }
                cursor = link.next;
            } else {
                break;
            }
        }
        None
    }

    /// Walk the LRU list from head and return the first non-renderable entry.
    fn find_non_renderable_lru(&self) -> Option<TileId> {
        let mut cursor = self.lru_head;
        while let Some(id) = cursor {
            if let Some((entry, link)) = self.entries.get(&id) {
                if !entry.is_renderable() {
                    return Some(id);
                }
                cursor = link.next;
            } else {
                break;
            }
        }
        None
    }

    /// Walk the LRU list from head and return the first non-pending,
    /// non-renderable entry.
    fn find_non_renderable_non_pending_lru(&self) -> Option<TileId> {
        let mut cursor = self.lru_head;
        while let Some(id) = cursor {
            if let Some((entry, link)) = self.entries.get(&id) {
                if !entry.is_pending() && !entry.is_renderable() {
                    return Some(id);
                }
                cursor = link.next;
            } else {
                break;
            }
        }
        None
    }

    /// Walk the LRU list from head and return the first `Pending` entry.
    fn find_pending_lru(&self) -> Option<TileId> {
        let mut cursor = self.lru_head;
        while let Some(id) = cursor {
            if let Some((entry, link)) = self.entries.get(&id) {
                if entry.is_pending() {
                    return Some(id);
                }
                cursor = link.next;
            } else {
                break;
            }
        }
        None
    }

    /// Walk the LRU list from head and return the first non-Pending entry.
    ///
    /// This skips `Pending` entries (in-flight requests) so that the
    /// eviction policy prefers removing stale `Loaded` data over
    /// cancelling active downloads.
    fn find_non_pending_lru(&self) -> Option<TileId> {
        let mut cursor = self.lru_head;
        while let Some(id) = cursor {
            if let Some((entry, link)) = self.entries.get(&id) {
                if !entry.is_pending() {
                    return Some(id);
                }
                cursor = link.next;
            } else {
                break;
            }
        }
        None
    }
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;
    use crate::tile_source::{DecodedImage, TileResponse};
    use std::time::Duration;

    fn dummy_tile_data() -> TileData {
        TileData::Raster(DecodedImage {
            width: 256,
            height: 256,
            data: vec![0u8; 256 * 256 * 4].into(),
        })
    }

    fn dummy_tile_response() -> TileResponse {
        TileResponse::from_data(dummy_tile_data())
    }

    fn expiring_tile_response() -> TileResponse {
        TileResponse::from_data(dummy_tile_data()).with_freshness(TileFreshness {
            expires_at: Some(SystemTime::now() - Duration::from_secs(1)),
            etag: Some("etag-1".into()),
            last_modified: None,
        })
    }

    // -- Construction and basic queries -----------------------------------

    #[test]
    fn new_cache_is_empty() {
        let cache = TileCache::new(10);
        assert!(cache.is_empty());
        assert_eq!(cache.len(), 0);
        assert_eq!(cache.capacity(), 10);
    }

    #[test]
    fn zero_capacity_cache() {
        let mut cache = TileCache::new(0);
        let result = cache.insert_pending_with_eviction(TileId::new(0, 0, 0));
        assert!(!result.inserted);
        assert!(result.evicted.is_empty());
        assert!(cache.is_empty());
    }

    // -- insert_pending ---------------------------------------------------

    #[test]
    fn insert_and_get() {
        let mut cache = TileCache::new(10);
        let id = TileId::new(0, 0, 0);
        assert!(cache.insert_pending(id));
        assert!(cache.contains(&id));
        assert!(cache.get(&id).unwrap().is_pending());
    }

    #[test]
    fn no_double_insert() {
        let mut cache = TileCache::new(10);
        let id = TileId::new(0, 0, 0);
        assert!(cache.insert_pending(id));
        assert!(!cache.insert_pending(id));
        assert_eq!(cache.len(), 1);
    }

    #[test]
    fn insert_does_not_overwrite_loaded() {
        let mut cache = TileCache::new(10);
        let id = TileId::new(0, 0, 0);
        cache.insert_pending(id);
        cache.promote(id, dummy_tile_response());
        // Trying to re-insert as Pending should be a no-op.
        assert!(!cache.insert_pending(id));
        assert!(cache.get(&id).unwrap().is_loaded());
    }

    // -- promote ----------------------------------------------------------

    #[test]
    fn promote_to_loaded() {
        let mut cache = TileCache::new(10);
        let id = TileId::new(0, 0, 0);
        cache.insert_pending(id);
        cache.promote(id, dummy_tile_response());
        let entry = cache.get(&id).unwrap();
        assert!(entry.is_loaded());
        assert!(entry.data().is_some());
    }

    #[test]
    fn promote_without_prior_pending() {
        // If the pending entry was evicted while the fetch was in
        // flight, promote should still insert the loaded data.
        let mut cache = TileCache::new(10);
        let id = TileId::new(5, 10, 10);
        cache.promote(id, dummy_tile_response());
        assert!(cache.contains(&id));
        assert!(cache.get(&id).unwrap().is_loaded());
    }

    #[test]
    fn pending_entry_cap_rejects_excess_pending_inserts() {
        let mut cache = TileCache::new(64);
        let ids: Vec<TileId> = (0..17).map(|i| TileId::new(5, i, 0)).collect();

        assert_eq!(cache.max_pending_entries(), 16);
        for &id in &ids[..16] {
            assert!(cache.insert_pending(id));
        }
        assert!(!cache.insert_pending(ids[16]));

        assert_eq!(cache.pending_entry_count(), 16);
        assert_eq!(cache.len(), 16);
        assert!(!cache.contains(&ids[16]));
    }

    #[test]
    fn pending_entry_cap_preserves_loaded_entries() {
        let mut cache = TileCache::new(64);
        let loaded: Vec<TileId> = (0..6).map(|i| TileId::new(5, i, 0)).collect();
        let pending: Vec<TileId> = (10..27).map(|i| TileId::new(5, i, 0)).collect();

        for &id in &loaded {
            cache.promote(id, dummy_tile_response());
        }
        for &id in &pending[..16] {
            assert!(cache.insert_pending(id));
        }

        assert!(!cache.insert_pending(pending[16]));
        assert_eq!(cache.pending_entry_count(), 16);
        for &id in &loaded {
            assert!(cache.contains(&id), "loaded tile should be retained when pending cap is hit");
        }
    }

    #[test]
    fn late_promotion_bypasses_pending_entry_cap() {
        let mut cache = TileCache::new(64);
        let late = TileId::new(6, 42, 0);

        for i in 0..cache.max_pending_entries() {
            assert!(cache.insert_pending(TileId::new(6, i as u32, 0)));
        }
        assert!(!cache.insert_pending(TileId::new(6, 63, 0)));

        cache.promote(late, dummy_tile_response());

        assert!(cache.contains(&late));
        assert!(cache.get(&late).unwrap().is_loaded());
    }

    #[test]
    fn pending_insert_prefers_evicting_pending_before_loaded() {
        let mut cache = TileCache::new(3);
        let a = TileId::new(1, 0, 0);
        let b = TileId::new(1, 0, 1);
        let c = TileId::new(1, 1, 0);

        cache.insert_pending(a); // LRU order: [a]
        cache.insert_pending(b); // [a, b]
        cache.insert_pending(c); // [a, b, c]

        // Promote 'a' to loaded -- should move it to MRU position.
        cache.promote(a, dummy_tile_response()); // [b, c, a]

        // Promote 'b' to loaded -- should move it to MRU position.
        cache.promote(b, dummy_tile_response()); // [c, a, b]

        // Insert 'd' -- pending admission should preserve renderable
        // continuity by evicting the oldest pending entry before loaded
        // imagery that can still be shown as exact or fallback coverage.
        let d = TileId::new(1, 1, 1);
        cache.insert_pending(d);
        assert!(cache.contains(&a), "'a' should survive (Loaded, still renderable)");
        assert!(cache.contains(&b), "'b' should survive (MRU Loaded)");
        assert!(!cache.contains(&c), "'c' should be evicted (oldest Pending)");
        assert!(cache.contains(&d));
    }

    #[test]
    fn pending_insert_keeps_expired_renderable_tile_over_pending() {
        let mut cache = TileCache::new(2);
        let expired = TileId::new(4, 0, 0);
        let pending = TileId::new(4, 1, 0);
        let incoming = TileId::new(4, 2, 0);

        cache.promote(expired, expiring_tile_response());
        assert!(cache.mark_expired(expired));
        assert!(cache.insert_pending(pending));

        let result = cache.insert_pending_with_eviction(incoming);

        assert!(result.inserted);
        assert!(cache.contains(&expired), "expired renderable tile should be retained");
        assert!(!cache.contains(&pending), "older pending tile should be evicted first");
        assert!(cache.contains(&incoming));
    }

    #[test]
    fn pending_insert_evicts_lru_renderable_as_last_resort() {
        let mut cache = TileCache::new(2);
        let loaded = TileId::new(5, 0, 0);
        let expired = TileId::new(5, 1, 0);
        let incoming = TileId::new(5, 2, 0);

        cache.promote(loaded, dummy_tile_response());
        cache.promote(expired, expiring_tile_response());
        assert!(cache.mark_expired(expired));

        let result = cache.insert_pending_with_eviction(incoming);

        assert!(result.inserted, "pending insert must succeed by evicting LRU renderable");
        assert_eq!(result.evicted.len(), 1);
        assert_eq!(result.evicted[0].id, loaded, "LRU renderable entry should be evicted");
        assert!(cache.contains(&expired));
        assert!(cache.contains(&incoming));
    }

    #[test]
    fn pending_insert_evicts_lru_renderable_failed_entry_as_last_resort() {
        let mut cache = TileCache::new(2);
        let failed_stale = TileId::new(6, 0, 0);
        let loaded = TileId::new(6, 1, 0);
        let incoming = TileId::new(6, 2, 0);

        cache.promote(failed_stale, dummy_tile_response());
        cache.mark_failed(failed_stale, &TileError::Network("boom".into()));
        cache.promote(loaded, dummy_tile_response());

        let result = cache.insert_pending_with_eviction(incoming);

        assert!(result.inserted, "pending insert must succeed by evicting LRU renderable");
        assert_eq!(result.evicted.len(), 1);
        assert_eq!(result.evicted[0].id, failed_stale, "LRU failed-but-renderable entry should be evicted");
        assert!(cache.contains(&loaded));
        assert!(cache.contains(&incoming));
    }

    // -- mark_failed ------------------------------------------------------

    #[test]
    fn cancel_reload_demotes_reloading_to_expired() {
        let mut cache = TileCache::new(10);
        let id = TileId::new(3, 0, 0);
        cache.promote(id, expiring_tile_response());
        assert!(cache.start_reload(id));
        assert!(cache.get(&id).unwrap().is_reloading());

        assert!(cache.cancel_reload(&id));

        let entry = cache.get(&id).unwrap();
        assert!(entry.is_expired());
        assert!(entry.is_renderable());
        assert!(entry.data().is_some());
    }

    #[test]
    fn cancel_reload_has_no_effect_on_non_reloading() {
        let mut cache = TileCache::new(10);
        let pending = TileId::new(3, 0, 0);
        let loaded = TileId::new(3, 1, 0);
        cache.insert_pending(pending);
        cache.promote(loaded, dummy_tile_response());

        assert!(!cache.cancel_reload(&pending));
        assert!(!cache.cancel_reload(&loaded));
        assert!(cache.get(&pending).unwrap().is_pending());
        assert!(cache.get(&loaded).unwrap().is_loaded());
    }

    #[test]
    fn mark_failed_sets_state() {
        let mut cache = TileCache::new(10);
        let id = TileId::new(0, 0, 0);
        cache.insert_pending(id);
        let err = TileError::Network("timeout".into());
        cache.mark_failed(id, &err);
        let entry = cache.get(&id).unwrap();
        assert!(entry.is_failed());
        if let TileCacheEntry::Failed { error, .. } = entry {
            assert!(error.contains("timeout"));
        }
    }

    #[test]
    fn mark_failed_ignores_missing_entry() {
        let mut cache = TileCache::new(1);
        cache.mark_failed(TileId::new(1, 0, 0), &TileError::Other("boom".into()));
        assert!(cache.is_empty());
    }

    // -- remove -----------------------------------------------------------

    #[test]
    fn remove_existing() {
        let mut cache = TileCache::new(10);
        let id = TileId::new(0, 0, 0);
        cache.insert_pending(id);
        assert!(cache.remove(&id));
        assert!(!cache.contains(&id));
        assert!(cache.is_empty());
    }

    #[test]
    fn remove_nonexistent() {
        let mut cache = TileCache::new(10);
        assert!(!cache.remove(&TileId::new(0, 0, 0)));
    }

    // -- clear ------------------------------------------------------------

    #[test]
    fn clear_empties_cache() {
        let mut cache = TileCache::new(10);
        cache.insert_pending(TileId::new(0, 0, 0));
        cache.insert_pending(TileId::new(1, 0, 0));
        cache.promote(TileId::new(1, 0, 0), dummy_tile_response());
        assert_eq!(cache.len(), 2);

        cache.clear();
        assert!(cache.is_empty());
        assert_eq!(cache.len(), 0);
        // Capacity is unchanged.
        assert_eq!(cache.capacity(), 10);
    }

    // -- eviction ---------------------------------------------------------

    #[test]
    fn eviction_at_capacity() {
        let mut cache = TileCache::new(2);
        let a = TileId::new(1, 0, 0);
        let b = TileId::new(1, 0, 1);
        let c = TileId::new(1, 1, 0);

        cache.insert_pending(a);
        cache.insert_pending(b);
        cache.insert_pending(c);

        assert_eq!(cache.len(), 2);
        assert!(!cache.contains(&a), "first entry should be evicted");
        assert!(cache.contains(&b));
        assert!(cache.contains(&c));
    }

    #[test]
    fn eviction_fifo_without_touch() {
        // Without any promote/touch, eviction follows insertion order.
        let mut cache = TileCache::new(3);
        let ids: Vec<TileId> = (0..5).map(|i| TileId::new(4, i, 0)).collect();

        for &id in &ids {
            cache.insert_pending(id);
        }

        // Only the last 3 should survive.
        assert_eq!(cache.len(), 3);
        assert!(!cache.contains(&ids[0]));
        assert!(!cache.contains(&ids[1]));
        assert!(cache.contains(&ids[2]));
        assert!(cache.contains(&ids[3]));
        assert!(cache.contains(&ids[4]));
    }

    // -- TileCacheEntry helpers -------------------------------------------

    #[test]
    fn entry_state_helpers() {
        assert!(TileCacheEntry::Pending.is_pending());
        assert!(!TileCacheEntry::Pending.is_loaded());
        assert!(!TileCacheEntry::Pending.is_failed());
        assert!(TileCacheEntry::Pending.data().is_none());

        let loaded = TileCacheEntry::Loaded(CachedTile {
            data: dummy_tile_data(),
            freshness: TileFreshness::default(),
            loaded_at: SystemTime::now(),
        });
        assert!(!loaded.is_pending());
        assert!(loaded.is_loaded());
        assert!(!loaded.is_failed());
        assert!(loaded.data().is_some());

        let failed = TileCacheEntry::Failed {
            error: "err".into(),
            stale: None,
        };
        assert!(!failed.is_pending());
        assert!(!failed.is_loaded());
        assert!(failed.is_failed());
        assert!(failed.data().is_none());
    }

    #[test]
    fn expired_tile_is_renderable_and_refreshable() {
        let mut cache = TileCache::new(4);
        let id = TileId::new(1, 0, 0);
        cache.promote(id, expiring_tile_response());

        assert_eq!(cache.expired_ids(), vec![id]);
        assert!(cache.mark_expired(id));
        assert!(cache.get(&id).unwrap().is_expired());
        assert!(cache.get(&id).unwrap().is_renderable());
        assert!(cache.start_reload(id));
        assert!(cache.get(&id).unwrap().is_reloading());
    }

    #[test]
    fn failed_reload_keeps_stale_payload_renderable() {
        let mut cache = TileCache::new(4);
        let id = TileId::new(1, 0, 0);
        cache.promote(id, dummy_tile_response());
        assert!(cache.start_reload(id));

        cache.mark_failed(id, &TileError::Network("timeout".into()));
        let entry = cache.get(&id).unwrap();
        assert!(entry.is_expired());
        assert!(entry.is_renderable());
    }

    // -- Phase 5: O(1) LRU ordering tests ---------------------------------

    #[test]
    fn lru_evicts_least_recently_used_first() {
        let mut cache = TileCache::new(3);
        let a = TileId::new(0, 0, 0);
        let b = TileId::new(1, 0, 0);
        let c = TileId::new(2, 0, 0);
        cache.insert_pending(a);
        cache.insert_pending(b);
        cache.insert_pending(c);

        // Touch `a` so `b` becomes the LRU.
        cache.touch(&a);

        let d = TileId::new(3, 0, 0);
        cache.insert_pending(d);

        // `b` should have been evicted (it was LRU).
        assert!(!cache.contains(&b), "b should be evicted as LRU");
        assert!(cache.contains(&a));
        assert!(cache.contains(&c));
        assert!(cache.contains(&d));
    }

    #[test]
    fn lru_touch_moves_to_mru_end() {
        let mut cache = TileCache::new(2);
        let a = TileId::new(0, 0, 0);
        let b = TileId::new(1, 0, 0);
        cache.insert_pending(a);
        cache.insert_pending(b);

        // Touch `a` so it becomes MRU; `b` is now LRU.
        cache.touch(&a);

        let c = TileId::new(2, 0, 0);
        cache.insert_pending(c);

        assert!(!cache.contains(&b), "b should be evicted");
        assert!(cache.contains(&a));
        assert!(cache.contains(&c));
    }

    #[test]
    fn lru_remove_is_o1() {
        let mut cache = TileCache::new(5);
        for i in 0..5 {
            cache.insert_pending(TileId::new(i, 0, 0));
        }

        // Remove the middle entry.
        let mid = TileId::new(2, 0, 0);
        assert!(cache.remove(&mid));
        assert!(!cache.contains(&mid));
        assert_eq!(cache.len(), 4);

        // Insert a new entry � should not panic or corrupt the list.
        cache.insert_pending(TileId::new(5, 0, 0));
        assert_eq!(cache.len(), 5);
    }

    // -- Phase 5: refresh_ttl (304 Not Modified) --------------------------

    #[test]
    fn refresh_ttl_updates_freshness_without_replacing_data() {
        let mut cache = TileCache::new(4);
        let id = TileId::new(1, 0, 0);
        cache.insert_pending(id);
        cache.promote(id, expiring_tile_response());

        // Mark as reloading (simulating a refresh request).
        assert!(cache.start_reload(id));
        assert!(cache.get(&id).unwrap().is_reloading());

        // Simulate 304 � refresh TTL.
        let new_freshness = TileFreshness {
            expires_at: Some(SystemTime::now() + Duration::from_secs(3600)),
            etag: Some("etag-2".into()),
            last_modified: None,
        };
        assert!(cache.refresh_ttl(id, new_freshness.clone()));

        let entry = cache.get(&id).unwrap();
        assert!(entry.is_loaded(), "should be back to Loaded state");
        assert!(!entry.is_expired());

        let freshness = entry.freshness().unwrap();
        assert_eq!(freshness.etag.as_deref(), Some("etag-2"));
    }

    #[test]
    fn refresh_ttl_returns_false_for_pending_entry() {
        let mut cache = TileCache::new(4);
        let id = TileId::new(1, 0, 0);
        cache.insert_pending(id);

        let freshness = TileFreshness::default();
        assert!(!cache.refresh_ttl(id, freshness));
    }

    // -- Phase 5: revalidation_hint ---------------------------------------

    #[test]
    fn revalidation_hint_extracts_etag_and_last_modified() {
        let mut cache = TileCache::new(4);
        let id = TileId::new(1, 0, 0);
        cache.insert_pending(id);
        cache.promote(id, expiring_tile_response());

        let hint = cache.revalidation_hint(&id).expect("hint for loaded tile");
        assert_eq!(hint.etag.as_deref(), Some("etag-1"));
        assert!(hint.has_validators());
    }

    #[test]
    fn revalidation_hint_returns_none_for_missing_tile() {
        let cache = TileCache::new(4);
        let id = TileId::new(1, 0, 0);
        assert!(cache.revalidation_hint(&id).is_none());
    }

    // -- Phase 5: byte-budget eviction ------------------------------------

    #[test]
    fn byte_budget_evicts_when_exceeded() {
        // Each dummy tile is 256*256*4 = 262144 bytes.
        let tile_bytes = 256 * 256 * 4;
        // Budget: 2 tiles worth of bytes.
        let mut cache = TileCache::with_byte_budget(10, tile_bytes * 2 + 100);
        assert_eq!(cache.max_bytes(), Some(tile_bytes * 2 + 100));

        let a = TileId::new(0, 0, 0);
        let b = TileId::new(1, 0, 0);
        let c = TileId::new(2, 0, 0);

        cache.insert_pending(a);
        cache.promote(a, dummy_tile_response());
        assert_eq!(cache.total_bytes(), tile_bytes);

        cache.insert_pending(b);
        cache.promote(b, dummy_tile_response());
        assert_eq!(cache.total_bytes(), tile_bytes * 2);

        // Third tile exceeds byte budget � should evict `a`.
        cache.insert_pending(c);
        cache.promote(c, dummy_tile_response());
        assert!(!cache.contains(&a), "a should be evicted by byte budget");
        assert!(cache.contains(&b));
        assert!(cache.contains(&c));
        assert!(cache.total_bytes() <= tile_bytes * 2 + 100);
    }

    #[test]
    fn byte_budget_tracks_removal() {
        let tile_bytes = 256 * 256 * 4;
        let mut cache = TileCache::with_byte_budget(10, tile_bytes * 10);

        let id = TileId::new(0, 0, 0);
        cache.insert_pending(id);
        cache.promote(id, dummy_tile_response());
        assert_eq!(cache.total_bytes(), tile_bytes);

        cache.remove(&id);
        assert_eq!(cache.total_bytes(), 0);
    }
}