Skip to main content

sui_text/
cache.rs

1use std::{
2    collections::hash_map::DefaultHasher,
3    hash::{BuildHasher, Hash, Hasher},
4};
5
6// Buckets are confirmed by comparing whole keys, so the bucket hash only needs
7// to be fast; every label paint looks its layout up.
8use rustc_hash::FxBuildHasher;
9
10use sui_core::{FontHandle, Size};
11
12use crate::{
13    font::FaceCacheKey,
14    model::{
15        FontFamilyStack, TextDocument, TextLayout, TextLayoutId, TextParagraphStyle, TextStyle,
16    },
17    style::{FontFeatures, FontStretch, FontStyle},
18};
19
20#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
21struct SizeCacheKey {
22    width_bits: u32,
23    height_bits: u32,
24}
25
26impl From<Size> for SizeCacheKey {
27    fn from(value: Size) -> Self {
28        Self {
29            width_bits: value.width.to_bits(),
30            height_bits: value.height.to_bits(),
31        }
32    }
33}
34
35#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
36struct TextStyleCacheKey {
37    font_handle: Option<u64>,
38    font_families: Option<FontFamilyStack>,
39    font_size_bits: u32,
40    line_height_bits: u32,
41    weight: u16,
42    style: FontStyle,
43    stretch: FontStretch,
44    // Features are hashed into a u64 so the key stays `Copy` and cheap to compare; layouts with
45    // different OpenType features must not share a cache entry.
46    features_hash: u64,
47}
48
49impl TextStyleCacheKey {
50    fn new(style: &TextStyle) -> Self {
51        Self {
52            font_handle: style.font.map(FontHandle::get),
53            font_families: style.font_families,
54            font_size_bits: style.font_size.to_bits(),
55            line_height_bits: style.line_height.to_bits(),
56            weight: style.weight.value(),
57            style: style.style,
58            stretch: style.stretch,
59            features_hash: hash_features(&style.features),
60        }
61    }
62}
63
64fn hash_features(features: &FontFeatures) -> u64 {
65    hash_value(features)
66}
67
68fn hash_value(value: &impl Hash) -> u64 {
69    let mut hasher = DefaultHasher::new();
70    value.hash(&mut hasher);
71    hasher.finish()
72}
73
74#[derive(Debug, Clone, PartialEq, Eq, Hash)]
75struct TextSpanCacheKey {
76    text: String,
77    style: TextStyleCacheKey,
78    face: FaceCacheKey,
79}
80
81#[derive(Debug, Clone, PartialEq, Eq, Hash)]
82struct TextParagraphCacheKey {
83    style: TextParagraphStyle,
84    spans: Vec<TextSpanCacheKey>,
85}
86
87#[derive(Debug, Clone, PartialEq, Eq, Hash)]
88pub(crate) struct TextLayoutCacheKey {
89    paragraphs: Vec<TextParagraphCacheKey>,
90    box_size: Option<SizeCacheKey>,
91}
92
93impl TextLayoutCacheKey {
94    pub(crate) fn stable_layout_id(
95        document: &TextDocument,
96        span_face_keys: &[FaceCacheKey],
97        box_size: Option<Size>,
98    ) -> TextLayoutId {
99        let mut state = DefaultHasher::new();
100        Self::hash_document_into(&mut state, document, span_face_keys, box_size);
101        TextLayoutId::new(state.finish())
102    }
103
104    pub(crate) fn new(
105        document: &TextDocument,
106        span_face_keys: &[FaceCacheKey],
107        box_size: Option<Size>,
108    ) -> Self {
109        let mut span_index = 0;
110        let paragraphs = document
111            .paragraphs
112            .iter()
113            .map(|paragraph| TextParagraphCacheKey {
114                style: paragraph.style.clone(),
115                spans: paragraph
116                    .spans
117                    .iter()
118                    .map(|span| {
119                        let face = span_face_keys[span_index];
120                        span_index += 1;
121                        TextSpanCacheKey {
122                            text: span.text.clone(),
123                            style: TextStyleCacheKey::new(&span.style),
124                            face,
125                        }
126                    })
127                    .collect(),
128            })
129            .collect();
130        debug_assert_eq!(span_index, span_face_keys.len());
131
132        Self {
133            paragraphs,
134            box_size: box_size.map(SizeCacheKey::from),
135        }
136    }
137
138    fn hash_document<S: BuildHasher>(
139        hasher: &S,
140        document: &TextDocument,
141        span_face_keys: &[FaceCacheKey],
142        box_size: Option<Size>,
143    ) -> u64 {
144        let mut state = hasher.build_hasher();
145        Self::hash_document_into(&mut state, document, span_face_keys, box_size);
146        state.finish()
147    }
148
149    fn hash_document_into<H: Hasher>(
150        state: &mut H,
151        document: &TextDocument,
152        span_face_keys: &[FaceCacheKey],
153        box_size: Option<Size>,
154    ) {
155        document.paragraphs.len().hash(state);
156        let mut span_index = 0;
157        for paragraph in &document.paragraphs {
158            paragraph.style.hash(state);
159            paragraph.spans.len().hash(state);
160            for span in &paragraph.spans {
161                span.text.hash(state);
162                TextStyleCacheKey::new(&span.style).hash(state);
163                span_face_keys[span_index].hash(state);
164                span_index += 1;
165            }
166        }
167        debug_assert_eq!(span_index, span_face_keys.len());
168        box_size.map(SizeCacheKey::from).hash(state);
169    }
170
171    fn matches_document(
172        &self,
173        document: &TextDocument,
174        span_face_keys: &[FaceCacheKey],
175        box_size: Option<Size>,
176    ) -> bool {
177        if self.box_size != box_size.map(SizeCacheKey::from) {
178            return false;
179        }
180        if self.paragraphs.len() != document.paragraphs.len() {
181            return false;
182        }
183
184        let mut span_index = 0;
185        for (cached_paragraph, paragraph) in self.paragraphs.iter().zip(&document.paragraphs) {
186            if cached_paragraph.style != paragraph.style {
187                return false;
188            }
189            if cached_paragraph.spans.len() != paragraph.spans.len() {
190                return false;
191            }
192
193            for (cached_span, span) in cached_paragraph.spans.iter().zip(&paragraph.spans) {
194                if cached_span.text != span.text
195                    || cached_span.style != TextStyleCacheKey::new(&span.style)
196                    || cached_span.face != span_face_keys[span_index]
197                {
198                    return false;
199                }
200                span_index += 1;
201            }
202        }
203
204        span_index == span_face_keys.len()
205    }
206}
207
208// Cache-owned references are bounded independently of layouts pinned by widgets
209// or immutable scene frames. Large one-off documents bypass this cache.
210const MAX_LAYOUT_ENTRIES: usize = 4_096;
211const MAX_LAYOUT_BYTES: usize = 32 * 1024 * 1024;
212
213#[derive(Debug)]
214pub(crate) struct TextLayoutCache {
215    entries: lru::LruCache<u64, Vec<TextLayoutCacheEntry>>,
216    entry_count: usize,
217    retained_bytes: usize,
218    max_entries: usize,
219    max_bytes: usize,
220    hits: usize,
221    misses: usize,
222}
223
224#[derive(Debug, Clone)]
225struct TextLayoutCacheEntry {
226    key: TextLayoutCacheKey,
227    layout: TextLayout,
228    retained_bytes: usize,
229}
230
231impl Default for TextLayoutCache {
232    fn default() -> Self {
233        Self::with_limits(MAX_LAYOUT_ENTRIES, MAX_LAYOUT_BYTES)
234    }
235}
236
237fn allocation_bytes<T>(values: &Vec<T>) -> usize {
238    values.capacity().saturating_mul(size_of::<T>())
239}
240
241fn layout_entry_bytes(key: &TextLayoutCacheKey, layout: &TextLayout) -> usize {
242    // Shared font bytes belong to the font registry; count layout-owned arrays
243    // and strings, conservatively charging shared layout data to each entry.
244    let data = &layout.data;
245    size_of::<TextLayoutCacheEntry>()
246        + size_of::<crate::model::TextLayoutData>()
247        + allocation_bytes(&key.paragraphs)
248        + key
249            .paragraphs
250            .iter()
251            .map(|paragraph| {
252                allocation_bytes(&paragraph.spans)
253                    + paragraph
254                        .spans
255                        .iter()
256                        .map(|span| span.text.capacity())
257                        .sum::<usize>()
258            })
259            .sum::<usize>()
260        + data.text.capacity()
261        + allocation_bytes(&data.faces)
262        + allocation_bytes(&data.paragraphs)
263        + allocation_bytes(&data.lines)
264        + data
265            .lines
266            .iter()
267            .map(|line| allocation_bytes(&line.clusters))
268            .sum::<usize>()
269        + allocation_bytes(&data.runs)
270        + allocation_bytes(&data.clusters)
271        + allocation_bytes(&data.glyphs)
272        + allocation_bytes(&layout.document.paragraphs)
273        + layout
274            .document
275            .paragraphs
276            .iter()
277            .map(|paragraph| {
278                allocation_bytes(&paragraph.spans)
279                    + paragraph
280                        .spans
281                        .iter()
282                        .map(|span| {
283                            span.text.capacity()
284                                + span.style.features.len() * size_of::<crate::style::FontFeature>()
285                        })
286                        .sum::<usize>()
287            })
288            .sum::<usize>()
289}
290
291#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
292pub struct TextLayoutCacheSnapshot {
293    pub entries: usize,
294    pub hits: usize,
295    pub misses: usize,
296}
297
298impl TextLayoutCacheSnapshot {
299    pub const fn requests(self) -> usize {
300        self.hits + self.misses
301    }
302
303    pub fn hit_rate(self) -> f64 {
304        let requests = self.requests();
305        if requests == 0 {
306            0.0
307        } else {
308            self.hits as f64 / requests as f64
309        }
310    }
311}
312
313impl TextLayoutCache {
314    pub(crate) fn with_limits(max_entries: usize, max_bytes: usize) -> Self {
315        Self {
316            entries: lru::LruCache::unbounded(),
317            entry_count: 0,
318            retained_bytes: 0,
319            max_entries,
320            max_bytes,
321            hits: 0,
322            misses: 0,
323        }
324    }
325
326    pub(crate) fn snapshot(&self) -> TextLayoutCacheSnapshot {
327        TextLayoutCacheSnapshot {
328            entries: self.entry_count,
329            hits: self.hits,
330            misses: self.misses,
331        }
332    }
333
334    pub(crate) fn get(
335        &mut self,
336        document: &TextDocument,
337        span_face_keys: &[FaceCacheKey],
338        box_size: Option<Size>,
339    ) -> Option<TextLayout> {
340        let hash =
341            TextLayoutCacheKey::hash_document(&FxBuildHasher, document, span_face_keys, box_size);
342        let cached = self
343            .entries
344            .get(&hash)
345            .and_then(|bucket| {
346                bucket.iter().find(|entry| {
347                    entry
348                        .key
349                        .matches_document(document, span_face_keys, box_size)
350                })
351            })
352            .map(|entry| entry.layout.clone());
353        if cached.is_some() {
354            self.hits += 1;
355        } else {
356            self.misses += 1;
357        }
358        cached
359    }
360
361    pub(crate) fn insert(
362        &mut self,
363        document: &TextDocument,
364        span_face_keys: &[FaceCacheKey],
365        box_size: Option<Size>,
366        layout: TextLayout,
367    ) {
368        let hash =
369            TextLayoutCacheKey::hash_document(&FxBuildHasher, document, span_face_keys, box_size);
370        let key = TextLayoutCacheKey::new(document, span_face_keys, box_size);
371        let retained_bytes = layout_entry_bytes(&key, &layout);
372        if retained_bytes > self.max_bytes || self.max_entries == 0 {
373            return;
374        }
375        if let Some(existing) = self
376            .entries
377            .get_mut(&hash)
378            .and_then(|bucket| bucket.iter_mut().find(|entry| entry.key == key))
379        {
380            self.retained_bytes -= existing.retained_bytes;
381            existing.layout = layout;
382            existing.retained_bytes = retained_bytes;
383        } else {
384            let bucket = self.entries.get_or_insert_mut(hash, Vec::new);
385            bucket.push(TextLayoutCacheEntry {
386                key,
387                layout,
388                retained_bytes,
389            });
390            self.entry_count += 1;
391        }
392        self.retained_bytes += retained_bytes;
393        while self.entry_count > self.max_entries || self.retained_bytes > self.max_bytes {
394            let Some((_, bucket)) = self.entries.pop_lru() else {
395                break;
396            };
397            self.entry_count -= bucket.len();
398            self.retained_bytes -= bucket
399                .iter()
400                .map(|entry| entry.retained_bytes)
401                .sum::<usize>();
402        }
403    }
404}
405
406// Size-only results are a few bytes each; their keys carry the measured text.
407const MAX_SIZE_ENTRIES: usize = 16_384;
408const MAX_SIZE_BYTES: usize = 4 * 1024 * 1024;
409
410/// Measured sizes by document and wrapping width. Box height never affects a
411/// size-only measurement, so it is not part of the key.
412#[derive(Debug)]
413pub(crate) struct TextSizeCache {
414    entries: lru::LruCache<u64, Vec<TextSizeCacheEntry>>,
415    entry_count: usize,
416    retained_bytes: usize,
417    max_entries: usize,
418    max_bytes: usize,
419}
420
421#[derive(Debug)]
422struct TextSizeCacheEntry {
423    key: TextLayoutCacheKey,
424    size: Size,
425    retained_bytes: usize,
426}
427
428/// A key prepared before the document is consumed by measurement.
429pub(crate) struct TextSizeCacheSlot {
430    hash: u64,
431    key: TextLayoutCacheKey,
432}
433
434impl Default for TextSizeCache {
435    fn default() -> Self {
436        Self::with_limits(MAX_SIZE_ENTRIES, MAX_SIZE_BYTES)
437    }
438}
439
440fn width_box(width: Option<f32>) -> Option<Size> {
441    width.map(|width| Size::new(width, 0.0))
442}
443
444impl TextSizeCache {
445    pub(crate) fn with_limits(max_entries: usize, max_bytes: usize) -> Self {
446        Self {
447            entries: lru::LruCache::unbounded(),
448            entry_count: 0,
449            retained_bytes: 0,
450            max_entries,
451            max_bytes,
452        }
453    }
454
455    #[cfg(test)]
456    pub(crate) fn len(&self) -> usize {
457        self.entry_count
458    }
459
460    pub(crate) fn get(
461        &mut self,
462        document: &TextDocument,
463        span_face_keys: &[FaceCacheKey],
464        width: Option<f32>,
465    ) -> Option<Size> {
466        let box_size = width_box(width);
467        let hash =
468            TextLayoutCacheKey::hash_document(&FxBuildHasher, document, span_face_keys, box_size);
469        self.entries.get(&hash).and_then(|bucket| {
470            bucket
471                .iter()
472                .find(|entry| {
473                    entry
474                        .key
475                        .matches_document(document, span_face_keys, box_size)
476                })
477                .map(|entry| entry.size)
478        })
479    }
480
481    pub(crate) fn slot(
482        &self,
483        document: &TextDocument,
484        span_face_keys: &[FaceCacheKey],
485        width: Option<f32>,
486    ) -> TextSizeCacheSlot {
487        let box_size = width_box(width);
488        TextSizeCacheSlot {
489            hash: TextLayoutCacheKey::hash_document(
490                &FxBuildHasher,
491                document,
492                span_face_keys,
493                box_size,
494            ),
495            key: TextLayoutCacheKey::new(document, span_face_keys, box_size),
496        }
497    }
498
499    pub(crate) fn insert(&mut self, slot: TextSizeCacheSlot, size: Size) {
500        let TextSizeCacheSlot { hash, key } = slot;
501        let retained_bytes = size_of::<TextSizeCacheEntry>()
502            + size_of::<[usize; 4]>()
503            + allocation_bytes(&key.paragraphs)
504            + key
505                .paragraphs
506                .iter()
507                .map(|paragraph| {
508                    allocation_bytes(&paragraph.spans)
509                        + paragraph
510                            .spans
511                            .iter()
512                            .map(|span| span.text.capacity())
513                            .sum::<usize>()
514                })
515                .sum::<usize>();
516        if retained_bytes > self.max_bytes || self.max_entries == 0 {
517            return;
518        }
519        let bucket = self.entries.get_or_insert_mut(hash, Vec::new);
520        if let Some(existing) = bucket.iter_mut().find(|entry| entry.key == key) {
521            existing.size = size;
522            return;
523        }
524        bucket.push(TextSizeCacheEntry {
525            key,
526            size,
527            retained_bytes,
528        });
529        self.entry_count += 1;
530        self.retained_bytes += retained_bytes;
531        while self.entry_count > self.max_entries || self.retained_bytes > self.max_bytes {
532            let Some((_, bucket)) = self.entries.pop_lru() else {
533                break;
534            };
535            self.entry_count -= bucket.len();
536            self.retained_bytes -= bucket
537                .iter()
538                .map(|entry| entry.retained_bytes)
539                .sum::<usize>();
540        }
541    }
542}