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