ghost_list.rs

//! Bounded recency list for ghost entries.
//!
//! Used by adaptive policies (ARC/2Q-style) to track recently evicted keys
//! without storing values. Implemented as an [`IntrusiveList`]
//! plus a `HashMap` index for O(1) lookups.
//!
//! ## Architecture
//!
//! ```text
//! ┌───────────────────────────────────────────────────────────────────────────┐
//! │                           GhostList Layout                                │
//! │                                                                           │
//! │   ┌─────────────────────────────┐   ┌─────────────────────────────────┐   │
//! │   │  index: HashMap<K, SlotId>  │   │  list: IntrusiveList<K>         │   │
//! │   │                             │   │                                 │   │
//! │   │  ┌───────────┬──────────┐   │   │  head ──► [A] ◄──► [B] ◄──► [C] │   │
//! │   │  │    Key    │  SlotId  │   │   │            MRU             LRU  │   │
//! │   │  ├───────────┼──────────┤   │   │                             ▲   │   │
//! │   │  │  "key_a"  │   id_0   │───┼───┼─────────► [A]               │   │   │
//! │   │  │  "key_b"  │   id_1   │───┼───┼─────────► [B]               │   │   │
//! │   │  │  "key_c"  │   id_2   │───┼───┼─────────► [C] ◄─────────────┘   │   │
//! │   │  └───────────┴──────────┘   │   │                    tail         │   │
//! │   └─────────────────────────────┘   └─────────────────────────────────┘   │
//! │                                                                           │
//! │   Record Flow (capacity = 3)                                              │
//! │   ──────────────────────────────                                          │
//! │                                                                           │
//! │   record("key_d") when full:                                              │
//! │     1. Check index: "key_d" not found                                     │
//! │     2. At capacity: evict LRU ("key_c")                                   │
//! │        - pop_back() from list                                             │
//! │        - remove("key_c") from index                                       │
//! │     3. Insert "key_d" at front (MRU)                                      │
//! │        - push_front("key_d") in list                                      │
//! │        - insert("key_d", id) in index                                     │
//! │                                                                           │
//! │   record("key_a") when present:                                           │
//! │     1. Check index: "key_a" found with id_0                               │
//! │     2. move_to_front(id_0) in list                                        │
//! │     3. Done (no eviction needed)                                          │
//! │                                                                           │
//! └───────────────────────────────────────────────────────────────────────────┘
//! ```
//!
//! ## Key Components
//!
//! - [`GhostList`]: Bounded recency tracker for evicted keys
//! - [`Iter`]: Iterator over keys in MRU to LRU order; created by [`GhostList::iter`]
//! - [`IntoIter`]: Consuming iterator over keys; created by `.into_iter()`
//!
//! ## Operations
//!
//! | Operation      | Description                           | Complexity |
//! |----------------|---------------------------------------|------------|
//! | [`record`](GhostList::record) | Add/promote key to MRU, evict if full | O(1) avg |
//! | [`remove`](GhostList::remove) | Remove key from ghost list | O(1) avg |
//! | [`contains`](GhostList::contains) | Check if key is tracked | O(1) avg |
//! | [`evict_lru`](GhostList::evict_lru) | Pop the least recently used key | O(1) avg |
//! | [`record_batch`](GhostList::record_batch) | Record multiple keys | O(n) |
//! | [`remove_batch`](GhostList::remove_batch) | Remove multiple keys | O(n) |
//! | [`iter`](GhostList::iter) | Iterate keys in MRU to LRU order | O(n) |
//!
//! ## Use Cases
//!
//! - **ARC policy**: Track B1 (recently evicted once) and B2 (recently evicted twice)
//! - **2Q policy**: Track ghost entries from A1out queue
//! - **Adaptive tuning**: Detect re-references to recently evicted keys
//!
//! ## Example Usage
//!
//! ```
//! use cachekit::ds::GhostList;
//!
//! // Track last 100 evicted keys
//! let mut ghost = GhostList::new(100);
//!
//! // Record evicted keys
//! ghost.record("page_1");
//! ghost.record("page_2");
//! ghost.record("page_3");
//!
//! // Check if a key was recently evicted (ghost hit)
//! if ghost.contains(&"page_1") {
//!     // Key was recently evicted - consider increasing cache size
//!     println!("Ghost hit! Should have kept page_1");
//! }
//!
//! // Re-recording moves to MRU position
//! ghost.record("page_1");  // Now page_1 is most recent
//! ```
//!
//! ## Use Case: ARC-Style Adaptation
//!
//! ```
//! use cachekit::ds::GhostList;
//!
//! struct AdaptiveCache {
//!     ghost_recent: GhostList<String>,   // B1: recently evicted from recency list
//!     ghost_frequent: GhostList<String>, // B2: recently evicted from frequency list
//!     p: usize,  // Adaptation parameter
//! }
//!
//! impl AdaptiveCache {
//!     fn new(capacity: usize) -> Self {
//!         Self {
//!             ghost_recent: GhostList::new(capacity),
//!             ghost_frequent: GhostList::new(capacity),
//!             p: capacity / 2,
//!         }
//!     }
//!
//!     fn on_miss(&mut self, key: String) {
//!         if self.ghost_recent.contains(&key) {
//!             // Hit in B1: increase recency preference
//!             self.p = self.p.saturating_add(1);
//!             self.ghost_recent.remove(&key);
//!         } else if self.ghost_frequent.contains(&key) {
//!             // Hit in B2: increase frequency preference
//!             self.p = self.p.saturating_sub(1);
//!             self.ghost_frequent.remove(&key);
//!         }
//!     }
//! }
//!
//! let mut cache = AdaptiveCache::new(100);
//! cache.ghost_recent.record("evicted_key".to_string());
//! cache.on_miss("evicted_key".to_string());  // Adapts based on ghost hit
//! ```
//!
//! ## Thread Safety
//!
//! `GhostList` is not thread-safe. For concurrent use, wrap in
//! `parking_lot::RwLock` or similar synchronization primitive.
//!
//! ## Security
//!
//! The default hasher is [`rustc_hash::FxBuildHasher`], chosen for speed on
//! trusted input. **`FxHash` is non-cryptographic and is not resistant to
//! hash-flooding / HashDoS attacks.** If a `GhostList` may observe keys
//! derived from untrusted input (for example, cache keys sourced from
//! HTTP URLs, user IDs, or request parameters), callers should either:
//!
//! - construct it with a DoS-resistant hasher via
//!   [`GhostList::with_hasher`] / [`GhostList::with_capacity_and_hasher`]
//!   (e.g. [`std::collections::hash_map::RandomState`]), or
//! - preprocess keys into a form the attacker cannot control the hash of.
//!
//! `GhostList` also rejects pathologically large capacities. [`GhostList::new`]
//! silently clamps `capacity` to [`GhostList::MAX_CAPACITY`] to prevent a
//! single oversized construction from aborting the process with an allocator
//! error (for example, if `capacity` is derived from untrusted configuration).
//! Use [`GhostList::try_new`] to detect the clamp explicitly.
//!
//! ## Implementation Notes
//!
//! - Backed by [`IntrusiveList`] for O(1) reordering
//! - Keys are stored in both the list and index (requires `Clone`)
//! - Zero-capacity ghost lists are no-ops (record does nothing)
//! - `K`'s `Hash`, `Eq`, and `Clone` impls must be mutually consistent:
//!   `a == b` implies `hash(a) == hash(b)`, and `a.clone() == a`. Violating
//!   this contract can leave a permanent, unreachable node in the internal
//!   arena (memory leak for the lifetime of the ghost list).
//! - `debug_validate_invariants()` available in debug/test builds
//!

use rustc_hash::FxBuildHasher;
use std::collections::HashMap;
use std::hash::{BuildHasher, Hash};

use crate::ds::intrusive_list::IntrusiveList;
use crate::ds::slot_arena::SlotId;

/// Bounded recency list of keys (no values), typically for ARC-style ghost tracking.
///
/// Tracks recently evicted keys to detect when items should have been kept in cache.
/// When a "ghost hit" occurs (accessing a key in the ghost list), adaptive policies
/// can adjust their behavior.
///
/// # Type Parameters
///
/// - `K`: Key type, must be `Eq + Hash + Clone`
///
/// # Example
///
/// ```
/// use cachekit::ds::GhostList;
///
/// let mut ghost = GhostList::new(3);
///
/// // Record evicted keys
/// ghost.record("a");
/// ghost.record("b");
/// ghost.record("c");
/// assert_eq!(ghost.len(), 3);
///
/// // At capacity, oldest is evicted
/// ghost.record("d");
/// assert!(!ghost.contains(&"a"));  // "a" was evicted
/// assert!(ghost.contains(&"d"));   // "d" is now tracked
///
/// // Re-recording promotes to MRU
/// ghost.record("b");
/// ghost.record("e");
/// assert!(ghost.contains(&"b"));   // "b" survives (was promoted)
/// assert!(!ghost.contains(&"c"));  // "c" was LRU, evicted
/// ```
///
/// # Use Case: Detecting Thrashing
///
/// ```
/// use cachekit::ds::GhostList;
///
/// let mut ghost = GhostList::new(50);
/// let mut ghost_hits = 0;
///
/// // Simulate evictions and re-accesses
/// let evicted_keys = vec!["key_1", "key_2", "key_3"];
/// for key in &evicted_keys {
///     ghost.record(*key);
/// }
///
/// // Later, check if we're re-accessing evicted keys
/// let accessed = vec!["key_1", "key_5", "key_2"];
/// for key in &accessed {
///     if ghost.contains(key) {
///         ghost_hits += 1;
///         // Could signal need for larger cache
///     }
/// }
///
/// assert_eq!(ghost_hits, 2);  // key_1 and key_2 were ghost hits
/// ```
///
/// # Traits
///
/// Implements [`Clone`], [`PartialEq`], [`Eq`], [`Default`], [`Extend<K>`](Extend),
/// [`FromIterator<K>`](FromIterator), and [`IntoIterator`] (consuming and borrowed).
pub struct GhostList<K, S = FxBuildHasher> {
    list: IntrusiveList<K>,
    index: HashMap<K, SlotId, S>,
    capacity: usize,
}

