fleuron/lines/line.rs
1//! A broken line: the runs on it, the spans it fills, and the
2//! widths that measure it.
3
4use std::ops::Range;
5
6use crate::content::{NodeId, SourceRange};
7use crate::fonts::{Features, ShapedGlyph};
8use crate::linebox::LineBox;
9use crate::style::{Color, TextDecoration};
10
11use super::flatten::FlatParagraph;
12use super::shape::ShapedSpan;
13
14/// A run of glyphs sharing one font and size — the paintable unit.
15#[derive(Debug, Clone, PartialEq)]
16pub struct ShapedRun {
17 /// Index into the registry that shaped the run.
18 pub font_id: u16,
19 /// Em size in points.
20 pub size: f32,
21 /// The text the run was shaped from. Glyph ids alone do not
22 /// spell anything, and the correspondence exists only in the
23 /// shaper's output.
24 pub text: String,
25 /// What the author wrote, where a transform made that differ
26 /// from what was shaped, and empty where the two are the same.
27 pub source: String,
28 /// The offset in `source` of every byte boundary of `text`.
29 /// Empty alongside `source`.
30 pub source_map: Vec<u32>,
31 /// Byte offset of `text` in the paragraph the glyphs' clusters
32 /// index.
33 pub text_start: u32,
34 /// Where the run was written: the node it was shaped from and
35 /// the bytes of that node's own text it stands for. `None` for
36 /// text no node was walked for: page furniture, an ornament.
37 pub origin: Option<SourceRange>,
38 /// The pseudo-element the run was cut from, where it was cut from
39 /// one.
40 pub pseudo_element: Option<NodeId>,
41 /// The innermost inline element the run came from: a link, an
42 /// emphasis, a strong, a code span. `None` on the text of the
43 /// paragraph itself.
44 pub inline: Option<NodeId>,
45 /// Points of space before the run's first glyph, from the leading
46 /// edges of the inline boxes that open on it.
47 pub lead: f32,
48 /// Points of space after its last glyph, from the trailing edges
49 /// of the ones that close on it.
50 pub trail: f32,
51 /// The features the run was shaped with.
52 pub features: Features,
53 /// What the run is painted in.
54 pub color: Color,
55 /// What is drawn across it: the rules `text-decoration` asks
56 /// for, each painted over the run's own advance.
57 pub decoration: TextDecoration,
58 /// The glyphs, in visual order.
59 pub glyphs: Vec<ShapedGlyph>,
60 /// Total advance of the run's glyphs, in font units. What an
61 /// inline box takes beside them is `lead` and `trail`, in points.
62 pub advance: u32,
63}
64
65impl ShapedRun {
66 /// The byte range in `text` each glyph stands for, in glyph
67 /// order. A glyph covers its cluster up to the next cluster that
68 /// starts later — which is how a ligature comes to span the
69 /// characters it swallowed.
70 pub fn glyph_ranges(&self) -> Vec<Range<u32>> {
71 let end = self.text.len() as u32;
72 let starts: Vec<u32> = self
73 .glyphs
74 .iter()
75 .map(|g| g.cluster.saturating_sub(self.text_start).min(end))
76 .collect();
77 starts
78 .iter()
79 .enumerate()
80 .map(|(i, start)| {
81 let next = starts[i + 1..]
82 .iter()
83 .find(|later| *later > start)
84 .copied()
85 .unwrap_or(end);
86 *start..next.max(*start)
87 })
88 .collect()
89 }
90}
91
92/// One span of a line: the runs set in it, and where they go.
93#[derive(Debug, Clone, PartialEq)]
94pub struct LineSpan {
95 /// The runs of `Line::runs` set here.
96 pub runs: Range<usize>,
97 /// Points from the line's own leading edge the span is set at.
98 pub offset: f32,
99 /// Advance of the span's glyphs, in font units.
100 pub width: u32,
101}
102
103/// The spans of one line, read as a slice either way. A band set
104/// undivided holds its span inline: the ordinary line of a book does
105/// not pay for an allocation.
106#[derive(Debug, Clone, PartialEq)]
107pub enum Spans {
108 /// The band was set in one span.
109 One(LineSpan),
110 /// It was divided, and these are its spans in reading order.
111 Many(Vec<LineSpan>),
112}
113
114impl std::ops::Deref for Spans {
115 type Target = [LineSpan];
116
117 fn deref(&self) -> &[LineSpan] {
118 match self {
119 Spans::One(span) => std::slice::from_ref(span),
120 Spans::Many(spans) => spans,
121 }
122 }
123}
124
125impl std::ops::DerefMut for Spans {
126 fn deref_mut(&mut self) -> &mut [LineSpan] {
127 match self {
128 Spans::One(span) => std::slice::from_mut(span),
129 Spans::Many(spans) => spans,
130 }
131 }
132}
133
134/// One inline element's box on one line: where it sits, and which of
135/// its edges it paints there.
136///
137/// An inline element covers as many lines as its runs reach, and one
138/// of these stands for what it takes on one of them. The edges the
139/// line break cut are open under `box-decoration-break: slice` and
140/// closed under `clone`.
141#[derive(Debug, Clone, Copy, PartialEq)]
142pub struct InlineFragment {
143 /// The inline element the box belongs to.
144 pub node: NodeId,
145 /// Which span of the line the box is set in, as an index into
146 /// `Line::spans`. An element covering two spans of one band has a
147 /// box in each of them.
148 pub span: usize,
149 /// Points from the leading edge of that span to the leading edge
150 /// of the border box. The span's own offset moves the box with
151 /// the text, which is what alignment moves.
152 pub x: f32,
153 /// Width of the border box, in points.
154 pub width: f32,
155 /// Points from the baseline up to the top of the border box.
156 pub above: f32,
157 /// Points from the baseline down to its bottom.
158 pub below: f32,
159 /// Whether the leading edge is painted here.
160 pub opens: bool,
161 /// Whether the trailing edge is.
162 pub closes: bool,
163}
164
165/// One typeset line: shaped runs plus its width in font units.
166///
167/// A line is a band of the page, which is set in one span or in
168/// several. The runs are in reading order across all of them.
169#[derive(Debug, Clone, PartialEq)]
170pub struct Line {
171 /// The line's runs, in visual order.
172 pub runs: Vec<ShapedRun>,
173 /// The spans the runs are divided between, in reading order.
174 pub spans: Spans,
175 /// The boxes the inline elements on the line paint there,
176 /// outermost first. Empty on the ordinary line of a book.
177 pub boxes: Vec<InlineFragment>,
178 /// Advance of the line's glyphs, trailing spaces excluded; a
179 /// hyphenated line's hyphen is charged here even though the glyph
180 /// joins the runs when the structured outpur paints it. What hangs
181 /// past the measure is charged here too, and taken off again by
182 /// `overhang` and `protrusion`.
183 pub width: u32,
184 /// Points the line's last glyph hangs past the measure.
185 pub overhang: f32,
186 /// Points the line's first glyph hangs before the line's origin.
187 pub protrusion: f32,
188 /// The line's vertical geometry — computed here, in points;
189 /// downstream stages position against it, never re-measure.
190 pub box_: LineBox,
191}
192
193impl Line {
194 /// Shaped runs as a line of one span: page furniture, an
195 /// ornament, an initial letter, and anything else set rather
196 /// than broken.
197 pub fn of(runs: Vec<ShapedRun>, box_: LineBox) -> Line {
198 let width = runs.iter().map(|run| run.advance).sum();
199 Line {
200 spans: Spans::One(LineSpan {
201 runs: 0..runs.len(),
202 offset: 0.0,
203 width,
204 }),
205 runs,
206 boxes: Vec::new(),
207 width,
208 overhang: 0.0,
209 protrusion: 0.0,
210 box_,
211 }
212 }
213
214 /// A band with nothing set in it yet.
215 pub(super) fn empty() -> Line {
216 Line {
217 runs: Vec::new(),
218 spans: Spans::Many(Vec::new()),
219 boxes: Vec::new(),
220 width: 0,
221 overhang: 0.0,
222 protrusion: 0.0,
223 box_: LineBox {
224 height: 0.0,
225 baseline: 0.0,
226 },
227 }
228 }
229}
230
231/// Prefix sums over the paragraph's shaped glyphs, in the
232/// paragraph's own font units: the width of any byte range is one
233/// subtraction.
234pub(super) struct Widths {
235 /// Advance of every glyph whose cluster starts before byte `i`.
236 text: Vec<f32>,
237 /// The same for space glyphs alone, which is where the glue is.
238 pub(super) spaces: Vec<f32>,
239 /// Whether a glyph's cluster starts at byte `i`. A break inside
240 /// a cluster would cut a ligature in half and lose it.
241 pub(super) starts: Vec<bool>,
242 /// Tracking charged to the last cluster starting before byte `i`.
243 /// Empty where nothing is tracked, which is most paragraphs.
244 trailing: Vec<f32>,
245 /// The inline boxes a break inside closes and opens again: their
246 /// byte range, their leading edge and their trailing edge, in
247 /// font units. Empty for every paragraph with no cloned box in
248 /// it, which is nearly all of them.
249 cloned: Vec<Cloned>,
250 /// Stretches set as they were written, which take no hyphen. An
251 /// inline code span is one.
252 literal: Vec<Range<usize>>,
253}
254
255/// One inline box that paints all four of its edges on every line it
256/// reaches, from `box-decoration-break: clone`.
257struct Cloned {
258 range: Range<usize>,
259 leading: f32,
260 trailing: f32,
261}
262
263impl Widths {
264 /// Whether a hyphen may be put at byte `at`: not inside a
265 /// cluster, whose glyph belongs to neither half of a break, and
266 /// not inside a stretch set as it was written.
267 pub(super) fn hyphenates(&self, at: usize) -> bool {
268 self.starts[at] && !self.literal.iter().any(|range| range.contains(&at))
269 }
270
271 /// The widths of one flattened paragraph, shaped. `units` takes a
272 /// length in points into the paragraph's own font units, which is
273 /// how an inline box's edges are charged beside the glyphs.
274 pub(super) fn build(flat: &FlatParagraph, shaped: &[ShapedSpan], units: f32) -> Widths {
275 let text = flat.text.as_str();
276 let tracked = shaped.iter().any(|span| span.tracking != 0.0);
277 let mut widths = Widths {
278 text: vec![0.0; text.len() + 1],
279 spaces: vec![0.0; text.len() + 1],
280 starts: vec![false; text.len() + 1],
281 trailing: if tracked {
282 vec![0.0; text.len() + 1]
283 } else {
284 Vec::new()
285 },
286 cloned: flat
287 .boxes
288 .iter()
289 .filter(|span| span.box_.cloned && !span.range.is_empty())
290 .map(|span| Cloned {
291 range: span.range.clone(),
292 leading: span.box_.leading() * units,
293 trailing: span.box_.trailing() * units,
294 })
295 .collect(),
296 literal: flat.literal.clone(),
297 };
298 let bytes = text.as_bytes();
299 for span in shaped {
300 for glyph in &span.glyphs {
301 let at = (span.range.start + glyph.cluster as usize).min(text.len());
302 let advance = glyph.x_advance as f32 * span.scale;
303 widths.text[at] += advance;
304 if bytes.get(at) == Some(&b' ') {
305 widths.spaces[at] += advance;
306 }
307 widths.starts[at] = true;
308 if tracked {
309 widths.trailing[at] = span.tracking;
310 }
311 }
312 }
313 // An inline box is width like any other: its leading edge
314 // falls at its first byte and its trailing edge at its last,
315 // so a line that holds either end is charged for it and one
316 // that runs through the middle is charged for neither.
317 for span in &flat.boxes {
318 if span.range.is_empty() {
319 continue;
320 }
321 widths.text[span.range.start] += span.box_.leading() * units;
322 widths.text[span.range.end - 1] += span.box_.trailing() * units;
323 }
324 // Exclusive prefixes: entry `i` totals the glyphs that
325 // start before byte `i`, which is exactly the glyphs on a line
326 // ending there.
327 let (mut text_total, mut space_total, mut track) = (0.0, 0.0, 0.0);
328 for at in 0..widths.text.len() {
329 let (here, space) = (widths.text[at], widths.spaces[at]);
330 widths.text[at] = text_total;
331 widths.spaces[at] = space_total;
332 text_total += here;
333 space_total += space;
334 if tracked {
335 let charged = widths.trailing[at];
336 widths.trailing[at] = track;
337 if widths.starts[at] {
338 track = charged;
339 }
340 }
341 }
342 widths
343 }
344
345 /// The advance of the glyphs in `[from, to)`, less the tracking
346 /// charged after the last of them: what runs between two letters
347 /// does not run past the last one.
348 pub(super) fn advance(&self, from: usize, to: usize) -> f32 {
349 if to <= from {
350 return 0.0;
351 }
352 self.text[to] - self.text[from] - self.trailing.get(to).copied().unwrap_or(0.0)
353 }
354
355 /// The same for a whole line, with the edges a cloned box closes
356 /// at the break and opens again after it.
357 ///
358 /// A box the line runs into the middle of paints its trailing
359 /// edge at the break, and one the line starts in the middle of
360 /// paints its leading edge at the line's own start. The edges at
361 /// the two true ends of the box are charged by `build`.
362 pub(super) fn line_advance(&self, from: usize, to: usize) -> f32 {
363 let mut width = self.advance(from, to);
364 for cloned in &self.cloned {
365 if from > cloned.range.start && from < cloned.range.end {
366 width += cloned.leading;
367 }
368 if to > cloned.range.start && to < cloned.range.end {
369 width += cloned.trailing;
370 }
371 }
372 width
373 }
374}
375
376/// One band's spans, leaving the buffer to the band after it.
377pub(super) fn gather(spans: &mut Vec<LineSpan>) -> Spans {
378 match spans.len() {
379 1 => Spans::One(spans.pop().expect("a span")),
380 _ => Spans::Many(std::mem::take(spans)),
381 }
382}
383
384/// Slices shaped spans into the runs of one line. `end` is where the
385/// line's paintable text stops: the spaces a break swallows are
386/// already off it.
387///
388/// A run records the text it was shaped from, which is what a
389/// painter that draws characters draws, and beside it what the
390/// author wrote, which is what extraction and copy and paste return.
391pub(super) fn cut_runs(
392 flat: &FlatParagraph,
393 shaped: &[ShapedSpan],
394 start: usize,
395 end: usize,
396) -> Vec<ShapedRun> {
397 let mut runs = Vec::new();
398 let mut trailing = 0i64;
399 for (span, spec) in shaped.iter().zip(flat.spans.iter()) {
400 if span.range.start >= end || span.range.end <= start {
401 continue;
402 }
403 let glyphs = span.glyphs_in(start, end);
404 if glyphs.is_empty() {
405 continue;
406 }
407 let advance = glyphs.iter().map(|g| g.x_advance).sum();
408 let text_start = span.range.start.max(start);
409 let text_end = span.range.end.min(end).max(text_start);
410 trailing = span.track;
411 let (source, source_map) = flat.source_of(text_start..text_end);
412 runs.push(ShapedRun {
413 font_id: spec.font_id,
414 size: spec.size,
415 text: flat.text[text_start..text_end].to_string(),
416 source,
417 source_map,
418 text_start: text_start as u32,
419 // Where the run was written is settled once the
420 // paragraph is broken, by `tile`.
421 origin: None,
422 pseudo_element: None,
423 inline: spec.inline,
424 lead: 0.0,
425 trail: 0.0,
426 features: spec.features.clone(),
427 color: spec.color,
428 decoration: spec.decoration,
429 glyphs,
430 advance,
431 });
432 }
433 // Tracking goes between letters: the line's last glyph keeps its
434 // own advance and nothing more.
435 if trailing != 0
436 && let Some(run) = runs.last_mut()
437 {
438 if let Some(glyph) = run.glyphs.last_mut() {
439 glyph.x_advance = (glyph.x_advance as i64 - trailing).max(0) as u32;
440 }
441 run.advance = run.glyphs.iter().map(|g| g.x_advance).sum();
442 }
443 runs
444}
445
446/// Says where each of a paragraph's runs was written, each range
447/// running on to where the next one starts, so the space a break
448/// swallowed belongs to a run rather than to nothing and the runs
449/// naming one node tile that node's text.
450pub(super) fn tile(lines: &mut [Line], flat: &FlatParagraph) {
451 let starts: Vec<usize> = lines
452 .iter()
453 .flat_map(|line| &line.runs)
454 .map(|run| run.text_start as usize)
455 .collect();
456 let mut ends = starts.iter().skip(1).copied().chain([flat.text.len()]);
457 let mut after = None;
458 for run in lines.iter_mut().flat_map(|line| &mut line.runs) {
459 let to = ends.next().unwrap_or(flat.text.len());
460 run.origin = flat.origin_of(after, run.text_start as usize, to);
461 run.pseudo_element = flat.pseudo_element_of(run.origin.as_ref(), run.text_start as usize);
462 after = run.origin.as_ref().map(|origin| origin.node);
463 }
464}
465
466#[cfg(test)]
467mod tests {
468 use crate::lines::testing::layout_body;
469
470 /// A run's glyphs map back to the characters they were shaped
471 /// from: the ffi ligature is one glyph spanning three bytes, and
472 /// the ranges tile the run's text without gaps.
473 #[test]
474 fn glyph_ranges_cover_the_run_text() {
475 let lines = layout_body("difficult", 200.0);
476 let run = &lines[0].runs[0];
477 assert_eq!(run.text, "difficult");
478 let ranges = run.glyph_ranges();
479 assert_eq!(
480 ranges.first().cloned(),
481 Some(0..1),
482 "the first glyph stands for the first byte"
483 );
484 assert!(
485 ranges.iter().any(|r| r.end - r.start == 3),
486 "no glyph spans the three characters of the ffi ligature: {ranges:?}"
487 );
488 assert_eq!(
489 ranges.last().map(|r| r.end),
490 Some(run.text.len() as u32),
491 "the last glyph runs to the end of the run's text"
492 );
493 for pair in ranges.windows(2) {
494 assert!(
495 pair[1].start == pair[0].end || pair[1].start == pair[0].start,
496 "ranges neither tile nor share a cluster: {pair:?}"
497 );
498 }
499 }
500}