epaint/text/
text_layout.rs

1use std::sync::Arc;
2
3use emath::{Align, GuiRounding as _, NumExt as _, Pos2, Rect, Vec2, pos2, vec2};
4
5use crate::{Color32, Mesh, Stroke, Vertex, stroke::PathStroke, text::font::Font};
6
7use super::{FontsImpl, Galley, Glyph, LayoutJob, LayoutSection, PlacedRow, Row, RowVisuals};
8
9// ----------------------------------------------------------------------------
10
11/// Represents GUI scale and convenience methods for rounding to pixels.
12#[derive(Clone, Copy)]
13struct PointScale {
14    pub pixels_per_point: f32,
15}
16
17impl PointScale {
18    #[inline(always)]
19    pub fn new(pixels_per_point: f32) -> Self {
20        Self { pixels_per_point }
21    }
22
23    #[inline(always)]
24    pub fn pixels_per_point(&self) -> f32 {
25        self.pixels_per_point
26    }
27
28    #[inline(always)]
29    pub fn round_to_pixel(&self, point: f32) -> f32 {
30        (point * self.pixels_per_point).round() / self.pixels_per_point
31    }
32
33    #[inline(always)]
34    pub fn floor_to_pixel(&self, point: f32) -> f32 {
35        (point * self.pixels_per_point).floor() / self.pixels_per_point
36    }
37}
38
39// ----------------------------------------------------------------------------
40
41/// Temporary storage before line-wrapping.
42#[derive(Clone)]
43struct Paragraph {
44    /// Start of the next glyph to be added.
45    pub cursor_x: f32,
46
47    /// This is included in case there are no glyphs
48    pub section_index_at_start: u32,
49
50    pub glyphs: Vec<Glyph>,
51
52    /// In case of an empty paragraph ("\n"), use this as height.
53    pub empty_paragraph_height: f32,
54}
55
56impl Paragraph {
57    pub fn from_section_index(section_index_at_start: u32) -> Self {
58        Self {
59            cursor_x: 0.0,
60            section_index_at_start,
61            glyphs: vec![],
62            empty_paragraph_height: 0.0,
63        }
64    }
65}
66
67/// Layout text into a [`Galley`].
68///
69/// In most cases you should use [`crate::Fonts::layout_job`] instead
70/// since that memoizes the input, making subsequent layouting of the same text much faster.
71pub fn layout(fonts: &mut FontsImpl, job: Arc<LayoutJob>) -> Galley {
72    profiling::function_scope!();
73
74    if job.wrap.max_rows == 0 {
75        // Early-out: no text
76        return Galley {
77            job,
78            rows: Default::default(),
79            rect: Rect::ZERO,
80            mesh_bounds: Rect::NOTHING,
81            num_vertices: 0,
82            num_indices: 0,
83            pixels_per_point: fonts.pixels_per_point(),
84            elided: true,
85            intrinsic_size: Vec2::ZERO,
86        };
87    }
88
89    // For most of this we ignore the y coordinate:
90
91    let mut paragraphs = vec![Paragraph::from_section_index(0)];
92    for (section_index, section) in job.sections.iter().enumerate() {
93        layout_section(fonts, &job, section_index as u32, section, &mut paragraphs);
94    }
95
96    let point_scale = PointScale::new(fonts.pixels_per_point());
97
98    let intrinsic_size = calculate_intrinsic_size(point_scale, &job, &paragraphs);
99
100    let mut elided = false;
101    let mut rows = rows_from_paragraphs(paragraphs, &job, &mut elided);
102    if elided {
103        if let Some(last_placed) = rows.last_mut() {
104            let last_row = Arc::make_mut(&mut last_placed.row);
105            replace_last_glyph_with_overflow_character(fonts, &job, last_row);
106            if let Some(last) = last_row.glyphs.last() {
107                last_row.size.x = last.max_x();
108            }
109        }
110    }
111
112    let justify = job.justify && job.wrap.max_width.is_finite();
113
114    if justify || job.halign != Align::LEFT {
115        let num_rows = rows.len();
116        for (i, placed_row) in rows.iter_mut().enumerate() {
117            let is_last_row = i + 1 == num_rows;
118            let justify_row = justify && !placed_row.ends_with_newline && !is_last_row;
119            halign_and_justify_row(
120                point_scale,
121                placed_row,
122                job.halign,
123                job.wrap.max_width,
124                justify_row,
125            );
126        }
127    }
128
129    // Calculate the Y positions and tessellate the text:
130    galley_from_rows(point_scale, job, rows, elided, intrinsic_size)
131}
132
133// Ignores the Y coordinate.
134fn layout_section(
135    fonts: &mut FontsImpl,
136    job: &LayoutJob,
137    section_index: u32,
138    section: &LayoutSection,
139    out_paragraphs: &mut Vec<Paragraph>,
140) {
141    let LayoutSection {
142        leading_space,
143        byte_range,
144        format,
145    } = section;
146    let font = fonts.font(&format.font_id);
147    let line_height = section
148        .format
149        .line_height
150        .unwrap_or_else(|| font.row_height());
151    let extra_letter_spacing = section.format.extra_letter_spacing;
152
153    let mut paragraph = out_paragraphs.last_mut().unwrap();
154    if paragraph.glyphs.is_empty() {
155        paragraph.empty_paragraph_height = line_height; // TODO(emilk): replace this hack with actually including `\n` in the glyphs?
156    }
157
158    paragraph.cursor_x += leading_space;
159
160    let mut last_glyph_id = None;
161
162    for chr in job.text[byte_range.clone()].chars() {
163        if job.break_on_newline && chr == '\n' {
164            out_paragraphs.push(Paragraph::from_section_index(section_index));
165            paragraph = out_paragraphs.last_mut().unwrap();
166            paragraph.empty_paragraph_height = line_height; // TODO(emilk): replace this hack with actually including `\n` in the glyphs?
167        } else {
168            let (font_impl, glyph_info) = font.font_impl_and_glyph_info(chr);
169            if let Some(font_impl) = font_impl {
170                if let Some(last_glyph_id) = last_glyph_id {
171                    paragraph.cursor_x += font_impl.pair_kerning(last_glyph_id, glyph_info.id);
172                    paragraph.cursor_x += extra_letter_spacing;
173                }
174            }
175
176            paragraph.glyphs.push(Glyph {
177                chr,
178                pos: pos2(paragraph.cursor_x, f32::NAN),
179                advance_width: glyph_info.advance_width,
180                line_height,
181                font_impl_height: font_impl.map_or(0.0, |f| f.row_height()),
182                font_impl_ascent: font_impl.map_or(0.0, |f| f.ascent()),
183                font_height: font.row_height(),
184                font_ascent: font.ascent(),
185                uv_rect: glyph_info.uv_rect,
186                section_index,
187            });
188
189            paragraph.cursor_x += glyph_info.advance_width;
190            paragraph.cursor_x = font.round_to_pixel(paragraph.cursor_x);
191            last_glyph_id = Some(glyph_info.id);
192        }
193    }
194}
195
196/// Calculate the intrinsic size of the text.
197///
198/// The result is eventually passed to `Response::intrinsic_size`.
199/// This works by calculating the size of each `Paragraph` (instead of each `Row`).
200fn calculate_intrinsic_size(
201    point_scale: PointScale,
202    job: &LayoutJob,
203    paragraphs: &[Paragraph],
204) -> Vec2 {
205    let mut intrinsic_size = Vec2::ZERO;
206    for (idx, paragraph) in paragraphs.iter().enumerate() {
207        let width = paragraph
208            .glyphs
209            .last()
210            .map(|l| l.max_x())
211            .unwrap_or_default();
212        intrinsic_size.x = f32::max(intrinsic_size.x, width);
213
214        let mut height = paragraph
215            .glyphs
216            .iter()
217            .map(|g| g.line_height)
218            .max_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal))
219            .unwrap_or(paragraph.empty_paragraph_height);
220        if idx == 0 {
221            height = f32::max(height, job.first_row_min_height);
222        }
223        intrinsic_size.y += point_scale.round_to_pixel(height);
224    }
225    intrinsic_size
226}
227
228// Ignores the Y coordinate.
229fn rows_from_paragraphs(
230    paragraphs: Vec<Paragraph>,
231    job: &LayoutJob,
232    elided: &mut bool,
233) -> Vec<PlacedRow> {
234    let num_paragraphs = paragraphs.len();
235
236    let mut rows = vec![];
237
238    for (i, paragraph) in paragraphs.into_iter().enumerate() {
239        if job.wrap.max_rows <= rows.len() {
240            *elided = true;
241            break;
242        }
243
244        let is_last_paragraph = (i + 1) == num_paragraphs;
245
246        if paragraph.glyphs.is_empty() {
247            rows.push(PlacedRow {
248                pos: pos2(0.0, f32::NAN),
249                row: Arc::new(Row {
250                    section_index_at_start: paragraph.section_index_at_start,
251                    glyphs: vec![],
252                    visuals: Default::default(),
253                    size: vec2(0.0, paragraph.empty_paragraph_height),
254                    ends_with_newline: !is_last_paragraph,
255                }),
256            });
257        } else {
258            let paragraph_max_x = paragraph.glyphs.last().unwrap().max_x();
259            if paragraph_max_x <= job.effective_wrap_width() {
260                // Early-out optimization: the whole paragraph fits on one row.
261                rows.push(PlacedRow {
262                    pos: pos2(0.0, f32::NAN),
263                    row: Arc::new(Row {
264                        section_index_at_start: paragraph.section_index_at_start,
265                        glyphs: paragraph.glyphs,
266                        visuals: Default::default(),
267                        size: vec2(paragraph_max_x, 0.0),
268                        ends_with_newline: !is_last_paragraph,
269                    }),
270                });
271            } else {
272                line_break(&paragraph, job, &mut rows, elided);
273                let placed_row = rows.last_mut().unwrap();
274                let row = Arc::make_mut(&mut placed_row.row);
275                row.ends_with_newline = !is_last_paragraph;
276            }
277        }
278    }
279
280    rows
281}
282
283fn line_break(
284    paragraph: &Paragraph,
285    job: &LayoutJob,
286    out_rows: &mut Vec<PlacedRow>,
287    elided: &mut bool,
288) {
289    let wrap_width = job.effective_wrap_width();
290
291    // Keeps track of good places to insert row break if we exceed `wrap_width`.
292    let mut row_break_candidates = RowBreakCandidates::default();
293
294    let mut first_row_indentation = paragraph.glyphs[0].pos.x;
295    let mut row_start_x = 0.0;
296    let mut row_start_idx = 0;
297
298    for i in 0..paragraph.glyphs.len() {
299        if job.wrap.max_rows <= out_rows.len() {
300            *elided = true;
301            break;
302        }
303
304        let potential_row_width = paragraph.glyphs[i].max_x() - row_start_x;
305
306        if wrap_width < potential_row_width {
307            // Row break:
308
309            if first_row_indentation > 0.0
310                && !row_break_candidates.has_good_candidate(job.wrap.break_anywhere)
311            {
312                // Allow the first row to be completely empty, because we know there will be more space on the next row:
313                // TODO(emilk): this records the height of this first row as zero, though that is probably fine since first_row_indentation usually comes with a first_row_min_height.
314                out_rows.push(PlacedRow {
315                    pos: pos2(0.0, f32::NAN),
316                    row: Arc::new(Row {
317                        section_index_at_start: paragraph.section_index_at_start,
318                        glyphs: vec![],
319                        visuals: Default::default(),
320                        size: Vec2::ZERO,
321                        ends_with_newline: false,
322                    }),
323                });
324                row_start_x += first_row_indentation;
325                first_row_indentation = 0.0;
326            } else if let Some(last_kept_index) = row_break_candidates.get(job.wrap.break_anywhere)
327            {
328                let glyphs: Vec<Glyph> = paragraph.glyphs[row_start_idx..=last_kept_index]
329                    .iter()
330                    .copied()
331                    .map(|mut glyph| {
332                        glyph.pos.x -= row_start_x;
333                        glyph
334                    })
335                    .collect();
336
337                let section_index_at_start = glyphs[0].section_index;
338                let paragraph_max_x = glyphs.last().unwrap().max_x();
339
340                out_rows.push(PlacedRow {
341                    pos: pos2(0.0, f32::NAN),
342                    row: Arc::new(Row {
343                        section_index_at_start,
344                        glyphs,
345                        visuals: Default::default(),
346                        size: vec2(paragraph_max_x, 0.0),
347                        ends_with_newline: false,
348                    }),
349                });
350
351                // Start a new row:
352                row_start_idx = last_kept_index + 1;
353                row_start_x = paragraph.glyphs[row_start_idx].pos.x;
354                row_break_candidates.forget_before_idx(row_start_idx);
355            } else {
356                // Found no place to break, so we have to overrun wrap_width.
357            }
358        }
359
360        row_break_candidates.add(i, &paragraph.glyphs[i..]);
361    }
362
363    if row_start_idx < paragraph.glyphs.len() {
364        // Final row of text:
365
366        if job.wrap.max_rows <= out_rows.len() {
367            *elided = true; // can't fit another row
368        } else {
369            let glyphs: Vec<Glyph> = paragraph.glyphs[row_start_idx..]
370                .iter()
371                .copied()
372                .map(|mut glyph| {
373                    glyph.pos.x -= row_start_x;
374                    glyph
375                })
376                .collect();
377
378            let section_index_at_start = glyphs[0].section_index;
379            let paragraph_min_x = glyphs[0].pos.x;
380            let paragraph_max_x = glyphs.last().unwrap().max_x();
381
382            out_rows.push(PlacedRow {
383                pos: pos2(paragraph_min_x, 0.0),
384                row: Arc::new(Row {
385                    section_index_at_start,
386                    glyphs,
387                    visuals: Default::default(),
388                    size: vec2(paragraph_max_x - paragraph_min_x, 0.0),
389                    ends_with_newline: false,
390                }),
391            });
392        }
393    }
394}
395
396/// Trims the last glyphs in the row and replaces it with an overflow character (e.g. `…`).
397///
398/// Called before we have any Y coordinates.
399fn replace_last_glyph_with_overflow_character(
400    fonts: &mut FontsImpl,
401    job: &LayoutJob,
402    row: &mut Row,
403) {
404    fn row_width(row: &Row) -> f32 {
405        if let (Some(first), Some(last)) = (row.glyphs.first(), row.glyphs.last()) {
406            last.max_x() - first.pos.x
407        } else {
408            0.0
409        }
410    }
411
412    fn row_height(section: &LayoutSection, font: &Font) -> f32 {
413        section
414            .format
415            .line_height
416            .unwrap_or_else(|| font.row_height())
417    }
418
419    let Some(overflow_character) = job.wrap.overflow_character else {
420        return;
421    };
422
423    // We always try to just append the character first:
424    if let Some(last_glyph) = row.glyphs.last() {
425        let section_index = last_glyph.section_index;
426        let section = &job.sections[section_index as usize];
427        let font = fonts.font(&section.format.font_id);
428        let line_height = row_height(section, font);
429
430        let (_, last_glyph_info) = font.font_impl_and_glyph_info(last_glyph.chr);
431
432        let mut x = last_glyph.pos.x + last_glyph.advance_width;
433
434        let (font_impl, replacement_glyph_info) = font.font_impl_and_glyph_info(overflow_character);
435
436        {
437            // Kerning:
438            x += section.format.extra_letter_spacing;
439            if let Some(font_impl) = font_impl {
440                x += font_impl.pair_kerning(last_glyph_info.id, replacement_glyph_info.id);
441            }
442        }
443
444        row.glyphs.push(Glyph {
445            chr: overflow_character,
446            pos: pos2(x, f32::NAN),
447            advance_width: replacement_glyph_info.advance_width,
448            line_height,
449            font_impl_height: font_impl.map_or(0.0, |f| f.row_height()),
450            font_impl_ascent: font_impl.map_or(0.0, |f| f.ascent()),
451            font_height: font.row_height(),
452            font_ascent: font.ascent(),
453            uv_rect: replacement_glyph_info.uv_rect,
454            section_index,
455        });
456    } else {
457        let section_index = row.section_index_at_start;
458        let section = &job.sections[section_index as usize];
459        let font = fonts.font(&section.format.font_id);
460        let line_height = row_height(section, font);
461
462        let x = 0.0; // TODO(emilk): heed paragraph leading_space 😬
463
464        let (font_impl, replacement_glyph_info) = font.font_impl_and_glyph_info(overflow_character);
465
466        row.glyphs.push(Glyph {
467            chr: overflow_character,
468            pos: pos2(x, f32::NAN),
469            advance_width: replacement_glyph_info.advance_width,
470            line_height,
471            font_impl_height: font_impl.map_or(0.0, |f| f.row_height()),
472            font_impl_ascent: font_impl.map_or(0.0, |f| f.ascent()),
473            font_height: font.row_height(),
474            font_ascent: font.ascent(),
475            uv_rect: replacement_glyph_info.uv_rect,
476            section_index,
477        });
478    }
479
480    if row_width(row) <= job.effective_wrap_width() || row.glyphs.len() == 1 {
481        return; // we are done
482    }
483
484    // We didn't fit it. Remove it again…
485    row.glyphs.pop();
486
487    // …then go into a loop where we replace the last character with the overflow character
488    // until we fit within the max_width:
489
490    loop {
491        let (prev_glyph, last_glyph) = match row.glyphs.as_mut_slice() {
492            [.., prev, last] => (Some(prev), last),
493            [.., last] => (None, last),
494            _ => {
495                unreachable!("We've already explicitly handled the empty row");
496            }
497        };
498
499        let section = &job.sections[last_glyph.section_index as usize];
500        let extra_letter_spacing = section.format.extra_letter_spacing;
501        let font = fonts.font(&section.format.font_id);
502
503        if let Some(prev_glyph) = prev_glyph {
504            let prev_glyph_id = font.font_impl_and_glyph_info(prev_glyph.chr).1.id;
505
506            // Undo kerning with previous glyph:
507            let (font_impl, glyph_info) = font.font_impl_and_glyph_info(last_glyph.chr);
508            last_glyph.pos.x -= extra_letter_spacing;
509            if let Some(font_impl) = font_impl {
510                last_glyph.pos.x -= font_impl.pair_kerning(prev_glyph_id, glyph_info.id);
511            }
512
513            // Replace the glyph:
514            last_glyph.chr = overflow_character;
515            let (font_impl, glyph_info) = font.font_impl_and_glyph_info(last_glyph.chr);
516            last_glyph.advance_width = glyph_info.advance_width;
517            last_glyph.font_impl_ascent = font_impl.map_or(0.0, |f| f.ascent());
518            last_glyph.font_impl_height = font_impl.map_or(0.0, |f| f.row_height());
519            last_glyph.uv_rect = glyph_info.uv_rect;
520
521            // Reapply kerning:
522            last_glyph.pos.x += extra_letter_spacing;
523            if let Some(font_impl) = font_impl {
524                last_glyph.pos.x += font_impl.pair_kerning(prev_glyph_id, glyph_info.id);
525            }
526
527            // Check if we're within width budget:
528            if row_width(row) <= job.effective_wrap_width() || row.glyphs.len() == 1 {
529                return; // We are done
530            }
531
532            // We didn't fit - pop the last glyph and try again.
533            row.glyphs.pop();
534        } else {
535            // Just replace and be done with it.
536            last_glyph.chr = overflow_character;
537            let (font_impl, glyph_info) = font.font_impl_and_glyph_info(last_glyph.chr);
538            last_glyph.advance_width = glyph_info.advance_width;
539            last_glyph.font_impl_ascent = font_impl.map_or(0.0, |f| f.ascent());
540            last_glyph.font_impl_height = font_impl.map_or(0.0, |f| f.row_height());
541            last_glyph.uv_rect = glyph_info.uv_rect;
542            return;
543        }
544    }
545}
546
547/// Horizontally aligned the text on a row.
548///
549/// Ignores the Y coordinate.
550fn halign_and_justify_row(
551    point_scale: PointScale,
552    placed_row: &mut PlacedRow,
553    halign: Align,
554    wrap_width: f32,
555    justify: bool,
556) {
557    let row = Arc::make_mut(&mut placed_row.row);
558
559    if row.glyphs.is_empty() {
560        return;
561    }
562
563    let num_leading_spaces = row
564        .glyphs
565        .iter()
566        .take_while(|glyph| glyph.chr.is_whitespace())
567        .count();
568
569    let glyph_range = if num_leading_spaces == row.glyphs.len() {
570        // There is only whitespace
571        (0, row.glyphs.len())
572    } else {
573        let num_trailing_spaces = row
574            .glyphs
575            .iter()
576            .rev()
577            .take_while(|glyph| glyph.chr.is_whitespace())
578            .count();
579
580        (num_leading_spaces, row.glyphs.len() - num_trailing_spaces)
581    };
582    let num_glyphs_in_range = glyph_range.1 - glyph_range.0;
583    assert!(num_glyphs_in_range > 0, "Should have at least one glyph");
584
585    let original_min_x = row.glyphs[glyph_range.0].logical_rect().min.x;
586    let original_max_x = row.glyphs[glyph_range.1 - 1].logical_rect().max.x;
587    let original_width = original_max_x - original_min_x;
588
589    let target_width = if justify && num_glyphs_in_range > 1 {
590        wrap_width
591    } else {
592        original_width
593    };
594
595    let (target_min_x, target_max_x) = match halign {
596        Align::LEFT => (0.0, target_width),
597        Align::Center => (-target_width / 2.0, target_width / 2.0),
598        Align::RIGHT => (-target_width, 0.0),
599    };
600
601    let num_spaces_in_range = row.glyphs[glyph_range.0..glyph_range.1]
602        .iter()
603        .filter(|glyph| glyph.chr.is_whitespace())
604        .count();
605
606    let mut extra_x_per_glyph = if num_glyphs_in_range == 1 {
607        0.0
608    } else {
609        (target_width - original_width) / (num_glyphs_in_range as f32 - 1.0)
610    };
611    extra_x_per_glyph = extra_x_per_glyph.at_least(0.0); // Don't contract
612
613    let mut extra_x_per_space = 0.0;
614    if 0 < num_spaces_in_range && num_spaces_in_range < num_glyphs_in_range {
615        // Add an integral number of pixels between each glyph,
616        // and add the balance to the spaces:
617
618        extra_x_per_glyph = point_scale.floor_to_pixel(extra_x_per_glyph);
619
620        extra_x_per_space = (target_width
621            - original_width
622            - extra_x_per_glyph * (num_glyphs_in_range as f32 - 1.0))
623            / (num_spaces_in_range as f32);
624    }
625
626    placed_row.pos.x = point_scale.round_to_pixel(target_min_x);
627    let mut translate_x = -original_min_x - extra_x_per_glyph * glyph_range.0 as f32;
628
629    for glyph in &mut row.glyphs {
630        glyph.pos.x += translate_x;
631        glyph.pos.x = point_scale.round_to_pixel(glyph.pos.x);
632        translate_x += extra_x_per_glyph;
633        if glyph.chr.is_whitespace() {
634            translate_x += extra_x_per_space;
635        }
636    }
637
638    // Note we ignore the leading/trailing whitespace here!
639    row.size.x = target_max_x - target_min_x;
640}
641
642/// Calculate the Y positions and tessellate the text.
643fn galley_from_rows(
644    point_scale: PointScale,
645    job: Arc<LayoutJob>,
646    mut rows: Vec<PlacedRow>,
647    elided: bool,
648    intrinsic_size: Vec2,
649) -> Galley {
650    let mut first_row_min_height = job.first_row_min_height;
651    let mut cursor_y = 0.0;
652
653    for placed_row in &mut rows {
654        let mut max_row_height = first_row_min_height.at_least(placed_row.height());
655        let row = Arc::make_mut(&mut placed_row.row);
656
657        first_row_min_height = 0.0;
658        for glyph in &row.glyphs {
659            max_row_height = max_row_height.at_least(glyph.line_height);
660        }
661        max_row_height = point_scale.round_to_pixel(max_row_height);
662
663        // Now position each glyph vertically:
664        for glyph in &mut row.glyphs {
665            let format = &job.sections[glyph.section_index as usize].format;
666
667            glyph.pos.y = glyph.font_impl_ascent
668
669                // Apply valign to the different in height of the entire row, and the height of this `Font`:
670                + format.valign.to_factor() * (max_row_height - glyph.line_height)
671
672                // When mixing different `FontImpl` (e.g. latin and emojis),
673                // we always center the difference:
674                + 0.5 * (glyph.font_height - glyph.font_impl_height);
675
676            glyph.pos.y = point_scale.round_to_pixel(glyph.pos.y);
677        }
678
679        placed_row.pos.y = cursor_y;
680        row.size.y = max_row_height;
681
682        cursor_y += max_row_height;
683        cursor_y = point_scale.round_to_pixel(cursor_y); // TODO(emilk): it would be better to do the calculations in pixels instead.
684    }
685
686    let format_summary = format_summary(&job);
687
688    let mut rect = Rect::ZERO;
689    let mut mesh_bounds = Rect::NOTHING;
690    let mut num_vertices = 0;
691    let mut num_indices = 0;
692
693    for placed_row in &mut rows {
694        rect |= placed_row.rect();
695
696        let row = Arc::make_mut(&mut placed_row.row);
697        row.visuals = tessellate_row(point_scale, &job, &format_summary, row);
698
699        mesh_bounds |= row.visuals.mesh_bounds.translate(placed_row.pos.to_vec2());
700        num_vertices += row.visuals.mesh.vertices.len();
701        num_indices += row.visuals.mesh.indices.len();
702
703        row.section_index_at_start = u32::MAX; // No longer in use.
704        for glyph in &mut row.glyphs {
705            glyph.section_index = u32::MAX; // No longer in use.
706        }
707    }
708
709    let mut galley = Galley {
710        job,
711        rows,
712        elided,
713        rect,
714        mesh_bounds,
715        num_vertices,
716        num_indices,
717        pixels_per_point: point_scale.pixels_per_point,
718        intrinsic_size,
719    };
720
721    if galley.job.round_output_to_gui {
722        galley.round_output_to_gui();
723    }
724
725    galley
726}
727
728#[derive(Default)]
729struct FormatSummary {
730    any_background: bool,
731    any_underline: bool,
732    any_strikethrough: bool,
733}
734
735fn format_summary(job: &LayoutJob) -> FormatSummary {
736    let mut format_summary = FormatSummary::default();
737    for section in &job.sections {
738        format_summary.any_background |= section.format.background != Color32::TRANSPARENT;
739        format_summary.any_underline |= section.format.underline != Stroke::NONE;
740        format_summary.any_strikethrough |= section.format.strikethrough != Stroke::NONE;
741    }
742    format_summary
743}
744
745fn tessellate_row(
746    point_scale: PointScale,
747    job: &LayoutJob,
748    format_summary: &FormatSummary,
749    row: &Row,
750) -> RowVisuals {
751    if row.glyphs.is_empty() {
752        return Default::default();
753    }
754
755    let mut mesh = Mesh::default();
756
757    mesh.reserve_triangles(row.glyphs.len() * 2);
758    mesh.reserve_vertices(row.glyphs.len() * 4);
759
760    if format_summary.any_background {
761        add_row_backgrounds(point_scale, job, row, &mut mesh);
762    }
763
764    let glyph_index_start = mesh.indices.len();
765    let glyph_vertex_start = mesh.vertices.len();
766    tessellate_glyphs(point_scale, job, row, &mut mesh);
767    let glyph_vertex_end = mesh.vertices.len();
768
769    if format_summary.any_underline {
770        add_row_hline(point_scale, row, &mut mesh, |glyph| {
771            let format = &job.sections[glyph.section_index as usize].format;
772            let stroke = format.underline;
773            let y = glyph.logical_rect().bottom();
774            (stroke, y)
775        });
776    }
777
778    if format_summary.any_strikethrough {
779        add_row_hline(point_scale, row, &mut mesh, |glyph| {
780            let format = &job.sections[glyph.section_index as usize].format;
781            let stroke = format.strikethrough;
782            let y = glyph.logical_rect().center().y;
783            (stroke, y)
784        });
785    }
786
787    let mesh_bounds = mesh.calc_bounds();
788
789    RowVisuals {
790        mesh,
791        mesh_bounds,
792        glyph_index_start,
793        glyph_vertex_range: glyph_vertex_start..glyph_vertex_end,
794    }
795}
796
797/// Create background for glyphs that have them.
798/// Creates as few rectangular regions as possible.
799fn add_row_backgrounds(point_scale: PointScale, job: &LayoutJob, row: &Row, mesh: &mut Mesh) {
800    if row.glyphs.is_empty() {
801        return;
802    }
803
804    let mut end_run = |start: Option<(Color32, Rect, f32)>, stop_x: f32| {
805        if let Some((color, start_rect, expand)) = start {
806            let rect = Rect::from_min_max(start_rect.left_top(), pos2(stop_x, start_rect.bottom()));
807            let rect = rect.expand(expand);
808            let rect = rect.round_to_pixels(point_scale.pixels_per_point());
809            mesh.add_colored_rect(rect, color);
810        }
811    };
812
813    let mut run_start = None;
814    let mut last_rect = Rect::NAN;
815
816    for glyph in &row.glyphs {
817        let format = &job.sections[glyph.section_index as usize].format;
818        let color = format.background;
819        let rect = glyph.logical_rect();
820
821        if color == Color32::TRANSPARENT {
822            end_run(run_start.take(), last_rect.right());
823        } else if let Some((existing_color, start, expand)) = run_start {
824            if existing_color == color
825                && start.top() == rect.top()
826                && start.bottom() == rect.bottom()
827                && format.expand_bg == expand
828            {
829                // continue the same background rectangle
830            } else {
831                end_run(run_start.take(), last_rect.right());
832                run_start = Some((color, rect, format.expand_bg));
833            }
834        } else {
835            run_start = Some((color, rect, format.expand_bg));
836        }
837
838        last_rect = rect;
839    }
840
841    end_run(run_start.take(), last_rect.right());
842}
843
844fn tessellate_glyphs(point_scale: PointScale, job: &LayoutJob, row: &Row, mesh: &mut Mesh) {
845    for glyph in &row.glyphs {
846        let uv_rect = glyph.uv_rect;
847        if !uv_rect.is_nothing() {
848            let mut left_top = glyph.pos + uv_rect.offset;
849            left_top.x = point_scale.round_to_pixel(left_top.x);
850            left_top.y = point_scale.round_to_pixel(left_top.y);
851
852            let rect = Rect::from_min_max(left_top, left_top + uv_rect.size);
853            let uv = Rect::from_min_max(
854                pos2(uv_rect.min[0] as f32, uv_rect.min[1] as f32),
855                pos2(uv_rect.max[0] as f32, uv_rect.max[1] as f32),
856            );
857
858            let format = &job.sections[glyph.section_index as usize].format;
859
860            let color = format.color;
861
862            if format.italics {
863                let idx = mesh.vertices.len() as u32;
864                mesh.add_triangle(idx, idx + 1, idx + 2);
865                mesh.add_triangle(idx + 2, idx + 1, idx + 3);
866
867                let top_offset = rect.height() * 0.25 * Vec2::X;
868
869                mesh.vertices.push(Vertex {
870                    pos: rect.left_top() + top_offset,
871                    uv: uv.left_top(),
872                    color,
873                });
874                mesh.vertices.push(Vertex {
875                    pos: rect.right_top() + top_offset,
876                    uv: uv.right_top(),
877                    color,
878                });
879                mesh.vertices.push(Vertex {
880                    pos: rect.left_bottom(),
881                    uv: uv.left_bottom(),
882                    color,
883                });
884                mesh.vertices.push(Vertex {
885                    pos: rect.right_bottom(),
886                    uv: uv.right_bottom(),
887                    color,
888                });
889            } else {
890                mesh.add_rect_with_uv(rect, uv, color);
891            }
892        }
893    }
894}
895
896/// Add a horizontal line over a row of glyphs with a stroke and y decided by a callback.
897fn add_row_hline(
898    point_scale: PointScale,
899    row: &Row,
900    mesh: &mut Mesh,
901    stroke_and_y: impl Fn(&Glyph) -> (Stroke, f32),
902) {
903    let mut path = crate::tessellator::Path::default(); // reusing path to avoid re-allocations.
904
905    let mut end_line = |start: Option<(Stroke, Pos2)>, stop_x: f32| {
906        if let Some((stroke, start)) = start {
907            let stop = pos2(stop_x, start.y);
908            path.clear();
909            path.add_line_segment([start, stop]);
910            let feathering = 1.0 / point_scale.pixels_per_point();
911            path.stroke_open(feathering, &PathStroke::from(stroke), mesh);
912        }
913    };
914
915    let mut line_start = None;
916    let mut last_right_x = f32::NAN;
917
918    for glyph in &row.glyphs {
919        let (stroke, mut y) = stroke_and_y(glyph);
920        stroke.round_center_to_pixel(point_scale.pixels_per_point, &mut y);
921
922        if stroke.is_empty() {
923            end_line(line_start.take(), last_right_x);
924        } else if let Some((existing_stroke, start)) = line_start {
925            if existing_stroke == stroke && start.y == y {
926                // continue the same line
927            } else {
928                end_line(line_start.take(), last_right_x);
929                line_start = Some((stroke, pos2(glyph.pos.x, y)));
930            }
931        } else {
932            line_start = Some((stroke, pos2(glyph.pos.x, y)));
933        }
934
935        last_right_x = glyph.max_x();
936    }
937
938    end_line(line_start.take(), last_right_x);
939}
940
941// ----------------------------------------------------------------------------
942
943/// Keeps track of good places to break a long row of text.
944/// Will focus primarily on spaces, secondarily on things like `-`
945#[derive(Clone, Copy, Default)]
946struct RowBreakCandidates {
947    /// Breaking at ` ` or other whitespace
948    /// is always the primary candidate.
949    space: Option<usize>,
950
951    /// Logograms (single character representing a whole word) or kana (Japanese hiragana and katakana) are good candidates for line break.
952    cjk: Option<usize>,
953
954    /// Breaking anywhere before a CJK character is acceptable too.
955    pre_cjk: Option<usize>,
956
957    /// Breaking at a dash is a super-
958    /// good idea.
959    dash: Option<usize>,
960
961    /// This is nicer for things like URLs, e.g. www.
962    /// example.com.
963    punctuation: Option<usize>,
964
965    /// Breaking after just random character is some
966    /// times necessary.
967    any: Option<usize>,
968}
969
970impl RowBreakCandidates {
971    fn add(&mut self, index: usize, glyphs: &[Glyph]) {
972        let chr = glyphs[0].chr;
973        const NON_BREAKING_SPACE: char = '\u{A0}';
974        if chr.is_whitespace() && chr != NON_BREAKING_SPACE {
975            self.space = Some(index);
976        } else if is_cjk(chr) && (glyphs.len() == 1 || is_cjk_break_allowed(glyphs[1].chr)) {
977            self.cjk = Some(index);
978        } else if chr == '-' {
979            self.dash = Some(index);
980        } else if chr.is_ascii_punctuation() {
981            self.punctuation = Some(index);
982        } else if glyphs.len() > 1 && is_cjk(glyphs[1].chr) {
983            self.pre_cjk = Some(index);
984        }
985        self.any = Some(index);
986    }
987
988    fn word_boundary(&self) -> Option<usize> {
989        [self.space, self.cjk, self.pre_cjk]
990            .into_iter()
991            .max()
992            .flatten()
993    }
994
995    fn has_good_candidate(&self, break_anywhere: bool) -> bool {
996        if break_anywhere {
997            self.any.is_some()
998        } else {
999            self.word_boundary().is_some()
1000        }
1001    }
1002
1003    fn get(&self, break_anywhere: bool) -> Option<usize> {
1004        if break_anywhere {
1005            self.any
1006        } else {
1007            self.word_boundary()
1008                .or(self.dash)
1009                .or(self.punctuation)
1010                .or(self.any)
1011        }
1012    }
1013
1014    fn forget_before_idx(&mut self, index: usize) {
1015        let Self {
1016            space,
1017            cjk,
1018            pre_cjk,
1019            dash,
1020            punctuation,
1021            any,
1022        } = self;
1023        if space.is_some_and(|s| s < index) {
1024            *space = None;
1025        }
1026        if cjk.is_some_and(|s| s < index) {
1027            *cjk = None;
1028        }
1029        if pre_cjk.is_some_and(|s| s < index) {
1030            *pre_cjk = None;
1031        }
1032        if dash.is_some_and(|s| s < index) {
1033            *dash = None;
1034        }
1035        if punctuation.is_some_and(|s| s < index) {
1036            *punctuation = None;
1037        }
1038        if any.is_some_and(|s| s < index) {
1039            *any = None;
1040        }
1041    }
1042}
1043
1044#[inline]
1045fn is_cjk_ideograph(c: char) -> bool {
1046    ('\u{4E00}' <= c && c <= '\u{9FFF}')
1047        || ('\u{3400}' <= c && c <= '\u{4DBF}')
1048        || ('\u{2B740}' <= c && c <= '\u{2B81F}')
1049}
1050
1051#[inline]
1052fn is_kana(c: char) -> bool {
1053    ('\u{3040}' <= c && c <= '\u{309F}') // Hiragana block
1054        || ('\u{30A0}' <= c && c <= '\u{30FF}') // Katakana block
1055}
1056
1057#[inline]
1058fn is_cjk(c: char) -> bool {
1059    // TODO(bigfarts): Add support for Korean Hangul.
1060    is_cjk_ideograph(c) || is_kana(c)
1061}
1062
1063#[inline]
1064fn is_cjk_break_allowed(c: char) -> bool {
1065    // See: https://en.wikipedia.org/wiki/Line_breaking_rules_in_East_Asian_languages#Characters_not_permitted_on_the_start_of_a_line.
1066    !")]}〕〉》」』】〙〗〟'\"⦆»ヽヾーァィゥェォッャュョヮヵヶぁぃぅぇぉっゃゅょゎゕゖㇰㇱㇲㇳㇴㇵㇶㇷㇸㇹㇺㇻㇼㇽㇾㇿ々〻‐゠–〜?!‼⁇⁈⁉・、:;,。.".contains(c)
1067}
1068
1069// ----------------------------------------------------------------------------
1070
1071#[cfg(test)]
1072mod tests {
1073    use crate::AlphaFromCoverage;
1074
1075    use super::{super::*, *};
1076
1077    #[test]
1078    fn test_zero_max_width() {
1079        let mut fonts = FontsImpl::new(
1080            1.0,
1081            1024,
1082            AlphaFromCoverage::default(),
1083            FontDefinitions::default(),
1084        );
1085        let mut layout_job = LayoutJob::single_section("W".into(), TextFormat::default());
1086        layout_job.wrap.max_width = 0.0;
1087        let galley = layout(&mut fonts, layout_job.into());
1088        assert_eq!(galley.rows.len(), 1);
1089    }
1090
1091    #[test]
1092    fn test_truncate_with_newline() {
1093        // No matter where we wrap, we should be appending the newline character.
1094
1095        let mut fonts = FontsImpl::new(
1096            1.0,
1097            1024,
1098            AlphaFromCoverage::default(),
1099            FontDefinitions::default(),
1100        );
1101        let text_format = TextFormat {
1102            font_id: FontId::monospace(12.0),
1103            ..Default::default()
1104        };
1105
1106        for text in ["Hello\nworld", "\nfoo"] {
1107            for break_anywhere in [false, true] {
1108                for max_width in [0.0, 5.0, 10.0, 20.0, f32::INFINITY] {
1109                    let mut layout_job =
1110                        LayoutJob::single_section(text.into(), text_format.clone());
1111                    layout_job.wrap.max_width = max_width;
1112                    layout_job.wrap.max_rows = 1;
1113                    layout_job.wrap.break_anywhere = break_anywhere;
1114
1115                    let galley = layout(&mut fonts, layout_job.into());
1116
1117                    assert!(galley.elided);
1118                    assert_eq!(galley.rows.len(), 1);
1119                    let row_text = galley.rows[0].text();
1120                    assert!(
1121                        row_text.ends_with('…'),
1122                        "Expected row to end with `…`, got {row_text:?} when line-breaking the text {text:?} with max_width {max_width} and break_anywhere {break_anywhere}.",
1123                    );
1124                }
1125            }
1126        }
1127
1128        {
1129            let mut layout_job = LayoutJob::single_section("Hello\nworld".into(), text_format);
1130            layout_job.wrap.max_width = 50.0;
1131            layout_job.wrap.max_rows = 1;
1132            layout_job.wrap.break_anywhere = false;
1133
1134            let galley = layout(&mut fonts, layout_job.into());
1135
1136            assert!(galley.elided);
1137            assert_eq!(galley.rows.len(), 1);
1138            let row_text = galley.rows[0].text();
1139            assert_eq!(row_text, "Hello…");
1140        }
1141    }
1142
1143    #[test]
1144    fn test_cjk() {
1145        let mut fonts = FontsImpl::new(
1146            1.0,
1147            1024,
1148            AlphaFromCoverage::default(),
1149            FontDefinitions::default(),
1150        );
1151        let mut layout_job = LayoutJob::single_section(
1152            "日本語とEnglishの混在した文章".into(),
1153            TextFormat::default(),
1154        );
1155        layout_job.wrap.max_width = 90.0;
1156        let galley = layout(&mut fonts, layout_job.into());
1157        assert_eq!(
1158            galley.rows.iter().map(|row| row.text()).collect::<Vec<_>>(),
1159            vec!["日本語と", "Englishの混在", "した文章"]
1160        );
1161    }
1162
1163    #[test]
1164    fn test_pre_cjk() {
1165        let mut fonts = FontsImpl::new(
1166            1.0,
1167            1024,
1168            AlphaFromCoverage::default(),
1169            FontDefinitions::default(),
1170        );
1171        let mut layout_job = LayoutJob::single_section(
1172            "日本語とEnglishの混在した文章".into(),
1173            TextFormat::default(),
1174        );
1175        layout_job.wrap.max_width = 110.0;
1176        let galley = layout(&mut fonts, layout_job.into());
1177        assert_eq!(
1178            galley.rows.iter().map(|row| row.text()).collect::<Vec<_>>(),
1179            vec!["日本語とEnglish", "の混在した文章"]
1180        );
1181    }
1182
1183    #[test]
1184    fn test_truncate_width() {
1185        let mut fonts = FontsImpl::new(
1186            1.0,
1187            1024,
1188            AlphaFromCoverage::default(),
1189            FontDefinitions::default(),
1190        );
1191        let mut layout_job =
1192            LayoutJob::single_section("# DNA\nMore text".into(), TextFormat::default());
1193        layout_job.wrap.max_width = f32::INFINITY;
1194        layout_job.wrap.max_rows = 1;
1195        layout_job.round_output_to_gui = false;
1196        let galley = layout(&mut fonts, layout_job.into());
1197        assert!(galley.elided);
1198        assert_eq!(
1199            galley.rows.iter().map(|row| row.text()).collect::<Vec<_>>(),
1200            vec!["# DNA…"]
1201        );
1202        let row = &galley.rows[0];
1203        assert_eq!(row.pos, Pos2::ZERO);
1204        assert_eq!(row.rect().max.x, row.glyphs.last().unwrap().max_x());
1205    }
1206
1207    #[test]
1208    fn test_empty_row() {
1209        let mut fonts = FontsImpl::new(
1210            1.0,
1211            1024,
1212            AlphaFromCoverage::default(),
1213            FontDefinitions::default(),
1214        );
1215
1216        let font_id = FontId::default();
1217        let font_height = fonts.font(&font_id).row_height();
1218
1219        let job = LayoutJob::simple(String::new(), font_id, Color32::WHITE, f32::INFINITY);
1220
1221        let galley = layout(&mut fonts, job.into());
1222
1223        assert_eq!(galley.rows.len(), 1, "Expected one row");
1224        assert_eq!(
1225            galley.rows[0].row.glyphs.len(),
1226            0,
1227            "Expected no glyphs in the empty row"
1228        );
1229        assert_eq!(
1230            galley.size(),
1231            Vec2::new(0.0, font_height.round()),
1232            "Unexpected galley size"
1233        );
1234        assert_eq!(
1235            galley.intrinsic_size(),
1236            Vec2::new(0.0, font_height.round()),
1237            "Unexpected intrinsic size"
1238        );
1239    }
1240
1241    #[test]
1242    fn test_end_with_newline() {
1243        let mut fonts = FontsImpl::new(
1244            1.0,
1245            1024,
1246            AlphaFromCoverage::default(),
1247            FontDefinitions::default(),
1248        );
1249
1250        let font_id = FontId::default();
1251        let font_height = fonts.font(&font_id).row_height();
1252
1253        let job = LayoutJob::simple("Hi!\n".to_owned(), font_id, Color32::WHITE, f32::INFINITY);
1254
1255        let galley = layout(&mut fonts, job.into());
1256
1257        assert_eq!(galley.rows.len(), 2, "Expected two rows");
1258        assert_eq!(
1259            galley.rows[1].row.glyphs.len(),
1260            0,
1261            "Expected no glyphs in the empty row"
1262        );
1263        assert_eq!(
1264            galley.size().round(),
1265            Vec2::new(17.0, font_height.round() * 2.0),
1266            "Unexpected galley size"
1267        );
1268        assert_eq!(
1269            galley.intrinsic_size().round(),
1270            Vec2::new(17.0, font_height.round() * 2.0),
1271            "Unexpected intrinsic size"
1272        );
1273    }
1274}