impl<K, S> std::fmt::Debug for GhostList<K, S> {
    /// Prints only structural metadata (`capacity` and `len`) — **not** the
    /// stored keys.
    ///
    /// Cache keys in real deployments frequently embed user identifiers,
    /// session tokens, URLs with sensitive query strings, or other PII.
    /// Echoing the full key list into logs, panic messages, or crash
    /// reports via `{:?}` would turn a benign observability statement
    /// into an information-disclosure surface. Callers who genuinely need
    /// to inspect keys should use [`GhostList::iter`] or, in debug builds,
    /// [`GhostList::debug_snapshot_keys`] and format the result
    /// explicitly.
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("GhostList")
            .field("capacity", &self.capacity)
            .field("len", &self.list.len())
            .finish_non_exhaustive()
    }
}

impl<K, S> Clone for GhostList<K, S>
where
    K: Eq + Hash + Clone,
    S: BuildHasher + Clone,
{
    fn clone(&self) -> Self {
        let alloc = self.list.len().min(self.capacity);
        let mut new_list = IntrusiveList::with_capacity(alloc);
        let mut new_index = HashMap::with_capacity_and_hasher(alloc, self.index.hasher().clone());

        for (_, key) in self.list.iter_entries() {
            let id = new_list.push_back(key.clone());
            new_index.insert(key.clone(), id);
        }

        Self {
            list: new_list,
            index: new_index,
            capacity: self.capacity,
        }
    }
}

/// Iterator over keys in a [`GhostList`], yielding references in MRU to LRU order.
///
/// Created by [`GhostList::iter`].
///
/// # Example
///
/// ```
/// use cachekit::ds::GhostList;
///
/// let mut ghost = GhostList::new(3);
/// ghost.record("a");
/// ghost.record("b");
///
/// let mut iter = ghost.iter();
/// assert_eq!(iter.next(), Some(&"b"));
/// assert_eq!(iter.next(), Some(&"a"));
/// assert_eq!(iter.next(), None);
/// ```
pub struct Iter<'a, K> {
    inner: MapToKey<'a, K>,
}

type MapToKey<'a, K> = std::iter::Map<
    crate::ds::intrusive_list::IntrusiveListEntryIter<'a, K>,
    fn((SlotId, &'a K)) -> &'a K,
>;

impl<'a, K: std::fmt::Debug> std::fmt::Debug for Iter<'a, K> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("Iter").finish_non_exhaustive()
    }
}

