ftui_render/

spatial_hit_index.rs

#![forbid(unsafe_code)]

//! Spatial hit-test index with z-order support and dirty-rect caching.
//!
//! Provides O(1) average-case hit-test queries for thousands of widgets
//! by using uniform grid bucketing with z-order tracking.
//!
//! # Design
//!
//! Uses a hybrid approach:
//! - **Uniform grid**: Screen divided into cells (default 8x8 pixels each)
//! - **Bucket lists**: Each grid cell stores widget IDs that overlap it
//! - **Z-order tracking**: Widgets have explicit z-order; topmost wins on overlap
//! - **Dirty-rect cache**: Last hover result cached; invalidated on dirty regions
//!
//! # Invariants
//!
//! 1. Hit-test always returns topmost widget (highest z) at query point
//! 2. Ties broken by registration order (later = on top)
//! 3. Dirty regions force recomputation of affected buckets only
//! 4. No allocations on steady-state hit-test queries
//!
//! # Failure Modes
//!
//! - Buckets are unbounded `Vec`s: pathological overlap degrades queries to
//!   a per-bucket linear scan but never loses entries (there is no separate
//!   fallback path).
//! - `HitId::default()` (id 0) is reserved as the removed-entry sentinel;
//!   [`SpatialHitIndex::register`] rejects it.
//! - Re-registering an existing id replaces the previous entry.

use crate::frame::{HitData, HitId, HitRegion};
use ahash::AHashMap;
use ftui_core::geometry::Rect;

// ---------------------------------------------------------------------------
// Configuration
// ---------------------------------------------------------------------------

/// Configuration for the spatial hit index.
#[derive(Debug, Clone)]
pub struct SpatialHitConfig {
    /// Grid cell size in terminal cells (default: 8).
    /// Smaller = more memory, faster queries. Larger = less memory, slower queries.
    pub cell_size: u16,

    /// Maximum widgets per bucket before logging warning (default: 64).
    pub bucket_warn_threshold: usize,

    /// Enable cache hit tracking for diagnostics (default: false).
    pub track_cache_stats: bool,
}

impl Default for SpatialHitConfig {
    fn default() -> Self {
        Self {
            cell_size: 8,
            bucket_warn_threshold: 64,
            track_cache_stats: false,
        }
    }
}

// ---------------------------------------------------------------------------
// Widget hitbox entry
// ---------------------------------------------------------------------------

/// A registered widget's hit information.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct HitEntry {
    /// Widget identifier.
    pub id: HitId,
    /// Bounding rectangle.
    pub rect: Rect,
    /// Region type for hit callbacks.
    pub region: HitRegion,
    /// User data attached to this hit.
    pub data: HitData,
    /// Z-order layer (higher = on top).
    pub z_order: u16,
    /// Registration order for tie-breaking.
    order: u32,
}

impl HitEntry {
    /// Create a new hit entry.
    pub fn new(
        id: HitId,
        rect: Rect,
        region: HitRegion,
        data: HitData,
        z_order: u16,
        order: u32,
    ) -> Self {
        Self {
            id,
            rect,
            region,
            data,
            z_order,
            order,
        }
    }

    /// Check if point (x, y) is inside this entry's rect.
    #[inline]
    pub fn contains(&self, x: u16, y: u16) -> bool {
        x >= self.rect.x
            && x < self.rect.x.saturating_add(self.rect.width)
            && y >= self.rect.y
            && y < self.rect.y.saturating_add(self.rect.height)
    }

    /// Compare for z-order (higher z wins, then later order wins).
    #[inline]
    fn cmp_z_order(&self, other: &Self) -> std::cmp::Ordering {
        match self.z_order.cmp(&other.z_order) {
            std::cmp::Ordering::Equal => self.order.cmp(&other.order),
            ord => ord,
        }
    }
}

// ---------------------------------------------------------------------------
// Bucket for grid cell
// ---------------------------------------------------------------------------

/// Bucket storing widget indices for a grid cell.
#[derive(Debug, Clone, Default)]
struct Bucket {
    /// Indices into the entries array.
    entries: Vec<u32>,
}

impl Bucket {
    /// Add an entry index to this bucket.
    #[inline]
    fn push(&mut self, entry_idx: u32) {
        self.entries.push(entry_idx);
    }

    /// Clear the bucket.
    #[inline]
    fn clear(&mut self) {
        self.entries.clear();
    }
}

// ---------------------------------------------------------------------------
// Cache for hover results
// ---------------------------------------------------------------------------

/// Cached hover result to avoid recomputation.
#[derive(Debug, Clone, Copy, Default)]
struct HoverCache {
    /// Last queried position.
    pos: (u16, u16),
    /// Cached result (entry index or None).
    result: Option<u32>,
    /// Whether cache is valid.
    valid: bool,
}

// ---------------------------------------------------------------------------
// Dirty region tracking
// ---------------------------------------------------------------------------

/// Dirty region tracker for incremental updates.
#[derive(Debug, Clone, Default)]
struct DirtyTracker {
    /// Dirty rectangles pending processing.
    dirty_rects: Vec<Rect>,
    /// Whether entire index needs rebuild.
    full_rebuild: bool,
}

impl DirtyTracker {
    /// Mark a rectangle as dirty.
    fn mark_dirty(&mut self, rect: Rect) {
        if !self.full_rebuild {
            self.dirty_rects.push(rect);
        }
    }

    /// Mark entire index as dirty.
    fn mark_full_rebuild(&mut self) {
        self.full_rebuild = true;
        self.dirty_rects.clear();
    }

    /// Clear dirty state after processing.
    fn clear(&mut self) {
        self.dirty_rects.clear();
        self.full_rebuild = false;
    }

    /// Check if position overlaps any dirty region.
    fn is_dirty(&self, x: u16, y: u16) -> bool {
        if self.full_rebuild {
            return true;
        }
        for rect in &self.dirty_rects {
            if x >= rect.x
                && x < rect.x.saturating_add(rect.width)
                && y >= rect.y
                && y < rect.y.saturating_add(rect.height)
            {
                return true;
            }
        }
        false
    }
}

// ---------------------------------------------------------------------------
// Cache statistics
// ---------------------------------------------------------------------------

/// Diagnostic statistics for cache performance.
#[derive(Debug, Clone, Copy, Default)]
pub struct CacheStats {
    /// Number of cache hits.
    pub hits: u64,
    /// Number of cache misses.
    pub misses: u64,
    /// Number of full index rebuilds.
    pub rebuilds: u64,
}

impl CacheStats {
    /// Cache hit rate as percentage.
    #[must_use]
    pub fn hit_rate(&self) -> f32 {
        let total = self.hits + self.misses;
        if total == 0 {
            0.0
        } else {
            (self.hits as f32 / total as f32) * 100.0
        }
    }
}

// ---------------------------------------------------------------------------
// SpatialHitIndex
// ---------------------------------------------------------------------------

