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_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 ¶graph.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(¶graph.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
202const 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 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(¶graph.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(¶graph.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}