impl<'a, K> Iterator for Iter<'a, K> {
    type Item = &'a K;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

impl<'a, K> ExactSizeIterator for Iter<'a, K> {}

impl<'a, K> std::iter::FusedIterator for Iter<'a, K> {}

/// Consuming iterator over keys in a [`GhostList`], yielding owned keys in MRU to LRU order.
///
/// Created by calling `.into_iter()` on a `GhostList`.
///
/// # Example
///
/// ```
/// use cachekit::ds::GhostList;
///
/// let mut ghost = GhostList::new(3);
/// ghost.record("a");
/// ghost.record("b");
///
/// let keys: Vec<_> = ghost.into_iter().collect();
/// assert_eq!(keys, vec!["b", "a"]);
/// ```
#[derive(Debug)]
pub struct IntoIter<K> {
    inner: std::vec::IntoIter<K>,
}

impl<K> Iterator for IntoIter<K> {
    type Item = K;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

impl<K> ExactSizeIterator for IntoIter<K> {}

impl<K> std::iter::FusedIterator for IntoIter<K> {}

impl<K, S> IntoIterator for GhostList<K, S>
where
    K: Eq + Hash + Clone,
    S: BuildHasher,
{
    type Item = K;
    type IntoIter = IntoIter<K>;

    /// Consumes the ghost list and yields keys in MRU to LRU order.
    fn into_iter(self) -> Self::IntoIter {
        let keys: Vec<K> = self.list.iter_entries().map(|(_, k)| k.clone()).collect();
        IntoIter {
            inner: keys.into_iter(),
        }
    }
}

impl<'a, K, S> IntoIterator for &'a GhostList<K, S>
where
    K: Eq + Hash + Clone,
    S: BuildHasher,
{
    type Item = &'a K;
    type IntoIter = Iter<'a, K>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<K, S> PartialEq for GhostList<K, S>
where
    K: Eq + Hash + Clone,
    S: BuildHasher,
{
    fn eq(&self, other: &Self) -> bool {
        self.capacity == other.capacity
            && self.len() == other.len()
            && self.iter().zip(other.iter()).all(|(a, b)| a == b)
    }
}

impl<K, S> Eq for GhostList<K, S>
where
    K: Eq + Hash + Clone,
    S: BuildHasher,
{
}

impl<K, S> Extend<K> for GhostList<K, S>
where
    K: Eq + Hash + Clone,
    S: BuildHasher,
{
    fn extend<I: IntoIterator<Item = K>>(&mut self, iter: I) {
        for key in iter {
            self.record(key);
        }
    }
}

impl<K, S> FromIterator<K> for GhostList<K, S>
where
    K: Eq + Hash + Clone,
    S: BuildHasher + Default,
{
    /// Collects keys into a ghost list whose capacity equals the number of unique keys.
    ///
    /// Duplicate keys are promoted rather than inserted twice, so the resulting
    /// length may be less than the iterator length.
    ///
    /// The capacity used during collection is clamped to
    /// [`GhostList::MAX_CAPACITY`], which protects against iterators that
    /// report a pathologically large `size_hint` lower bound.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let ghost: GhostList<&str> = ["a", "b", "c", "b"].into_iter().collect();
    /// assert_eq!(ghost.len(), 3);
    /// assert!(ghost.contains(&"a"));
    /// ```
    fn from_iter<I: IntoIterator<Item = K>>(iter: I) -> Self {
        let iter = iter.into_iter();
        let (lower, _) = iter.size_hint();
        // Cap the initial allocation to avoid a hostile `size_hint` triggering
        // an oversized preallocation (OOM DoS vector).
        let initial = lower.clamp(16, Self::MAX_CAPACITY);
        let mut ghost = Self::with_capacity_and_hasher(initial, S::default());
        for key in iter {
            ghost.record(key);
        }
        ghost.capacity = ghost.len();
        ghost
    }
}

impl<K> GhostList<K, FxBuildHasher>
where
    K: Eq + Hash + Clone,
{
    /// Creates a new ghost list with a maximum of `capacity` keys, using the
    /// default [`FxBuildHasher`].
    ///
    /// A capacity of 0 creates a no-op ghost list that ignores all records.
    ///
    /// `capacity` is silently clamped to [`Self::MAX_CAPACITY`] to prevent a
    /// single oversized construction from aborting the process with an
    /// allocator error when the value is derived from untrusted input. Use
    /// [`Self::try_new`] if you want to detect the clamp explicitly.
    ///
    /// **Security note:** the default hasher (`FxBuildHasher`) is fast but
    /// not DoS-resistant. When keys may be attacker-influenced, construct
    /// with [`Self::with_capacity_and_hasher`] using
    /// [`std::collections::hash_map::RandomState`] or another
    /// cryptographically-randomised hasher instead. See the
    /// [module-level security notes](self).
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let ghost: GhostList<String> = GhostList::new(100);
    /// assert_eq!(ghost.capacity(), 100);
    /// assert!(ghost.is_empty());
    /// ```
    pub fn new(capacity: usize) -> Self {
        Self::with_capacity_and_hasher(capacity, FxBuildHasher)
    }

    /// Creates a new ghost list, returning an error if `capacity` exceeds
    /// [`Self::MAX_CAPACITY`].
    ///
    /// Prefer this over [`Self::new`] when `capacity` is user-supplied and
    /// you want to reject oversized requests rather than silently clamp.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let ghost: GhostList<String> = GhostList::try_new(100).unwrap();
    /// assert_eq!(ghost.capacity(), 100);
    ///
    /// assert!(GhostList::<String>::try_new(usize::MAX).is_err());
    /// ```
    pub fn try_new(capacity: usize) -> Result<Self, CapacityOverflowError> {
        Self::try_with_capacity_and_hasher(capacity, FxBuildHasher)
    }
}

/// Returned by [`GhostList::try_new`] and
/// [`GhostList::try_with_capacity_and_hasher`] when the requested capacity
/// exceeds [`GhostList::MAX_CAPACITY`].
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct CapacityOverflowError {
    /// Capacity requested by the caller.
    pub requested: usize,
    /// Hard maximum enforced by [`GhostList`].
    pub max: usize,
}

impl std::fmt::Display for CapacityOverflowError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(
            f,
            "GhostList capacity {} exceeds maximum of {}",
            self.requested, self.max
        )
    }
}

impl std::error::Error for CapacityOverflowError {}

impl<K, S> Default for GhostList<K, S>
where
    K: Eq + Hash + Clone,
    S: BuildHasher + Default,
{
    /// Creates an empty ghost list with zero capacity (no-op mode).
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let ghost: GhostList<String> = GhostList::default();
    /// assert_eq!(ghost.capacity(), 0);
    /// assert!(ghost.is_empty());
    /// ```
    fn default() -> Self {
        Self::with_capacity_and_hasher(0, S::default())
    }
}

impl<K, S> GhostList<K, S>
where
    K: Eq + Hash + Clone,
    S: BuildHasher,
{
    /// Upper bound on the capacity accepted by [`Self::new`],
    /// [`Self::with_hasher`], and [`Self::with_capacity_and_hasher`].
    ///
    /// Capacities larger than this are clamped. This is a defense-in-depth
    /// guard that prevents a single construction call from triggering an
    /// allocator abort when `capacity` is derived from untrusted input.
    ///
    /// The value is derived at compile time from `size_of::<K>()` and the
    /// target's pointer width, so the backing `Vec` allocations cannot
    /// themselves overflow `isize::MAX` bytes on any supported target, and
    /// the total byte footprint of a single `GhostList` cannot exceed a
    /// fixed platform-independent budget.
    ///
    /// The computation is:
    ///
    /// - A per-entry byte cost is assembled from two sources whose values
    ///   are exact at compile time for the chosen `K`:
    ///   - the intrusive-list arena's [`IntrusiveList::BYTES_PER_ENTRY`],
    ///     which bundles `Option<Node<K>>`, the per-slot generation, and a
    ///     worst-case free-list entry; and
    ///   - the hash-map's per-bucket cost of `size_of::<(K, SlotId)>() + 1`
    ///     (one control byte per bucket), multiplied by a worst-case
    ///     [load-factor inflation](#load-factor-multiplier) of `3`.
    /// - A byte budget is chosen as the smaller of:
    ///   - 16 GiB (a hard cap on any single construction), and
    ///   - `isize::MAX / 4` (leaving a 4× safety margin on smaller
    ///     pointer widths so that both backing allocations plus a
    ///     transient rehash-time doubling all fit in address space).
    /// - `MAX_CAPACITY` is `byte_budget / per_entry`.
    ///
    /// <a id="load-factor-multiplier"></a>
    /// **Load-factor multiplier.** `hashbrown` rounds the bucket count up
    /// to the next power of two sized for a 7/8 target load factor, so the
    /// backing allocation at capacity `N` can be as large as
    /// `(N * 8 / 7 + 1).next_power_of_two()` buckets. The worst-case
    /// inflation ratio is `16/7 ≈ 2.29` (achieved when `N * 8 / 7`
    /// narrowly exceeds a power of two); we round that up to `3` so the
    /// arithmetic stays integer and the clamp remains conservative against
    /// future load-factor changes in `hashbrown`.
    ///
    /// Worked examples (64-bit target, 16 GiB budget):
    ///
    /// - `K = u32`   → `MAX_CAPACITY` ≈ 135 M.
    /// - `K = [u8; 4096]` → `MAX_CAPACITY` ≈ 1.04 M.
    pub const MAX_CAPACITY: usize = {
        // `hashbrown` rounds bucket counts up to a power of two sized for a
        // 7/8 load factor. Worst-case blowup is 16/7; round to 3 so the
        // arithmetic is exact and the clamp stays conservative.
        const HASHMAP_LOAD_FACTOR_MULTIPLIER: usize = 3;

        // Exact, compile-time-known per-entry footprint of each container.
        // These are sourced directly from the backing types' layouts so
        // they track any future change to `Node<K>`, `SlotId`, or
        // `hashbrown`'s bucket format.
        let list_per_entry = IntrusiveList::<K>::BYTES_PER_ENTRY;
        let bucket_bytes = std::mem::size_of::<(K, SlotId)>().saturating_add(1);
        let index_per_entry = bucket_bytes.saturating_mul(HASHMAP_LOAD_FACTOR_MULTIPLIER);
        let per_entry = list_per_entry.saturating_add(index_per_entry);

        // Hard ceiling on any single construction: 16 GiB. Anything larger
        // than this is almost certainly a misconfiguration or adversarial
        // input — legitimate ghost lists are 6+ orders of magnitude smaller.
        // Compute in u64 so the literal fits on 32-bit targets, then
        // saturate back into usize.
        let sixteen_gib_u64: u64 = 16 * 1024 * 1024 * 1024;
        let sixteen_gib: usize = if sixteen_gib_u64 <= usize::MAX as u64 {
            sixteen_gib_u64 as usize
        } else {
            usize::MAX
        };

        // Address-space-relative budget: 1/4 of `isize::MAX` so that both
        // the arena and the hash map can be resident simultaneously and
        // still briefly double their backing storage during a rehash
        // without exhausting address space. Matters on 32-bit.
        let isize_quarter = (isize::MAX as usize) / 4;

        let byte_budget = if sixteen_gib < isize_quarter {
            sixteen_gib
        } else {
            isize_quarter
        };

        byte_budget / if per_entry == 0 { 1 } else { per_entry }
    };

    /// Creates a new ghost list with the given hasher and capacity clamped to
    /// [`Self::MAX_CAPACITY`].
    ///
    /// Use this constructor to install a DoS-resistant hasher (e.g.
    /// [`std::collections::hash_map::RandomState`]) when keys may be
    /// attacker-influenced; see the [module-level security notes](self).
    pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self {
        let capacity = capacity.min(Self::MAX_CAPACITY);
        Self {
            list: IntrusiveList::with_capacity(capacity),
            index: HashMap::with_capacity_and_hasher(capacity, hasher),
            capacity,
        }
    }

    /// Creates a new ghost list with the given hasher, returning an error if
    /// `capacity` exceeds [`Self::MAX_CAPACITY`].
    ///
    /// This is the fallible counterpart to [`Self::with_capacity_and_hasher`]
    /// and the hasher-aware counterpart to [`Self::try_new`]. Prefer it when
    /// `capacity` is user-supplied and you want to reject oversized requests
    /// rather than silently clamp — particularly in combination with a
    /// DoS-resistant hasher, where the caller is already handling untrusted
    /// input.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    /// use std::collections::hash_map::RandomState;
    ///
    /// let ghost: GhostList<String, RandomState> =
    ///     GhostList::try_with_capacity_and_hasher(100, RandomState::new()).unwrap();
    /// assert_eq!(ghost.capacity(), 100);
    ///
    /// assert!(
    ///     GhostList::<String, RandomState>::try_with_capacity_and_hasher(
    ///         usize::MAX,
    ///         RandomState::new(),
    ///     )
    ///     .is_err()
    /// );
    /// ```
    pub fn try_with_capacity_and_hasher(
        capacity: usize,
        hasher: S,
    ) -> Result<Self, CapacityOverflowError> {
        if capacity > Self::MAX_CAPACITY {
            return Err(CapacityOverflowError {
                requested: capacity,
                max: Self::MAX_CAPACITY,
            });
        }
        Ok(Self::with_capacity_and_hasher(capacity, hasher))
    }

    /// Creates a new ghost list with the given hasher and zero capacity.
    ///
    /// The list is a no-op until further methods (there are none today) grow
    /// its capacity. Provided primarily for symmetry with
    /// [`std::collections::HashMap::with_hasher`].
    pub fn with_hasher(hasher: S) -> Self {
        Self::with_capacity_and_hasher(0, hasher)
    }

    /// Returns the configured capacity.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let ghost: GhostList<&str> = GhostList::new(50);
    /// assert_eq!(ghost.capacity(), 50);
    /// ```
    pub fn capacity(&self) -> usize {
        self.capacity
    }

    /// Returns the number of keys currently tracked.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let mut ghost = GhostList::new(10);
    /// assert_eq!(ghost.len(), 0);
    ///
    /// ghost.record("a");
    /// ghost.record("b");
    /// assert_eq!(ghost.len(), 2);
    ///
    /// // Re-recording same key doesn't increase length
    /// ghost.record("a");
    /// assert_eq!(ghost.len(), 2);
    /// ```
    pub fn len(&self) -> usize {
        self.list.len()
    }

    /// Returns `true` if there are no keys tracked.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let mut ghost: GhostList<&str> = GhostList::new(10);
    /// assert!(ghost.is_empty());
    ///
    /// ghost.record("key");
    /// assert!(!ghost.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.list.is_empty()
    }

    /// Returns `true` if `key` is present in the ghost list.
    ///
    /// This is the "ghost hit" check used by adaptive policies.
    ///
    /// # Complexity
    ///
    /// O(1) average case, O(n) worst case due to hash collisions.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let mut ghost = GhostList::new(10);
    /// ghost.record("evicted_page");
    ///
    /// // Check for ghost hit
    /// if ghost.contains(&"evicted_page") {
    ///     println!("Ghost hit! Key was recently evicted.");
    /// }
    ///
    /// assert!(ghost.contains(&"evicted_page"));
    /// assert!(!ghost.contains(&"never_seen"));
    /// ```
    pub fn contains(&self, key: &K) -> bool {
        self.index.contains_key(key)
    }

    /// Records `key` as most-recently-seen, evicting the least recent if needed.
    ///
    /// If the key is already present, it is promoted to MRU position and returns `None`.
    /// If at capacity, the LRU key is evicted before inserting and returned.
    ///
    /// # Returns
    ///
    /// - `Some(evicted_key)` if a key was evicted to make room
    /// - `None` if the key was already present (promoted) or capacity not reached
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let mut ghost = GhostList::new(2);
    ///
    /// assert_eq!(ghost.record("a"), None);  // No eviction
    /// assert_eq!(ghost.record("b"), None);  // No eviction
    /// assert!(ghost.contains(&"a"));
    /// assert!(ghost.contains(&"b"));
    ///
    /// // At capacity: "a" is LRU, will be evicted
    /// assert_eq!(ghost.record("c"), Some("a"));  // Returns evicted key
    /// assert!(!ghost.contains(&"a"));  // Evicted
    /// assert!(ghost.contains(&"b"));
    /// assert!(ghost.contains(&"c"));
    ///
    /// // Re-recording "b" promotes it to MRU (no eviction)
    /// assert_eq!(ghost.record("b"), None);  // Already present
    /// assert_eq!(ghost.record("d"), Some("c"));  // Evicts "c"
    /// assert!(ghost.contains(&"b"));   // Survived (was MRU)
    /// assert!(!ghost.contains(&"c"));  // Evicted (was LRU)
    /// ```
    pub fn record(&mut self, key: K) -> Option<K> {
        if self.capacity == 0 {
            return None;
        }

        if let Some(&id) = self.index.get(&key) {
            self.list.move_to_front(id);
            return None;
        }

        // Reserve index capacity *before* mutating the list so that an
        // allocation failure here cannot leave the list containing a node
        // that the index never learns about (which would desynchronise
        // `list.len() == index.len()` and leak a slot permanently).
        self.index.reserve(1);

        let evicted = if self.list.len() >= self.capacity {
            let old_key = self.list.pop_back()?;
            self.index.remove(&old_key);
            Some(old_key)
        } else {
            None
        };

        let id = self.list.push_front(key.clone());
        self.index.insert(key, id);

        evicted
    }

