Skip to main content

ftui_render/
spatial_hit_index.rs

1#![forbid(unsafe_code)]
2
3//! Spatial hit-test index with z-order support and dirty-rect caching.
4//!
5//! Provides O(1) average-case hit-test queries for thousands of widgets
6//! by using uniform grid bucketing with z-order tracking.
7//!
8//! # Design
9//!
10//! Uses a hybrid approach:
11//! - **Uniform grid**: Screen divided into cells (default 8x8 pixels each)
12//! - **Bucket lists**: Each grid cell stores widget IDs that overlap it
13//! - **Z-order tracking**: Widgets have explicit z-order; topmost wins on overlap
14//! - **Dirty-rect cache**: Last hover result cached; invalidated on dirty regions
15//!
16//! # Invariants
17//!
18//! 1. Hit-test always returns topmost widget (highest z) at query point
19//! 2. Ties broken by registration order (later = on top)
20//! 3. Dirty regions force recomputation of affected buckets only
21//! 4. No allocations on steady-state hit-test queries
22//!
23//! # Failure Modes
24//!
25//! - Buckets are unbounded `Vec`s: pathological overlap degrades queries to
26//!   a per-bucket linear scan but never loses entries (there is no separate
27//!   fallback path).
28//! - `HitId::default()` (id 0) is reserved as the removed-entry sentinel;
29//!   [`SpatialHitIndex::register`] rejects it.
30//! - Re-registering an existing id replaces the previous entry.
31
32use crate::frame::{HitData, HitId, HitRegion};
33use ahash::AHashMap;
34use ftui_core::geometry::Rect;
35
36// ---------------------------------------------------------------------------
37// Configuration
38// ---------------------------------------------------------------------------
39
40/// Configuration for the spatial hit index.
41#[derive(Debug, Clone)]
42pub struct SpatialHitConfig {
43    /// Grid cell size in terminal cells (default: 8).
44    /// Smaller = more memory, faster queries. Larger = less memory, slower queries.
45    pub cell_size: u16,
46
47    /// Maximum widgets per bucket before logging warning (default: 64).
48    pub bucket_warn_threshold: usize,
49
50    /// Enable cache hit tracking for diagnostics (default: false).
51    pub track_cache_stats: bool,
52}
53
54impl Default for SpatialHitConfig {
55    fn default() -> Self {
56        Self {
57            cell_size: 8,
58            bucket_warn_threshold: 64,
59            track_cache_stats: false,
60        }
61    }
62}
63
64// ---------------------------------------------------------------------------
65// Widget hitbox entry
66// ---------------------------------------------------------------------------
67
68/// A registered widget's hit information.
69#[derive(Debug, Clone, Copy, PartialEq, Eq)]
70pub struct HitEntry {
71    /// Widget identifier.
72    pub id: HitId,
73    /// Bounding rectangle.
74    pub rect: Rect,
75    /// Region type for hit callbacks.
76    pub region: HitRegion,
77    /// User data attached to this hit.
78    pub data: HitData,
79    /// Z-order layer (higher = on top).
80    pub z_order: u16,
81    /// Registration order for tie-breaking.
82    order: u32,
83}
84
85impl HitEntry {
86    /// Create a new hit entry.
87    pub fn new(
88        id: HitId,
89        rect: Rect,
90        region: HitRegion,
91        data: HitData,
92        z_order: u16,
93        order: u32,
94    ) -> Self {
95        Self {
96            id,
97            rect,
98            region,
99            data,
100            z_order,
101            order,
102        }
103    }
104
105    /// Check if point (x, y) is inside this entry's rect.
106    #[inline]
107    pub fn contains(&self, x: u16, y: u16) -> bool {
108        x >= self.rect.x
109            && x < self.rect.x.saturating_add(self.rect.width)
110            && y >= self.rect.y
111            && y < self.rect.y.saturating_add(self.rect.height)
112    }
113
114    /// Compare for z-order (higher z wins, then later order wins).
115    #[inline]
116    fn cmp_z_order(&self, other: &Self) -> std::cmp::Ordering {
117        match self.z_order.cmp(&other.z_order) {
118            std::cmp::Ordering::Equal => self.order.cmp(&other.order),
119            ord => ord,
120        }
121    }
122}
123
124// ---------------------------------------------------------------------------
125// Bucket for grid cell
126// ---------------------------------------------------------------------------
127
128/// Bucket storing widget indices for a grid cell.
129#[derive(Debug, Clone, Default)]
130struct Bucket {
131    /// Indices into the entries array.
132    entries: Vec<u32>,
133}
134
135impl Bucket {
136    /// Add an entry index to this bucket.
137    #[inline]
138    fn push(&mut self, entry_idx: u32) {
139        self.entries.push(entry_idx);
140    }
141
142    /// Clear the bucket.
143    #[inline]
144    fn clear(&mut self) {
145        self.entries.clear();
146    }
147}
148
149// ---------------------------------------------------------------------------
150// Cache for hover results
151// ---------------------------------------------------------------------------
152
153/// Cached hover result to avoid recomputation.
154#[derive(Debug, Clone, Copy, Default)]
155struct HoverCache {
156    /// Last queried position.
157    pos: (u16, u16),
158    /// Cached result (entry index or None).
159    result: Option<u32>,
160    /// Whether cache is valid.
161    valid: bool,
162}
163
164// ---------------------------------------------------------------------------
165// Dirty region tracking
166// ---------------------------------------------------------------------------
167
168/// Dirty region tracker for incremental updates.
169#[derive(Debug, Clone, Default)]
170struct DirtyTracker {
171    /// Dirty rectangles pending processing.
172    dirty_rects: Vec<Rect>,
173    /// Whether entire index needs rebuild.
174    full_rebuild: bool,
175}
176
177impl DirtyTracker {
178    /// Mark a rectangle as dirty.
179    fn mark_dirty(&mut self, rect: Rect) {
180        if !self.full_rebuild {
181            self.dirty_rects.push(rect);
182        }
183    }
184
185    /// Mark entire index as dirty.
186    fn mark_full_rebuild(&mut self) {
187        self.full_rebuild = true;
188        self.dirty_rects.clear();
189    }
190
191    /// Clear dirty state after processing.
192    fn clear(&mut self) {
193        self.dirty_rects.clear();
194        self.full_rebuild = false;
195    }
196
197    /// Check if position overlaps any dirty region.
198    fn is_dirty(&self, x: u16, y: u16) -> bool {
199        if self.full_rebuild {
200            return true;
201        }
202        for rect in &self.dirty_rects {
203            if x >= rect.x
204                && x < rect.x.saturating_add(rect.width)
205                && y >= rect.y
206                && y < rect.y.saturating_add(rect.height)
207            {
208                return true;
209            }
210        }
211        false
212    }
213}
214
215// ---------------------------------------------------------------------------
216// Cache statistics
217// ---------------------------------------------------------------------------
218
219/// Diagnostic statistics for cache performance.
220#[derive(Debug, Clone, Copy, Default)]
221pub struct CacheStats {
222    /// Number of cache hits.
223    pub hits: u64,
224    /// Number of cache misses.
225    pub misses: u64,
226    /// Number of full index rebuilds.
227    pub rebuilds: u64,
228}
229
230impl CacheStats {
231    /// Cache hit rate as percentage.
232    #[must_use]
233    pub fn hit_rate(&self) -> f32 {
234        let total = self.hits + self.misses;
235        if total == 0 {
236            0.0
237        } else {
238            (self.hits as f32 / total as f32) * 100.0
239        }
240    }
241}
242
243// ---------------------------------------------------------------------------
244// SpatialHitIndex
245// ---------------------------------------------------------------------------
246
247/// Spatial index for efficient hit-testing with z-order support.
248///
249/// Provides O(1) average-case queries by bucketing widgets into a uniform grid.
250/// Supports dirty-rect caching to avoid recomputation of unchanged regions.
251#[derive(Debug)]
252pub struct SpatialHitIndex {
253    config: SpatialHitConfig,
254
255    /// Screen dimensions.
256    width: u16,
257    height: u16,
258
259    /// Grid dimensions (in buckets).
260    grid_width: u16,
261    grid_height: u16,
262
263    /// All registered hit entries.
264    entries: Vec<HitEntry>,
265
266    /// Spatial grid buckets (row-major).
267    buckets: Vec<Bucket>,
268
269    /// Registration counter for tie-breaking.
270    next_order: u32,
271
272    /// Hover cache.
273    cache: HoverCache,
274
275    /// Dirty region tracker.
276    dirty: DirtyTracker,
277
278    /// Diagnostic statistics.
279    stats: CacheStats,
280
281    /// Fast lookup from HitId to entry index.
282    id_to_entry: AHashMap<HitId, u32>,
283}
284
285impl SpatialHitIndex {
286    /// Create a new spatial hit index for the given screen dimensions.
287    pub fn new(width: u16, height: u16, mut config: SpatialHitConfig) -> Self {
288        // Clamp into the *stored* config, not just into a local. `cell_size`
289        // is a public field on a public struct, so zero is reachable, and
290        // `bucket_index` and `bucket_range` both divide by
291        // `self.config.cell_size` - a clamp that only sized the grid left the
292        // whole query path dividing by zero, so `register` and `hit_test`
293        // panicked on an index that had constructed successfully.
294        config.cell_size = config.cell_size.max(1);
295        let cell_size = config.cell_size;
296        // Ceiling division in u32: the previous `saturating_add(cell-1)`
297        // destroyed the ceiling for width/height >= 65529, producing a grid
298        // one column/row short and out-of-bounds bucket indices.
299        let grid_width = u32::from(width).div_ceil(u32::from(cell_size)) as u16;
300        let grid_height = u32::from(height).div_ceil(u32::from(cell_size)) as u16;
301        let bucket_count = grid_width as usize * grid_height as usize;
302
303        Self {
304            config,
305            width,
306            height,
307            grid_width,
308            grid_height,
309            entries: Vec::with_capacity(256),
310            buckets: vec![Bucket::default(); bucket_count],
311            next_order: 0,
312            cache: HoverCache::default(),
313            dirty: DirtyTracker::default(),
314            stats: CacheStats::default(),
315            id_to_entry: AHashMap::with_capacity(256),
316        }
317    }
318
319    /// Create with default configuration.
320    pub fn with_defaults(width: u16, height: u16) -> Self {
321        Self::new(width, height, SpatialHitConfig::default())
322    }
323
324    /// Register a widget hitbox.
325    ///
326    /// # Arguments
327    ///
328    /// - `id`: Unique widget identifier
329    /// - `rect`: Bounding rectangle
330    /// - `region`: Hit region type
331    /// - `data`: User data
332    /// - `z_order`: Z-order layer (higher = on top)
333    pub fn register(
334        &mut self,
335        id: HitId,
336        rect: Rect,
337        region: HitRegion,
338        data: HitData,
339        z_order: u16,
340    ) {
341        // `HitId::default()` (id 0) is this index's removed-entry sentinel:
342        // hit_test skips it and rebuild_buckets compacts it away, so
343        // registering it would create a permanently unhittable entry.
344        // Reject it explicitly instead of corrupting silently (documented
345        // in the module's failure modes).
346        if id == HitId::default() {
347            return;
348        }
349
350        // Re-registering an id replaces the old entry. Without this, the
351        // stale entry stayed live in the buckets (a ghost hitbox), and
352        // rebuild_buckets would even resurrect it into id_to_entry after a
353        // remove().
354        if self.id_to_entry.contains_key(&id) {
355            self.remove(id);
356        }
357
358        // Create entry
359        let entry_idx = self.entries.len() as u32;
360        let entry = HitEntry::new(id, rect, region, data, z_order, self.next_order);
361        self.next_order = self.next_order.wrapping_add(1);
362
363        self.entries.push(entry);
364        self.id_to_entry.insert(id, entry_idx);
365
366        // Add to relevant buckets
367        self.add_to_buckets(entry_idx, rect);
368
369        // Invalidate cache for this region
370        self.dirty.mark_dirty(rect);
371        if self.cache.valid && self.dirty.is_dirty(self.cache.pos.0, self.cache.pos.1) {
372            self.cache.valid = false;
373        }
374    }
375
376    /// Register with default z-order (0).
377    pub fn register_simple(&mut self, id: HitId, rect: Rect, region: HitRegion, data: HitData) {
378        self.register(id, rect, region, data, 0);
379    }
380
381    /// Update an existing widget's hitbox.
382    ///
383    /// Returns `true` if widget was found and updated.
384    pub fn update(&mut self, id: HitId, new_rect: Rect) -> bool {
385        let Some(&entry_idx) = self.id_to_entry.get(&id) else {
386            return false;
387        };
388
389        let old_rect = self.entries[entry_idx as usize].rect;
390
391        // Mark both old and new regions as dirty
392        self.dirty.mark_dirty(old_rect);
393        self.dirty.mark_dirty(new_rect);
394
395        // Update entry
396        self.entries[entry_idx as usize].rect = new_rect;
397
398        // Rebuild buckets for affected regions
399        // For simplicity, we do a full rebuild. Production could do incremental.
400        self.rebuild_buckets();
401
402        // Invalidate cache
403        self.cache.valid = false;
404
405        true
406    }
407
408    /// Remove a widget from the index.
409    ///
410    /// Returns `true` if widget was found and removed.
411    pub fn remove(&mut self, id: HitId) -> bool {
412        let Some(&entry_idx) = self.id_to_entry.get(&id) else {
413            return false;
414        };
415
416        let rect = self.entries[entry_idx as usize].rect;
417        self.dirty.mark_dirty(rect);
418
419        // Mark entry as removed (set id to default)
420        self.entries[entry_idx as usize].id = HitId::default();
421        self.id_to_entry.remove(&id);
422
423        // Rebuild buckets
424        self.rebuild_buckets();
425        self.cache.valid = false;
426
427        true
428    }
429
430    /// Hit test at the given position.
431    ///
432    /// Returns the topmost (highest z-order) widget at (x, y), if any.
433    ///
434    /// # Performance
435    ///
436    /// - O(1) average case with cache hit
437    /// - O(k) where k = widgets overlapping the bucket cell
438    #[must_use]
439    pub fn hit_test(&mut self, x: u16, y: u16) -> Option<(HitId, HitRegion, HitData)> {
440        // Bounds check
441        if x >= self.width || y >= self.height {
442            return None;
443        }
444
445        // Check cache
446        if self.cache.valid && self.cache.pos == (x, y) {
447            if self.config.track_cache_stats {
448                self.stats.hits += 1;
449            }
450            return self.cache.result.map(|idx| {
451                let e = &self.entries[idx as usize];
452                (e.id, e.region, e.data)
453            });
454        }
455
456        if self.config.track_cache_stats {
457            self.stats.misses += 1;
458        }
459
460        // Find bucket
461        let bucket_idx = self.bucket_index(x, y);
462        let bucket = &self.buckets[bucket_idx];
463
464        // Find topmost widget at (x, y)
465        let mut best: Option<&HitEntry> = None;
466        let mut best_idx: Option<u32> = None;
467
468        for &entry_idx in &bucket.entries {
469            let entry = &self.entries[entry_idx as usize];
470
471            // Skip removed entries
472            if entry.id == HitId::default() {
473                continue;
474            }
475
476            // Check if point is inside this entry
477            if entry.contains(x, y) {
478                // Compare z-order
479                match best {
480                    None => {
481                        best = Some(entry);
482                        best_idx = Some(entry_idx);
483                    }
484                    Some(current_best) if entry.cmp_z_order(current_best).is_gt() => {
485                        best = Some(entry);
486                        best_idx = Some(entry_idx);
487                    }
488                    _ => {}
489                }
490            }
491        }
492
493        // Update cache
494        self.cache.pos = (x, y);
495        self.cache.result = best_idx;
496        self.cache.valid = true;
497        // The cache now reflects the current index state, so prior dirties are irrelevant.
498        self.dirty.clear();
499
500        best.map(|e| (e.id, e.region, e.data))
501    }
502
503    /// Hit test without modifying cache (for read-only queries).
504    #[must_use]
505    pub fn hit_test_readonly(&self, x: u16, y: u16) -> Option<(HitId, HitRegion, HitData)> {
506        if x >= self.width || y >= self.height {
507            return None;
508        }
509
510        let bucket_idx = self.bucket_index(x, y);
511        let bucket = &self.buckets[bucket_idx];
512
513        let mut best: Option<&HitEntry> = None;
514
515        for &entry_idx in &bucket.entries {
516            let entry = &self.entries[entry_idx as usize];
517            if entry.id == HitId::default() {
518                continue;
519            }
520            if entry.contains(x, y) {
521                match best {
522                    None => best = Some(entry),
523                    Some(current_best) if entry.cmp_z_order(current_best).is_gt() => {
524                        best = Some(entry)
525                    }
526                    _ => {}
527                }
528            }
529        }
530
531        best.map(|e| (e.id, e.region, e.data))
532    }
533
534    /// Clear all entries and reset the index.
535    pub fn clear(&mut self) {
536        self.entries.clear();
537        self.id_to_entry.clear();
538        for bucket in &mut self.buckets {
539            bucket.clear();
540        }
541        self.next_order = 0;
542        self.cache.valid = false;
543        self.dirty.clear();
544    }
545
546    /// Get diagnostic statistics.
547    #[must_use]
548    pub fn stats(&self) -> CacheStats {
549        self.stats
550    }
551
552    /// Reset diagnostic statistics.
553    pub fn reset_stats(&mut self) {
554        self.stats = CacheStats::default();
555    }
556
557    /// Number of registered widgets.
558    #[inline]
559    #[must_use]
560    pub fn len(&self) -> usize {
561        self.id_to_entry.len()
562    }
563
564    /// Check if empty.
565    #[inline]
566    #[must_use]
567    pub fn is_empty(&self) -> bool {
568        self.id_to_entry.is_empty()
569    }
570
571    /// Invalidate cache for a specific region.
572    pub fn invalidate_region(&mut self, rect: Rect) {
573        self.dirty.mark_dirty(rect);
574        if self.cache.valid && self.dirty.is_dirty(self.cache.pos.0, self.cache.pos.1) {
575            self.cache.valid = false;
576        }
577    }
578
579    /// Force full cache invalidation.
580    pub fn invalidate_all(&mut self) {
581        self.cache.valid = false;
582        self.dirty.mark_full_rebuild();
583    }
584
585    // -----------------------------------------------------------------------
586    // Internal helpers
587    // -----------------------------------------------------------------------
588
589    /// Calculate bucket index for a point.
590    ///
591    /// Clamped to the grid like [`bucket_range`](Self::bucket_range), so a
592    /// point inside screen bounds can never index past the bucket vec.
593    #[inline]
594    fn bucket_index(&self, x: u16, y: u16) -> usize {
595        let cell_size = self.config.cell_size;
596        let bx = (x / cell_size).min(self.grid_width.saturating_sub(1));
597        let by = (y / cell_size).min(self.grid_height.saturating_sub(1));
598        by as usize * self.grid_width as usize + bx as usize
599    }
600
601    /// Calculate bucket range for a rectangle.
602    fn bucket_range(&self, rect: Rect) -> (u16, u16, u16, u16) {
603        let cell_size = self.config.cell_size;
604        let bx_start = rect.x / cell_size;
605        let by_start = rect.y / cell_size;
606        let bx_end = rect.x.saturating_add(rect.width.saturating_sub(1)) / cell_size;
607        let by_end = rect.y.saturating_add(rect.height.saturating_sub(1)) / cell_size;
608        (
609            bx_start.min(self.grid_width.saturating_sub(1)),
610            by_start.min(self.grid_height.saturating_sub(1)),
611            bx_end.min(self.grid_width.saturating_sub(1)),
612            by_end.min(self.grid_height.saturating_sub(1)),
613        )
614    }
615
616    /// Add an entry to all buckets it overlaps.
617    fn add_to_buckets(&mut self, entry_idx: u32, rect: Rect) {
618        if rect.width == 0 || rect.height == 0 {
619            return;
620        }
621
622        let (bx_start, by_start, bx_end, by_end) = self.bucket_range(rect);
623
624        for by in by_start..=by_end {
625            for bx in bx_start..=bx_end {
626                let bucket_idx = by as usize * self.grid_width as usize + bx as usize;
627                if bucket_idx < self.buckets.len() {
628                    self.buckets[bucket_idx].push(entry_idx);
629
630                    // Warn if bucket is getting large
631                    if self.buckets[bucket_idx].entries.len() > self.config.bucket_warn_threshold {
632                        // In production, log this
633                    }
634                }
635            }
636        }
637    }
638
639    /// Rebuild all buckets from entries, compacting storage.
640    fn rebuild_buckets(&mut self) {
641        // Clear all buckets
642        for bucket in &mut self.buckets {
643            bucket.clear();
644        }
645
646        // Compact entries in-place to remove dead slots (HitId::default())
647        let mut valid_idx = 0;
648        for i in 0..self.entries.len() {
649            if self.entries[i].id != HitId::default() {
650                if i != valid_idx {
651                    self.entries[valid_idx] = self.entries[i];
652                }
653                valid_idx += 1;
654            }
655        }
656        self.entries.truncate(valid_idx);
657
658        // Rebuild lookup map from compacted entries
659        self.id_to_entry.clear();
660        for (idx, entry) in self.entries.iter().enumerate() {
661            self.id_to_entry.insert(entry.id, idx as u32);
662        }
663
664        // Rebuild buckets by iterating over entry indices to avoid borrowing
665        // the entire entries vector while modifying buckets.
666        for idx in 0..self.entries.len() {
667            let rect = self.entries[idx].rect;
668            self.add_to_buckets_internal(idx as u32, rect);
669        }
670
671        self.dirty.clear();
672        self.stats.rebuilds += 1;
673    }
674
675    /// Add entry to buckets (internal, doesn't modify dirty tracker).
676    fn add_to_buckets_internal(&mut self, entry_idx: u32, rect: Rect) {
677        if rect.width == 0 || rect.height == 0 {
678            return;
679        }
680
681        let (bx_start, by_start, bx_end, by_end) = self.bucket_range(rect);
682
683        for by in by_start..=by_end {
684            for bx in bx_start..=bx_end {
685                let bucket_idx = by as usize * self.grid_width as usize + bx as usize;
686                if bucket_idx < self.buckets.len() {
687                    self.buckets[bucket_idx].push(entry_idx);
688                }
689            }
690        }
691    }
692}
693
694// ---------------------------------------------------------------------------
695// Tests
696// ---------------------------------------------------------------------------
697
698#[cfg(test)]
699mod tests {
700    use super::*;
701
702    fn index() -> SpatialHitIndex {
703        SpatialHitIndex::with_defaults(80, 24)
704    }
705
706    // --- Regressions (exploration-audit round 7) ---
707
708    #[test]
709    fn u16_max_dimensions_do_not_panic_or_miss_hits() {
710        // Regression: saturating_add destroyed the ceiling division for
711        // width >= 65529, making the bucket grid one column short —
712        // hit_test near the right edge indexed out of bounds (1-row grids)
713        // or read the wrong bucket and returned None inside a widget.
714        let mut idx = SpatialHitIndex::with_defaults(u16::MAX, 8);
715        idx.register_simple(
716            HitId::new(1),
717            Rect::new(65520, 0, 15, 8),
718            HitRegion::Button,
719            0,
720        );
721        assert!(
722            idx.hit_test(65530, 5).is_some(),
723            "hit inside the widget at extreme x must resolve"
724        );
725
726        let mut idx = SpatialHitIndex::with_defaults(u16::MAX, 24);
727        idx.register_simple(
728            HitId::new(2),
729            Rect::new(65520, 0, 15, 8),
730            HitRegion::Button,
731            0,
732        );
733        assert_eq!(
734            idx.hit_test(65530, 0).map(|(id, _, _)| id),
735            Some(HitId::new(2))
736        );
737    }
738
739    #[test]
740    fn reregistering_id_replaces_old_entry() {
741        // Regression: re-registering an id left the old entry live in the
742        // buckets (ghost hitbox), and rebuild_buckets resurrected it into
743        // id_to_entry after remove().
744        let mut idx = index();
745        idx.register_simple(HitId::new(1), Rect::new(0, 0, 5, 5), HitRegion::Button, 7);
746        idx.register_simple(HitId::new(1), Rect::new(20, 10, 5, 5), HitRegion::Button, 9);
747        assert_eq!(idx.len(), 1);
748        assert!(
749            idx.hit_test(2, 2).is_none(),
750            "old location must not be a ghost hitbox"
751        );
752        let hit = idx.hit_test(22, 12).expect("new location must hit");
753        assert_eq!(hit.2, 9, "data must come from the replacement entry");
754
755        // remove() must kill the entry for good — no resurrection.
756        assert!(idx.remove(HitId::new(1)));
757        assert!(idx.hit_test(22, 12).is_none());
758        assert!(idx.hit_test(2, 2).is_none());
759        assert_eq!(idx.len(), 0);
760    }
761
762    #[test]
763    fn hit_id_zero_is_rejected_not_silently_unhittable() {
764        let mut idx = index();
765        idx.register_simple(
766            HitId::default(),
767            Rect::new(0, 0, 10, 10),
768            HitRegion::Button,
769            7,
770        );
771        assert_eq!(idx.len(), 0, "sentinel id must not create an entry");
772        assert!(idx.hit_test(5, 5).is_none());
773    }
774
775    // --- Basic functionality ---
776
777    #[test]
778    fn initial_state_empty() {
779        let idx = index();
780        assert!(idx.is_empty());
781        assert_eq!(idx.len(), 0);
782    }
783
784    #[test]
785    fn register_and_hit_test() {
786        let mut idx = index();
787        idx.register_simple(
788            HitId::new(1),
789            Rect::new(10, 5, 20, 3),
790            HitRegion::Button,
791            42,
792        );
793
794        // Inside rect
795        let result = idx.hit_test(15, 6);
796        assert_eq!(result, Some((HitId::new(1), HitRegion::Button, 42)));
797
798        // Outside rect
799        assert!(idx.hit_test(5, 5).is_none());
800        assert!(idx.hit_test(35, 5).is_none());
801    }
802
803    #[test]
804    fn z_order_topmost_wins() {
805        let mut idx = index();
806
807        // Register two overlapping widgets with different z-order
808        idx.register(
809            HitId::new(1),
810            Rect::new(0, 0, 10, 10),
811            HitRegion::Content,
812            1,
813            0, // Lower z
814        );
815        idx.register(
816            HitId::new(2),
817            Rect::new(5, 5, 10, 10),
818            HitRegion::Border,
819            2,
820            1, // Higher z
821        );
822
823        // In overlap region, widget 2 should win (higher z)
824        let result = idx.hit_test(7, 7);
825        assert_eq!(result, Some((HitId::new(2), HitRegion::Border, 2)));
826
827        // In widget 1 only region
828        let result = idx.hit_test(2, 2);
829        assert_eq!(result, Some((HitId::new(1), HitRegion::Content, 1)));
830    }
831
832    #[test]
833    fn same_z_order_later_wins() {
834        let mut idx = index();
835
836        // Same z-order, later registration wins
837        idx.register(
838            HitId::new(1),
839            Rect::new(0, 0, 10, 10),
840            HitRegion::Content,
841            1,
842            0,
843        );
844        idx.register(
845            HitId::new(2),
846            Rect::new(5, 5, 10, 10),
847            HitRegion::Border,
848            2,
849            0,
850        );
851
852        // In overlap, widget 2 (later) should win
853        let result = idx.hit_test(7, 7);
854        assert_eq!(result, Some((HitId::new(2), HitRegion::Border, 2)));
855    }
856
857    #[test]
858    fn hit_test_border_inclusive() {
859        let mut idx = index();
860        idx.register_simple(
861            HitId::new(1),
862            Rect::new(10, 10, 5, 5),
863            HitRegion::Content,
864            0,
865        );
866
867        // Corners should hit
868        assert!(idx.hit_test(10, 10).is_some()); // Top-left
869        assert!(idx.hit_test(14, 10).is_some()); // Top-right
870        assert!(idx.hit_test(10, 14).is_some()); // Bottom-left
871        assert!(idx.hit_test(14, 14).is_some()); // Bottom-right
872
873        // Just outside should miss
874        assert!(idx.hit_test(15, 10).is_none()); // Right of rect
875        assert!(idx.hit_test(10, 15).is_none()); // Below rect
876        assert!(idx.hit_test(9, 10).is_none()); // Left of rect
877        assert!(idx.hit_test(10, 9).is_none()); // Above rect
878    }
879
880    #[test]
881    fn update_widget_rect() {
882        let mut idx = index();
883        idx.register_simple(
884            HitId::new(1),
885            Rect::new(0, 0, 10, 10),
886            HitRegion::Content,
887            0,
888        );
889
890        // Should hit at original position
891        assert!(idx.hit_test(5, 5).is_some());
892
893        // Update position (staying within 80x24 bounds)
894        let updated = idx.update(HitId::new(1), Rect::new(50, 10, 10, 10));
895        assert!(updated);
896
897        // Should no longer hit at original position
898        assert!(idx.hit_test(5, 5).is_none());
899
900        // Should hit at new position
901        assert!(idx.hit_test(55, 15).is_some());
902    }
903
904    #[test]
905    fn remove_widget() {
906        let mut idx = index();
907        idx.register_simple(
908            HitId::new(1),
909            Rect::new(0, 0, 10, 10),
910            HitRegion::Content,
911            0,
912        );
913
914        assert!(idx.hit_test(5, 5).is_some());
915
916        let removed = idx.remove(HitId::new(1));
917        assert!(removed);
918
919        assert!(idx.hit_test(5, 5).is_none());
920        assert!(idx.is_empty());
921    }
922
923    #[test]
924    fn clear_all() {
925        let mut idx = index();
926        idx.register_simple(
927            HitId::new(1),
928            Rect::new(0, 0, 10, 10),
929            HitRegion::Content,
930            0,
931        );
932        idx.register_simple(
933            HitId::new(2),
934            Rect::new(20, 20, 10, 10),
935            HitRegion::Button,
936            1,
937        );
938
939        assert_eq!(idx.len(), 2);
940
941        idx.clear();
942
943        assert!(idx.is_empty());
944        assert!(idx.hit_test(5, 5).is_none());
945        assert!(idx.hit_test(25, 25).is_none());
946    }
947
948    // --- Cache tests ---
949
950    #[test]
951    fn cache_hit_on_same_position() {
952        let mut idx = SpatialHitIndex::new(
953            80,
954            24,
955            SpatialHitConfig {
956                track_cache_stats: true,
957                ..Default::default()
958            },
959        );
960        idx.register_simple(
961            HitId::new(1),
962            Rect::new(0, 0, 10, 10),
963            HitRegion::Content,
964            0,
965        );
966
967        // First query - miss
968        let _ = idx.hit_test(5, 5);
969        assert_eq!(idx.stats().misses, 1);
970        assert_eq!(idx.stats().hits, 0);
971
972        // Second query at same position - hit
973        let _ = idx.hit_test(5, 5);
974        assert_eq!(idx.stats().hits, 1);
975
976        // Query at different position - miss
977        let _ = idx.hit_test(7, 7);
978        assert_eq!(idx.stats().misses, 2);
979    }
980
981    #[test]
982    fn cache_invalidated_on_register() {
983        let mut idx = SpatialHitIndex::new(
984            80,
985            24,
986            SpatialHitConfig {
987                track_cache_stats: true,
988                ..Default::default()
989            },
990        );
991        idx.register_simple(
992            HitId::new(1),
993            Rect::new(0, 0, 10, 10),
994            HitRegion::Content,
995            0,
996        );
997
998        // Prime cache
999        let _ = idx.hit_test(5, 5);
1000
1001        // Register overlapping widget
1002        idx.register_simple(HitId::new(2), Rect::new(0, 0, 10, 10), HitRegion::Button, 1);
1003
1004        // Cache should be invalidated, so next query is a miss
1005        let hits_before = idx.stats().hits;
1006        let _ = idx.hit_test(5, 5);
1007        // Due to dirty tracking, cache is invalidated in overlapping region
1008        assert_eq!(idx.stats().hits, hits_before);
1009    }
1010
1011    // --- Property tests ---
1012
1013    #[test]
1014    fn property_random_layout_correctness() {
1015        let mut idx = index();
1016        let widgets = vec![
1017            (HitId::new(1), Rect::new(0, 0, 20, 10), 0u16),
1018            (HitId::new(2), Rect::new(10, 5, 20, 10), 1),
1019            (HitId::new(3), Rect::new(25, 0, 15, 15), 2),
1020        ];
1021
1022        for (id, rect, z) in &widgets {
1023            idx.register(*id, *rect, HitRegion::Content, id.id() as u64, *z);
1024        }
1025
1026        // Test multiple points
1027        for x in 0..60 {
1028            for y in 0..20 {
1029                let indexed_result = idx.hit_test_readonly(x, y);
1030
1031                // Compute expected result with naive O(n) scan
1032                let mut best: Option<(HitId, u16)> = None;
1033                for (id, rect, z) in &widgets {
1034                    if x >= rect.x
1035                        && x < rect.x + rect.width
1036                        && y >= rect.y
1037                        && y < rect.y + rect.height
1038                    {
1039                        match best {
1040                            None => best = Some((*id, *z)),
1041                            Some((_, best_z)) if *z > best_z => best = Some((*id, *z)),
1042                            _ => {}
1043                        }
1044                    }
1045                }
1046
1047                let expected_id = best.map(|(id, _)| id);
1048                let indexed_id = indexed_result.map(|(id, _, _)| id);
1049
1050                assert_eq!(
1051                    indexed_id, expected_id,
1052                    "Mismatch at ({}, {}): indexed={:?}, expected={:?}",
1053                    x, y, indexed_id, expected_id
1054                );
1055            }
1056        }
1057    }
1058
1059    // --- Edge cases ---
1060
1061    #[test]
1062    fn out_of_bounds_returns_none() {
1063        let mut idx = index();
1064        idx.register_simple(
1065            HitId::new(1),
1066            Rect::new(0, 0, 10, 10),
1067            HitRegion::Content,
1068            0,
1069        );
1070
1071        assert!(idx.hit_test(100, 100).is_none());
1072        assert!(idx.hit_test(80, 0).is_none());
1073        assert!(idx.hit_test(0, 24).is_none());
1074    }
1075
1076    #[test]
1077    fn zero_size_rect_ignored() {
1078        let mut idx = index();
1079        idx.register_simple(
1080            HitId::new(1),
1081            Rect::new(10, 10, 0, 0),
1082            HitRegion::Content,
1083            0,
1084        );
1085
1086        // Should not hit even at the exact position
1087        assert!(idx.hit_test(10, 10).is_none());
1088    }
1089
1090    #[test]
1091    fn large_rect_spans_many_buckets() {
1092        let mut idx = index();
1093        // Rect spans multiple buckets (80x24 with 8x8 cells = 10x3 buckets)
1094        idx.register_simple(
1095            HitId::new(1),
1096            Rect::new(0, 0, 80, 24),
1097            HitRegion::Content,
1098            0,
1099        );
1100
1101        // Should hit everywhere
1102        assert!(idx.hit_test(0, 0).is_some());
1103        assert!(idx.hit_test(40, 12).is_some());
1104        assert!(idx.hit_test(79, 23).is_some());
1105    }
1106
1107    #[test]
1108    fn update_nonexistent_returns_false() {
1109        let mut idx = index();
1110        let result = idx.update(HitId::new(999), Rect::new(0, 0, 10, 10));
1111        assert!(!result);
1112    }
1113
1114    #[test]
1115    fn remove_nonexistent_returns_false() {
1116        let mut idx = index();
1117        let result = idx.remove(HitId::new(999));
1118        assert!(!result);
1119    }
1120
1121    #[test]
1122    fn stats_hit_rate() {
1123        let mut stats = CacheStats::default();
1124        assert_eq!(stats.hit_rate(), 0.0);
1125
1126        stats.hits = 75;
1127        stats.misses = 25;
1128        assert!((stats.hit_rate() - 75.0).abs() < 0.01);
1129    }
1130
1131    #[test]
1132    fn config_defaults() {
1133        let config = SpatialHitConfig::default();
1134        assert_eq!(config.cell_size, 8);
1135        assert_eq!(config.bucket_warn_threshold, 64);
1136        assert!(!config.track_cache_stats);
1137    }
1138
1139    #[test]
1140    fn invalidate_region() {
1141        let mut idx = index();
1142        idx.register_simple(
1143            HitId::new(1),
1144            Rect::new(0, 0, 10, 10),
1145            HitRegion::Content,
1146            0,
1147        );
1148
1149        // Prime cache
1150        let _ = idx.hit_test(5, 5);
1151        assert!(idx.cache.valid);
1152
1153        // Invalidate region that includes cached position
1154        idx.invalidate_region(Rect::new(0, 0, 10, 10));
1155        assert!(!idx.cache.valid);
1156    }
1157
1158    #[test]
1159    fn invalidate_all() {
1160        let mut idx = index();
1161        idx.register_simple(
1162            HitId::new(1),
1163            Rect::new(0, 0, 10, 10),
1164            HitRegion::Content,
1165            0,
1166        );
1167
1168        let _ = idx.hit_test(5, 5);
1169        assert!(idx.cache.valid);
1170
1171        idx.invalidate_all();
1172        assert!(!idx.cache.valid);
1173    }
1174
1175    #[test]
1176    fn three_overlapping_widgets_z_order() {
1177        let mut idx = index();
1178        idx.register(
1179            HitId::new(1),
1180            Rect::new(0, 0, 20, 20),
1181            HitRegion::Content,
1182            10,
1183            0,
1184        );
1185        idx.register(
1186            HitId::new(2),
1187            Rect::new(5, 5, 15, 15),
1188            HitRegion::Border,
1189            20,
1190            2,
1191        );
1192        idx.register(
1193            HitId::new(3),
1194            Rect::new(8, 8, 10, 10),
1195            HitRegion::Button,
1196            30,
1197            1,
1198        );
1199        // At (10, 10): all three overlap; widget 2 has highest z=2
1200        let result = idx.hit_test(10, 10);
1201        assert_eq!(result, Some((HitId::new(2), HitRegion::Border, 20)));
1202    }
1203
1204    #[test]
1205    fn hit_test_readonly_matches_mutable() {
1206        let mut idx = index();
1207        idx.register_simple(
1208            HitId::new(1),
1209            Rect::new(5, 5, 10, 10),
1210            HitRegion::Content,
1211            0,
1212        );
1213        let mutable_result = idx.hit_test(8, 8);
1214        let readonly_result = idx.hit_test_readonly(8, 8);
1215        assert_eq!(mutable_result, readonly_result);
1216    }
1217
1218    #[test]
1219    fn single_pixel_widget() {
1220        let mut idx = index();
1221        idx.register_simple(HitId::new(1), Rect::new(5, 5, 1, 1), HitRegion::Button, 0);
1222        assert!(idx.hit_test(5, 5).is_some());
1223        assert!(idx.hit_test(6, 5).is_none());
1224        assert!(idx.hit_test(5, 6).is_none());
1225    }
1226
1227    #[test]
1228    fn clear_on_empty_is_idempotent() {
1229        let mut idx = index();
1230        idx.clear();
1231        assert!(idx.is_empty());
1232        idx.clear();
1233        assert!(idx.is_empty());
1234    }
1235
1236    #[test]
1237    fn register_remove_register_cycle() {
1238        let mut idx = index();
1239        idx.register_simple(
1240            HitId::new(1),
1241            Rect::new(0, 0, 10, 10),
1242            HitRegion::Content,
1243            0,
1244        );
1245        assert_eq!(idx.len(), 1);
1246        idx.remove(HitId::new(1));
1247        assert_eq!(idx.len(), 0);
1248        idx.register_simple(HitId::new(1), Rect::new(20, 20, 5, 5), HitRegion::Border, 0);
1249        assert_eq!(idx.len(), 1);
1250        // Should hit at new location, not old
1251        assert!(idx.hit_test(22, 22).is_some());
1252        assert!(idx.hit_test(5, 5).is_none());
1253    }
1254
1255    #[test]
1256    fn invalidate_non_overlapping_region_preserves_cache() {
1257        let mut idx = index();
1258        idx.register_simple(
1259            HitId::new(1),
1260            Rect::new(0, 0, 10, 10),
1261            HitRegion::Content,
1262            0,
1263        );
1264        let _ = idx.hit_test(5, 5);
1265        assert!(idx.cache.valid);
1266        // Invalidate a region that doesn't overlap the cached point
1267        idx.invalidate_region(Rect::new(50, 50, 10, 10));
1268        assert!(idx.cache.valid);
1269    }
1270
1271    #[test]
1272    fn hit_entry_contains() {
1273        let entry = HitEntry::new(
1274            HitId::new(1),
1275            Rect::new(10, 10, 20, 20),
1276            HitRegion::Content,
1277            0,
1278            0,
1279            0,
1280        );
1281        assert!(entry.contains(15, 15));
1282        assert!(entry.contains(10, 10));
1283        assert!(!entry.contains(9, 10));
1284        assert!(!entry.contains(30, 30));
1285    }
1286
1287    #[test]
1288    fn reset_stats_clears_counters() {
1289        let mut idx = SpatialHitIndex::new(
1290            80,
1291            24,
1292            SpatialHitConfig {
1293                cell_size: 8,
1294                bucket_warn_threshold: 64,
1295                track_cache_stats: true,
1296            },
1297        );
1298        idx.register_simple(
1299            HitId::new(1),
1300            Rect::new(0, 0, 10, 10),
1301            HitRegion::Content,
1302            0,
1303        );
1304        let _ = idx.hit_test(5, 5);
1305        let _ = idx.hit_test(5, 5); // cache hit
1306        let stats = idx.stats();
1307        assert!(stats.hits > 0 || stats.misses > 0);
1308        idx.reset_stats();
1309        let stats = idx.stats();
1310        assert_eq!(stats.hits, 0);
1311        assert_eq!(stats.misses, 0);
1312    }
1313
1314    // =========================================================================
1315    // Edge-Case Tests (bd-9bvp0)
1316    // =========================================================================
1317
1318    // --- SpatialHitConfig trait coverage ---
1319
1320    #[test]
1321    fn config_debug_clone() {
1322        let config = SpatialHitConfig::default();
1323        let dbg = format!("{:?}", config);
1324        assert!(dbg.contains("SpatialHitConfig"), "Debug: {dbg}");
1325        let cloned = config.clone();
1326        assert_eq!(cloned.cell_size, 8);
1327    }
1328
1329    // --- HitEntry trait coverage ---
1330
1331    #[test]
1332    fn hit_entry_debug_clone_copy_eq() {
1333        let entry = HitEntry::new(
1334            HitId::new(1),
1335            Rect::new(0, 0, 10, 10),
1336            HitRegion::Content,
1337            42,
1338            5,
1339            0,
1340        );
1341        let dbg = format!("{:?}", entry);
1342        assert!(dbg.contains("HitEntry"), "Debug: {dbg}");
1343        let copied = entry; // Copy
1344        assert_eq!(entry, copied);
1345        let cloned: HitEntry = entry; // Clone == Copy for this type
1346        assert_eq!(entry, cloned);
1347    }
1348
1349    #[test]
1350    fn hit_entry_ne() {
1351        let a = HitEntry::new(
1352            HitId::new(1),
1353            Rect::new(0, 0, 10, 10),
1354            HitRegion::Content,
1355            0,
1356            0,
1357            0,
1358        );
1359        let b = HitEntry::new(
1360            HitId::new(2),
1361            Rect::new(0, 0, 10, 10),
1362            HitRegion::Content,
1363            0,
1364            0,
1365            0,
1366        );
1367        assert_ne!(a, b);
1368    }
1369
1370    #[test]
1371    fn hit_entry_contains_zero_width() {
1372        let entry = HitEntry::new(
1373            HitId::new(1),
1374            Rect::new(10, 10, 0, 5),
1375            HitRegion::Content,
1376            0,
1377            0,
1378            0,
1379        );
1380        // Zero width: x >= 10 && x < 10+0=10 → always false
1381        assert!(!entry.contains(10, 10));
1382    }
1383
1384    #[test]
1385    fn hit_entry_contains_zero_height() {
1386        let entry = HitEntry::new(
1387            HitId::new(1),
1388            Rect::new(10, 10, 5, 0),
1389            HitRegion::Content,
1390            0,
1391            0,
1392            0,
1393        );
1394        assert!(!entry.contains(10, 10));
1395    }
1396
1397    #[test]
1398    fn hit_entry_contains_at_saturating_boundary() {
1399        // Rect near u16::MAX tests saturating_add
1400        let entry = HitEntry::new(
1401            HitId::new(1),
1402            Rect::new(u16::MAX - 5, u16::MAX - 5, 10, 10),
1403            HitRegion::Content,
1404            0,
1405            0,
1406            0,
1407        );
1408        // saturating_add: (65530 + 10).min(65535) = 65535
1409        // contains uses strict <, so u16::MAX is excluded
1410        assert!(entry.contains(u16::MAX - 5, u16::MAX - 5));
1411        assert!(entry.contains(u16::MAX - 1, u16::MAX - 1));
1412        assert!(!entry.contains(u16::MAX, u16::MAX));
1413    }
1414
1415    // --- CacheStats ---
1416
1417    #[test]
1418    fn cache_stats_default() {
1419        let stats = CacheStats::default();
1420        assert_eq!(stats.hits, 0);
1421        assert_eq!(stats.misses, 0);
1422        assert_eq!(stats.rebuilds, 0);
1423        assert_eq!(stats.hit_rate(), 0.0);
1424    }
1425
1426    #[test]
1427    fn cache_stats_debug_copy() {
1428        let stats = CacheStats {
1429            hits: 10,
1430            misses: 5,
1431            rebuilds: 1,
1432        };
1433        let dbg = format!("{:?}", stats);
1434        assert!(dbg.contains("CacheStats"), "Debug: {dbg}");
1435        let copy = stats; // Copy
1436        assert_eq!(copy.hits, stats.hits);
1437    }
1438
1439    #[test]
1440    fn cache_stats_100_percent_hit_rate() {
1441        let stats = CacheStats {
1442            hits: 100,
1443            misses: 0,
1444            rebuilds: 0,
1445        };
1446        assert!((stats.hit_rate() - 100.0).abs() < 0.01);
1447    }
1448
1449    #[test]
1450    fn cache_stats_0_percent_hit_rate() {
1451        let stats = CacheStats {
1452            hits: 0,
1453            misses: 100,
1454            rebuilds: 0,
1455        };
1456        assert!((stats.hit_rate()).abs() < 0.01);
1457    }
1458
1459    // --- SpatialHitIndex construction ---
1460
1461    #[test]
1462    fn new_with_cell_size_zero_clamped_to_one() {
1463        let config = SpatialHitConfig {
1464            cell_size: 0,
1465            ..Default::default()
1466        };
1467        let mut idx = SpatialHitIndex::new(80, 24, config);
1468        // cell_size=0 clamped to 1, grid = 80x24 buckets
1469        assert_eq!(idx.grid_width, 80);
1470        assert_eq!(idx.grid_height, 24);
1471        assert!(idx.is_empty());
1472
1473        // The clamp has to reach the query path too. `bucket_index` and
1474        // `bucket_range` divide by `self.config.cell_size`, so a clamp that
1475        // only sized the grid left both dividing by zero - and asserting on
1476        // the grid alone could not see it.
1477        assert_eq!(idx.config.cell_size, 1, "the stored config must be clamped");
1478        idx.register_simple(HitId::new(1), Rect::new(2, 3, 4, 2), HitRegion::Button, 7);
1479        assert_eq!(
1480            idx.hit_test(3, 4),
1481            Some((HitId::new(1), HitRegion::Button, 7))
1482        );
1483        assert_eq!(idx.hit_test(70, 20), None);
1484    }
1485
1486    #[test]
1487    fn new_with_cell_size_one() {
1488        let config = SpatialHitConfig {
1489            cell_size: 1,
1490            ..Default::default()
1491        };
1492        let idx = SpatialHitIndex::new(10, 5, config);
1493        // 1 bucket per cell
1494        assert_eq!(idx.grid_width, 10);
1495        assert_eq!(idx.grid_height, 5);
1496    }
1497
1498    #[test]
1499    fn new_with_large_cell_size() {
1500        let config = SpatialHitConfig {
1501            cell_size: 100,
1502            ..Default::default()
1503        };
1504        let idx = SpatialHitIndex::new(80, 24, config);
1505        // 80/100 rounds up to 1, 24/100 rounds up to 1
1506        assert_eq!(idx.grid_width, 1);
1507        assert_eq!(idx.grid_height, 1);
1508    }
1509
1510    #[test]
1511    fn new_zero_dimensions() {
1512        let idx = SpatialHitIndex::with_defaults(0, 0);
1513        assert!(idx.is_empty());
1514        // All hit tests should return None
1515        assert!(idx.hit_test_readonly(0, 0).is_none());
1516    }
1517
1518    #[test]
1519    fn with_defaults_uses_default_config() {
1520        let idx = SpatialHitIndex::with_defaults(80, 24);
1521        assert_eq!(idx.config.cell_size, 8);
1522        assert_eq!(idx.config.bucket_warn_threshold, 64);
1523        assert!(!idx.config.track_cache_stats);
1524    }
1525
1526    #[test]
1527    fn index_debug_format() {
1528        let idx = SpatialHitIndex::with_defaults(10, 10);
1529        let dbg = format!("{:?}", idx);
1530        assert!(dbg.contains("SpatialHitIndex"), "Debug: {dbg}");
1531    }
1532
1533    // --- Register edge cases ---
1534
1535    #[test]
1536    fn register_zero_width_rect_not_in_buckets() {
1537        let mut idx = index();
1538        idx.register_simple(HitId::new(1), Rect::new(5, 5, 0, 10), HitRegion::Content, 0);
1539        // Still registered (len=1) but won't be found by hit_test
1540        assert_eq!(idx.len(), 1);
1541        assert!(idx.hit_test(5, 5).is_none());
1542    }
1543
1544    #[test]
1545    fn register_zero_height_rect_not_in_buckets() {
1546        let mut idx = index();
1547        idx.register_simple(HitId::new(1), Rect::new(5, 5, 10, 0), HitRegion::Content, 0);
1548        assert_eq!(idx.len(), 1);
1549        assert!(idx.hit_test(5, 5).is_none());
1550    }
1551
1552    #[test]
1553    fn register_rect_extending_past_screen() {
1554        let mut idx = index();
1555        // Rect extends past 80x24 screen
1556        idx.register_simple(
1557            HitId::new(1),
1558            Rect::new(70, 20, 20, 10),
1559            HitRegion::Content,
1560            0,
1561        );
1562        // Should still hit within screen bounds
1563        assert!(idx.hit_test(75, 22).is_some());
1564        // Outside screen returns None
1565        assert!(idx.hit_test(85, 25).is_none());
1566    }
1567
1568    #[test]
1569    fn register_many_widgets() {
1570        let mut idx = index();
1571        for i in 0..100u32 {
1572            let x = (i % 8) as u16 * 10;
1573            let y = (i / 8) as u16 * 3;
1574            idx.register_simple(
1575                HitId::new(i + 1),
1576                Rect::new(x, y, 5, 2),
1577                HitRegion::Content,
1578                i as u64,
1579            );
1580        }
1581        assert_eq!(idx.len(), 100);
1582        // Spot check
1583        let result = idx.hit_test(2, 1);
1584        assert!(result.is_some());
1585    }
1586
1587    #[test]
1588    fn register_simple_uses_z_order_zero() {
1589        let mut idx = index();
1590        idx.register_simple(
1591            HitId::new(1),
1592            Rect::new(0, 0, 10, 10),
1593            HitRegion::Content,
1594            0,
1595        );
1596        // Register with explicit z=1 in same area
1597        idx.register(
1598            HitId::new(2),
1599            Rect::new(0, 0, 10, 10),
1600            HitRegion::Border,
1601            0,
1602            1,
1603        );
1604        // Widget 2 should win (z=1 > z=0)
1605        let result = idx.hit_test(5, 5);
1606        assert_eq!(result, Some((HitId::new(2), HitRegion::Border, 0)));
1607    }
1608
1609    // --- Update edge cases ---
1610
1611    #[test]
1612    fn update_to_zero_size_rect() {
1613        let mut idx = index();
1614        idx.register_simple(
1615            HitId::new(1),
1616            Rect::new(0, 0, 10, 10),
1617            HitRegion::Content,
1618            0,
1619        );
1620        assert!(idx.hit_test(5, 5).is_some());
1621
1622        idx.update(HitId::new(1), Rect::new(0, 0, 0, 0));
1623        // Zero-size rect won't be in buckets
1624        assert!(idx.hit_test(0, 0).is_none());
1625    }
1626
1627    #[test]
1628    fn update_shrinks_widget() {
1629        let mut idx = index();
1630        idx.register_simple(
1631            HitId::new(1),
1632            Rect::new(0, 0, 20, 20),
1633            HitRegion::Content,
1634            0,
1635        );
1636        assert!(idx.hit_test(15, 15).is_some());
1637
1638        idx.update(HitId::new(1), Rect::new(0, 0, 5, 5));
1639        assert!(idx.hit_test(15, 15).is_none());
1640        assert!(idx.hit_test(2, 2).is_some());
1641    }
1642
1643    // --- Remove edge cases ---
1644
1645    #[test]
1646    fn remove_middle_entry_compacts() {
1647        let mut idx = index();
1648        idx.register_simple(HitId::new(1), Rect::new(0, 0, 5, 5), HitRegion::Content, 10);
1649        idx.register_simple(
1650            HitId::new(2),
1651            Rect::new(10, 0, 5, 5),
1652            HitRegion::Content,
1653            20,
1654        );
1655        idx.register_simple(
1656            HitId::new(3),
1657            Rect::new(20, 0, 5, 5),
1658            HitRegion::Content,
1659            30,
1660        );
1661        assert_eq!(idx.len(), 3);
1662
1663        idx.remove(HitId::new(2));
1664        assert_eq!(idx.len(), 2);
1665
1666        // Widget 1 and 3 should still work
1667        let r1 = idx.hit_test(2, 2);
1668        assert_eq!(r1, Some((HitId::new(1), HitRegion::Content, 10)));
1669        let r3 = idx.hit_test(22, 2);
1670        assert_eq!(r3, Some((HitId::new(3), HitRegion::Content, 30)));
1671    }
1672
1673    #[test]
1674    fn double_remove_returns_false() {
1675        let mut idx = index();
1676        idx.register_simple(
1677            HitId::new(1),
1678            Rect::new(0, 0, 10, 10),
1679            HitRegion::Content,
1680            0,
1681        );
1682        assert!(idx.remove(HitId::new(1)));
1683        assert!(!idx.remove(HitId::new(1)));
1684    }
1685
1686    // --- hit_test edge cases ---
1687
1688    #[test]
1689    fn hit_test_at_exact_screen_boundary() {
1690        let mut idx = index(); // 80x24
1691        idx.register_simple(
1692            HitId::new(1),
1693            Rect::new(70, 20, 10, 4),
1694            HitRegion::Content,
1695            0,
1696        );
1697        // Last valid pixel
1698        assert!(idx.hit_test(79, 23).is_some());
1699        // One past screen
1700        assert!(idx.hit_test(80, 23).is_none());
1701        assert!(idx.hit_test(79, 24).is_none());
1702    }
1703
1704    #[test]
1705    fn hit_test_at_grid_cell_boundaries() {
1706        let mut idx = index(); // cell_size=8
1707        idx.register_simple(
1708            HitId::new(1),
1709            Rect::new(6, 6, 4, 4), // spans cells (0,0) and (1,1)
1710            HitRegion::Content,
1711            0,
1712        );
1713        // At x=7,y=7 (cell 0,0) - should hit
1714        assert!(idx.hit_test(7, 7).is_some());
1715        // At x=8,y=8 (cell 1,1) - should hit
1716        assert!(idx.hit_test(8, 8).is_some());
1717        // At x=9,y=9 (cell 1,1) - should hit
1718        assert!(idx.hit_test(9, 9).is_some());
1719        // At x=10,y=10 (cell 1,1) - outside rect
1720        assert!(idx.hit_test(10, 10).is_none());
1721    }
1722
1723    #[test]
1724    fn hit_test_readonly_out_of_bounds() {
1725        let idx = index();
1726        assert!(idx.hit_test_readonly(80, 0).is_none());
1727        assert!(idx.hit_test_readonly(0, 24).is_none());
1728        assert!(idx.hit_test_readonly(u16::MAX, u16::MAX).is_none());
1729    }
1730
1731    #[test]
1732    fn hit_test_readonly_skips_removed() {
1733        let mut idx = index();
1734        idx.register_simple(
1735            HitId::new(1),
1736            Rect::new(0, 0, 10, 10),
1737            HitRegion::Content,
1738            0,
1739        );
1740        idx.register_simple(HitId::new(2), Rect::new(0, 0, 10, 10), HitRegion::Border, 1);
1741        idx.remove(HitId::new(2));
1742        // Widget 1 should still be found
1743        let result = idx.hit_test_readonly(5, 5);
1744        assert_eq!(result, Some((HitId::new(1), HitRegion::Content, 0)));
1745    }
1746
1747    // --- Cache behavior ---
1748
1749    #[test]
1750    fn cache_updates_on_different_positions() {
1751        let mut idx = SpatialHitIndex::new(
1752            80,
1753            24,
1754            SpatialHitConfig {
1755                track_cache_stats: true,
1756                ..Default::default()
1757            },
1758        );
1759        idx.register_simple(
1760            HitId::new(1),
1761            Rect::new(0, 0, 40, 12),
1762            HitRegion::Content,
1763            1,
1764        );
1765        idx.register_simple(
1766            HitId::new(2),
1767            Rect::new(40, 12, 40, 12),
1768            HitRegion::Border,
1769            2,
1770        );
1771
1772        // First query
1773        let r1 = idx.hit_test(5, 5);
1774        assert_eq!(r1, Some((HitId::new(1), HitRegion::Content, 1)));
1775        assert_eq!(idx.stats().misses, 1);
1776
1777        // Different position - miss
1778        let r2 = idx.hit_test(50, 15);
1779        assert_eq!(r2, Some((HitId::new(2), HitRegion::Border, 2)));
1780        assert_eq!(idx.stats().misses, 2);
1781
1782        // Back to first position - miss (cache only stores one position)
1783        let _ = idx.hit_test(5, 5);
1784        assert_eq!(idx.stats().misses, 3);
1785    }
1786
1787    #[test]
1788    fn cache_invalidated_by_invalidate_all_then_same_position() {
1789        let mut idx = SpatialHitIndex::new(
1790            80,
1791            24,
1792            SpatialHitConfig {
1793                track_cache_stats: true,
1794                ..Default::default()
1795            },
1796        );
1797        idx.register_simple(
1798            HitId::new(1),
1799            Rect::new(0, 0, 10, 10),
1800            HitRegion::Content,
1801            0,
1802        );
1803
1804        // Prime cache
1805        let _ = idx.hit_test(5, 5);
1806        assert_eq!(idx.stats().misses, 1);
1807        assert_eq!(idx.stats().hits, 0);
1808
1809        // Invalidate all then query same position
1810        idx.invalidate_all();
1811        let _ = idx.hit_test(5, 5);
1812        // Should be a miss since cache was invalidated
1813        assert_eq!(idx.stats().misses, 2);
1814    }
1815
1816    #[test]
1817    fn cache_not_updated_by_readonly() {
1818        let mut idx = SpatialHitIndex::new(
1819            80,
1820            24,
1821            SpatialHitConfig {
1822                track_cache_stats: true,
1823                ..Default::default()
1824            },
1825        );
1826        idx.register_simple(
1827            HitId::new(1),
1828            Rect::new(0, 0, 10, 10),
1829            HitRegion::Content,
1830            0,
1831        );
1832
1833        // readonly doesn't update cache
1834        let _ = idx.hit_test_readonly(5, 5);
1835        assert_eq!(idx.stats().hits, 0);
1836        assert_eq!(idx.stats().misses, 0);
1837
1838        // mutable query at same position should be a miss
1839        let _ = idx.hit_test(5, 5);
1840        assert_eq!(idx.stats().misses, 1);
1841    }
1842
1843    // --- Invalidation edge cases ---
1844
1845    #[test]
1846    fn invalidate_region_zero_size() {
1847        let mut idx = index();
1848        idx.register_simple(
1849            HitId::new(1),
1850            Rect::new(0, 0, 10, 10),
1851            HitRegion::Content,
1852            0,
1853        );
1854        let _ = idx.hit_test(5, 5);
1855        assert!(idx.cache.valid);
1856
1857        // Zero-size rect shouldn't invalidate anything
1858        idx.invalidate_region(Rect::new(5, 5, 0, 0));
1859        assert!(idx.cache.valid);
1860    }
1861
1862    #[test]
1863    fn invalidate_region_outside_screen() {
1864        let mut idx = index();
1865        idx.register_simple(
1866            HitId::new(1),
1867            Rect::new(0, 0, 10, 10),
1868            HitRegion::Content,
1869            0,
1870        );
1871        let _ = idx.hit_test(5, 5);
1872        assert!(idx.cache.valid);
1873
1874        // Region outside screen
1875        idx.invalidate_region(Rect::new(100, 100, 10, 10));
1876        // Cache position (5,5) is not in the dirty region, so cache stays valid
1877        assert!(idx.cache.valid);
1878    }
1879
1880    // --- Rebuild tracking ---
1881
1882    #[test]
1883    fn rebuild_counted_in_stats() {
1884        let mut idx = SpatialHitIndex::new(
1885            80,
1886            24,
1887            SpatialHitConfig {
1888                track_cache_stats: true,
1889                ..Default::default()
1890            },
1891        );
1892        idx.register_simple(
1893            HitId::new(1),
1894            Rect::new(0, 0, 10, 10),
1895            HitRegion::Content,
1896            0,
1897        );
1898        assert_eq!(idx.stats().rebuilds, 0);
1899
1900        // Update triggers rebuild
1901        idx.update(HitId::new(1), Rect::new(10, 10, 5, 5));
1902        assert_eq!(idx.stats().rebuilds, 1);
1903
1904        // Remove triggers rebuild
1905        idx.remove(HitId::new(1));
1906        assert_eq!(idx.stats().rebuilds, 2);
1907    }
1908
1909    // --- Full lifecycle ---
1910
1911    #[test]
1912    fn register_hit_update_hit_remove_clear() {
1913        let mut idx = index();
1914
1915        // Register
1916        idx.register_simple(
1917            HitId::new(1),
1918            Rect::new(0, 0, 10, 10),
1919            HitRegion::Content,
1920            0,
1921        );
1922        assert_eq!(idx.len(), 1);
1923
1924        // Hit
1925        assert!(idx.hit_test(5, 5).is_some());
1926
1927        // Update
1928        idx.update(HitId::new(1), Rect::new(20, 20, 10, 10));
1929        assert!(idx.hit_test(5, 5).is_none());
1930        assert!(idx.hit_test(25, 22).is_some());
1931
1932        // Remove
1933        idx.remove(HitId::new(1));
1934        assert!(idx.is_empty());
1935        assert!(idx.hit_test(25, 22).is_none());
1936
1937        // Re-register
1938        idx.register_simple(HitId::new(2), Rect::new(0, 0, 5, 5), HitRegion::Button, 99);
1939        assert_eq!(idx.len(), 1);
1940        let r = idx.hit_test(2, 2);
1941        assert_eq!(r, Some((HitId::new(2), HitRegion::Button, 99)));
1942
1943        // Clear
1944        idx.clear();
1945        assert!(idx.is_empty());
1946        assert!(idx.hit_test(2, 2).is_none());
1947    }
1948
1949    // --- Z-order tie-breaking ---
1950
1951    #[test]
1952    fn z_order_tie_broken_by_registration_order() {
1953        let mut idx = index();
1954        // Same z_order=5, different registration order
1955        idx.register(
1956            HitId::new(1),
1957            Rect::new(0, 0, 10, 10),
1958            HitRegion::Content,
1959            10,
1960            5,
1961        );
1962        idx.register(
1963            HitId::new(2),
1964            Rect::new(0, 0, 10, 10),
1965            HitRegion::Border,
1966            20,
1967            5,
1968        );
1969        idx.register(
1970            HitId::new(3),
1971            Rect::new(0, 0, 10, 10),
1972            HitRegion::Button,
1973            30,
1974            5,
1975        );
1976
1977        // Widget 3 wins (latest registration at same z)
1978        let result = idx.hit_test(5, 5);
1979        assert_eq!(result, Some((HitId::new(3), HitRegion::Button, 30)));
1980    }
1981
1982    #[test]
1983    fn z_order_higher_z_beats_later_registration() {
1984        let mut idx = index();
1985        // Widget 1: z=10, registered first
1986        idx.register(
1987            HitId::new(1),
1988            Rect::new(0, 0, 10, 10),
1989            HitRegion::Content,
1990            10,
1991            10,
1992        );
1993        // Widget 2: z=5, registered later
1994        idx.register(
1995            HitId::new(2),
1996            Rect::new(0, 0, 10, 10),
1997            HitRegion::Border,
1998            20,
1999            5,
2000        );
2001
2002        // Widget 1 wins (higher z trumps registration order)
2003        let result = idx.hit_test(5, 5);
2004        assert_eq!(result, Some((HitId::new(1), HitRegion::Content, 10)));
2005    }
2006
2007    // --- HitRegion variants in hit_test ---
2008
2009    #[test]
2010    fn all_hit_region_variants_returned() {
2011        let mut idx = index();
2012        let regions = [
2013            (1, HitRegion::Content),
2014            (2, HitRegion::Border),
2015            (3, HitRegion::Scrollbar),
2016            (4, HitRegion::Handle),
2017            (5, HitRegion::Button),
2018            (6, HitRegion::Link),
2019            (7, HitRegion::Custom(42)),
2020        ];
2021        for (i, (id, region)) in regions.iter().enumerate() {
2022            let x = (i as u16) * 10;
2023            idx.register_simple(HitId::new(*id), Rect::new(x, 0, 5, 5), *region, *id as u64);
2024        }
2025        for (i, (id, region)) in regions.iter().enumerate() {
2026            let x = (i as u16) * 10 + 2;
2027            let result = idx.hit_test(x, 2);
2028            assert_eq!(
2029                result,
2030                Some((HitId::new(*id), *region, *id as u64)),
2031                "Failed for region {:?}",
2032                region
2033            );
2034        }
2035    }
2036
2037    // --- Width=1 and Height=1 edge ---
2038
2039    #[test]
2040    fn single_cell_screen() {
2041        let mut idx = SpatialHitIndex::with_defaults(1, 1);
2042        idx.register_simple(HitId::new(1), Rect::new(0, 0, 1, 1), HitRegion::Content, 0);
2043        assert!(idx.hit_test(0, 0).is_some());
2044        assert!(idx.hit_test(1, 0).is_none());
2045    }
2046
2047    // --- Readonly equivalence across whole grid ---
2048
2049    #[test]
2050    fn hit_test_readonly_equivalent_to_mutable_for_grid() {
2051        let mut idx = index();
2052        idx.register(
2053            HitId::new(1),
2054            Rect::new(0, 0, 40, 12),
2055            HitRegion::Content,
2056            1,
2057            0,
2058        );
2059        idx.register(
2060            HitId::new(2),
2061            Rect::new(30, 8, 20, 10),
2062            HitRegion::Border,
2063            2,
2064            1,
2065        );
2066        idx.register(
2067            HitId::new(3),
2068            Rect::new(60, 0, 20, 24),
2069            HitRegion::Button,
2070            3,
2071            2,
2072        );
2073
2074        // Compare at grid of points
2075        for x in (0..80).step_by(5) {
2076            for y in (0..24).step_by(3) {
2077                let ro = idx.hit_test_readonly(x, y);
2078                let expected_id = ro.map(|(id, _, _)| id);
2079                // We can't use hit_test (mutates cache) in a fair comparison loop,
2080                // so just verify readonly is consistent with itself
2081                let ro2 = idx.hit_test_readonly(x, y);
2082                assert_eq!(ro, ro2, "Readonly inconsistency at ({x}, {y})");
2083                // Also verify against mutable
2084                let mut_result = idx.hit_test(x, y);
2085                let mut_id = mut_result.map(|(id, _, _)| id);
2086                assert_eq!(
2087                    expected_id, mut_id,
2088                    "Mutable/readonly mismatch at ({x}, {y})"
2089                );
2090            }
2091        }
2092    }
2093}