cosmic_text/
shape.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2
3#![allow(clippy::too_many_arguments)]
4
5use crate::fallback::FontFallbackIter;
6use crate::{
7    math, Align, AttrsList, CacheKeyFlags, Color, Font, FontSystem, LayoutGlyph, LayoutLine,
8    Metrics, Wrap,
9};
10#[cfg(not(feature = "std"))]
11use alloc::vec::Vec;
12
13use core::cmp::{max, min};
14use core::fmt;
15use core::mem;
16use core::ops::Range;
17
18#[cfg(not(feature = "std"))]
19use core_maths::CoreFloat;
20use unicode_script::{Script, UnicodeScript};
21use unicode_segmentation::UnicodeSegmentation;
22
23/// The shaping strategy of some text.
24#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
25pub enum Shaping {
26    /// Basic shaping with no font fallback.
27    ///
28    /// This shaping strategy is very cheap, but it will not display complex
29    /// scripts properly nor try to find missing glyphs in your system fonts.
30    ///
31    /// You should use this strategy when you have complete control of the text
32    /// and the font you are displaying in your application.
33    #[cfg(feature = "swash")]
34    Basic,
35    /// Advanced text shaping and font fallback.
36    ///
37    /// You will need to enable this strategy if the text contains a complex
38    /// script, the font used needs it, and/or multiple fonts in your system
39    /// may be needed to display all of the glyphs.
40    Advanced,
41}
42
43impl Shaping {
44    fn run(
45        self,
46        glyphs: &mut Vec<ShapeGlyph>,
47        font_system: &mut FontSystem,
48        line: &str,
49        attrs_list: &AttrsList,
50        start_run: usize,
51        end_run: usize,
52        span_rtl: bool,
53    ) {
54        match self {
55            #[cfg(feature = "swash")]
56            Self::Basic => shape_skip(font_system, glyphs, line, attrs_list, start_run, end_run),
57            #[cfg(not(feature = "shape-run-cache"))]
58            Self::Advanced => shape_run(
59                glyphs,
60                font_system,
61                line,
62                attrs_list,
63                start_run,
64                end_run,
65                span_rtl,
66            ),
67            #[cfg(feature = "shape-run-cache")]
68            Self::Advanced => shape_run_cached(
69                glyphs,
70                font_system,
71                line,
72                attrs_list,
73                start_run,
74                end_run,
75                span_rtl,
76            ),
77        }
78    }
79}
80
81/// A set of buffers containing allocations for shaped text.
82#[derive(Default)]
83pub struct ShapeBuffer {
84    /// Buffer for holding unicode text.
85    rustybuzz_buffer: Option<rustybuzz::UnicodeBuffer>,
86
87    /// Temporary buffers for scripts.
88    scripts: Vec<Script>,
89
90    /// Buffer for shape spans.
91    spans: Vec<ShapeSpan>,
92
93    /// Buffer for shape words.
94    words: Vec<ShapeWord>,
95
96    /// Buffers for visual lines.
97    visual_lines: Vec<VisualLine>,
98    cached_visual_lines: Vec<VisualLine>,
99
100    /// Buffer for sets of layout glyphs.
101    glyph_sets: Vec<Vec<LayoutGlyph>>,
102}
103
104impl fmt::Debug for ShapeBuffer {
105    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
106        f.pad("ShapeBuffer { .. }")
107    }
108}
109
110fn shape_fallback(
111    scratch: &mut ShapeBuffer,
112    glyphs: &mut Vec<ShapeGlyph>,
113    font: &Font,
114    line: &str,
115    attrs_list: &AttrsList,
116    start_run: usize,
117    end_run: usize,
118    span_rtl: bool,
119) -> Vec<usize> {
120    let run = &line[start_run..end_run];
121
122    let font_scale = font.rustybuzz().units_per_em() as f32;
123    let ascent = f32::from(font.rustybuzz().ascender()) / font_scale;
124    let descent = -f32::from(font.rustybuzz().descender()) / font_scale;
125
126    let mut buffer = scratch.rustybuzz_buffer.take().unwrap_or_default();
127    buffer.set_direction(if span_rtl {
128        rustybuzz::Direction::RightToLeft
129    } else {
130        rustybuzz::Direction::LeftToRight
131    });
132    if run.contains('\t') {
133        // Push string to buffer, replacing tabs with spaces
134        //TODO: Find a way to do this with minimal allocating, calling
135        // UnicodeBuffer::push_str multiple times causes issues and
136        // UnicodeBuffer::add resizes the buffer with every character
137        buffer.push_str(&run.replace('\t', " "));
138    } else {
139        buffer.push_str(run);
140    }
141    buffer.guess_segment_properties();
142
143    let rtl = matches!(buffer.direction(), rustybuzz::Direction::RightToLeft);
144    assert_eq!(rtl, span_rtl);
145
146    let attrs = attrs_list.get_span(start_run);
147    let mut rb_font_features = Vec::new();
148
149    // Convert attrs::Feature to rustybuzz::Feature
150    for feature in attrs.font_features.features {
151        rb_font_features.push(rustybuzz::Feature::new(
152            rustybuzz::ttf_parser::Tag::from_bytes(feature.tag.as_bytes()),
153            feature.value,
154            0..usize::MAX,
155        ));
156    }
157
158    let shape_plan = rustybuzz::ShapePlan::new(
159        font.rustybuzz(),
160        buffer.direction(),
161        Some(buffer.script()),
162        buffer.language().as_ref(),
163        &rb_font_features,
164    );
165    let glyph_buffer = rustybuzz::shape_with_plan(font.rustybuzz(), &shape_plan, buffer);
166    let glyph_infos = glyph_buffer.glyph_infos();
167    let glyph_positions = glyph_buffer.glyph_positions();
168
169    let mut missing = Vec::new();
170    glyphs.reserve(glyph_infos.len());
171    let glyph_start = glyphs.len();
172    for (info, pos) in glyph_infos.iter().zip(glyph_positions.iter()) {
173        let start_glyph = start_run + info.cluster as usize;
174
175        if info.glyph_id == 0 {
176            missing.push(start_glyph);
177        }
178
179        let attrs = attrs_list.get_span(start_glyph);
180        let x_advance = pos.x_advance as f32 / font_scale
181            + attrs.letter_spacing_opt.map_or(0.0, |spacing| spacing.0);
182        let y_advance = pos.y_advance as f32 / font_scale;
183        let x_offset = pos.x_offset as f32 / font_scale;
184        let y_offset = pos.y_offset as f32 / font_scale;
185
186        glyphs.push(ShapeGlyph {
187            start: start_glyph,
188            end: end_run, // Set later
189            x_advance,
190            y_advance,
191            x_offset,
192            y_offset,
193            ascent,
194            descent,
195            font_monospace_em_width: font.monospace_em_width(),
196            font_id: font.id(),
197            font_weight: attrs.weight,
198            glyph_id: info.glyph_id.try_into().expect("failed to cast glyph ID"),
199            //TODO: color should not be related to shaping
200            color_opt: attrs.color_opt,
201            metadata: attrs.metadata,
202            cache_key_flags: attrs.cache_key_flags,
203            metrics_opt: attrs.metrics_opt.map(Into::into),
204        });
205    }
206
207    // Adjust end of glyphs
208    if rtl {
209        for i in glyph_start + 1..glyphs.len() {
210            let next_start = glyphs[i - 1].start;
211            let next_end = glyphs[i - 1].end;
212            let prev = &mut glyphs[i];
213            if prev.start == next_start {
214                prev.end = next_end;
215            } else {
216                prev.end = next_start;
217            }
218        }
219    } else {
220        for i in (glyph_start + 1..glyphs.len()).rev() {
221            let next_start = glyphs[i].start;
222            let next_end = glyphs[i].end;
223            let prev = &mut glyphs[i - 1];
224            if prev.start == next_start {
225                prev.end = next_end;
226            } else {
227                prev.end = next_start;
228            }
229        }
230    }
231
232    // Restore the buffer to save an allocation.
233    scratch.rustybuzz_buffer = Some(glyph_buffer.clear());
234
235    missing
236}
237
238fn shape_run(
239    glyphs: &mut Vec<ShapeGlyph>,
240    font_system: &mut FontSystem,
241    line: &str,
242    attrs_list: &AttrsList,
243    start_run: usize,
244    end_run: usize,
245    span_rtl: bool,
246) {
247    // Re-use the previous script buffer if possible.
248    let mut scripts = {
249        let mut scripts = mem::take(&mut font_system.shape_buffer.scripts);
250        scripts.clear();
251        scripts
252    };
253    for c in line[start_run..end_run].chars() {
254        match c.script() {
255            Script::Common | Script::Inherited | Script::Latin | Script::Unknown => (),
256            script => {
257                if !scripts.contains(&script) {
258                    scripts.push(script);
259                }
260            }
261        }
262    }
263
264    log::trace!("      Run {:?}: '{}'", &scripts, &line[start_run..end_run],);
265
266    let attrs = attrs_list.get_span(start_run);
267
268    let fonts = font_system.get_font_matches(&attrs);
269
270    let default_families = [&attrs.family];
271    let mut font_iter = FontFallbackIter::new(
272        font_system,
273        &fonts,
274        &default_families,
275        &scripts,
276        &line[start_run..end_run],
277        attrs.weight,
278    );
279
280    let font = font_iter.next().expect("no default font found");
281
282    let glyph_start = glyphs.len();
283    let mut missing = {
284        let scratch = font_iter.shape_caches();
285        shape_fallback(
286            scratch, glyphs, &font, line, attrs_list, start_run, end_run, span_rtl,
287        )
288    };
289
290    //TODO: improve performance!
291    while !missing.is_empty() {
292        let Some(font) = font_iter.next() else {
293            break;
294        };
295
296        log::trace!(
297            "Evaluating fallback with font '{}'",
298            font_iter.face_name(font.id())
299        );
300        let mut fb_glyphs = Vec::new();
301        let scratch = font_iter.shape_caches();
302        let fb_missing = shape_fallback(
303            scratch,
304            &mut fb_glyphs,
305            &font,
306            line,
307            attrs_list,
308            start_run,
309            end_run,
310            span_rtl,
311        );
312
313        // Insert all matching glyphs
314        let mut fb_i = 0;
315        while fb_i < fb_glyphs.len() {
316            let start = fb_glyphs[fb_i].start;
317            let end = fb_glyphs[fb_i].end;
318
319            // Skip clusters that are not missing, or where the fallback font is missing
320            if !missing.contains(&start) || fb_missing.contains(&start) {
321                fb_i += 1;
322                continue;
323            }
324
325            let mut missing_i = 0;
326            while missing_i < missing.len() {
327                if missing[missing_i] >= start && missing[missing_i] < end {
328                    // println!("No longer missing {}", missing[missing_i]);
329                    missing.remove(missing_i);
330                } else {
331                    missing_i += 1;
332                }
333            }
334
335            // Find prior glyphs
336            let mut i = glyph_start;
337            while i < glyphs.len() {
338                if glyphs[i].start >= start && glyphs[i].end <= end {
339                    break;
340                }
341                i += 1;
342            }
343
344            // Remove prior glyphs
345            while i < glyphs.len() {
346                if glyphs[i].start >= start && glyphs[i].end <= end {
347                    let _glyph = glyphs.remove(i);
348                    // log::trace!("Removed {},{} from {}", _glyph.start, _glyph.end, i);
349                } else {
350                    break;
351                }
352            }
353
354            while fb_i < fb_glyphs.len() {
355                if fb_glyphs[fb_i].start >= start && fb_glyphs[fb_i].end <= end {
356                    let fb_glyph = fb_glyphs.remove(fb_i);
357                    // log::trace!("Insert {},{} from font {} at {}", fb_glyph.start, fb_glyph.end, font_i, i);
358                    glyphs.insert(i, fb_glyph);
359                    i += 1;
360                } else {
361                    break;
362                }
363            }
364        }
365    }
366
367    // Debug missing font fallbacks
368    font_iter.check_missing(&line[start_run..end_run]);
369
370    /*
371    for glyph in glyphs.iter() {
372        log::trace!("'{}': {}, {}, {}, {}", &line[glyph.start..glyph.end], glyph.x_advance, glyph.y_advance, glyph.x_offset, glyph.y_offset);
373    }
374    */
375
376    // Restore the scripts buffer.
377    font_system.shape_buffer.scripts = scripts;
378}
379
380#[cfg(feature = "shape-run-cache")]
381fn shape_run_cached(
382    glyphs: &mut Vec<ShapeGlyph>,
383    font_system: &mut FontSystem,
384    line: &str,
385    attrs_list: &AttrsList,
386    start_run: usize,
387    end_run: usize,
388    span_rtl: bool,
389) {
390    use crate::{AttrsOwned, ShapeRunKey};
391
392    let run_range = start_run..end_run;
393    let mut key = ShapeRunKey {
394        text: line[run_range.clone()].to_string(),
395        default_attrs: AttrsOwned::new(&attrs_list.defaults()),
396        attrs_spans: Vec::new(),
397    };
398    for (attrs_range, attrs) in attrs_list.spans.overlapping(&run_range) {
399        if attrs == &key.default_attrs {
400            // Skip if attrs matches default attrs
401            continue;
402        }
403        let start = max(attrs_range.start, start_run).saturating_sub(start_run);
404        let end = min(attrs_range.end, end_run).saturating_sub(start_run);
405        if end > start {
406            let range = start..end;
407            key.attrs_spans.push((range, attrs.clone()));
408        }
409    }
410    if let Some(cache_glyphs) = font_system.shape_run_cache.get(&key) {
411        for mut glyph in cache_glyphs.iter().cloned() {
412            // Adjust glyph start and end to match run position
413            glyph.start += start_run;
414            glyph.end += start_run;
415            glyphs.push(glyph);
416        }
417        return;
418    }
419
420    // Fill in cache if not already set
421    let mut cache_glyphs = Vec::new();
422    shape_run(
423        &mut cache_glyphs,
424        font_system,
425        line,
426        attrs_list,
427        start_run,
428        end_run,
429        span_rtl,
430    );
431    glyphs.extend_from_slice(&cache_glyphs);
432    for glyph in cache_glyphs.iter_mut() {
433        // Adjust glyph start and end to remove run position
434        glyph.start -= start_run;
435        glyph.end -= start_run;
436    }
437    font_system.shape_run_cache.insert(key, cache_glyphs);
438}
439
440#[cfg(feature = "swash")]
441fn shape_skip(
442    font_system: &mut FontSystem,
443    glyphs: &mut Vec<ShapeGlyph>,
444    line: &str,
445    attrs_list: &AttrsList,
446    start_run: usize,
447    end_run: usize,
448) {
449    let attrs = attrs_list.get_span(start_run);
450    let fonts = font_system.get_font_matches(&attrs);
451
452    let default_families = [&attrs.family];
453    let mut font_iter = FontFallbackIter::new(
454        font_system,
455        &fonts,
456        &default_families,
457        &[],
458        "",
459        attrs.weight,
460    );
461
462    let font = font_iter.next().expect("no default font found");
463    let font_id = font.id();
464    let font_monospace_em_width = font.monospace_em_width();
465    let font = font.as_swash();
466
467    let charmap = font.charmap();
468    let metrics = font.metrics(&[]);
469    let glyph_metrics = font.glyph_metrics(&[]).scale(1.0);
470
471    let ascent = metrics.ascent / f32::from(metrics.units_per_em);
472    let descent = metrics.descent / f32::from(metrics.units_per_em);
473
474    glyphs.extend(
475        line[start_run..end_run]
476            .char_indices()
477            .map(|(chr_idx, codepoint)| {
478                let glyph_id = charmap.map(codepoint);
479                let x_advance = glyph_metrics.advance_width(glyph_id)
480                    + attrs.letter_spacing_opt.map_or(0.0, |spacing| spacing.0);
481                let attrs = attrs_list.get_span(start_run + chr_idx);
482
483                ShapeGlyph {
484                    start: chr_idx + start_run,
485                    end: chr_idx + start_run + codepoint.len_utf8(),
486                    x_advance,
487                    y_advance: 0.0,
488                    x_offset: 0.0,
489                    y_offset: 0.0,
490                    ascent,
491                    descent,
492                    font_monospace_em_width,
493                    font_id,
494                    font_weight: attrs.weight,
495                    glyph_id,
496                    color_opt: attrs.color_opt,
497                    metadata: attrs.metadata,
498                    cache_key_flags: attrs.cache_key_flags,
499                    metrics_opt: attrs.metrics_opt.map(Into::into),
500                }
501            }),
502    );
503}
504
505/// A shaped glyph
506#[derive(Clone, Debug)]
507pub struct ShapeGlyph {
508    pub start: usize,
509    pub end: usize,
510    pub x_advance: f32,
511    pub y_advance: f32,
512    pub x_offset: f32,
513    pub y_offset: f32,
514    pub ascent: f32,
515    pub descent: f32,
516    pub font_monospace_em_width: Option<f32>,
517    pub font_id: fontdb::ID,
518    pub font_weight: fontdb::Weight,
519    pub glyph_id: u16,
520    pub color_opt: Option<Color>,
521    pub metadata: usize,
522    pub cache_key_flags: CacheKeyFlags,
523    pub metrics_opt: Option<Metrics>,
524}
525
526impl ShapeGlyph {
527    const fn layout(
528        &self,
529        font_size: f32,
530        line_height_opt: Option<f32>,
531        x: f32,
532        y: f32,
533        w: f32,
534        level: unicode_bidi::Level,
535    ) -> LayoutGlyph {
536        LayoutGlyph {
537            start: self.start,
538            end: self.end,
539            font_size,
540            line_height_opt,
541            font_id: self.font_id,
542            font_weight: self.font_weight,
543            glyph_id: self.glyph_id,
544            x,
545            y,
546            w,
547            level,
548            x_offset: self.x_offset,
549            y_offset: self.y_offset,
550            color_opt: self.color_opt,
551            metadata: self.metadata,
552            cache_key_flags: self.cache_key_flags,
553        }
554    }
555
556    /// Get the width of the [`ShapeGlyph`] in pixels, either using the provided font size
557    /// or the [`ShapeGlyph::metrics_opt`] override.
558    pub fn width(&self, font_size: f32) -> f32 {
559        self.metrics_opt.map_or(font_size, |x| x.font_size) * self.x_advance
560    }
561}
562
563/// A shaped word (for word wrapping)
564#[derive(Clone, Debug)]
565pub struct ShapeWord {
566    pub blank: bool,
567    pub glyphs: Vec<ShapeGlyph>,
568}
569
570impl ShapeWord {
571    /// Creates an empty word.
572    ///
573    /// The returned word is in an invalid state until [`Self::build_in_buffer`] is called.
574    pub(crate) fn empty() -> Self {
575        Self {
576            blank: true,
577            glyphs: Vec::default(),
578        }
579    }
580
581    /// Shape a word into a set of glyphs.
582    #[allow(clippy::too_many_arguments)]
583    pub fn new(
584        font_system: &mut FontSystem,
585        line: &str,
586        attrs_list: &AttrsList,
587        word_range: Range<usize>,
588        level: unicode_bidi::Level,
589        blank: bool,
590        shaping: Shaping,
591    ) -> Self {
592        let mut empty = Self::empty();
593        empty.build(
594            font_system,
595            line,
596            attrs_list,
597            word_range,
598            level,
599            blank,
600            shaping,
601        );
602        empty
603    }
604
605    /// See [`Self::new`].
606    ///
607    /// Reuses as much of the pre-existing internal allocations as possible.
608    #[allow(clippy::too_many_arguments)]
609    pub fn build(
610        &mut self,
611        font_system: &mut FontSystem,
612        line: &str,
613        attrs_list: &AttrsList,
614        word_range: Range<usize>,
615        level: unicode_bidi::Level,
616        blank: bool,
617        shaping: Shaping,
618    ) {
619        let word = &line[word_range.clone()];
620
621        log::trace!(
622            "      Word{}: '{}'",
623            if blank { " BLANK" } else { "" },
624            word
625        );
626
627        let mut glyphs = mem::take(&mut self.glyphs);
628        glyphs.clear();
629
630        let span_rtl = level.is_rtl();
631
632        // Fast path optimization: For simple ASCII words, skip expensive grapheme iteration
633        let is_simple_ascii =
634            word.is_ascii() && !word.chars().any(|c| c.is_ascii_control() && c != '\t');
635
636        if is_simple_ascii && !word.is_empty() {
637            let _attrs = attrs_list.defaults();
638            shaping.run(
639                &mut glyphs,
640                font_system,
641                line,
642                attrs_list,
643                word_range.start,
644                word_range.end,
645                span_rtl,
646            );
647        } else {
648            // Complex text path: Full grapheme iteration and attribute processing
649            let mut start_run = word_range.start;
650            let mut attrs = attrs_list.defaults();
651            for (egc_i, _egc) in word.grapheme_indices(true) {
652                let start_egc = word_range.start + egc_i;
653                let attrs_egc = attrs_list.get_span(start_egc);
654                if !attrs.compatible(&attrs_egc) {
655                    shaping.run(
656                        &mut glyphs,
657                        font_system,
658                        line,
659                        attrs_list,
660                        start_run,
661                        start_egc,
662                        span_rtl,
663                    );
664
665                    start_run = start_egc;
666                    attrs = attrs_egc;
667                }
668            }
669            if start_run < word_range.end {
670                shaping.run(
671                    &mut glyphs,
672                    font_system,
673                    line,
674                    attrs_list,
675                    start_run,
676                    word_range.end,
677                    span_rtl,
678                );
679            }
680        }
681
682        self.blank = blank;
683        self.glyphs = glyphs;
684    }
685
686    /// Get the width of the [`ShapeWord`] in pixels, using the [`ShapeGlyph::width`] function.
687    pub fn width(&self, font_size: f32) -> f32 {
688        let mut width = 0.0;
689        for glyph in &self.glyphs {
690            width += glyph.width(font_size);
691        }
692        width
693    }
694}
695
696/// A shaped span (for bidirectional processing)
697#[derive(Clone, Debug)]
698pub struct ShapeSpan {
699    pub level: unicode_bidi::Level,
700    pub words: Vec<ShapeWord>,
701}
702
703impl ShapeSpan {
704    /// Creates an empty span.
705    ///
706    /// The returned span is in an invalid state until [`Self::build_in_buffer`] is called.
707    pub(crate) fn empty() -> Self {
708        Self {
709            level: unicode_bidi::Level::ltr(),
710            words: Vec::default(),
711        }
712    }
713
714    /// Shape a span into a set of words.
715    pub fn new(
716        font_system: &mut FontSystem,
717        line: &str,
718        attrs_list: &AttrsList,
719        span_range: Range<usize>,
720        line_rtl: bool,
721        level: unicode_bidi::Level,
722        shaping: Shaping,
723    ) -> Self {
724        let mut empty = Self::empty();
725        empty.build(
726            font_system,
727            line,
728            attrs_list,
729            span_range,
730            line_rtl,
731            level,
732            shaping,
733        );
734        empty
735    }
736
737    /// See [`Self::new`].
738    ///
739    /// Reuses as much of the pre-existing internal allocations as possible.
740    pub fn build(
741        &mut self,
742        font_system: &mut FontSystem,
743        line: &str,
744        attrs_list: &AttrsList,
745        span_range: Range<usize>,
746        line_rtl: bool,
747        level: unicode_bidi::Level,
748        shaping: Shaping,
749    ) {
750        let span = &line[span_range.start..span_range.end];
751
752        log::trace!(
753            "  Span {}: '{}'",
754            if level.is_rtl() { "RTL" } else { "LTR" },
755            span
756        );
757
758        let mut words = mem::take(&mut self.words);
759
760        // Cache the shape words in reverse order so they can be popped for reuse in the same order.
761        let mut cached_words = mem::take(&mut font_system.shape_buffer.words);
762        cached_words.clear();
763        if line_rtl != level.is_rtl() {
764            // Un-reverse previous words so the internal glyph counts match accurately when rewriting memory.
765            cached_words.append(&mut words);
766        } else {
767            cached_words.extend(words.drain(..).rev());
768        }
769
770        let mut start_word = 0;
771        for (end_lb, _) in unicode_linebreak::linebreaks(span) {
772            let mut start_lb = end_lb;
773            for (i, c) in span[start_word..end_lb].char_indices().rev() {
774                // TODO: Not all whitespace characters are linebreakable, e.g. 00A0 (No-break
775                // space)
776                // https://www.unicode.org/reports/tr14/#GL
777                // https://www.unicode.org/Public/UCD/latest/ucd/PropList.txt
778                if c.is_whitespace() {
779                    start_lb = start_word + i;
780                } else {
781                    break;
782                }
783            }
784            if start_word < start_lb {
785                let mut word = cached_words.pop().unwrap_or_else(ShapeWord::empty);
786                word.build(
787                    font_system,
788                    line,
789                    attrs_list,
790                    (span_range.start + start_word)..(span_range.start + start_lb),
791                    level,
792                    false,
793                    shaping,
794                );
795                words.push(word);
796            }
797            if start_lb < end_lb {
798                for (i, c) in span[start_lb..end_lb].char_indices() {
799                    // assert!(c.is_whitespace());
800                    let mut word = cached_words.pop().unwrap_or_else(ShapeWord::empty);
801                    word.build(
802                        font_system,
803                        line,
804                        attrs_list,
805                        (span_range.start + start_lb + i)
806                            ..(span_range.start + start_lb + i + c.len_utf8()),
807                        level,
808                        true,
809                        shaping,
810                    );
811                    words.push(word);
812                }
813            }
814            start_word = end_lb;
815        }
816
817        // Reverse glyphs in RTL lines
818        if line_rtl {
819            for word in &mut words {
820                word.glyphs.reverse();
821            }
822        }
823
824        // Reverse words in spans that do not match line direction
825        if line_rtl != level.is_rtl() {
826            words.reverse();
827        }
828
829        self.level = level;
830        self.words = words;
831
832        // Cache buffer for future reuse.
833        font_system.shape_buffer.words = cached_words;
834    }
835}
836
837/// A shaped line (or paragraph)
838#[derive(Clone, Debug)]
839pub struct ShapeLine {
840    pub rtl: bool,
841    pub spans: Vec<ShapeSpan>,
842    pub metrics_opt: Option<Metrics>,
843}
844
845// Visual Line Ranges: (span_index, (first_word_index, first_glyph_index), (last_word_index, last_glyph_index))
846type VlRange = (usize, (usize, usize), (usize, usize));
847
848#[derive(Default)]
849struct VisualLine {
850    ranges: Vec<VlRange>,
851    spaces: u32,
852    w: f32,
853}
854
855impl VisualLine {
856    fn clear(&mut self) {
857        self.ranges.clear();
858        self.spaces = 0;
859        self.w = 0.;
860    }
861}
862
863impl ShapeLine {
864    /// Creates an empty line.
865    ///
866    /// The returned line is in an invalid state until [`Self::build_in_buffer`] is called.
867    pub(crate) fn empty() -> Self {
868        Self {
869            rtl: false,
870            spans: Vec::default(),
871            metrics_opt: None,
872        }
873    }
874
875    /// Shape a line into a set of spans, using a scratch buffer. If [`unicode_bidi::BidiInfo`]
876    /// detects multiple paragraphs, they will be joined.
877    ///
878    /// # Panics
879    ///
880    /// Will panic if `line` contains multiple paragraphs that do not have matching direction
881    pub fn new(
882        font_system: &mut FontSystem,
883        line: &str,
884        attrs_list: &AttrsList,
885        shaping: Shaping,
886        tab_width: u16,
887    ) -> Self {
888        let mut empty = Self::empty();
889        empty.build(font_system, line, attrs_list, shaping, tab_width);
890        empty
891    }
892
893    /// See [`Self::new`].
894    ///
895    /// Reuses as much of the pre-existing internal allocations as possible.
896    ///
897    /// # Panics
898    ///
899    /// Will panic if `line` contains multiple paragraphs that do not have matching direction
900    pub fn build(
901        &mut self,
902        font_system: &mut FontSystem,
903        line: &str,
904        attrs_list: &AttrsList,
905        shaping: Shaping,
906        tab_width: u16,
907    ) {
908        let mut spans = mem::take(&mut self.spans);
909
910        // Cache the shape spans in reverse order so they can be popped for reuse in the same order.
911        let mut cached_spans = mem::take(&mut font_system.shape_buffer.spans);
912        cached_spans.clear();
913        cached_spans.extend(spans.drain(..).rev());
914
915        let bidi = unicode_bidi::BidiInfo::new(line, None);
916        let rtl = if bidi.paragraphs.is_empty() {
917            false
918        } else {
919            bidi.paragraphs[0].level.is_rtl()
920        };
921
922        log::trace!("Line {}: '{}'", if rtl { "RTL" } else { "LTR" }, line);
923
924        for para_info in &bidi.paragraphs {
925            let line_rtl = para_info.level.is_rtl();
926            assert_eq!(line_rtl, rtl);
927
928            let line_range = para_info.range.clone();
929            let levels = Self::adjust_levels(&unicode_bidi::Paragraph::new(&bidi, para_info));
930
931            // Find consecutive level runs. We use this to create Spans.
932            // Each span is a set of characters with equal levels.
933            let mut start = line_range.start;
934            let mut run_level = levels[start];
935            spans.reserve(line_range.end - start + 1);
936
937            for (i, &new_level) in levels
938                .iter()
939                .enumerate()
940                .take(line_range.end)
941                .skip(start + 1)
942            {
943                if new_level != run_level {
944                    // End of the previous run, start of a new one.
945                    let mut span = cached_spans.pop().unwrap_or_else(ShapeSpan::empty);
946                    span.build(
947                        font_system,
948                        line,
949                        attrs_list,
950                        start..i,
951                        line_rtl,
952                        run_level,
953                        shaping,
954                    );
955                    spans.push(span);
956                    start = i;
957                    run_level = new_level;
958                }
959            }
960            let mut span = cached_spans.pop().unwrap_or_else(ShapeSpan::empty);
961            span.build(
962                font_system,
963                line,
964                attrs_list,
965                start..line_range.end,
966                line_rtl,
967                run_level,
968                shaping,
969            );
970            spans.push(span);
971        }
972
973        // Adjust for tabs
974        let mut x = 0.0;
975        for span in &mut spans {
976            for word in &mut span.words {
977                for glyph in &mut word.glyphs {
978                    if line.get(glyph.start..glyph.end) == Some("\t") {
979                        // Tabs are shaped as spaces, so they will always have the x_advance of a space.
980                        let tab_x_advance = f32::from(tab_width) * glyph.x_advance;
981                        let tab_stop = (math::floorf(x / tab_x_advance) + 1.0) * tab_x_advance;
982                        glyph.x_advance = tab_stop - x;
983                    }
984                    x += glyph.x_advance;
985                }
986            }
987        }
988
989        self.rtl = rtl;
990        self.spans = spans;
991        self.metrics_opt = attrs_list.defaults().metrics_opt.map(Into::into);
992
993        // Return the buffer for later reuse.
994        font_system.shape_buffer.spans = cached_spans;
995    }
996
997    // A modified version of first part of unicode_bidi::bidi_info::visual_run
998    fn adjust_levels(para: &unicode_bidi::Paragraph) -> Vec<unicode_bidi::Level> {
999        use unicode_bidi::BidiClass::{B, BN, FSI, LRE, LRI, LRO, PDF, PDI, RLE, RLI, RLO, S, WS};
1000        let text = para.info.text;
1001        let levels = &para.info.levels;
1002        let original_classes = &para.info.original_classes;
1003
1004        let mut levels = levels.clone();
1005        let line_classes = &original_classes[..];
1006        let line_levels = &mut levels[..];
1007
1008        // Reset some whitespace chars to paragraph level.
1009        // <http://www.unicode.org/reports/tr9/#L1>
1010        let mut reset_from: Option<usize> = Some(0);
1011        let mut reset_to: Option<usize> = None;
1012        for (i, c) in text.char_indices() {
1013            match line_classes[i] {
1014                // Ignored by X9
1015                RLE | LRE | RLO | LRO | PDF | BN => {}
1016                // Segment separator, Paragraph separator
1017                B | S => {
1018                    assert_eq!(reset_to, None);
1019                    reset_to = Some(i + c.len_utf8());
1020                    if reset_from.is_none() {
1021                        reset_from = Some(i);
1022                    }
1023                }
1024                // Whitespace, isolate formatting
1025                WS | FSI | LRI | RLI | PDI => {
1026                    if reset_from.is_none() {
1027                        reset_from = Some(i);
1028                    }
1029                }
1030                _ => {
1031                    reset_from = None;
1032                }
1033            }
1034            if let (Some(from), Some(to)) = (reset_from, reset_to) {
1035                for level in &mut line_levels[from..to] {
1036                    *level = para.para.level;
1037                }
1038                reset_from = None;
1039                reset_to = None;
1040            }
1041        }
1042        if let Some(from) = reset_from {
1043            for level in &mut line_levels[from..] {
1044                *level = para.para.level;
1045            }
1046        }
1047        levels
1048    }
1049
1050    // A modified version of second part of unicode_bidi::bidi_info::visual run
1051    fn reorder(&self, line_range: &[VlRange]) -> Vec<Range<usize>> {
1052        let line: Vec<unicode_bidi::Level> = line_range
1053            .iter()
1054            .map(|(span_index, _, _)| self.spans[*span_index].level)
1055            .collect();
1056        // Find consecutive level runs.
1057        let mut runs = Vec::new();
1058        let mut start = 0;
1059        let mut run_level = line[start];
1060        let mut min_level = run_level;
1061        let mut max_level = run_level;
1062
1063        for (i, &new_level) in line.iter().enumerate().skip(start + 1) {
1064            if new_level != run_level {
1065                // End of the previous run, start of a new one.
1066                runs.push(start..i);
1067                start = i;
1068                run_level = new_level;
1069                min_level = min(run_level, min_level);
1070                max_level = max(run_level, max_level);
1071            }
1072        }
1073        runs.push(start..line.len());
1074
1075        let run_count = runs.len();
1076
1077        // Re-order the odd runs.
1078        // <http://www.unicode.org/reports/tr9/#L2>
1079
1080        // Stop at the lowest *odd* level.
1081        min_level = min_level.new_lowest_ge_rtl().expect("Level error");
1082
1083        while max_level >= min_level {
1084            // Look for the start of a sequence of consecutive runs of max_level or higher.
1085            let mut seq_start = 0;
1086            while seq_start < run_count {
1087                if line[runs[seq_start].start] < max_level {
1088                    seq_start += 1;
1089                    continue;
1090                }
1091
1092                // Found the start of a sequence. Now find the end.
1093                let mut seq_end = seq_start + 1;
1094                while seq_end < run_count {
1095                    if line[runs[seq_end].start] < max_level {
1096                        break;
1097                    }
1098                    seq_end += 1;
1099                }
1100
1101                // Reverse the runs within this sequence.
1102                runs[seq_start..seq_end].reverse();
1103
1104                seq_start = seq_end;
1105            }
1106            max_level
1107                .lower(1)
1108                .expect("Lowering embedding level below zero");
1109        }
1110
1111        runs
1112    }
1113
1114    pub fn layout(
1115        &self,
1116        font_size: f32,
1117        width_opt: Option<f32>,
1118        wrap: Wrap,
1119        align: Option<Align>,
1120        match_mono_width: Option<f32>,
1121    ) -> Vec<LayoutLine> {
1122        let mut lines = Vec::with_capacity(1);
1123        self.layout_to_buffer(
1124            &mut ShapeBuffer::default(),
1125            font_size,
1126            width_opt,
1127            wrap,
1128            align,
1129            &mut lines,
1130            match_mono_width,
1131        );
1132        lines
1133    }
1134
1135    pub fn layout_to_buffer(
1136        &self,
1137        scratch: &mut ShapeBuffer,
1138        font_size: f32,
1139        width_opt: Option<f32>,
1140        wrap: Wrap,
1141        align: Option<Align>,
1142        layout_lines: &mut Vec<LayoutLine>,
1143        match_mono_width: Option<f32>,
1144    ) {
1145        fn add_to_visual_line(
1146            vl: &mut VisualLine,
1147            span_index: usize,
1148            start: (usize, usize),
1149            end: (usize, usize),
1150            width: f32,
1151            number_of_blanks: u32,
1152        ) {
1153            if end == start {
1154                return;
1155            }
1156
1157            vl.ranges.push((span_index, start, end));
1158            vl.w += width;
1159            vl.spaces += number_of_blanks;
1160        }
1161
1162        // For each visual line a list of  (span index,  and range of words in that span)
1163        // Note that a BiDi visual line could have multiple spans or parts of them
1164        // let mut vl_range_of_spans = Vec::with_capacity(1);
1165        let mut visual_lines = mem::take(&mut scratch.visual_lines);
1166        let mut cached_visual_lines = mem::take(&mut scratch.cached_visual_lines);
1167        cached_visual_lines.clear();
1168        cached_visual_lines.extend(visual_lines.drain(..).map(|mut l| {
1169            l.clear();
1170            l
1171        }));
1172
1173        // Cache glyph sets in reverse order so they will ideally be reused in exactly the same lines.
1174        let mut cached_glyph_sets = mem::take(&mut scratch.glyph_sets);
1175        cached_glyph_sets.clear();
1176        cached_glyph_sets.extend(layout_lines.drain(..).rev().map(|mut v| {
1177            v.glyphs.clear();
1178            v.glyphs
1179        }));
1180
1181        // This would keep the maximum number of spans that would fit on a visual line
1182        // If one span is too large, this variable will hold the range of words inside that span
1183        // that fits on a line.
1184        // let mut current_visual_line: Vec<VlRange> = Vec::with_capacity(1);
1185        let mut current_visual_line = cached_visual_lines.pop().unwrap_or_default();
1186
1187        if wrap == Wrap::None {
1188            for (span_index, span) in self.spans.iter().enumerate() {
1189                let mut word_range_width = 0.;
1190                let mut number_of_blanks: u32 = 0;
1191                for word in &span.words {
1192                    let word_width = word.width(font_size);
1193                    word_range_width += word_width;
1194                    if word.blank {
1195                        number_of_blanks += 1;
1196                    }
1197                }
1198                add_to_visual_line(
1199                    &mut current_visual_line,
1200                    span_index,
1201                    (0, 0),
1202                    (span.words.len(), 0),
1203                    word_range_width,
1204                    number_of_blanks,
1205                );
1206            }
1207        } else {
1208            for (span_index, span) in self.spans.iter().enumerate() {
1209                let mut word_range_width = 0.;
1210                let mut width_before_last_blank = 0.;
1211                let mut number_of_blanks: u32 = 0;
1212
1213                // Create the word ranges that fits in a visual line
1214                if self.rtl != span.level.is_rtl() {
1215                    // incongruent directions
1216                    let mut fitting_start = (span.words.len(), 0);
1217                    for (i, word) in span.words.iter().enumerate().rev() {
1218                        let word_width = word.width(font_size);
1219
1220                        // Addition in the same order used to compute the final width, so that
1221                        // relayouts with that width as the `line_width` will produce the same
1222                        // wrapping results.
1223                        if current_visual_line.w + (word_range_width + word_width)
1224                            <= width_opt.unwrap_or(f32::INFINITY)
1225                            // Include one blank word over the width limit since it won't be
1226                            // counted in the final width
1227                            || (word.blank
1228                                && (current_visual_line.w + word_range_width) <= width_opt.unwrap_or(f32::INFINITY))
1229                        {
1230                            // fits
1231                            if word.blank {
1232                                number_of_blanks += 1;
1233                                width_before_last_blank = word_range_width;
1234                            }
1235                            word_range_width += word_width;
1236                        } else if wrap == Wrap::Glyph
1237                            // Make sure that the word is able to fit on it's own line, if not, fall back to Glyph wrapping.
1238                            || (wrap == Wrap::WordOrGlyph && word_width > width_opt.unwrap_or(f32::INFINITY))
1239                        {
1240                            // Commit the current line so that the word starts on the next line.
1241                            if word_range_width > 0.
1242                                && wrap == Wrap::WordOrGlyph
1243                                && word_width > width_opt.unwrap_or(f32::INFINITY)
1244                            {
1245                                add_to_visual_line(
1246                                    &mut current_visual_line,
1247                                    span_index,
1248                                    (i + 1, 0),
1249                                    fitting_start,
1250                                    word_range_width,
1251                                    number_of_blanks,
1252                                );
1253
1254                                visual_lines.push(current_visual_line);
1255                                current_visual_line = cached_visual_lines.pop().unwrap_or_default();
1256
1257                                number_of_blanks = 0;
1258                                word_range_width = 0.;
1259
1260                                fitting_start = (i, 0);
1261                            }
1262
1263                            for (glyph_i, glyph) in word.glyphs.iter().enumerate().rev() {
1264                                let glyph_width = glyph.width(font_size);
1265                                if current_visual_line.w + (word_range_width + glyph_width)
1266                                    <= width_opt.unwrap_or(f32::INFINITY)
1267                                {
1268                                    word_range_width += glyph_width;
1269                                } else {
1270                                    add_to_visual_line(
1271                                        &mut current_visual_line,
1272                                        span_index,
1273                                        (i, glyph_i + 1),
1274                                        fitting_start,
1275                                        word_range_width,
1276                                        number_of_blanks,
1277                                    );
1278                                    visual_lines.push(current_visual_line);
1279                                    current_visual_line =
1280                                        cached_visual_lines.pop().unwrap_or_default();
1281
1282                                    number_of_blanks = 0;
1283                                    word_range_width = glyph_width;
1284                                    fitting_start = (i, glyph_i + 1);
1285                                }
1286                            }
1287                        } else {
1288                            // Wrap::Word, Wrap::WordOrGlyph
1289
1290                            // If we had a previous range, commit that line before the next word.
1291                            if word_range_width > 0. {
1292                                // Current word causing a wrap is not whitespace, so we ignore the
1293                                // previous word if it's a whitespace
1294                                let trailing_blank = span
1295                                    .words
1296                                    .get(i + 1)
1297                                    .is_some_and(|previous_word| previous_word.blank);
1298
1299                                if trailing_blank {
1300                                    number_of_blanks = number_of_blanks.saturating_sub(1);
1301                                    add_to_visual_line(
1302                                        &mut current_visual_line,
1303                                        span_index,
1304                                        (i + 2, 0),
1305                                        fitting_start,
1306                                        width_before_last_blank,
1307                                        number_of_blanks,
1308                                    );
1309                                } else {
1310                                    add_to_visual_line(
1311                                        &mut current_visual_line,
1312                                        span_index,
1313                                        (i + 1, 0),
1314                                        fitting_start,
1315                                        word_range_width,
1316                                        number_of_blanks,
1317                                    );
1318                                }
1319
1320                                visual_lines.push(current_visual_line);
1321                                current_visual_line = cached_visual_lines.pop().unwrap_or_default();
1322                                number_of_blanks = 0;
1323                            }
1324
1325                            if word.blank {
1326                                word_range_width = 0.;
1327                                fitting_start = (i, 0);
1328                            } else {
1329                                word_range_width = word_width;
1330                                fitting_start = (i + 1, 0);
1331                            }
1332                        }
1333                    }
1334                    add_to_visual_line(
1335                        &mut current_visual_line,
1336                        span_index,
1337                        (0, 0),
1338                        fitting_start,
1339                        word_range_width,
1340                        number_of_blanks,
1341                    );
1342                } else {
1343                    // congruent direction
1344                    let mut fitting_start = (0, 0);
1345                    for (i, word) in span.words.iter().enumerate() {
1346                        let word_width = word.width(font_size);
1347                        if current_visual_line.w + (word_range_width + word_width)
1348                            <= width_opt.unwrap_or(f32::INFINITY)
1349                            // Include one blank word over the width limit since it won't be
1350                            // counted in the final width.
1351                            || (word.blank
1352                                && (current_visual_line.w + word_range_width) <= width_opt.unwrap_or(f32::INFINITY))
1353                        {
1354                            // fits
1355                            if word.blank {
1356                                number_of_blanks += 1;
1357                                width_before_last_blank = word_range_width;
1358                            }
1359                            word_range_width += word_width;
1360                        } else if wrap == Wrap::Glyph
1361                            // Make sure that the word is able to fit on it's own line, if not, fall back to Glyph wrapping.
1362                            || (wrap == Wrap::WordOrGlyph && word_width > width_opt.unwrap_or(f32::INFINITY))
1363                        {
1364                            // Commit the current line so that the word starts on the next line.
1365                            if word_range_width > 0.
1366                                && wrap == Wrap::WordOrGlyph
1367                                && word_width > width_opt.unwrap_or(f32::INFINITY)
1368                            {
1369                                add_to_visual_line(
1370                                    &mut current_visual_line,
1371                                    span_index,
1372                                    fitting_start,
1373                                    (i, 0),
1374                                    word_range_width,
1375                                    number_of_blanks,
1376                                );
1377
1378                                visual_lines.push(current_visual_line);
1379                                current_visual_line = cached_visual_lines.pop().unwrap_or_default();
1380
1381                                number_of_blanks = 0;
1382                                word_range_width = 0.;
1383
1384                                fitting_start = (i, 0);
1385                            }
1386
1387                            for (glyph_i, glyph) in word.glyphs.iter().enumerate() {
1388                                let glyph_width = glyph.width(font_size);
1389                                if current_visual_line.w + (word_range_width + glyph_width)
1390                                    <= width_opt.unwrap_or(f32::INFINITY)
1391                                {
1392                                    word_range_width += glyph_width;
1393                                } else {
1394                                    add_to_visual_line(
1395                                        &mut current_visual_line,
1396                                        span_index,
1397                                        fitting_start,
1398                                        (i, glyph_i),
1399                                        word_range_width,
1400                                        number_of_blanks,
1401                                    );
1402                                    visual_lines.push(current_visual_line);
1403                                    current_visual_line =
1404                                        cached_visual_lines.pop().unwrap_or_default();
1405
1406                                    number_of_blanks = 0;
1407                                    word_range_width = glyph_width;
1408                                    fitting_start = (i, glyph_i);
1409                                }
1410                            }
1411                        } else {
1412                            // Wrap::Word, Wrap::WordOrGlyph
1413
1414                            // If we had a previous range, commit that line before the next word.
1415                            if word_range_width > 0. {
1416                                // Current word causing a wrap is not whitespace, so we ignore the
1417                                // previous word if it's a whitespace.
1418                                let trailing_blank = i > 0 && span.words[i - 1].blank;
1419
1420                                if trailing_blank {
1421                                    number_of_blanks = number_of_blanks.saturating_sub(1);
1422                                    add_to_visual_line(
1423                                        &mut current_visual_line,
1424                                        span_index,
1425                                        fitting_start,
1426                                        (i - 1, 0),
1427                                        width_before_last_blank,
1428                                        number_of_blanks,
1429                                    );
1430                                } else {
1431                                    add_to_visual_line(
1432                                        &mut current_visual_line,
1433                                        span_index,
1434                                        fitting_start,
1435                                        (i, 0),
1436                                        word_range_width,
1437                                        number_of_blanks,
1438                                    );
1439                                }
1440
1441                                visual_lines.push(current_visual_line);
1442                                current_visual_line = cached_visual_lines.pop().unwrap_or_default();
1443                                number_of_blanks = 0;
1444                            }
1445
1446                            if word.blank {
1447                                word_range_width = 0.;
1448                                fitting_start = (i + 1, 0);
1449                            } else {
1450                                word_range_width = word_width;
1451                                fitting_start = (i, 0);
1452                            }
1453                        }
1454                    }
1455                    add_to_visual_line(
1456                        &mut current_visual_line,
1457                        span_index,
1458                        fitting_start,
1459                        (span.words.len(), 0),
1460                        word_range_width,
1461                        number_of_blanks,
1462                    );
1463                }
1464            }
1465        }
1466
1467        if current_visual_line.ranges.is_empty() {
1468            current_visual_line.clear();
1469            cached_visual_lines.push(current_visual_line);
1470        } else {
1471            visual_lines.push(current_visual_line);
1472        }
1473
1474        // Create the LayoutLines using the ranges inside visual lines
1475        let align = align.unwrap_or(if self.rtl { Align::Right } else { Align::Left });
1476
1477        let line_width = width_opt.map_or_else(
1478            || {
1479                let mut width: f32 = 0.0;
1480                for visual_line in &visual_lines {
1481                    width = width.max(visual_line.w);
1482                }
1483                width
1484            },
1485            |width| width,
1486        );
1487
1488        let start_x = if self.rtl { line_width } else { 0.0 };
1489
1490        let number_of_visual_lines = visual_lines.len();
1491        for (index, visual_line) in visual_lines.iter().enumerate() {
1492            if visual_line.ranges.is_empty() {
1493                continue;
1494            }
1495            let new_order = self.reorder(&visual_line.ranges);
1496            let mut glyphs = cached_glyph_sets
1497                .pop()
1498                .unwrap_or_else(|| Vec::with_capacity(1));
1499            let mut x = start_x;
1500            let mut y = 0.;
1501            let mut max_ascent: f32 = 0.;
1502            let mut max_descent: f32 = 0.;
1503            let alignment_correction = match (align, self.rtl) {
1504                (Align::Left, true) => line_width - visual_line.w,
1505                (Align::Left, false) => 0.,
1506                (Align::Right, true) => 0.,
1507                (Align::Right, false) => line_width - visual_line.w,
1508                (Align::Center, _) => (line_width - visual_line.w) / 2.0,
1509                (Align::End, _) => line_width - visual_line.w,
1510                (Align::Justified, _) => 0.,
1511            };
1512
1513            if self.rtl {
1514                x -= alignment_correction;
1515            } else {
1516                x += alignment_correction;
1517            }
1518
1519            // TODO: Only certain `is_whitespace` chars are typically expanded but this is what is
1520            // currently used to compute `visual_line.spaces`.
1521            //
1522            // https://www.unicode.org/reports/tr14/#Introduction
1523            // > When expanding or compressing interword space according to common
1524            // > typographical practice, only the spaces marked by U+0020 SPACE and U+00A0
1525            // > NO-BREAK SPACE are subject to compression, and only spaces marked by U+0020
1526            // > SPACE, U+00A0 NO-BREAK SPACE, and occasionally spaces marked by U+2009 THIN
1527            // > SPACE are subject to expansion. All other space characters normally have
1528            // > fixed width.
1529            //
1530            // (also some spaces aren't followed by potential linebreaks but they could
1531            //  still be expanded)
1532
1533            // Amount of extra width added to each blank space within a line.
1534            let justification_expansion = if matches!(align, Align::Justified)
1535                && visual_line.spaces > 0
1536                // Don't justify the last line in a paragraph.
1537                && index != number_of_visual_lines - 1
1538            {
1539                (line_width - visual_line.w) / visual_line.spaces as f32
1540            } else {
1541                0.
1542            };
1543
1544            let mut process_range = |range: Range<usize>| {
1545                for &(span_index, (starting_word, starting_glyph), (ending_word, ending_glyph)) in
1546                    &visual_line.ranges[range]
1547                {
1548                    let span = &self.spans[span_index];
1549                    // If ending_glyph is not 0 we need to include glyphs from the ending_word
1550                    for i in starting_word..ending_word + usize::from(ending_glyph != 0) {
1551                        let word = &span.words[i];
1552                        let included_glyphs = match (i == starting_word, i == ending_word) {
1553                            (false, false) => &word.glyphs[..],
1554                            (true, false) => &word.glyphs[starting_glyph..],
1555                            (false, true) => &word.glyphs[..ending_glyph],
1556                            (true, true) => &word.glyphs[starting_glyph..ending_glyph],
1557                        };
1558
1559                        for glyph in included_glyphs {
1560                            // Use overridden font size
1561                            let font_size = glyph.metrics_opt.map_or(font_size, |x| x.font_size);
1562
1563                            let match_mono_em_width = match_mono_width.map(|w| w / font_size);
1564
1565                            let glyph_font_size = match (
1566                                match_mono_em_width,
1567                                glyph.font_monospace_em_width,
1568                            ) {
1569                                (Some(match_em_width), Some(glyph_em_width))
1570                                    if glyph_em_width != match_em_width =>
1571                                {
1572                                    let glyph_to_match_factor = glyph_em_width / match_em_width;
1573                                    let glyph_font_size = math::roundf(glyph_to_match_factor)
1574                                        .max(1.0)
1575                                        / glyph_to_match_factor
1576                                        * font_size;
1577                                    log::trace!(
1578                                        "Adjusted glyph font size ({font_size} => {glyph_font_size})"
1579                                    );
1580                                    glyph_font_size
1581                                }
1582                                _ => font_size,
1583                            };
1584
1585                            let x_advance = glyph_font_size.mul_add(
1586                                glyph.x_advance,
1587                                if word.blank {
1588                                    justification_expansion
1589                                } else {
1590                                    0.0
1591                                },
1592                            );
1593                            if self.rtl {
1594                                x -= x_advance;
1595                            }
1596                            let y_advance = glyph_font_size * glyph.y_advance;
1597                            glyphs.push(glyph.layout(
1598                                glyph_font_size,
1599                                glyph.metrics_opt.map(|x| x.line_height),
1600                                x,
1601                                y,
1602                                x_advance,
1603                                span.level,
1604                            ));
1605                            if !self.rtl {
1606                                x += x_advance;
1607                            }
1608                            y += y_advance;
1609                            max_ascent = max_ascent.max(glyph_font_size * glyph.ascent);
1610                            max_descent = max_descent.max(glyph_font_size * glyph.descent);
1611                        }
1612                    }
1613                }
1614            };
1615
1616            if self.rtl {
1617                for range in new_order.into_iter().rev() {
1618                    process_range(range);
1619                }
1620            } else {
1621                /* LTR */
1622                for range in new_order {
1623                    process_range(range);
1624                }
1625            }
1626
1627            let mut line_height_opt: Option<f32> = None;
1628            for glyph in &glyphs {
1629                if let Some(glyph_line_height) = glyph.line_height_opt {
1630                    line_height_opt = line_height_opt
1631                        .map_or(Some(glyph_line_height), |line_height| {
1632                            Some(line_height.max(glyph_line_height))
1633                        });
1634                }
1635            }
1636
1637            layout_lines.push(LayoutLine {
1638                w: if align != Align::Justified {
1639                    visual_line.w
1640                } else if self.rtl {
1641                    start_x - x
1642                } else {
1643                    x
1644                },
1645                max_ascent,
1646                max_descent,
1647                line_height_opt,
1648                glyphs,
1649            });
1650        }
1651
1652        // This is used to create a visual line for empty lines (e.g. lines with only a <CR>)
1653        if layout_lines.is_empty() {
1654            layout_lines.push(LayoutLine {
1655                w: 0.0,
1656                max_ascent: 0.0,
1657                max_descent: 0.0,
1658                line_height_opt: self.metrics_opt.map(|x| x.line_height),
1659                glyphs: Vec::default(),
1660            });
1661        }
1662
1663        // Restore the buffer to the scratch set to prevent reallocations.
1664        scratch.visual_lines = visual_lines;
1665        scratch.visual_lines.append(&mut cached_visual_lines);
1666        scratch.cached_visual_lines = cached_visual_lines;
1667        scratch.glyph_sets = cached_glyph_sets;
1668    }
1669}