    /// Records a batch of keys; returns number of keys processed.
    ///
    /// Note: All keys are processed (count equals input length), since `record` is infallible.
    /// Duplicates are automatically promoted to MRU rather than inserted twice.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let mut ghost = GhostList::new(10);
    ///
    /// let evicted = vec!["page_1", "page_2", "page_3"];
    /// let count = ghost.record_batch(&evicted);
    ///
    /// assert_eq!(count, 3);
    /// assert_eq!(ghost.len(), 3);
    /// ```
    pub fn record_batch<'a, I>(&mut self, keys: I) -> usize
    where
        I: IntoIterator<Item = &'a K>,
        K: 'a,
    {
        let mut count = 0;
        for key in keys {
            self.record(key.clone());
            count += 1;
        }
        count
    }

    /// Removes `key` from the ghost list; returns `true` if it was present.
    ///
    /// Typically called after a ghost hit to prevent double-counting.
    ///
    /// # Complexity
    ///
    /// O(1) average case, O(n) worst case due to hash collisions.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let mut ghost = GhostList::new(10);
    /// ghost.record("key");
    ///
    /// // Ghost hit: remove from ghost list
    /// assert!(ghost.remove(&"key"));
    /// assert!(!ghost.contains(&"key"));
    ///
    /// // Removing missing key returns false
    /// assert!(!ghost.remove(&"missing"));
    /// ```
    pub fn remove(&mut self, key: &K) -> bool {
        let id = match self.index.remove(key) {
            Some(id) => id,
            None => return false,
        };
        self.list.remove(id);
        true
    }

    /// Removes and returns the LRU (least recently used) key.
    ///
    /// Returns `None` if the ghost list is empty.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let mut ghost = GhostList::new(3);
    /// ghost.record("a");
    /// ghost.record("b");
    /// ghost.record("c");
    ///
    /// // "a" is LRU (inserted first, never promoted)
    /// assert_eq!(ghost.evict_lru(), Some("a"));
    /// assert!(!ghost.contains(&"a"));
    /// assert_eq!(ghost.len(), 2);
    ///
    /// assert_eq!(ghost.evict_lru(), Some("b"));
    /// assert_eq!(ghost.evict_lru(), Some("c"));
    /// assert_eq!(ghost.evict_lru(), None);  // Empty
    /// ```
    pub fn evict_lru(&mut self) -> Option<K> {
        let key = self.list.pop_back()?;
        self.index.remove(&key);
        Some(key)
    }

    /// Removes a batch of keys; returns number of keys actually removed.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let mut ghost = GhostList::new(10);
    /// ghost.record_batch(&["a", "b", "c"]);
    ///
    /// // Remove some keys (including one that doesn't exist)
    /// let removed = ghost.remove_batch(&["a", "c", "missing"]);
    ///
    /// assert_eq!(removed, 2);  // Only "a" and "c" were removed
    /// assert!(ghost.contains(&"b"));
    /// ```
    pub fn remove_batch<'a, I>(&mut self, keys: I) -> usize
    where
        I: IntoIterator<Item = &'a K>,
        K: 'a,
    {
        let mut removed = 0;
        for key in keys {
            if self.remove(key) {
                removed += 1;
            }
        }
        removed
    }

    /// Clears all tracked keys.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let mut ghost = GhostList::new(10);
    /// ghost.record("a");
    /// ghost.record("b");
    ///
    /// ghost.clear();
    /// assert!(ghost.is_empty());
    /// assert!(!ghost.contains(&"a"));
    /// ```
    pub fn clear(&mut self) {
        self.list.clear();
        self.index.clear();
    }

    /// Clears all tracked keys and shrinks internal storage.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let mut ghost = GhostList::new(100);
    /// let keys: Vec<_> = (0..50).map(|i| format!("key_{}", i)).collect();
    /// ghost.record_batch(&keys);
    ///
    /// ghost.clear_shrink();
    /// assert!(ghost.is_empty());
    /// ```
    pub fn clear_shrink(&mut self) {
        self.clear();
        self.list.clear_shrink();
        self.index.shrink_to_fit();
    }

    /// Returns a conservative lower-bound memory footprint in bytes.
    ///
    /// This estimate includes the struct size, intrusive list overhead,
    /// and HashMap entry storage. It underestimates actual memory usage by
    /// approximately 20-30% for small capacities due to:
    /// - HashMap control bytes and alignment padding
    /// - Key storage overhead in both structures
    /// - Internal capacity buffering
    ///
    /// Use this for rough capacity planning, not precise memory accounting.
    /// For accurate measurements, use a memory profiler.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let ghost: GhostList<u64> = GhostList::new(100);
    /// let bytes = ghost.approx_bytes();
    /// assert!(bytes > 0);
    ///
    /// // Approximate memory per entry
    /// let per_entry = bytes / 100.max(1);
    /// println!("~{} bytes per entry (lower bound)", per_entry);
    /// ```
    pub fn approx_bytes(&self) -> usize {
        // Saturating arithmetic here prevents a huge hash-map capacity (or a
        // large `K`) from silently wrapping to a nonsensical value — callers
        // sometimes use this for budget enforcement, where a wrapped result
        // is worse than a saturated one.
        let entry_bytes = self
            .index
            .capacity()
            .saturating_mul(std::mem::size_of::<(K, SlotId)>());
        std::mem::size_of::<Self>()
            .saturating_add(self.list.approx_bytes())
            .saturating_add(entry_bytes)
    }