/// Spatial index for efficient hit-testing with z-order support.
///
/// Provides O(1) average-case queries by bucketing widgets into a uniform grid.
/// Supports dirty-rect caching to avoid recomputation of unchanged regions.
#[derive(Debug)]
pub struct SpatialHitIndex {
    config: SpatialHitConfig,

    /// Screen dimensions.
    width: u16,
    height: u16,

    /// Grid dimensions (in buckets).
    grid_width: u16,
    grid_height: u16,

    /// All registered hit entries.
    entries: Vec<HitEntry>,

    /// Spatial grid buckets (row-major).
    buckets: Vec<Bucket>,

    /// Registration counter for tie-breaking.
    next_order: u32,

    /// Hover cache.
    cache: HoverCache,

    /// Dirty region tracker.
    dirty: DirtyTracker,

    /// Diagnostic statistics.
    stats: CacheStats,

    /// Fast lookup from HitId to entry index.
    id_to_entry: AHashMap<HitId, u32>,
}

impl SpatialHitIndex {
    /// Create a new spatial hit index for the given screen dimensions.
    pub fn new(width: u16, height: u16, config: SpatialHitConfig) -> Self {
        let cell_size = config.cell_size.max(1);
        // Ceiling division in u32: the previous `saturating_add(cell-1)`
        // destroyed the ceiling for width/height >= 65529, producing a grid
        // one column/row short and out-of-bounds bucket indices.
        let grid_width = u32::from(width).div_ceil(u32::from(cell_size)) as u16;
        let grid_height = u32::from(height).div_ceil(u32::from(cell_size)) as u16;
        let bucket_count = grid_width as usize * grid_height as usize;

        Self {
            config,
            width,
            height,
            grid_width,
            grid_height,
            entries: Vec::with_capacity(256),
            buckets: vec![Bucket::default(); bucket_count],
            next_order: 0,
            cache: HoverCache::default(),
            dirty: DirtyTracker::default(),
            stats: CacheStats::default(),
            id_to_entry: AHashMap::with_capacity(256),
        }
    }

    /// Create with default configuration.
    pub fn with_defaults(width: u16, height: u16) -> Self {
        Self::new(width, height, SpatialHitConfig::default())
    }

    /// Register a widget hitbox.
    ///
    /// # Arguments
    ///
    /// - `id`: Unique widget identifier
    /// - `rect`: Bounding rectangle
    /// - `region`: Hit region type
    /// - `data`: User data
    /// - `z_order`: Z-order layer (higher = on top)
    pub fn register(
        &mut self,
        id: HitId,
        rect: Rect,
        region: HitRegion,
        data: HitData,
        z_order: u16,
    ) {
        // `HitId::default()` (id 0) is this index's removed-entry sentinel:
        // hit_test skips it and rebuild_buckets compacts it away, so
        // registering it would create a permanently unhittable entry.
        // Reject it explicitly instead of corrupting silently (documented
        // in the module's failure modes).
        if id == HitId::default() {
            return;
        }

        // Re-registering an id replaces the old entry. Without this, the
        // stale entry stayed live in the buckets (a ghost hitbox), and
        // rebuild_buckets would even resurrect it into id_to_entry after a
        // remove().
        if self.id_to_entry.contains_key(&id) {
            self.remove(id);
        }

        // Create entry
        let entry_idx = self.entries.len() as u32;
        let entry = HitEntry::new(id, rect, region, data, z_order, self.next_order);
        self.next_order = self.next_order.wrapping_add(1);

        self.entries.push(entry);
        self.id_to_entry.insert(id, entry_idx);

        // Add to relevant buckets
        self.add_to_buckets(entry_idx, rect);

        // Invalidate cache for this region
        self.dirty.mark_dirty(rect);
        if self.cache.valid && self.dirty.is_dirty(self.cache.pos.0, self.cache.pos.1) {
            self.cache.valid = false;
        }
    }

    /// Register with default z-order (0).
    pub fn register_simple(&mut self, id: HitId, rect: Rect, region: HitRegion, data: HitData) {
        self.register(id, rect, region, data, 0);
    }

    /// Update an existing widget's hitbox.
    ///
    /// Returns `true` if widget was found and updated.
    pub fn update(&mut self, id: HitId, new_rect: Rect) -> bool {
        let Some(&entry_idx) = self.id_to_entry.get(&id) else {
            return false;
        };

        let old_rect = self.entries[entry_idx as usize].rect;

        // Mark both old and new regions as dirty
        self.dirty.mark_dirty(old_rect);
        self.dirty.mark_dirty(new_rect);

        // Update entry
        self.entries[entry_idx as usize].rect = new_rect;

        // Rebuild buckets for affected regions
        // For simplicity, we do a full rebuild. Production could do incremental.
        self.rebuild_buckets();

        // Invalidate cache
        self.cache.valid = false;

        true
    }

    /// Remove a widget from the index.
    ///
    /// Returns `true` if widget was found and removed.
    pub fn remove(&mut self, id: HitId) -> bool {
        let Some(&entry_idx) = self.id_to_entry.get(&id) else {
            return false;
        };

        let rect = self.entries[entry_idx as usize].rect;
        self.dirty.mark_dirty(rect);

        // Mark entry as removed (set id to default)
        self.entries[entry_idx as usize].id = HitId::default();
        self.id_to_entry.remove(&id);

        // Rebuild buckets
        self.rebuild_buckets();
        self.cache.valid = false;

        true
    }

    /// Hit test at the given position.
    ///
    /// Returns the topmost (highest z-order) widget at (x, y), if any.
    ///
    /// # Performance
    ///
    /// - O(1) average case with cache hit
    /// - O(k) where k = widgets overlapping the bucket cell
    #[must_use]
    pub fn hit_test(&mut self, x: u16, y: u16) -> Option<(HitId, HitRegion, HitData)> {
        // Bounds check
        if x >= self.width || y >= self.height {
            return None;
        }

        // Check cache
        if self.cache.valid && self.cache.pos == (x, y) {
            if self.config.track_cache_stats {
                self.stats.hits += 1;
            }
            return self.cache.result.map(|idx| {
                let e = &self.entries[idx as usize];
                (e.id, e.region, e.data)
            });
        }

        if self.config.track_cache_stats {
            self.stats.misses += 1;
        }

        // Find bucket
        let bucket_idx = self.bucket_index(x, y);
        let bucket = &self.buckets[bucket_idx];

        // Find topmost widget at (x, y)
        let mut best: Option<&HitEntry> = None;
        let mut best_idx: Option<u32> = None;

        for &entry_idx in &bucket.entries {
            let entry = &self.entries[entry_idx as usize];

            // Skip removed entries
            if entry.id == HitId::default() {
                continue;
            }

            // Check if point is inside this entry
            if entry.contains(x, y) {
                // Compare z-order
                match best {
                    None => {
                        best = Some(entry);
                        best_idx = Some(entry_idx);
                    }
                    Some(current_best) if entry.cmp_z_order(current_best).is_gt() => {
                        best = Some(entry);
                        best_idx = Some(entry_idx);
                    }
                    _ => {}
                }
            }
        }

        // Update cache
        self.cache.pos = (x, y);
        self.cache.result = best_idx;
        self.cache.valid = true;
        // The cache now reflects the current index state, so prior dirties are irrelevant.
        self.dirty.clear();

        best.map(|e| (e.id, e.region, e.data))
    }

