1use std::collections::HashMap;
26use std::hash::Hash;
27
28use crate::font::FontId;
29use crate::shaping::{ShapedGlyph, ShapedLine, TextMetrics};
30
31pub const DEFAULT_MEMORY_BUDGET: usize = 16 * 1024 * 1024;
33
34#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
38pub struct FontSizeBits(pub u32);
39
40impl FontSizeBits {
41 #[inline(always)]
43 pub fn from_f32(size: f32) -> Self {
44 Self(size.to_bits())
45 }
46
47 #[inline(always)]
49 pub fn to_f32(self) -> f32 {
50 f32::from_bits(self.0)
51 }
52}
53
54#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
59pub struct TextHash(pub u64);
60
61impl TextHash {
62 pub fn from_bytes(bytes: &[u8]) -> Self {
64 let mut hash = 0xcbf29ce484222325u64;
66 for &byte in bytes {
67 hash = (hash ^ byte as u64).wrapping_mul(0x100000001b3);
68 }
69 Self(hash)
70 }
71
72 #[inline]
74 pub fn from_string(text: &str) -> Self {
75 Self::from_bytes(text.as_bytes())
76 }
77}
78
79#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
81pub struct ShapeCacheKey {
82 pub font_id: FontId,
84 pub font_size_bits: FontSizeBits,
86 pub text_hash: TextHash,
88 pub max_width_bits: MaxWidthBits,
91 pub family_hash: TextHash,
93 pub line_height_bits: LineHeightBits,
95}
96
97#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
100pub struct MaxWidthBits(pub u32);
101
102impl MaxWidthBits {
103 #[inline]
107 pub fn from_opt(width: Option<f32>) -> Self {
108 match width {
109 Some(w) if w.is_finite() && w > 0.0 => Self(w.to_bits()),
110 Some(w) if w.is_finite() && w <= 0.0 => Self(0),
111 _ => Self(u32::MAX),
112 }
113 }
114
115 #[inline]
119 pub fn to_opt(self) -> Option<f32> {
120 if self.0 == u32::MAX {
121 None
122 } else if self.0 == 0 {
123 Some(0.0)
124 } else {
125 Some(f32::from_bits(self.0))
126 }
127 }
128}
129
130#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
132pub struct LineHeightBits(pub u32);
133
134impl LineHeightBits {
135 #[inline]
138 pub fn from_f32(line_height: f32) -> Self {
139 if line_height.is_finite() && line_height > 0.0 {
140 Self(line_height.to_bits())
141 } else {
142 Self(0)
143 }
144 }
145
146 #[inline]
148 pub fn to_f32(self) -> f32 {
149 if self.0 == 0 {
150 0.0
151 } else {
152 f32::from_bits(self.0)
153 }
154 }
155}
156
157impl ShapeCacheKey {
158 #[inline]
160 pub fn new(font_id: FontId, font_size: f32, text: &str) -> Self {
161 Self::with_max_width_and_family(font_id, font_size, text, None, "", 0.0)
162 }
163
164 #[inline]
166 pub fn with_max_width(
167 font_id: FontId,
168 font_size: f32,
169 text: &str,
170 max_width: Option<f32>,
171 ) -> Self {
172 Self::with_max_width_and_family(font_id, font_size, text, max_width, "", 0.0)
173 }
174
175 #[inline]
177 pub fn with_max_width_and_family(
178 font_id: FontId,
179 font_size: f32,
180 text: &str,
181 max_width: Option<f32>,
182 family: &str,
183 line_height: f32,
184 ) -> Self {
185 Self {
186 font_id,
187 font_size_bits: FontSizeBits::from_f32(font_size),
188 text_hash: TextHash::from_string(text),
189 max_width_bits: MaxWidthBits::from_opt(max_width),
190 family_hash: TextHash::from_string(family),
191 line_height_bits: LineHeightBits::from_f32(line_height),
192 }
193 }
194}
195
196#[derive(Clone, Debug)]
198pub struct CachedShape {
199 pub lines: Vec<ShapedLine>,
201 pub metrics: TextMetrics,
203 pub mem_size: usize,
205}
206
207impl CachedShape {
208 pub fn new(lines: Vec<ShapedLine>, metrics: TextMetrics) -> Self {
210 let mem_size = Self::estimate_mem_size(&lines);
211 Self {
212 lines,
213 metrics,
214 mem_size,
215 }
216 }
217
218 fn estimate_mem_size(lines: &[ShapedLine]) -> usize {
220 let mut total = std::mem::size_of::<TextMetrics>() + std::mem::size_of::<usize>();
222 for line in lines {
224 total += std::mem::size_of::<ShapedLine>();
225 total += line.text.capacity();
226 total += line.glyphs.len() * std::mem::size_of::<ShapedGlyph>();
227 }
228 total
229 }
230}
231
232pub struct TextShapeCache {
252 entries: HashMap<ShapeCacheKey, (u64, CachedShape)>,
253 age: u64,
255 total_mem: usize,
257 budget: usize,
259 hits: u64,
261 misses: u64,
263}
264
265impl Default for TextShapeCache {
266 fn default() -> Self {
267 Self::new(DEFAULT_MEMORY_BUDGET)
268 }
269}
270
271impl TextShapeCache {
272 pub fn new(budget: usize) -> Self {
274 Self {
275 entries: HashMap::new(),
276 age: 0,
277 total_mem: 0,
278 budget,
279 hits: 0,
280 misses: 0,
281 }
282 }
283
284 #[inline]
286 pub fn with_default_budget() -> Self {
287 Self::default()
288 }
289
290 #[inline]
292 pub fn len(&self) -> usize {
293 self.entries.len()
294 }
295
296 #[inline]
298 pub fn is_empty(&self) -> bool {
299 self.entries.is_empty()
300 }
301
302 #[inline]
304 pub fn total_memory(&self) -> usize {
305 self.total_mem
306 }
307
308 #[inline]
310 pub fn budget(&self) -> usize {
311 self.budget
312 }
313
314 #[inline]
316 pub fn hits(&self) -> u64 {
317 self.hits
318 }
319
320 #[inline]
322 pub fn misses(&self) -> u64 {
323 self.misses
324 }
325
326 #[inline]
328 pub fn hit_rate(&self) -> f64 {
329 let total = self.hits + self.misses;
330 if total == 0 {
331 0.0
332 } else {
333 self.hits as f64 / total as f64
334 }
335 }
336
337 pub fn get(&mut self, key: &ShapeCacheKey) -> Option<&CachedShape> {
342 if let Some((entry_age, shape)) = self.entries.get_mut(key) {
343 *entry_age = self.age;
344 self.age += 1;
345 self.hits += 1;
346 Some(shape)
347 } else {
348 self.misses += 1;
349 None
350 }
351 }
352
353 pub fn insert(&mut self, key: ShapeCacheKey, shape: CachedShape) {
358 let mem_size = shape.mem_size;
359
360 if let Some((_, old)) = self.entries.remove(&key) {
362 self.total_mem = self.total_mem.saturating_sub(old.mem_size);
363 }
364
365 while self.total_mem + mem_size > self.budget && !self.entries.is_empty() {
367 self.evict_oldest();
368 }
369
370 self.total_mem += mem_size;
371 self.entries.insert(key, (self.age, shape));
372 self.age += 1;
373 }
374
375 fn evict_oldest(&mut self) {
377 if let Some(&oldest_key) = self
378 .entries
379 .iter()
380 .min_by_key(|(_, (age, _))| *age)
381 .map(|(k, _)| k)
382 {
383 if let Some((_, removed)) = self.entries.remove(&oldest_key) {
384 self.total_mem = self.total_mem.saturating_sub(removed.mem_size);
385 }
386 }
387 }
388
389 pub fn clear(&mut self) {
391 self.entries.clear();
392 self.total_mem = 0;
393 }
394
395 pub fn trim(&mut self, keep_age: u64) {
400 let current_age = self.age;
401 self.entries.retain(|_, (age, shape)| {
402 if *age + keep_age >= current_age {
403 true
404 } else {
405 self.total_mem = self.total_mem.saturating_sub(shape.mem_size);
406 false
407 }
408 });
409 }
410
411 pub fn invalidate_font(&mut self, font_id: FontId) {
414 self.entries.retain(|key, (_, shape)| {
415 if key.font_id == font_id {
416 self.total_mem = self.total_mem.saturating_sub(shape.mem_size);
417 false
418 } else {
419 true
420 }
421 });
422 }
423
424 pub fn invalidate_font_size(&mut self, font_size: f32) {
426 let bits = FontSizeBits::from_f32(font_size);
427 self.entries.retain(|key, (_, shape)| {
428 if key.font_size_bits == bits {
429 self.total_mem = self.total_mem.saturating_sub(shape.mem_size);
430 false
431 } else {
432 true
433 }
434 });
435 }
436
437 pub fn resize(&mut self, new_budget: usize) {
440 self.budget = new_budget;
441 while self.total_mem > self.budget && !self.entries.is_empty() {
442 self.evict_oldest();
443 }
444 }
445}
446
447impl std::fmt::Debug for TextShapeCache {
448 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
449 f.debug_struct("TextShapeCache")
450 .field("entries", &self.entries.len())
451 .field("total_mem", &self.total_mem)
452 .field("budget", &self.budget)
453 .field("hits", &self.hits)
454 .field("misses", &self.misses)
455 .field("hit_rate", &self.hit_rate())
456 .finish()
457 }
458}
459
460#[cfg(test)]
461mod tests {
462 use super::*;
463 use crate::shaping::TextMetrics;
464
465 fn make_cached_shape(width: f32, height: f32, line_count: usize) -> CachedShape {
466 let metrics = TextMetrics {
467 width,
468 height,
469 line_count,
470 };
471 CachedShape::new(vec![], metrics)
472 }
473
474 fn make_key(_id: u32, size: f32, text: &str) -> ShapeCacheKey {
475 ShapeCacheKey::new(FontId(dummy_font_id()), size, text)
476 }
477
478 fn dummy_font_id() -> fontdb::ID {
480 fontdb::ID::dummy()
483 }
484
485 fn make_key_v2(_id_val: u64, size: f32, text: &str) -> ShapeCacheKey {
486 ShapeCacheKey::new(FontId(dummy_font_id()), size, text)
487 }
488
489 #[test]
490 fn make_key_v2_compiles() {
491 let _ = make_key_v2(1, 16.0, "test");
492 }
493
494 #[test]
495 fn font_size_bits_roundtrip() {
496 let bits = FontSizeBits::from_f32(16.0);
497 assert_eq!(bits.to_f32(), 16.0);
498 let bits_nan = FontSizeBits::from_f32(f32::NAN);
499 assert!(bits_nan.to_f32().is_nan());
500 }
501
502 #[test]
503 fn text_hash_deterministic() {
504 let h1 = TextHash::from_string("Hello");
505 let h2 = TextHash::from_string("Hello");
506 assert_eq!(h1, h2);
507 let h3 = TextHash::from_string("World");
508 assert_ne!(h1, h3);
509 }
510
511 #[test]
512 fn text_hash_empty() {
513 let h = TextHash::from_string("");
514 assert_eq!(h.0, 0xcbf29ce484222325);
516 }
517
518 #[test]
519 fn cache_key_equality() {
520 let k1 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
521 let k2 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
522 assert_eq!(k1, k2);
523 }
524
525 #[test]
526 fn cache_key_differs_by_text() {
527 let k1 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
528 let k2 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "World");
529 assert_ne!(k1, k2);
530 }
531
532 #[test]
533 fn cache_key_differs_by_font_size() {
534 let k1 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
535 let k2 = ShapeCacheKey::new(FontId(dummy_font_id()), 20.0, "Hello");
536 assert_ne!(k1, k2);
537 }
538
539 #[test]
540 fn cache_new_is_empty() {
541 let cache = TextShapeCache::new(1024);
542 assert!(cache.is_empty());
543 assert_eq!(cache.len(), 0);
544 assert_eq!(cache.total_memory(), 0);
545 }
546
547 #[test]
548 fn cache_insert_and_get() {
549 let mut cache = TextShapeCache::new(1024 * 1024);
550 let key = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
551 let shape = make_cached_shape(100.0, 20.0, 1);
552 cache.insert(key, shape);
553 assert_eq!(cache.len(), 1);
554
555 let retrieved = cache.get(&key);
556 assert!(retrieved.is_some());
557 assert_eq!(retrieved.unwrap().metrics.width, 100.0);
558 }
559
560 #[test]
561 fn cache_miss_returns_none() {
562 let mut cache = TextShapeCache::new(1024 * 1024);
563 let key = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
564 assert!(cache.get(&key).is_none());
565 assert_eq!(cache.misses(), 1);
566 }
567
568 #[test]
569 fn cache_hit_rate() {
570 let mut cache = TextShapeCache::new(1024 * 1024);
571 let key = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
572 cache.insert(key, make_cached_shape(100.0, 20.0, 1));
573
574 cache.get(&key);
576 cache.get(&key);
577 let missing_key = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "World");
578 cache.get(&missing_key);
579
580 assert_eq!(cache.hits(), 2);
581 assert_eq!(cache.misses(), 1);
582 assert!((cache.hit_rate() - 2.0 / 3.0).abs() < 0.001);
583 }
584
585 #[test]
586 fn cache_eviction_on_budget_exceeded() {
587 let mut cache = TextShapeCache::new(200); let key1 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "A");
589 let key2 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "B");
590 let key3 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "C");
591
592 cache.insert(key1, make_cached_shape(10.0, 10.0, 1));
594 cache.insert(key2, make_cached_shape(20.0, 10.0, 1));
595 cache.insert(key3, make_cached_shape(30.0, 10.0, 1));
596
597 assert!(
599 cache.total_memory() <= 200,
600 "total mem {} should be <= 200",
601 cache.total_memory()
602 );
603 }
604
605 #[test]
606 fn cache_lru_eviction_order() {
607 let mut cache = TextShapeCache::new(300);
608 let key1 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "A");
609 let key2 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "B");
610 let key3 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "C");
611
612 cache.insert(key1, make_cached_shape(10.0, 10.0, 1));
613 cache.insert(key2, make_cached_shape(20.0, 10.0, 1));
614
615 cache.get(&key1);
617
618 cache.insert(key3, make_cached_shape(30.0, 10.0, 1));
620
621 assert!(cache.get(&key1).is_some(), "key1 should still be present");
622 }
624
625 #[test]
626 fn cache_clear() {
627 let mut cache = TextShapeCache::new(1024 * 1024);
628 let key = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
629 cache.insert(key, make_cached_shape(100.0, 20.0, 1));
630 assert!(!cache.is_empty());
631
632 cache.clear();
633 assert!(cache.is_empty());
634 assert_eq!(cache.total_memory(), 0);
635 }
636
637 #[test]
638 fn cache_update_existing_entry() {
639 let mut cache = TextShapeCache::new(1024 * 1024);
640 let key = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
641 cache.insert(key, make_cached_shape(100.0, 20.0, 1));
642
643 cache.insert(key, make_cached_shape(200.0, 40.0, 2));
645 assert_eq!(cache.len(), 1, "should still have 1 entry");
646
647 let retrieved = cache.get(&key).unwrap();
648 assert_eq!(retrieved.metrics.width, 200.0);
649 assert_eq!(retrieved.metrics.line_count, 2);
650 }
651
652 #[test]
653 fn cache_invalidate_font() {
654 let mut cache = TextShapeCache::new(1024 * 1024);
655 let fid = FontId(dummy_font_id());
656 let key = ShapeCacheKey::new(fid, 16.0, "Hello");
657 cache.insert(key, make_cached_shape(100.0, 20.0, 1));
658 assert!(!cache.is_empty());
659
660 cache.invalidate_font(fid);
661 assert!(cache.is_empty());
662 }
663
664 #[test]
665 fn cache_invalidate_font_size() {
666 let mut cache = TextShapeCache::new(1024 * 1024);
667 let key16 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "Hello");
668 let key20 = ShapeCacheKey::new(FontId(dummy_font_id()), 20.0, "Hello");
669 cache.insert(key16, make_cached_shape(100.0, 20.0, 1));
670 cache.insert(key20, make_cached_shape(120.0, 24.0, 1));
671 assert_eq!(cache.len(), 2);
672
673 cache.invalidate_font_size(16.0);
674 assert_eq!(cache.len(), 1);
675 assert!(cache.get(&key20).is_some());
676 }
677
678 #[test]
679 fn cache_resize_evicts() {
680 let mut cache = TextShapeCache::new(1024 * 1024);
681 for i in 0..10 {
682 let key = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, &format!("text{i}"));
683 cache.insert(key, make_cached_shape(100.0, 20.0, 1));
684 }
685 assert!(cache.total_memory() > 0);
686
687 cache.resize(1);
689 assert!(
691 cache.total_memory() <= 1 || cache.is_empty(),
692 "total mem {} should be <= 1 or cache empty",
693 cache.total_memory()
694 );
695 }
696
697 #[test]
698 fn cache_trim_old_entries() {
699 let mut cache = TextShapeCache::new(1024 * 1024);
700 let key1 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "A");
701 let key2 = ShapeCacheKey::new(FontId(dummy_font_id()), 16.0, "B");
702
703 cache.insert(key1, make_cached_shape(10.0, 10.0, 1));
704 cache.insert(key2, make_cached_shape(20.0, 10.0, 1));
706 cache.get(&key2);
710
711 cache.trim(1);
713
714 assert!(cache.get(&key2).is_some());
716 }
717
718 #[test]
719 fn cache_debug_format() {
720 let cache = TextShapeCache::new(1024);
721 let debug = format!("{:?}", cache);
722 assert!(debug.contains("TextShapeCache"));
723 assert!(debug.contains("hit_rate"));
724 }
725
726 #[test]
727 fn cached_shape_mem_size_estimation() {
728 let shape = make_cached_shape(100.0, 20.0, 1);
729 let _ = shape.mem_size;
733 }
734
735 #[test]
736 fn cached_shape_with_lines() {
737 use crate::shaping::ShapedLine;
738 let line = ShapedLine {
739 text: "Hello".to_string(),
740 rtl: false,
741 line_y: 0.0,
742 line_top: 0.0,
743 line_height: 20.0,
744 line_w: 50.0,
745 glyphs: vec![],
746 };
747 let shape = CachedShape::new(
748 vec![line],
749 TextMetrics {
750 width: 50.0,
751 height: 20.0,
752 line_count: 1,
753 },
754 );
755 assert!(shape.mem_size > 0);
756 }
757
758 #[test]
760 fn make_key_compiles() {
761 let _ = make_key(1, 16.0, "test");
762 }
763}