    /// Returns an iterator over keys in MRU -> LRU order.
    ///
    /// Useful for observability and advanced use cases. However, prefer point lookups
    /// via `contains()` for performance-critical paths.
    ///
    /// # Complexity
    ///
    /// Iteration is O(n) where n is the number of keys tracked.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let mut ghost = GhostList::new(3);
    /// ghost.record("a");
    /// ghost.record("b");
    /// ghost.record("c");
    ///
    /// let keys: Vec<_> = ghost.iter().collect();
    /// assert_eq!(keys, vec![&"c", &"b", &"a"]);  // MRU to LRU
    /// ```
    pub fn iter(&self) -> Iter<'_, K> {
        fn extract_key<K>((_, key): (SlotId, &K)) -> &K {
            key
        }
        Iter {
            inner: self.list.iter_entries().map(extract_key),
        }
    }

    /// Returns an iterator over keys in MRU -> LRU order.
    ///
    /// This is a semantic alias for [`iter()`](Self::iter) that makes the intent clearer,
    /// matching the convention of `HashMap::keys()`.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let mut ghost = GhostList::new(3);
    /// ghost.record("a");
    /// ghost.record("b");
    ///
    /// // More explicit than iter()
    /// for key in ghost.keys() {
    ///     println!("Ghost entry: {}", key);
    /// }
    /// ```
    pub fn keys(&self) -> Iter<'_, K> {
        self.iter()
    }

    #[cfg(any(test, debug_assertions))]
    /// Returns keys in MRU -> LRU order (requires `K: Clone`).
    pub fn debug_snapshot_keys(&self) -> Vec<K>
    where
        K: Clone,
    {
        self.list
            .iter_entries()
            .map(|(_, key)| key.clone())
            .collect()
    }

    #[cfg(any(test, debug_assertions))]
    /// Returns a reference to the LRU (least recently used) key, if any.
    ///
    /// Useful for debugging and observability.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let mut ghost = GhostList::new(3);
    /// ghost.record("a");
    /// ghost.record("b");
    /// ghost.record("c");
    ///
    /// assert_eq!(ghost.debug_peek_lru(), Some(&"a"));
    /// ```
    pub fn debug_peek_lru(&self) -> Option<&K> {
        self.list.iter_entries().last().map(|(_, k)| k)
    }

    #[cfg(any(test, debug_assertions))]
    /// Returns a reference to the MRU (most recently used) key, if any.
    ///
    /// Useful for debugging and observability.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::GhostList;
    ///
    /// let mut ghost = GhostList::new(3);
    /// ghost.record("a");
    /// ghost.record("b");
    /// ghost.record("c");
    ///
    /// assert_eq!(ghost.debug_peek_mru(), Some(&"c"));
    /// ```
    pub fn debug_peek_mru(&self) -> Option<&K> {
        self.list.iter_entries().next().map(|(_, k)| k)
    }

    #[cfg(any(test, debug_assertions))]
    /// Returns `SlotId`s in MRU to LRU order, useful for snapshot-based testing.
    pub fn debug_snapshot_ids(&self) -> Vec<SlotId> {
        self.list.iter_ids().collect()
    }

    #[cfg(any(test, debug_assertions))]
    /// Returns `SlotId`s sorted by internal index for deterministic comparisons.
    pub fn debug_snapshot_ids_sorted(&self) -> Vec<SlotId> {
        let mut ids: Vec<_> = self.list.iter_ids().collect();
        ids.sort_by_key(|id| id.index());
        ids
    }

    #[cfg(any(test, debug_assertions))]
    /// Returns keys ordered by internal `SlotId` index for deterministic comparisons.
    pub fn debug_snapshot_keys_sorted(&self) -> Vec<K>
    where
        K: Clone,
    {
        let mut ids: Vec<_> = self.list.iter_ids().collect();
        ids.sort_by_key(|id| id.index());
        ids.into_iter()
            .filter_map(|id| self.list.get(id).cloned())
            .collect()
    }

    #[cfg(any(test, debug_assertions))]
    /// Asserts that all internal invariants hold.
    ///
    /// # Panics
    ///
    /// Panics if the list length and index length diverge, the length exceeds
    /// capacity, or any index entry points to a missing slot.
    pub fn debug_validate_invariants(&self) {
        assert_eq!(self.list.len(), self.index.len());
        assert!(self.list.len() <= self.capacity);
        if self.capacity == 0 {
            assert!(self.list.is_empty());
        }
        for &id in self.index.values() {
            assert!(self.list.contains(id));
        }
    }
}

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

    #[test]
    fn ghost_list_records_and_evictions() {
        let mut ghost = GhostList::new(2);
        ghost.record("a");
        ghost.record("b");
        assert!(ghost.contains(&"a"));
        assert!(ghost.contains(&"b"));

        ghost.record("a");
        ghost.record("c");

        assert!(ghost.contains(&"a"));
        assert!(ghost.contains(&"c"));
        assert!(!ghost.contains(&"b"));
    }

    #[test]
    fn ghost_list_zero_capacity_is_noop() {
        let mut ghost = GhostList::new(0);
        ghost.record("a");
        ghost.record("b");
        assert!(ghost.is_empty());
        assert_eq!(ghost.len(), 0);
        assert!(!ghost.contains(&"a"));
        assert!(!ghost.contains(&"b"));
    }

    #[test]
    fn ghost_list_record_existing_moves_to_front() {
        let mut ghost = GhostList::new(3);
        ghost.record("a");
        ghost.record("b");
        ghost.record("c");
        assert!(ghost.contains(&"a"));
        assert!(ghost.contains(&"b"));
        assert!(ghost.contains(&"c"));

        ghost.record("a");
        ghost.record("d");

        assert!(ghost.contains(&"a"));
        assert!(!ghost.contains(&"b"));
        assert!(ghost.contains(&"c"));
        assert!(ghost.contains(&"d"));
    }

    #[test]
    fn ghost_list_remove_existing_and_missing() {
        let mut ghost = GhostList::new(2);
        ghost.record("a");
        ghost.record("b");
        assert!(ghost.remove(&"a"));
        assert!(!ghost.contains(&"a"));
        assert_eq!(ghost.len(), 1);

        assert!(!ghost.remove(&"missing"));
        assert_eq!(ghost.len(), 1);
    }

    #[test]
    fn ghost_list_clear_resets_state() {
        let mut ghost = GhostList::new(2);
        ghost.record("a");
        ghost.record("b");
        ghost.clear();

        assert!(ghost.is_empty());
        assert_eq!(ghost.len(), 0);
        assert!(!ghost.contains(&"a"));
        assert!(!ghost.contains(&"b"));
    }

    #[test]
    fn ghost_list_debug_invariants_hold() {
        let mut ghost = GhostList::new(2);
        ghost.record("a");
        ghost.record("b");
        ghost.record("a");
        ghost.debug_validate_invariants();
    }

    #[test]
    fn ghost_list_debug_snapshots() {
        let mut ghost = GhostList::new(2);
        ghost.record("a");
        ghost.record("b");
        let keys = ghost.debug_snapshot_keys();
        let ids = ghost.debug_snapshot_ids();
        assert_eq!(keys.len(), 2);
        assert_eq!(ids.len(), 2);
        assert_eq!(ghost.debug_snapshot_ids_sorted().len(), 2);
        assert_eq!(ghost.debug_snapshot_keys_sorted().len(), 2);
    }

    #[test]
    fn ghost_list_batch_ops() {
        let mut ghost = GhostList::new(3);
        assert_eq!(ghost.record_batch(&["a", "b", "c"]), 3);
        assert_eq!(ghost.remove_batch(&["b", "d"]), 1);
        assert!(ghost.contains(&"a"));
        assert!(ghost.contains(&"c"));
        assert!(!ghost.contains(&"b"));
    }

    #[test]
    fn ghost_list_iter() {
        let mut ghost = GhostList::new(5);
        ghost.record("a");
        ghost.record("b");
        ghost.record("c");

        let keys: Vec<_> = ghost.iter().cloned().collect();
        assert_eq!(keys, vec!["c", "b", "a"]); // MRU to LRU

        // Verify iterator works on empty list
        ghost.clear();
        assert_eq!(ghost.iter().count(), 0);
    }

    #[test]
    fn ghost_list_debug_peek_lru_mru() {
        let mut ghost = GhostList::new(3);
        assert_eq!(ghost.debug_peek_lru(), None);
        assert_eq!(ghost.debug_peek_mru(), None);

        ghost.record("a");
        assert_eq!(ghost.debug_peek_lru(), Some(&"a"));
        assert_eq!(ghost.debug_peek_mru(), Some(&"a"));

        ghost.record("b");
        ghost.record("c");
        assert_eq!(ghost.debug_peek_lru(), Some(&"a")); // Oldest
        assert_eq!(ghost.debug_peek_mru(), Some(&"c")); // Newest

        // Promote "a" to MRU
        assert_eq!(ghost.record("a"), None); // No eviction (already present)
        assert_eq!(ghost.debug_peek_lru(), Some(&"b"));
        assert_eq!(ghost.debug_peek_mru(), Some(&"a"));
    }

    #[test]
    fn ghost_list_record_returns_evicted() {
        let mut ghost = GhostList::new(2);

        // No eviction when capacity not reached
        assert_eq!(ghost.record("a"), None);
        assert_eq!(ghost.record("b"), None);
        assert_eq!(ghost.len(), 2);

        // Eviction when at capacity
        assert_eq!(ghost.record("c"), Some("a")); // "a" was LRU
        assert!(!ghost.contains(&"a"));
        assert!(ghost.contains(&"b"));
        assert!(ghost.contains(&"c"));

        // Re-recording existing key returns None (no eviction)
        assert_eq!(ghost.record("b"), None);
        assert_eq!(ghost.record("d"), Some("c")); // "c" was LRU

        // Zero-capacity ghost list never evicts
        let mut zero_ghost = GhostList::new(0);
        assert_eq!(zero_ghost.record("x"), None);
        assert!(zero_ghost.is_empty());
    }

    #[test]
    fn ghost_list_keys_alias() {
        let mut ghost = GhostList::new(3);
        ghost.record("a");
        ghost.record("b");
        ghost.record("c");

        // keys() should work identically to iter()
        let keys_via_keys: Vec<_> = ghost.keys().cloned().collect();
        let keys_via_iter: Vec<_> = ghost.iter().cloned().collect();
        assert_eq!(keys_via_keys, keys_via_iter);
        assert_eq!(keys_via_keys, vec!["c", "b", "a"]);
    }

    #[test]
    fn ghost_list_default() {
        let ghost: GhostList<String> = GhostList::default();
        assert_eq!(ghost.capacity(), 0);
        assert!(ghost.is_empty());
        assert_eq!(ghost.len(), 0);
    }

    #[test]
    fn ghost_list_clone() {
        let mut ghost = GhostList::new(3);
        ghost.record("a");
        ghost.record("b");
        ghost.record("c");

        let cloned = ghost.clone();
        assert_eq!(cloned.len(), ghost.len());
        assert_eq!(cloned.capacity(), ghost.capacity());
        assert!(cloned.contains(&"a"));
        assert!(cloned.contains(&"b"));
        assert!(cloned.contains(&"c"));

        // Verify they are independent
        ghost.record("d");
        assert!(ghost.contains(&"d"));
        assert!(!cloned.contains(&"d"));
    }

    // -------------------------------------------------------------------------
    // IntoIterator (consuming)
    // -------------------------------------------------------------------------

    #[test]
    fn ghost_list_into_iter_yields_mru_to_lru() {
        let mut ghost = GhostList::new(3);
        ghost.record("a");
        ghost.record("b");
        ghost.record("c");

        let keys: Vec<_> = ghost.into_iter().collect();
        assert_eq!(keys, vec!["c", "b", "a"]);
    }

    #[test]
    fn ghost_list_into_iter_empty() {
        let ghost: GhostList<&str> = GhostList::new(5);
        let keys: Vec<_> = ghost.into_iter().collect();
        assert!(keys.is_empty());
    }

    #[test]
    fn ghost_list_into_iter_size_hint() {
        let mut ghost = GhostList::new(4);
        ghost.record("a");
        ghost.record("b");
        ghost.record("c");

        let iter = ghost.into_iter();
        assert_eq!(iter.size_hint(), (3, Some(3)));
    }

    #[test]
    fn ghost_list_into_iter_exact_size() {
        let mut ghost = GhostList::new(3);
        ghost.record("x");
        ghost.record("y");

        let mut iter = ghost.into_iter();
        assert_eq!(iter.len(), 2);
        iter.next();
        assert_eq!(iter.len(), 1);
        iter.next();
        assert_eq!(iter.len(), 0);
    }

    // -------------------------------------------------------------------------
    // IntoIterator (borrowed, &GhostList)
    // -------------------------------------------------------------------------

    #[test]
    fn ghost_list_ref_into_iter_yields_mru_to_lru() {
        let mut ghost = GhostList::new(3);
        ghost.record("a");
        ghost.record("b");
        ghost.record("c");

        let keys: Vec<_> = (&ghost).into_iter().cloned().collect();
        assert_eq!(keys, vec!["c", "b", "a"]);
        // Ghost list is still usable after borrowed iteration
        assert_eq!(ghost.len(), 3);
    }

    #[test]
    fn ghost_list_ref_into_iter_via_for_loop() {
        let mut ghost = GhostList::new(3);
        ghost.record(1u32);
        ghost.record(2u32);
        ghost.record(3u32);

        let mut seen = Vec::new();
        for key in &ghost {
            seen.push(*key);
        }
        assert_eq!(seen, vec![3u32, 2, 1]); // MRU to LRU
    }

    // -------------------------------------------------------------------------
    // PartialEq / Eq
    // -------------------------------------------------------------------------

    #[test]
    fn ghost_list_equal_same_content_and_capacity() {
        let mut a = GhostList::new(3);
        a.record("x");
        a.record("y");

        let mut b = GhostList::new(3);
        b.record("x");
        b.record("y");

        assert_eq!(a, b);
    }

    #[test]
    fn ghost_list_not_equal_different_order() {
        let mut a = GhostList::new(3);
        a.record("x");
        a.record("y");

        let mut b = GhostList::new(3);
        b.record("y");
        b.record("x");

        // Both contain the same keys but in different MRU order
        assert_ne!(a, b);
    }

    #[test]
    fn ghost_list_not_equal_different_capacity() {
        let mut a = GhostList::new(3);
        a.record("x");

        let mut b = GhostList::new(5);
        b.record("x");

        assert_ne!(a, b);
    }

    #[test]
    fn ghost_list_not_equal_different_content() {
        let mut a = GhostList::new(3);
        a.record("x");
        a.record("y");

        let mut b = GhostList::new(3);
        b.record("x");
        b.record("z");

        assert_ne!(a, b);
    }

    #[test]
    fn ghost_list_equal_empty_lists_same_capacity() {
        let a: GhostList<&str> = GhostList::new(10);
        let b: GhostList<&str> = GhostList::new(10);
        assert_eq!(a, b);
    }

    #[test]
    fn ghost_list_partial_eq_is_reflexive() {
        let mut ghost = GhostList::new(3);
        ghost.record("a");
        ghost.record("b");
        assert_eq!(ghost, ghost.clone());
    }

    // -------------------------------------------------------------------------
    // Extend
    // -------------------------------------------------------------------------

    #[test]
    fn ghost_list_extend_records_all_keys() {
        let mut ghost = GhostList::new(5);
        ghost.extend(["a", "b", "c"]);

        assert_eq!(ghost.len(), 3);
        assert!(ghost.contains(&"a"));
        assert!(ghost.contains(&"b"));
        assert!(ghost.contains(&"c"));
    }

    #[test]
    fn ghost_list_extend_respects_capacity() {
        let mut ghost = GhostList::new(2);
        ghost.extend(["a", "b", "c", "d"]);

        // Capacity is 2; oldest keys evicted
        assert_eq!(ghost.len(), 2);
        assert!(ghost.contains(&"c"));
        assert!(ghost.contains(&"d"));
        assert!(!ghost.contains(&"a"));
        assert!(!ghost.contains(&"b"));
    }

    #[test]
    fn ghost_list_extend_promotes_existing_keys() {
        let mut ghost = GhostList::new(3);
        ghost.record("a");
        ghost.record("b");
        ghost.record("c");

        // Extending with existing key "a" promotes it to MRU
        ghost.extend(["a"]);
        let keys: Vec<_> = ghost.iter().cloned().collect();
        assert_eq!(keys[0], "a"); // "a" is now MRU
        assert_eq!(ghost.len(), 3);
    }

    #[test]
    fn ghost_list_extend_from_iterator() {
        let mut ghost = GhostList::new(10);
        let keys = vec!["p", "q", "r", "s"];
        ghost.extend(keys);

        assert_eq!(ghost.len(), 4);
        assert!(ghost.contains(&"p"));
        assert!(ghost.contains(&"s"));
    }

    // -------------------------------------------------------------------------
    // evict_lru
    // -------------------------------------------------------------------------

    #[test]
    fn ghost_list_evict_lru_removes_oldest() {
        let mut ghost = GhostList::new(3);
        ghost.record("a");
        ghost.record("b");
        ghost.record("c");

        // LRU is "a" (inserted first, never promoted)
        assert_eq!(ghost.evict_lru(), Some("a"));
        assert!(!ghost.contains(&"a"));
        assert_eq!(ghost.len(), 2);

        assert_eq!(ghost.evict_lru(), Some("b"));
        assert_eq!(ghost.evict_lru(), Some("c"));
        assert_eq!(ghost.evict_lru(), None); // Empty
        assert!(ghost.is_empty());
    }

    #[test]
    fn ghost_list_evict_lru_empty_returns_none() {
        let mut ghost: GhostList<&str> = GhostList::new(5);
        assert_eq!(ghost.evict_lru(), None);
    }

    #[test]
    fn ghost_list_evict_lru_after_promotion() {
        let mut ghost = GhostList::new(3);
        ghost.record("a");
        ghost.record("b");
        ghost.record("c");

        // Promote "a" to MRU — now "b" is LRU
        ghost.record("a");
        assert_eq!(ghost.evict_lru(), Some("b"));
        assert!(ghost.contains(&"a"));
        assert!(ghost.contains(&"c"));
    }

    // -------------------------------------------------------------------------
    // Debug impls
    // -------------------------------------------------------------------------

    #[test]
    fn ghost_list_iter_debug() {
        let mut ghost = GhostList::new(3);
        ghost.record("a");
        ghost.record("b");

        let iter = ghost.iter();
        let debug_str = format!("{:?}", iter);
        assert!(debug_str.contains("Iter"));
    }

    #[test]
    fn ghost_list_into_iter_debug() {
        let mut ghost = GhostList::new(3);
        ghost.record("a");

        let iter = ghost.into_iter();
        let debug_str = format!("{:?}", iter);
        assert!(debug_str.contains("IntoIter"));
    }

    #[test]
    fn ghost_list_debug_does_not_leak_keys() {
        // Simulate a "sensitive" key value. The Debug impl for GhostList
        // must NOT echo this substring, otherwise `{:?}` becomes an
        // information-disclosure surface when the list is logged.
        const SECRET: &str = "session-token-deadbeef-SECRET";

        let mut ghost = GhostList::new(4);
        ghost.record(SECRET.to_string());
        ghost.record("other-key".to_string());

        let debug_str = format!("{:?}", ghost);

        assert!(
            !debug_str.contains("SECRET"),
            "GhostList Debug must not echo stored keys; got: {debug_str}"
        );
        assert!(
            !debug_str.contains("other-key"),
            "GhostList Debug must not echo stored keys; got: {debug_str}"
        );

        // Structural metadata is fine (and useful).
        assert!(debug_str.contains("GhostList"));
        assert!(debug_str.contains("capacity"));
        assert!(debug_str.contains("len"));
    }

    #[test]
    fn ghost_list_debug_works_for_non_debug_keys() {
        // Regression: the Debug impl must NOT require `K: Debug`. Verified
        // by constructing a ghost list of a `K` that is deliberately not
        // `Debug` and still formatting it.
        #[derive(Clone, Eq, PartialEq, Hash)]
        struct NoDebug(u32);

        let mut ghost = GhostList::new(2);
        ghost.record(NoDebug(1));
        ghost.record(NoDebug(2));

        let s = format!("{:?}", ghost);
        assert!(s.contains("GhostList"));
    }

    // -------------------------------------------------------------------------
    // Security hardening
    // -------------------------------------------------------------------------
    //
    // Some tests below would materialize a `GhostList` at [`GhostList::MAX_CAPACITY`].
    // On a 64-bit target that can require backing storage on the order of the 16 GiB
    // construction budget, so they are `#[ignore]` and are meant for high-memory
    // machines: `cargo test ghost_list_ -- --ignored --test-threads=1`

    #[test]
    #[ignore = "allocates up to 16 GiB; run: cargo test ghost_list_new_clamps_oversized_capacity -- --ignored --test-threads=1"]
    fn ghost_list_new_clamps_oversized_capacity() {
        let ghost: GhostList<u32> = GhostList::new(usize::MAX);
        assert_eq!(
            ghost.capacity(),
            GhostList::<u32>::MAX_CAPACITY,
            "new() must clamp to MAX_CAPACITY to avoid OOM-abort DoS"
        );
        assert!(ghost.is_empty());
    }

    #[test]
    fn ghost_list_max_capacity_respects_byte_budget() {
        // Validate the robust per-entry invariant used by `MAX_CAPACITY`:
        // at the clamp boundary, the worst-case footprint of the arena
        // plus the hash map (including `hashbrown`'s power-of-two bucket
        // inflation) must still fit inside both the 16 GiB construction
        // ceiling and the 1/4-of-`isize::MAX` address-space budget.
        //
        // We recompute `per_entry` here from the same primitives that
        // `MAX_CAPACITY` uses, so a regression in either the constant or
        // the formula will trip this assertion. Exercise it across several
        // key sizes so that a fat-key OOM (as seen with 4 KiB keys) cannot
        // silently reappear.
        fn assert_fits<K: Clone + Eq + Hash>() {
            let max = GhostList::<K>::MAX_CAPACITY;
            let list_per_entry = IntrusiveList::<K>::BYTES_PER_ENTRY;
            let bucket_bytes = std::mem::size_of::<(K, SlotId)>() + 1;
            // Matches `HASHMAP_LOAD_FACTOR_MULTIPLIER` in `MAX_CAPACITY`.
            let index_per_entry = bucket_bytes * 3;
            let per_entry = list_per_entry + index_per_entry;

            let sixteen_gib: usize = 16 * 1024 * 1024 * 1024;
            let isize_quarter = (isize::MAX as usize) / 4;
            let budget = sixteen_gib.min(isize_quarter);

            let footprint = max.checked_mul(per_entry).unwrap_or_else(|| {
                panic!("MAX_CAPACITY overflow for K={}", std::any::type_name::<K>())
            });
            assert!(
                footprint <= budget,
                "MAX_CAPACITY footprint {footprint} exceeds budget {budget} for K={}",
                std::any::type_name::<K>(),
            );
        }

        assert_fits::<u8>();
        assert_fits::<u32>();
        assert_fits::<u64>();
        assert_fits::<[u8; 64]>();
        assert_fits::<[u8; 4096]>();
    }

    #[test]
    fn ghost_list_max_capacity_shrinks_for_large_keys() {
        // A 4 KiB key type must produce a MUCH smaller MAX_CAPACITY than a
        // 4-byte key type; otherwise we'd OOM-abort on constructing
        // `new(usize::MAX)` for fat keys.
        #[repr(C)]
        #[derive(Clone, Eq, PartialEq, Hash)]
        struct Fat([u8; 4096]);

        let small_cap = GhostList::<u32>::MAX_CAPACITY;
        let fat_cap = GhostList::<Fat>::MAX_CAPACITY;
        assert!(
            fat_cap < small_cap,
            "MAX_CAPACITY must scale down with size_of::<K>(): \
             fat_cap={fat_cap} small_cap={small_cap}"
        );
    }

    #[test]
    #[ignore = "allocates multiple GiB; run: cargo test ghost_list_max_capacity_fat_key_materializes_at_clamp -- --ignored --test-threads=1"]
    fn ghost_list_max_capacity_fat_key_materializes_at_clamp() {
        #[repr(C)]
        #[derive(Clone, Eq, PartialEq, Hash)]
        struct Fat([u8; 4096]);

        let fat_cap = GhostList::<Fat>::MAX_CAPACITY;
        let ghost: GhostList<Fat> = GhostList::new(usize::MAX);
        assert_eq!(ghost.capacity(), fat_cap);
    }

    #[test]
    fn ghost_list_try_new_rejects_oversized_capacity() {
        let err = GhostList::<u32>::try_new(usize::MAX).unwrap_err();
        assert_eq!(err.requested, usize::MAX);
        assert_eq!(err.max, GhostList::<u32>::MAX_CAPACITY);

        // Succeeds well below the construction ceiling (full `MAX_CAPACITY` is
        // covered in an ignored test — it can allocate on the order of 16 GiB).
        const N: usize = 65_536;
        let ok = GhostList::<u32>::try_new(N).unwrap();
        assert_eq!(ok.capacity(), N);
    }

    #[test]
    #[ignore = "allocates up to 16 GiB; run: cargo test ghost_list_try_new_succeeds_at_max_capacity -- --ignored --test-threads=1"]
    fn ghost_list_try_new_succeeds_at_max_capacity() {
        let ok = GhostList::<u32>::try_new(GhostList::<u32>::MAX_CAPACITY).unwrap();
        assert_eq!(ok.capacity(), GhostList::<u32>::MAX_CAPACITY);
    }

    #[test]
    fn ghost_list_try_with_capacity_and_hasher_rejects_oversized_capacity() {
        use std::collections::hash_map::RandomState;

        // Mirrors `try_new`, but on the custom-hasher path a security-
        // conscious caller (e.g. using `RandomState` for DoS resistance)
        // can detect the clamp instead of silently losing capacity.
        type Gh = GhostList<u32, RandomState>;

        let err = Gh::try_with_capacity_and_hasher(usize::MAX, RandomState::new()).unwrap_err();
        assert_eq!(err.requested, usize::MAX);
        assert_eq!(err.max, Gh::MAX_CAPACITY);

        const N: usize = 65_536;
        let ok = Gh::try_with_capacity_and_hasher(N, RandomState::new()).unwrap();
        assert_eq!(ok.capacity(), N);

        // Zero capacity is always valid.
        let empty = Gh::try_with_capacity_and_hasher(0, RandomState::new()).unwrap();
        assert_eq!(empty.capacity(), 0);
        assert!(empty.is_empty());

        // Exactly at the boundary: MAX_CAPACITY + 1 must fail.
        if let Some(over) = Gh::MAX_CAPACITY.checked_add(1) {
            let err = Gh::try_with_capacity_and_hasher(over, RandomState::new()).unwrap_err();
            assert_eq!(err.requested, over);
        }
    }

    #[test]
    #[ignore = "allocates up to 16 GiB; run: cargo test ghost_list_try_with_capacity_and_hasher_succeeds_at_max_capacity -- --ignored --test-threads=1"]
    fn ghost_list_try_with_capacity_and_hasher_succeeds_at_max_capacity() {
        use std::collections::hash_map::RandomState;

        type Gh = GhostList<u32, RandomState>;
        let ok = Gh::try_with_capacity_and_hasher(Gh::MAX_CAPACITY, RandomState::new()).unwrap();
        assert_eq!(ok.capacity(), Gh::MAX_CAPACITY);
    }

    #[test]
    fn ghost_list_from_iter_clamps_hostile_size_hint() {
        struct HostileIter(usize);
        impl Iterator for HostileIter {
            type Item = u32;
            fn next(&mut self) -> Option<u32> {
                if self.0 == 0 {
                    None
                } else {
                    self.0 -= 1;
                    Some(self.0 as u32)
                }
            }
            fn size_hint(&self) -> (usize, Option<usize>) {
                // Report a pathological lower bound.
                (usize::MAX, None)
            }
        }

        // If `from_iter` honoured the hostile size_hint without clamping, this
        // would attempt to preallocate for usize::MAX entries and abort.
        let ghost: GhostList<u32> = HostileIter(3).collect();
        assert_eq!(ghost.len(), 3);
    }

    #[test]
    fn ghost_list_with_custom_hasher_is_dos_resistant() {
        use std::collections::hash_map::RandomState;

        let mut ghost: GhostList<u32, RandomState> =
            GhostList::with_capacity_and_hasher(4, RandomState::new());
        ghost.record(1);
        ghost.record(2);
        ghost.record(3);
        assert!(ghost.contains(&1));
        assert!(ghost.contains(&3));
        assert_eq!(ghost.len(), 3);
    }

    #[test]
    fn ghost_list_record_preserves_invariant_after_heavy_churn() {
        // Regression: record() previously mutated the list before reserving
        // hash-map capacity, so an allocation failure mid-insert could leak
        // a slot. With the pre-reserve fix, invariants must hold through
        // any number of inserts/evictions.
        let mut ghost = GhostList::new(8);
        for i in 0..1_000u32 {
            ghost.record(i);
            ghost.debug_validate_invariants();
        }
        assert_eq!(ghost.len(), 8);
    }

    #[test]
    fn ghost_list_approx_bytes_does_not_overflow_on_huge_capacity() {
        // Construct a ghost list whose index would overflow usize if
        // `capacity * size_of::<(K, SlotId)>` were computed without
        // saturating arithmetic. MAX_CAPACITY is already within safe bounds,
        // so the saturating path mostly matters for `index.capacity()` after
        // hash-map growth — but we still want to confirm the call never
        // panics or wraps.
        let ghost: GhostList<u64> = GhostList::new(1024);
        let bytes = ghost.approx_bytes();
        assert!(bytes > 0);
        assert!(bytes < usize::MAX / 2);
    }
}