    /// Hit test without modifying cache (for read-only queries).
    #[must_use]
    pub fn hit_test_readonly(&self, x: u16, y: u16) -> Option<(HitId, HitRegion, HitData)> {
        if x >= self.width || y >= self.height {
            return None;
        }

        let bucket_idx = self.bucket_index(x, y);
        let bucket = &self.buckets[bucket_idx];

        let mut best: Option<&HitEntry> = None;

        for &entry_idx in &bucket.entries {
            let entry = &self.entries[entry_idx as usize];
            if entry.id == HitId::default() {
                continue;
            }
            if entry.contains(x, y) {
                match best {
                    None => best = Some(entry),
                    Some(current_best) if entry.cmp_z_order(current_best).is_gt() => {
                        best = Some(entry)
                    }
                    _ => {}
                }
            }
        }

        best.map(|e| (e.id, e.region, e.data))
    }

    /// Clear all entries and reset the index.
    pub fn clear(&mut self) {
        self.entries.clear();
        self.id_to_entry.clear();
        for bucket in &mut self.buckets {
            bucket.clear();
        }
        self.next_order = 0;
        self.cache.valid = false;
        self.dirty.clear();
    }

    /// Get diagnostic statistics.
    #[must_use]
    pub fn stats(&self) -> CacheStats {
        self.stats
    }

    /// Reset diagnostic statistics.
    pub fn reset_stats(&mut self) {
        self.stats = CacheStats::default();
    }

    /// Number of registered widgets.
    #[inline]
    #[must_use]
    pub fn len(&self) -> usize {
        self.id_to_entry.len()
    }

