Skip to main content

text_typeset/layout/
paragraph.rs

1use std::collections::{HashMap, HashSet};
2use std::ops::Range;
3use std::sync::OnceLock;
4
5use icu_segmenter::LineSegmenter;
6use icu_segmenter::options::LineBreakOptions;
7
8use crate::layout::line::{LayoutLine, PositionedRun, RunDecorations};
9use crate::shaping::run::{ShapedGlyph, ShapedRun};
10use crate::shaping::shaper::{FontMetricsPx, TextDirection};
11
12/// How [`break_into_lines`] should treat the order of the runs it is given.
13///
14/// The two layout paths differ here and getting it wrong reverses text
15/// twice. The single-line path runs the bidi algorithm itself and shapes
16/// in display order, so its runs must be left alone; the block path hands
17/// over logical-order runs tagged with embedding levels and needs each
18/// line reordered once the breaks are known.
19#[derive(Debug, Clone, Copy, PartialEq, Eq)]
20pub enum RunOrder {
21    /// Runs already arrive in visual order — do not reorder them.
22    AlreadyVisual,
23    /// Runs are in logical order; reorder each line per UAX #9 rule L2,
24    /// and resolve `Start`/`End` alignment against this base direction.
25    Logical(TextDirection),
26}
27
28/// Whether a break opportunity *must* be taken (LB4/LB5 hard line
29/// break) or *may* be taken (regular UAX #14 break opportunity).
30///
31/// `icu_segmenter::LineSegmenter` doesn't distinguish the two — it just
32/// emits byte offsets — so we classify each emitted offset ourselves by
33/// looking at the line-break property of the preceding code point.
34#[derive(Debug, Clone, Copy, PartialEq, Eq)]
35enum BreakOpportunity {
36    Allowed,
37    Mandatory,
38}
39
40/// Shared compiled-data line segmenter. `LineSegmenter::new_auto`
41/// returns a `LineSegmenterBorrowed<'static>` (Copy, statically-baked
42/// CLDR data), but constructing it still touches the option-parsing
43/// path — cache once to keep `break_into_lines` allocation-free.
44fn line_segmenter() -> icu_segmenter::LineSegmenterBorrowed<'static> {
45    static CELL: OnceLock<icu_segmenter::LineSegmenterBorrowed<'static>> = OnceLock::new();
46    *CELL.get_or_init(|| LineSegmenter::new_auto(LineBreakOptions::default()))
47}
48
49/// UAX #14 LB4/LB5: a break at `byte_offset` is mandatory iff the
50/// immediately-preceding code point is one of the hard line break
51/// characters (LF, CR, NEL, VT, FF, LS, PS). The CR+LF sequence is
52/// handled implicitly: the segmenter emits a single break after the
53/// LF, and the char before that offset is `\n` — mandatory.
54fn is_mandatory_break_at(text: &str, byte_offset: usize) -> bool {
55    if byte_offset == 0 {
56        return false;
57    }
58    let preceding = &text[..byte_offset];
59    preceding
60        .chars()
61        .next_back()
62        .is_some_and(crate::types::is_hard_break)
63}
64
65/// Enumerate UAX #14 break opportunities in `text` and classify each
66/// as `Allowed` or `Mandatory`. Replaces the previous
67/// `unicode_linebreak::linebreaks(text)` call site one-to-one.
68fn enumerate_breaks(text: &str) -> Vec<(usize, BreakOpportunity)> {
69    line_segmenter()
70        .segment_str(text)
71        .map(|byte_offset| {
72            let kind = if is_mandatory_break_at(text, byte_offset) {
73                BreakOpportunity::Mandatory
74            } else {
75                BreakOpportunity::Allowed
76            };
77            (byte_offset, kind)
78        })
79        .collect()
80}
81
82/// Byte offsets in `text` where a hyphenated line break may occur and a
83/// hyphen glyph should be rendered: Knuth-Liang dictionary points inside
84/// words (in `lang_code`, an ISO 639-1 code) plus soft-hyphen (U+00AD)
85/// positions.
86///
87/// Returned offsets are "break before this byte" positions, matching the
88/// UAX #14 offsets from [`enumerate_breaks`]. Soft hyphens are honored
89/// regardless of language; dictionary breaks apply only when the
90/// language's patterns are compiled in (`hypher::Lang::from_iso` resolves
91/// it) — otherwise it gracefully degrades to soft-hyphen-only.
92fn hyphenation_breaks(text: &str, lang_code: [u8; 2]) -> Vec<usize> {
93    use hypher::hyphenate;
94
95    let mut offsets = Vec::new();
96
97    // Soft hyphens: break after the U+00AD so the hyphen renders at line end.
98    for (idx, ch) in text.char_indices() {
99        if ch == '\u{00AD}' {
100            offsets.push(idx + ch.len_utf8());
101        }
102    }
103
104    // Dictionary hyphenation, word by word — only if the language resolves.
105    if let Some(lang) = hypher::Lang::from_iso(lang_code) {
106        let mut word_start: Option<usize> = None;
107        let flush = |start: usize, end: usize, offsets: &mut Vec<usize>| {
108            let word = &text[start..end];
109            // Skip trivially short words; `hyphenate` would yield no interior
110            // breaks anyway, and this avoids the call overhead.
111            if word.chars().count() < 5 {
112                return;
113            }
114            let mut pos = start;
115            let mut syllables = hyphenate(word, lang).peekable();
116            while let Some(syl) = syllables.next() {
117                pos += syl.len();
118                // A break sits between syllables, not after the last one.
119                if syllables.peek().is_some() {
120                    offsets.push(pos);
121                }
122            }
123        };
124        for (idx, ch) in text.char_indices() {
125            if ch.is_alphabetic() {
126                word_start.get_or_insert(idx);
127            } else if let Some(start) = word_start.take() {
128                flush(start, idx, &mut offsets);
129            }
130        }
131        if let Some(start) = word_start.take() {
132            flush(start, text.len(), &mut offsets);
133        }
134    }
135
136    offsets.sort_unstable();
137    offsets.dedup();
138    offsets
139}
140
141/// Map hyphenation byte offsets to glyph indices (first glyph whose
142/// cluster is `>=` the offset), mirroring [`map_breaks_to_glyph_indices`].
143fn map_offsets_to_glyph_indices(flat: &[FlatGlyph], offsets: &[usize]) -> HashSet<usize> {
144    let mut set = HashSet::new();
145    let mut cursor = 0usize;
146    for &byte_offset in offsets {
147        while cursor < flat.len() && (flat[cursor].cluster as usize) < byte_offset {
148            cursor += 1;
149        }
150        set.insert(cursor.min(flat.len()));
151    }
152    set
153}
154
155/// Append a rendered hyphen glyph to the end of a line that broke at a
156/// hyphenation point, accounting for its advance in the run and line
157/// widths. The hyphen inherits the last glyph's cluster so caret/hit
158/// math treats it as part of the final character.
159fn append_hyphen(line: &mut LayoutLine, hyphen: &ShapedGlyph) {
160    if let Some(run) = line.runs.last_mut() {
161        let mut g = hyphen.clone();
162        g.cluster = run
163            .shaped_run
164            .glyphs
165            .last()
166            .map(|gl| gl.cluster)
167            .unwrap_or(0);
168        run.shaped_run.glyphs.push(g);
169        run.shaped_run.advance_width += hyphen.x_advance;
170        line.width += hyphen.x_advance;
171    }
172}
173
174/// Convert a byte offset within a UTF-8 string to a char offset.
175///
176/// Clamps to `text.len()` and rounds down to the nearest char boundary
177/// if `byte_offset` lands inside a multi-byte character. HarfBuzz can
178/// emit cluster values that don't coincide with UTF-8 char boundaries
179/// (ligature splits, fallback shaping), so callers must never assume
180/// cluster values are well-aligned.
181fn byte_offset_to_char_offset(text: &str, byte_offset: usize) -> usize {
182    let mut off = byte_offset.min(text.len());
183    while off > 0 && !text.is_char_boundary(off) {
184        off -= 1;
185    }
186    text[..off].chars().count()
187}
188
189/// Everything line wrapping needs to hyphenate: the pre-shaped hyphen
190/// glyph to append at a break and the ISO 639-1 language for the
191/// dictionary. Passed as `Some` only when hyphenation is enabled.
192pub struct Hyphenator {
193    /// Hyphen (`-`) glyph in the run's font, appended at hyphenated breaks.
194    pub glyph: ShapedGlyph,
195    /// ISO 639-1 language code for the Knuth-Liang dictionary.
196    pub language: [u8; 2],
197}
198
199/// Text alignment within a line.
200///
201/// `Left`/`Right` are absolute; `Start`/`End` are relative to the
202/// paragraph's base direction and are what an *unset* alignment should
203/// use. Keeping both lets a writer who explicitly chose "flush left" keep
204/// that in an RTL paragraph, while a paragraph nobody has aligned simply
205/// follows its own direction.
206#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
207pub enum Alignment {
208    /// Leading edge: left in an LTR paragraph, right in an RTL one.
209    #[default]
210    Start,
211    /// Trailing edge: right in an LTR paragraph, left in an RTL one.
212    End,
213    Left,
214    Right,
215    Center,
216    Justify,
217}
218
219impl Alignment {
220    /// Resolve the direction-relative variants against a base direction.
221    ///
222    /// Always returns an absolute alignment, so line layout never has to
223    /// think about direction again.
224    pub fn resolve_for(self, base: TextDirection) -> Alignment {
225        let rtl = base == TextDirection::RightToLeft;
226        match self {
227            Alignment::Start if rtl => Alignment::Right,
228            Alignment::Start => Alignment::Left,
229            Alignment::End if rtl => Alignment::Left,
230            Alignment::End => Alignment::Right,
231            absolute => absolute,
232        }
233    }
234}
235
236/// Put a line's runs into visual order per UAX #9 rule L2, then re-lay
237/// their x positions left to right.
238///
239/// Line breaking is a logical operation and runs arrive in logical order,
240/// so this is where a mixed-direction line finally becomes visual. It has
241/// to run per line rather than per paragraph: reordering a paragraph
242/// before breaking it would let a wrap point fall in the middle of an
243/// already-reversed span and scramble every line after it.
244///
245/// The runs keep their glyphs untouched — harfrust already emitted those
246/// in visual order within each run. Only the runs' relative order and
247/// their x origins change.
248fn reorder_line_visually(line: &mut LayoutLine) {
249    if line.runs.len() < 2 {
250        return;
251    }
252    // Cheap scan before any allocation: with nothing right-to-left on
253    // the line there is nothing for rule L2 to reverse, and that is
254    // every line of an ordinary Latin document. Building the level and
255    // permutation vectors first would allocate twice per line on every
256    // relayout just to conclude the same thing.
257    if line.runs.iter().all(|r| r.shaped_run.bidi_level % 2 == 0) {
258        return;
259    }
260
261    let levels: Vec<u8> = line.runs.iter().map(|r| r.shaped_run.bidi_level).collect();
262
263    let order = crate::shaping::shaper::visual_order(&levels);
264    if order.iter().copied().eq(0..order.len()) {
265        return; // already visual — the common all-LTR case
266    }
267
268    // The line's left edge, which `build_line` set to the first-line
269    // indent. Re-laying from here keeps the indent intact.
270    let origin = line.runs.iter().map(|r| r.x).fold(f32::INFINITY, f32::min);
271
272    let mut reordered: Vec<crate::layout::line::PositionedRun> = Vec::with_capacity(order.len());
273    let mut taken: Vec<Option<crate::layout::line::PositionedRun>> =
274        line.runs.drain(..).map(Some).collect();
275    for logical_idx in order {
276        if let Some(run) = taken[logical_idx].take() {
277            reordered.push(run);
278        }
279    }
280
281    let mut x = origin;
282    for run in &mut reordered {
283        run.x = x;
284        x += run.shaped_run.advance_width;
285    }
286    line.runs = reordered;
287}
288
289/// Break shaped runs into lines that fit within `available_width`.
290///
291/// Strategy: shape-first-then-break.
292/// 1. The caller has already shaped the full paragraph into one or more ShapedRuns.
293/// 2. We use unicode-linebreak to find break opportunities in the original text.
294/// 3. We map break positions to glyph boundaries via cluster values.
295/// 4. Greedy line wrapping: accumulate glyph advances, break at the last
296///    allowed opportunity before exceeding the width.
297/// 5. Apply alignment per line.
298#[allow(clippy::too_many_arguments)]
299pub fn break_into_lines(
300    runs: Vec<ShapedRun>,
301    text: &str,
302    available_width: f32,
303    alignment: Alignment,
304    first_line_indent: f32,
305    metrics: &FontMetricsPx,
306    hyphenator: Option<Hyphenator>,
307    run_order: RunOrder,
308) -> Vec<LayoutLine> {
309    // Where a glyph-less line puts the caret. The alignment pass below only
310    // moves runs, so an empty line must carry this explicitly.
311    let empty_caret_x = {
312        let base = match run_order {
313            RunOrder::Logical(base) => base,
314            RunOrder::AlreadyVisual => TextDirection::LeftToRight,
315        };
316        empty_line_caret_x(alignment, base, first_line_indent, available_width)
317    };
318
319    if runs.is_empty() || text.is_empty() {
320        // Empty paragraph: produce one empty line for the block to have height
321        return vec![make_empty_line(metrics, 0..0, empty_caret_x)];
322    }
323
324    // Flatten all glyphs into a single sequence with their run association, in
325    // logical order when the runs come in logical order (see `flatten_runs`).
326    let flat = flatten_runs(&runs, matches!(run_order, RunOrder::Logical(_)));
327    if flat.is_empty() {
328        return vec![make_empty_line(metrics, 0..0, empty_caret_x)];
329    }
330
331    // Get UAX #14 break opportunities (byte offsets in text), each
332    // classified as Allowed or Mandatory.
333    let breaks: Vec<(usize, BreakOpportunity)> = enumerate_breaks(text);
334
335    // Build sets of allowed and mandatory break positions (glyph indices)
336    let (break_points, mandatory_breaks) = map_breaks_to_glyph_indices(&flat, &breaks);
337
338    // Hyphenation break candidates (glyph indices). A break here needs a
339    // trailing hyphen glyph and must reserve its advance in the fit check.
340    let hyphen_points = if let Some(h) = &hyphenator {
341        map_offsets_to_glyph_indices(&flat, &hyphenation_breaks(text, h.language))
342    } else {
343        HashSet::new()
344    };
345    let hyphen_adv = hyphenator
346        .as_ref()
347        .map(|h| h.glyph.x_advance)
348        .unwrap_or(0.0);
349
350    // Greedy line wrapping
351    let mut lines = Vec::new();
352    // Whether each line ends at a hard break, which justification leaves alone.
353    let mut hard_ends: Vec<bool> = Vec::new();
354    let mut line_start_glyph = 0usize;
355    let mut line_width = 0.0f32;
356    // Last break opportunity within the current line: (glyph index, whether
357    // breaking there renders a hyphen).
358    let mut last_break: Option<(usize, bool)> = None;
359    // First line may be indented; subsequent lines use full width
360    let mut effective_width = available_width - first_line_indent;
361
362    for i in 0..flat.len() {
363        let glyph_advance = flat[i].x_advance;
364        line_width += glyph_advance;
365
366        // Check for mandatory break — O(1) lookup — and where it falls in the text.
367        let mandatory_at = mandatory_breaks.get(&(i + 1)).copied();
368        let is_mandatory = mandatory_at.is_some();
369
370        let exceeds_width = line_width > effective_width && line_start_glyph < i;
371
372        if is_mandatory || exceeds_width {
373            let (break_at, needs_hyphen) = if is_mandatory {
374                (i + 1, false)
375            } else if let Some((bp, hy)) = last_break {
376                if bp > line_start_glyph {
377                    (bp, hy)
378                } else {
379                    (i + 1, false) // emergency break -no opportunity found
380                }
381            } else {
382                (i + 1, false) // emergency break -no break opportunities at all
383            };
384
385            let indent = if lines.is_empty() {
386                first_line_indent
387            } else {
388                0.0
389            };
390            let mut line = build_line(
391                &runs,
392                &flat,
393                line_start_glyph,
394                break_at,
395                metrics,
396                indent,
397                text,
398                if is_mandatory { mandatory_at } else { None },
399            );
400            if needs_hyphen && let Some(h) = &hyphenator {
401                append_hyphen(&mut line, &h.glyph);
402            }
403            lines.push(line);
404            hard_ends.push(is_mandatory);
405
406            line_start_glyph = break_at;
407            // Subsequent lines use full available width
408            effective_width = available_width;
409            // Re-accumulate width for glyphs already scanned past the break
410            line_width = 0.0;
411            for j in break_at..=i {
412                if j < flat.len() {
413                    line_width += flat[j].x_advance;
414                }
415            }
416            last_break = None;
417        }
418
419        // Update the break opportunity AFTER the width check so that a break
420        // discovered at this glyph does not clobber the previous one when the
421        // width is already exceeded. Hyphenation points are checked first so
422        // a soft hyphen (which is also a UAX #14 opportunity) renders its
423        // hyphen; they only count when the hyphen itself still fits.
424        let at = i + 1;
425        if hyphen_points.contains(&at) && line_width + hyphen_adv <= effective_width {
426            last_break = Some((at, true));
427        } else if break_points.contains(&at) {
428            last_break = Some((at, false));
429        }
430    }
431
432    // Remaining glyphs form the last line
433    if line_start_glyph < flat.len() {
434        let line = build_line(
435            &runs,
436            &flat,
437            line_start_glyph,
438            flat.len(),
439            metrics,
440            if lines.is_empty() {
441                first_line_indent
442            } else {
443                0.0
444            },
445            text,
446            None,
447        );
448        lines.push(line);
449        hard_ends.push(false);
450    }
451
452    // A hard break at the very end starts a line of its own, empty, where the
453    // caret goes after Shift+Enter at the end of a paragraph: without it the
454    // caret stayed at the end of the line it had just left, and the paragraph
455    // a line short.
456    if text
457        .chars()
458        .next_back()
459        .is_some_and(crate::types::is_hard_break)
460    {
461        let end = byte_offset_to_char_offset(text, text.len());
462        let base = match run_order {
463            RunOrder::Logical(base) => base,
464            RunOrder::AlreadyVisual => TextDirection::LeftToRight,
465        };
466        let caret_x = empty_line_caret_x(alignment, base, 0.0, available_width);
467        lines.push(make_empty_line(metrics, end..end, caret_x));
468        hard_ends.push(false);
469    }
470
471    // Put each line's runs into visual order before anything reads their
472    // x positions. Alignment shifts every run by the same amount so it
473    // does not care about order, but `justify_line` re-lays runs
474    // sequentially from the vector and would otherwise justify a
475    // mixed-direction line in logical order.
476    let base_direction = match run_order {
477        RunOrder::Logical(base) => {
478            for line in &mut lines {
479                reorder_line_visually(line);
480            }
481            base
482        }
483        // Already visual: reordering here would reverse the caller's work.
484        RunOrder::AlreadyVisual => TextDirection::LeftToRight,
485    };
486
487    // Apply alignment. An unset alignment follows the paragraph's base
488    // direction, so an RTL paragraph right-aligns without the host having
489    // to translate direction into alignment itself.
490    let alignment = alignment.resolve_for(base_direction);
491    let rtl_paragraph = base_direction == TextDirection::RightToLeft;
492    let effective_width = available_width;
493    let last_idx = lines.len().saturating_sub(1);
494    for (i, line) in lines.iter_mut().enumerate() {
495        let indent = if i == 0 { first_line_indent } else { 0.0 };
496        // A first-line indent insets from the paragraph's *leading* edge,
497        // which in an RTL paragraph is the right one. `build_line` always
498        // insets from the left, so undo that here and let the narrowed
499        // `line_avail` below carry the inset over to the right instead.
500        if rtl_paragraph && indent != 0.0 {
501            for run in &mut line.runs {
502                run.x -= indent;
503            }
504        }
505        let line_avail = effective_width - indent;
506        match alignment {
507            // `resolve_for` maps these onto Left/Right, so they cannot
508            // reach here — but fail soft rather than panicking in a
509            // layout pass that runs on every keystroke.
510            Alignment::Start | Alignment::End | Alignment::Left => {
511                // Runs already sit at the indent, except in an RTL
512                // paragraph where the block above moved them to 0 so the
513                // inset could go to the trailing edge. An explicit Left
514                // means the writer wants flush-left text, and the indent
515                // still belongs on the paragraph's leading edge, so put
516                // it back.
517                if rtl_paragraph && indent != 0.0 {
518                    for run in &mut line.runs {
519                        run.x += indent;
520                    }
521                }
522            }
523            Alignment::Right => {
524                let shift = (line_avail - line.width).max(0.0);
525                for run in &mut line.runs {
526                    run.x += shift;
527                }
528            }
529            Alignment::Center => {
530                let shift = ((line_avail - line.width) / 2.0).max(0.0);
531                for run in &mut line.runs {
532                    run.x += shift;
533                }
534            }
535            Alignment::Justify => {
536                // Don't justify the last line, nor one a hard break ends: a
537                // line of verse or of a letter set apart by Shift+Enter keeps
538                // its words where they are, as a browser and Typst set it.
539                if i < last_idx && !hard_ends[i] && line.width > 0.0 {
540                    justify_line(line, line_avail, text);
541                }
542            }
543        }
544    }
545
546    if lines.is_empty() {
547        lines.push(make_empty_line(metrics, 0..0, empty_caret_x));
548    }
549
550    // Convert glyph cluster values from byte offsets to char offsets.
551    // This must happen AFTER alignment because justify_line needs byte
552    // offsets to find space characters in the original text.
553    for line in &mut lines {
554        for run in &mut line.runs {
555            for glyph in &mut run.shaped_run.glyphs {
556                glyph.cluster = byte_offset_to_char_offset(text, glyph.cluster as usize) as u32;
557            }
558        }
559    }
560
561    lines
562}
563
564/// A flattened glyph with enough info to map back to runs.
565struct FlatGlyph {
566    x_advance: f32,
567    cluster: u32,
568    run_index: usize,
569    glyph_index_in_run: usize,
570}
571
572/// The glyphs of `runs` as one sequence, each with its run and its index in it.
573///
574/// With `logical`, the runs arrive in logical order and so does the sequence: a
575/// right-to-left run's glyphs, which shaping stores in visual order (its last
576/// character first), are walked from its end. Line breaking reads the sequence as the
577/// text runs, so walked visually such a run was broken from its logical end: a wrapped
578/// right-to-left paragraph set its last words on its first line, and a break inside
579/// one (a line separator, which stays in the run it sits in) mapped to its first
580/// glyph and was never taken. A line still takes a contiguous slice of each run's
581/// glyphs, since the logical stretch of a run is a contiguous stretch of it visually.
582fn flatten_runs(runs: &[ShapedRun], logical: bool) -> Vec<FlatGlyph> {
583    let mut flat = Vec::new();
584    for (run_idx, run) in runs.iter().enumerate() {
585        // Offset cluster values from fragment-text space to block-text space.
586        // rustybuzz assigns clusters as byte offsets within the fragment text (0-based),
587        // but unicode-linebreak returns byte offsets in the full block text.
588        let cluster_offset = run.text_range.start as u32;
589        let push = |flat: &mut Vec<FlatGlyph>, glyph_idx: usize| {
590            flat.push(FlatGlyph {
591                x_advance: run.glyphs[glyph_idx].x_advance,
592                cluster: run.glyphs[glyph_idx].cluster + cluster_offset,
593                run_index: run_idx,
594                glyph_index_in_run: glyph_idx,
595            });
596        };
597        if logical && run.direction == TextDirection::RightToLeft {
598            for glyph_idx in (0..run.glyphs.len()).rev() {
599                push(&mut flat, glyph_idx);
600            }
601        } else {
602            for glyph_idx in 0..run.glyphs.len() {
603                push(&mut flat, glyph_idx);
604            }
605        }
606    }
607    flat
608}
609
610/// Map unicode-linebreak byte offsets to glyph indices using a merged walk.
611/// Both `flat` (by cluster) and `breaks` (by byte offset) are sorted,
612/// so a single O(b + m) pass replaces the previous O(b × m) approach.
613///
614/// Returns (break_points: HashSet<glyph_idx>, mandatory_breaks: glyph_idx → the byte
615/// offset of the break in the text).
616fn map_breaks_to_glyph_indices(
617    flat: &[FlatGlyph],
618    breaks: &[(usize, BreakOpportunity)],
619) -> (HashSet<usize>, HashMap<usize, usize>) {
620    let mut break_points = HashSet::new();
621    let mut mandatory_breaks = HashMap::new();
622    let mut glyph_cursor = 0usize;
623
624    for &(byte_offset, opportunity) in breaks {
625        // Advance glyph cursor to the first glyph whose cluster >= byte_offset
626        while glyph_cursor < flat.len() && (flat[glyph_cursor].cluster as usize) < byte_offset {
627            glyph_cursor += 1;
628        }
629        let glyph_idx = if glyph_cursor < flat.len() {
630            glyph_cursor
631        } else {
632            flat.len()
633        };
634        break_points.insert(glyph_idx);
635        if opportunity == BreakOpportunity::Mandatory {
636            mandatory_breaks.insert(glyph_idx, byte_offset);
637        }
638    }
639
640    (break_points, mandatory_breaks)
641}
642
643/// Build a LayoutLine from a glyph range within the flat sequence.
644///
645/// `hard_end` is where a hard break the line ends at falls in the text, the byte
646/// after the break: the line's text ends there. Read from the next glyph instead, it
647/// overshot into the next line when that one opens with a right-to-left run, whose
648/// first glyph carries its *last* cluster, and the break was lost.
649#[allow(clippy::too_many_arguments)]
650fn build_line(
651    runs: &[ShapedRun],
652    flat: &[FlatGlyph],
653    start: usize,
654    end: usize,
655    metrics: &FontMetricsPx,
656    indent: f32,
657    text: &str,
658    hard_end: Option<usize>,
659) -> LayoutLine {
660    // Group consecutive glyphs by run_index to reconstruct PositionedRuns. A group is
661    // a contiguous slice of its run's glyphs, walked forwards, or backwards for a
662    // right-to-left run laid out in logical order (see `flatten_runs`), so its slice is
663    // the span of the indices it holds.
664    let mut positioned_runs = Vec::new();
665    let mut x = indent;
666    let mut i = start;
667    while i < end {
668        let run_idx = flat[i].run_index;
669        let (mut lo, mut hi) = (flat[i].glyph_index_in_run, flat[i].glyph_index_in_run);
670        let mut j = i + 1;
671        while j < end && flat[j].run_index == run_idx {
672            lo = lo.min(flat[j].glyph_index_in_run);
673            hi = hi.max(flat[j].glyph_index_in_run);
674            j += 1;
675        }
676        if let Some((pr, advance)) = extract_sub_run(runs, run_idx, lo, hi + 1) {
677            positioned_runs.push(PositionedRun {
678                decorations: RunDecorations {
679                    underline_style: pr.underline_style,
680                    overline: pr.overline,
681                    strikeout: pr.strikeout,
682                    is_link: pr.is_link,
683                    foreground_color: pr.foreground_color,
684                    underline_color: pr.underline_color,
685                    background_color: pr.background_color,
686                    anchor_href: pr.anchor_href.clone(),
687                    tooltip: pr.tooltip.clone(),
688                    vertical_alignment: pr.vertical_alignment,
689                },
690                shaped_run: pr,
691                x,
692            });
693            x += advance;
694        }
695        i = j;
696    }
697
698    let width = x - indent;
699
700    // Compute char range from cluster values.
701    // Clusters from rustybuzz are byte offsets — convert to char offsets
702    // so that positions match text-document's character-based coordinates.
703    //
704    // Glyphs are in *visual* order, so for an RTL run `flat[start]` holds
705    // the largest cluster and `flat[end-1]` the smallest. Take the min/max
706    // over the line's glyphs instead of trusting the array ends, so the
707    // logical range is correct for both directions.
708    let byte_start = flat[start..end.min(flat.len())]
709        .iter()
710        .map(|g| g.cluster as usize)
711        .min()
712        .unwrap_or(0);
713    let byte_end = if let Some(hard_end) = hard_end {
714        hard_end
715    } else if end >= flat.len() {
716        // Last glyph reaches the end of the input text. Always snap to the
717        // full length: a trailing ligature glyph may cover several source
718        // chars, so `max_cluster + 1` would be wrong.
719        text.len()
720    } else {
721        // Next visual glyph's cluster bounds an LTR line exactly; for a
722        // wrapped RTL line take whichever is larger so the logical end
723        // still covers the line's highest cluster.
724        let line_max = flat[start..end]
725            .iter()
726            .map(|g| g.cluster as usize)
727            .max()
728            .unwrap_or(0);
729        (flat[end].cluster as usize).max(line_max)
730    };
731    let char_start = byte_offset_to_char_offset(text, byte_start);
732    let char_end = byte_offset_to_char_offset(text, byte_end);
733    let hard_break_chars = match text
734        .get(byte_start..byte_end)
735        .and_then(crate::types::LineEnd::hard_break_ending)
736    {
737        Some(crate::types::LineEnd::HardBreak { chars, .. }) => chars as usize,
738        _ => 0,
739    };
740
741    // Expand line height for inline images taller than the font ascent
742    let mut ascent = metrics.ascent;
743    for run in &positioned_runs {
744        if run.shaped_run.image_name.is_some() && run.shaped_run.image_height > ascent {
745            ascent = run.shaped_run.image_height;
746        }
747    }
748    let line_height = ascent + metrics.descent + metrics.leading;
749
750    LayoutLine {
751        runs: positioned_runs,
752        y: 0.0, // will be set by the caller (block layout)
753        ascent,
754        descent: metrics.descent,
755        leading: metrics.leading,
756        width,
757        char_range: char_start..char_end,
758        line_height,
759        // Degenerate fallback only: a built line normally derives caret
760        // positions from its runs, but if every run came out glyph-less
761        // the caret still has the line's start to sit at.
762        empty_caret_x: indent,
763        hard_break_chars,
764    }
765}
766
767/// Extract a sub-run (slice of glyphs) from a ShapedRun.
768/// Cluster values are offset to block-text space (adding text_range.start).
769fn extract_sub_run(
770    runs: &[ShapedRun],
771    run_index: usize,
772    glyph_start: usize,
773    glyph_end: usize,
774) -> Option<(ShapedRun, f32)> {
775    let run = &runs[run_index];
776    let end = glyph_end.min(run.glyphs.len());
777    if glyph_start >= end {
778        return None;
779    }
780    let cluster_offset = run.text_range.start as u32;
781    let mut sub_glyphs = run.glyphs[glyph_start..end].to_vec();
782    // Offset cluster values from fragment-local to block-text space
783    for g in &mut sub_glyphs {
784        g.cluster += cluster_offset;
785    }
786    let advance: f32 = sub_glyphs.iter().map(|g| g.x_advance).sum();
787
788    let sub_run = ShapedRun {
789        font_face_id: run.font_face_id,
790        size_px: run.size_px,
791        weight: run.weight,
792        italic: run.italic,
793        glyphs: sub_glyphs,
794        advance_width: advance,
795        text_range: run.text_range.clone(),
796        direction: run.direction,
797        bidi_level: run.bidi_level,
798        underline_style: run.underline_style,
799        overline: run.overline,
800        strikeout: run.strikeout,
801        is_link: run.is_link,
802        foreground_color: run.foreground_color,
803        underline_color: run.underline_color,
804        background_color: run.background_color,
805        anchor_href: run.anchor_href.clone(),
806        tooltip: run.tooltip.clone(),
807        vertical_alignment: run.vertical_alignment,
808        image_name: run.image_name.clone(),
809        image_height: run.image_height,
810    };
811    Some((sub_run, advance))
812}
813
814fn make_empty_line(
815    metrics: &FontMetricsPx,
816    char_range: Range<usize>,
817    empty_caret_x: f32,
818) -> LayoutLine {
819    LayoutLine {
820        runs: Vec::new(),
821        y: 0.0,
822        ascent: metrics.ascent,
823        descent: metrics.descent,
824        leading: metrics.leading,
825        width: 0.0,
826        char_range,
827        line_height: metrics.ascent + metrics.descent + metrics.leading,
828        empty_caret_x,
829        hard_break_chars: 0,
830    }
831}
832
833/// The x where the caret sits on a line with no glyphs — i.e. where the
834/// first typed character's glyph would land. Mirrors the run-shifting
835/// arithmetic of `break_into_lines`' alignment pass with a line width of
836/// zero, so an empty paragraph's caret cannot disagree with where the
837/// first keystroke lays text out (the "caret jumps on the first
838/// character" bug).
839fn empty_line_caret_x(
840    alignment: Alignment,
841    base_direction: TextDirection,
842    first_line_indent: f32,
843    available_width: f32,
844) -> f32 {
845    let rtl = base_direction == TextDirection::RightToLeft;
846    let indent = first_line_indent;
847    let line_avail = (available_width - indent).max(0.0);
848    match alignment.resolve_for(base_direction) {
849        // In an RTL paragraph the alignment pass first moves runs to the
850        // left edge so the indent insets from the *right*; Right then
851        // shifts by the remaining width. Width zero leaves the caret at
852        // `line_avail` (RTL) or the full width (LTR).
853        Alignment::Right => {
854            if rtl {
855                line_avail
856            } else {
857                available_width
858            }
859        }
860        Alignment::Center => {
861            let shift = line_avail / 2.0;
862            if rtl { shift } else { indent + shift }
863        }
864        // Justify never justifies the last line, and a lone line is the
865        // last line, so runs keep their unshifted positions: the indent
866        // for LTR; the left edge for RTL, where the alignment pass moved
867        // them and Justify does not put the indent back.
868        Alignment::Justify => {
869            if rtl {
870                0.0
871            } else {
872                indent
873            }
874        }
875        // `resolve_for` maps Start/End onto Left/Right, so what remains is
876        // Left — which keeps runs at the indent in both directions.
877        _ => indent,
878    }
879}
880
881/// Distribute extra space among word gaps for justification.
882///
883/// Finds space glyphs (cluster mapping to ' ') across all runs and
884/// increases their x_advance proportionally. Then recomputes run x positions.
885fn justify_line(line: &mut LayoutLine, target_width: f32, text: &str) {
886    let extra = target_width - line.width;
887    if extra <= 0.0 {
888        return;
889    }
890
891    // Count space glyphs across all runs
892    let mut space_count = 0usize;
893    for run in &line.runs {
894        for glyph in &run.shaped_run.glyphs {
895            let byte_offset = glyph.cluster as usize;
896            if let Some(ch) = text.get(byte_offset..).and_then(|s| s.chars().next())
897                && ch == ' '
898            {
899                space_count += 1;
900            }
901        }
902    }
903
904    if space_count == 0 {
905        return;
906    }
907
908    let extra_per_space = extra / space_count as f32;
909
910    // Increase x_advance of space glyphs
911    for run in &mut line.runs {
912        for glyph in &mut run.shaped_run.glyphs {
913            let byte_offset = glyph.cluster as usize;
914            if let Some(ch) = text.get(byte_offset..).and_then(|s| s.chars().next())
915                && ch == ' '
916            {
917                glyph.x_advance += extra_per_space;
918            }
919        }
920        // Recompute run advance width
921        run.shaped_run.advance_width = run.shaped_run.glyphs.iter().map(|g| g.x_advance).sum();
922    }
923
924    // Recompute run x positions (runs follow each other)
925    let first_x = line.runs.first().map(|r| r.x).unwrap_or(0.0);
926    let mut x = first_x;
927    for run in &mut line.runs {
928        run.x = x;
929        x += run.shaped_run.advance_width;
930    }
931
932    line.width = target_width;
933}