1use std::hash::{Hash, Hasher};
54
55use ftui_core::geometry::Rect;
56use rustc_hash::FxHashMap;
57
58use crate::{Constraint, Direction, LayoutSizeHint};
59
60#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
69pub struct LayoutCacheKey {
70 pub area_x: u16,
72 pub area_y: u16,
74 pub area_width: u16,
76 pub area_height: u16,
78 pub constraints_hash: u64,
80 pub constraints_hash_fx: u64,
82 pub constraints_len: u16,
84 pub direction: Direction,
86 pub intrinsics_hash: Option<u64>,
88 pub intrinsics_hash_fx: Option<u64>,
90}
91
92impl LayoutCacheKey {
93 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 #[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 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 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#[derive(Clone, Debug)]
209struct CachedLayoutEntry {
210 chunks: crate::Rects,
212 generation: u64,
214 access_count: u32,
216}
217
218#[derive(Debug, Clone, Default)]
220pub struct LayoutCacheStats {
221 pub entries: usize,
223 pub hits: u64,
225 pub misses: u64,
227 pub hit_rate: f64,
229}
230
231#[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 #[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 pub fn get_or_compute<F>(&mut self, key: LayoutCacheKey, compute: F) -> crate::Rects
299 where
300 F: FnOnce() -> crate::Rects,
301 {
302 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 self.misses += 1;
313 let chunks = compute();
314
315 if self.entries.len() >= self.max_entries {
317 self.evict_lru();
318 }
319
320 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 #[inline]
349 pub fn invalidate_all(&mut self) {
350 self.generation = self.generation.wrapping_add(1);
351 }
352
353 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 #[inline]
374 pub fn reset_stats(&mut self) {
375 self.hits = 0;
376 self.misses = 0;
377 }
378
379 #[inline]
385 pub fn clear(&mut self) {
386 self.entries.clear();
387 self.generation = self.generation.wrapping_add(1);
388 }
389
390 #[inline]
392 pub fn len(&self) -> usize {
393 self.entries.len()
394 }
395
396 #[inline]
398 pub fn is_empty(&self) -> bool {
399 self.entries.is_empty()
400 }
401
402 #[inline]
404 pub fn capacity(&self) -> usize {
405 self.max_entries
406 }
407
408 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 fn default() -> Self {
424 Self::new(64)
425 }
426}
427
428#[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 #[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 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 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 #[inline]
498 pub fn invalidate_all(&mut self) {
499 self.generation = self.generation.wrapping_add(1);
500 }
501
502 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 #[inline]
519 pub fn reset_stats(&mut self) {
520 self.hits = 0;
521 self.misses = 0;
522 }
523
524 #[inline]
526 pub fn clear(&mut self) {
527 self.cache.clear();
528 self.generation = self.generation.wrapping_add(1);
529 }
530
531 #[inline]
533 pub fn len(&self) -> usize {
534 self.cache.len()
535 }
536
537 #[inline]
539 pub fn is_empty(&self) -> bool {
540 self.cache.is_empty()
541 }
542
543 #[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#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
568pub struct CoherenceId {
569 pub constraints_hash: u64,
571 pub direction: Direction,
573}
574
575impl CoherenceId {
576 pub fn new(constraints: &[Constraint], direction: Direction) -> Self {
578 Self {
579 constraints_hash: LayoutCacheKey::hash_constraints(constraints).0,
580 direction,
581 }
582 }
583
584 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#[derive(Debug, Clone)]
621pub struct CoherenceCache {
622 entries: FxHashMap<CoherenceId, CoherenceEntry>,
623 max_entries: usize,
624 tick: u64,
626}
627
628#[derive(Debug, Clone)]
629struct CoherenceEntry {
630 allocation: crate::Sizes,
632 last_stored: u64,
634}
635
636impl CoherenceCache {
637 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 #[inline]
651 pub fn get(&self, id: &CoherenceId) -> Option<crate::Sizes> {
652 self.entries.get(id).map(|e| e.allocation.clone())
653 }
654
655 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 #[inline]
676 pub fn clear(&mut self) {
677 self.entries.clear();
678 }
679
680 #[inline]
682 pub fn len(&self) -> usize {
683 self.entries.len()
684 }
685
686 #[inline]
688 pub fn is_empty(&self) -> bool {
689 self.entries.is_empty()
690 }
691
692 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 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 #[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 #[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 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 cache.get_or_compute(k1, || should_not_call("k1 should hit"));
907
908 cache.get_or_compute(k3, || smallvec::smallvec![Rect::new(0, 0, 30, 30)]);
910
911 assert_eq!(cache.len(), 2);
912
913 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 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); cache.get_or_compute(k1, || should_not_call("hit")); cache.get_or_compute(k2, crate::Rects::new); 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 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 #[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 #[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 #[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 cache.get_or_compute(key, crate::Rects::new);
1116
1117 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 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 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 let (sum, max) = cc.displacement(&id, &[32, 48]);
1215 assert_eq!(sum, 4); 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 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 let key2 = make_key(120, 40);
1249 let id2 = CoherenceId::from_cache_key(&key2);
1250
1251 assert_eq!(id, id2);
1252 }
1253
1254 #[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 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 let alloc2 = round_layout_stable(&targets, total, cc.get(&id));
1271 assert_eq!(alloc1, alloc2, "Same inputs should yield identical layout");
1272 }
1273
1274 #[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 let mut max_displacement_ever: u32 = 0;
1286 let mut total_displacement_sum: u64 = 0;
1287 let steps = 61; 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 assert!(
1306 max_displacement_ever <= 2,
1307 "Max single-step displacement should be <=2 cells, got {}",
1308 max_displacement_ever
1309 );
1310
1311 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 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 #[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 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}