    /// Check if empty.
    #[inline]
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.id_to_entry.is_empty()
    }

    /// Invalidate cache for a specific region.
    pub fn invalidate_region(&mut self, rect: Rect) {
        self.dirty.mark_dirty(rect);
        if self.cache.valid && self.dirty.is_dirty(self.cache.pos.0, self.cache.pos.1) {
            self.cache.valid = false;
        }
    }

    /// Force full cache invalidation.
    pub fn invalidate_all(&mut self) {
        self.cache.valid = false;
        self.dirty.mark_full_rebuild();
    }

    // -----------------------------------------------------------------------
    // Internal helpers
    // -----------------------------------------------------------------------

    /// Calculate bucket index for a point.
    ///
    /// Clamped to the grid like [`bucket_range`](Self::bucket_range), so a
    /// point inside screen bounds can never index past the bucket vec.
    #[inline]
    fn bucket_index(&self, x: u16, y: u16) -> usize {
        let cell_size = self.config.cell_size;
        let bx = (x / cell_size).min(self.grid_width.saturating_sub(1));
        let by = (y / cell_size).min(self.grid_height.saturating_sub(1));
        by as usize * self.grid_width as usize + bx as usize
    }

    /// Calculate bucket range for a rectangle.
    fn bucket_range(&self, rect: Rect) -> (u16, u16, u16, u16) {
        let cell_size = self.config.cell_size;
        let bx_start = rect.x / cell_size;
        let by_start = rect.y / cell_size;
        let bx_end = rect.x.saturating_add(rect.width.saturating_sub(1)) / cell_size;
        let by_end = rect.y.saturating_add(rect.height.saturating_sub(1)) / cell_size;
        (
            bx_start.min(self.grid_width.saturating_sub(1)),
            by_start.min(self.grid_height.saturating_sub(1)),
            bx_end.min(self.grid_width.saturating_sub(1)),
            by_end.min(self.grid_height.saturating_sub(1)),
        )
    }

    /// Add an entry to all buckets it overlaps.
    fn add_to_buckets(&mut self, entry_idx: u32, rect: Rect) {
        if rect.width == 0 || rect.height == 0 {
            return;
        }

        let (bx_start, by_start, bx_end, by_end) = self.bucket_range(rect);

        for by in by_start..=by_end {
            for bx in bx_start..=bx_end {
                let bucket_idx = by as usize * self.grid_width as usize + bx as usize;
                if bucket_idx < self.buckets.len() {
                    self.buckets[bucket_idx].push(entry_idx);

                    // Warn if bucket is getting large
                    if self.buckets[bucket_idx].entries.len() > self.config.bucket_warn_threshold {
                        // In production, log this
                    }
                }
            }
        }
    }

    /// Rebuild all buckets from entries, compacting storage.
    fn rebuild_buckets(&mut self) {
        // Clear all buckets
        for bucket in &mut self.buckets {
            bucket.clear();
        }

        // Compact entries in-place to remove dead slots (HitId::default())
        let mut valid_idx = 0;
        for i in 0..self.entries.len() {
            if self.entries[i].id != HitId::default() {
                if i != valid_idx {
                    self.entries[valid_idx] = self.entries[i];
                }
                valid_idx += 1;
            }
        }
        self.entries.truncate(valid_idx);

        // Rebuild lookup map from compacted entries
        self.id_to_entry.clear();
        for (idx, entry) in self.entries.iter().enumerate() {
            self.id_to_entry.insert(entry.id, idx as u32);
        }

        // Rebuild buckets by iterating over entry indices to avoid borrowing
        // the entire entries vector while modifying buckets.
        for idx in 0..self.entries.len() {
            let rect = self.entries[idx].rect;
            self.add_to_buckets_internal(idx as u32, rect);
        }

        self.dirty.clear();
        self.stats.rebuilds += 1;
    }

    /// Add entry to buckets (internal, doesn't modify dirty tracker).
    fn add_to_buckets_internal(&mut self, entry_idx: u32, rect: Rect) {
        if rect.width == 0 || rect.height == 0 {
            return;
        }

        let (bx_start, by_start, bx_end, by_end) = self.bucket_range(rect);

        for by in by_start..=by_end {
            for bx in bx_start..=bx_end {
                let bucket_idx = by as usize * self.grid_width as usize + bx as usize;
                if bucket_idx < self.buckets.len() {
                    self.buckets[bucket_idx].push(entry_idx);
                }
            }
        }
    }
}

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

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

    fn index() -> SpatialHitIndex {
        SpatialHitIndex::with_defaults(80, 24)
    }

    // --- Regressions (exploration-audit round 7) ---

    #[test]
    fn u16_max_dimensions_do_not_panic_or_miss_hits() {
        // Regression: saturating_add destroyed the ceiling division for
        // width >= 65529, making the bucket grid one column short —
        // hit_test near the right edge indexed out of bounds (1-row grids)
        // or read the wrong bucket and returned None inside a widget.
        let mut idx = SpatialHitIndex::with_defaults(u16::MAX, 8);
        idx.register_simple(
            HitId::new(1),
            Rect::new(65520, 0, 15, 8),
            HitRegion::Button,
            0,
        );
        assert!(
            idx.hit_test(65530, 5).is_some(),
            "hit inside the widget at extreme x must resolve"
        );

        let mut idx = SpatialHitIndex::with_defaults(u16::MAX, 24);
        idx.register_simple(
            HitId::new(2),
            Rect::new(65520, 0, 15, 8),
            HitRegion::Button,
            0,
        );
        assert_eq!(
            idx.hit_test(65530, 0).map(|(id, _, _)| id),
            Some(HitId::new(2))
        );
    }

    #[test]
    fn reregistering_id_replaces_old_entry() {
        // Regression: re-registering an id left the old entry live in the
        // buckets (ghost hitbox), and rebuild_buckets resurrected it into
        // id_to_entry after remove().
        let mut idx = index();
        idx.register_simple(HitId::new(1), Rect::new(0, 0, 5, 5), HitRegion::Button, 7);
        idx.register_simple(HitId::new(1), Rect::new(20, 10, 5, 5), HitRegion::Button, 9);
        assert_eq!(idx.len(), 1);
        assert!(
            idx.hit_test(2, 2).is_none(),
            "old location must not be a ghost hitbox"
        );
        let hit = idx.hit_test(22, 12).expect("new location must hit");
        assert_eq!(hit.2, 9, "data must come from the replacement entry");

        // remove() must kill the entry for good — no resurrection.
        assert!(idx.remove(HitId::new(1)));
        assert!(idx.hit_test(22, 12).is_none());
        assert!(idx.hit_test(2, 2).is_none());
        assert_eq!(idx.len(), 0);
    }

    #[test]
    fn hit_id_zero_is_rejected_not_silently_unhittable() {
        let mut idx = index();
        idx.register_simple(
            HitId::default(),
            Rect::new(0, 0, 10, 10),
            HitRegion::Button,
            7,
        );
        assert_eq!(idx.len(), 0, "sentinel id must not create an entry");
        assert!(idx.hit_test(5, 5).is_none());
    }

    // --- Basic functionality ---

    #[test]
    fn initial_state_empty() {
        let idx = index();
        assert!(idx.is_empty());
        assert_eq!(idx.len(), 0);
    }

    #[test]
    fn register_and_hit_test() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(10, 5, 20, 3),
            HitRegion::Button,
            42,
        );

        // Inside rect
        let result = idx.hit_test(15, 6);
        assert_eq!(result, Some((HitId::new(1), HitRegion::Button, 42)));

        // Outside rect
        assert!(idx.hit_test(5, 5).is_none());
        assert!(idx.hit_test(35, 5).is_none());
    }

    #[test]
    fn z_order_topmost_wins() {
        let mut idx = index();

        // Register two overlapping widgets with different z-order
        idx.register(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            1,
            0, // Lower z
        );
        idx.register(
            HitId::new(2),
            Rect::new(5, 5, 10, 10),
            HitRegion::Border,
            2,
            1, // Higher z
        );

        // In overlap region, widget 2 should win (higher z)
        let result = idx.hit_test(7, 7);
        assert_eq!(result, Some((HitId::new(2), HitRegion::Border, 2)));

        // In widget 1 only region
        let result = idx.hit_test(2, 2);
        assert_eq!(result, Some((HitId::new(1), HitRegion::Content, 1)));
    }

    #[test]
    fn same_z_order_later_wins() {
        let mut idx = index();

        // Same z-order, later registration wins
        idx.register(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            1,
            0,
        );
        idx.register(
            HitId::new(2),
            Rect::new(5, 5, 10, 10),
            HitRegion::Border,
            2,
            0,
        );

        // In overlap, widget 2 (later) should win
        let result = idx.hit_test(7, 7);
        assert_eq!(result, Some((HitId::new(2), HitRegion::Border, 2)));
    }

    #[test]
    fn hit_test_border_inclusive() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(10, 10, 5, 5),
            HitRegion::Content,
            0,
        );

        // Corners should hit
        assert!(idx.hit_test(10, 10).is_some()); // Top-left
        assert!(idx.hit_test(14, 10).is_some()); // Top-right
        assert!(idx.hit_test(10, 14).is_some()); // Bottom-left
        assert!(idx.hit_test(14, 14).is_some()); // Bottom-right

        // Just outside should miss
        assert!(idx.hit_test(15, 10).is_none()); // Right of rect
        assert!(idx.hit_test(10, 15).is_none()); // Below rect
        assert!(idx.hit_test(9, 10).is_none()); // Left of rect
        assert!(idx.hit_test(10, 9).is_none()); // Above rect
    }

    #[test]
    fn update_widget_rect() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );

        // Should hit at original position
        assert!(idx.hit_test(5, 5).is_some());

        // Update position (staying within 80x24 bounds)
        let updated = idx.update(HitId::new(1), Rect::new(50, 10, 10, 10));
        assert!(updated);

        // Should no longer hit at original position
        assert!(idx.hit_test(5, 5).is_none());

        // Should hit at new position
        assert!(idx.hit_test(55, 15).is_some());
    }

    #[test]
    fn remove_widget() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );

        assert!(idx.hit_test(5, 5).is_some());

        let removed = idx.remove(HitId::new(1));
        assert!(removed);

        assert!(idx.hit_test(5, 5).is_none());
        assert!(idx.is_empty());
    }

    #[test]
    fn clear_all() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );
        idx.register_simple(
            HitId::new(2),
            Rect::new(20, 20, 10, 10),
            HitRegion::Button,
            1,
        );

        assert_eq!(idx.len(), 2);

        idx.clear();

        assert!(idx.is_empty());
        assert!(idx.hit_test(5, 5).is_none());
        assert!(idx.hit_test(25, 25).is_none());
    }

    // --- Cache tests ---

    #[test]
    fn cache_hit_on_same_position() {
        let mut idx = SpatialHitIndex::new(
            80,
            24,
            SpatialHitConfig {
                track_cache_stats: true,
                ..Default::default()
            },
        );
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );

        // First query - miss
        let _ = idx.hit_test(5, 5);
        assert_eq!(idx.stats().misses, 1);
        assert_eq!(idx.stats().hits, 0);

        // Second query at same position - hit
        let _ = idx.hit_test(5, 5);
        assert_eq!(idx.stats().hits, 1);

        // Query at different position - miss
        let _ = idx.hit_test(7, 7);
        assert_eq!(idx.stats().misses, 2);
    }

    #[test]
    fn cache_invalidated_on_register() {
        let mut idx = SpatialHitIndex::new(
            80,
            24,
            SpatialHitConfig {
                track_cache_stats: true,
                ..Default::default()
            },
        );
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );

        // Prime cache
        let _ = idx.hit_test(5, 5);

        // Register overlapping widget
        idx.register_simple(HitId::new(2), Rect::new(0, 0, 10, 10), HitRegion::Button, 1);

        // Cache should be invalidated, so next query is a miss
        let hits_before = idx.stats().hits;
        let _ = idx.hit_test(5, 5);
        // Due to dirty tracking, cache is invalidated in overlapping region
        assert_eq!(idx.stats().hits, hits_before);
    }

    // --- Property tests ---

    #[test]
    fn property_random_layout_correctness() {
        let mut idx = index();
        let widgets = vec![
            (HitId::new(1), Rect::new(0, 0, 20, 10), 0u16),
            (HitId::new(2), Rect::new(10, 5, 20, 10), 1),
            (HitId::new(3), Rect::new(25, 0, 15, 15), 2),
        ];

        for (id, rect, z) in &widgets {
            idx.register(*id, *rect, HitRegion::Content, id.id() as u64, *z);
        }

        // Test multiple points
        for x in 0..60 {
            for y in 0..20 {
                let indexed_result = idx.hit_test_readonly(x, y);

                // Compute expected result with naive O(n) scan
                let mut best: Option<(HitId, u16)> = None;
                for (id, rect, z) in &widgets {
                    if x >= rect.x
                        && x < rect.x + rect.width
                        && y >= rect.y
                        && y < rect.y + rect.height
                    {
                        match best {
                            None => best = Some((*id, *z)),
                            Some((_, best_z)) if *z > best_z => best = Some((*id, *z)),
                            _ => {}
                        }
                    }
                }

                let expected_id = best.map(|(id, _)| id);
                let indexed_id = indexed_result.map(|(id, _, _)| id);

                assert_eq!(
                    indexed_id, expected_id,
                    "Mismatch at ({}, {}): indexed={:?}, expected={:?}",
                    x, y, indexed_id, expected_id
                );
            }
        }
    }

    // --- Edge cases ---

    #[test]
    fn out_of_bounds_returns_none() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );

        assert!(idx.hit_test(100, 100).is_none());
        assert!(idx.hit_test(80, 0).is_none());
        assert!(idx.hit_test(0, 24).is_none());
    }

    #[test]
    fn zero_size_rect_ignored() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(10, 10, 0, 0),
            HitRegion::Content,
            0,
        );

        // Should not hit even at the exact position
        assert!(idx.hit_test(10, 10).is_none());
    }

    #[test]
    fn large_rect_spans_many_buckets() {
        let mut idx = index();
        // Rect spans multiple buckets (80x24 with 8x8 cells = 10x3 buckets)
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 80, 24),
            HitRegion::Content,
            0,
        );

        // Should hit everywhere
        assert!(idx.hit_test(0, 0).is_some());
        assert!(idx.hit_test(40, 12).is_some());
        assert!(idx.hit_test(79, 23).is_some());
    }

    #[test]
    fn update_nonexistent_returns_false() {
        let mut idx = index();
        let result = idx.update(HitId::new(999), Rect::new(0, 0, 10, 10));
        assert!(!result);
    }

    #[test]
    fn remove_nonexistent_returns_false() {
        let mut idx = index();
        let result = idx.remove(HitId::new(999));
        assert!(!result);
    }

    #[test]
    fn stats_hit_rate() {
        let mut stats = CacheStats::default();
        assert_eq!(stats.hit_rate(), 0.0);

        stats.hits = 75;
        stats.misses = 25;
        assert!((stats.hit_rate() - 75.0).abs() < 0.01);
    }

    #[test]
    fn config_defaults() {
        let config = SpatialHitConfig::default();
        assert_eq!(config.cell_size, 8);
        assert_eq!(config.bucket_warn_threshold, 64);
        assert!(!config.track_cache_stats);
    }

    #[test]
    fn invalidate_region() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );

        // Prime cache
        let _ = idx.hit_test(5, 5);
        assert!(idx.cache.valid);

        // Invalidate region that includes cached position
        idx.invalidate_region(Rect::new(0, 0, 10, 10));
        assert!(!idx.cache.valid);
    }

    #[test]
    fn invalidate_all() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );

        let _ = idx.hit_test(5, 5);
        assert!(idx.cache.valid);

        idx.invalidate_all();
        assert!(!idx.cache.valid);
    }

    #[test]
    fn three_overlapping_widgets_z_order() {
        let mut idx = index();
        idx.register(
            HitId::new(1),
            Rect::new(0, 0, 20, 20),
            HitRegion::Content,
            10,
            0,
        );
        idx.register(
            HitId::new(2),
            Rect::new(5, 5, 15, 15),
            HitRegion::Border,
            20,
            2,
        );
        idx.register(
            HitId::new(3),
            Rect::new(8, 8, 10, 10),
            HitRegion::Button,
            30,
            1,
        );
        // At (10, 10): all three overlap; widget 2 has highest z=2
        let result = idx.hit_test(10, 10);
        assert_eq!(result, Some((HitId::new(2), HitRegion::Border, 20)));
    }

    #[test]
    fn hit_test_readonly_matches_mutable() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(5, 5, 10, 10),
            HitRegion::Content,
            0,
        );
        let mutable_result = idx.hit_test(8, 8);
        let readonly_result = idx.hit_test_readonly(8, 8);
        assert_eq!(mutable_result, readonly_result);
    }

    #[test]
    fn single_pixel_widget() {
        let mut idx = index();
        idx.register_simple(HitId::new(1), Rect::new(5, 5, 1, 1), HitRegion::Button, 0);
        assert!(idx.hit_test(5, 5).is_some());
        assert!(idx.hit_test(6, 5).is_none());
        assert!(idx.hit_test(5, 6).is_none());
    }

    #[test]
    fn clear_on_empty_is_idempotent() {
        let mut idx = index();
        idx.clear();
        assert!(idx.is_empty());
        idx.clear();
        assert!(idx.is_empty());
    }

    #[test]
    fn register_remove_register_cycle() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );
        assert_eq!(idx.len(), 1);
        idx.remove(HitId::new(1));
        assert_eq!(idx.len(), 0);
        idx.register_simple(HitId::new(1), Rect::new(20, 20, 5, 5), HitRegion::Border, 0);
        assert_eq!(idx.len(), 1);
        // Should hit at new location, not old
        assert!(idx.hit_test(22, 22).is_some());
        assert!(idx.hit_test(5, 5).is_none());
    }

    #[test]
    fn invalidate_non_overlapping_region_preserves_cache() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );
        let _ = idx.hit_test(5, 5);
        assert!(idx.cache.valid);
        // Invalidate a region that doesn't overlap the cached point
        idx.invalidate_region(Rect::new(50, 50, 10, 10));
        assert!(idx.cache.valid);
    }

    #[test]
    fn hit_entry_contains() {
        let entry = HitEntry::new(
            HitId::new(1),
            Rect::new(10, 10, 20, 20),
            HitRegion::Content,
            0,
            0,
            0,
        );
        assert!(entry.contains(15, 15));
        assert!(entry.contains(10, 10));
        assert!(!entry.contains(9, 10));
        assert!(!entry.contains(30, 30));
    }

    #[test]
    fn reset_stats_clears_counters() {
        let mut idx = SpatialHitIndex::new(
            80,
            24,
            SpatialHitConfig {
                cell_size: 8,
                bucket_warn_threshold: 64,
                track_cache_stats: true,
            },
        );
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );
        let _ = idx.hit_test(5, 5);
        let _ = idx.hit_test(5, 5); // cache hit
        let stats = idx.stats();
        assert!(stats.hits > 0 || stats.misses > 0);
        idx.reset_stats();
        let stats = idx.stats();
        assert_eq!(stats.hits, 0);
        assert_eq!(stats.misses, 0);
    }

    // =========================================================================
    // Edge-Case Tests (bd-9bvp0)
    // =========================================================================

    // --- SpatialHitConfig trait coverage ---

    #[test]
    fn config_debug_clone() {
        let config = SpatialHitConfig::default();
        let dbg = format!("{:?}", config);
        assert!(dbg.contains("SpatialHitConfig"), "Debug: {dbg}");
        let cloned = config.clone();
        assert_eq!(cloned.cell_size, 8);
    }

    // --- HitEntry trait coverage ---

    #[test]
    fn hit_entry_debug_clone_copy_eq() {
        let entry = HitEntry::new(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            42,
            5,
            0,
        );
        let dbg = format!("{:?}", entry);
        assert!(dbg.contains("HitEntry"), "Debug: {dbg}");
        let copied = entry; // Copy
        assert_eq!(entry, copied);
        let cloned: HitEntry = entry; // Clone == Copy for this type
        assert_eq!(entry, cloned);
    }

    #[test]
    fn hit_entry_ne() {
        let a = HitEntry::new(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
            0,
            0,
        );
        let b = HitEntry::new(
            HitId::new(2),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
            0,
            0,
        );
        assert_ne!(a, b);
    }

    #[test]
    fn hit_entry_contains_zero_width() {
        let entry = HitEntry::new(
            HitId::new(1),
            Rect::new(10, 10, 0, 5),
            HitRegion::Content,
            0,
            0,
            0,
        );
        // Zero width: x >= 10 && x < 10+0=10 → always false
        assert!(!entry.contains(10, 10));
    }

    #[test]
    fn hit_entry_contains_zero_height() {
        let entry = HitEntry::new(
            HitId::new(1),
            Rect::new(10, 10, 5, 0),
            HitRegion::Content,
            0,
            0,
            0,
        );
        assert!(!entry.contains(10, 10));
    }

    #[test]
    fn hit_entry_contains_at_saturating_boundary() {
        // Rect near u16::MAX tests saturating_add
        let entry = HitEntry::new(
            HitId::new(1),
            Rect::new(u16::MAX - 5, u16::MAX - 5, 10, 10),
            HitRegion::Content,
            0,
            0,
            0,
        );
        // saturating_add: (65530 + 10).min(65535) = 65535
        // contains uses strict <, so u16::MAX is excluded
        assert!(entry.contains(u16::MAX - 5, u16::MAX - 5));
        assert!(entry.contains(u16::MAX - 1, u16::MAX - 1));
        assert!(!entry.contains(u16::MAX, u16::MAX));
    }

    // --- CacheStats ---

    #[test]
    fn cache_stats_default() {
        let stats = CacheStats::default();
        assert_eq!(stats.hits, 0);
        assert_eq!(stats.misses, 0);
        assert_eq!(stats.rebuilds, 0);
        assert_eq!(stats.hit_rate(), 0.0);
    }

    #[test]
    fn cache_stats_debug_copy() {
        let stats = CacheStats {
            hits: 10,
            misses: 5,
            rebuilds: 1,
        };
        let dbg = format!("{:?}", stats);
        assert!(dbg.contains("CacheStats"), "Debug: {dbg}");
        let copy = stats; // Copy
        assert_eq!(copy.hits, stats.hits);
    }

    #[test]
    fn cache_stats_100_percent_hit_rate() {
        let stats = CacheStats {
            hits: 100,
            misses: 0,
            rebuilds: 0,
        };
        assert!((stats.hit_rate() - 100.0).abs() < 0.01);
    }

    #[test]
    fn cache_stats_0_percent_hit_rate() {
        let stats = CacheStats {
            hits: 0,
            misses: 100,
            rebuilds: 0,
        };
        assert!((stats.hit_rate()).abs() < 0.01);
    }

    // --- SpatialHitIndex construction ---

    #[test]
    fn new_with_cell_size_zero_clamped_to_one() {
        let config = SpatialHitConfig {
            cell_size: 0,
            ..Default::default()
        };
        let idx = SpatialHitIndex::new(80, 24, config);
        // cell_size=0 clamped to 1, grid = 80x24 buckets
        assert_eq!(idx.grid_width, 80);
        assert_eq!(idx.grid_height, 24);
        assert!(idx.is_empty());
    }

    #[test]
    fn new_with_cell_size_one() {
        let config = SpatialHitConfig {
            cell_size: 1,
            ..Default::default()
        };
        let idx = SpatialHitIndex::new(10, 5, config);
        // 1 bucket per cell
        assert_eq!(idx.grid_width, 10);
        assert_eq!(idx.grid_height, 5);
    }

    #[test]
    fn new_with_large_cell_size() {
        let config = SpatialHitConfig {
            cell_size: 100,
            ..Default::default()
        };
        let idx = SpatialHitIndex::new(80, 24, config);
        // 80/100 rounds up to 1, 24/100 rounds up to 1
        assert_eq!(idx.grid_width, 1);
        assert_eq!(idx.grid_height, 1);
    }

    #[test]
    fn new_zero_dimensions() {
        let idx = SpatialHitIndex::with_defaults(0, 0);
        assert!(idx.is_empty());
        // All hit tests should return None
        assert!(idx.hit_test_readonly(0, 0).is_none());
    }

    #[test]
    fn with_defaults_uses_default_config() {
        let idx = SpatialHitIndex::with_defaults(80, 24);
        assert_eq!(idx.config.cell_size, 8);
        assert_eq!(idx.config.bucket_warn_threshold, 64);
        assert!(!idx.config.track_cache_stats);
    }

    #[test]
    fn index_debug_format() {
        let idx = SpatialHitIndex::with_defaults(10, 10);
        let dbg = format!("{:?}", idx);
        assert!(dbg.contains("SpatialHitIndex"), "Debug: {dbg}");
    }

    // --- Register edge cases ---

    #[test]
    fn register_zero_width_rect_not_in_buckets() {
        let mut idx = index();
        idx.register_simple(HitId::new(1), Rect::new(5, 5, 0, 10), HitRegion::Content, 0);
        // Still registered (len=1) but won't be found by hit_test
        assert_eq!(idx.len(), 1);
        assert!(idx.hit_test(5, 5).is_none());
    }

    #[test]
    fn register_zero_height_rect_not_in_buckets() {
        let mut idx = index();
        idx.register_simple(HitId::new(1), Rect::new(5, 5, 10, 0), HitRegion::Content, 0);
        assert_eq!(idx.len(), 1);
        assert!(idx.hit_test(5, 5).is_none());
    }

    #[test]
    fn register_rect_extending_past_screen() {
        let mut idx = index();
        // Rect extends past 80x24 screen
        idx.register_simple(
            HitId::new(1),
            Rect::new(70, 20, 20, 10),
            HitRegion::Content,
            0,
        );
        // Should still hit within screen bounds
        assert!(idx.hit_test(75, 22).is_some());
        // Outside screen returns None
        assert!(idx.hit_test(85, 25).is_none());
    }

    #[test]
    fn register_many_widgets() {
        let mut idx = index();
        for i in 0..100u32 {
            let x = (i % 8) as u16 * 10;
            let y = (i / 8) as u16 * 3;
            idx.register_simple(
                HitId::new(i + 1),
                Rect::new(x, y, 5, 2),
                HitRegion::Content,
                i as u64,
            );
        }
        assert_eq!(idx.len(), 100);
        // Spot check
        let result = idx.hit_test(2, 1);
        assert!(result.is_some());
    }

    #[test]
    fn register_simple_uses_z_order_zero() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );
        // Register with explicit z=1 in same area
        idx.register(
            HitId::new(2),
            Rect::new(0, 0, 10, 10),
            HitRegion::Border,
            0,
            1,
        );
        // Widget 2 should win (z=1 > z=0)
        let result = idx.hit_test(5, 5);
        assert_eq!(result, Some((HitId::new(2), HitRegion::Border, 0)));
    }

    // --- Update edge cases ---

    #[test]
    fn update_to_zero_size_rect() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );
        assert!(idx.hit_test(5, 5).is_some());

        idx.update(HitId::new(1), Rect::new(0, 0, 0, 0));
        // Zero-size rect won't be in buckets
        assert!(idx.hit_test(0, 0).is_none());
    }

    #[test]
    fn update_shrinks_widget() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 20, 20),
            HitRegion::Content,
            0,
        );
        assert!(idx.hit_test(15, 15).is_some());

        idx.update(HitId::new(1), Rect::new(0, 0, 5, 5));
        assert!(idx.hit_test(15, 15).is_none());
        assert!(idx.hit_test(2, 2).is_some());
    }

    // --- Remove edge cases ---

    #[test]
    fn remove_middle_entry_compacts() {
        let mut idx = index();
        idx.register_simple(HitId::new(1), Rect::new(0, 0, 5, 5), HitRegion::Content, 10);
        idx.register_simple(
            HitId::new(2),
            Rect::new(10, 0, 5, 5),
            HitRegion::Content,
            20,
        );
        idx.register_simple(
            HitId::new(3),
            Rect::new(20, 0, 5, 5),
            HitRegion::Content,
            30,
        );
        assert_eq!(idx.len(), 3);

        idx.remove(HitId::new(2));
        assert_eq!(idx.len(), 2);

        // Widget 1 and 3 should still work
        let r1 = idx.hit_test(2, 2);
        assert_eq!(r1, Some((HitId::new(1), HitRegion::Content, 10)));
        let r3 = idx.hit_test(22, 2);
        assert_eq!(r3, Some((HitId::new(3), HitRegion::Content, 30)));
    }

    #[test]
    fn double_remove_returns_false() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );
        assert!(idx.remove(HitId::new(1)));
        assert!(!idx.remove(HitId::new(1)));
    }

    // --- hit_test edge cases ---

    #[test]
    fn hit_test_at_exact_screen_boundary() {
        let mut idx = index(); // 80x24
        idx.register_simple(
            HitId::new(1),
            Rect::new(70, 20, 10, 4),
            HitRegion::Content,
            0,
        );
        // Last valid pixel
        assert!(idx.hit_test(79, 23).is_some());
        // One past screen
        assert!(idx.hit_test(80, 23).is_none());
        assert!(idx.hit_test(79, 24).is_none());
    }

    #[test]
    fn hit_test_at_grid_cell_boundaries() {
        let mut idx = index(); // cell_size=8
        idx.register_simple(
            HitId::new(1),
            Rect::new(6, 6, 4, 4), // spans cells (0,0) and (1,1)
            HitRegion::Content,
            0,
        );
        // At x=7,y=7 (cell 0,0) - should hit
        assert!(idx.hit_test(7, 7).is_some());
        // At x=8,y=8 (cell 1,1) - should hit
        assert!(idx.hit_test(8, 8).is_some());
        // At x=9,y=9 (cell 1,1) - should hit
        assert!(idx.hit_test(9, 9).is_some());
        // At x=10,y=10 (cell 1,1) - outside rect
        assert!(idx.hit_test(10, 10).is_none());
    }

    #[test]
    fn hit_test_readonly_out_of_bounds() {
        let idx = index();
        assert!(idx.hit_test_readonly(80, 0).is_none());
        assert!(idx.hit_test_readonly(0, 24).is_none());
        assert!(idx.hit_test_readonly(u16::MAX, u16::MAX).is_none());
    }

    #[test]
    fn hit_test_readonly_skips_removed() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );
        idx.register_simple(HitId::new(2), Rect::new(0, 0, 10, 10), HitRegion::Border, 1);
        idx.remove(HitId::new(2));
        // Widget 1 should still be found
        let result = idx.hit_test_readonly(5, 5);
        assert_eq!(result, Some((HitId::new(1), HitRegion::Content, 0)));
    }

    // --- Cache behavior ---

    #[test]
    fn cache_updates_on_different_positions() {
        let mut idx = SpatialHitIndex::new(
            80,
            24,
            SpatialHitConfig {
                track_cache_stats: true,
                ..Default::default()
            },
        );
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 40, 12),
            HitRegion::Content,
            1,
        );
        idx.register_simple(
            HitId::new(2),
            Rect::new(40, 12, 40, 12),
            HitRegion::Border,
            2,
        );

        // First query
        let r1 = idx.hit_test(5, 5);
        assert_eq!(r1, Some((HitId::new(1), HitRegion::Content, 1)));
        assert_eq!(idx.stats().misses, 1);

        // Different position - miss
        let r2 = idx.hit_test(50, 15);
        assert_eq!(r2, Some((HitId::new(2), HitRegion::Border, 2)));
        assert_eq!(idx.stats().misses, 2);

        // Back to first position - miss (cache only stores one position)
        let _ = idx.hit_test(5, 5);
        assert_eq!(idx.stats().misses, 3);
    }

    #[test]
    fn cache_invalidated_by_invalidate_all_then_same_position() {
        let mut idx = SpatialHitIndex::new(
            80,
            24,
            SpatialHitConfig {
                track_cache_stats: true,
                ..Default::default()
            },
        );
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );

        // Prime cache
        let _ = idx.hit_test(5, 5);
        assert_eq!(idx.stats().misses, 1);
        assert_eq!(idx.stats().hits, 0);

        // Invalidate all then query same position
        idx.invalidate_all();
        let _ = idx.hit_test(5, 5);
        // Should be a miss since cache was invalidated
        assert_eq!(idx.stats().misses, 2);
    }

    #[test]
    fn cache_not_updated_by_readonly() {
        let mut idx = SpatialHitIndex::new(
            80,
            24,
            SpatialHitConfig {
                track_cache_stats: true,
                ..Default::default()
            },
        );
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );

        // readonly doesn't update cache
        let _ = idx.hit_test_readonly(5, 5);
        assert_eq!(idx.stats().hits, 0);
        assert_eq!(idx.stats().misses, 0);

        // mutable query at same position should be a miss
        let _ = idx.hit_test(5, 5);
        assert_eq!(idx.stats().misses, 1);
    }

    // --- Invalidation edge cases ---

    #[test]
    fn invalidate_region_zero_size() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );
        let _ = idx.hit_test(5, 5);
        assert!(idx.cache.valid);

        // Zero-size rect shouldn't invalidate anything
        idx.invalidate_region(Rect::new(5, 5, 0, 0));
        assert!(idx.cache.valid);
    }

    #[test]
    fn invalidate_region_outside_screen() {
        let mut idx = index();
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );
        let _ = idx.hit_test(5, 5);
        assert!(idx.cache.valid);

        // Region outside screen
        idx.invalidate_region(Rect::new(100, 100, 10, 10));
        // Cache position (5,5) is not in the dirty region, so cache stays valid
        assert!(idx.cache.valid);
    }

    // --- Rebuild tracking ---

    #[test]
    fn rebuild_counted_in_stats() {
        let mut idx = SpatialHitIndex::new(
            80,
            24,
            SpatialHitConfig {
                track_cache_stats: true,
                ..Default::default()
            },
        );
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );
        assert_eq!(idx.stats().rebuilds, 0);

        // Update triggers rebuild
        idx.update(HitId::new(1), Rect::new(10, 10, 5, 5));
        assert_eq!(idx.stats().rebuilds, 1);

        // Remove triggers rebuild
        idx.remove(HitId::new(1));
        assert_eq!(idx.stats().rebuilds, 2);
    }

    // --- Full lifecycle ---

    #[test]
    fn register_hit_update_hit_remove_clear() {
        let mut idx = index();

        // Register
        idx.register_simple(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            0,
        );
        assert_eq!(idx.len(), 1);

        // Hit
        assert!(idx.hit_test(5, 5).is_some());

        // Update
        idx.update(HitId::new(1), Rect::new(20, 20, 10, 10));
        assert!(idx.hit_test(5, 5).is_none());
        assert!(idx.hit_test(25, 22).is_some());

        // Remove
        idx.remove(HitId::new(1));
        assert!(idx.is_empty());
        assert!(idx.hit_test(25, 22).is_none());

        // Re-register
        idx.register_simple(HitId::new(2), Rect::new(0, 0, 5, 5), HitRegion::Button, 99);
        assert_eq!(idx.len(), 1);
        let r = idx.hit_test(2, 2);
        assert_eq!(r, Some((HitId::new(2), HitRegion::Button, 99)));

        // Clear
        idx.clear();
        assert!(idx.is_empty());
        assert!(idx.hit_test(2, 2).is_none());
    }

    // --- Z-order tie-breaking ---

    #[test]
    fn z_order_tie_broken_by_registration_order() {
        let mut idx = index();
        // Same z_order=5, different registration order
        idx.register(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            10,
            5,
        );
        idx.register(
            HitId::new(2),
            Rect::new(0, 0, 10, 10),
            HitRegion::Border,
            20,
            5,
        );
        idx.register(
            HitId::new(3),
            Rect::new(0, 0, 10, 10),
            HitRegion::Button,
            30,
            5,
        );

        // Widget 3 wins (latest registration at same z)
        let result = idx.hit_test(5, 5);
        assert_eq!(result, Some((HitId::new(3), HitRegion::Button, 30)));
    }

    #[test]
    fn z_order_higher_z_beats_later_registration() {
        let mut idx = index();
        // Widget 1: z=10, registered first
        idx.register(
            HitId::new(1),
            Rect::new(0, 0, 10, 10),
            HitRegion::Content,
            10,
            10,
        );
        // Widget 2: z=5, registered later
        idx.register(
            HitId::new(2),
            Rect::new(0, 0, 10, 10),
            HitRegion::Border,
            20,
            5,
        );

        // Widget 1 wins (higher z trumps registration order)
        let result = idx.hit_test(5, 5);
        assert_eq!(result, Some((HitId::new(1), HitRegion::Content, 10)));
    }

    // --- HitRegion variants in hit_test ---

    #[test]
    fn all_hit_region_variants_returned() {
        let mut idx = index();
        let regions = [
            (1, HitRegion::Content),
            (2, HitRegion::Border),
            (3, HitRegion::Scrollbar),
            (4, HitRegion::Handle),
            (5, HitRegion::Button),
            (6, HitRegion::Link),
            (7, HitRegion::Custom(42)),
        ];
        for (i, (id, region)) in regions.iter().enumerate() {
            let x = (i as u16) * 10;
            idx.register_simple(HitId::new(*id), Rect::new(x, 0, 5, 5), *region, *id as u64);
        }
        for (i, (id, region)) in regions.iter().enumerate() {
            let x = (i as u16) * 10 + 2;
            let result = idx.hit_test(x, 2);
            assert_eq!(
                result,
                Some((HitId::new(*id), *region, *id as u64)),
                "Failed for region {:?}",
                region
            );
        }
    }

    // --- Width=1 and Height=1 edge ---

    #[test]
    fn single_cell_screen() {
        let mut idx = SpatialHitIndex::with_defaults(1, 1);
        idx.register_simple(HitId::new(1), Rect::new(0, 0, 1, 1), HitRegion::Content, 0);
        assert!(idx.hit_test(0, 0).is_some());
        assert!(idx.hit_test(1, 0).is_none());
    }

    // --- Readonly equivalence across whole grid ---

    #[test]
    fn hit_test_readonly_equivalent_to_mutable_for_grid() {
        let mut idx = index();
        idx.register(
            HitId::new(1),
            Rect::new(0, 0, 40, 12),
            HitRegion::Content,
            1,
            0,
        );
        idx.register(
            HitId::new(2),
            Rect::new(30, 8, 20, 10),
            HitRegion::Border,
            2,
            1,
        );
        idx.register(
            HitId::new(3),
            Rect::new(60, 0, 20, 24),
            HitRegion::Button,
            3,
            2,
        );

        // Compare at grid of points
        for x in (0..80).step_by(5) {
            for y in (0..24).step_by(3) {
                let ro = idx.hit_test_readonly(x, y);
                let expected_id = ro.map(|(id, _, _)| id);
                // We can't use hit_test (mutates cache) in a fair comparison loop,
                // so just verify readonly is consistent with itself
                let ro2 = idx.hit_test_readonly(x, y);
                assert_eq!(ro, ro2, "Readonly inconsistency at ({x}, {y})");
                // Also verify against mutable
                let mut_result = idx.hit_test(x, y);
                let mut_id = mut_result.map(|(id, _, _)| id);
                assert_eq!(
                    expected_id, mut_id,
                    "Mutable/readonly mismatch at ({x}, {y})"
                );
            }
        }
    }
}