Skip to main content

gpui/text_system/
line_layout.rs

1use crate::{FontId, GlyphId, Pixels, PlatformTextSystem, Point, SharedString, Size, point, px};
2use collections::FxHashMap;
3use parking_lot::{Mutex, RwLock, RwLockUpgradableReadGuard};
4use smallvec::SmallVec;
5use std::{
6    borrow::Borrow,
7    hash::{Hash, Hasher},
8    ops::Range,
9    sync::Arc,
10};
11
12use super::LineWrapper;
13
14/// A laid out and styled line of text
15#[derive(Default, Debug)]
16pub struct LineLayout {
17    /// The font size for this line
18    pub font_size: Pixels,
19    /// The width of the line
20    pub width: Pixels,
21    /// The ascent of the line
22    pub ascent: Pixels,
23    /// The descent of the line
24    pub descent: Pixels,
25    /// The shaped runs that make up this line
26    pub runs: Vec<ShapedRun>,
27    /// The length of the line in utf-8 bytes
28    pub len: usize,
29}
30
31/// A run of text that has been shaped .
32#[derive(Debug, Clone)]
33pub struct ShapedRun {
34    /// The font id for this run
35    pub font_id: FontId,
36    /// The glyphs that make up this run
37    pub glyphs: Vec<ShapedGlyph>,
38}
39
40/// A single glyph, ready to paint.
41#[derive(Clone, Debug)]
42pub struct ShapedGlyph {
43    /// The ID for this glyph, as determined by the text system.
44    pub id: GlyphId,
45
46    /// The position of this glyph in its containing line.
47    pub position: Point<Pixels>,
48
49    /// The index of this glyph in the original text.
50    pub index: usize,
51
52    /// Whether this glyph is an emoji
53    pub is_emoji: bool,
54}
55
56impl LineLayout {
57    /// The index for the character at the given x coordinate
58    pub fn index_for_x(&self, x: Pixels) -> Option<usize> {
59        if x >= self.width {
60            None
61        } else {
62            for run in self.runs.iter().rev() {
63                for glyph in run.glyphs.iter().rev() {
64                    if glyph.position.x <= x {
65                        return Some(glyph.index);
66                    }
67                }
68            }
69            Some(0)
70        }
71    }
72
73    /// closest_index_for_x returns the character boundary closest to the given x coordinate
74    /// (e.g. to handle aligning up/down arrow keys)
75    pub fn closest_index_for_x(&self, x: Pixels) -> usize {
76        let mut prev_index = 0;
77        let mut prev_x = px(0.);
78
79        for run in self.runs.iter() {
80            for glyph in run.glyphs.iter() {
81                if glyph.position.x >= x {
82                    if glyph.position.x - x < x - prev_x {
83                        return glyph.index;
84                    } else {
85                        return prev_index;
86                    }
87                }
88                prev_index = glyph.index;
89                prev_x = glyph.position.x;
90            }
91        }
92
93        if self.len == 1 {
94            if x > self.width / 2. {
95                return 1;
96            } else {
97                return 0;
98            }
99        }
100
101        self.len
102    }
103
104    /// The x position of the character at the given index
105    pub fn x_for_index(&self, index: usize) -> Pixels {
106        for run in &self.runs {
107            for glyph in &run.glyphs {
108                if glyph.index >= index {
109                    return glyph.position.x;
110                }
111            }
112        }
113        self.width
114    }
115
116    /// The corresponding Font at the given index
117    pub fn font_id_for_index(&self, index: usize) -> Option<FontId> {
118        for run in &self.runs {
119            for glyph in &run.glyphs {
120                if glyph.index >= index {
121                    return Some(run.font_id);
122                }
123            }
124        }
125        None
126    }
127
128    fn compute_wrap_boundaries(
129        &self,
130        text: &str,
131        wrap_width: Pixels,
132        max_lines: Option<usize>,
133    ) -> SmallVec<[WrapBoundary; 1]> {
134        let mut boundaries = SmallVec::new();
135        let mut first_non_whitespace_ix = None;
136        let mut last_candidate_ix = None;
137        let mut last_candidate_x = px(0.);
138        let mut last_boundary = WrapBoundary {
139            run_ix: 0,
140            glyph_ix: 0,
141        };
142        let mut last_boundary_x = px(0.);
143        let mut prev_ch = '\0';
144        let mut glyphs = self
145            .runs
146            .iter()
147            .enumerate()
148            .flat_map(move |(run_ix, run)| {
149                run.glyphs.iter().enumerate().map(move |(glyph_ix, glyph)| {
150                    let character = text[glyph.index..].chars().next().unwrap();
151                    (
152                        WrapBoundary { run_ix, glyph_ix },
153                        character,
154                        glyph.position.x,
155                    )
156                })
157            })
158            .peekable();
159
160        while let Some((boundary, ch, x)) = glyphs.next() {
161            if ch == '\n' {
162                continue;
163            }
164
165            // Here is very similar to `LineWrapper::wrap_line` to determine text wrapping,
166            // but there are some differences, so we have to duplicate the code here.
167            if LineWrapper::is_word_char(ch) {
168                if prev_ch == ' ' && ch != ' ' && first_non_whitespace_ix.is_some() {
169                    last_candidate_ix = Some(boundary);
170                    last_candidate_x = x;
171                }
172            } else {
173                if ch != ' ' && first_non_whitespace_ix.is_some() {
174                    last_candidate_ix = Some(boundary);
175                    last_candidate_x = x;
176                }
177            }
178
179            if ch != ' ' && first_non_whitespace_ix.is_none() {
180                first_non_whitespace_ix = Some(boundary);
181            }
182
183            let next_x = glyphs.peek().map_or(self.width, |(_, _, x)| *x);
184            let width = next_x - last_boundary_x;
185
186            if width > wrap_width && boundary > last_boundary {
187                // When used line_clamp, we should limit the number of lines.
188                if let Some(max_lines) = max_lines
189                    && boundaries.len() >= max_lines.saturating_sub(1)
190                {
191                    break;
192                }
193
194                if let Some(last_candidate_ix) = last_candidate_ix.take() {
195                    last_boundary = last_candidate_ix;
196                    last_boundary_x = last_candidate_x;
197                } else {
198                    last_boundary = boundary;
199                    last_boundary_x = x;
200                }
201                boundaries.push(last_boundary);
202            }
203            prev_ch = ch;
204        }
205
206        boundaries
207    }
208}
209
210/// A line of text that has been wrapped to fit a given width
211#[derive(Default, Debug)]
212pub struct WrappedLineLayout {
213    /// The line layout, pre-wrapping.
214    pub unwrapped_layout: Arc<LineLayout>,
215
216    /// The boundaries at which the line was wrapped
217    pub wrap_boundaries: SmallVec<[WrapBoundary; 1]>,
218
219    /// The width of the line, if it was wrapped
220    pub wrap_width: Option<Pixels>,
221}
222
223/// A boundary at which a line was wrapped
224#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
225pub struct WrapBoundary {
226    /// The index in the run just before the line was wrapped
227    pub run_ix: usize,
228    /// The index of the glyph just before the line was wrapped
229    pub glyph_ix: usize,
230}
231
232impl WrappedLineLayout {
233    /// The length of the underlying text, in utf8 bytes.
234    #[allow(clippy::len_without_is_empty)]
235    pub fn len(&self) -> usize {
236        self.unwrapped_layout.len
237    }
238
239    /// The width of this line, in pixels, whether or not it was wrapped.
240    pub fn width(&self) -> Pixels {
241        self.wrap_width
242            .unwrap_or(Pixels::MAX)
243            .min(self.unwrapped_layout.width)
244    }
245
246    /// The size of the whole wrapped text, for the given line_height.
247    /// can span multiple lines if there are multiple wrap boundaries.
248    pub fn size(&self, line_height: Pixels) -> Size<Pixels> {
249        Size {
250            width: self.width(),
251            height: line_height * (self.wrap_boundaries.len() + 1),
252        }
253    }
254
255    /// The ascent of a line in this layout
256    pub fn ascent(&self) -> Pixels {
257        self.unwrapped_layout.ascent
258    }
259
260    /// The descent of a line in this layout
261    pub fn descent(&self) -> Pixels {
262        self.unwrapped_layout.descent
263    }
264
265    /// The wrap boundaries in this layout
266    pub fn wrap_boundaries(&self) -> &[WrapBoundary] {
267        &self.wrap_boundaries
268    }
269
270    /// The font size of this layout
271    pub fn font_size(&self) -> Pixels {
272        self.unwrapped_layout.font_size
273    }
274
275    /// The runs in this layout, sans wrapping
276    pub fn runs(&self) -> &[ShapedRun] {
277        &self.unwrapped_layout.runs
278    }
279
280    /// The index corresponding to a given position in this layout for the given line height.
281    ///
282    /// See also [`Self::closest_index_for_position`].
283    pub fn index_for_position(
284        &self,
285        position: Point<Pixels>,
286        line_height: Pixels,
287    ) -> Result<usize, usize> {
288        self._index_for_position(position, line_height, false)
289    }
290
291    /// The closest index to a given position in this layout for the given line height.
292    ///
293    /// Closest means the character boundary closest to the given position.
294    ///
295    /// See also [`LineLayout::closest_index_for_x`].
296    pub fn closest_index_for_position(
297        &self,
298        position: Point<Pixels>,
299        line_height: Pixels,
300    ) -> Result<usize, usize> {
301        self._index_for_position(position, line_height, true)
302    }
303
304    fn _index_for_position(
305        &self,
306        mut position: Point<Pixels>,
307        line_height: Pixels,
308        closest: bool,
309    ) -> Result<usize, usize> {
310        let wrapped_line_ix = (position.y / line_height) as usize;
311
312        let wrapped_line_start_index;
313        let wrapped_line_start_x;
314        if wrapped_line_ix > 0 {
315            let Some(line_start_boundary) = self.wrap_boundaries.get(wrapped_line_ix - 1) else {
316                return Err(0);
317            };
318            let run = &self.unwrapped_layout.runs[line_start_boundary.run_ix];
319            let glyph = &run.glyphs[line_start_boundary.glyph_ix];
320            wrapped_line_start_index = glyph.index;
321            wrapped_line_start_x = glyph.position.x;
322        } else {
323            wrapped_line_start_index = 0;
324            wrapped_line_start_x = Pixels::ZERO;
325        };
326
327        let wrapped_line_end_index;
328        let wrapped_line_end_x;
329        if wrapped_line_ix < self.wrap_boundaries.len() {
330            let next_wrap_boundary_ix = wrapped_line_ix;
331            let next_wrap_boundary = self.wrap_boundaries[next_wrap_boundary_ix];
332            let run = &self.unwrapped_layout.runs[next_wrap_boundary.run_ix];
333            let glyph = &run.glyphs[next_wrap_boundary.glyph_ix];
334            wrapped_line_end_index = glyph.index;
335            wrapped_line_end_x = glyph.position.x;
336        } else {
337            wrapped_line_end_index = self.unwrapped_layout.len;
338            wrapped_line_end_x = self.unwrapped_layout.width;
339        };
340
341        let mut position_in_unwrapped_line = position;
342        position_in_unwrapped_line.x += wrapped_line_start_x;
343        if position_in_unwrapped_line.x < wrapped_line_start_x {
344            Err(wrapped_line_start_index)
345        } else if position_in_unwrapped_line.x >= wrapped_line_end_x {
346            Err(wrapped_line_end_index)
347        } else {
348            if closest {
349                Ok(self
350                    .unwrapped_layout
351                    .closest_index_for_x(position_in_unwrapped_line.x))
352            } else {
353                // The shaper can place a trailing zero-width wrap boundary glyph slightly past
354                // the line's width, so the row can extend past where `index_for_x` has glyphs.
355                self.unwrapped_layout
356                    .index_for_x(position_in_unwrapped_line.x)
357                    .ok_or(wrapped_line_end_index)
358            }
359        }
360    }
361
362    /// Returns the pixel position for the given byte index.
363    pub fn position_for_index(&self, index: usize, line_height: Pixels) -> Option<Point<Pixels>> {
364        let mut line_start_ix = 0;
365        let mut line_end_indices = self
366            .wrap_boundaries
367            .iter()
368            .map(|wrap_boundary| {
369                let run = &self.unwrapped_layout.runs[wrap_boundary.run_ix];
370                let glyph = &run.glyphs[wrap_boundary.glyph_ix];
371                glyph.index
372            })
373            .chain([self.len()])
374            .enumerate();
375        for (ix, line_end_ix) in line_end_indices {
376            let line_y = ix as f32 * line_height;
377            if index < line_start_ix {
378                break;
379            } else if index > line_end_ix {
380                line_start_ix = line_end_ix;
381                continue;
382            } else {
383                let line_start_x = self.unwrapped_layout.x_for_index(line_start_ix);
384                let x = self.unwrapped_layout.x_for_index(index) - line_start_x;
385                return Some(point(x, line_y));
386            }
387        }
388
389        None
390    }
391}
392
393pub(crate) struct LineLayoutCache {
394    previous_frame: Mutex<FrameCache>,
395    current_frame: RwLock<FrameCache>,
396    platform_text_system: Arc<dyn PlatformTextSystem>,
397}
398
399#[derive(Default)]
400struct FrameCache {
401    lines: FxHashMap<Arc<CacheKey>, Arc<LineLayout>>,
402    wrapped_lines: FxHashMap<Arc<CacheKey>, Arc<WrappedLineLayout>>,
403    used_lines: Vec<Arc<CacheKey>>,
404    used_wrapped_lines: Vec<Arc<CacheKey>>,
405
406    // Content-addressable caches keyed by caller-provided text hash + layout params.
407    // These allow cache hits without materializing a contiguous `SharedString`.
408    //
409    // IMPORTANT: To support allocation-free lookups, we store these maps using a key type
410    // (`HashedCacheKeyRef`) that can be computed without building a contiguous `&str`/`SharedString`.
411    // On miss, we allocate once and store under an owned `HashedCacheKey`.
412    lines_by_hash: FxHashMap<Arc<HashedCacheKey>, Arc<LineLayout>>,
413    wrapped_lines_by_hash: FxHashMap<Arc<HashedCacheKey>, Arc<WrappedLineLayout>>,
414    used_lines_by_hash: Vec<Arc<HashedCacheKey>>,
415    used_wrapped_lines_by_hash: Vec<Arc<HashedCacheKey>>,
416}
417
418#[derive(Clone, Default)]
419pub(crate) struct LineLayoutIndex {
420    lines_index: usize,
421    wrapped_lines_index: usize,
422    lines_by_hash_index: usize,
423    wrapped_lines_by_hash_index: usize,
424}
425
426impl LineLayoutCache {
427    pub fn new(platform_text_system: Arc<dyn PlatformTextSystem>) -> Self {
428        Self {
429            previous_frame: Mutex::default(),
430            current_frame: RwLock::default(),
431            platform_text_system,
432        }
433    }
434
435    pub fn layout_index(&self) -> LineLayoutIndex {
436        let frame = self.current_frame.read();
437        LineLayoutIndex {
438            lines_index: frame.used_lines.len(),
439            wrapped_lines_index: frame.used_wrapped_lines.len(),
440            lines_by_hash_index: frame.used_lines_by_hash.len(),
441            wrapped_lines_by_hash_index: frame.used_wrapped_lines_by_hash.len(),
442        }
443    }
444
445    pub fn reuse_layouts(&self, range: Range<LineLayoutIndex>) {
446        let mut previous_frame = &mut *self.previous_frame.lock();
447        let mut current_frame = &mut *self.current_frame.write();
448
449        for key in &previous_frame.used_lines[range.start.lines_index..range.end.lines_index] {
450            if let Some((key, line)) = previous_frame.lines.remove_entry(key) {
451                current_frame.lines.insert(key, line);
452            }
453            current_frame.used_lines.push(key.clone());
454        }
455
456        for key in &previous_frame.used_wrapped_lines
457            [range.start.wrapped_lines_index..range.end.wrapped_lines_index]
458        {
459            if let Some((key, line)) = previous_frame.wrapped_lines.remove_entry(key) {
460                current_frame.wrapped_lines.insert(key, line);
461            }
462            current_frame.used_wrapped_lines.push(key.clone());
463        }
464
465        for key in &previous_frame.used_lines_by_hash
466            [range.start.lines_by_hash_index..range.end.lines_by_hash_index]
467        {
468            if let Some((key, line)) = previous_frame.lines_by_hash.remove_entry(key) {
469                current_frame.lines_by_hash.insert(key, line);
470            }
471            current_frame.used_lines_by_hash.push(key.clone());
472        }
473
474        for key in &previous_frame.used_wrapped_lines_by_hash
475            [range.start.wrapped_lines_by_hash_index..range.end.wrapped_lines_by_hash_index]
476        {
477            if let Some((key, line)) = previous_frame.wrapped_lines_by_hash.remove_entry(key) {
478                current_frame.wrapped_lines_by_hash.insert(key, line);
479            }
480            current_frame.used_wrapped_lines_by_hash.push(key.clone());
481        }
482    }
483
484    pub fn truncate_layouts(&self, index: LineLayoutIndex) {
485        let mut current_frame = &mut *self.current_frame.write();
486        current_frame.used_lines.truncate(index.lines_index);
487        current_frame
488            .used_wrapped_lines
489            .truncate(index.wrapped_lines_index);
490        current_frame
491            .used_lines_by_hash
492            .truncate(index.lines_by_hash_index);
493        current_frame
494            .used_wrapped_lines_by_hash
495            .truncate(index.wrapped_lines_by_hash_index);
496    }
497
498    pub fn finish_frame(&self) {
499        let mut prev_frame = self.previous_frame.lock();
500        let mut curr_frame = self.current_frame.write();
501        std::mem::swap(&mut *prev_frame, &mut *curr_frame);
502        curr_frame.lines.clear();
503        curr_frame.wrapped_lines.clear();
504        curr_frame.used_lines.clear();
505        curr_frame.used_wrapped_lines.clear();
506
507        curr_frame.lines_by_hash.clear();
508        curr_frame.wrapped_lines_by_hash.clear();
509        curr_frame.used_lines_by_hash.clear();
510        curr_frame.used_wrapped_lines_by_hash.clear();
511    }
512
513    pub fn layout_wrapped_line<Text>(
514        &self,
515        text: Text,
516        font_size: Pixels,
517        runs: &[FontRun],
518        wrap_width: Option<Pixels>,
519        max_lines: Option<usize>,
520    ) -> Arc<WrappedLineLayout>
521    where
522        Text: AsRef<str>,
523        SharedString: From<Text>,
524    {
525        let key = &CacheKeyRef {
526            text: text.as_ref(),
527            font_size,
528            runs,
529            wrap_width,
530            force_width: None,
531        } as &dyn AsCacheKeyRef;
532
533        let current_frame = self.current_frame.upgradable_read();
534        if let Some(layout) = current_frame.wrapped_lines.get(key) {
535            return layout.clone();
536        }
537
538        let previous_frame_entry = self.previous_frame.lock().wrapped_lines.remove_entry(key);
539        if let Some((key, layout)) = previous_frame_entry {
540            let mut current_frame = RwLockUpgradableReadGuard::upgrade(current_frame);
541            current_frame
542                .wrapped_lines
543                .insert(key.clone(), layout.clone());
544            current_frame.used_wrapped_lines.push(key);
545            layout
546        } else {
547            drop(current_frame);
548            let text = SharedString::from(text);
549            let unwrapped_layout = self.layout_line::<&SharedString>(&text, font_size, runs, None);
550            let wrap_boundaries = if let Some(wrap_width) = wrap_width {
551                unwrapped_layout.compute_wrap_boundaries(text.as_ref(), wrap_width, max_lines)
552            } else {
553                SmallVec::new()
554            };
555            let layout = Arc::new(WrappedLineLayout {
556                unwrapped_layout,
557                wrap_boundaries,
558                wrap_width,
559            });
560            let key = Arc::new(CacheKey {
561                text,
562                font_size,
563                runs: SmallVec::from(runs),
564                wrap_width,
565                force_width: None,
566            });
567
568            let mut current_frame = self.current_frame.write();
569            current_frame
570                .wrapped_lines
571                .insert(key.clone(), layout.clone());
572            current_frame.used_wrapped_lines.push(key);
573
574            layout
575        }
576    }
577
578    pub fn layout_line<Text>(
579        &self,
580        text: Text,
581        font_size: Pixels,
582        runs: &[FontRun],
583        force_width: Option<Pixels>,
584    ) -> Arc<LineLayout>
585    where
586        Text: AsRef<str>,
587        SharedString: From<Text>,
588    {
589        let key = &CacheKeyRef {
590            text: text.as_ref(),
591            font_size,
592            runs,
593            wrap_width: None,
594            force_width,
595        } as &dyn AsCacheKeyRef;
596
597        let current_frame = self.current_frame.upgradable_read();
598        if let Some(layout) = current_frame.lines.get(key) {
599            return layout.clone();
600        }
601
602        let mut current_frame = RwLockUpgradableReadGuard::upgrade(current_frame);
603        if let Some((key, layout)) = self.previous_frame.lock().lines.remove_entry(key) {
604            current_frame.lines.insert(key.clone(), layout.clone());
605            current_frame.used_lines.push(key);
606            layout
607        } else {
608            let text = SharedString::from(text);
609            let mut layout = self
610                .platform_text_system
611                .layout_line(&text, font_size, runs);
612
613            if let Some(force_width) = force_width {
614                apply_force_width_to_layout(&mut layout, force_width);
615            }
616
617            let key = Arc::new(CacheKey {
618                text,
619                font_size,
620                runs: SmallVec::from(runs),
621                wrap_width: None,
622                force_width,
623            });
624            let layout = Arc::new(layout);
625            current_frame.lines.insert(key.clone(), layout.clone());
626            current_frame.used_lines.push(key);
627            layout
628        }
629    }
630
631    /// Try to retrieve a previously-shaped line layout using a caller-provided content hash.
632    ///
633    /// This is a *non-allocating* cache probe: it does not materialize any text. If the layout
634    /// is not already cached in either the current frame or previous frame, returns `None`.
635    ///
636    /// Contract (caller enforced):
637    /// - Same `text_hash` implies identical text content (collision risk accepted by caller).
638    /// - `text_len` should be the UTF-8 byte length of the text (helps reduce accidental collisions).
639    pub fn try_layout_line_by_hash(
640        &self,
641        text_hash: u64,
642        text_len: usize,
643        font_size: Pixels,
644        runs: &[FontRun],
645        force_width: Option<Pixels>,
646    ) -> Option<Arc<LineLayout>> {
647        let key_ref = HashedCacheKeyRef {
648            text_hash,
649            text_len,
650            font_size,
651            runs,
652            wrap_width: None,
653            force_width,
654        };
655
656        let current_frame = self.current_frame.read();
657        if let Some((_, layout)) = current_frame.lines_by_hash.iter().find(|(key, _)| {
658            HashedCacheKeyRef {
659                text_hash: key.text_hash,
660                text_len: key.text_len,
661                font_size: key.font_size,
662                runs: key.runs.as_slice(),
663                wrap_width: key.wrap_width,
664                force_width: key.force_width,
665            } == key_ref
666        }) {
667            return Some(layout.clone());
668        }
669
670        let previous_frame = self.previous_frame.lock();
671        if let Some((_, layout)) = previous_frame.lines_by_hash.iter().find(|(key, _)| {
672            HashedCacheKeyRef {
673                text_hash: key.text_hash,
674                text_len: key.text_len,
675                font_size: key.font_size,
676                runs: key.runs.as_slice(),
677                wrap_width: key.wrap_width,
678                force_width: key.force_width,
679            } == key_ref
680        }) {
681            return Some(layout.clone());
682        }
683
684        None
685    }
686
687    /// Layout a line of text using a caller-provided content hash as the cache key.
688    ///
689    /// This enables cache hits without materializing a contiguous `SharedString` for `text`.
690    /// If the cache misses, `materialize_text` is invoked to produce the `SharedString` for shaping.
691    ///
692    /// Contract (caller enforced):
693    /// - Same `text_hash` implies identical text content (collision risk accepted by caller).
694    /// - `text_len` should be the UTF-8 byte length of the text (helps reduce accidental collisions).
695    pub fn layout_line_by_hash(
696        &self,
697        text_hash: u64,
698        text_len: usize,
699        font_size: Pixels,
700        runs: &[FontRun],
701        force_width: Option<Pixels>,
702        materialize_text: impl FnOnce() -> SharedString,
703    ) -> Arc<LineLayout> {
704        let key_ref = HashedCacheKeyRef {
705            text_hash,
706            text_len,
707            font_size,
708            runs,
709            wrap_width: None,
710            force_width,
711        };
712
713        // Fast path: already cached (no allocation).
714        let current_frame = self.current_frame.upgradable_read();
715        if let Some((_, layout)) = current_frame.lines_by_hash.iter().find(|(key, _)| {
716            HashedCacheKeyRef {
717                text_hash: key.text_hash,
718                text_len: key.text_len,
719                font_size: key.font_size,
720                runs: key.runs.as_slice(),
721                wrap_width: key.wrap_width,
722                force_width: key.force_width,
723            } == key_ref
724        }) {
725            return layout.clone();
726        }
727
728        let mut current_frame = RwLockUpgradableReadGuard::upgrade(current_frame);
729
730        // Try to reuse from previous frame without allocating; do a linear scan to find a matching key.
731        // (We avoid `drain()` here because it would eagerly move all entries.)
732        let mut previous_frame = self.previous_frame.lock();
733        if let Some(existing_key) = previous_frame
734            .used_lines_by_hash
735            .iter()
736            .find(|key| {
737                HashedCacheKeyRef {
738                    text_hash: key.text_hash,
739                    text_len: key.text_len,
740                    font_size: key.font_size,
741                    runs: key.runs.as_slice(),
742                    wrap_width: key.wrap_width,
743                    force_width: key.force_width,
744                } == key_ref
745            })
746            .cloned()
747        {
748            if let Some((key, layout)) = previous_frame.lines_by_hash.remove_entry(&existing_key) {
749                current_frame
750                    .lines_by_hash
751                    .insert(key.clone(), layout.clone());
752                current_frame.used_lines_by_hash.push(key);
753                return layout;
754            }
755        }
756
757        let text = materialize_text();
758        let mut layout = self
759            .platform_text_system
760            .layout_line(&text, font_size, runs);
761
762        if let Some(force_width) = force_width {
763            apply_force_width_to_layout(&mut layout, force_width);
764        }
765
766        let key = Arc::new(HashedCacheKey {
767            text_hash,
768            text_len,
769            font_size,
770            runs: SmallVec::from(runs),
771            wrap_width: None,
772            force_width,
773        });
774        let layout = Arc::new(layout);
775        current_frame
776            .lines_by_hash
777            .insert(key.clone(), layout.clone());
778        current_frame.used_lines_by_hash.push(key);
779        layout
780    }
781}
782
783// Combining marks (e.g. Thai vowel signs, Arabic diacritics) are shaped by
784// HarfBuzz at the same x position as their base character. The force-width
785// loop must not advance the cell counter for these zero-advance glyphs,
786// otherwise they get displaced into the next cell. We detect them by checking
787// whether shaped x has advanced by at least half a cell beyond the last base.
788fn apply_force_width_to_layout(layout: &mut LineLayout, force_width: Pixels) {
789    let mut glyph_pos: usize = 0;
790    // NEG_INFINITY ensures the first glyph is always classified as a base.
791    let mut last_base_shaped_x = px(f32::NEG_INFINITY);
792    let mut last_base_actual_x = px(0.);
793
794    for run in layout.runs.iter_mut() {
795        for glyph in run.glyphs.iter_mut() {
796            let shaped_x = glyph.position.x;
797
798            if shaped_x > last_base_shaped_x + force_width * 0.5 {
799                let forced_x = glyph_pos * force_width;
800                if (shaped_x - forced_x).abs() > px(1.) {
801                    glyph.position.x = forced_x;
802                }
803                last_base_shaped_x = shaped_x;
804                last_base_actual_x = glyph.position.x;
805                glyph_pos += 1;
806            } else {
807                glyph.position.x = last_base_actual_x + (shaped_x - last_base_shaped_x);
808            }
809        }
810    }
811}
812
813/// A run of text with a single font.
814#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
815#[expect(missing_docs)]
816pub struct FontRun {
817    pub len: usize,
818    pub font_id: FontId,
819}
820
821trait AsCacheKeyRef {
822    fn as_cache_key_ref(&self) -> CacheKeyRef<'_>;
823}
824
825#[derive(Clone, Debug, Eq)]
826struct CacheKey {
827    text: SharedString,
828    font_size: Pixels,
829    runs: SmallVec<[FontRun; 1]>,
830    wrap_width: Option<Pixels>,
831    force_width: Option<Pixels>,
832}
833
834#[derive(Copy, Clone, PartialEq, Eq, Hash)]
835struct CacheKeyRef<'a> {
836    text: &'a str,
837    font_size: Pixels,
838    runs: &'a [FontRun],
839    wrap_width: Option<Pixels>,
840    force_width: Option<Pixels>,
841}
842
843#[derive(Clone, Debug)]
844struct HashedCacheKey {
845    text_hash: u64,
846    text_len: usize,
847    font_size: Pixels,
848    runs: SmallVec<[FontRun; 1]>,
849    wrap_width: Option<Pixels>,
850    force_width: Option<Pixels>,
851}
852
853#[derive(Copy, Clone)]
854struct HashedCacheKeyRef<'a> {
855    text_hash: u64,
856    text_len: usize,
857    font_size: Pixels,
858    runs: &'a [FontRun],
859    wrap_width: Option<Pixels>,
860    force_width: Option<Pixels>,
861}
862
863impl PartialEq for dyn AsCacheKeyRef + '_ {
864    fn eq(&self, other: &dyn AsCacheKeyRef) -> bool {
865        self.as_cache_key_ref() == other.as_cache_key_ref()
866    }
867}
868
869impl PartialEq for HashedCacheKey {
870    fn eq(&self, other: &Self) -> bool {
871        self.text_hash == other.text_hash
872            && self.text_len == other.text_len
873            && self.font_size == other.font_size
874            && self.runs.as_slice() == other.runs.as_slice()
875            && self.wrap_width == other.wrap_width
876            && self.force_width == other.force_width
877    }
878}
879
880impl Eq for HashedCacheKey {}
881
882impl Hash for HashedCacheKey {
883    fn hash<H: Hasher>(&self, state: &mut H) {
884        self.text_hash.hash(state);
885        self.text_len.hash(state);
886        self.font_size.hash(state);
887        self.runs.as_slice().hash(state);
888        self.wrap_width.hash(state);
889        self.force_width.hash(state);
890    }
891}
892
893impl PartialEq for HashedCacheKeyRef<'_> {
894    fn eq(&self, other: &Self) -> bool {
895        self.text_hash == other.text_hash
896            && self.text_len == other.text_len
897            && self.font_size == other.font_size
898            && self.runs == other.runs
899            && self.wrap_width == other.wrap_width
900            && self.force_width == other.force_width
901    }
902}
903
904impl Eq for HashedCacheKeyRef<'_> {}
905
906impl Hash for HashedCacheKeyRef<'_> {
907    fn hash<H: Hasher>(&self, state: &mut H) {
908        self.text_hash.hash(state);
909        self.text_len.hash(state);
910        self.font_size.hash(state);
911        self.runs.hash(state);
912        self.wrap_width.hash(state);
913        self.force_width.hash(state);
914    }
915}
916
917impl Eq for dyn AsCacheKeyRef + '_ {}
918
919impl Hash for dyn AsCacheKeyRef + '_ {
920    fn hash<H: Hasher>(&self, state: &mut H) {
921        self.as_cache_key_ref().hash(state)
922    }
923}
924
925impl AsCacheKeyRef for CacheKey {
926    fn as_cache_key_ref(&self) -> CacheKeyRef<'_> {
927        CacheKeyRef {
928            text: &self.text,
929            font_size: self.font_size,
930            runs: self.runs.as_slice(),
931            wrap_width: self.wrap_width,
932            force_width: self.force_width,
933        }
934    }
935}
936
937impl PartialEq for CacheKey {
938    fn eq(&self, other: &Self) -> bool {
939        self.as_cache_key_ref().eq(&other.as_cache_key_ref())
940    }
941}
942
943impl Hash for CacheKey {
944    fn hash<H: Hasher>(&self, state: &mut H) {
945        self.as_cache_key_ref().hash(state);
946    }
947}
948
949impl<'a> Borrow<dyn AsCacheKeyRef + 'a> for Arc<CacheKey> {
950    fn borrow(&self) -> &(dyn AsCacheKeyRef + 'a) {
951        self.as_ref() as &dyn AsCacheKeyRef
952    }
953}
954
955impl AsCacheKeyRef for CacheKeyRef<'_> {
956    fn as_cache_key_ref(&self) -> CacheKeyRef<'_> {
957        *self
958    }
959}
960
961#[cfg(test)]
962mod tests {
963    use super::*;
964    use crate::GlyphId;
965
966    fn glyph_at(x: f32, index: usize) -> ShapedGlyph {
967        ShapedGlyph {
968            id: GlyphId(0),
969            position: point(px(x), px(0.)),
970            index,
971            is_emoji: false,
972        }
973    }
974
975    fn make_layout(glyphs: Vec<ShapedGlyph>) -> LineLayout {
976        LineLayout {
977            font_size: px(16.),
978            width: px(100.),
979            ascent: px(12.),
980            descent: px(4.),
981            runs: vec![ShapedRun {
982                font_id: FontId(0),
983                glyphs,
984            }],
985            len: 0,
986        }
987    }
988
989    fn glyph_x_positions(layout: &LineLayout) -> Vec<f32> {
990        layout.runs[0]
991            .glyphs
992            .iter()
993            .map(|g| f32::from(g.position.x))
994            .collect()
995    }
996
997    #[test]
998    fn test_hit_testing_past_width_before_wrap_boundary() {
999        // A trailing zero-width glyph can be positioned beyond the measured width.
1000        let mut layout = make_layout(vec![glyph_at(0., 0), glyph_at(101., 1)]);
1001        layout.len = 2;
1002        let wrapped = WrappedLineLayout {
1003            unwrapped_layout: Arc::new(layout),
1004            wrap_boundaries: smallvec::smallvec![WrapBoundary {
1005                run_ix: 0,
1006                glyph_ix: 1
1007            }],
1008            wrap_width: Some(px(100.)),
1009        };
1010        assert_eq!(
1011            wrapped.index_for_position(point(px(50.), px(0.)), px(16.)),
1012            Ok(0)
1013        );
1014        assert_eq!(
1015            wrapped.index_for_position(point(px(100.5), px(0.)), px(16.)),
1016            Err(1)
1017        );
1018        assert_eq!(
1019            wrapped.index_for_position(point(px(101.), px(0.)), px(16.)),
1020            Err(1)
1021        );
1022    }
1023
1024    #[test]
1025    fn test_force_width_latin_unchanged() {
1026        let cell_width = px(8.);
1027        let mut layout = make_layout(vec![glyph_at(0., 0), glyph_at(8., 1), glyph_at(16., 2)]);
1028
1029        apply_force_width_to_layout(&mut layout, cell_width);
1030
1031        let positions = glyph_x_positions(&layout);
1032        assert_eq!(positions, vec![0., 8., 16.]);
1033    }
1034
1035    #[test]
1036    fn test_force_width_combining_marks_not_advanced() {
1037        let cell_width = px(8.);
1038        // Simulates Thai "กี" — base consonant at x=0, combining vowel also at x=0
1039        let mut layout = make_layout(vec![
1040            glyph_at(0., 0), // ก (base)
1041            glyph_at(0., 3), // ี (combining mark, same x)
1042        ]);
1043
1044        apply_force_width_to_layout(&mut layout, cell_width);
1045
1046        let positions = glyph_x_positions(&layout);
1047        assert_eq!(positions, vec![0., 0.]);
1048    }
1049
1050    #[test]
1051    fn test_force_width_base_after_combining_mark() {
1052        let cell_width = px(8.);
1053        let mut layout = make_layout(vec![glyph_at(0., 0), glyph_at(0., 3), glyph_at(8., 6)]);
1054
1055        apply_force_width_to_layout(&mut layout, cell_width);
1056
1057        let positions = glyph_x_positions(&layout);
1058        assert_eq!(positions, vec![0., 0., 8.]);
1059    }
1060
1061    #[test]
1062    fn test_force_width_multiple_combining_marks() {
1063        let cell_width = px(8.);
1064        // Simulates "ก้" — base + vowel + tone mark (two combining marks stacked)
1065        let mut layout = make_layout(vec![
1066            glyph_at(0., 0), // ก (base)
1067            glyph_at(0., 3), // vowel (combining)
1068            glyph_at(0., 6), // tone mark (combining)
1069            glyph_at(8., 9), // next base
1070        ]);
1071
1072        apply_force_width_to_layout(&mut layout, cell_width);
1073
1074        let positions = glyph_x_positions(&layout);
1075        assert_eq!(positions, vec![0., 0., 0., 8.]);
1076    }
1077
1078    #[test]
1079    fn test_force_width_corrects_drifted_base_positions() {
1080        let cell_width = px(8.);
1081        // Font metrics don't perfectly match cell grid — glyphs drift >1px from cell boundary
1082        let mut layout = make_layout(vec![
1083            glyph_at(0.5, 0),  // within 1px tolerance, kept as-is
1084            glyph_at(10.2, 1), // >1px off from 8.0, corrected
1085            glyph_at(19.8, 2), // >1px off from 16.0, corrected
1086        ]);
1087
1088        apply_force_width_to_layout(&mut layout, cell_width);
1089
1090        let positions = glyph_x_positions(&layout);
1091        assert_eq!(positions, vec![0.5, 8., 16.]);
1092    }
1093
1094    #[test]
1095    fn test_force_width_combining_mark_after_within_tolerance_base() {
1096        let cell_width = px(8.);
1097        // Base glyph is within 1px of grid so it keeps its shaped position.
1098        // The combining mark must align to the base's actual position, not the grid slot.
1099        let mut layout = make_layout(vec![glyph_at(0.5, 0), glyph_at(0.5, 3)]);
1100
1101        apply_force_width_to_layout(&mut layout, cell_width);
1102
1103        let positions = glyph_x_positions(&layout);
1104        assert_eq!(positions, vec![0.5, 0.5]);
1105    }
1106}