Skip to main content

docling_pdf/
dp_lines.rs

1//! Port of docling-parse's line-cell sanitizer
2//! (`src/parse/page_item_sanitators/cells.h` → `create_line_cells` /
3//! `contract_cells_into_lines_v1`). It merges per-glyph char cells into line
4//! cells via a 3-pass contraction — left-to-right, right-to-left, then
5//! left-to-right with reverse — using corner-distance adjacency and inserting at
6//! most one space per merge. This reproduces docling-parse's inter-word spacing
7//! (justified double spaces, the space before a `:`, and RTL ordering) that an
8//! ad-hoc gap-heuristic reconstruction can't.
9//!
10//! Geometry uses native PDF coordinates (y increases upward); each cell carries
11//! its four transformed corners r0=bottom-left, r1=bottom-right, r2=top-right,
12//! r3=top-left, exactly like `page_cell.h`.
13
14use crate::pdfium_backend::{Glyph, TextCell};
15
16// config.h: the factors that actually bind for line cells.
17const MERGE: f64 = 1.0; // line_space_width_factor_for_merge (adjacency gate)
18const MERGE_WITH_SPACE: f64 = 0.33; // line_space_width_factor_for_merge_with_space
19
20// create_word_cells: words contract under their own, tighter factors — the
21// adjacency gate is word_space_width_factor_for_merge (0.33) and the space
22// threshold is twice that (2.0 * 0.33), which the 0.33 gate can never exceed,
23// so a word cell never contains an inserted space. Space glyphs are hard
24// word-boundary barriers during the contraction (`applicable`'s
25// `block_spaces`) and are erased only afterwards, as docling-parse does.
26const WORD_MERGE: f64 = 0.33; // word_space_width_factor_for_merge
27const WORD_MERGE_WITH_SPACE: f64 = 2.0 * WORD_MERGE;
28const H_TOL: f64 = 1.0; // horizontal_cell_tolerance (ligature eps_d1 relaxation)
29
30#[derive(Clone)]
31struct Cell {
32    text: String,
33    rx0: f64,
34    ry0: f64, // bottom-left
35    rx1: f64,
36    ry1: f64, // bottom-right
37    rx2: f64,
38    ry2: f64, // top-right
39    rx3: f64,
40    ry3: f64, // top-left
41    ltr: bool,
42    active: bool,
43    lig_carry: bool, // last_merged_cell_was_ligature
44    font: u64,       // hash of docling-parse's font name (for enforce_same_font)
45    // Cached invariants of `text` / the quad, maintained by `build_cells` and
46    // `merge_with`. The contraction is quadratic in merge attempts, and
47    // recomputing these per attempt (trim/char-count/ligature scans over the
48    // *growing* line text, min/max over the quad) dominated large-page
49    // parsing — the caches turn every attempt into flag reads.
50    blank: bool,   // text.trim().is_empty()
51    lig: bool,     // is_ligature(&text)
52    fb: bool,      // any char in U+FB00..=U+FB06 (the range half of is_ligature)
53    nchars: usize, // text.chars().count()
54    b_l: f64,      // bounds(): axis-aligned quad extremes
55    b_r: f64,
56    b_b: f64,
57    b_t: f64,
58    /// The pen's origin and the font size, `[x, y, size]` ([`Glyph::pen`]),
59    /// for the word contraction's baseline test (#921).
60    pen: Option<[f64; 3]>,
61    /// The glyph's font is a math face ([`Glyph::math_font`]).
62    math_font: bool,
63}
64
65impl Cell {
66    /// Length of the bottom edge (baseline advance) — `page_cell.h::length`.
67    fn length(&self) -> f64 {
68        ((self.rx1 - self.rx0).powi(2) + (self.ry1 - self.ry0).powi(2)).sqrt()
69    }
70
71    /// Running mean glyph advance over the whole accumulated cell.
72    fn avg_char_width(&self) -> f64 {
73        if self.nchars > 0 {
74            self.length() / self.nchars as f64
75        } else {
76            0.0
77        }
78    }
79
80    /// Distance from this cell's bottom-right corner to `other`'s bottom-left.
81    fn gap(&self, other: &Cell) -> f64 {
82        ((self.rx1 - other.rx0).powi(2) + (self.ry1 - other.ry0).powi(2)).sqrt()
83    }
84
85    /// `is_adjacent_to`: both the bottom-corner gap (`< eps0`) and the top-corner
86    /// gap (`< eps1`) must be small. The vertical component keeps different
87    /// baselines/lines from merging.
88    fn adjacent(&self, other: &Cell, eps0: f64, eps1: f64) -> bool {
89        let d0 = self.gap(other);
90        let d1 = ((self.rx2 - other.rx3).powi(2) + (self.ry2 - other.ry3).powi(2)).sqrt();
91        d0 < eps0 && d1 < eps1
92    }
93
94    /// Punctuation/space cells are bidi-neutral bridges.
95    fn same_orientation(&self, other: &Cell) -> bool {
96        self.ltr == other.ltr || is_punct_or_space(&self.text) || is_punct_or_space(&other.text)
97    }
98
99    /// `merge_with`: absorb `other` (which lies to this cell's right). Insert at
100    /// most one separator space when the gap exceeds `delta`. RTL prepends.
101    ///
102    /// `euclidean` picks the gap measure: docling-parse uses the **Euclidean
103    /// corner distance** `d0` (the same one `is_adjacent_to` uses). The pure-Rust
104    /// parser produces clean advance boxes, so it uses `d0` to match docling
105    /// byte-for-byte. pdfium's loose boxes overhang (an `f` extends left and
106    /// overlaps its neighbour), which a Euclidean distance reads as a false
107    /// positive gap and over-inserts spaces (`Self` → `Sel f`); that path keeps
108    /// the **signed horizontal gap** instead.
109    fn merge_with(&mut self, other: &Cell, delta: f64, euclidean: bool) {
110        let gap = if euclidean {
111            self.gap(other)
112        } else {
113            other.rx0 - self.rx1
114        };
115        let space = delta < gap;
116        if !self.ltr || !other.ltr {
117            if space {
118                self.text.insert(0, ' ');
119            }
120            self.text = format!("{}{}", other.text, self.text);
121            self.ltr = false;
122        } else {
123            if space {
124                self.text.push(' ');
125            }
126            self.text.push_str(&other.text);
127            self.ltr = true;
128        }
129        // Extend the right edge to `other`.
130        self.rx1 = other.rx1;
131        self.ry1 = other.ry1;
132        self.rx2 = other.rx2;
133        self.ry2 = other.ry2;
134        // Cache upkeep. Blankness and the ligature char-range scan distribute
135        // over concatenation (the inserted separator is whitespace and not in
136        // the range); the equality patterns ("ff", "fi", …) do NOT — "fi" is a
137        // ligature cell, "fiction" is not — so a short merged text recomputes
138        // exactly and a longer one (which no equality pattern can match) falls
139        // back to the distributed range flag alone.
140        self.blank = self.blank && other.blank;
141        self.nchars += other.nchars + usize::from(space);
142        self.fb = self.fb || other.fb;
143        self.lig = if self.text.len() <= 3 {
144            is_ligature(&self.text)
145        } else {
146            self.fb
147        };
148        let (l, r, b, t) = quad_bounds(self);
149        self.b_l = l;
150        self.b_r = r;
151        self.b_b = b;
152        self.b_t = t;
153    }
154}
155
156/// Axis-aligned bounds of a cell's quad, `(l, r, b, t)` in PDF points (y-up),
157/// from the cache `merge_with` maintains.
158fn bounds(c: &Cell) -> (f64, f64, f64, f64) {
159    (c.b_l, c.b_r, c.b_b, c.b_t)
160}
161
162/// The cached bounds' source of truth: min/max over the quad corners.
163fn quad_bounds(c: &Cell) -> (f64, f64, f64, f64) {
164    let xs = [c.rx0, c.rx1, c.rx2, c.rx3];
165    let ys = [c.ry0, c.ry1, c.ry2, c.ry3];
166    let fold = |it: &[f64], f: fn(f64, f64) -> f64| it.iter().copied().reduce(f).unwrap();
167    (
168        fold(&xs, f64::min),
169        fold(&xs, f64::max),
170        fold(&ys, f64::min),
171        fold(&ys, f64::max),
172    )
173}
174
175/// Is another active cell painted inside the horizontal gap between `i` and
176/// `j`? The contraction walks cells in **stream** order, and a generator that
177/// draws a line's bold runs after its regular text leaves them as later cells
178/// — the space tolerance would then stitch `C.[ ]Zur Wahrung …` straight
179/// across the hole where the bold `6.` sits, and the stranded token ends up at
180/// the line's end ("… wenn Sie die Mitteilung 6."). An occupied gap is not a
181/// gap. Space-only cells never block (they *are* the gap), and the scan is
182/// skipped entirely for glyph-adjacent merges (no room for anything).
183fn gap_occupied(cells: &[Cell], i: usize, j: usize) -> bool {
184    let (al, ar, ab, at) = bounds(&cells[i]);
185    let (bl, br, bb, bt) = bounds(&cells[j]);
186    let (gl, gr) = if ar <= bl { (ar, bl) } else { (br, al) };
187    if gr - gl < 0.5 {
188        return false; // touching or overlapping — nothing fits in between
189    }
190    let (band_b, band_t) = (ab.min(bb), at.max(bt));
191    cells.iter().enumerate().any(|(k, c)| {
192        if k == i || k == j || !c.active || c.blank {
193            return false;
194        }
195        let (cl, cr, cb, ct) = bounds(c);
196        // Vertically on this line: most of the candidate inside the pair's band.
197        let overlap = (ct.min(band_t) - cb.max(band_b)).max(0.0);
198        overlap > 0.5 * (ct - cb).max(f64::EPSILON)
199            // Horizontally: real ink inside the gap interval.
200            && cr.min(gr) - cl.max(gl) > 0.1
201    })
202}
203
204/// `applicable_for_merge`: both active and same reading orientation. A different
205/// font normally blocks the merge (keeps a bold label and its value as separate
206/// line cells). On the clean-box parser path, **punctuation/space cells bridge
207/// fonts** so a sentence period set in a separate punctuation font joins its word
208/// instead of fragmenting (`العمل .` → `العمل.`); letters still enforce the font.
209fn applicable(a: &Cell, b: &Cell, parser: bool, block_spaces: bool) -> bool {
210    if !a.active || !b.active {
211        return false;
212    }
213    // Word mode (`block_spaces`): a space glyph is a hard word-boundary barrier
214    // that never merges in either direction; the space cells themselves are
215    // erased after the contraction (`create_word_cells`).
216    if block_spaces && (is_all_space(&a.text) || is_all_space(&b.text)) {
217        return false;
218    }
219    // A lone punctuation glyph (not a space) set in a separate punctuation font
220    // bridges fonts so it joins its word — but only next to RTL text. In LTR a
221    // different-font punctuation (e.g. a bold `:`) is a real run boundary docling
222    // keeps spaced (`Laboratories :`); in Arabic the sentence period sits in a
223    // Latin punctuation font yet attaches (`العمل.`). Parser path only.
224    let lone_punct = |s: &str| {
225        let mut ch = s.chars();
226        matches!(ch.next(), Some(c) if c != ' ' && is_punct_or_space(&c.to_string()))
227            && ch.next().is_none()
228    };
229    let punct_bridge =
230        parser && ((lone_punct(&a.text) && !b.ltr) || (lone_punct(&b.text) && !a.ltr));
231    let font_neutral = a.lig || b.lig || punct_bridge;
232    if a.font != 0 && b.font != 0 && a.font != b.font && !font_neutral {
233        return false;
234    }
235    a.same_orientation(b)
236}
237
238/// Left-to-right pass: `i` ascending accumulates cells to its right.
239fn pass_ltr(cells: &mut [Cell], allow_reverse: bool, euclidean: bool, p: Factors) {
240    for i in 0..cells.len() {
241        if !cells[i].active {
242            continue;
243        }
244        let mut j = i + 1;
245        while j < cells.len() {
246            if !applicable(&cells[i], &cells[j], euclidean, p.block_spaces) {
247                break;
248            }
249            let i_lig = cells[i].lig || cells[i].lig_carry;
250            let j_lig = cells[j].lig || cells[j].lig_carry;
251            let d0 = cells[i].avg_char_width() * p.merge;
252            let d1 = cells[i].avg_char_width() * p.merge_with_space;
253            let adj_d1 = d0 + if i_lig || j_lig { H_TOL } else { 0.0 };
254            if cells[i].adjacent(&cells[j], d0, adj_d1) && !gap_occupied(cells, i, j) {
255                let other = cells[j].clone();
256                cells[i].merge_with(&other, d1, euclidean);
257                cells[i].lig_carry = other.lig;
258                cells[j].active = false;
259                j += 1; // i keeps absorbing the next cell to its right
260            } else if allow_reverse
261                && cells[j].adjacent(&cells[i], d0, adj_d1)
262                && !gap_occupied(cells, j, i)
263            {
264                let other = cells[i].clone();
265                cells[j].merge_with(&other, d1, euclidean);
266                cells[j].lig_carry = other.lig;
267                cells[i].active = false;
268                break; // i is consumed
269            } else {
270                break;
271            }
272        }
273    }
274}
275
276/// Right-to-left pass: `i` descending; its immediate left neighbour `i-1`
277/// absorbs it (then the outer loop continues leftward through the absorber).
278fn pass_rtl(cells: &mut [Cell], euclidean: bool, p: Factors) {
279    let n = cells.len();
280    for k in 0..n {
281        let i = n - 1 - k;
282        if !cells[i].active || i == 0 {
283            continue;
284        }
285        let j = i - 1;
286        if !applicable(&cells[i], &cells[j], euclidean, p.block_spaces) {
287            continue;
288        }
289        let i_lig = cells[i].lig || cells[i].lig_carry;
290        let j_lig = cells[j].lig || cells[j].lig_carry;
291        let d0 = cells[i].avg_char_width() * p.merge;
292        let d1 = cells[i].avg_char_width() * p.merge_with_space;
293        let adj_d1 = d0 + if i_lig || j_lig { H_TOL } else { 0.0 };
294        if cells[j].adjacent(&cells[i], d0, adj_d1) && !gap_occupied(cells, j, i) {
295            let other = cells[i].clone();
296            cells[j].merge_with(&other, d1, euclidean);
297            cells[j].lig_carry = other.lig;
298            cells[i].active = false;
299        }
300    }
301}
302
303/// The contraction's tuning: the adjacency-gate and space-insertion factors
304/// (per `sanitize_bbox`'s callers) plus the word mode's space barrier.
305#[derive(Clone, Copy)]
306struct Factors {
307    merge: f64,
308    merge_with_space: f64,
309    block_spaces: bool,
310}
311
312const LINE_FACTORS: Factors = Factors {
313    merge: MERGE,
314    merge_with_space: MERGE_WITH_SPACE,
315    block_spaces: false,
316};
317const WORD_FACTORS: Factors = Factors {
318    merge: WORD_MERGE,
319    merge_with_space: WORD_MERGE_WITH_SPACE,
320    block_spaces: true,
321};
322
323/// True when the cell's text is entirely whitespace (`utils::string::is_space`).
324fn is_all_space(s: &str) -> bool {
325    !s.is_empty() && s.chars().all(char::is_whitespace)
326}
327
328fn contract(cells: &mut Vec<Cell>, euclidean: bool, p: Factors) {
329    pass_ltr(cells, false, euclidean, p);
330    cells.retain(|c| c.active);
331    pass_rtl(cells, euclidean, p);
332    cells.retain(|c| c.active);
333    pass_ltr(cells, true, euclidean, p);
334    cells.retain(|c| c.active);
335}
336
337/// Build per-glyph char cells from a page's glyph stream (shared by the line and
338/// word paths): drop degenerate spaces, recompose ligatures, init word segments.
339fn build_cells(glyphs: &[Glyph], euclidean: bool) -> Vec<Cell> {
340    let mut cells: Vec<Cell> = Vec::new();
341    for g in glyphs {
342        // Use the loose box (uniform font ascent/descent + advance) so adjacent
343        // glyphs share a top edge, matching docling-parse's `compute_rect`.
344        if !g.ll.is_finite() {
345            continue;
346        }
347        // The char cell's quad: the loose rectangle for upright text, the
348        // glyph's own rotated quad otherwise (#528) — the contraction below
349        // works on corners and edge lengths, so it reads a 90°/180°/270° line
350        // in its own reading order, exactly like docling-parse.
351        let q = g.quad.map(|q| q.map(f64::from)).unwrap_or_else(|| {
352            let (l, b, r, t) = (g.ll as f64, g.lb as f64, g.lr as f64, g.lt as f64);
353            [l, b, r, b, r, t, l, t]
354        });
355        // Drop *degenerate* space glyphs (zero-width loose box): pdfium's generated
356        // spaces get a zero-width box at the wrong baseline that breaks the
357        // corner-distance adjacency. Without them the inter-word gap drives
358        // `merge_with`'s space insertion. Spaces with a real width are kept (they
359        // carry justified double-space information). The width is the baseline
360        // edge — a rotated glyph's x extent is its em height.
361        if g.ch == ' ' && (q[2] - q[0]).hypot(q[3] - q[1]) < 0.5 {
362            continue;
363        }
364        // Recompose a ligature: pdfium decomposes one font glyph (Latin fi/ffi,
365        // Arabic lam-alef) into several chars at the *same* loose box. Append them
366        // into one cell so the contraction never inserts a space inside it.
367        // "Same box": both baseline corners match as points, upright or
368        // rotated. A ligature's chars share one box, baseline included; glyphs
369        // stacked one under another at the same x (a chart's y-axis ticks
370        // `3`…`8`, each placed by its own `cm`) are separate cells — comparing
371        // the x span alone glued those into one `345678` cell carrying the
372        // first tick's box (#609), where docling-parse keeps six.
373        if let Some(last) = cells.last_mut() {
374            let near =
375                |ax: f64, ay: f64, bx: f64, by: f64| (ax - bx).abs() < 0.5 && (ay - by).abs() < 0.5;
376            if near(last.rx0, last.ry0, q[0], q[1]) && near(last.rx1, last.ry1, q[2], q[3]) {
377                // Overprint duplicate: the *same* character re-stamped, offset by a
378                // fraction of its width (a kashida/elongation segment re-drawn for
379                // weight). docling-parse drops it; appending over-counts
380                // (right_to_left_02's `قويووووة` vs `قويوووة`). Require a real offset
381                // (> 0.1) so a ligature expansion — which decomposes one glyph into
382                // several chars at the *identical* box (`ff`→`ff`, diff ≈ 0) — is still
383                // recomposed; real doubled letters sit a full advance apart (> 0.5).
384                let offset = match g.quad {
385                    None => (q[0] - last.rx0).abs(),
386                    Some(_) => (q[0] - last.rx0).hypot(q[1] - last.ry0),
387                };
388                if euclidean && offset > 0.1 && last.text.ends_with(g.ch) {
389                    continue;
390                }
391                last.text.push(g.ch);
392                last.ltr = !is_right_to_left(&last.text);
393                last.blank = last.blank && g.ch.is_whitespace();
394                last.nchars += 1;
395                // Recomposed ligature cells stay tiny; recomputing is exact.
396                last.fb = last.fb || (0xFB00..=0xFB06).contains(&(g.ch as u32));
397                last.lig = is_ligature(&last.text);
398                continue;
399            }
400        }
401        let text = g.ch.to_string();
402        let ltr = !is_right_to_left(&text);
403        let blank = g.ch.is_whitespace();
404        let lig = is_ligature(&text);
405        let fb = (0xFB00..=0xFB06).contains(&(g.ch as u32));
406        cells.push(Cell {
407            text,
408            rx0: q[0],
409            ry0: q[1],
410            rx1: q[2],
411            ry1: q[3],
412            rx2: q[4],
413            ry2: q[5],
414            rx3: q[6],
415            ry3: q[7],
416            ltr,
417            active: true,
418            lig_carry: false,
419            font: g.font,
420            blank,
421            lig,
422            fb,
423            nchars: 1,
424            b_l: (g.ll as f64).min(g.lr as f64),
425            b_r: (g.ll as f64).max(g.lr as f64),
426            b_b: (g.lb as f64).min(g.lt as f64),
427            b_t: (g.lb as f64).max(g.lt as f64),
428            pen: g.pen.map(|p| p.map(f64::from)),
429            math_font: g.math_font,
430        });
431    }
432    cells
433}
434
435/// Build line cells from a page's glyph stream under the process's word-gap
436/// rule (`DOCLING_RS_PDF_WORD_GAP`, #921).
437pub(crate) fn line_cells(glyphs: &[Glyph], page_h: f32, euclidean: bool) -> Vec<TextCell> {
438    line_and_word_cells_with(glyphs, page_h, euclidean, WordGap::from_env()).0
439}
440
441/// Build **word** cells from a page's glyph stream via docling-parse's
442/// `create_word_cells`: a second contraction over the same char cells under the
443/// word factors — adjacency gate 0.33 (vs the line's 1.0), so a gap wide enough
444/// to become a line-internal space still merges glyphs into one spaceless word
445/// when it stays under the gate (tight-set Korean: line `1군 감염병`, word
446/// `1군감염병`); real space glyphs are hard barriers and are erased afterwards.
447/// These are the per-word tokens TableFormer matches table-grid cells against.
448pub(crate) fn word_cells(glyphs: &[Glyph], page_h: f32, euclidean: bool) -> Vec<TextCell> {
449    line_and_word_cells_with(glyphs, page_h, euclidean, WordGap::from_env()).1
450}
451
452/// Build the line cells **and** the word cells from one shared glyph build
453/// under docling-parse ≤ 6's contraction ([`WordGap::Legacy`]): the char
454/// cells are constructed once and contracted twice, under the line factors
455/// and the word factors respectively — exactly docling-parse's
456/// `create_line_cells` + `create_word_cells` pair. The tests pin the legacy
457/// contraction through it; production goes through the process's rule.
458#[cfg(test)]
459pub(crate) fn line_and_word_cells(
460    glyphs: &[Glyph],
461    page_h: f32,
462    euclidean: bool,
463) -> (Vec<TextCell>, Vec<TextCell>) {
464    line_and_word_cells_with(glyphs, page_h, euclidean, WordGap::Legacy)
465}
466
467/// [`line_and_word_cells`] under the word-gap rule `gap` (#921): the legacy
468/// contraction, or docling-parse ≥ 7's line runs.
469pub(crate) fn line_and_word_cells_with(
470    glyphs: &[Glyph],
471    page_h: f32,
472    euclidean: bool,
473    gap: WordGap,
474) -> (Vec<TextCell>, Vec<TextCell>) {
475    let built = build_cells(glyphs, euclidean);
476    if gap != WordGap::Legacy {
477        return contract_runs(&built, gap, page_h);
478    }
479    let to_text_cell = |c: Cell| {
480        let l = c.rx0.min(c.rx1).min(c.rx2).min(c.rx3) as f32;
481        let r = c.rx0.max(c.rx1).max(c.rx2).max(c.rx3) as f32;
482        let top = c.ry0.max(c.ry1).max(c.ry2).max(c.ry3) as f32;
483        let bot = c.ry0.min(c.ry1).min(c.ry2).min(c.ry3) as f32;
484        TextCell {
485            text: c.text,
486            l,
487            t: page_h - top,
488            r,
489            b: page_h - bot,
490        }
491    };
492    // Word run: docling-parse's `create_word_cells` order — copy the char
493    // cells, contract (`sanitize_bbox`), *then* erase the spaces. The space
494    // glyphs stay in the stream during the contraction, where `applicable`'s
495    // `block_spaces` makes each one a hard word boundary; they are dropped
496    // afterwards by the blank filter below. Filtering them out up front let
497    // the 0.33 gate alone decide word breaks, which glues tight-set Latin
498    // (`MODE` + `to`: 1.8 pt apart under a 2.0 pt gate → `MODEto`) and the
499    // thin-spaced Korean docling-parse ≥ 7 keeps apart (`1군` `감염병`).
500    let mut word_run: Vec<Cell> = built.clone();
501    let mut cells = built;
502    contract(&mut cells, euclidean, LINE_FACTORS);
503    let lines = to_text_cells(cells, to_text_cell);
504    contract(&mut word_run, euclidean, WORD_FACTORS);
505    word_run.retain(|c| !c.text.trim().is_empty());
506    let words = to_text_cells(word_run, to_text_cell);
507    (lines, words)
508}
509
510/// Map the contracted cells into a freshly allocated, exactly sized vector.
511///
512/// A plain `into_iter().map(..).collect()` would take std's in-place-collect
513/// path and hand back the *input's* allocation: one ~150-byte [`Cell`] slot per
514/// glyph of the page, reinterpreted as ~4× as many 40-byte [`TextCell`] slots,
515/// while the contraction leaves a few glyphs per cell. Callers keep these
516/// vectors for the whole document (the text-layer path holds every page), so
517/// the dead capacity added up to ~30× the cells' real size — gigabytes on a
518/// long table-heavy PDF.
519fn to_text_cells(cells: Vec<Cell>, f: impl Fn(Cell) -> TextCell) -> Vec<TextCell> {
520    let mut out = Vec::with_capacity(cells.len());
521    out.extend(cells.into_iter().map(f));
522    out
523}
524
525fn is_rtl_char(c: char) -> bool {
526    let ch = c as u32;
527    (0x0600..=0x06FF).contains(&ch)
528        || (0x0750..=0x077F).contains(&ch)
529        || (0x08A0..=0x08FF).contains(&ch)
530        || (0xFB50..=0xFDFF).contains(&ch)
531        || (0xFE70..=0xFEFF).contains(&ch)
532        || (0x0590..=0x05FF).contains(&ch)
533        || (0xFB1D..=0xFB4F).contains(&ch)
534        || (0x0700..=0x074F).contains(&ch)
535        || (0x0780..=0x07BF).contains(&ch)
536        || (0x07C0..=0x07FF).contains(&ch)
537}
538
539/// All codepoints are RTL-script (matches `string.h::is_right_to_left`).
540fn is_right_to_left(s: &str) -> bool {
541    !s.is_empty() && s.chars().all(is_rtl_char)
542}
543
544/// A single-codepoint punctuation/space cell (matches `string.h`).
545fn is_punct_or_space(s: &str) -> bool {
546    let mut chars = s.chars();
547    let (Some(c), None) = (chars.next(), chars.next()) else {
548        return false;
549    };
550    if matches!(
551        c,
552        ' ' | '\t'
553            | '\n'
554            | '\r'
555            | '\u{0c}'
556            | '\u{0b}'
557            | '.'
558            | ','
559            | ';'
560            | ':'
561            | '!'
562            | '?'
563            | '('
564            | ')'
565            | '['
566            | ']'
567            | '{'
568            | '}'
569            | '\''
570            | '"'
571            | '`'
572            | '\u{2018}'
573            | '\u{2019}'
574            | '\u{201c}'
575            | '\u{201d}'
576            | '-'
577            | '\u{2013}'
578            | '\u{2014}'
579            | '_'
580            | '/'
581            | '\\'
582            | '|'
583            | '@'
584            | '#'
585            | '%'
586            | '&'
587            | '*'
588            | '+'
589            | '='
590            | '<'
591            | '>'
592    ) {
593        return true;
594    }
595    let ch = c as u32;
596    (0x2000..=0x206F).contains(&ch)
597        || (0x3000..=0x303F).contains(&ch)
598        || (0xFE50..=0xFE6F).contains(&ch)
599        || (0xFF00..=0xFF0F).contains(&ch)
600        || (0xFF1A..=0xFF1F).contains(&ch)
601        || (0xFF3B..=0xFF5E).contains(&ch)
602}
603
604/// Ligature glyph or its ASCII spelling (matches `string.h::is_ligature`).
605fn is_ligature(s: &str) -> bool {
606    matches!(s, "ff" | "fi" | "fl" | "ffi" | "ffl")
607        || s.chars().any(|c| (0xFB00..=0xFB06).contains(&(c as u32)))
608}
609
610// ------------------------------------------------------------ word gaps (#921)
611
612/// How a word boundary is decided where the PDF draws no space glyph — a
613/// word set apart only by moving the text cursor (#921).
614///
615/// [`WordGap::Adaptive`], the default, and [`WordGap::Factor`] follow
616/// docling-parse ≥ 7's contractor (`cells.h::contract`, 2026-09, PR #351 —
617/// what docling ≥ 2.142 runs on, `docling-parse>=7.22`): glyphs are grouped
618/// into line runs by geometry alone (no font boundary), every gap between
619/// two visible glyphs is normalized by the mean advance of those two
620/// glyphs, and a normalized gap above the threshold starts a new word; an
621/// explicit space glyph is always a boundary. Line cells are the run's
622/// words joined by single spaces. Letter spacing is detected first
623/// ([`tracked_gaps`]) — our addition, where docling-parse cuts letter-spaced
624/// words mid-word.
625///
626/// [`WordGap::Legacy`] is the contraction above: the docling-parse ≤ 6 rule
627/// this port started from, where a gap splits two words when it exceeds
628/// 0.33 × the running mean advance of the cell accumulated so far — a cell
629/// that restarts at every font change, so the threshold drifts along a line
630/// (`und dem` in a second font resource read `unddem`: 1.955 pt against
631/// 0.33 × 5.925 pt, the mean of `und` alone).
632#[derive(Clone, Copy, Debug, Default, PartialEq)]
633pub enum WordGap {
634    /// docling-parse ≤ 6's running-mean contraction.
635    Legacy,
636    /// A fixed normalized threshold for every line.
637    Factor(f64),
638    /// docling-parse ≥ 7's line-local threshold: a two-cluster k-means over
639    /// the line's normalized gaps (character spacing vs word spacing), at
640    /// least 0.18, capped at 0.35, 0.25 when the gaps do not separate.
641    #[default]
642    Adaptive,
643}
644
645impl WordGap {
646    /// The accepted spellings, for error messages.
647    pub const ACCEPTED: &'static str = "legacy, adaptive, or a factor in (0, 4]";
648
649    /// `legacy` / `adaptive` / a positive factor up to 4 (case-insensitive);
650    /// `Err` with the reason for anything else.
651    pub fn parse(s: &str) -> Result<Self, String> {
652        let t = s.trim().to_ascii_lowercase();
653        match t.as_str() {
654            "legacy" => Ok(WordGap::Legacy),
655            "adaptive" | "auto" | "default" => Ok(WordGap::Adaptive),
656            _ => match t.parse::<f64>() {
657                Ok(f) if f.is_finite() && f > 0.0 && f <= 4.0 => Ok(WordGap::Factor(f)),
658                _ => Err(format!(
659                    "pdf_word_gap must be {}, got {s:?}",
660                    WordGap::ACCEPTED
661                )),
662            },
663        }
664    }
665
666    /// `DOCLING_RS_PDF_WORD_GAP`, or the default ([`WordGap::Adaptive`])
667    /// when it is unset (an unreadable value warns once and keeps the
668    /// default).
669    pub fn from_env() -> Self {
670        let Some(v) = docling_core::env::nonempty("DOCLING_RS_PDF_WORD_GAP") else {
671            return WordGap::default();
672        };
673        WordGap::parse(&v).unwrap_or_else(|e| {
674            static WARNED: std::sync::Once = std::sync::Once::new();
675            WARNED.call_once(|| {
676                eprintln!("docling-pdf: DOCLING_RS_PDF_WORD_GAP: {e}; using adaptive")
677            });
678            WordGap::default()
679        })
680    }
681}
682
683/// One glyph cell of a line run, with its writing axis precomputed.
684struct RunCell<'a> {
685    cell: &'a Cell,
686    /// Unit vector along the bottom edge (the writing direction).
687    ux: f64,
688    uy: f64,
689    /// Bottom-edge length: the advance the glyph's loose box spans.
690    advance: f64,
691    height: f64,
692    space: bool,
693}
694
695impl<'a> RunCell<'a> {
696    fn new(cell: &'a Cell) -> Self {
697        let (dx, dy) = (cell.rx1 - cell.rx0, cell.ry1 - cell.ry0);
698        let advance = dx.hypot(dy);
699        let (ux, uy) = if advance > 1e-9 {
700            (dx / advance, dy / advance)
701        } else {
702            (1.0, 0.0)
703        };
704        let h0 = (cell.rx3 - cell.rx0).hypot(cell.ry3 - cell.ry0);
705        let h1 = (cell.rx2 - cell.rx1).hypot(cell.ry2 - cell.ry1);
706        RunCell {
707            cell,
708            ux,
709            uy,
710            advance,
711            height: 0.5 * (h0 + h1),
712            space: cell.blank,
713        }
714    }
715
716    /// The normalization length of a gap next to this glyph: its advance,
717    /// else half its height (docling-parse's `cell_space_width` fallback).
718    fn scale(&self) -> f64 {
719        if self.advance > 1e-6 {
720            self.advance
721        } else {
722            (0.5 * self.height).max(1e-6)
723        }
724    }
725}
726
727/// Signed distance along `lhs`'s writing direction from where its pen
728/// advance ends to where `rhs`'s starts (`forward_gap`, the
729/// `has_text_placement` form docling-parse takes for every rendered glyph).
730/// Our quads run in pen order — `r0 → r1` is the advance — so this is the
731/// trailing edge of `lhs` to the leading edge of `rhs` whatever the script:
732/// right-to-left text drawn in visual order still advances along `+u`, and
733/// flipping the axis for it (the geometric fallback) read every Arabic or
734/// Hebrew glyph pair as a step back of two advances, a new line each.
735fn forward_gap(lhs: &RunCell, rhs: &RunCell) -> f64 {
736    let (l, r) = (lhs.cell, rhs.cell);
737    let (tx, ty) = (0.5 * (l.rx1 + l.rx2), 0.5 * (l.ry1 + l.ry2));
738    let (hx, hy) = (0.5 * (r.rx0 + r.rx3), 0.5 * (r.ry0 + r.ry3));
739    (hx - tx) * lhs.ux + (hy - ty) * lhs.uy
740}
741
742/// Overlap, across the writing direction, of `lhs`'s trailing edge and
743/// `rhs`'s leading edge — positive for glyphs on one text line.
744fn facing_edge_overlap(lhs: &RunCell, rhs: &RunCell) -> f64 {
745    let (l, r) = (lhs.cell, rhs.cell);
746    let (ux, uy) = if l.ltr {
747        (lhs.ux, lhs.uy)
748    } else {
749        (-lhs.ux, -lhs.uy)
750    };
751    let (nx, ny) = (-uy, ux);
752    let proj = |x: f64, y: f64| x * nx + y * ny;
753    let (a0, a1) = if l.ltr {
754        (proj(l.rx1, l.ry1), proj(l.rx2, l.ry2))
755    } else {
756        (proj(l.rx0, l.ry0), proj(l.rx3, l.ry3))
757    };
758    let (b0, b1) = if l.ltr {
759        (proj(r.rx0, r.ry0), proj(r.rx3, r.ry3))
760    } else {
761        (proj(r.rx1, r.ry1), proj(r.rx2, r.ry2))
762    };
763    a0.max(a1).min(b0.max(b1)) - a0.min(a1).max(b0.min(b1))
764}
765
766/// A glyph of a mathematical layout by its symbols — the symbol half of
767/// `has_math_positioning_semantics`; the font-name half is
768/// [`Glyph::math_font`].
769fn is_math_glyph(text: &str) -> bool {
770    const MATH: &str = "∑∏∫√∞∈∉≠≤≥⊂⊃⊆⊇⊥∪∩⎛⎜⎝⎞⎟⎠⎡⎢⎣⎤⎥⎦";
771    text.chars().any(|c| MATH.contains(c))
772}
773
774/// A sub- or superscript placed by moving the cursor next to its base in a
775/// mathematical context (`is_local_positioned_attachment`).
776fn is_local_attachment(lhs: &RunCell, rhs: &RunCell) -> bool {
777    let scale = lhs.scale().max(rhs.scale());
778    if forward_gap(lhs, rhs) > 0.10 * scale {
779        return false;
780    }
781    let (off, (lh, rh)) = baseline_offset(lhs, rhs);
782    let math = |c: &RunCell| c.cell.math_font || is_math_glyph(&c.cell.text);
783    off <= 2.0 * lh.max(rh).max(1e-6) && (math(lhs) || math(rhs))
784}
785
786/// How far `rhs` sits from `lhs`'s baseline, across `lhs`'s writing axis,
787/// and the two glyphs' nominal heights: the pens' origins and the font sizes
788/// when the parser knows them (docling-parse's `text_origin` /
789/// `nominal_text_height`), else the loose boxes' bottom corners and heights.
790/// The boxes overstate a size change — a superscript's box bottom sits only
791/// its own, smaller descent below a raised baseline — so `Lysak` + its ORCID
792/// read as two words where docling-parse 7 keeps one.
793fn baseline_offset(lhs: &RunCell, rhs: &RunCell) -> (f64, (f64, f64)) {
794    let (nx, ny) = (-lhs.uy, lhs.ux);
795    match (lhs.cell.pen, rhs.cell.pen) {
796        (Some(a), Some(b)) => (
797            ((b[0] - a[0]) * nx + (b[1] - a[1]) * ny).abs(),
798            (a[2], b[2]),
799        ),
800        _ => (
801            ((rhs.cell.rx0 - lhs.cell.rx0) * nx + (rhs.cell.ry0 - lhs.cell.ry0) * ny).abs(),
802            (lhs.height, rhs.height),
803        ),
804    }
805}
806
807/// Whether `rhs` continues `lhs`'s text line (`continues_line`): the same
808/// writing direction, facing edges that overlap across it, and a cursor
809/// move between a step back and four advances forward.
810fn continues_line(lhs: &RunCell, rhs: &RunCell) -> bool {
811    if lhs.ux * rhs.ux + lhs.uy * rhs.uy < 0.985 {
812        return false;
813    }
814    let scale = lhs.scale().max(rhs.scale());
815    let gap = forward_gap(lhs, rhs);
816    if facing_edge_overlap(lhs, rhs) <= 1e-6 && !is_local_attachment(lhs, rhs) {
817        return false;
818    }
819    -scale <= gap && gap <= 4.0 * scale
820}
821
822/// Whether two glyphs sit on one baseline (`word_baselines_compatible`): a
823/// baseline shift beyond 0.35 × the smaller height starts a new word,
824/// unless it is a mathematical attachment.
825fn baselines_compatible(lhs: &RunCell, rhs: &RunCell) -> bool {
826    let (off, (lh, rh)) = baseline_offset(lhs, rhs);
827    off <= 0.35 * lh.min(rh).max(1e-6) || is_local_attachment(lhs, rhs)
828}
829
830/// The gap between two visible glyphs over their mean advance.
831fn normalized_gap(lhs: &RunCell, rhs: &RunCell) -> f64 {
832    forward_gap(lhs, rhs).max(0.0) / (0.5 * (lhs.scale() + rhs.scale())).max(1e-6)
833}
834
835/// What a glyph is to the letter-spacing detector.
836#[derive(Clone, Copy, PartialEq)]
837enum TrackClass {
838    /// Letters and digits — what letter-spaced (Sperrsatz) words are set in.
839    Letter,
840    /// Leader dots.
841    Dot,
842    Other,
843}
844
845fn track_class(text: &str) -> TrackClass {
846    if matches!(text, "." | "·" | "…") {
847        TrackClass::Dot
848    } else if !text.is_empty() && text.chars().all(char::is_alphanumeric) {
849        TrackClass::Letter
850    } else {
851        TrackClass::Other
852    }
853}
854
855/// Points two letter-spacing gaps may differ by and still be one tracking:
856/// producers set a letter-spaced word with one constant cursor move (#921's
857/// fixtures: within 0.17 pt), which rounding and kerning blur slightly.
858fn tracking_tolerance(gap: f64) -> f64 {
859    (0.08 * gap).max(0.25)
860}
861
862/// Letter spacing (Sperrsatz, tracked capitals, leader dots) in a line run
863/// (#921): `true` at index `i` when the gap from the previous visible glyph
864/// to `run[i]` is tracking inside one word rather than a word boundary.
865///
866/// docling-parse ≥ 7 judges each gap by its width over the flanking glyphs'
867/// mean advance, and a letter-spaced word defeats that: its gaps are one
868/// constant cursor move in points, but divided by the advances of `i`, `l`
869/// or `t` beside `M` or `D` they spread over 0.25–0.75, straddling any
870/// threshold, so the word is cut mid-word (`Di ens tk lasse`, `Heimarbei
871/// tstari f`). Constancy in points is the signal instead: a chain of three
872/// or more consecutive gaps between letters that are open (≥ 0.1 of an
873/// advance), at most one advance wide (not table columns) and equal within
874/// [`tracking_tolerance`] is tracking — when nothing on either side of it is
875/// tighter. That last test is what tells it from justified prose, whose
876/// word gaps are equal along a line too and chain up across one-letter
877/// words (`Peter W J Staar`, `Abs 1 Z 3 UrlG`): there the chain is flanked
878/// by abutting letters, while a letter-spaced word starts and ends at the
879/// line's ends, a space glyph or a wider gap; and one character repeated
880/// (`C C C C`, a figure's token row) is no word. Once a run has such a chain,
881/// shorter stretches at the same tracking with the same open flanks join
882/// it: the short words of the heading (`für`, `und`, `II`) and closing
883/// punctuation (`:`). Four or more dots in a row, each within an advance of
884/// the last, are one leader whatever their spacing.
885fn tracked_gaps(run: &[RunCell]) -> Vec<bool> {
886    struct Gap {
887        left: usize,
888        right: usize,
889        pt: f64,
890        n: f64,
891        left_class: TrackClass,
892        right_class: TrackClass,
893    }
894    let mut gaps: Vec<Gap> = Vec::new();
895    let mut prev: Option<usize> = None;
896    let mut crossed_space = false;
897    for (i, c) in run.iter().enumerate() {
898        if c.space {
899            crossed_space = true;
900            continue;
901        }
902        if let (Some(p), false) = (prev, crossed_space) {
903            gaps.push(Gap {
904                left: p,
905                right: i,
906                pt: forward_gap(&run[p], c),
907                n: normalized_gap(&run[p], c),
908                left_class: track_class(&run[p].cell.text),
909                right_class: track_class(&c.cell.text),
910            });
911        }
912        prev = Some(i);
913        crossed_space = false;
914    }
915    // `gaps[k]` and `gaps[k + 1]` share a glyph — no space glyph between.
916    let joined = |k: usize| gaps[k + 1].left == gaps[k].right;
917    // The longest stretch from `k` of joined gaps that `fits`, as its end.
918    let stretch = |k: usize, fits: &dyn Fn(&Gap) -> bool| {
919        let mut end = k;
920        while end < gaps.len() && fits(&gaps[end]) && (end == k || joined(end - 1)) {
921            end += 1;
922        }
923        end
924    };
925    // No gap right before or after `k..end` tighter than `floor` points.
926    let flanks_open = |k: usize, end: usize, floor: f64| {
927        let before = k > 0 && joined(k - 1) && gaps[k - 1].pt < floor;
928        let after = end < gaps.len() && joined(end - 1) && gaps[end].pt < floor;
929        !before && !after
930    };
931
932    let mut tracked = vec![false; run.len()];
933    let mut leader = vec![false; run.len()];
934    let mut letter_tracking: Vec<f64> = Vec::new();
935    let mut k = 0;
936    while k < gaps.len() {
937        let dots = |g: &Gap| {
938            g.left_class == TrackClass::Dot && g.right_class == TrackClass::Dot && g.n <= 1.0
939        };
940        let end = stretch(k, &dots);
941        if end - k >= 3 {
942            for g in &gaps[k..end] {
943                tracked[g.right] = true;
944                leader[g.left] = true;
945                leader[g.right] = true;
946            }
947            k = end;
948            continue;
949        }
950        let first = &gaps[k];
951        let letters = |g: &Gap| {
952            g.left_class == TrackClass::Letter
953                && g.right_class == TrackClass::Letter
954                && (0.1..=1.0).contains(&g.n)
955        };
956        if !letters(first) {
957            k += 1;
958            continue;
959        }
960        let (mut lo, mut hi) = (first.pt, first.pt);
961        let mut end = k + 1;
962        while end < gaps.len()
963            && joined(end - 1)
964            && letters(&gaps[end])
965            && hi.max(gaps[end].pt) - lo.min(gaps[end].pt) <= tracking_tolerance(lo)
966        {
967            lo = lo.min(gaps[end].pt);
968            hi = hi.max(gaps[end].pt);
969            end += 1;
970        }
971        // One character repeated (`C C C C` in a figure, `x x x x`) is a row
972        // of tokens, not a word.
973        let one_char = gaps[k..end]
974            .iter()
975            .all(|g| run[g.right].cell.text == run[first.left].cell.text);
976        if end - k >= 3 && !one_char && flanks_open(k, end, lo - tracking_tolerance(lo)) {
977            for g in &gaps[k..end] {
978                tracked[g.right] = true;
979            }
980            letter_tracking.push(0.5 * (lo + hi));
981            k = end;
982        } else {
983            k += 1;
984        }
985    }
986
987    for &t in &letter_tracking {
988        let tol = tracking_tolerance(t);
989        let same = |g: &Gap| {
990            (g.left_class == TrackClass::Letter || g.right_class == TrackClass::Letter)
991                && g.left_class != TrackClass::Dot
992                && g.right_class != TrackClass::Dot
993                && g.n <= 1.0
994                && (g.pt - t).abs() <= tol
995        };
996        let mut k = 0;
997        while k < gaps.len() {
998            let end = stretch(k, &same);
999            if end == k {
1000                k += 1;
1001                continue;
1002            }
1003            if flanks_open(k, end, t - tol) && !gaps[k..end].iter().any(|g| leader[g.left]) {
1004                for g in &gaps[k..end] {
1005                    tracked[g.right] = true;
1006                }
1007            }
1008            k = end;
1009        }
1010    }
1011    tracked
1012}
1013
1014/// Where a gap enters [`infer_word_gap`]'s k-means at most. A gap this wide
1015/// is a word boundary under any threshold the rule can pick (it caps at
1016/// 0.35), so its exact width carries no information — but one wide gap
1017/// after a comma or before a column (0.8–5 advances) dragged the high
1018/// cluster's mean up until the midpoint hit the 0.35 cap, and the line's
1019/// real word gaps (0.31–0.33 in tight justified text) fell under it:
1020/// `jedochwerdenweiterlaufendeQuartierkosten`, `KhurramAzeemHashmi`.
1021/// **Divergence** from docling-parse 7, which glues those (#921: 68 → 7
1022/// glues on the EVU agreement, measured against `pdftotext`'s words).
1023const GAP_CLUSTER_CLIP: f64 = 0.5;
1024
1025/// docling-parse ≥ 7's `infer_word_gap`: the line's normalized gaps (not
1026/// across an explicit space) split by an eight-step two-cluster k-means;
1027/// 0.25 when there are fewer than two or they do not separate, else the
1028/// midpoint of the two cluster means, at least 0.18. Letter-spacing gaps
1029/// (`tracked`, #921) stay out of the sample: they are settled already, and
1030/// their spread would drag the low cluster up into the word gaps. Each gap
1031/// enters at most [`GAP_CLUSTER_CLIP`] wide.
1032fn infer_word_gap(run: &[RunCell], tracked: &[bool]) -> f64 {
1033    let mut gaps = Vec::new();
1034    let mut prev: Option<&RunCell> = None;
1035    let mut crossed_space = false;
1036    for (i, c) in run.iter().enumerate() {
1037        if c.space {
1038            crossed_space = true;
1039            continue;
1040        }
1041        if let (Some(p), false, false) = (prev, crossed_space, tracked[i]) {
1042            gaps.push(normalized_gap(p, c).min(GAP_CLUSTER_CLIP));
1043        }
1044        prev = Some(c);
1045        crossed_space = false;
1046    }
1047    if gaps.len() < 2 {
1048        return 0.25;
1049    }
1050    let mut low = gaps.iter().copied().fold(f64::INFINITY, f64::min);
1051    let mut high = gaps.iter().copied().fold(f64::NEG_INFINITY, f64::max);
1052    if high < 0.18 || high - low < 0.08 {
1053        return 0.25;
1054    }
1055    for _ in 0..8 {
1056        let mid = 0.5 * (low + high);
1057        let (mut ls, mut ln, mut hs, mut hn) = (0.0, 0usize, 0.0, 0usize);
1058        for &g in &gaps {
1059            if g <= mid {
1060                ls += g;
1061                ln += 1;
1062            } else {
1063                hs += g;
1064                hn += 1;
1065            }
1066        }
1067        if ln == 0 || hn == 0 {
1068            return 0.25;
1069        }
1070        low = ls / ln as f64;
1071        high = hs / hn as f64;
1072    }
1073    if high < 0.18 || high - low < 0.08 {
1074        return 0.25;
1075    }
1076    (0.5 * (low + high)).max(0.18)
1077}
1078
1079/// A word or line being assembled: its text and its rotation-aligned box.
1080struct Agg {
1081    text: String,
1082    ltr: bool,
1083    q: [f64; 8],
1084    /// A word that starts only because its first glyph sits on another
1085    /// baseline than the glyph before it, with no horizontal gap between
1086    /// them, *inside a bracket* — a raised footnote marker after `(`, the
1087    /// `)` after it, a citation's `]` — joins the line text without a space
1088    /// (#992, a deliberate divergence from docling-parse's `( 1 )`; the
1089    /// word cell is still its own).
1090    glued: bool,
1091}
1092
1093impl Agg {
1094    fn of(c: &Cell, glued: bool) -> Self {
1095        Agg {
1096            text: c.text.clone(),
1097            ltr: c.ltr,
1098            q: [c.rx0, c.ry0, c.rx1, c.ry1, c.rx2, c.ry2, c.rx3, c.ry3],
1099            glued,
1100        }
1101    }
1102
1103    /// `append_cell`: the text in reading order (an RTL piece prepends), and
1104    /// the smallest rectangle aligned with the writing direction holding
1105    /// both boxes.
1106    fn append(&mut self, text: &str, ltr: bool, q: &[f64; 8], space: bool) {
1107        if self.ltr && ltr {
1108            if space {
1109                self.text.push(' ');
1110            }
1111            self.text.push_str(text);
1112        } else {
1113            let sep = if space { " " } else { "" };
1114            self.text = format!("{text}{sep}{}", self.text);
1115            self.ltr = false;
1116        }
1117        let (mut ux, mut uy) = (self.q[2] - self.q[0], self.q[3] - self.q[1]);
1118        if ux.hypot(uy) <= 1e-9 {
1119            (ux, uy) = (q[2] - q[0], q[3] - q[1]);
1120        }
1121        let n = ux.hypot(uy);
1122        if n <= 1e-9 {
1123            return;
1124        }
1125        let (ux, uy) = (ux / n, uy / n);
1126        let (nx, ny) = (-uy, ux);
1127        let (mut u0, mut u1, mut n0, mut n1) = (
1128            f64::INFINITY,
1129            f64::NEG_INFINITY,
1130            f64::INFINITY,
1131            f64::NEG_INFINITY,
1132        );
1133        for k in 0..4 {
1134            for (x, y) in [(self.q[2 * k], self.q[2 * k + 1]), (q[2 * k], q[2 * k + 1])] {
1135                let (u, v) = (x * ux + y * uy, x * nx + y * ny);
1136                u0 = u0.min(u);
1137                u1 = u1.max(u);
1138                n0 = n0.min(v);
1139                n1 = n1.max(v);
1140            }
1141        }
1142        let pt = |u: f64, v: f64| (u * ux + v * nx, u * uy + v * ny);
1143        let (a, b, c, d) = (pt(u0, n0), pt(u1, n0), pt(u1, n1), pt(u0, n1));
1144        self.q = [a.0, a.1, b.0, b.1, c.0, c.1, d.0, d.1];
1145    }
1146
1147    fn into_cell(self, page_h: f32) -> TextCell {
1148        let xs = [self.q[0], self.q[2], self.q[4], self.q[6]];
1149        let ys = [self.q[1], self.q[3], self.q[5], self.q[7]];
1150        let (l, r) = (
1151            xs.iter().copied().fold(f64::INFINITY, f64::min),
1152            xs.iter().copied().fold(f64::NEG_INFINITY, f64::max),
1153        );
1154        let (b, t) = (
1155            ys.iter().copied().fold(f64::INFINITY, f64::min),
1156            ys.iter().copied().fold(f64::NEG_INFINITY, f64::max),
1157        );
1158        TextCell {
1159            text: self.text,
1160            l: l as f32,
1161            t: page_h - t as f32,
1162            r: r as f32,
1163            b: page_h - b as f32,
1164        }
1165    }
1166}
1167
1168/// Whether the page's producer draws its word spaces as glyphs: at least
1169/// half of the lines long enough to hold several words (eight glyphs or
1170/// more) carry a space glyph. Producers are consistent about it — a TeX or
1171/// Arbortext page has none, a Word or EUR-Lex page has them on every line —
1172/// so this tells a space-less line on a spaced page (a lone word) from the
1173/// cursor-move pages #921 is about.
1174fn page_draws_spaces(runs: &[Vec<RunCell>]) -> bool {
1175    let long = |r: &&Vec<RunCell>| r.iter().filter(|c| !c.space).count() >= 8;
1176    let lines = runs.iter().filter(long).count();
1177    let spaced = runs
1178        .iter()
1179        .filter(long)
1180        .filter(|r| r.iter().any(|c| c.space))
1181        .count();
1182    lines > 0 && 2 * spaced >= lines
1183}
1184
1185/// docling-parse ≥ 7's contraction (`cells.h::contract`) over our char
1186/// cells, with the word threshold `gap` picks: the line runs, their words,
1187/// and the lines as the words joined by single spaces.
1188fn contract_runs(cells: &[Cell], gap: WordGap, page_h: f32) -> (Vec<TextCell>, Vec<TextCell>) {
1189    // Line runs, in source order. Explicit spaces belong to the open run as
1190    // boundary markers and take no part in the geometry test.
1191    let mut runs: Vec<Vec<RunCell>> = Vec::new();
1192    for c in cells.iter().filter(|c| !c.text.is_empty()) {
1193        let rc = RunCell::new(c);
1194        if rc.space {
1195            match runs.last_mut() {
1196                Some(run) => run.push(rc),
1197                None => runs.push(vec![rc]),
1198            }
1199            continue;
1200        }
1201        let starts = match runs.last().and_then(|r| r.iter().rev().find(|c| !c.space)) {
1202            Some(prev) => !continues_line(prev, &rc),
1203            None => runs.is_empty(),
1204        };
1205        if starts {
1206            runs.push(Vec::new());
1207        }
1208        runs.last_mut().expect("a run is open").push(rc);
1209    }
1210
1211    let (mut words_out, mut lines_out) = (Vec::new(), Vec::new());
1212    let page_spaced = page_draws_spaces(&runs);
1213    for run in &runs {
1214        // A line on a page whose producer draws its word spaces as glyphs is
1215        // judged like a line that draws them (below), even when it has none
1216        // of its own: a lone word in a table cell or a heading carries no
1217        // space glyph, and its only open gap is kerning — EUR-Lex's
1218        // `Offenlegungspf|lichten` at 0.22–0.25, cut by the line-local
1219        // threshold of 0.18 (docling-parse 7 cuts it too; #921).
1220        let has_spaces = page_spaced || run.iter().any(|c| c.space);
1221        let tracked = tracked_gaps(run);
1222        // A line that draws its word spaces as glyphs marks its boundaries
1223        // itself; docling-parse 7 splits an unmarked gap there only above
1224        // 0.35 (`min(0.35, 1.0)`). A fixed factor keeps that floor: its job
1225        // is the space-less lines (#921), and below it a spaced line's
1226        // loosely kerned pairs fall apart — EUR-Lex's `f|l` at 0.24 read
1227        // `Verpf lichtungen` under 0.2.
1228        let threshold = match gap {
1229            WordGap::Factor(f) if has_spaces => f.max(0.35),
1230            WordGap::Factor(f) => f,
1231            _ => (if has_spaces {
1232                1.0
1233            } else {
1234                infer_word_gap(run, &tracked)
1235            })
1236            .min(0.35),
1237        };
1238        let mut words: Vec<Agg> = Vec::new();
1239        let mut prev: Option<&RunCell> = None;
1240        let mut boundary = false;
1241        for (i, c) in run.iter().enumerate() {
1242            if c.space {
1243                boundary = true;
1244                continue;
1245            }
1246            let mut starts = words.is_empty() || boundary;
1247            let mut glued = false;
1248            // A TOC leader may omit the boundary before its first dot while
1249            // spacing every later one: keep that dot with the leader.
1250            if !starts
1251                && c.cell.text == "."
1252                && i + 4 < run.len()
1253                && run[i + 1].space
1254                && run[i + 2].cell.text == "."
1255                && run[i + 3].space
1256                && run[i + 4].cell.text == "."
1257                && prev.is_some_and(|p| p.cell.text != ".")
1258            {
1259                starts = true;
1260            }
1261            if let (false, Some(p)) = (starts, prev) {
1262                let shifted = !baselines_compatible(p, c);
1263                let gapped = !tracked[i] && normalized_gap(p, c) > threshold;
1264                starts = shifted || gapped;
1265                // A baseline shift with the glyphs touching, inside a
1266                // bracket: docling-parse starts a word
1267                // (`word_baselines_compatible`) and its line text then reads
1268                // `Richtlinie 2003/71/EG ( 1 )` for a raised footnote marker
1269                // where the page shows `(1)` and pdftotext / pdfium read it
1270                // so (#992). The word stays its own cell; the line text
1271                // joins it as the page does. Only after an opening bracket
1272                // or before a closing one: elsewhere docling's space is the
1273                // more useful reading — `SynthTabNet 1 .`, `1 https://…`,
1274                // `상해 1) 나`, the `1 /4` fraction — and joining them cost
1275                // five groundtruth files when this rule had no bracket test.
1276                let opens = |s: &str| matches!(s.chars().last(), Some('(' | '[' | '{'));
1277                let closes = |s: &str| matches!(s.chars().next(), Some(')' | ']' | '}'));
1278                glued = shifted
1279                    && !gapped
1280                    && (words.last().is_some_and(|w| opens(&w.text)) || closes(&c.cell.text));
1281            }
1282            if starts {
1283                words.push(Agg::of(c.cell, glued));
1284            } else {
1285                let q = [
1286                    c.cell.rx0, c.cell.ry0, c.cell.rx1, c.cell.ry1, c.cell.rx2, c.cell.ry2,
1287                    c.cell.rx3, c.cell.ry3,
1288                ];
1289                words.last_mut().expect("a word is open").append(
1290                    &c.cell.text,
1291                    c.cell.ltr,
1292                    &q,
1293                    false,
1294                );
1295            }
1296            prev = Some(c);
1297            boundary = false;
1298        }
1299        let mut it = words.into_iter();
1300        let Some(first) = it.next() else {
1301            continue;
1302        };
1303        let mut line = Agg {
1304            text: first.text.clone(),
1305            ltr: first.ltr,
1306            q: first.q,
1307            glued: false,
1308        };
1309        words_out.push(first.into_cell(page_h));
1310        for w in it {
1311            line.append(&w.text, w.ltr, &w.q, !w.glued);
1312            words_out.push(w.into_cell(page_h));
1313        }
1314        lines_out.push(line.into_cell(page_h));
1315    }
1316    (lines_out, words_out)
1317}
1318
1319#[cfg(test)]
1320mod tests {
1321    use super::*;
1322
1323    fn glyph(ch: char, l: f32, r: f32) -> Glyph {
1324        Glyph {
1325            ch,
1326            l,
1327            b: 100.0,
1328            r,
1329            t: 110.0,
1330            ll: l,
1331            lb: 98.0,
1332            lr: r,
1333            lt: 110.0,
1334            font: 0,
1335            quad: None,
1336            pen: None,
1337            math_font: false,
1338            invisible: false,
1339        }
1340    }
1341
1342    /// Tight-set Latin (a table cell in a born-digital manual): the gap between
1343    /// `MODE` and `to` (1.84 pt) is under the 0.33 × average-width word gate (2.0 pt), so
1344    /// only the space glyph between them keeps the words apart. docling-parse
1345    /// erases spaces after the word contraction, not before.
1346    #[test]
1347    fn space_glyph_separates_tight_words() {
1348        let glyphs = [
1349            glyph('M', 137.66, 143.74),
1350            glyph('O', 143.74, 149.82),
1351            glyph('D', 149.82, 155.90),
1352            glyph('E', 155.90, 161.98),
1353            glyph(' ', 161.84, 164.09),
1354            glyph('t', 163.82, 166.60),
1355            glyph('o', 166.60, 171.60),
1356        ];
1357        let (lines, words) = line_and_word_cells(&glyphs, 792.0, true);
1358        let words: Vec<&str> = words.iter().map(|w| w.text.as_str()).collect();
1359        assert_eq!(words, ["MODE", "to"]);
1360        assert_eq!(lines.len(), 1);
1361        assert_eq!(lines[0].text, "MODE to");
1362    }
1363
1364    /// #609: a chart's y-axis ticks set one under another at the same x (each
1365    /// tick placed by its own `cm`, same `Tm`) are six line cells with their
1366    /// own boxes, as in docling-parse — not one `345678` cell with the first
1367    /// tick's box. A ligature decomposed at one box still recomposes.
1368    #[test]
1369    fn stacked_glyphs_at_one_x_stay_separate_cells() {
1370        let at = |ch: char, b: f32| Glyph {
1371            lb: b,
1372            lt: b + 10.0,
1373            b,
1374            t: b + 10.0,
1375            ..glyph(ch, 98.0, 103.0)
1376        };
1377        let ticks: Vec<Glyph> = "345678"
1378            .chars()
1379            .enumerate()
1380            .map(|(k, ch)| at(ch, 316.0 + 25.92 * k as f32))
1381            .collect();
1382        let lines = line_cells(&ticks, 792.0, true);
1383        let texts: Vec<&str> = lines.iter().map(|c| c.text.as_str()).collect();
1384        assert_eq!(texts, ["3", "4", "5", "6", "7", "8"]);
1385        assert!(lines.windows(2).all(|w| w[0].t > w[1].t));
1386
1387        let lig = [glyph('f', 10.0, 16.0), glyph('i', 10.0, 16.0)];
1388        let lines = line_cells(&lig, 792.0, true);
1389        assert_eq!(lines.len(), 1);
1390        assert_eq!(lines[0].text, "fi");
1391    }
1392
1393    /// The returned vectors own no more than their cells. Collecting straight
1394    /// from the per-glyph `Cell` buffer reused its allocation (std's in-place
1395    /// collect), so a page kept ~4 slots per *glyph* — on a dense table page,
1396    /// 30× the cells' size, for every page the text-layer path held.
1397    #[test]
1398    fn cells_do_not_keep_the_glyph_buffer() {
1399        // Ten rows of `777 777 …`: abutting glyphs, words split by space glyphs.
1400        let glyphs: Vec<Glyph> = (0..400)
1401            .map(|i| {
1402                let x = (i % 40) as f32 * 6.0;
1403                let ch = if i % 4 == 3 { ' ' } else { '7' };
1404                let mut g = glyph(ch, x, x + 6.0);
1405                let row = (i / 40) as f32 * 14.0;
1406                (g.b, g.t, g.lb, g.lt) = (100.0 + row, 110.0 + row, 98.0 + row, 110.0 + row);
1407                g
1408            })
1409            .collect();
1410        let (lines, words) = line_and_word_cells(&glyphs, 792.0, true);
1411        assert_eq!((lines.len(), words.len()), (10, 100));
1412        assert_eq!(lines.capacity(), lines.len());
1413        assert_eq!(words.capacity(), words.len());
1414    }
1415
1416    /// #921, page 8 of the reporter's collective agreement: `und dem` sits in
1417    /// a second font resource between runs of the body font, word gaps are
1418    /// cursor moves (no space glyph). Glyph boxes as the parser reads them.
1419    fn und_dem_line() -> Vec<Glyph> {
1420        let at = |ch: char, l: f32, r: f32, font: u64| Glyph {
1421            ch,
1422            l,
1423            b: 682.056,
1424            r,
1425            t: 691.05,
1426            ll: l,
1427            lb: 682.056,
1428            lr: r,
1429            lt: 691.05,
1430            font,
1431            quad: None,
1432            pen: None,
1433            math_font: false,
1434            invisible: false,
1435        };
1436        let mut g = Vec::new();
1437        let mut run = |text: &str, edges: &[f32], font: u64| {
1438            for (i, ch) in text.chars().enumerate() {
1439                g.push(at(ch, edges[i], edges[i + 1], font));
1440            }
1441        };
1442        run(
1443            "schaft",
1444            &[
1445                328.976, 333.216, 338.572, 344.325, 350.486, 353.920, 357.248,
1446            ],
1447            1,
1448        );
1449        run("und", &[359.261, 365.121, 370.875, 377.035], 2);
1450        run("dem", &[378.990, 385.151, 390.701, 399.287], 2);
1451        run("Öst", &[401.214, 409.092, 413.332, 416.660], 1);
1452        g
1453    }
1454
1455    #[test]
1456    fn legacy_rule_keeps_the_borderline_und_dem_glued() {
1457        // The baselines' rule: the cell restarts at the font change, so the
1458        // threshold is 0.33 × the mean advance of `und` alone (1.9553 pt)
1459        // and the 1.9550 pt gap stays inside the word.
1460        let (lines, words) = line_and_word_cells(&und_dem_line(), 792.0, true);
1461        assert!(lines.iter().any(|c| c.text == "unddem"), "{lines:?}");
1462        assert!(words.iter().any(|c| c.text == "unddem"), "{words:?}");
1463    }
1464
1465    #[test]
1466    fn line_local_word_gaps_split_und_dem() {
1467        for gap in [WordGap::Adaptive, WordGap::Factor(0.2)] {
1468            let (lines, words) = line_and_word_cells_with(&und_dem_line(), 792.0, true, gap);
1469            let texts: Vec<&str> = lines.iter().map(|c| c.text.as_str()).collect();
1470            assert_eq!(texts, ["schaft und dem Öst"], "{gap:?}");
1471            let texts: Vec<&str> = words.iter().map(|c| c.text.as_str()).collect();
1472            assert_eq!(texts, ["schaft", "und", "dem", "Öst"], "{gap:?}");
1473            // The word boxes are the glyphs' own extent.
1474            assert!((words[1].l - 359.261).abs() < 1e-3 && (words[1].r - 377.035).abs() < 1e-3);
1475        }
1476        // A factor above the normalized gaps (0.234 … 0.438) keeps them all.
1477        let (lines, _) =
1478            line_and_word_cells_with(&und_dem_line(), 792.0, true, WordGap::Factor(0.5));
1479        assert_eq!(lines[0].text, "schaftunddemÖst");
1480    }
1481
1482    #[test]
1483    fn a_superscript_attaches_by_pen_origin_and_math_face() {
1484        // `Lysak` at 10 pt, then `[0000` at 7 pt raised `rise` pt with no gap.
1485        // The baseline test reads the pens' origins and font sizes, as
1486        // docling-parse 7 does (`pen: None` falls back to the loose boxes).
1487        let at = |ch: char, l: f32, y: f32, size: f32, math: bool, pen: bool| Glyph {
1488            lb: y - 0.2 * size,
1489            lt: y + 0.8 * size,
1490            b: y - 0.2 * size,
1491            t: y + 0.8 * size,
1492            pen: pen.then_some([l, y, size]),
1493            math_font: math,
1494            ..glyph(ch, l, l + 0.5 * size)
1495        };
1496        let line = |rise: f32, math: bool, pen: bool| {
1497            let mut g: Vec<Glyph> = "Lysak"
1498                .chars()
1499                .enumerate()
1500                .map(|(k, ch)| at(ch, 100.0 + 5.0 * k as f32, 600.0, 10.0, math, pen))
1501                .collect();
1502            g.extend(
1503                "[0000"
1504                    .chars()
1505                    .enumerate()
1506                    .map(|(k, ch)| at(ch, 125.0 + 3.5 * k as f32, 600.0 + rise, 7.0, math, pen)),
1507            );
1508            let (lines, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1509            (
1510                lines[0].text.clone(),
1511                words.iter().map(|w| w.text.clone()).collect::<Vec<_>>(),
1512            )
1513        };
1514        let one = |s: &str| (s.to_string(), vec![s.to_string()]);
1515        let two = |s: &str| {
1516            (
1517                s.to_string(),
1518                vec!["Lysak".to_string(), "[0000".to_string()],
1519            )
1520        };
1521        // 2305.03393v1's ORCID: 3.6 pt up is more than 0.35 × 7 pt, a new word
1522        // unless it is a local attachment, which a TeX face (`cmr`) makes it.
1523        // Not a math face: two words, spaced — the raised run *opens* a
1524        // bracket, which is not the #992 join (that is for a run after an
1525        // opening bracket or before a closing one).
1526        assert_eq!(line(3.6, true, true), one("Lysak[0000"));
1527        assert_eq!(line(3.6, false, true), two("Lysak [0000"));
1528        // 2 pt up: on the pens 2.0 ≤ 0.35 × 7, one word; the boxes' bottoms
1529        // differ by the descents too (2.6 pt), which read it as two.
1530        assert_eq!(line(2.0, false, true), one("Lysak[0000"));
1531        assert_eq!(line(2.0, false, false), two("Lysak [0000"));
1532    }
1533
1534    /// #992: a raised footnote marker between parentheses — `(`, a 6.8 pt
1535    /// `1` 3.5 pt up, `)` — is three word cells (the baseline rule) but the
1536    /// line reads `(1)` as the page does; with a real gap before the marker
1537    /// (`EG (1)`) the space is the gap's, as before. The same raised `1`
1538    /// right after a letter keeps docling's space (`EG 1`): only a bracket
1539    /// joins.
1540    #[test]
1541    fn a_touching_superscript_joins_the_line_text_inside_brackets_only() {
1542        let at = |ch: char, l: f32, w: f32, y: f32, size: f32| Glyph {
1543            lb: y - 0.2 * size,
1544            lt: y + 0.8 * size,
1545            b: y - 0.2 * size,
1546            t: y + 0.8 * size,
1547            pen: Some([l, y, size]),
1548            ..glyph(ch, l, l + w)
1549        };
1550        let g = [
1551            at('E', 100.0, 6.0, 600.0, 10.5),
1552            at('G', 106.0, 6.9, 600.0, 10.5),
1553            at('(', 115.3, 3.2, 600.0, 10.5),
1554            at('1', 118.5, 3.1, 603.5, 6.8),
1555            at(')', 121.6, 3.2, 600.0, 10.5),
1556            at('e', 127.2, 5.0, 600.0, 10.5),
1557        ];
1558        let (lines, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1559        assert_eq!(lines[0].text, "EG (1) e");
1560        let words: Vec<&str> = words.iter().map(|w| w.text.as_str()).collect();
1561        assert_eq!(words, ["EG", "(", "1", ")", "e"]);
1562        // `EG` then the raised `1` touching the `G`: docling's `EG 1`.
1563        let g = [
1564            at('E', 100.0, 6.0, 600.0, 10.5),
1565            at('G', 106.0, 6.9, 600.0, 10.5),
1566            at('1', 112.9, 3.1, 603.5, 6.8),
1567        ];
1568        let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1569        assert_eq!(lines[0].text, "EG 1");
1570    }
1571
1572    #[test]
1573    fn a_factor_keeps_docling_parse_s_floor_on_lines_with_space_glyphs() {
1574        // `Verpf` + `lichtungen` 0.6 pt apart (0.24 of the flanking advances)
1575        // on a line whose word spaces are glyphs: below the 0.35 floor
1576        // docling-parse 7 keeps for such lines, so it is not a boundary even
1577        // under a factor of 0.2. The same gap on a space-less line splits.
1578        let mut g = Vec::new();
1579        let mut x = 100.0f32;
1580        let put = |g: &mut Vec<Glyph>, s: &str, x: &mut f32| {
1581            for ch in s.chars() {
1582                g.push(glyph(ch, *x, *x + 2.5));
1583                *x += 2.5;
1584            }
1585        };
1586        put(&mut g, "Die", &mut x);
1587        g.push(glyph(' ', x, x + 2.5));
1588        x += 2.5;
1589        put(&mut g, "Verpf", &mut x);
1590        x += 0.6;
1591        put(&mut g, "lichtungen", &mut x);
1592        let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Factor(0.2));
1593        assert_eq!(lines[0].text, "Die Verpflichtungen");
1594        let spaceless: Vec<Glyph> = g.into_iter().filter(|c| c.ch != ' ').collect();
1595        let (lines, _) = line_and_word_cells_with(&spaceless, 792.0, true, WordGap::Factor(0.2));
1596        assert_eq!(lines[0].text, "Die Verpf lichtungen");
1597    }
1598
1599    #[test]
1600    fn right_to_left_glyphs_in_visual_order_stay_one_line() {
1601        // Arabic drawn in visual order (the pen moves left to right, as most
1602        // producers store it): the gap runs along the pen, not against the
1603        // script — reversed, every glyph pair read as a step back of two
1604        // advances and each glyph became a line of its own.
1605        let mut g = Vec::new();
1606        let mut x = 100.0f32;
1607        for (k, word) in [
1608            "\u{0631}\u{0627}\u{0632}\u{0627}\u{0628}",
1609            "\u{0631}\u{062f}",
1610        ]
1611        .iter()
1612        .enumerate()
1613        {
1614            if k > 0 {
1615                x += 3.0;
1616            }
1617            for ch in word.chars() {
1618                g.push(glyph(ch, x, x + 5.0));
1619                x += 5.0;
1620            }
1621        }
1622        for gap in [WordGap::Adaptive, WordGap::Factor(0.2)] {
1623            let (lines, words) = line_and_word_cells_with(&g, 792.0, true, gap);
1624            assert_eq!(
1625                lines.len(),
1626                1,
1627                "{gap:?}: {:?}",
1628                lines.iter().map(|c| &c.text).collect::<Vec<_>>()
1629            );
1630            assert_eq!(words.len(), 2, "{gap:?}");
1631        }
1632    }
1633
1634    #[test]
1635    fn letter_spacing_stays_one_word_under_the_adaptive_rule() {
1636        // Sperrsatz: every letter 1.5 pt apart, the words 6 pt apart. The
1637        // line's gaps form two clusters, so the letters stay together.
1638        let mut g = Vec::new();
1639        let mut x = 100.0f32;
1640        for (k, word) in ["Allgemeine", "Bestimmungen"].iter().enumerate() {
1641            if k > 0 {
1642                x += 6.0;
1643            }
1644            for ch in word.chars() {
1645                g.push(glyph(ch, x, x + 5.0));
1646                x += 5.0 + 1.5;
1647            }
1648            x -= 1.5;
1649        }
1650        let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1651        assert_eq!(lines[0].text, "Allgemeine Bestimmungen");
1652    }
1653
1654    /// Glyphs 2.5 pt wide on a line at `y`, each `(text, gap before)` piece
1655    /// set after the previous one; `' '` pieces are space glyphs.
1656    fn set_line(pieces: &[(&str, f32)], y: f32) -> Vec<Glyph> {
1657        let mut g = Vec::new();
1658        let mut x = 100.0f32;
1659        for (text, gap) in pieces {
1660            x += gap;
1661            for ch in text.chars() {
1662                g.push(Glyph {
1663                    b: y,
1664                    t: y + 10.0,
1665                    lb: y - 2.0,
1666                    lt: y + 10.0,
1667                    ..glyph(ch, x, x + 2.5)
1668                });
1669                x += 2.5;
1670            }
1671        }
1672        g
1673    }
1674
1675    #[test]
1676    fn one_wide_gap_does_not_raise_the_line_s_word_gap() {
1677        // #921, EVU p. 3: word gaps of 0.32 advances in tight justified text
1678        // and one gap of 3.2 before a tab stop. Unclipped, the wide gap is
1679        // the high cluster alone, the midpoint caps at 0.35 and the line
1680        // reads `jedochwerdenweiterlaufende`.
1681        let g = set_line(
1682            &[
1683                ("jedoch", 0.0),
1684                ("werden", 0.8),
1685                ("weiterlaufende", 0.8),
1686                ("Quartierkosten", 8.0),
1687            ],
1688            600.0,
1689        );
1690        let (_, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1691        let texts: Vec<&str> = words.iter().map(|c| c.text.as_str()).collect();
1692        assert_eq!(
1693            texts,
1694            ["jedoch", "werden", "weiterlaufende", "Quartierkosten"]
1695        );
1696    }
1697
1698    #[test]
1699    fn a_lone_word_on_a_page_that_draws_spaces_keeps_its_kerning() {
1700        // #921, EUR-Lex: `Offenlegungspf` + `lichten` 0.8 pt apart (0.32
1701        // advances) in a one-word table cell. On a page whose lines carry
1702        // space glyphs the gap is kerning, not a word boundary; on a
1703        // space-less page (TeX, Arbortext) the same line splits.
1704        let lone = || set_line(&[("Offenlegungspf", 0.0), ("lichten", 0.8)], 500.0);
1705        let spaced = |y| {
1706            set_line(
1707                &[
1708                    ("Die", 0.0),
1709                    (" ", 0.0),
1710                    ("Taxonomie", 0.0),
1711                    (" ", 0.0),
1712                    ("gilt", 0.0),
1713                ],
1714                y,
1715            )
1716        };
1717        let mut page = lone();
1718        page.extend(spaced(600.0));
1719        page.extend(spaced(620.0));
1720        let texts = |g: &[Glyph]| {
1721            let (lines, _) = line_and_word_cells_with(g, 792.0, true, WordGap::Adaptive);
1722            lines.into_iter().map(|c| c.text).collect::<Vec<_>>()
1723        };
1724        assert!(texts(&page).contains(&"Offenlegungspflichten".to_string()));
1725        assert_eq!(texts(&lone()), ["Offenlegungspf lichten"]);
1726    }
1727
1728    #[test]
1729    fn word_gap_spellings() {
1730        assert_eq!(WordGap::parse("adaptive"), Ok(WordGap::Adaptive));
1731        assert_eq!(WordGap::parse(" Legacy "), Ok(WordGap::Legacy));
1732        assert_eq!(WordGap::parse("0.2"), Ok(WordGap::Factor(0.2)));
1733        for bad in ["0", "-1", "5", "nan", "wide"] {
1734            assert!(WordGap::parse(bad).is_err(), "{bad}");
1735        }
1736    }
1737}