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///
299/// An inline image wider than the paragraph's measure is first scaled down to
300/// fit it, its height by the same factor, before any line is built, so a line,
301/// its selection, caret and hit test and the painted quad all see one size.
302#[allow(clippy::too_many_arguments)]
303pub fn break_into_lines(
304 mut runs: Vec<ShapedRun>,
305 text: &str,
306 available_width: f32,
307 alignment: Alignment,
308 first_line_indent: f32,
309 metrics: &FontMetricsPx,
310 hyphenator: Option<Hyphenator>,
311 run_order: RunOrder,
312) -> Vec<LayoutLine> {
313 // A line with no right edge, in an unbounded width (a single-line field
314 // that scrolls rather than wraps), cannot be aligned against one: Right,
315 // Center and Justify would move its text, or an empty line's caret, to
316 // infinity. It starts at the left; a right-to-left paragraph aligns to
317 // the right by default, so without this its text was never seen.
318 let alignment = if available_width.is_finite() {
319 alignment
320 } else {
321 Alignment::Left
322 };
323 // Where a glyph-less line puts the caret. The alignment pass below only
324 // moves runs, so an empty line must carry this explicitly.
325 let empty_caret_x = {
326 let base = match run_order {
327 RunOrder::Logical(base) => base,
328 RunOrder::AlreadyVisual => TextDirection::LeftToRight,
329 };
330 empty_line_caret_x(alignment, base, first_line_indent, available_width)
331 };
332
333 if runs.is_empty() || text.is_empty() {
334 // Empty paragraph: produce one empty line for the block to have height
335 return vec![make_empty_line(metrics, 0..0, empty_caret_x)];
336 }
337
338 // Before anything reads an advance: the line breaker, the line's ascent,
339 // the selection, the caret, the hit test and the painted quad all take the
340 // image's size from its run, so scaling it here is what keeps them agreeing.
341 // The first line is the narrowest whatever the indent's sign, so measuring
342 // against it is what lets an image that opens an indented paragraph fit.
343 fit_images_to_measure(&mut runs, available_width - first_line_indent.max(0.0));
344
345 // Flatten all glyphs into a single sequence with their run association, in
346 // logical order when the runs come in logical order (see `flatten_runs`).
347 let flat = flatten_runs(&runs, matches!(run_order, RunOrder::Logical(_)));
348 if flat.is_empty() {
349 return vec![make_empty_line(metrics, 0..0, empty_caret_x)];
350 }
351
352 // Get UAX #14 break opportunities (byte offsets in text), each
353 // classified as Allowed or Mandatory.
354 let breaks: Vec<(usize, BreakOpportunity)> = enumerate_breaks(text);
355
356 // Build sets of allowed and mandatory break positions (glyph indices)
357 let (break_points, mandatory_breaks) = map_breaks_to_glyph_indices(&flat, &breaks);
358
359 // Hyphenation break candidates (glyph indices). A break here needs a
360 // trailing hyphen glyph and must reserve its advance in the fit check.
361 let hyphen_points = if let Some(h) = &hyphenator {
362 map_offsets_to_glyph_indices(&flat, &hyphenation_breaks(text, h.language))
363 } else {
364 HashSet::new()
365 };
366 let hyphen_adv = hyphenator
367 .as_ref()
368 .map(|h| h.glyph.x_advance)
369 .unwrap_or(0.0);
370
371 // Greedy line wrapping
372 let mut lines = Vec::new();
373 // Whether each line ends at a hard break, which justification leaves alone.
374 let mut hard_ends: Vec<bool> = Vec::new();
375 let mut line_start_glyph = 0usize;
376 let mut line_width = 0.0f32;
377 // Last break opportunity within the current line: (glyph index, whether
378 // breaking there renders a hyphen).
379 let mut last_break: Option<(usize, bool)> = None;
380 // First line may be indented; subsequent lines use full width
381 let mut effective_width = available_width - first_line_indent;
382
383 for i in 0..flat.len() {
384 let glyph_advance = flat[i].x_advance;
385 line_width += glyph_advance;
386
387 // Check for mandatory break — O(1) lookup — and where it falls in the text.
388 let mandatory_at = mandatory_breaks.get(&(i + 1)).copied();
389 let is_mandatory = mandatory_at.is_some();
390
391 let exceeds_width = line_width > effective_width && line_start_glyph < i;
392
393 // An emergency break goes before the glyph that overflowed, at the last
394 // cluster boundary after the line's start: the line keeps at least one
395 // cluster and a cluster wider than the line is never split. With no such
396 // boundary the line goes on, and a later glyph asks again.
397 let decision = if is_mandatory {
398 Some((i + 1, false))
399 } else if exceeds_width {
400 match last_break {
401 Some((bp, hy)) if bp > line_start_glyph => Some((bp, hy)),
402 _ => (line_start_glyph + 1..=i)
403 .rev()
404 .find(|&k| flat[k].cluster != flat[k - 1].cluster)
405 .map(|k| (k, false)),
406 }
407 } else {
408 None
409 };
410
411 if let Some((break_at, needs_hyphen)) = decision {
412 let indent = if lines.is_empty() {
413 first_line_indent
414 } else {
415 0.0
416 };
417 let mut line = build_line(
418 &runs,
419 &flat,
420 line_start_glyph,
421 break_at,
422 metrics,
423 indent,
424 text,
425 if is_mandatory { mandatory_at } else { None },
426 );
427 if needs_hyphen && let Some(h) = &hyphenator {
428 append_hyphen(&mut line, &h.glyph);
429 }
430 lines.push(line);
431 hard_ends.push(is_mandatory);
432
433 line_start_glyph = break_at;
434 // Subsequent lines use full available width
435 effective_width = available_width;
436 // Re-accumulate width for glyphs already scanned past the break
437 line_width = 0.0;
438 for j in break_at..=i {
439 if j < flat.len() {
440 line_width += flat[j].x_advance;
441 }
442 }
443 last_break = None;
444 }
445
446 // Update the break opportunity AFTER the width check so that a break
447 // discovered at this glyph does not clobber the previous one when the
448 // width is already exceeded. Hyphenation points are checked first so
449 // a soft hyphen (which is also a UAX #14 opportunity) renders its
450 // hyphen; they only count when the hyphen itself still fits.
451 let at = i + 1;
452 if hyphen_points.contains(&at) && line_width + hyphen_adv <= effective_width {
453 last_break = Some((at, true));
454 } else if break_points.contains(&at) {
455 last_break = Some((at, false));
456 }
457 }
458
459 // Remaining glyphs form the last line
460 if line_start_glyph < flat.len() {
461 let line = build_line(
462 &runs,
463 &flat,
464 line_start_glyph,
465 flat.len(),
466 metrics,
467 if lines.is_empty() {
468 first_line_indent
469 } else {
470 0.0
471 },
472 text,
473 None,
474 );
475 lines.push(line);
476 hard_ends.push(false);
477 }
478
479 // A hard break at the very end starts a line of its own, empty, where the
480 // caret goes after Shift+Enter at the end of a paragraph: without it the
481 // caret stayed at the end of the line it had just left, and the paragraph
482 // a line short.
483 if text
484 .chars()
485 .next_back()
486 .is_some_and(crate::types::is_hard_break)
487 {
488 let end = byte_offset_to_char_offset(text, text.len());
489 let base = match run_order {
490 RunOrder::Logical(base) => base,
491 RunOrder::AlreadyVisual => TextDirection::LeftToRight,
492 };
493 let caret_x = empty_line_caret_x(alignment, base, 0.0, available_width);
494 lines.push(make_empty_line(metrics, end..end, caret_x));
495 hard_ends.push(false);
496 }
497
498 // Put each line's runs into visual order before anything reads their
499 // x positions. Alignment shifts every run by the same amount so it
500 // does not care about order, but `justify_line` re-lays runs
501 // sequentially from the vector and would otherwise justify a
502 // mixed-direction line in logical order.
503 let base_direction = match run_order {
504 RunOrder::Logical(base) => {
505 for line in &mut lines {
506 reorder_line_visually(line);
507 }
508 base
509 }
510 // Already visual: reordering here would reverse the caller's work.
511 RunOrder::AlreadyVisual => TextDirection::LeftToRight,
512 };
513
514 // Apply alignment. An unset alignment follows the paragraph's base
515 // direction, so an RTL paragraph right-aligns without the host having
516 // to translate direction into alignment itself.
517 let alignment = alignment.resolve_for(base_direction);
518 let rtl_paragraph = base_direction == TextDirection::RightToLeft;
519 let effective_width = available_width;
520 let last_idx = lines.len().saturating_sub(1);
521 for (i, line) in lines.iter_mut().enumerate() {
522 let indent = if i == 0 { first_line_indent } else { 0.0 };
523 // A first-line indent insets from the paragraph's *leading* edge,
524 // which in an RTL paragraph is the right one. `build_line` always
525 // insets from the left, so undo that here and let the narrowed
526 // `line_avail` below carry the inset over to the right instead.
527 if rtl_paragraph && indent != 0.0 {
528 for run in &mut line.runs {
529 run.x -= indent;
530 }
531 }
532 let line_avail = effective_width - indent;
533 match alignment {
534 // `resolve_for` maps these onto Left/Right, so they cannot
535 // reach here — but fail soft rather than panicking in a
536 // layout pass that runs on every keystroke.
537 Alignment::Start | Alignment::End | Alignment::Left => {
538 // Runs already sit at the indent, except in an RTL
539 // paragraph where the block above moved them to 0 so the
540 // inset could go to the trailing edge. An explicit Left
541 // means the writer wants flush-left text, and the indent
542 // still belongs on the paragraph's leading edge, so put
543 // it back.
544 if rtl_paragraph && indent != 0.0 {
545 for run in &mut line.runs {
546 run.x += indent;
547 }
548 }
549 }
550 Alignment::Right => {
551 let shift = (line_avail - line.width).max(0.0);
552 for run in &mut line.runs {
553 run.x += shift;
554 }
555 }
556 Alignment::Center => {
557 let shift = ((line_avail - line.width) / 2.0).max(0.0);
558 for run in &mut line.runs {
559 run.x += shift;
560 }
561 }
562 Alignment::Justify => {
563 // Don't justify the last line, nor one a hard break ends: a
564 // line of verse or of a letter set apart by Shift+Enter keeps
565 // its words where they are, as a browser and Typst set it.
566 if i < last_idx && !hard_ends[i] && line.width > 0.0 {
567 justify_line(line, line_avail, text);
568 }
569 }
570 }
571 }
572
573 if lines.is_empty() {
574 lines.push(make_empty_line(metrics, 0..0, empty_caret_x));
575 }
576
577 // Convert glyph cluster values from byte offsets to char offsets.
578 // This must happen AFTER alignment because justify_line needs byte
579 // offsets to find space characters in the original text.
580 for line in &mut lines {
581 for run in &mut line.runs {
582 for glyph in &mut run.shaped_run.glyphs {
583 glyph.cluster = byte_offset_to_char_offset(text, glyph.cluster as usize) as u32;
584 }
585 }
586 }
587
588 lines
589}
590
591/// Scale every inline image wider than `measure` down to it, keeping its
592/// proportions. Never scales up.
593///
594/// An image is set at its own size until it no longer fits the line it sits on,
595/// the CSS `max-width: 100%` of a replaced element. Without this a picture wider
596/// than the column (a screenshot from a high-density screen, a photograph at its
597/// pixel size) ran past the frame's edge, and the line, the selection and the hit
598/// test ran with it. The measure is the paragraph's own, after its margins, list
599/// indent and the cell or quote it sits in, not the room left after the text
600/// before it on the line: an image that does not fit there breaks onto a line of
601/// its own, as it always has, and is then capped to the whole measure.
602///
603/// The size a host stored is never changed: shaping starts again from it on every
604/// layout, so a narrower and then a wider measure give the same result as the wider
605/// one alone. A measure that is not a positive finite number (an unbounded
606/// single-line field, a frame not sized yet) leaves images alone, and neither side
607/// of a scaled image goes below one pixel.
608fn fit_images_to_measure(runs: &mut [ShapedRun], measure: f32) {
609 if !measure.is_finite() || measure <= 0.0 {
610 return;
611 }
612 let measure = measure.max(1.0);
613 for run in runs.iter_mut().filter(|r| r.image_name.is_some()) {
614 let width = run.advance_width;
615 if !width.is_finite() || width <= measure {
616 continue;
617 }
618 let factor = measure / width;
619 for glyph in &mut run.glyphs {
620 glyph.x_advance *= factor;
621 }
622 run.advance_width = measure;
623 if run.image_height.is_finite() && run.image_height > 0.0 {
624 run.image_height = (run.image_height * factor).max(1.0);
625 }
626 }
627}
628
629/// A flattened glyph with enough info to map back to runs.
630struct FlatGlyph {
631 x_advance: f32,
632 cluster: u32,
633 run_index: usize,
634 glyph_index_in_run: usize,
635}
636
637/// The glyphs of `runs` as one sequence, each with its run and its index in it.
638///
639/// With `logical`, the runs arrive in logical order and so does the sequence: a
640/// right-to-left run's glyphs, which shaping stores in visual order (its last
641/// character first), are walked from its end. Line breaking reads the sequence as the
642/// text runs, so walked visually such a run was broken from its logical end: a wrapped
643/// right-to-left paragraph set its last words on its first line, and a break inside
644/// one (a line separator, which stays in the run it sits in) mapped to its first
645/// glyph and was never taken. A line still takes a contiguous slice of each run's
646/// glyphs, since the logical stretch of a run is a contiguous stretch of it visually.
647fn flatten_runs(runs: &[ShapedRun], logical: bool) -> Vec<FlatGlyph> {
648 let mut flat = Vec::new();
649 for (run_idx, run) in runs.iter().enumerate() {
650 // Offset cluster values from fragment-text space to block-text space.
651 // rustybuzz assigns clusters as byte offsets within the fragment text (0-based),
652 // but unicode-linebreak returns byte offsets in the full block text.
653 let cluster_offset = run.text_range.start as u32;
654 let push = |flat: &mut Vec<FlatGlyph>, glyph_idx: usize| {
655 flat.push(FlatGlyph {
656 x_advance: run.glyphs[glyph_idx].x_advance,
657 cluster: run.glyphs[glyph_idx].cluster + cluster_offset,
658 run_index: run_idx,
659 glyph_index_in_run: glyph_idx,
660 });
661 };
662 if logical && run.direction == TextDirection::RightToLeft {
663 for glyph_idx in (0..run.glyphs.len()).rev() {
664 push(&mut flat, glyph_idx);
665 }
666 } else {
667 for glyph_idx in 0..run.glyphs.len() {
668 push(&mut flat, glyph_idx);
669 }
670 }
671 }
672 flat
673}
674
675/// Map unicode-linebreak byte offsets to glyph indices using a merged walk.
676/// Both `flat` (by cluster) and `breaks` (by byte offset) are sorted,
677/// so a single O(b + m) pass replaces the previous O(b × m) approach.
678///
679/// Returns (break_points: HashSet<glyph_idx>, mandatory_breaks: glyph_idx → the byte
680/// offset of the break in the text).
681fn map_breaks_to_glyph_indices(
682 flat: &[FlatGlyph],
683 breaks: &[(usize, BreakOpportunity)],
684) -> (HashSet<usize>, HashMap<usize, usize>) {
685 let mut break_points = HashSet::new();
686 let mut mandatory_breaks = HashMap::new();
687 let mut glyph_cursor = 0usize;
688
689 for &(byte_offset, opportunity) in breaks {
690 // Advance glyph cursor to the first glyph whose cluster >= byte_offset
691 while glyph_cursor < flat.len() && (flat[glyph_cursor].cluster as usize) < byte_offset {
692 glyph_cursor += 1;
693 }
694 let glyph_idx = if glyph_cursor < flat.len() {
695 glyph_cursor
696 } else {
697 flat.len()
698 };
699 break_points.insert(glyph_idx);
700 if opportunity == BreakOpportunity::Mandatory {
701 mandatory_breaks.insert(glyph_idx, byte_offset);
702 }
703 }
704
705 (break_points, mandatory_breaks)
706}
707
708/// Build a LayoutLine from a glyph range within the flat sequence.
709///
710/// `hard_end` is where a hard break the line ends at falls in the text, the byte
711/// after the break: the line's text ends there. Read from the next glyph instead, it
712/// overshot into the next line when that one opens with a right-to-left run, whose
713/// first glyph carries its *last* cluster, and the break was lost.
714#[allow(clippy::too_many_arguments)]
715fn build_line(
716 runs: &[ShapedRun],
717 flat: &[FlatGlyph],
718 start: usize,
719 end: usize,
720 metrics: &FontMetricsPx,
721 indent: f32,
722 text: &str,
723 hard_end: Option<usize>,
724) -> LayoutLine {
725 // Group consecutive glyphs by run_index to reconstruct PositionedRuns. A group is
726 // a contiguous slice of its run's glyphs, walked forwards, or backwards for a
727 // right-to-left run laid out in logical order (see `flatten_runs`), so its slice is
728 // the span of the indices it holds.
729 let mut positioned_runs = Vec::new();
730 let mut x = indent;
731 let mut i = start;
732 while i < end {
733 let run_idx = flat[i].run_index;
734 let (mut lo, mut hi) = (flat[i].glyph_index_in_run, flat[i].glyph_index_in_run);
735 let mut j = i + 1;
736 while j < end && flat[j].run_index == run_idx {
737 lo = lo.min(flat[j].glyph_index_in_run);
738 hi = hi.max(flat[j].glyph_index_in_run);
739 j += 1;
740 }
741 if let Some((pr, advance)) = extract_sub_run(runs, run_idx, lo, hi + 1) {
742 positioned_runs.push(PositionedRun {
743 decorations: RunDecorations {
744 underline_style: pr.underline_style,
745 overline: pr.overline,
746 strikeout: pr.strikeout,
747 is_link: pr.is_link,
748 foreground_color: pr.foreground_color,
749 underline_color: pr.underline_color,
750 background_color: pr.background_color,
751 anchor_href: pr.anchor_href.clone(),
752 tooltip: pr.tooltip.clone(),
753 vertical_alignment: pr.vertical_alignment,
754 },
755 shaped_run: pr,
756 x,
757 });
758 x += advance;
759 }
760 i = j;
761 }
762
763 let width = x - indent;
764
765 // Compute char range from cluster values.
766 // Clusters from rustybuzz are byte offsets — convert to char offsets
767 // so that positions match text-document's character-based coordinates.
768 //
769 // Glyphs are in *visual* order, so for an RTL run `flat[start]` holds
770 // the largest cluster and `flat[end-1]` the smallest. Take the min/max
771 // over the line's glyphs instead of trusting the array ends, so the
772 // logical range is correct for both directions.
773 let byte_start = flat[start..end.min(flat.len())]
774 .iter()
775 .map(|g| g.cluster as usize)
776 .min()
777 .unwrap_or(0);
778 let byte_end = if let Some(hard_end) = hard_end {
779 hard_end
780 } else if end >= flat.len() {
781 // Last glyph reaches the end of the input text. Always snap to the
782 // full length: a trailing ligature glyph may cover several source
783 // chars, so `max_cluster + 1` would be wrong.
784 text.len()
785 } else {
786 // Next visual glyph's cluster bounds an LTR line exactly; for a
787 // wrapped RTL line take whichever is larger so the logical end
788 // still covers the line's highest cluster.
789 let line_max = flat[start..end]
790 .iter()
791 .map(|g| g.cluster as usize)
792 .max()
793 .unwrap_or(0);
794 (flat[end].cluster as usize).max(line_max)
795 };
796 let char_start = byte_offset_to_char_offset(text, byte_start);
797 let char_end = byte_offset_to_char_offset(text, byte_end);
798 let hard_break_chars = match text
799 .get(byte_start..byte_end)
800 .and_then(crate::types::LineEnd::hard_break_ending)
801 {
802 Some(crate::types::LineEnd::HardBreak { chars, .. }) => chars as usize,
803 _ => 0,
804 };
805
806 // Expand line height for inline images taller than the font ascent
807 let mut ascent = metrics.ascent;
808 for run in &positioned_runs {
809 if run.shaped_run.image_name.is_some() && run.shaped_run.image_height > ascent {
810 ascent = run.shaped_run.image_height;
811 }
812 }
813 let line_height = ascent + metrics.descent + metrics.leading;
814
815 LayoutLine {
816 runs: positioned_runs,
817 y: 0.0, // will be set by the caller (block layout)
818 ascent,
819 descent: metrics.descent,
820 leading: metrics.leading,
821 width,
822 char_range: char_start..char_end,
823 line_height,
824 // Degenerate fallback only: a built line normally derives caret
825 // positions from its runs, but if every run came out glyph-less
826 // the caret still has the line's start to sit at.
827 empty_caret_x: indent,
828 hard_break_chars,
829 }
830}
831
832/// Extract a sub-run (slice of glyphs) from a ShapedRun.
833/// Cluster values are offset to block-text space (adding text_range.start).
834fn extract_sub_run(
835 runs: &[ShapedRun],
836 run_index: usize,
837 glyph_start: usize,
838 glyph_end: usize,
839) -> Option<(ShapedRun, f32)> {
840 let run = &runs[run_index];
841 let end = glyph_end.min(run.glyphs.len());
842 if glyph_start >= end {
843 return None;
844 }
845 let cluster_offset = run.text_range.start as u32;
846 let mut sub_glyphs = run.glyphs[glyph_start..end].to_vec();
847 // Offset cluster values from fragment-local to block-text space
848 for g in &mut sub_glyphs {
849 g.cluster += cluster_offset;
850 }
851 let advance: f32 = sub_glyphs.iter().map(|g| g.x_advance).sum();
852
853 let sub_run = ShapedRun {
854 font_face_id: run.font_face_id,
855 size_px: run.size_px,
856 weight: run.weight,
857 italic: run.italic,
858 glyphs: sub_glyphs,
859 advance_width: advance,
860 text_range: run.text_range.clone(),
861 direction: run.direction,
862 bidi_level: run.bidi_level,
863 underline_style: run.underline_style,
864 overline: run.overline,
865 strikeout: run.strikeout,
866 is_link: run.is_link,
867 foreground_color: run.foreground_color,
868 underline_color: run.underline_color,
869 background_color: run.background_color,
870 anchor_href: run.anchor_href.clone(),
871 tooltip: run.tooltip.clone(),
872 vertical_alignment: run.vertical_alignment,
873 image_name: run.image_name.clone(),
874 image_height: run.image_height,
875 };
876 Some((sub_run, advance))
877}
878
879fn make_empty_line(
880 metrics: &FontMetricsPx,
881 char_range: Range<usize>,
882 empty_caret_x: f32,
883) -> LayoutLine {
884 LayoutLine {
885 runs: Vec::new(),
886 y: 0.0,
887 ascent: metrics.ascent,
888 descent: metrics.descent,
889 leading: metrics.leading,
890 width: 0.0,
891 char_range,
892 line_height: metrics.ascent + metrics.descent + metrics.leading,
893 empty_caret_x,
894 hard_break_chars: 0,
895 }
896}
897
898/// The x where the caret sits on a line with no glyphs — i.e. where the
899/// first typed character's glyph would land. Mirrors the run-shifting
900/// arithmetic of `break_into_lines`' alignment pass with a line width of
901/// zero, so an empty paragraph's caret cannot disagree with where the
902/// first keystroke lays text out (the "caret jumps on the first
903/// character" bug).
904fn empty_line_caret_x(
905 alignment: Alignment,
906 base_direction: TextDirection,
907 first_line_indent: f32,
908 available_width: f32,
909) -> f32 {
910 let rtl = base_direction == TextDirection::RightToLeft;
911 let indent = first_line_indent;
912 let line_avail = (available_width - indent).max(0.0);
913 match alignment.resolve_for(base_direction) {
914 // In an RTL paragraph the alignment pass first moves runs to the
915 // left edge so the indent insets from the *right*; Right then
916 // shifts by the remaining width. Width zero leaves the caret at
917 // `line_avail` (RTL) or the full width (LTR).
918 Alignment::Right => {
919 if rtl {
920 line_avail
921 } else {
922 available_width
923 }
924 }
925 Alignment::Center => {
926 let shift = line_avail / 2.0;
927 if rtl { shift } else { indent + shift }
928 }
929 // Justify never justifies the last line, and a lone line is the
930 // last line, so runs keep their unshifted positions: the indent
931 // for LTR; the left edge for RTL, where the alignment pass moved
932 // them and Justify does not put the indent back.
933 Alignment::Justify => {
934 if rtl {
935 0.0
936 } else {
937 indent
938 }
939 }
940 // `resolve_for` maps Start/End onto Left/Right, so what remains is
941 // Left — which keeps runs at the indent in both directions.
942 _ => indent,
943 }
944}
945
946/// Distribute extra space among word gaps for justification.
947///
948/// Finds space glyphs (cluster mapping to ' ') across all runs and
949/// increases their x_advance proportionally. Then recomputes run x positions.
950fn justify_line(line: &mut LayoutLine, target_width: f32, text: &str) {
951 let extra = target_width - line.width;
952 if extra <= 0.0 {
953 return;
954 }
955
956 // Count space glyphs across all runs
957 let mut space_count = 0usize;
958 for run in &line.runs {
959 for glyph in &run.shaped_run.glyphs {
960 let byte_offset = glyph.cluster as usize;
961 if let Some(ch) = text.get(byte_offset..).and_then(|s| s.chars().next())
962 && ch == ' '
963 {
964 space_count += 1;
965 }
966 }
967 }
968
969 if space_count == 0 {
970 return;
971 }
972
973 let extra_per_space = extra / space_count as f32;
974
975 // Increase x_advance of space glyphs
976 for run in &mut line.runs {
977 for glyph in &mut run.shaped_run.glyphs {
978 let byte_offset = glyph.cluster as usize;
979 if let Some(ch) = text.get(byte_offset..).and_then(|s| s.chars().next())
980 && ch == ' '
981 {
982 glyph.x_advance += extra_per_space;
983 }
984 }
985 // Recompute run advance width
986 run.shaped_run.advance_width = run.shaped_run.glyphs.iter().map(|g| g.x_advance).sum();
987 }
988
989 // Recompute run x positions (runs follow each other)
990 let first_x = line.runs.first().map(|r| r.x).unwrap_or(0.0);
991 let mut x = first_x;
992 for run in &mut line.runs {
993 run.x = x;
994 x += run.shaped_run.advance_width;
995 }
996
997 line.width = target_width;
998}