Skip to main content

sui_text/
cache.rs

1use std::{
2    collections::hash_map::{DefaultHasher, RandomState},
3    hash::{BuildHasher, Hash, Hasher},
4};
5
6use sui_core::{FontHandle, Size};
7
8use crate::{
9    font::FaceCacheKey,
10    model::{TextDocument, TextLayout, TextLayoutId, TextParagraphStyle, TextStyle},
11    style::{FontFeatures, FontStretch, FontStyle},
12};
13
14#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
15struct SizeCacheKey {
16    width_bits: u32,
17    height_bits: u32,
18}
19
20impl From<Size> for SizeCacheKey {
21    fn from(value: Size) -> Self {
22        Self {
23            width_bits: value.width.to_bits(),
24            height_bits: value.height.to_bits(),
25        }
26    }
27}
28
29#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
30struct TextStyleCacheKey {
31    font_handle: Option<u64>,
32    font_families_hash: u64,
33    font_size_bits: u32,
34    line_height_bits: u32,
35    weight: u16,
36    style: FontStyle,
37    stretch: FontStretch,
38    // Features are hashed into a u64 so the key stays `Copy` and cheap to compare; layouts with
39    // different OpenType features must not share a cache entry.
40    features_hash: u64,
41}
42
43impl TextStyleCacheKey {
44    fn new(style: &TextStyle) -> Self {
45        Self {
46            font_handle: style.font.map(FontHandle::get),
47            font_families_hash: hash_value(&style.font_families),
48            font_size_bits: style.font_size.to_bits(),
49            line_height_bits: style.line_height.to_bits(),
50            weight: style.weight.value(),
51            style: style.style,
52            stretch: style.stretch,
53            features_hash: hash_features(&style.features),
54        }
55    }
56}
57
58fn hash_features(features: &FontFeatures) -> u64 {
59    hash_value(features)
60}
61
62fn hash_value(value: &impl Hash) -> u64 {
63    let mut hasher = DefaultHasher::new();
64    value.hash(&mut hasher);
65    hasher.finish()
66}
67
68#[derive(Debug, Clone, PartialEq, Eq, Hash)]
69struct TextSpanCacheKey {
70    text: String,
71    style: TextStyleCacheKey,
72    face: FaceCacheKey,
73}
74
75#[derive(Debug, Clone, PartialEq, Eq, Hash)]
76struct TextParagraphCacheKey {
77    style: TextParagraphStyle,
78    spans: Vec<TextSpanCacheKey>,
79}
80
81#[derive(Debug, Clone, PartialEq, Eq, Hash)]
82pub(crate) struct TextLayoutCacheKey {
83    paragraphs: Vec<TextParagraphCacheKey>,
84    box_size: Option<SizeCacheKey>,
85}
86
87impl TextLayoutCacheKey {
88    pub(crate) fn stable_layout_id(
89        document: &TextDocument,
90        span_face_keys: &[FaceCacheKey],
91        box_size: Option<Size>,
92    ) -> TextLayoutId {
93        let mut state = DefaultHasher::new();
94        Self::hash_document_into(&mut state, document, span_face_keys, box_size);
95        TextLayoutId::new(state.finish())
96    }
97
98    pub(crate) fn new(
99        document: &TextDocument,
100        span_face_keys: &[FaceCacheKey],
101        box_size: Option<Size>,
102    ) -> Self {
103        let mut span_index = 0;
104        let paragraphs = document
105            .paragraphs
106            .iter()
107            .map(|paragraph| TextParagraphCacheKey {
108                style: paragraph.style.clone(),
109                spans: paragraph
110                    .spans
111                    .iter()
112                    .map(|span| {
113                        let face = span_face_keys[span_index];
114                        span_index += 1;
115                        TextSpanCacheKey {
116                            text: span.text.clone(),
117                            style: TextStyleCacheKey::new(&span.style),
118                            face,
119                        }
120                    })
121                    .collect(),
122            })
123            .collect();
124        debug_assert_eq!(span_index, span_face_keys.len());
125
126        Self {
127            paragraphs,
128            box_size: box_size.map(SizeCacheKey::from),
129        }
130    }
131
132    fn hash_document<S: BuildHasher>(
133        hasher: &S,
134        document: &TextDocument,
135        span_face_keys: &[FaceCacheKey],
136        box_size: Option<Size>,
137    ) -> u64 {
138        let mut state = hasher.build_hasher();
139        Self::hash_document_into(&mut state, document, span_face_keys, box_size);
140        state.finish()
141    }
142
143    fn hash_document_into<H: Hasher>(
144        state: &mut H,
145        document: &TextDocument,
146        span_face_keys: &[FaceCacheKey],
147        box_size: Option<Size>,
148    ) {
149        document.paragraphs.len().hash(state);
150        let mut span_index = 0;
151        for paragraph in &document.paragraphs {
152            paragraph.style.hash(state);
153            paragraph.spans.len().hash(state);
154            for span in &paragraph.spans {
155                span.text.hash(state);
156                TextStyleCacheKey::new(&span.style).hash(state);
157                span_face_keys[span_index].hash(state);
158                span_index += 1;
159            }
160        }
161        debug_assert_eq!(span_index, span_face_keys.len());
162        box_size.map(SizeCacheKey::from).hash(state);
163    }
164
165    fn matches_document(
166        &self,
167        document: &TextDocument,
168        span_face_keys: &[FaceCacheKey],
169        box_size: Option<Size>,
170    ) -> bool {
171        if self.box_size != box_size.map(SizeCacheKey::from) {
172            return false;
173        }
174        if self.paragraphs.len() != document.paragraphs.len() {
175            return false;
176        }
177
178        let mut span_index = 0;
179        for (cached_paragraph, paragraph) in self.paragraphs.iter().zip(&document.paragraphs) {
180            if cached_paragraph.style != paragraph.style {
181                return false;
182            }
183            if cached_paragraph.spans.len() != paragraph.spans.len() {
184                return false;
185            }
186
187            for (cached_span, span) in cached_paragraph.spans.iter().zip(&paragraph.spans) {
188                if cached_span.text != span.text
189                    || cached_span.style != TextStyleCacheKey::new(&span.style)
190                    || cached_span.face != span_face_keys[span_index]
191                {
192                    return false;
193                }
194                span_index += 1;
195            }
196        }
197
198        span_index == span_face_keys.len()
199    }
200}
201
202// Cache-owned references are bounded independently of layouts pinned by widgets
203// or immutable scene frames. Large one-off documents bypass this cache.
204const MAX_LAYOUT_ENTRIES: usize = 4_096;
205const MAX_LAYOUT_BYTES: usize = 32 * 1024 * 1024;
206
207#[derive(Debug)]
208pub(crate) struct TextLayoutCache {
209    entries: lru::LruCache<u64, Vec<TextLayoutCacheEntry>>,
210    hash_builder: RandomState,
211    entry_count: usize,
212    retained_bytes: usize,
213    max_entries: usize,
214    max_bytes: usize,
215    hits: usize,
216    misses: usize,
217}
218
219#[derive(Debug, Clone)]
220struct TextLayoutCacheEntry {
221    key: TextLayoutCacheKey,
222    layout: TextLayout,
223    retained_bytes: usize,
224}
225
226impl Default for TextLayoutCache {
227    fn default() -> Self {
228        Self::with_limits(MAX_LAYOUT_ENTRIES, MAX_LAYOUT_BYTES)
229    }
230}
231
232fn allocation_bytes<T>(values: &Vec<T>) -> usize {
233    values.capacity().saturating_mul(size_of::<T>())
234}
235
236fn layout_entry_bytes(key: &TextLayoutCacheKey, layout: &TextLayout) -> usize {
237    // Shared font bytes belong to the font registry; count layout-owned arrays
238    // and strings, conservatively charging shared layout data to each entry.
239    let data = &layout.data;
240    size_of::<TextLayoutCacheEntry>()
241        + size_of::<crate::model::TextLayoutData>()
242        + allocation_bytes(&key.paragraphs)
243        + key
244            .paragraphs
245            .iter()
246            .map(|paragraph| {
247                allocation_bytes(&paragraph.spans)
248                    + paragraph
249                        .spans
250                        .iter()
251                        .map(|span| span.text.capacity())
252                        .sum::<usize>()
253            })
254            .sum::<usize>()
255        + data.text.capacity()
256        + allocation_bytes(&data.faces)
257        + allocation_bytes(&data.paragraphs)
258        + allocation_bytes(&data.lines)
259        + data
260            .lines
261            .iter()
262            .map(|line| allocation_bytes(&line.clusters))
263            .sum::<usize>()
264        + allocation_bytes(&data.runs)
265        + allocation_bytes(&data.clusters)
266        + allocation_bytes(&data.glyphs)
267        + allocation_bytes(&layout.document.paragraphs)
268        + layout
269            .document
270            .paragraphs
271            .iter()
272            .map(|paragraph| {
273                allocation_bytes(&paragraph.spans)
274                    + paragraph
275                        .spans
276                        .iter()
277                        .map(|span| {
278                            span.text.capacity()
279                                + span.style.features.len() * size_of::<crate::style::FontFeature>()
280                        })
281                        .sum::<usize>()
282            })
283            .sum::<usize>()
284}
285
286#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
287pub struct TextLayoutCacheSnapshot {
288    pub entries: usize,
289    pub hits: usize,
290    pub misses: usize,
291}
292
293impl TextLayoutCacheSnapshot {
294    pub const fn requests(self) -> usize {
295        self.hits + self.misses
296    }
297
298    pub fn hit_rate(self) -> f64 {
299        let requests = self.requests();
300        if requests == 0 {
301            0.0
302        } else {
303            self.hits as f64 / requests as f64
304        }
305    }
306}
307
308impl TextLayoutCache {
309    pub(crate) fn with_limits(max_entries: usize, max_bytes: usize) -> Self {
310        Self {
311            entries: lru::LruCache::unbounded(),
312            hash_builder: RandomState::new(),
313            entry_count: 0,
314            retained_bytes: 0,
315            max_entries,
316            max_bytes,
317            hits: 0,
318            misses: 0,
319        }
320    }
321
322    pub(crate) fn snapshot(&self) -> TextLayoutCacheSnapshot {
323        TextLayoutCacheSnapshot {
324            entries: self.entry_count,
325            hits: self.hits,
326            misses: self.misses,
327        }
328    }
329
330    pub(crate) fn get(
331        &mut self,
332        document: &TextDocument,
333        span_face_keys: &[FaceCacheKey],
334        box_size: Option<Size>,
335    ) -> Option<TextLayout> {
336        let hash = TextLayoutCacheKey::hash_document(
337            &self.hash_builder,
338            document,
339            span_face_keys,
340            box_size,
341        );
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 = TextLayoutCacheKey::hash_document(
369            &self.hash_builder,
370            document,
371            span_face_keys,
372            box_size,
373        );
374        let key = TextLayoutCacheKey::new(document, span_face_keys, box_size);
375        let retained_bytes = layout_entry_bytes(&key, &layout);
376        if retained_bytes > self.max_bytes || self.max_entries == 0 {
377            return;
378        }
379        if let Some(existing) = self
380            .entries
381            .get_mut(&hash)
382            .and_then(|bucket| bucket.iter_mut().find(|entry| entry.key == key))
383        {
384            self.retained_bytes -= existing.retained_bytes;
385            existing.layout = layout;
386            existing.retained_bytes = retained_bytes;
387        } else {
388            let bucket = self.entries.get_or_insert_mut(hash, Vec::new);
389            bucket.push(TextLayoutCacheEntry {
390                key,
391                layout,
392                retained_bytes,
393            });
394            self.entry_count += 1;
395        }
396        self.retained_bytes += retained_bytes;
397        while self.entry_count > self.max_entries || self.retained_bytes > self.max_bytes {
398            let Some((_, bucket)) = self.entries.pop_lru() else {
399                break;
400            };
401            self.entry_count -= bucket.len();
402            self.retained_bytes -= bucket
403                .iter()
404                .map(|entry| entry.retained_bytes)
405                .sum::<usize>();
406        }
407    }
408}