Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_austenite/src/linebreak.rs

31.9 KiB, 201 runs

created by r1870400018:35932, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Total-fit line breaking, after Knuth and Plass (*Breaking Paragraphs into Lines*, 1981).
2//!
3//! A paragraph is turned into the box-glue-penalty stream the [`ir`](crate::ir) already models: a
4//! shaped word is a rigid box, the space between words is stretchable glue, and each legal break --
5//! from `fe2o3_text`'s UAX #14 opportunities -- is a point the optimiser may take. The active-node
6//! dynamic program picks the set of breaks minimising the sum of squared demerits, so a loose line
7//! early is paid for against the whole paragraph rather than greedily.
8//!
9//! Two facts a reader could not derive. The last line is set flush left, not justified, by ending
10//! the stream with a glue of near-infinite stretch before the forced break: that glue swallows the
11//! slack, so the words keep their natural spacing. And justification is realised in the glue itself
12//! -- each chosen line's inter-word glue carries its *adjusted* natural width -- so the existing
13//! driver lays a line left to right with no notion of a ratio, and still fills the measure.
14
15use crate::font::ShapedText;
16use crate::hyphenate::Hyphenator;
17use crate::ir::{
18 BoxNode,
19 Dims,
20 Glue,
21 Leaf,
22 Node,
23 Penalty,
24 Sp,
25};
26use crate::ledger::AnchorId;
27
28use oxedyne_fe2o3_core::prelude::*;
29use oxedyne_fe2o3_font::{
30 face::Role,
31 set::FontSet,
32 shape::{
33 Dir,
34 Feature,
35 },
36};
37use oxedyne_fe2o3_graphics::colour::Rgba;
38use oxedyne_fe2o3_text::unicode::linebreak::{
39 self,
40 Break,
41};
42
43use std::sync::Arc;
44
45const LINE_PENALTY: f64 = 10.0; // Knuth's l, the intrinsic cost of ending any line
46const MAX_RATIO: f64 = 10.0; // tolerance: a break looser than this is infeasible
47const FLAGGED_DEMERIT: f64 = 10_000.0; // two flagged breaks in a row (consecutive hyphens)
48const HYPHEN_PENALTY: i32 = 50; // the cost of taking a discretionary (interior) break
49const HYPHEN_MIN: usize = 5; // a word shorter than this is never split
50
51/// The finishing glue's stretch: large against any real line, so a short last line sets flush left.
52fn inf_stretch() -> Sp { Sp::from_pt(10_000.0) }
53
54/// Breaks `text` into optimally-set lines at `measure`, each an [`Node::HBox`] of shaped words and
55/// justified glue, joined by inter-line glue sized so baselines fall `leading` apart -- a vertical
56/// list ready for the driver.
57pub fn break_paragraph(
58 fonts: Arc<FontSet>,
59 role: Role,
60 dir: Dir,
61 size: Sp,
62 text: &str,
63 measure: Sp,
64 leading: Sp,
65 hyphenate: bool,
66 fill: Rgba, // the colour every prose leaf of this paragraph draws in, from `theme.text.fill`
67 cap: Option<Sp>, // the block-edge model; see [`set_lines`]
68)
69 -> Outcome<Vec<Node>>
70{
71 let items = res!(build_items(fonts, role, dir, size, text, hyphenate));
72 if items.is_empty() {
73 return Ok(Vec::new());
74 }
75 let breaks = optimal_breaks(&items, measure, true);
76 let lines = res!(set_lines(&items, &breaks, measure, leading, true, fill, cap));
77 Ok(lines)
78}
79
80/// One run of a segmented paragraph: a stretch of text in a named face, or a pre-built footnote mark
81/// leaf. A rich paragraph is a sequence of these -- an emphasised run and the body either side of it,
82/// the text around each footnote mark, and the marks themselves -- so a run shapes in its own face while
83/// line breaking still flows across the boundaries. The `role` is per run: `*strong*` arrives as a
84/// `Bold` piece, `/emph/` as an `Italic` one, the surrounding prose as `Body`.
85pub enum Piece {
86 Text { text: String, role: Role },
87 // A `#smallcaps[...]` run: shaped in `role` with the font's small-capitals feature, and otherwise
88 // broken exactly as a text run -- words, interword glue and hyphenation alike.
89 SmallCaps { text: String, role: Role },
90 Mark(Leaf), // a footnote mark, already shaped as a raised superscript (LeafKind::Mark)
91 // A zero-width anchor woven into the line at the point it was authored, recording where an identity
92 // landed without occupying any horizontal space -- the marginalia anchor, whose margin note is drawn
93 // post-convergence from the ledger. It never removes a break opportunity: the line breaks exactly as
94 // it would with the anchor absent, so a paragraph carrying one sets byte-identically to one that does not.
95 Anchor(AnchorId),
96 Math { // an inline maths box, already flattened to leaves and glue by math::layout
97 nodes: Vec<Node>,
98 width: Sp,
99 height: Sp, // the line height the box asks for, the surrounding text ascent
100 depth: Sp, // how far the box hangs below the baseline
101 over: Sp, // how far it climbs above the line, so the line above can open for it
102 },
103}
104
105/// Breaks a segmented paragraph the way [`break_paragraph`] breaks a plain one, but with footnote marks
106/// woven into the stream. Each text piece contributes its words and interword glue; each mark piece a
107/// rigid superscript box that never breaks and that the following space may break after. The result is
108/// the same vertical list of HBox lines, so the driver sets it with no special case -- and a paragraph
109/// of a single text piece produces exactly what [`break_paragraph`] would.
110///
111/// `justify` fills each line to the measure by adjusting its interword glue, the body's set; `false`
112/// sets the lines ragged right, each space at its natural width -- what a table cell wants, so the
113/// band's own justification to the table width cannot stretch or collapse the words within a cell.
114pub fn break_paragraph_pieces(
115 fonts: Arc<FontSet>,
116 role: Role,
117 dir: Dir,
118 size: Sp,
119 pieces: &[Piece],
120 measure: Sp,
121 leading: Sp,
122 justify: bool,
123 hyphenate: bool,
124 fill: Rgba, // the colour every prose text leaf draws in; marks and maths keep their own black
125 cap: Option<Sp>, // the block-edge model; see [`set_lines`]
126)
127 -> Outcome<Vec<Node>>
128{
129 let (sp_w, stretch, shrink, hyphen) = res!(interword(fonts.clone(), role, dir, size));
130 let hyph = Hyphenator::en_us();
131
132 let mut items = Vec::new();
133 for piece in pieces {
134 match piece {
135 Piece::Text { text, role: run } => {
136 // The run shapes in its own face; the interword glue keeps the paragraph's role, so a space
137 // beside an emphasised word stays the body space (TeX sets the space in the surrounding font).
138 res!(push_text_run(
139 &mut items, fonts.clone(), *run, dir, size, text, sp_w, stretch, shrink, &hyph, &hyphen, hyphenate, &[]));
140 },
141 Piece::SmallCaps { text, role: run } => {
142 res!(push_text_run(
143 &mut items, fonts.clone(), *run, dir, size, text, sp_w, stretch, shrink, &hyph, &hyphen, hyphenate,
144 &[Feature::SMALL_CAPS]));
145 },
146 Piece::Mark(leaf) => {
147 items.push(Item {
148 kind: Kind::Mark(leaf.clone()), width: leaf.dims.width, stretch: Sp::ZERO,
149 shrink: Sp::ZERO, penalty: Penalty::INFINITY, flagged: false, hyphen: None });
150 },
151 Piece::Anchor(id) => {
152 // Zero of everything: no width to shift a break, an infinite penalty so it is never itself a
153 // breakpoint, and `is_break` looks through it so the glue beside it breaks as if it were absent.
154 items.push(Item {
155 kind: Kind::Anchor(id.clone()), width: Sp::ZERO, stretch: Sp::ZERO,
156 shrink: Sp::ZERO, penalty: Penalty::INFINITY, flagged: false, hyphen: None });
157 },
158 Piece::Math { nodes, width, height, depth, over } => {
159 // A rigid cluster, like a very wide box: it never breaks, and the space after it may.
160 items.push(Item {
161 kind: Kind::Math { nodes: nodes.clone(), height: *height, depth: *depth, over: *over },
162 width: *width, stretch: Sp::ZERO, shrink: Sp::ZERO,
163 penalty: Penalty::INFINITY, flagged: false, hyphen: None });
164 },
165 }
166 }
167 push_finish(&mut items); // the forced break that ends the paragraph, whatever the last piece was
168
169 if items.is_empty() {
170 return Ok(Vec::new());
171 }
172 let breaks = optimal_breaks(&items, measure, justify);
173 let lines = res!(set_lines(&items, &breaks, measure, leading, justify, fill, cap));
174 Ok(lines)
175}
176
177/// One entry of the box-glue-penalty stream. A `Boxed` word (or word fragment) is rigid; a `Glued`
178/// space stretches and shrinks; a `Pen` is a break carrying no space (a hyphen point, or the forced
179/// end of the stream); a `Mark` is a footnote's superscript, rigid like a box but already built with
180/// its raised dimensions.
181enum Kind {
182 Boxed(ShapedText),
183 Glued,
184 Pen,
185 Mark(Leaf),
186 Anchor(AnchorId), // a zero-width position marker woven into the line, drawn as a `Node::Anchor`
187 Math { // an inline maths box: pre-built leaves and glue, its own extent
188 nodes: Vec<Node>,
189 height: Sp,
190 depth: Sp,
191 over: Sp, // how far the box climbs above the line top, for the interline gap above it
192 },
193}
194
195struct Item {
196 kind: Kind,
197 width: Sp, // box advance, or glue natural length
198 stretch: Sp,
199 shrink: Sp,
200 penalty: i32, // break cost; a box carries INFINITY, a plain space break 0
201 flagged: bool,
202 hyphen: Option<ShapedText>, // a discretionary's hyphen glyph, drawn only if the break is taken
203}
204
205/// Shapes each word of `text` and turns UAX #14's opportunities into the box-glue-penalty stream, then
206/// closes it with the forced break that ends the paragraph.
207fn build_items(
208 fonts: Arc<FontSet>,
209 role: Role,
210 dir: Dir,
211 size: Sp,
212 text: &str,
213 hyphenate: bool,
214)
215 -> Outcome<Vec<Item>>
216{
217 let (sp_w, stretch, shrink, hyphen) = res!(interword(fonts.clone(), role, dir, size));
218 let hyph = Hyphenator::en_us();
219
220 let mut items = Vec::new();
221 res!(push_text_run(&mut items, fonts, role, dir, size, text, sp_w, stretch, shrink, &hyph, &hyphen, hyphenate, &[]));
222 push_finish(&mut items);
223 Ok(items)
224}
225
226/// The interword space, measured from the face with the classic TeX-ish elasticity -- it grows by a
227/// half and gives up a third -- and the hyphen glyph a taken discretionary draws, both shaped once.
228fn interword(
229 fonts: Arc<FontSet>,
230 role: Role,
231 dir: Dir,
232 size: Sp,
233)
234 -> Outcome<(Sp, Sp, Sp, ShapedText)>
235{
236 let space = res!(ShapedText::new(fonts.clone(), role, dir, size, " "));
237 let sp_w = space.dims().width;
238 let stretch = Sp(sp_w.raw() / 2);
239 let shrink = Sp(sp_w.raw() / 3);
240 let hyphen = res!(ShapedText::new(fonts, role, dir, size, "-"));
241 Ok((sp_w, stretch, shrink, hyphen))
242}
243
244/// The glue and forced break that end a paragraph: a glue of near-infinite stretch swallows the last
245/// line's slack so it sets flush left, then a forced break the optimiser must take.
246fn push_finish(items: &mut Vec<Item>) {
247 items.push(Item {
248 kind: Kind::Glued, width: Sp::ZERO, stretch: inf_stretch(), shrink: Sp::ZERO,
249 penalty: Penalty::INFINITY, flagged: false, hyphen: None });
250 items.push(Item {
251 kind: Kind::Pen, width: Sp::ZERO, stretch: Sp::ZERO, shrink: Sp::ZERO,
252 penalty: Penalty::EJECT, flagged: false, hyphen: None });
253}
254
255/// Appends one run of text as words and interword glue, turning UAX #14's opportunities into the
256/// stream. Punctuation stays with its word: the opportunities only fall after spaces (and the odd slash
257/// or hyphen), so trimming a segment's trailing whitespace leaves the word with its clinging marks. The
258/// run's terminal opportunity does not close the paragraph -- that is [`push_finish`]'s single job,
259/// after every run -- so a mark piece may follow this run's last word with nothing between them.
260#[allow(clippy::too_many_arguments)]
261fn push_text_run(
262 items: &mut Vec<Item>,
263 fonts: Arc<FontSet>,
264 role: Role,
265 dir: Dir,
266 size: Sp,
267 text: &str,
268 sp_w: Sp,
269 stretch: Sp,
270 shrink: Sp,
271 hyph: &Hyphenator,
272 hyphen: &ShapedText,
273 hyphenate: bool,
274 features: &[Feature], // OpenType features every word of the run is shaped with
275)
276 -> Outcome<()>
277{
278 // A run that follows a mark (or another run) may open with a space -- the interword space that parts
279 // the mark from the next word. Lift it out as its own elastic, breakable glue rather than baking it
280 // into the first word's box, so the space justifies and the line may break after the mark.
281 let trimmed = text.trim_start_matches(|c: char| matches!(c, ' ' | '\t' | '\n' | '\r'));
282 let lead = text.len() - trimmed.len();
283 if lead > 0 {
284 let spaces = text[..lead].chars().filter(|c| *c == ' ').count() as i32;
285 if spaces > 0 {
286 items.push(Item {
287 kind: Kind::Glued, width: Sp(sp_w.raw() * spaces), stretch, shrink,
288 penalty: 0, flagged: false, hyphen: None });
289 }
290 }
291 let text = trimmed;
292
293 let opps = linebreak::line_breaks(text);
294 let n = opps.len();
295 let mut prev = 0usize;
296 for (oi, opp) in opps.iter().enumerate() {
297 let seg = &text[prev..opp.offset];
298 prev = opp.offset;
299 let word = seg.trim_end_matches(|c: char| matches!(c, ' ' | '\t' | '\n' | '\r'));
300 let tail = &seg[word.len()..];
301 if !word.is_empty() {
302 res!(push_word(items, fonts.clone(), role, dir, size, word, hyph, hyphen, hyphenate, features));
303 }
304 let spaces = tail.chars().filter(|c| *c == ' ').count() as i32;
305 match opp.kind {
306 Break::Mandatory if oi + 1 == n => {
307 // The run's own end. Any trailing space becomes a breakable glue so a following mark or
308 // run may part from this word; the paragraph's forced break is added once, by push_finish.
309 if spaces > 0 {
310 items.push(Item {
311 kind: Kind::Glued, width: Sp(sp_w.raw() * spaces), stretch, shrink,
312 penalty: 0, flagged: false, hyphen: None });
313 }
314 },
315 Break::Mandatory => {
316 // An interior hard break (an explicit newline within the run): flush the line and force it.
317 push_finish(items);
318 },
319 Break::Optional => {
320 if spaces > 0 {
321 items.push(Item {
322 kind: Kind::Glued, width: Sp(sp_w.raw() * spaces), stretch, shrink,
323 penalty: 0, flagged: false, hyphen: None });
324 } else {
325 // A break with no space -- a slash or an already-present hyphen. Latin prose rarely
326 // reaches here; it becomes a zero-width penalty so the two parts may still part.
327 items.push(Item {
328 kind: Kind::Pen, width: Sp::ZERO, stretch: Sp::ZERO, shrink: Sp::ZERO,
329 penalty: 0, flagged: false, hyphen: None });
330 }
331 },
332 }
333 }
334 Ok(())
335}
336
337/// Shapes one word and pushes it as boxes. A word long enough to hold a legal Liang break is split at
338/// each point into fragment boxes joined by flagged hyphen penalties, so the optimiser may take one
339/// and end a line inside the word; otherwise the word is a single rigid box. The hyphenation runs on
340/// the word's alphabetic core, so leading and trailing punctuation stay clinging to the outer
341/// fragments.
342#[allow(clippy::too_many_arguments)]
343fn push_word(
344 items: &mut Vec<Item>,
345 fonts: Arc<FontSet>,
346 role: Role,
347 dir: Dir,
348 size: Sp,
349 word: &str,
350 hyph: &Hyphenator,
351 hyphen: &ShapedText,
352 hyphenate: bool,
353 features: &[Feature],
354)
355 -> Outcome<()>
356{
357 // The alphabetic core, and where it starts in the word, so break points map back to word bytes. With
358 // hyphenation off (`#set text(hyphenate: false)`), no point is offered and the word stays one rigid box.
359 let start = word.len() - word.trim_start_matches(|c: char| !c.is_alphabetic()).len();
360 let core = word.trim_matches(|c: char| !c.is_alphabetic());
361 let points = if hyphenate && core.chars().count() >= HYPHEN_MIN { hyph.hyphenate(core) } else { Vec::new() };
362
363 if points.is_empty() {
364 let shaped = res!(ShapedText::new_with_features(fonts, role, dir, size, word, features));
365 let w = shaped.dims().width;
366 items.push(Item {
367 kind: Kind::Boxed(shaped), width: w, stretch: Sp::ZERO, shrink: Sp::ZERO,
368 penalty: Penalty::INFINITY, flagged: false, hyphen: None });
369 return Ok(());
370 }
371
372 // Turn each char-prefix count into a byte split within the word, then walk the fragments.
373 let mut splits: Vec<usize> = Vec::with_capacity(points.len());
374 for &chars in &points {
375 let off = core.char_indices().nth(chars).map_or(core.len(), |(b, _)| b);
376 splits.push(start + off);
377 }
378 let mut bounds = Vec::with_capacity(splits.len() + 2);
379 bounds.push(0);
380 bounds.extend_from_slice(&splits);
381 bounds.push(word.len());
382
383 for w in bounds.windows(2) {
384 let frag = &word[w[0]..w[1]];
385 let shaped = res!(ShapedText::new_with_features(fonts.clone(), role, dir, size, frag, features));
386 let fw = shaped.dims().width;
387 items.push(Item {
388 kind: Kind::Boxed(shaped), width: fw, stretch: Sp::ZERO, shrink: Sp::ZERO,
389 penalty: Penalty::INFINITY, flagged: false, hyphen: None });
390 if w[1] < word.len() {
391 // A discretionary between two fragments: a flagged break whose taken cost is the hyphen's
392 // width, added to the line only when the optimiser chooses it (see line_len).
393 items.push(Item {
394 kind: Kind::Pen, width: Sp::ZERO, stretch: Sp::ZERO, shrink: Sp::ZERO,
395 penalty: HYPHEN_PENALTY, flagged: true, hyphen: Some(hyphen.clone()) });
396 }
397 }
398 Ok(())
399}
400
401/// Is item `i` a legal breakpoint? A space breaks after a word, unless forbidden -- the finishing
402/// glue carries an infinite penalty so only the forced break after it ends the last line. A penalty
403/// breaks unless forbidden; a box never breaks.
404fn is_break(items: &[Item], i: usize) -> bool {
405 match items[i].kind {
406 Kind::Glued => i > 0
407 && prev_is_boxlike(items, i)
408 && items[i].penalty < Penalty::INFINITY,
409 Kind::Pen => items[i].penalty < Penalty::INFINITY,
410 Kind::Boxed(_) => false,
411 Kind::Mark(_) => false, // a mark clings to its word; the space after it may break
412 Kind::Anchor(_) => false, // a zero-width anchor never breaks; the glue beside it may
413 Kind::Math { .. } => false, // a maths box is rigid; the space after it may break
414 }
415}
416
417/// Is the item before glue `i` one a space can break after -- a word, a mark or a maths box? A zero-width
418/// [`Kind::Anchor`] is looked through, not counted: it neither is a breakable box nor blocks the space from
419/// breaking after the box before it, so a line carrying a margin anchor breaks exactly as the same line
420/// without one would. Without this the anchor would sit between a word and its trailing space and forbid
421/// the break there, moving the line ends of a paragraph that carries a claim code.
422fn prev_is_boxlike(items: &[Item], i: usize) -> bool {
423 let mut j = i;
424 while j > 0 {
425 j -= 1;
426 match items[j].kind {
427 Kind::Anchor(_) => continue, // look through it to the real box before
428 Kind::Boxed(_) | Kind::Mark(_) | Kind::Math { .. } => return true,
429 _ => return false,
430 }
431 }
432 false
433}
434
435/// Was the break at predecessor position `pos` flagged? The sentinel start (`-1`) never was.
436fn flagged_at(items: &[Item], pos: isize) -> bool {
437 pos >= 0 && items[pos as usize].flagged
438}
439
440/// The natural length of the line running `[lower, b)` and ending at the break `b`, given the width
441/// prefix sums `sw`. A discretionary break adds its hyphen glyph -- the width appears on the line only
442/// when the break is taken, which is exactly the standard Knuth-Plass discretionary rule.
443fn line_len(items: &[Item], sw: &[i64], lower: usize, b: usize) -> f64 {
444 let mut l = (sw[b] - sw[lower]) as f64;
445 if let Some(h) = &items[b].hyphen {
446 l += h.dims().width.raw() as f64;
447 }
448 l
449}
450
451/// One settled breakpoint: where it broke, which node it came from, and the running demerit total.
452struct Rec {
453 pos: isize, // item index of the break, or -1 for the paragraph start
454 prev: Option<usize>, // index into the node store of the line's start
455 total: f64,
456}
457
458/// The adjustment ratio for a line of natural length `l` set to `target`, given its total stretch
459/// `y` and shrink `z`. Positive stretches, negative shrinks; the float boundary the architecture
460/// permits at a ratio.
461fn ratio(target: f64, l: f64, y: f64, z: f64) -> f64 {
462 let diff = target - l;
463 if diff > 0.0 {
464 if y > 0.0 { diff / y } else { MAX_RATIO + 1.0 } // nothing to stretch: as good as too loose
465 } else if diff < 0.0 {
466 if z > 0.0 { diff / z } else { -2.0 } // nothing to shrink: overfull
467 } else {
468 0.0
469 }
470}
471
472/// The demerits of a line ending at a break of cost `pen`, with adjustment ratio `r`, following a
473/// flagged break iff `after_flagged` and being itself `flagged`.
474fn demerits(r: f64, pen: i32, flagged: bool, after_flagged: bool) -> f64 {
475 let bad = 100.0 * r.abs().powi(3);
476 let base = (LINE_PENALTY + bad).powi(2);
477 let mut d = base;
478 if pen >= 0 && pen < Penalty::INFINITY {
479 d += (pen as f64).powi(2);
480 } else if pen > Penalty::EJECT && pen < 0 {
481 d -= (pen as f64).powi(2);
482 }
483 // A forced break (pen <= EJECT) adds nothing beyond the base.
484 if flagged && after_flagged {
485 d += FLAGGED_DEMERIT;
486 }
487 d
488}
489
490/// Runs the active-node dynamic program and returns the chosen break positions in order, beginning
491/// with the sentinel start `-1` and ending at the forced end of the stream.
492///
493/// The fallback for an overfull line with no feasible break: when no active node can reach a break
494/// within tolerance -- a word wider than the measure, say -- and the break is forced or the active
495/// set would empty, the least-bad predecessor is taken anyway, so the program never dead-ends and
496/// the line is simply set overfull.
497fn optimal_breaks(items: &[Item], measure: Sp, justify: bool) -> Vec<isize> {
498 let n = items.len();
499 let target = measure.raw() as f64;
500
501 // Prefix sums to the point, in i64: a whole paragraph's width can exceed i32.
502 let mut sw = vec![0i64; n + 1];
503 let mut sy = vec![0i64; n + 1];
504 let mut sz = vec![0i64; n + 1];
505 for i in 0..n {
506 sw[i + 1] = sw[i] + items[i].width.raw() as i64;
507 sy[i + 1] = sy[i] + items[i].stretch.raw() as i64;
508 sz[i + 1] = sz[i] + items[i].shrink.raw() as i64;
509 }
510
511 let mut nodes: Vec<Rec> = vec![Rec { pos: -1, prev: None, total: 0.0 }];
512 let mut active: Vec<usize> = vec![0];
513
514 for b in 0..n {
515 if !is_break(items, b) {
516 continue;
517 }
518 let forced = matches!(items[b].kind, Kind::Pen) && items[b].penalty <= Penalty::EJECT;
519 let pen = items[b].penalty;
520 let flagged_b = items[b].flagged;
521
522 let mut best_feasible: Option<(usize, f64)> = None;
523 let mut best_forced: Option<(usize, f64)> = None; // least-bad, feasibility ignored
524 let mut dead: Vec<usize> = Vec::new();
525
526 for (k, &ni) in active.iter().enumerate() {
527 let a = nodes[ni].pos;
528 let lower = if a < 0 { 0usize } else { a as usize + 1 };
529 let l = line_len(items, &sw, lower, b);
530 let y = (sy[b] - sy[lower]) as f64;
531 // A ragged set never shrinks a space to fit: with no shrink capacity, a line naturally wider
532 // than the measure is infeasible, so the breaker takes an earlier break rather than letting the
533 // line overrun -- what a table cell wants, where an overrun would cross its column rule.
534 let z = if justify { (sz[b] - sz[lower]) as f64 } else { 0.0 };
535 let r = ratio(target, l, y, z);
536 let d = demerits(r, pen, flagged_b, flagged_at(items, a));
537 let total = nodes[ni].total + d;
538
539 if best_forced.map_or(true, |(_, t)| total < t) {
540 best_forced = Some((ni, total));
541 }
542 let feasible = r >= -1.0 && (forced || r <= MAX_RATIO);
543 if feasible && best_feasible.map_or(true, |(_, t)| total < t) {
544 best_feasible = Some((ni, total));
545 }
546 // A node whose line to b is overfull cannot reach any later break either; a forced break
547 // ends every line before it. Retire such nodes.
548 if r < -1.0 || forced {
549 dead.push(k);
550 }
551 }
552
553 for &k in dead.iter().rev() {
554 active.remove(k);
555 }
556
557 let chosen = best_feasible.or_else(|| {
558 if forced || active.is_empty() { best_forced } else { None }
559 });
560 if let Some((prev_ni, total)) = chosen {
561 nodes.push(Rec { pos: b as isize, prev: Some(prev_ni), total });
562 active.push(nodes.len() - 1);
563 }
564 }
565
566 // The terminal node is the one settled at the final forced break with the least total demerits.
567 let mut terminal: Option<usize> = None;
568 let mut best: f64 = f64::INFINITY;
569 for (idx, rec) in nodes.iter().enumerate() {
570 if rec.pos == (n as isize - 1) && rec.total <= best {
571 best = rec.total;
572 terminal = Some(idx);
573 }
574 }
575
576 let mut breaks = Vec::new();
577 let mut cur = terminal;
578 while let Some(idx) = cur {
579 breaks.push(nodes[idx].pos);
580 cur = nodes[idx].prev;
581 }
582 breaks.reverse(); // from the sentinel start to the forced end
583 breaks
584}
585
586/// Raises every drawn leaf of a line by `drop`, a negative shift added to whatever shift the leaf already
587/// carries -- so a footnote mark or a maths script, raised by its own shift or by a shortened box, keeps
588/// that raise relative to the text around it. It is how the block-edge model lifts a first line's glyphs to
589/// meet the cap-height top edge without disturbing anything set on the line.
590fn raise_leaves(list: &mut [Node], drop: Sp) {
591 for node in list.iter_mut() {
592 match node {
593 Node::Leaf(l) => l.shift = l.shift - drop,
594 Node::HBox(b) | Node::VBox(b) => raise_leaves(&mut b.list, drop),
595 _ => (),
596 }
597 }
598}
599
600/// Sets each chosen line as an HBox of shaped words and justified glue, joined by leading glue. A
601/// line ending at a forced break keeps natural spacing (flush left); every other line distributes
602/// its slack by the adjustment ratio.
603fn set_lines(
604 items: &[Item],
605 breaks: &[isize],
606 measure: Sp,
607 leading: Sp,
608 justify: bool,
609 fill: Rgba, // the fill every text box (and a taken hyphen) is coloured with as it becomes a leaf
610 // The block-edge model. `Some(cap)` seats the paragraph's top edge at the cap height `cap` rather than
611 // the face ascender, and its bottom edge at the baseline rather than the descender -- Typst's default
612 // `top-edge: "cap-height", bottom-edge: "baseline"`, which is what the inter-block glue (`par.skip`, a
613 // heading's before/after, a caption's framing) then attaches to. Within-paragraph line pitch is
614 // untouched: only the first line's height and the last line's depth move, and neither feeds the
615 // interline glue. `None` keeps the ascender/descender edges, for a context whose box edges are its own
616 // (a table cell measured to its inset, the standalone SVG preview).
617 cap: Option<Sp>,
618)
619 -> Outcome<Vec<Node>>
620{
621 let n = items.len();
622 let target = measure.raw() as f64;
623
624 let mut sw = vec![0i64; n + 1];
625 let mut sy = vec![0i64; n + 1];
626 let mut sz = vec![0i64; n + 1];
627 for i in 0..n {
628 sw[i + 1] = sw[i] + items[i].width.raw() as i64;
629 sy[i + 1] = sy[i] + items[i].stretch.raw() as i64;
630 sz[i + 1] = sz[i] + items[i].shrink.raw() as i64;
631 }
632
633 // Each set line, kept with its own height, depth and overshoot, so the interline glue between two of
634 // them can be sized from the depth of the upper and the height of the lower -- TeX's baselineskip
635 // rule, which a single line's own extent cannot give -- and opened further when the lower line
636 // carries inline maths that climbs above its own top.
637 let mut lines: Vec<(Node, Sp, Sp, Sp, Sp)> = Vec::new();
638 for w in breaks.windows(2) {
639 let a = w[0];
640 let hi = w[1] as usize;
641 let lower = if a < 0 { 0usize } else { a as usize + 1 };
642 let forced = matches!(items[hi].kind, Kind::Pen) && items[hi].penalty <= Penalty::EJECT;
643
644 let l = line_len(items, &sw, lower, hi);
645 let y = (sy[hi] - sy[lower]) as f64;
646 let z = (sz[hi] - sz[lower]) as f64;
647 let r = ratio(target, l, y, z);
648
649 let mut children: Vec<Node> = Vec::new();
650 let mut height = Sp::ZERO;
651 let mut depth = Sp::ZERO;
652 let mut over = Sp::ZERO; // how far any inline maths on the line climbs above the line top
653 let mut mdepth = Sp::ZERO; // depth owed to inline maths alone, kept as the block bottom edge
654 for item in items.iter().take(hi).skip(lower) {
655 match &item.kind {
656 Kind::Boxed(shaped) => {
657 // Every prose box takes the paragraph's fill as it becomes a drawn leaf; black leaves the
658 // glyph emitters' bytes exactly as before.
659 let leaf = Leaf::text(shaped.clone().with_colour(fill));
660 if leaf.dims.height > height { height = leaf.dims.height; }
661 if leaf.dims.depth > depth { depth = leaf.dims.depth; }
662 children.push(Node::Leaf(leaf));
663 },
664 Kind::Mark(leaf) => {
665 // The mark carries its own raised dims; a superscript is shorter than the line, so it
666 // takes the line's height from the words around it, not from itself.
667 let leaf = leaf.clone();
668 if leaf.dims.height > height { height = leaf.dims.height; }
669 if leaf.dims.depth > depth { depth = leaf.dims.depth; }
670 children.push(Node::Leaf(leaf));
671 },
672 Kind::Anchor(id) => {
673 // A zero-width marker: it draws no ink and takes no height or depth, so it neither
674 // advances the line's cursor nor raises its extent. The driver records where it landed
675 // when it places the line, which is the (x, y) the margin note is drawn against.
676 children.push(Node::Anchor(id.clone()));
677 },
678 Kind::Math { nodes, height: mh, depth: md, over: mo } => {
679 // The cluster's leaves are already seated by shift. It asks for the line's own text
680 // height so its baseline meets the prose; its depth may hang lower, opening the space
681 // below; and its overshoot opens the space above, so a tall fraction clears the line
682 // above rather than climbing into it.
683 if *mh > height { height = *mh; }
684 if *md > depth { depth = *md; }
685 if *md > mdepth { mdepth = *md; }
686 if *mo > over { over = *mo; }
687 for n in nodes {
688 children.push(n.clone());
689 }
690 },
691 Kind::Glued => {
692 // Justification lives in the glue: the natural space plus the ratio's share of its
693 // elasticity, so the driver's plain left-to-right pass fills the measure. A ragged set
694 // (a cell), or the natural-spaced last line of a paragraph, keeps the space at its
695 // natural width.
696 let nat = item.width;
697 let adj = if !justify || forced {
698 nat
699 } else if r >= 0.0 {
700 Sp(nat.raw() + (r * item.stretch.raw() as f64).round() as i32)
701 } else {
702 Sp(nat.raw() + (r * item.shrink.raw() as f64).round() as i32)
703 };
704 children.push(Node::Glue(Glue::new(adj, Sp::ZERO, Sp::ZERO)));
705 },
706 Kind::Pen => (), // an unchosen interior break sets no ink
707 }
708 }
709
710 // A taken discretionary draws its hyphen as the line's last box, in the paragraph's own fill.
711 if let Some(h) = &items[hi].hyphen {
712 let leaf = Leaf::text(h.clone().with_colour(fill));
713 if leaf.dims.height > height { height = leaf.dims.height; }
714 if leaf.dims.depth > depth { depth = leaf.dims.depth; }
715 children.push(Node::Leaf(leaf));
716 }
717
718 let dims = Dims::new(measure, height, depth);
719 lines.push((Node::HBox(BoxNode::new(children, dims)), height, depth, over, mdepth));
720 }
721
722 // The block-edge model, applied once the lines are set. The first line's top edge drops from the face
723 // ascender to the cap height, and the last line's bottom edge rises from the descender to the baseline
724 // (or to the depth of inline maths, which genuinely hangs below and must keep its room). This moves the
725 // box edges the inter-block glue attaches to, not the baselines: the drawer seats each glyph at the
726 // line-top plus the leaf's own ascent, so lifting the first line's top to the cap height would drop the
727 // glyphs unless they are raised to match -- hence `raise_leaves`, which shifts every leaf of the first
728 // line up by the same amount the top moved, keeping a footnote mark's or a script's raise intact. The
729 // interline glue below reads the untouched tuple metrics, and never a line's own height above it nor its
730 // own depth below it, so the within-paragraph pitch set by `leading` is left exactly as it was. A
731 // single-line paragraph is both first and last, and takes both edges.
732 if let Some(cap) = cap {
733 if let Some(first) = lines.first_mut() {
734 let natural = first.1; // the line's own ascent, from the untouched tuple
735 if natural > cap {
736 let drop = natural - cap;
737 if let Node::HBox(b) = &mut first.0 {
738 b.dims.height = cap;
739 raise_leaves(&mut b.list, drop);
740 }
741 }
742 }
743 if let Some(last) = lines.last_mut() {
744 let md = last.4;
745 if let Node::HBox(b) = &mut last.0 {
746 b.dims.depth = md;
747 }
748 }
749 }
750
751 // Assemble the vertical list: each line, then the glue to the next. The glue sets the baselines
752 // `leading` apart when the type is loose enough, and otherwise falls to a minimum so a tall line --
753 // one carrying an inline fraction, say -- opens the space it needs rather than climbing into the
754 // line above. The upper line's depth and the lower line's height are what the gap is measured from,
755 // so a line's own height never has to stand in for its neighbour's.
756 let heights: Vec<Sp> = lines.iter().map(|l| l.1).collect();
757 let overs: Vec<Sp> = lines.iter().map(|l| l.3).collect();
758 let count = lines.len();
759 let mut out = Vec::with_capacity(count * 2);
760 for (i, (node, _height, depth_above, _over, _mdepth)) in lines.into_iter().enumerate() {
761 out.push(node);
762 if i + 1 < count {
763 // The baselineskip glue, never less than the overshoot the lower line needs to clear the one
764 // above; a plain pair of prose lines wants neither, so the gap stays zero as before.
765 let want = leading - depth_above - heights[i + 1];
766 let mut gap = if want > Sp::ZERO { want } else { Sp::ZERO };
767 if overs[i + 1] > gap { gap = overs[i + 1]; }
768 out.push(Node::Glue(Glue::fixed(gap)));
769 }
770 }
771 Ok(out)
772}