1use std::{
2 collections::hash_map::DefaultHasher,
3 hash::{BuildHasher, Hash, Hasher},
4};
5
6use 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_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 ¶graph.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(¶graph.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
208const 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 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(¶graph.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(¶graph.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
406const MAX_SIZE_ENTRIES: usize = 16_384;
408const MAX_SIZE_BYTES: usize = 4 * 1024 * 1024;
409
410#[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
428pub(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(¶graph.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}