#[cfg(test)]
mod property_tests {
    use super::*;
    use proptest::prelude::*;

    // =============================================================================
    // Property Tests - Core Invariants
    // =============================================================================

    proptest! {
        /// Property: Invariants hold after any sequence of operations
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_invariants_always_hold(
            capacity in 1usize..20,
            ops in prop::collection::vec((0u8..3, any::<u32>()), 0..50)
        ) {
            let mut ghost: GhostList<u32> = GhostList::new(capacity);

            for (op, key) in ops {
                match op % 3 {
                    0 => { ghost.record(key); }
                    1 => { ghost.remove(&key); }
                    2 => { let _ = ghost.contains(&key); }
                    _ => unreachable!(),
                }

                ghost.debug_validate_invariants();
            }
        }

        /// Property: len() never exceeds capacity
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_len_never_exceeds_capacity(
            capacity in 1usize..30,
            keys in prop::collection::vec(any::<u32>(), 0..100)
        ) {
            let mut ghost: GhostList<u32> = GhostList::new(capacity);

            for key in keys {
                ghost.record(key);
                prop_assert!(ghost.len() <= capacity);
            }
        }

        /// Property: Empty state is consistent
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_empty_state_consistent(
            capacity in 1usize..20,
            keys in prop::collection::vec(any::<u32>(), 1..20)
        ) {
            let mut ghost: GhostList<u32> = GhostList::new(capacity);

            for key in keys {
                ghost.record(key);
            }

            ghost.clear();

            prop_assert!(ghost.is_empty());
            prop_assert_eq!(ghost.len(), 0);
            prop_assert_eq!(ghost.capacity(), capacity);
        }
    }

