Skip to main content

ftui_layout/
cache.rs

1//! Layout cache for memoizing layout computation results.
2//!
3//! This module provides [`LayoutCache`] which caches the `Vec<Rect>` results from
4//! layout computations to avoid redundant constraint solving during rendering.
5//!
6//! # Overview
7//!
8//! Layout computation (constraint solving, flex distribution) can be expensive for
9//! complex nested layouts. During a single frame, the same layout may be queried
10//! multiple times with identical parameters. The cache eliminates this redundancy.
11//!
12//! # Usage
13//!
14//! ```ignore
15//! use ftui_layout::{Flex, Constraint, LayoutCache, LayoutCacheKey, Direction};
16//! use ftui_core::geometry::Rect;
17//!
18//! let mut cache = LayoutCache::new(64);
19//!
20//! let flex = Flex::horizontal()
21//!     .constraints([Constraint::Percentage(50.0), Constraint::Fill]);
22//!
23//! let area = Rect::new(0, 0, 80, 24);
24//!
25//! // First call computes and caches
26//! let rects = flex.split_cached(area, &mut cache);
27//!
28//! // Second call returns cached result
29//! let cached = flex.split_cached(area, &mut cache);
30//! ```
31//!
32//! # Invalidation
33//!
34//! ## Generation-Based (Primary)
35//!
36//! Call [`LayoutCache::invalidate_all()`] after any state change affecting layouts:
37//!
38//! ```ignore
39//! match msg {
40//!     Msg::DataChanged(_) => {
41//!         self.layout_cache.invalidate_all();
42//!     }
43//!     Msg::Resize(_) => {
44//!         // Area is part of cache key, no invalidation needed!
45//!     }
46//! }
47//! ```
48//!
49//! # Cache Eviction
50//!
51//! The cache uses LRU (Least Recently Used) eviction when at capacity.
52
53use std::hash::{Hash, Hasher};
54
55use ftui_core::geometry::Rect;
56use rustc_hash::FxHashMap;
57
58use crate::{Constraint, Direction, LayoutSizeHint};
59
60/// Key for layout cache lookups.
61///
62/// Includes all parameters that affect layout computation:
63/// - The available area (stored as components for Hash)
64/// - A fingerprint of all constraints
65/// - The length of the constraints slice
66/// - The layout direction
67/// - Optionally, a fingerprint of intrinsic size hints
68#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
69pub struct LayoutCacheKey {
70    /// Area x-coordinate.
71    pub area_x: u16,
72    /// Area y-coordinate.
73    pub area_y: u16,
74    /// Area width.
75    pub area_width: u16,
76    /// Area height.
77    pub area_height: u16,
78    /// Primary hash fingerprint of constraints.
79    pub constraints_hash: u64,
80    /// Secondary hash fingerprint of constraints (for 128-bit collision resistance).
81    pub constraints_hash_fx: u64,
82    /// Length of constraints slice.
83    pub constraints_len: u16,
84    /// Layout direction.
85    pub direction: Direction,
86    /// Primary hash fingerprint of intrinsic sizes (if using FitContent).
87    pub intrinsics_hash: Option<u64>,
88    /// Secondary hash fingerprint of intrinsic sizes.
89    pub intrinsics_hash_fx: Option<u64>,
90}
91
92impl LayoutCacheKey {
93    /// Create a new cache key from layout parameters.
94    ///
95    /// # Arguments
96    ///
97    /// * `area` - The available rectangle for layout
98    /// * `constraints` - The constraint list
99    /// * `direction` - Horizontal or Vertical layout
100    /// * `intrinsics` - Optional size hints for FitContent constraints
101    pub fn new(
102        area: Rect,
103        constraints: &[Constraint],
104        direction: Direction,
105        intrinsics: Option<&[LayoutSizeHint]>,
106    ) -> Self {
107        let (ch1, ch2) = Self::hash_constraints(constraints);
108        let intr_hashes = intrinsics.map(Self::hash_intrinsics);
109        Self {
110            area_x: area.x,
111            area_y: area.y,
112            area_width: area.width,
113            area_height: area.height,
114            constraints_hash: ch1,
115            constraints_hash_fx: ch2,
116            constraints_len: constraints.len() as u16,
117            direction,
118            intrinsics_hash: intr_hashes.map(|h| h.0),
119            intrinsics_hash_fx: intr_hashes.map(|h| h.1),
120        }
121    }
122
123    /// Reconstruct the area Rect from cached components.
124    #[inline]
125    pub fn area(&self) -> Rect {
126        Rect::new(self.area_x, self.area_y, self.area_width, self.area_height)
127    }
128
129    /// Hash a slice of constraints with two independent hashers.
130    fn hash_constraints(constraints: &[Constraint]) -> (u64, u64) {
131        let mut h1 = std::collections::hash_map::DefaultHasher::new();
132        let mut h2 = rustc_hash::FxHasher::default();
133        for c in constraints {
134            std::mem::discriminant(c).hash(&mut h1);
135            std::mem::discriminant(c).hash(&mut h2);
136            match c {
137                Constraint::Fixed(v) => {
138                    v.hash(&mut h1);
139                    v.hash(&mut h2);
140                }
141                Constraint::Percentage(p) => {
142                    p.to_bits().hash(&mut h1);
143                    p.to_bits().hash(&mut h2);
144                }
145                Constraint::Min(v) => {
146                    v.hash(&mut h1);
147                    v.hash(&mut h2);
148                }
149                Constraint::Max(v) => {
150                    v.hash(&mut h1);
151                    v.hash(&mut h2);
152                }
153                Constraint::Ratio(n, d) => {
154                    fn gcd(mut a: u32, mut b: u32) -> u32 {
155                        while b != 0 {
156                            let t = b;
157                            b = a % b;
158                            a = t;
159                        }
160                        a
161                    }
162                    let divisor = gcd(*n, *d);
163                    if let (Some(n_div), Some(d_div)) =
164                        (n.checked_div(divisor), d.checked_div(divisor))
165                    {
166                        n_div.hash(&mut h1);
167                        d_div.hash(&mut h1);
168                        n_div.hash(&mut h2);
169                        d_div.hash(&mut h2);
170                    } else {
171                        n.hash(&mut h1);
172                        d.hash(&mut h1);
173                        n.hash(&mut h2);
174                        d.hash(&mut h2);
175                    }
176                }
177                Constraint::Fill => {}
178                Constraint::FitContent => {}
179                Constraint::FitContentBounded { min, max } => {
180                    min.hash(&mut h1);
181                    max.hash(&mut h1);
182                    min.hash(&mut h2);
183                    max.hash(&mut h2);
184                }
185                Constraint::FitMin => {}
186            }
187        }
188        (h1.finish(), h2.finish())
189    }
190
191    /// Hash a slice of intrinsic size hints.
192    fn hash_intrinsics(intrinsics: &[LayoutSizeHint]) -> (u64, u64) {
193        let mut h1 = std::collections::hash_map::DefaultHasher::new();
194        let mut h2 = rustc_hash::FxHasher::default();
195        for hint in intrinsics {
196            hint.min.hash(&mut h1);
197            hint.preferred.hash(&mut h1);
198            hint.max.hash(&mut h1);
199            hint.min.hash(&mut h2);
200            hint.preferred.hash(&mut h2);
201            hint.max.hash(&mut h2);
202        }
203        (h1.finish(), h2.finish())
204    }
205}
206
207/// Cached layout result with metadata for eviction.
208#[derive(Clone, Debug)]
209struct CachedLayoutEntry {
210    /// The cached layout rectangles.
211    chunks: crate::Rects,
212    /// Generation when this entry was created/updated.
213    generation: u64,
214    /// Access count for LRU eviction.
215    access_count: u32,
216}
217
218/// Statistics about layout cache performance.
219#[derive(Debug, Clone, Default)]
220pub struct LayoutCacheStats {
221    /// Number of entries currently in the cache.
222    pub entries: usize,
223    /// Total cache hits since creation or last reset.
224    pub hits: u64,
225    /// Total cache misses since creation or last reset.
226    pub misses: u64,
227    /// Hit rate as a fraction (0.0 to 1.0).
228    pub hit_rate: f64,
229}
230
231/// Cache for layout computation results.
232///
233/// Stores `Vec<Rect>` results keyed by [`LayoutCacheKey`] to avoid redundant
234/// constraint solving during rendering.
235///
236/// # Capacity
237///
238/// The cache has a fixed maximum capacity. When full, the least recently used
239/// entries are evicted to make room for new ones.
240///
241/// # Generation-Based Invalidation
242///
243/// Each entry is tagged with a generation number. Calling [`invalidate_all()`]
244/// bumps the generation, making all existing entries stale.
245///
246/// [`invalidate_all()`]: LayoutCache::invalidate_all
247#[derive(Debug)]
248pub struct LayoutCache {
249    entries: FxHashMap<LayoutCacheKey, CachedLayoutEntry>,
250    generation: u64,
251    max_entries: usize,
252    hits: u64,
253    misses: u64,
254}
255
256impl LayoutCache {
257    /// Create a new cache with the specified maximum capacity.
258    ///
259    /// # Arguments
260    ///
261    /// * `max_entries` - Maximum number of entries before LRU eviction occurs.
262    ///   A typical value is 64-256 for most UIs.
263    ///
264    /// # Example
265    ///
266    /// ```
267    /// use ftui_layout::LayoutCache;
268    /// let cache = LayoutCache::new(64);
269    /// ```
270    #[inline]
271    pub fn new(max_entries: usize) -> Self {
272        Self {
273            entries: FxHashMap::with_capacity_and_hasher(max_entries, Default::default()),
274            generation: 0,
275            max_entries,
276            hits: 0,
277            misses: 0,
278        }
279    }
280
281    /// Get cached layout or compute and cache a new one.
282    ///
283    /// If a valid (same generation) cache entry exists for the given key,
284    /// returns a clone of it. Otherwise, calls the `compute` closure,
285    /// caches the result, and returns it.
286    ///
287    /// # Arguments
288    ///
289    /// * `key` - The cache key identifying this layout computation
290    /// * `compute` - Closure to compute the layout if not cached
291    ///
292    /// # Example
293    ///
294    /// ```ignore
295    /// let key = LayoutCacheKey::new(area, &constraints, Direction::Horizontal, None);
296    /// let rects = cache.get_or_compute(key, || flex.split(area));
297    /// ```
298    pub fn get_or_compute<F>(&mut self, key: LayoutCacheKey, compute: F) -> crate::Rects
299    where
300        F: FnOnce() -> crate::Rects,
301    {
302        // Check for existing valid entry
303        if let Some(entry) = self.entries.get_mut(&key)
304            && entry.generation == self.generation
305        {
306            self.hits += 1;
307            entry.access_count = entry.access_count.saturating_add(1);
308            return entry.chunks.clone();
309        }
310
311        // Cache miss - compute the value
312        self.misses += 1;
313        let chunks = compute();
314
315        // Evict if at capacity
316        if self.entries.len() >= self.max_entries {
317            self.evict_lru();
318        }
319
320        // Insert new entry
321        self.entries.insert(
322            key,
323            CachedLayoutEntry {
324                chunks: chunks.clone(),
325                generation: self.generation,
326                access_count: 1,
327            },
328        );
329
330        chunks
331    }
332
333    /// Invalidate all entries by bumping the generation.
334    ///
335    /// Existing entries become stale and will be recomputed on next access.
336    /// This is an O(1) operation - entries are not immediately removed.
337    ///
338    /// # When to Call
339    ///
340    /// Call this after any state change that affects layout:
341    /// - Model data changes that affect widget content
342    /// - Theme/font changes that affect sizing
343    ///
344    /// # Note
345    ///
346    /// Resize events don't require invalidation because the area
347    /// is part of the cache key.
348    #[inline]
349    pub fn invalidate_all(&mut self) {
350        self.generation = self.generation.wrapping_add(1);
351    }
352
353    /// Get current cache statistics.
354    ///
355    /// Returns hit/miss counts and the current hit rate.
356    pub fn stats(&self) -> LayoutCacheStats {
357        let total = self.hits + self.misses;
358        LayoutCacheStats {
359            entries: self.entries.len(),
360            hits: self.hits,
361            misses: self.misses,
362            hit_rate: if total > 0 {
363                self.hits as f64 / total as f64
364            } else {
365                0.0
366            },
367        }
368    }
369
370    /// Reset statistics counters to zero.
371    ///
372    /// Useful for measuring hit rate over a specific period (e.g., per frame).
373    #[inline]
374    pub fn reset_stats(&mut self) {
375        self.hits = 0;
376        self.misses = 0;
377    }
378
379    /// Clear all entries from the cache.
380    ///
381    /// Unlike [`invalidate_all()`], this immediately frees memory.
382    ///
383    /// [`invalidate_all()`]: LayoutCache::invalidate_all
384    #[inline]
385    pub fn clear(&mut self) {
386        self.entries.clear();
387        self.generation = self.generation.wrapping_add(1);
388    }
389
390    /// Returns the current number of entries in the cache.
391    #[inline]
392    pub fn len(&self) -> usize {
393        self.entries.len()
394    }
395
396    /// Returns true if the cache is empty.
397    #[inline]
398    pub fn is_empty(&self) -> bool {
399        self.entries.is_empty()
400    }
401
402    /// Returns the maximum capacity of the cache.
403    #[inline]
404    pub fn capacity(&self) -> usize {
405        self.max_entries
406    }
407
408    /// Evict the least recently used entry.
409    fn evict_lru(&mut self) {
410        if let Some(key) = self
411            .entries
412            .iter()
413            .min_by_key(|(_, e)| e.access_count)
414            .map(|(k, _)| *k)
415        {
416            self.entries.remove(&key);
417        }
418    }
419}
420
421impl Default for LayoutCache {
422    /// Creates a cache with default capacity of 64 entries.
423    fn default() -> Self {
424        Self::new(64)
425    }
426}
427
428// ---------------------------------------------------------------------------
429// S3-FIFO Layout Cache (bd-l6yba.3)
430// ---------------------------------------------------------------------------
431
432/// Layout cache backed by S3-FIFO eviction.
433///
434/// Drop-in replacement for [`LayoutCache`] that uses the scan-resistant
435/// S3-FIFO eviction policy instead of the HashMap-based LRU. This protects
436/// frequently-accessed layout computations from being evicted by transient
437/// layouts (e.g. popup menus or tooltips that appear once).
438///
439/// Supports the same generation-based invalidation as [`LayoutCache`].
440#[cfg(feature = "experimental")]
441#[derive(Debug)]
442pub struct S3FifoLayoutCache {
443    cache: ftui_core::s3_fifo::S3Fifo<LayoutCacheKey, CachedLayoutEntry>,
444    generation: u64,
445    max_entries: usize,
446    hits: u64,
447    misses: u64,
448}
449
450#[cfg(feature = "experimental")]
451impl S3FifoLayoutCache {
452    /// Create a new S3-FIFO layout cache with the given capacity.
453    #[inline]
454    pub fn new(max_entries: usize) -> Self {
455        Self {
456            cache: ftui_core::s3_fifo::S3Fifo::new(max_entries.max(2)),
457            generation: 0,
458            max_entries: max_entries.max(2),
459            hits: 0,
460            misses: 0,
461        }
462    }
463
464    /// Get cached layout or compute and cache a new one.
465    ///
466    /// Same semantics as [`LayoutCache::get_or_compute`]: entries from
467    /// a previous generation are treated as misses.
468    pub fn get_or_compute<F>(&mut self, key: LayoutCacheKey, compute: F) -> crate::Rects
469    where
470        F: FnOnce() -> crate::Rects,
471    {
472        if let Some(entry) = self.cache.get(&key) {
473            if entry.generation == self.generation {
474                self.hits += 1;
475                return entry.chunks.clone();
476            }
477            // Stale entry (old generation) — remove and recompute.
478            self.cache.remove(&key);
479        }
480
481        self.misses += 1;
482        let chunks = compute();
483
484        self.cache.insert(
485            key,
486            CachedLayoutEntry {
487                chunks: chunks.clone(),
488                generation: self.generation,
489                access_count: 1,
490            },
491        );
492
493        chunks
494    }
495
496    /// Invalidate all entries by bumping the generation (O(1)).
497    #[inline]
498    pub fn invalidate_all(&mut self) {
499        self.generation = self.generation.wrapping_add(1);
500    }
501
502    /// Get current cache statistics.
503    pub fn stats(&self) -> LayoutCacheStats {
504        let total = self.hits + self.misses;
505        LayoutCacheStats {
506            entries: self.cache.len(),
507            hits: self.hits,
508            misses: self.misses,
509            hit_rate: if total > 0 {
510                self.hits as f64 / total as f64
511            } else {
512                0.0
513            },
514        }
515    }
516
517    /// Reset statistics counters.
518    #[inline]
519    pub fn reset_stats(&mut self) {
520        self.hits = 0;
521        self.misses = 0;
522    }
523
524    /// Clear all entries.
525    #[inline]
526    pub fn clear(&mut self) {
527        self.cache.clear();
528        self.generation = self.generation.wrapping_add(1);
529    }
530
531    /// Current number of entries.
532    #[inline]
533    pub fn len(&self) -> usize {
534        self.cache.len()
535    }
536
537    /// Whether the cache is empty.
538    #[inline]
539    pub fn is_empty(&self) -> bool {
540        self.cache.is_empty()
541    }
542
543    /// Maximum capacity.
544    #[inline]
545    pub fn capacity(&self) -> usize {
546        self.max_entries
547    }
548}
549
550#[cfg(feature = "experimental")]
551impl Default for S3FifoLayoutCache {
552    fn default() -> Self {
553        Self::new(64)
554    }
555}
556
557// ---------------------------------------------------------------------------
558// Coherence Cache: Temporal Stability for Layout Rounding
559// ---------------------------------------------------------------------------
560
561/// Identity for a layout computation, used as key in the coherence cache.
562///
563/// This is a subset of [`LayoutCacheKey`] that identifies a *layout slot*
564/// independently of the available area. Two computations with the same
565/// `CoherenceId` but different area sizes represent the same logical layout
566/// being re-rendered at a different terminal size.
567#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
568pub struct CoherenceId {
569    /// Hash fingerprint of constraints.
570    pub constraints_hash: u64,
571    /// Layout direction.
572    pub direction: Direction,
573}
574
575impl CoherenceId {
576    /// Create a coherence ID from layout parameters.
577    pub fn new(constraints: &[Constraint], direction: Direction) -> Self {
578        Self {
579            constraints_hash: LayoutCacheKey::hash_constraints(constraints).0,
580            direction,
581        }
582    }
583
584    /// Create a coherence ID from an existing cache key.
585    pub fn from_cache_key(key: &LayoutCacheKey) -> Self {
586        Self {
587            constraints_hash: key.constraints_hash,
588            direction: key.direction,
589        }
590    }
591}
592
593/// Stores previous layout allocations for temporal coherence.
594///
595/// When terminal size changes, the layout solver re-computes positions from
596/// scratch. Without coherence, rounding tie-breaks can cause widgets to
597/// "jump" between frames even when the total size change is small.
598///
599/// The `CoherenceCache` feeds previous allocations to
600/// [`round_layout_stable`](crate::round_layout_stable) so that tie-breaking
601/// favours keeping elements where they were.
602///
603/// # Usage
604///
605/// ```ignore
606/// use ftui_layout::{CoherenceCache, CoherenceId, round_layout_stable, Constraint, Direction};
607///
608/// let mut coherence = CoherenceCache::new(64);
609///
610/// let id = CoherenceId::new(&constraints, Direction::Horizontal);
611/// let prev = coherence.get(&id);
612/// let alloc = round_layout_stable(&targets, total, prev);
613/// coherence.store(id, alloc.clone());
614/// ```
615///
616/// # Eviction
617///
618/// Entries are evicted on a least-recently-stored basis when the cache
619/// reaches capacity. The cache does not grow unboundedly.
620#[derive(Debug, Clone)]
621pub struct CoherenceCache {
622    entries: FxHashMap<CoherenceId, CoherenceEntry>,
623    max_entries: usize,
624    /// Monotonic counter for LRU eviction.
625    tick: u64,
626}
627
628#[derive(Debug, Clone)]
629struct CoherenceEntry {
630    /// Previous allocation sizes.
631    allocation: crate::Sizes,
632    /// Tick when this entry was last stored.
633    last_stored: u64,
634}
635
636impl CoherenceCache {
637    /// Create a new coherence cache with the specified capacity.
638    pub fn new(max_entries: usize) -> Self {
639        Self {
640            entries: FxHashMap::with_capacity_and_hasher(max_entries.min(256), Default::default()),
641            max_entries,
642            tick: 0,
643        }
644    }
645
646    /// Retrieve the previous allocation for a layout, if available.
647    ///
648    /// Returns `Some(allocation)` suitable for passing directly to
649    /// [`round_layout_stable`](crate::round_layout_stable).
650    #[inline]
651    pub fn get(&self, id: &CoherenceId) -> Option<crate::Sizes> {
652        self.entries.get(id).map(|e| e.allocation.clone())
653    }
654
655    /// Store a layout allocation for future coherence lookups.
656    ///
657    /// If the cache is at capacity, evicts the oldest entry.
658    pub fn store(&mut self, id: CoherenceId, allocation: crate::Sizes) {
659        self.tick = self.tick.wrapping_add(1);
660
661        if self.entries.len() >= self.max_entries && !self.entries.contains_key(&id) {
662            self.evict_oldest();
663        }
664
665        self.entries.insert(
666            id,
667            CoherenceEntry {
668                allocation,
669                last_stored: self.tick,
670            },
671        );
672    }
673
674    /// Clear all stored allocations.
675    #[inline]
676    pub fn clear(&mut self) {
677        self.entries.clear();
678    }
679
680    /// Number of entries in the cache.
681    #[inline]
682    pub fn len(&self) -> usize {
683        self.entries.len()
684    }
685
686    /// Returns true if the cache is empty.
687    #[inline]
688    pub fn is_empty(&self) -> bool {
689        self.entries.is_empty()
690    }
691
692    /// Compute displacement between a new allocation and the previously stored one.
693    ///
694    /// Returns `(sum_displacement, max_displacement)` in cells.
695    /// If no previous allocation exists for the ID, returns `(0, 0)`.
696    pub fn displacement(&self, id: &CoherenceId, new_alloc: &[u16]) -> (u64, u32) {
697        match self.entries.get(id) {
698            Some(entry) => {
699                let prev = &entry.allocation;
700                let len = prev.len().min(new_alloc.len());
701                let mut sum: u64 = 0;
702                let mut max: u32 = 0;
703                for i in 0..len {
704                    let d = (new_alloc[i] as i32 - prev[i] as i32).unsigned_abs();
705                    sum += u64::from(d);
706                    max = max.max(d);
707                }
708                // If lengths differ, count the extra elements as full displacement
709                for &v in &prev[len..] {
710                    sum += u64::from(v);
711                    max = max.max(u32::from(v));
712                }
713                for &v in &new_alloc[len..] {
714                    sum += u64::from(v);
715                    max = max.max(u32::from(v));
716                }
717                (sum, max)
718            }
719            None => (0, 0),
720        }
721    }
722
723    fn evict_oldest(&mut self) {
724        if let Some(key) = self
725            .entries
726            .iter()
727            .min_by_key(|(_, e)| e.last_stored)
728            .map(|(k, _)| *k)
729        {
730            self.entries.remove(&key);
731        }
732    }
733}
734
735impl Default for CoherenceCache {
736    fn default() -> Self {
737        Self::new(64)
738    }
739}
740
741#[cfg(test)]
742mod tests {
743    use super::*;
744
745    fn make_key(width: u16, height: u16) -> LayoutCacheKey {
746        LayoutCacheKey::new(
747            Rect::new(0, 0, width, height),
748            &[Constraint::Percentage(50.0), Constraint::Fill],
749            Direction::Horizontal,
750            None,
751        )
752    }
753
754    fn should_not_call(label: &str) -> crate::Rects {
755        unreachable!("{label}");
756    }
757
758    // --- LayoutCacheKey tests ---
759
760    #[test]
761    fn same_params_produce_same_key() {
762        let k1 = make_key(80, 24);
763        let k2 = make_key(80, 24);
764        assert_eq!(k1, k2);
765    }
766
767    #[test]
768    fn different_area_different_key() {
769        let k1 = make_key(80, 24);
770        let k2 = make_key(120, 40);
771        assert_ne!(k1, k2);
772    }
773
774    #[test]
775    fn different_constraints_different_key() {
776        let k1 = LayoutCacheKey::new(
777            Rect::new(0, 0, 80, 24),
778            &[Constraint::Fixed(20)],
779            Direction::Horizontal,
780            None,
781        );
782        let k2 = LayoutCacheKey::new(
783            Rect::new(0, 0, 80, 24),
784            &[Constraint::Fixed(30)],
785            Direction::Horizontal,
786            None,
787        );
788        assert_ne!(k1, k2);
789    }
790
791    #[test]
792    fn different_direction_different_key() {
793        let k1 = LayoutCacheKey::new(
794            Rect::new(0, 0, 80, 24),
795            &[Constraint::Fill],
796            Direction::Horizontal,
797            None,
798        );
799        let k2 = LayoutCacheKey::new(
800            Rect::new(0, 0, 80, 24),
801            &[Constraint::Fill],
802            Direction::Vertical,
803            None,
804        );
805        assert_ne!(k1, k2);
806    }
807
808    #[test]
809    fn different_intrinsics_different_key() {
810        let hints1 = [LayoutSizeHint {
811            min: 10,
812            preferred: 20,
813            max: None,
814        }];
815        let hints2 = [LayoutSizeHint {
816            min: 10,
817            preferred: 30,
818            max: None,
819        }];
820
821        let k1 = LayoutCacheKey::new(
822            Rect::new(0, 0, 80, 24),
823            &[Constraint::FitContent],
824            Direction::Horizontal,
825            Some(&hints1),
826        );
827        let k2 = LayoutCacheKey::new(
828            Rect::new(0, 0, 80, 24),
829            &[Constraint::FitContent],
830            Direction::Horizontal,
831            Some(&hints2),
832        );
833        assert_ne!(k1, k2);
834    }
835
836    // --- LayoutCache tests ---
837
838    #[test]
839    fn cache_returns_same_result() {
840        let mut cache = LayoutCache::new(100);
841        let key = make_key(80, 24);
842
843        let mut compute_count = 0;
844        let compute = || {
845            compute_count += 1;
846            smallvec::smallvec![Rect::new(0, 0, 40, 24), Rect::new(40, 0, 40, 24)]
847        };
848
849        let r1 = cache.get_or_compute(key, compute);
850        let r2 = cache.get_or_compute(key, || should_not_call("should not call"));
851
852        assert_eq!(r1, r2);
853        assert_eq!(compute_count, 1);
854    }
855
856    #[test]
857    fn different_area_is_cache_miss() {
858        let mut cache = LayoutCache::new(100);
859
860        let mut compute_count = 0;
861        let mut compute = || {
862            compute_count += 1;
863            smallvec::smallvec![Rect::default()]
864        };
865
866        let k1 = make_key(80, 24);
867        let k2 = make_key(120, 40);
868
869        cache.get_or_compute(k1, &mut compute);
870        cache.get_or_compute(k2, &mut compute);
871
872        assert_eq!(compute_count, 2);
873    }
874
875    #[test]
876    fn invalidation_clears_cache() {
877        let mut cache = LayoutCache::new(100);
878        let key = make_key(80, 24);
879
880        let mut compute_count = 0;
881        let mut compute = || {
882            compute_count += 1;
883            smallvec::smallvec![]
884        };
885
886        cache.get_or_compute(key, &mut compute);
887        cache.invalidate_all();
888        cache.get_or_compute(key, &mut compute);
889
890        assert_eq!(compute_count, 2);
891    }
892
893    #[test]
894    fn lru_eviction_works() {
895        let mut cache = LayoutCache::new(2);
896
897        let k1 = make_key(10, 10);
898        let k2 = make_key(20, 20);
899        let k3 = make_key(30, 30);
900
901        // Insert two entries
902        cache.get_or_compute(k1, || smallvec::smallvec![Rect::new(0, 0, 10, 10)]);
903        cache.get_or_compute(k2, || smallvec::smallvec![Rect::new(0, 0, 20, 20)]);
904
905        // Access k1 again (increases access count)
906        cache.get_or_compute(k1, || should_not_call("k1 should hit"));
907
908        // Insert k3, should evict k2 (least accessed)
909        cache.get_or_compute(k3, || smallvec::smallvec![Rect::new(0, 0, 30, 30)]);
910
911        assert_eq!(cache.len(), 2);
912
913        // k2 should be evicted
914        let mut was_called = false;
915        cache.get_or_compute(k2, || {
916            was_called = true;
917            smallvec::smallvec![]
918        });
919        assert!(was_called, "k2 should have been evicted");
920
921        // k1 should still be cached
922        cache.get_or_compute(k1, || should_not_call("k1 should still be cached"));
923    }
924
925    #[test]
926    fn stats_track_hits_and_misses() {
927        let mut cache = LayoutCache::new(100);
928
929        let k1 = make_key(80, 24);
930        let k2 = make_key(120, 40);
931
932        cache.get_or_compute(k1, crate::Rects::new); // miss
933        cache.get_or_compute(k1, || should_not_call("hit")); // hit
934        cache.get_or_compute(k2, crate::Rects::new); // miss
935
936        let stats = cache.stats();
937        assert_eq!(stats.hits, 1);
938        assert_eq!(stats.misses, 2);
939        assert!((stats.hit_rate - 1.0 / 3.0).abs() < 0.01);
940    }
941
942    #[test]
943    fn reset_stats_clears_counters() {
944        let mut cache = LayoutCache::new(100);
945        let key = make_key(80, 24);
946
947        cache.get_or_compute(key, crate::Rects::new);
948        cache.get_or_compute(key, || should_not_call("hit"));
949
950        let stats = cache.stats();
951        assert_eq!(stats.hits, 1);
952        assert_eq!(stats.misses, 1);
953
954        cache.reset_stats();
955
956        let stats = cache.stats();
957        assert_eq!(stats.hits, 0);
958        assert_eq!(stats.misses, 0);
959        assert_eq!(stats.hit_rate, 0.0);
960    }
961
962    #[test]
963    fn clear_removes_all_entries() {
964        let mut cache = LayoutCache::new(100);
965
966        cache.get_or_compute(make_key(80, 24), crate::Rects::new);
967        cache.get_or_compute(make_key(120, 40), crate::Rects::new);
968
969        assert_eq!(cache.len(), 2);
970
971        cache.clear();
972
973        assert_eq!(cache.len(), 0);
974        assert!(cache.is_empty());
975
976        // All entries should miss now
977        let mut was_called = false;
978        cache.get_or_compute(make_key(80, 24), || {
979            was_called = true;
980            smallvec::smallvec![]
981        });
982        assert!(was_called);
983    }
984
985    #[test]
986    fn default_capacity_is_64() {
987        let cache = LayoutCache::default();
988        assert_eq!(cache.capacity(), 64);
989    }
990
991    #[test]
992    fn generation_wraps_around() {
993        let mut cache = LayoutCache::new(100);
994        cache.generation = u64::MAX;
995        cache.invalidate_all();
996        assert_eq!(cache.generation, 0);
997    }
998
999    // --- Constraint hashing tests ---
1000
1001    #[test]
1002    fn constraint_hash_is_stable() {
1003        let constraints = [
1004            Constraint::Fixed(20),
1005            Constraint::Percentage(50.0),
1006            Constraint::Min(10),
1007        ];
1008
1009        let h1 = LayoutCacheKey::hash_constraints(&constraints);
1010        let h2 = LayoutCacheKey::hash_constraints(&constraints);
1011
1012        assert_eq!(h1, h2);
1013    }
1014
1015    #[test]
1016    fn different_constraint_values_different_hash() {
1017        let c1 = [Constraint::Fixed(20)];
1018        let c2 = [Constraint::Fixed(30)];
1019
1020        let h1 = LayoutCacheKey::hash_constraints(&c1);
1021        let h2 = LayoutCacheKey::hash_constraints(&c2);
1022
1023        assert_ne!(h1, h2);
1024    }
1025
1026    #[test]
1027    fn different_constraint_types_different_hash() {
1028        let c1 = [Constraint::Fixed(20)];
1029        let c2 = [Constraint::Min(20)];
1030
1031        let h1 = LayoutCacheKey::hash_constraints(&c1);
1032        let h2 = LayoutCacheKey::hash_constraints(&c2);
1033
1034        assert_ne!(h1, h2);
1035    }
1036
1037    #[test]
1038    fn fit_content_bounded_values_in_hash() {
1039        let c1 = [Constraint::FitContentBounded { min: 10, max: 50 }];
1040        let c2 = [Constraint::FitContentBounded { min: 10, max: 60 }];
1041
1042        let h1 = LayoutCacheKey::hash_constraints(&c1);
1043        let h2 = LayoutCacheKey::hash_constraints(&c2);
1044
1045        assert_ne!(h1, h2);
1046    }
1047
1048    // --- Intrinsics hashing tests ---
1049
1050    #[test]
1051    fn intrinsics_hash_is_stable() {
1052        let hints = [
1053            LayoutSizeHint {
1054                min: 10,
1055                preferred: 20,
1056                max: Some(30),
1057            },
1058            LayoutSizeHint {
1059                min: 5,
1060                preferred: 15,
1061                max: None,
1062            },
1063        ];
1064
1065        let h1 = LayoutCacheKey::hash_intrinsics(&hints);
1066        let h2 = LayoutCacheKey::hash_intrinsics(&hints);
1067
1068        assert_eq!(h1, h2);
1069    }
1070
1071    #[test]
1072    fn different_intrinsics_different_hash() {
1073        let h1 = [LayoutSizeHint {
1074            min: 10,
1075            preferred: 20,
1076            max: None,
1077        }];
1078        let h2 = [LayoutSizeHint {
1079            min: 10,
1080            preferred: 25,
1081            max: None,
1082        }];
1083
1084        let hash1 = LayoutCacheKey::hash_intrinsics(&h1);
1085        let hash2 = LayoutCacheKey::hash_intrinsics(&h2);
1086
1087        assert_ne!(hash1, hash2);
1088    }
1089
1090    // --- Property-like tests ---
1091
1092    #[test]
1093    fn cache_is_deterministic() {
1094        let mut cache1 = LayoutCache::new(100);
1095        let mut cache2 = LayoutCache::new(100);
1096
1097        for i in 0..10u16 {
1098            let key = make_key(i * 10, i * 5);
1099            let result = smallvec::smallvec![Rect::new(0, 0, i, i)];
1100
1101            cache1.get_or_compute(key, || result.clone());
1102            cache2.get_or_compute(key, || result);
1103        }
1104
1105        assert_eq!(cache1.stats().entries, cache2.stats().entries);
1106        assert_eq!(cache1.stats().misses, cache2.stats().misses);
1107    }
1108
1109    #[test]
1110    fn hit_count_increments_on_each_access() {
1111        let mut cache = LayoutCache::new(100);
1112        let key = make_key(80, 24);
1113
1114        // First access is a miss
1115        cache.get_or_compute(key, crate::Rects::new);
1116
1117        // Subsequent accesses are hits
1118        for _ in 0..5 {
1119            cache.get_or_compute(key, || should_not_call("should hit"));
1120        }
1121
1122        let stats = cache.stats();
1123        assert_eq!(stats.misses, 1);
1124        assert_eq!(stats.hits, 5);
1125    }
1126
1127    // -----------------------------------------------------------------------
1128    // Coherence Cache Tests (bd-4kq0.4.2)
1129    // -----------------------------------------------------------------------
1130
1131    fn make_coherence_id(n: u16) -> CoherenceId {
1132        CoherenceId::new(
1133            &[Constraint::Fixed(n), Constraint::Fill],
1134            Direction::Horizontal,
1135        )
1136    }
1137
1138    #[test]
1139    fn coherence_store_and_get() {
1140        let mut cc = CoherenceCache::new(64);
1141        let id = make_coherence_id(1);
1142
1143        assert!(cc.get(&id).is_none());
1144
1145        cc.store(id, smallvec::smallvec![30u16, 50u16]);
1146        assert_eq!(cc.get(&id), Some(smallvec::smallvec![30u16, 50u16]));
1147    }
1148
1149    #[test]
1150    fn coherence_update_replaces_allocation() {
1151        let mut cc = CoherenceCache::new(64);
1152        let id = make_coherence_id(1);
1153
1154        cc.store(id, smallvec::smallvec![30u16, 50u16]);
1155        cc.store(id, smallvec::smallvec![31u16, 49u16]);
1156
1157        assert_eq!(cc.get(&id), Some(smallvec::smallvec![31u16, 49u16]));
1158        assert_eq!(cc.len(), 1);
1159    }
1160
1161    #[test]
1162    fn coherence_different_ids_are_separate() {
1163        let mut cc = CoherenceCache::new(64);
1164        let id1 = make_coherence_id(1);
1165        let id2 = make_coherence_id(2);
1166
1167        cc.store(id1, smallvec::smallvec![40u16, 40u16]);
1168        cc.store(id2, smallvec::smallvec![30u16, 50u16]);
1169
1170        assert_eq!(cc.get(&id1), Some(smallvec::smallvec![40u16, 40u16]));
1171        assert_eq!(cc.get(&id2), Some(smallvec::smallvec![30u16, 50u16]));
1172    }
1173
1174    #[test]
1175    fn coherence_eviction_at_capacity() {
1176        let mut cc = CoherenceCache::new(2);
1177
1178        let id1 = make_coherence_id(1);
1179        let id2 = make_coherence_id(2);
1180        let id3 = make_coherence_id(3);
1181
1182        cc.store(id1, smallvec::smallvec![10u16]);
1183        cc.store(id2, smallvec::smallvec![20u16]);
1184        cc.store(id3, smallvec::smallvec![30u16]);
1185
1186        assert_eq!(cc.len(), 2);
1187        // id1 should be evicted (oldest)
1188        assert!(cc.get(&id1).is_none());
1189        assert_eq!(cc.get(&id2), Some(smallvec::smallvec![20u16]));
1190        assert_eq!(cc.get(&id3), Some(smallvec::smallvec![30u16]));
1191    }
1192
1193    #[test]
1194    fn coherence_clear() {
1195        let mut cc = CoherenceCache::new(64);
1196        let id = make_coherence_id(1);
1197
1198        cc.store(id, smallvec::smallvec![10u16, 20u16]);
1199        assert_eq!(cc.len(), 1);
1200
1201        cc.clear();
1202        assert!(cc.is_empty());
1203        assert!(cc.get(&id).is_none());
1204    }
1205
1206    #[test]
1207    fn coherence_displacement_with_previous() {
1208        let mut cc = CoherenceCache::new(64);
1209        let id = make_coherence_id(1);
1210
1211        cc.store(id, smallvec::smallvec![30u16, 50u16]);
1212
1213        // New allocation differs by 2 cells in each slot
1214        let (sum, max) = cc.displacement(&id, &[32, 48]);
1215        assert_eq!(sum, 4); // |32-30| + |48-50| = 2 + 2
1216        assert_eq!(max, 2);
1217    }
1218
1219    #[test]
1220    fn coherence_displacement_without_previous() {
1221        let cc = CoherenceCache::new(64);
1222        let id = make_coherence_id(1);
1223
1224        let (sum, max) = cc.displacement(&id, &[30, 50]);
1225        assert_eq!(sum, 0);
1226        assert_eq!(max, 0);
1227    }
1228
1229    #[test]
1230    fn coherence_displacement_different_lengths() {
1231        let mut cc = CoherenceCache::new(64);
1232        let id = make_coherence_id(1);
1233
1234        cc.store(id, smallvec::smallvec![30u16, 50u16]);
1235
1236        // New allocation has 3 elements (extra element counted as displacement)
1237        let (sum, max) = cc.displacement(&id, &[30, 50, 10]);
1238        assert_eq!(sum, 10);
1239        assert_eq!(max, 10);
1240    }
1241
1242    #[test]
1243    fn coherence_from_cache_key() {
1244        let key = make_key(80, 24);
1245        let id = CoherenceId::from_cache_key(&key);
1246
1247        // Same constraints + direction should produce same ID regardless of area
1248        let key2 = make_key(120, 40);
1249        let id2 = CoherenceId::from_cache_key(&key2);
1250
1251        assert_eq!(id, id2);
1252    }
1253
1254    // --- unit_cache_reuse ---
1255
1256    #[test]
1257    fn unit_cache_reuse_unchanged_constraints_yield_identical_layout() {
1258        use crate::round_layout_stable;
1259
1260        let mut cc = CoherenceCache::new(64);
1261        let id = make_coherence_id(1);
1262
1263        // First layout at width 80
1264        let targets = [26.67, 26.67, 26.66];
1265        let total = 80;
1266        let alloc1 = round_layout_stable(&targets, total, cc.get(&id));
1267        cc.store(id, alloc1.clone());
1268
1269        // Same constraints, same width → should produce identical result
1270        let alloc2 = round_layout_stable(&targets, total, cc.get(&id));
1271        assert_eq!(alloc1, alloc2, "Same inputs should yield identical layout");
1272    }
1273
1274    // --- e2e_resize_sweep ---
1275
1276    #[test]
1277    fn e2e_resize_sweep_bounded_displacement() {
1278        use crate::round_layout_stable;
1279
1280        let mut cc = CoherenceCache::new(64);
1281        let id = make_coherence_id(1);
1282
1283        // Equal three-way split: targets are total/3 each
1284        // Sweep terminal width from 60 to 120 in steps of 1
1285        let mut max_displacement_ever: u32 = 0;
1286        let mut total_displacement_sum: u64 = 0;
1287        let steps = 61; // 60..=120
1288
1289        for width in 60u16..=120 {
1290            let third = f64::from(width) / 3.0;
1291            let targets = [third, third, third];
1292
1293            let prev = cc.get(&id);
1294            let alloc = round_layout_stable(&targets, width, prev);
1295
1296            let (d_sum, d_max) = cc.displacement(&id, &alloc);
1297            total_displacement_sum += d_sum;
1298            max_displacement_ever = max_displacement_ever.max(d_max);
1299
1300            cc.store(id, alloc);
1301        }
1302
1303        // Each 1-cell width change should cause at most 1 cell of displacement
1304        // in each slot (ideal: only 1 slot changes by 1).
1305        assert!(
1306            max_displacement_ever <= 2,
1307            "Max single-step displacement should be <=2 cells, got {}",
1308            max_displacement_ever
1309        );
1310
1311        // Average displacement per step should be ~1 (one extra cell redistributed)
1312        let avg = total_displacement_sum as f64 / steps as f64;
1313        assert!(
1314            avg < 3.0,
1315            "Average displacement per step should be <3 cells, got {:.2}",
1316            avg
1317        );
1318    }
1319
1320    #[test]
1321    fn e2e_resize_sweep_deterministic() {
1322        use crate::round_layout_stable;
1323
1324        // Two identical sweeps should produce identical displacement logs
1325        let sweep = |seed: u16| -> Vec<(u16, crate::Sizes, u64, u32)> {
1326            let mut cc = CoherenceCache::new(64);
1327            let id = CoherenceId::new(
1328                &[Constraint::Percentage(30.0), Constraint::Fill],
1329                Direction::Horizontal,
1330            );
1331
1332            let mut log = Vec::new();
1333            for width in (40 + seed)..(100 + seed) {
1334                let targets = [f64::from(width) * 0.3, f64::from(width) * 0.7];
1335                let prev = cc.get(&id);
1336                let alloc = round_layout_stable(&targets, width, prev);
1337                let (d_sum, d_max) = cc.displacement(&id, &alloc);
1338                cc.store(id, alloc.clone());
1339                log.push((width, alloc, d_sum, d_max));
1340            }
1341            log
1342        };
1343
1344        let log1 = sweep(0);
1345        let log2 = sweep(0);
1346        assert_eq!(log1, log2, "Identical sweeps should produce identical logs");
1347    }
1348
1349    #[test]
1350    fn default_coherence_cache_capacity_is_64() {
1351        let cc = CoherenceCache::default();
1352        assert_eq!(cc.max_entries, 64);
1353    }
1354
1355    // ── S3-FIFO Layout Cache ────────────────────────────────────────
1356
1357    #[cfg(feature = "experimental")]
1358    fn s3_fifo_test_key(x: u16, w: u16) -> LayoutCacheKey {
1359        LayoutCacheKey {
1360            area_x: x,
1361            area_y: 0,
1362            area_width: w,
1363            area_height: 24,
1364            constraints_hash: 42,
1365            constraints_hash_fx: 42,
1366            constraints_len: 2,
1367            direction: Direction::Horizontal,
1368            intrinsics_hash: None,
1369            intrinsics_hash_fx: None,
1370        }
1371    }
1372
1373    #[test]
1374    #[cfg(feature = "experimental")]
1375    fn s3fifo_layout_new_is_empty() {
1376        let cache = S3FifoLayoutCache::new(64);
1377        assert!(cache.is_empty());
1378        assert_eq!(cache.len(), 0);
1379        assert_eq!(cache.capacity(), 64);
1380    }
1381
1382    #[test]
1383    #[cfg(feature = "experimental")]
1384    fn s3fifo_layout_default_capacity() {
1385        let cache = S3FifoLayoutCache::default();
1386        assert_eq!(cache.capacity(), 64);
1387    }
1388
1389    #[test]
1390    #[cfg(feature = "experimental")]
1391    fn s3fifo_layout_get_or_compute_caches() {
1392        let mut cache = S3FifoLayoutCache::new(64);
1393        let key = s3_fifo_test_key(0, 80);
1394        let rects1 = cache.get_or_compute(key, || smallvec::smallvec![Rect::new(0, 0, 40, 24)]);
1395        let rects2 = cache.get_or_compute(key, || panic!("should not recompute"));
1396        assert_eq!(rects1, rects2);
1397        let stats = cache.stats();
1398        assert_eq!(stats.hits, 1);
1399        assert_eq!(stats.misses, 1);
1400    }
1401
1402    #[test]
1403    #[cfg(feature = "experimental")]
1404    fn s3fifo_layout_generation_invalidation() {
1405        let mut cache = S3FifoLayoutCache::new(64);
1406        let key = s3_fifo_test_key(0, 80);
1407        cache.get_or_compute(key, || smallvec::smallvec![Rect::new(0, 0, 40, 24)]);
1408
1409        cache.invalidate_all();
1410
1411        // After invalidation, should recompute
1412        let rects = cache.get_or_compute(key, || smallvec::smallvec![Rect::new(0, 0, 80, 24)]);
1413        assert_eq!(rects.as_slice(), &[Rect::new(0, 0, 80, 24)]);
1414        let stats = cache.stats();
1415        assert_eq!(stats.misses, 2);
1416    }
1417
1418    #[test]
1419    #[cfg(feature = "experimental")]
1420    fn s3fifo_layout_clear() {
1421        let mut cache = S3FifoLayoutCache::new(64);
1422        let key = s3_fifo_test_key(0, 80);
1423        cache.get_or_compute(key, || smallvec::smallvec![Rect::new(0, 0, 40, 24)]);
1424        cache.clear();
1425        assert!(cache.is_empty());
1426    }
1427
1428    #[test]
1429    #[cfg(feature = "experimental")]
1430    fn s3fifo_layout_different_keys() {
1431        let mut cache = S3FifoLayoutCache::new(64);
1432        let k1 = s3_fifo_test_key(0, 80);
1433        let k2 = s3_fifo_test_key(0, 120);
1434        cache.get_or_compute(k1, || smallvec::smallvec![Rect::new(0, 0, 40, 24)]);
1435        cache.get_or_compute(k2, || smallvec::smallvec![Rect::new(0, 0, 60, 24)]);
1436        assert_eq!(cache.len(), 2);
1437    }
1438
1439    #[test]
1440    #[cfg(feature = "experimental")]
1441    fn s3fifo_layout_reset_stats() {
1442        let mut cache = S3FifoLayoutCache::new(64);
1443        let key = s3_fifo_test_key(0, 80);
1444        cache.get_or_compute(key, crate::Rects::new);
1445        cache.get_or_compute(key, crate::Rects::new);
1446        cache.reset_stats();
1447        let stats = cache.stats();
1448        assert_eq!(stats.hits, 0);
1449        assert_eq!(stats.misses, 0);
1450    }
1451
1452    #[test]
1453    #[cfg(feature = "experimental")]
1454    fn s3fifo_layout_produces_same_results_as_lru() {
1455        let mut lru = LayoutCache::new(64);
1456        let mut s3 = S3FifoLayoutCache::new(64);
1457
1458        for w in [80, 100, 120, 160, 200] {
1459            let key = s3_fifo_test_key(0, w);
1460            let expected = smallvec::smallvec![Rect::new(0, 0, w / 2, 24)];
1461            let lru_r = lru.get_or_compute(key, || expected.clone());
1462            let s3_r = s3.get_or_compute(key, || expected.clone());
1463            assert_eq!(lru_r, s3_r, "mismatch for width={w}");
1464        }
1465    }
1466}