    // =============================================================================
    // Property Tests - LRU Eviction Order
    // =============================================================================

    proptest! {
        /// Property: LRU eviction - oldest keys evicted first
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_lru_eviction_order(
            capacity in 2usize..10,
            keys in prop::collection::vec(0u32..50, 1..30)
        ) {
            let mut ghost: GhostList<u32> = GhostList::new(capacity);
            let mut reference: std::collections::VecDeque<u32> = std::collections::VecDeque::new();

            for key in keys {
                ghost.record(key);

                if let Some(pos) = reference.iter().position(|&k| k == key) {
                    reference.remove(pos);
                } else if reference.len() >= capacity {
                    reference.pop_back();
                }
                reference.push_front(key);
            }

            prop_assert_eq!(ghost.len(), reference.len());
            for &ref_key in &reference {
                prop_assert!(ghost.contains(&ref_key));
            }

            let snapshot = ghost.debug_snapshot_keys();
            prop_assert_eq!(snapshot, reference.iter().copied().collect::<Vec<_>>());

            ghost.debug_validate_invariants();
        }

        /// Property: Recording existing key doesn't increase length
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_rerecord_no_length_increase(
            capacity in 2usize..10,
            key in any::<u32>()
        ) {
            let mut ghost: GhostList<u32> = GhostList::new(capacity);

            ghost.record(key);
            let len_after_first = ghost.len();

            ghost.record(key);
            let len_after_second = ghost.len();

            prop_assert_eq!(len_after_first, len_after_second);
            prop_assert_eq!(len_after_first, 1);
        }
    }

    // =============================================================================
    // Property Tests - Promotion to MRU
    // =============================================================================

    proptest! {
        /// Property: Re-recording promotes to MRU position
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_rerecord_promotes_to_mru(
            capacity in 2usize..10,
            keys in prop::collection::vec(0u32..20, 2..10)
        ) {
            prop_assume!(keys.len() >= 2);
            let mut ghost: GhostList<u32> = GhostList::new(capacity);

            // Record keys
            for &key in &keys {
                ghost.record(key);
            }

            if ghost.is_empty() {
                return Ok(());
            }

            // Get snapshot to find a key that's in the list
            let snapshot = ghost.debug_snapshot_keys();
            if snapshot.is_empty() {
                return Ok(());
            }

            let promoted_key = snapshot[snapshot.len() - 1]; // Pick LRU key

            // Re-record to promote
            ghost.record(promoted_key);

            // Should now be at MRU position (index 0 in snapshot)
            let new_snapshot = ghost.debug_snapshot_keys();
            if !new_snapshot.is_empty() {
                prop_assert_eq!(new_snapshot[0], promoted_key);
            }
        }

        /// Property: Promoted keys survive longer than unpromoted
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_promoted_keys_survive_longer(
            capacity in 3usize..8,
            fill_keys in prop::collection::vec(0u32..10, 3..8)
        ) {
            prop_assume!(fill_keys.len() >= capacity);
            let mut ghost: GhostList<u32> = GhostList::new(capacity);

            // Fill to capacity with unique keys
            let mut unique = Vec::new();
            for &key in &fill_keys {
                if !unique.contains(&key) && unique.len() < capacity {
                    ghost.record(key);
                    unique.push(key);
                }
            }

            if unique.len() < capacity {
                return Ok(());
            }

            // Pick LRU key and promote it
            let snapshot = ghost.debug_snapshot_keys();
            let promoted_key = snapshot[snapshot.len() - 1];
            ghost.record(promoted_key);

            // Record enough new keys to cause evictions
            for i in 100..(100 + capacity - 1) {
                ghost.record(i as u32);
            }

            // Promoted key should still be present
            prop_assert!(ghost.contains(&promoted_key));
        }
    }

    // =============================================================================
    // Property Tests - Contains and Remove
    // =============================================================================

    proptest! {
        /// Property: recorded keys are present, removed keys are not
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_contains_after_record(
            capacity in 1usize..20,
            key in any::<u32>()
        ) {
            let mut ghost: GhostList<u32> = GhostList::new(capacity);

            ghost.record(key);
            prop_assert!(ghost.contains(&key));

            ghost.remove(&key);
            prop_assert!(!ghost.contains(&key));
        }

        /// Property: remove returns true only for present keys
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_remove_returns_correct_bool(
            capacity in 1usize..10,
            keys in prop::collection::vec(any::<u32>(), 1..20)
        ) {
            let mut ghost: GhostList<u32> = GhostList::new(capacity);

            for &key in &keys {
                ghost.record(key);
            }

            for &key in &keys {
                let was_present = ghost.contains(&key);
                let remove_result = ghost.remove(&key);

                if was_present {
                    prop_assert!(remove_result);
                    prop_assert!(!ghost.contains(&key));
                }

                // Removing again should return false
                prop_assert!(!ghost.remove(&key));
            }
        }
    }

    // =============================================================================
    // Property Tests - Clear Operations
    // =============================================================================

    proptest! {
        /// Property: clear resets to empty state
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_clear_resets_state(
            capacity in 1usize..20,
            keys in prop::collection::vec(any::<u32>(), 1..30)
        ) {
            let mut ghost: GhostList<u32> = GhostList::new(capacity);

            for key in keys {
                ghost.record(key);
            }

            ghost.clear();

            prop_assert!(ghost.is_empty());
            prop_assert_eq!(ghost.len(), 0);
            prop_assert_eq!(ghost.capacity(), capacity);
            ghost.debug_validate_invariants();
        }

        /// Property: clear_shrink behaves like clear
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_clear_shrink_same_as_clear(
            capacity in 1usize..20,
            keys in prop::collection::vec(any::<u32>(), 1..30)
        ) {
            let mut ghost1: GhostList<u32> = GhostList::new(capacity);
            let mut ghost2: GhostList<u32> = GhostList::new(capacity);

            for &key in &keys {
                ghost1.record(key);
                ghost2.record(key);
            }

            ghost1.clear();
            ghost2.clear_shrink();

            prop_assert_eq!(ghost1.len(), ghost2.len());
            prop_assert_eq!(ghost1.is_empty(), ghost2.is_empty());
            prop_assert_eq!(ghost1.capacity(), ghost2.capacity());
        }

        /// Property: usable after clear
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_usable_after_clear(
            capacity in 1usize..10,
            keys1 in prop::collection::vec(any::<u32>(), 1..20),
            keys2 in prop::collection::vec(any::<u32>(), 1..20)
        ) {
            let mut ghost: GhostList<u32> = GhostList::new(capacity);

            for key in keys1 {
                ghost.record(key);
            }

            ghost.clear();

            for &key in &keys2 {
                ghost.record(key);
            }

            let unique_keys2: std::collections::HashSet<_> = keys2.into_iter().collect();
            let expected_len = unique_keys2.len().min(capacity);
            prop_assert_eq!(ghost.len(), expected_len);
        }
    }

    // =============================================================================
    // Property Tests - Zero Capacity
    // =============================================================================

    proptest! {
        /// Property: zero capacity ghost list is always empty (no-op)
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_zero_capacity_always_empty(
            keys in prop::collection::vec(any::<u32>(), 0..30)
        ) {
            let mut ghost: GhostList<u32> = GhostList::new(0);

            for key in keys {
                ghost.record(key);
                prop_assert!(ghost.is_empty());
                prop_assert_eq!(ghost.len(), 0);
                prop_assert_eq!(ghost.capacity(), 0);
                prop_assert!(!ghost.contains(&key));
            }
        }
    }

    // =============================================================================
    // Property Tests - Batch Operations
    // =============================================================================

    proptest! {
        /// Property: record_batch records all keys
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_record_batch_records_all(
            capacity in 5usize..20,
            keys in prop::collection::vec(0u32..20, 1..10)
        ) {
            let mut ghost: GhostList<u32> = GhostList::new(capacity);

            let count = ghost.record_batch(&keys);

            prop_assert_eq!(count, keys.len());

            let unique_keys: std::collections::HashSet<_> = keys.into_iter().collect();
            let expected_len = unique_keys.len().min(capacity);
            prop_assert_eq!(ghost.len(), expected_len);
        }

        /// Property: remove_batch removes only present keys
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_remove_batch_only_present(
            capacity in 5usize..20,
            record_keys in prop::collection::vec(0u32..10, 1..10),
            remove_keys in prop::collection::vec(0u32..20, 1..10)
        ) {
            let mut ghost: GhostList<u32> = GhostList::new(capacity);

            ghost.record_batch(&record_keys);

            let removed = ghost.remove_batch(&remove_keys);

            let record_set: std::collections::HashSet<_> = record_keys.into_iter().collect();
            let remove_set: std::collections::HashSet<_> = remove_keys.into_iter().collect();

            // Count how many keys to remove were actually present
            let mut expected_removed = 0;
            for key in remove_set {
                if record_set.contains(&key) && !ghost.is_empty() {
                    expected_removed += 1;
                }
            }

            // removed count should match or be less (due to LRU evictions before removal)
            prop_assert!(removed <= expected_removed || removed <= record_set.len());
        }
    }

    // =============================================================================
    // Property Tests - Reference Implementation Equivalence
    // =============================================================================

    proptest! {
        /// Property: Behavior matches reference VecDeque implementation
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_matches_reference_implementation(
            capacity in 2usize..10,
            keys in prop::collection::vec(0u32..20, 0..30)
        ) {
            let mut ghost: GhostList<u32> = GhostList::new(capacity);
            let mut reference: std::collections::VecDeque<u32> = std::collections::VecDeque::new();

            for key in keys {
                // Update ghost list
                ghost.record(key);

                // Update reference implementation
                if let Some(pos) = reference.iter().position(|&k| k == key) {
                    reference.remove(pos);
                } else if reference.len() >= capacity {
                    reference.pop_back(); // Remove LRU
                }
                reference.push_front(key); // Add at MRU

                // Verify length matches
                prop_assert_eq!(ghost.len(), reference.len());

                // Verify all keys in reference are in ghost list
                for &ref_key in &reference {
                    prop_assert!(ghost.contains(&ref_key));
                }

                // Verify snapshot matches reference
                let snapshot = ghost.debug_snapshot_keys();
                prop_assert_eq!(snapshot.len(), reference.len());
                for (snap_key, ref_key) in snapshot.iter().zip(reference.iter()) {
                    prop_assert_eq!(snap_key, ref_key);
                }
            }
        }
    }
}