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    line_and_word_cells_cut(glyphs, page_h, euclidean, gap, zero_advance_run())
476}
477
478/// `DOCLING_RS_PDF_ZERO_ADVANCE_RUN`: off. On, the glyph after a
479/// zero-advance one starts a line run, as in docling-parse ≥ 7 — its
480/// `facing_edge_overlap` takes the writing axis from the left cell's bottom
481/// edge and returns 0 for one of no length. That cuts an Arabic word at its
482/// tanween and sets the pieces apart (`أيضًا` reads `أيض ً`, its tail a clause
483/// away), and docling's groundtruth has it so: the knob is for comparing
484/// against docling, not for reading. Off, the mark stays in its line.
485fn zero_advance_run() -> bool {
486    static ON: std::sync::OnceLock<bool> = std::sync::OnceLock::new();
487    *ON.get_or_init(|| docling_core::env::flag("DOCLING_RS_PDF_ZERO_ADVANCE_RUN"))
488}
489
490/// [`line_and_word_cells_with`] with [`zero_advance_run`] as an argument.
491fn line_and_word_cells_cut(
492    glyphs: &[Glyph],
493    page_h: f32,
494    euclidean: bool,
495    gap: WordGap,
496    zero_advance_run: bool,
497) -> (Vec<TextCell>, Vec<TextCell>) {
498    let built = build_cells(glyphs, euclidean);
499    if gap != WordGap::Legacy {
500        return contract_runs(&built, gap, page_h, zero_advance_run);
501    }
502    let to_text_cell = |c: Cell| {
503        let l = c.rx0.min(c.rx1).min(c.rx2).min(c.rx3) as f32;
504        let r = c.rx0.max(c.rx1).max(c.rx2).max(c.rx3) as f32;
505        let top = c.ry0.max(c.ry1).max(c.ry2).max(c.ry3) as f32;
506        let bot = c.ry0.min(c.ry1).min(c.ry2).min(c.ry3) as f32;
507        TextCell {
508            text: c.text,
509            l,
510            t: page_h - top,
511            r,
512            b: page_h - bot,
513        }
514    };
515    // Word run: docling-parse's `create_word_cells` order — copy the char
516    // cells, contract (`sanitize_bbox`), *then* erase the spaces. The space
517    // glyphs stay in the stream during the contraction, where `applicable`'s
518    // `block_spaces` makes each one a hard word boundary; they are dropped
519    // afterwards by the blank filter below. Filtering them out up front let
520    // the 0.33 gate alone decide word breaks, which glues tight-set Latin
521    // (`MODE` + `to`: 1.8 pt apart under a 2.0 pt gate → `MODEto`) and the
522    // thin-spaced Korean docling-parse ≥ 7 keeps apart (`1군` `감염병`).
523    let mut word_run: Vec<Cell> = built.clone();
524    let mut cells = built;
525    contract(&mut cells, euclidean, LINE_FACTORS);
526    let lines = to_text_cells(cells, to_text_cell);
527    contract(&mut word_run, euclidean, WORD_FACTORS);
528    word_run.retain(|c| !c.text.trim().is_empty());
529    let words = to_text_cells(word_run, to_text_cell);
530    (lines, words)
531}
532
533/// Map the contracted cells into a freshly allocated, exactly sized vector.
534///
535/// A plain `into_iter().map(..).collect()` would take std's in-place-collect
536/// path and hand back the *input's* allocation: one ~150-byte [`Cell`] slot per
537/// glyph of the page, reinterpreted as ~4× as many 40-byte [`TextCell`] slots,
538/// while the contraction leaves a few glyphs per cell. Callers keep these
539/// vectors for the whole document (the text-layer path holds every page), so
540/// the dead capacity added up to ~30× the cells' real size — gigabytes on a
541/// long table-heavy PDF.
542fn to_text_cells(cells: Vec<Cell>, f: impl Fn(Cell) -> TextCell) -> Vec<TextCell> {
543    let mut out = Vec::with_capacity(cells.len());
544    out.extend(cells.into_iter().map(f));
545    out
546}
547
548fn is_rtl_char(c: char) -> bool {
549    let ch = c as u32;
550    (0x0600..=0x06FF).contains(&ch)
551        || (0x0750..=0x077F).contains(&ch)
552        || (0x08A0..=0x08FF).contains(&ch)
553        || (0xFB50..=0xFDFF).contains(&ch)
554        || (0xFE70..=0xFEFF).contains(&ch)
555        || (0x0590..=0x05FF).contains(&ch)
556        || (0xFB1D..=0xFB4F).contains(&ch)
557        || (0x0700..=0x074F).contains(&ch)
558        || (0x0780..=0x07BF).contains(&ch)
559        || (0x07C0..=0x07FF).contains(&ch)
560}
561
562/// All codepoints are RTL-script (matches `string.h::is_right_to_left`).
563fn is_right_to_left(s: &str) -> bool {
564    !s.is_empty() && s.chars().all(is_rtl_char)
565}
566
567/// A single-codepoint punctuation/space cell (matches `string.h`).
568fn is_punct_or_space(s: &str) -> bool {
569    let mut chars = s.chars();
570    let (Some(c), None) = (chars.next(), chars.next()) else {
571        return false;
572    };
573    if matches!(
574        c,
575        ' ' | '\t'
576            | '\n'
577            | '\r'
578            | '\u{0c}'
579            | '\u{0b}'
580            | '.'
581            | ','
582            | ';'
583            | ':'
584            | '!'
585            | '?'
586            | '('
587            | ')'
588            | '['
589            | ']'
590            | '{'
591            | '}'
592            | '\''
593            | '"'
594            | '`'
595            | '\u{2018}'
596            | '\u{2019}'
597            | '\u{201c}'
598            | '\u{201d}'
599            | '-'
600            | '\u{2013}'
601            | '\u{2014}'
602            | '_'
603            | '/'
604            | '\\'
605            | '|'
606            | '@'
607            | '#'
608            | '%'
609            | '&'
610            | '*'
611            | '+'
612            | '='
613            | '<'
614            | '>'
615    ) {
616        return true;
617    }
618    let ch = c as u32;
619    (0x2000..=0x206F).contains(&ch)
620        || (0x3000..=0x303F).contains(&ch)
621        || (0xFE50..=0xFE6F).contains(&ch)
622        || (0xFF00..=0xFF0F).contains(&ch)
623        || (0xFF1A..=0xFF1F).contains(&ch)
624        || (0xFF3B..=0xFF5E).contains(&ch)
625}
626
627/// Ligature glyph or its ASCII spelling (matches `string.h::is_ligature`).
628fn is_ligature(s: &str) -> bool {
629    matches!(s, "ff" | "fi" | "fl" | "ffi" | "ffl")
630        || s.chars().any(|c| (0xFB00..=0xFB06).contains(&(c as u32)))
631}
632
633// ------------------------------------------------------------ word gaps (#921)
634
635/// How a word boundary is decided where the PDF draws no space glyph — a
636/// word set apart only by moving the text cursor (#921).
637///
638/// [`WordGap::Adaptive`], the default, and [`WordGap::Factor`] follow
639/// docling-parse ≥ 7's contractor (`cells.h::contract`, 2026-09, PR #351 —
640/// what docling ≥ 2.142 runs on, `docling-parse>=7.22`): glyphs are grouped
641/// into line runs by geometry alone (no font boundary), every gap between
642/// two visible glyphs is normalized by the mean advance of those two
643/// glyphs, and a normalized gap above the threshold starts a new word; an
644/// explicit space glyph is always a boundary. Line cells are the run's
645/// words joined by single spaces. Letter spacing is detected first
646/// ([`tracked_gaps`]) — our addition, where docling-parse cuts letter-spaced
647/// words mid-word.
648///
649/// [`WordGap::Legacy`] is the contraction above: the docling-parse ≤ 6 rule
650/// this port started from, where a gap splits two words when it exceeds
651/// 0.33 × the running mean advance of the cell accumulated so far — a cell
652/// that restarts at every font change, so the threshold drifts along a line
653/// (`und dem` in a second font resource read `unddem`: 1.955 pt against
654/// 0.33 × 5.925 pt, the mean of `und` alone).
655#[derive(Clone, Copy, Debug, Default, PartialEq)]
656pub enum WordGap {
657    /// docling-parse ≤ 6's running-mean contraction.
658    Legacy,
659    /// A fixed normalized threshold for every line.
660    Factor(f64),
661    /// docling-parse ≥ 7's line-local threshold: a two-cluster k-means over
662    /// the line's normalized gaps (character spacing vs word spacing), at
663    /// least 0.18, capped at 0.35, 0.25 when the gaps do not separate.
664    #[default]
665    Adaptive,
666}
667
668impl WordGap {
669    /// The accepted spellings, for error messages.
670    pub const ACCEPTED: &'static str = "legacy, adaptive, or a factor in (0, 4]";
671
672    /// `legacy` / `adaptive` / a positive factor up to 4 (case-insensitive);
673    /// `Err` with the reason for anything else.
674    pub fn parse(s: &str) -> Result<Self, String> {
675        let t = s.trim().to_ascii_lowercase();
676        match t.as_str() {
677            "legacy" => Ok(WordGap::Legacy),
678            "adaptive" | "auto" | "default" => Ok(WordGap::Adaptive),
679            _ => match t.parse::<f64>() {
680                Ok(f) if f.is_finite() && f > 0.0 && f <= 4.0 => Ok(WordGap::Factor(f)),
681                _ => Err(format!(
682                    "pdf_word_gap must be {}, got {s:?}",
683                    WordGap::ACCEPTED
684                )),
685            },
686        }
687    }
688
689    /// `DOCLING_RS_PDF_WORD_GAP`, or the default ([`WordGap::Adaptive`])
690    /// when it is unset (an unreadable value warns once and keeps the
691    /// default).
692    pub fn from_env() -> Self {
693        let Some(v) = docling_core::env::nonempty("DOCLING_RS_PDF_WORD_GAP") else {
694            return WordGap::default();
695        };
696        WordGap::parse(&v).unwrap_or_else(|e| {
697            static WARNED: std::sync::Once = std::sync::Once::new();
698            WARNED.call_once(|| {
699                eprintln!("docling-pdf: DOCLING_RS_PDF_WORD_GAP: {e}; using adaptive")
700            });
701            WordGap::default()
702        })
703    }
704}
705
706/// The bottom-edge length at or under which a glyph gives no writing axis:
707/// docling-parse's own bound in `facing_edge_overlap`. ([`RunCell::scale`]'s
708/// 1e-6 is its `cell_space_width`'s, a different question — whether the
709/// advance can normalize a gap.)
710const NO_AXIS: f64 = 1e-9;
711
712/// One glyph cell of a line run, with its writing axis precomputed.
713struct RunCell<'a> {
714    cell: &'a Cell,
715    /// Unit vector along the bottom edge (the writing direction).
716    ux: f64,
717    uy: f64,
718    /// Bottom-edge length: the advance the glyph's loose box spans.
719    advance: f64,
720    height: f64,
721    space: bool,
722}
723
724impl<'a> RunCell<'a> {
725    fn new(cell: &'a Cell) -> Self {
726        let (dx, dy) = (cell.rx1 - cell.rx0, cell.ry1 - cell.ry0);
727        let advance = dx.hypot(dy);
728        let (ux, uy) = if advance > NO_AXIS {
729            (dx / advance, dy / advance)
730        } else {
731            (1.0, 0.0)
732        };
733        let h0 = (cell.rx3 - cell.rx0).hypot(cell.ry3 - cell.ry0);
734        let h1 = (cell.rx2 - cell.rx1).hypot(cell.ry2 - cell.ry1);
735        RunCell {
736            cell,
737            ux,
738            uy,
739            advance,
740            height: 0.5 * (h0 + h1),
741            space: cell.blank,
742        }
743    }
744
745    /// The normalization length of a gap next to this glyph: its advance,
746    /// else half its height (docling-parse's `cell_space_width` fallback).
747    fn scale(&self) -> f64 {
748        if self.advance > 1e-6 {
749            self.advance
750        } else {
751            (0.5 * self.height).max(1e-6)
752        }
753    }
754}
755
756/// Signed distance along `lhs`'s writing direction from where its pen
757/// advance ends to where `rhs`'s starts (`forward_gap`, the
758/// `has_text_placement` form docling-parse takes for every rendered glyph).
759/// Our quads run in pen order — `r0 → r1` is the advance — so this is the
760/// trailing edge of `lhs` to the leading edge of `rhs` whatever the script:
761/// right-to-left text drawn in visual order still advances along `+u`, and
762/// flipping the axis for it (the geometric fallback) read every Arabic or
763/// Hebrew glyph pair as a step back of two advances, a new line each.
764fn forward_gap(lhs: &RunCell, rhs: &RunCell) -> f64 {
765    let (l, r) = (lhs.cell, rhs.cell);
766    let (tx, ty) = (0.5 * (l.rx1 + l.rx2), 0.5 * (l.ry1 + l.ry2));
767    let (hx, hy) = (0.5 * (r.rx0 + r.rx3), 0.5 * (r.ry0 + r.ry3));
768    (hx - tx) * lhs.ux + (hy - ty) * lhs.uy
769}
770
771/// Overlap, across the writing direction, of `lhs`'s trailing edge and
772/// `rhs`'s leading edge — positive for glyphs on one text line.
773fn facing_edge_overlap(lhs: &RunCell, rhs: &RunCell, zero_advance_run: bool) -> f64 {
774    let (l, r) = (lhs.cell, rhs.cell);
775    // docling-parse takes the axis from `lhs`'s bottom edge and gives up on
776    // one of no length: nothing overlaps a zero-advance glyph's trailing
777    // edge, so the glyph after it starts a run. We do so only when asked
778    // ([`zero_advance_run`]) and otherwise measure along the x axis.
779    if zero_advance_run && lhs.advance <= NO_AXIS {
780        return 0.0;
781    }
782    let (ux, uy) = if l.ltr {
783        (lhs.ux, lhs.uy)
784    } else {
785        (-lhs.ux, -lhs.uy)
786    };
787    let (nx, ny) = (-uy, ux);
788    let proj = |x: f64, y: f64| x * nx + y * ny;
789    let (a0, a1) = if l.ltr {
790        (proj(l.rx1, l.ry1), proj(l.rx2, l.ry2))
791    } else {
792        (proj(l.rx0, l.ry0), proj(l.rx3, l.ry3))
793    };
794    let (b0, b1) = if l.ltr {
795        (proj(r.rx0, r.ry0), proj(r.rx3, r.ry3))
796    } else {
797        (proj(r.rx1, r.ry1), proj(r.rx2, r.ry2))
798    };
799    a0.max(a1).min(b0.max(b1)) - a0.min(a1).max(b0.min(b1))
800}
801
802/// A glyph of a mathematical layout by its symbols — the symbol half of
803/// `has_math_positioning_semantics`; the font-name half is
804/// [`Glyph::math_font`].
805fn is_math_glyph(text: &str) -> bool {
806    const MATH: &str = "∑∏∫√∞∈∉≠≤≥⊂⊃⊆⊇⊥∪∩⎛⎜⎝⎞⎟⎠⎡⎢⎣⎤⎥⎦";
807    text.chars().any(|c| MATH.contains(c))
808}
809
810/// A sub- or superscript placed by moving the cursor next to its base in a
811/// mathematical context (`is_local_positioned_attachment`).
812fn is_local_attachment(lhs: &RunCell, rhs: &RunCell) -> bool {
813    let scale = lhs.scale().max(rhs.scale());
814    if forward_gap(lhs, rhs) > 0.10 * scale {
815        return false;
816    }
817    let (off, (lh, rh)) = baseline_offset(lhs, rhs);
818    let math = |c: &RunCell| c.cell.math_font || is_math_glyph(&c.cell.text);
819    off <= 2.0 * lh.max(rh).max(1e-6) && (math(lhs) || math(rhs))
820}
821
822/// How far `rhs` sits from `lhs`'s baseline, across `lhs`'s writing axis,
823/// and the two glyphs' nominal heights: the pens' origins and the font sizes
824/// when the parser knows them (docling-parse's `text_origin` /
825/// `nominal_text_height`), else the loose boxes' bottom corners and heights.
826/// The boxes overstate a size change — a superscript's box bottom sits only
827/// its own, smaller descent below a raised baseline — so `Lysak` + its ORCID
828/// read as two words where docling-parse 7 keeps one.
829fn baseline_offset(lhs: &RunCell, rhs: &RunCell) -> (f64, (f64, f64)) {
830    let (nx, ny) = (-lhs.uy, lhs.ux);
831    match (lhs.cell.pen, rhs.cell.pen) {
832        (Some(a), Some(b)) => (
833            ((b[0] - a[0]) * nx + (b[1] - a[1]) * ny).abs(),
834            (a[2], b[2]),
835        ),
836        _ => (
837            ((rhs.cell.rx0 - lhs.cell.rx0) * nx + (rhs.cell.ry0 - lhs.cell.ry0) * ny).abs(),
838            (lhs.height, rhs.height),
839        ),
840    }
841}
842
843/// Whether `rhs` continues `lhs`'s text line (`continues_line`): the same
844/// writing direction, facing edges that overlap across it, and a cursor
845/// move between a step back and four advances forward.
846fn continues_line(lhs: &RunCell, rhs: &RunCell, zero_advance_run: bool) -> bool {
847    if lhs.ux * rhs.ux + lhs.uy * rhs.uy < 0.985 {
848        return false;
849    }
850    let scale = lhs.scale().max(rhs.scale());
851    let gap = forward_gap(lhs, rhs);
852    if facing_edge_overlap(lhs, rhs, zero_advance_run) <= 1e-6 && !is_local_attachment(lhs, rhs) {
853        return false;
854    }
855    -scale <= gap && gap <= 4.0 * scale
856}
857
858/// Whether two glyphs sit on one baseline (`word_baselines_compatible`): a
859/// baseline shift beyond 0.35 × the smaller height starts a new word,
860/// unless it is a mathematical attachment.
861fn baselines_compatible(lhs: &RunCell, rhs: &RunCell) -> bool {
862    let (off, (lh, rh)) = baseline_offset(lhs, rhs);
863    off <= 0.35 * lh.min(rh).max(1e-6) || is_local_attachment(lhs, rhs)
864}
865
866/// The gap between two visible glyphs over their mean advance.
867fn normalized_gap(lhs: &RunCell, rhs: &RunCell) -> f64 {
868    forward_gap(lhs, rhs).max(0.0) / (0.5 * (lhs.scale() + rhs.scale())).max(1e-6)
869}
870
871/// What a glyph is to the letter-spacing detector.
872#[derive(Clone, Copy, PartialEq)]
873enum TrackClass {
874    /// Letters and digits — what letter-spaced (Sperrsatz) words are set in.
875    Letter,
876    /// Leader dots.
877    Dot,
878    Other,
879}
880
881fn track_class(text: &str) -> TrackClass {
882    if matches!(text, "." | "·" | "…") {
883        TrackClass::Dot
884    } else if !text.is_empty() && text.chars().all(char::is_alphanumeric) {
885        TrackClass::Letter
886    } else {
887        TrackClass::Other
888    }
889}
890
891/// Points two letter-spacing gaps may differ by and still be one tracking:
892/// producers set a letter-spaced word with one constant cursor move (#921's
893/// fixtures: within 0.17 pt), which rounding and kerning blur slightly.
894fn tracking_tolerance(gap: f64) -> f64 {
895    (0.08 * gap).max(0.25)
896}
897
898/// Letter spacing (Sperrsatz, tracked capitals, leader dots) in a line run
899/// (#921): `true` at index `i` when the gap from the previous visible glyph
900/// to `run[i]` is tracking inside one word rather than a word boundary.
901///
902/// docling-parse ≥ 7 judges each gap by its width over the flanking glyphs'
903/// mean advance, and a letter-spaced word defeats that: its gaps are one
904/// constant cursor move in points, but divided by the advances of `i`, `l`
905/// or `t` beside `M` or `D` they spread over 0.25–0.75, straddling any
906/// threshold, so the word is cut mid-word (`Di ens tk lasse`, `Heimarbei
907/// tstari f`). Constancy in points is the signal instead: a chain of three
908/// or more consecutive gaps between letters that are open (≥ 0.1 of an
909/// advance), at most one advance wide (not table columns) and equal within
910/// [`tracking_tolerance`] is tracking — when nothing on either side of it is
911/// tighter. That last test is what tells it from justified prose, whose
912/// word gaps are equal along a line too and chain up across one-letter
913/// words (`Peter W J Staar`, `Abs 1 Z 3 UrlG`): there the chain is flanked
914/// by abutting letters, while a letter-spaced word starts and ends at the
915/// line's ends, a space glyph or a wider gap; and one character repeated
916/// (`C C C C`, a figure's token row) is no word. Once a run has such a chain,
917/// shorter stretches at the same tracking with the same open flanks join
918/// it: the short words of the heading (`für`, `und`, `II`) and closing
919/// punctuation (`:`). Four or more dots in a row, each within an advance of
920/// the last, are one leader whatever their spacing.
921fn tracked_gaps(run: &[RunCell]) -> Vec<bool> {
922    struct Gap {
923        left: usize,
924        right: usize,
925        pt: f64,
926        n: f64,
927        left_class: TrackClass,
928        right_class: TrackClass,
929    }
930    let mut gaps: Vec<Gap> = Vec::new();
931    let mut prev: Option<usize> = None;
932    let mut crossed_space = false;
933    for (i, c) in run.iter().enumerate() {
934        if c.space {
935            crossed_space = true;
936            continue;
937        }
938        if let (Some(p), false) = (prev, crossed_space) {
939            gaps.push(Gap {
940                left: p,
941                right: i,
942                pt: forward_gap(&run[p], c),
943                n: normalized_gap(&run[p], c),
944                left_class: track_class(&run[p].cell.text),
945                right_class: track_class(&c.cell.text),
946            });
947        }
948        prev = Some(i);
949        crossed_space = false;
950    }
951    // `gaps[k]` and `gaps[k + 1]` share a glyph — no space glyph between.
952    let joined = |k: usize| gaps[k + 1].left == gaps[k].right;
953    // The longest stretch from `k` of joined gaps that `fits`, as its end.
954    let stretch = |k: usize, fits: &dyn Fn(&Gap) -> bool| {
955        let mut end = k;
956        while end < gaps.len() && fits(&gaps[end]) && (end == k || joined(end - 1)) {
957            end += 1;
958        }
959        end
960    };
961    // No gap right before or after `k..end` tighter than `floor` points.
962    let flanks_open = |k: usize, end: usize, floor: f64| {
963        let before = k > 0 && joined(k - 1) && gaps[k - 1].pt < floor;
964        let after = end < gaps.len() && joined(end - 1) && gaps[end].pt < floor;
965        !before && !after
966    };
967
968    let mut tracked = vec![false; run.len()];
969    let mut leader = vec![false; run.len()];
970    let mut letter_tracking: Vec<f64> = Vec::new();
971    let mut k = 0;
972    while k < gaps.len() {
973        let dots = |g: &Gap| {
974            g.left_class == TrackClass::Dot && g.right_class == TrackClass::Dot && g.n <= 1.0
975        };
976        let end = stretch(k, &dots);
977        if end - k >= 3 {
978            for g in &gaps[k..end] {
979                tracked[g.right] = true;
980                leader[g.left] = true;
981                leader[g.right] = true;
982            }
983            k = end;
984            continue;
985        }
986        let first = &gaps[k];
987        let letters = |g: &Gap| {
988            g.left_class == TrackClass::Letter
989                && g.right_class == TrackClass::Letter
990                && (0.1..=1.0).contains(&g.n)
991        };
992        if !letters(first) {
993            k += 1;
994            continue;
995        }
996        let (mut lo, mut hi) = (first.pt, first.pt);
997        let mut end = k + 1;
998        while end < gaps.len()
999            && joined(end - 1)
1000            && letters(&gaps[end])
1001            && hi.max(gaps[end].pt) - lo.min(gaps[end].pt) <= tracking_tolerance(lo)
1002        {
1003            lo = lo.min(gaps[end].pt);
1004            hi = hi.max(gaps[end].pt);
1005            end += 1;
1006        }
1007        // One character repeated (`C C C C` in a figure, `x x x x`) is a row
1008        // of tokens, not a word.
1009        let one_char = gaps[k..end]
1010            .iter()
1011            .all(|g| run[g.right].cell.text == run[first.left].cell.text);
1012        if end - k >= 3 && !one_char && flanks_open(k, end, lo - tracking_tolerance(lo)) {
1013            for g in &gaps[k..end] {
1014                tracked[g.right] = true;
1015            }
1016            letter_tracking.push(0.5 * (lo + hi));
1017            k = end;
1018        } else {
1019            k += 1;
1020        }
1021    }
1022
1023    for &t in &letter_tracking {
1024        let tol = tracking_tolerance(t);
1025        let same = |g: &Gap| {
1026            (g.left_class == TrackClass::Letter || g.right_class == TrackClass::Letter)
1027                && g.left_class != TrackClass::Dot
1028                && g.right_class != TrackClass::Dot
1029                && g.n <= 1.0
1030                && (g.pt - t).abs() <= tol
1031        };
1032        let mut k = 0;
1033        while k < gaps.len() {
1034            let end = stretch(k, &same);
1035            if end == k {
1036                k += 1;
1037                continue;
1038            }
1039            if flanks_open(k, end, t - tol) && !gaps[k..end].iter().any(|g| leader[g.left]) {
1040                for g in &gaps[k..end] {
1041                    tracked[g.right] = true;
1042                }
1043            }
1044            k = end;
1045        }
1046    }
1047    tracked
1048}
1049
1050/// Where a gap enters [`infer_word_gap`]'s k-means at most. A gap this wide
1051/// is a word boundary under any threshold the rule can pick (it caps at
1052/// 0.35), so its exact width carries no information — but one wide gap
1053/// after a comma or before a column (0.8–5 advances) dragged the high
1054/// cluster's mean up until the midpoint hit the 0.35 cap, and the line's
1055/// real word gaps (0.31–0.33 in tight justified text) fell under it:
1056/// `jedochwerdenweiterlaufendeQuartierkosten`, `KhurramAzeemHashmi`.
1057/// **Divergence** from docling-parse 7, which glues those (#921: 68 → 7
1058/// glues on the EVU agreement, measured against `pdftotext`'s words).
1059const GAP_CLUSTER_CLIP: f64 = 0.5;
1060
1061/// docling-parse ≥ 7's `infer_word_gap`: the line's normalized gaps (not
1062/// across an explicit space) split by an eight-step two-cluster k-means;
1063/// 0.25 when there are fewer than two or they do not separate, else the
1064/// midpoint of the two cluster means, at least 0.18. Letter-spacing gaps
1065/// (`tracked`, #921) stay out of the sample: they are settled already, and
1066/// their spread would drag the low cluster up into the word gaps. Each gap
1067/// enters at most [`GAP_CLUSTER_CLIP`] wide.
1068fn infer_word_gap(run: &[RunCell], tracked: &[bool]) -> f64 {
1069    let mut gaps = Vec::new();
1070    let mut prev: Option<&RunCell> = None;
1071    let mut crossed_space = false;
1072    for (i, c) in run.iter().enumerate() {
1073        if c.space {
1074            crossed_space = true;
1075            continue;
1076        }
1077        if let (Some(p), false, false) = (prev, crossed_space, tracked[i]) {
1078            gaps.push(normalized_gap(p, c).min(GAP_CLUSTER_CLIP));
1079        }
1080        prev = Some(c);
1081        crossed_space = false;
1082    }
1083    if gaps.len() < 2 {
1084        return 0.25;
1085    }
1086    let mut low = gaps.iter().copied().fold(f64::INFINITY, f64::min);
1087    let mut high = gaps.iter().copied().fold(f64::NEG_INFINITY, f64::max);
1088    if high < 0.18 || high - low < 0.08 {
1089        return 0.25;
1090    }
1091    for _ in 0..8 {
1092        let mid = 0.5 * (low + high);
1093        let (mut ls, mut ln, mut hs, mut hn) = (0.0, 0usize, 0.0, 0usize);
1094        for &g in &gaps {
1095            if g <= mid {
1096                ls += g;
1097                ln += 1;
1098            } else {
1099                hs += g;
1100                hn += 1;
1101            }
1102        }
1103        if ln == 0 || hn == 0 {
1104            return 0.25;
1105        }
1106        low = ls / ln as f64;
1107        high = hs / hn as f64;
1108    }
1109    if high < 0.18 || high - low < 0.08 {
1110        return 0.25;
1111    }
1112    (0.5 * (low + high)).max(0.18)
1113}
1114
1115/// A word or line being assembled: its text and its rotation-aligned box.
1116struct Agg {
1117    text: String,
1118    ltr: bool,
1119    q: [f64; 8],
1120    /// A word that starts only because its first glyph sits on another
1121    /// baseline than the glyph before it, with no horizontal gap between
1122    /// them, *inside a bracket* — a raised footnote marker after `(`, the
1123    /// `)` after it, a citation's `]` — joins the line text without a space
1124    /// (#992, a deliberate divergence from docling-parse's `( 1 )`; the
1125    /// word cell is still its own).
1126    glued: bool,
1127}
1128
1129impl Agg {
1130    fn of(c: &Cell, glued: bool) -> Self {
1131        Agg {
1132            text: c.text.clone(),
1133            ltr: c.ltr,
1134            q: [c.rx0, c.ry0, c.rx1, c.ry1, c.rx2, c.ry2, c.rx3, c.ry3],
1135            glued,
1136        }
1137    }
1138
1139    /// `append_cell`: the text in reading order (an RTL piece prepends), and
1140    /// the smallest rectangle aligned with the writing direction holding
1141    /// both boxes.
1142    fn append(&mut self, text: &str, ltr: bool, q: &[f64; 8], space: bool) {
1143        if self.ltr && ltr {
1144            if space {
1145                self.text.push(' ');
1146            }
1147            self.text.push_str(text);
1148        } else {
1149            let sep = if space { " " } else { "" };
1150            self.text = format!("{text}{sep}{}", self.text);
1151            self.ltr = false;
1152        }
1153        let (mut ux, mut uy) = (self.q[2] - self.q[0], self.q[3] - self.q[1]);
1154        if ux.hypot(uy) <= 1e-9 {
1155            (ux, uy) = (q[2] - q[0], q[3] - q[1]);
1156        }
1157        let n = ux.hypot(uy);
1158        if n <= 1e-9 {
1159            return;
1160        }
1161        let (ux, uy) = (ux / n, uy / n);
1162        let (nx, ny) = (-uy, ux);
1163        let (mut u0, mut u1, mut n0, mut n1) = (
1164            f64::INFINITY,
1165            f64::NEG_INFINITY,
1166            f64::INFINITY,
1167            f64::NEG_INFINITY,
1168        );
1169        for k in 0..4 {
1170            for (x, y) in [(self.q[2 * k], self.q[2 * k + 1]), (q[2 * k], q[2 * k + 1])] {
1171                let (u, v) = (x * ux + y * uy, x * nx + y * ny);
1172                u0 = u0.min(u);
1173                u1 = u1.max(u);
1174                n0 = n0.min(v);
1175                n1 = n1.max(v);
1176            }
1177        }
1178        let pt = |u: f64, v: f64| (u * ux + v * nx, u * uy + v * ny);
1179        let (a, b, c, d) = (pt(u0, n0), pt(u1, n0), pt(u1, n1), pt(u0, n1));
1180        self.q = [a.0, a.1, b.0, b.1, c.0, c.1, d.0, d.1];
1181    }
1182
1183    fn into_cell(self, page_h: f32) -> TextCell {
1184        let xs = [self.q[0], self.q[2], self.q[4], self.q[6]];
1185        let ys = [self.q[1], self.q[3], self.q[5], self.q[7]];
1186        let (l, r) = (
1187            xs.iter().copied().fold(f64::INFINITY, f64::min),
1188            xs.iter().copied().fold(f64::NEG_INFINITY, f64::max),
1189        );
1190        let (b, t) = (
1191            ys.iter().copied().fold(f64::INFINITY, f64::min),
1192            ys.iter().copied().fold(f64::NEG_INFINITY, f64::max),
1193        );
1194        TextCell {
1195            text: self.text,
1196            l: l as f32,
1197            t: page_h - t as f32,
1198            r: r as f32,
1199            b: page_h - b as f32,
1200        }
1201    }
1202}
1203
1204/// Whether the page's producer draws its word spaces as glyphs: at least
1205/// half of the lines long enough to hold several words (eight glyphs or
1206/// more) carry a space glyph. Producers are consistent about it — a TeX or
1207/// Arbortext page has none, a Word or EUR-Lex page has them on every line —
1208/// so this tells a space-less line on a spaced page (a lone word) from the
1209/// cursor-move pages #921 is about.
1210fn page_draws_spaces(runs: &[Vec<RunCell>]) -> bool {
1211    let long = |r: &&Vec<RunCell>| r.iter().filter(|c| !c.space).count() >= 8;
1212    let lines = runs.iter().filter(long).count();
1213    let spaced = runs
1214        .iter()
1215        .filter(long)
1216        .filter(|r| r.iter().any(|c| c.space))
1217        .count();
1218    lines > 0 && 2 * spaced >= lines
1219}
1220
1221/// Whether one of the page's space glyphs sits in a gap between two
1222/// consecutive glyphs of `run` (its middle inside the gap along the run's
1223/// writing direction, most of its height within the band of the two glyphs
1224/// beside it). Such a line draws its
1225/// word spaces, only not between its letters: LibreOffice sets an Arabic
1226/// line's spaces first and then its letters in visual order, so the spaces
1227/// fall to the run open before them and this run has none of its own.
1228/// `spaces` are the page's space cells by the middle of their height.
1229fn spaces_drawn_apart(run: &[RunCell], spaces: &[(f64, &Cell)]) -> bool {
1230    let mut visible = run.iter().filter(|c| !c.space);
1231    let Some(first) = visible.next() else {
1232        return false;
1233    };
1234    // The spaces inside the run's extent; most runs have none.
1235    let (mut l, mut r, mut b, mut t) = bounds(first.cell);
1236    for c in visible.clone() {
1237        let (cl, cr, cb, ct) = bounds(c.cell);
1238        (l, r, b, t) = (l.min(cl), r.max(cr), b.min(cb), t.max(ct));
1239    }
1240    let (lo, hi) = (
1241        spaces.partition_point(|&(y, _)| y < b),
1242        spaces.partition_point(|&(y, _)| y <= t),
1243    );
1244    let inside: Vec<&Cell> = spaces[lo..hi]
1245        .iter()
1246        .map(|&(_, c)| c)
1247        .filter(|c| (l..=r).contains(&(0.5 * (c.b_l + c.b_r))))
1248        .collect();
1249    if inside.is_empty() {
1250        return false;
1251    }
1252    let (ux, uy) = (first.ux, first.uy);
1253    let along = |x: f64, y: f64| x * ux + y * uy;
1254    let across = |c: &Cell| {
1255        let v = [
1256            c.rx0 * -uy + c.ry0 * ux,
1257            c.rx1 * -uy + c.ry1 * ux,
1258            c.rx2 * -uy + c.ry2 * ux,
1259            c.rx3 * -uy + c.ry3 * ux,
1260        ];
1261        let lo = v.iter().copied().fold(f64::INFINITY, f64::min);
1262        let hi = v.iter().copied().fold(f64::NEG_INFINITY, f64::max);
1263        (lo, hi)
1264    };
1265    // The open gaps, as (trailing edge, leading edge, the band of the two
1266    // glyphs beside the gap: an Arabic mark's box can be shorter than the
1267    // space after it).
1268    let mut gaps = Vec::new();
1269    let mut prev = first;
1270    for c in visible {
1271        let (lhs, rhs) = (prev.cell, c.cell);
1272        let tail = along(0.5 * (lhs.rx1 + lhs.rx2), 0.5 * (lhs.ry1 + lhs.ry2));
1273        let head = along(0.5 * (rhs.rx0 + rhs.rx3), 0.5 * (rhs.ry0 + rhs.ry3));
1274        if head > tail {
1275            let ((l0, l1), (r0, r1)) = (across(lhs), across(rhs));
1276            gaps.push((tail, head, (l0.min(r0), l1.max(r1))));
1277        }
1278        prev = c;
1279    }
1280    inside.iter().any(|c| {
1281        let mid = along(0.5 * (c.rx0 + c.rx2), 0.5 * (c.ry0 + c.ry2));
1282        let (s0, s1) = across(c);
1283        gaps.iter().any(|&(tail, head, (b0, b1))| {
1284            tail <= mid && mid <= head && s1.min(b1) - s0.max(b0) > 0.5 * (s1 - s0)
1285        })
1286    })
1287}
1288
1289/// docling-parse ≥ 7's contraction (`cells.h::contract`) over our char
1290/// cells, with the word threshold `gap` picks: the line runs, their words,
1291/// and the lines as the words joined by single spaces.
1292fn contract_runs(
1293    cells: &[Cell],
1294    gap: WordGap,
1295    page_h: f32,
1296    zero_advance_run: bool,
1297) -> (Vec<TextCell>, Vec<TextCell>) {
1298    // Line runs, in source order. Explicit spaces belong to the open run as
1299    // boundary markers and take no part in the geometry test.
1300    let mut runs: Vec<Vec<RunCell>> = Vec::new();
1301    for c in cells.iter().filter(|c| !c.text.is_empty()) {
1302        let rc = RunCell::new(c);
1303        if rc.space {
1304            match runs.last_mut() {
1305                Some(run) => run.push(rc),
1306                None => runs.push(vec![rc]),
1307            }
1308            continue;
1309        }
1310        let starts = match runs.last().and_then(|r| r.iter().rev().find(|c| !c.space)) {
1311            Some(prev) => !continues_line(prev, &rc, zero_advance_run),
1312            None => runs.is_empty(),
1313        };
1314        if starts {
1315            runs.push(Vec::new());
1316        }
1317        runs.last_mut().expect("a run is open").push(rc);
1318    }
1319
1320    let (mut words_out, mut lines_out) = (Vec::new(), Vec::new());
1321    let page_spaced = page_draws_spaces(&runs);
1322    let mut spaces: Vec<(f64, &Cell)> = Vec::new();
1323    if page_spaced {
1324        spaces.extend(
1325            runs.iter()
1326                .flatten()
1327                .filter(|c| c.space)
1328                .map(|c| (0.5 * (c.cell.b_b + c.cell.b_t), c.cell)),
1329        );
1330        spaces.sort_by(|a, b| a.0.total_cmp(&b.0));
1331    }
1332    for run in &runs {
1333        // A line on a page whose producer draws its word spaces as glyphs is
1334        // judged like a line that draws them (below), even when it has none
1335        // of its own: a lone word in a table cell or a heading carries no
1336        // space glyph, and its only open gap is kerning — EUR-Lex's
1337        // `Offenlegungspf|lichten` at 0.22–0.25, cut by the line-local
1338        // threshold of 0.18 (docling-parse 7 cuts it too; #921). Not a line
1339        // whose spaces were drawn apart from its letters: it is no lone word,
1340        // and like docling-parse we infer its gap — under the cap its word
1341        // gaps of a third of an advance stayed glued (`علىشراء`).
1342        let has_spaces =
1343            run.iter().any(|c| c.space) || (page_spaced && !spaces_drawn_apart(run, &spaces));
1344        let tracked = tracked_gaps(run);
1345        // A line that draws its word spaces as glyphs marks its boundaries
1346        // itself; docling-parse 7 splits an unmarked gap there only above
1347        // 0.35 (`min(0.35, 1.0)`). A fixed factor keeps that floor: its job
1348        // is the space-less lines (#921), and below it a spaced line's
1349        // loosely kerned pairs fall apart — EUR-Lex's `f|l` at 0.24 read
1350        // `Verpf lichtungen` under 0.2.
1351        let threshold = match gap {
1352            WordGap::Factor(f) if has_spaces => f.max(0.35),
1353            WordGap::Factor(f) => f,
1354            _ => (if has_spaces {
1355                1.0
1356            } else {
1357                infer_word_gap(run, &tracked)
1358            })
1359            .min(0.35),
1360        };
1361        let mut words: Vec<Agg> = Vec::new();
1362        let mut prev: Option<&RunCell> = None;
1363        let mut boundary = false;
1364        for (i, c) in run.iter().enumerate() {
1365            if c.space {
1366                boundary = true;
1367                continue;
1368            }
1369            let mut starts = words.is_empty() || boundary;
1370            let mut glued = false;
1371            // A TOC leader may omit the boundary before its first dot while
1372            // spacing every later one: keep that dot with the leader.
1373            if !starts
1374                && c.cell.text == "."
1375                && i + 4 < run.len()
1376                && run[i + 1].space
1377                && run[i + 2].cell.text == "."
1378                && run[i + 3].space
1379                && run[i + 4].cell.text == "."
1380                && prev.is_some_and(|p| p.cell.text != ".")
1381            {
1382                starts = true;
1383            }
1384            if let (false, Some(p)) = (starts, prev) {
1385                let shifted = !baselines_compatible(p, c);
1386                let gapped = !tracked[i] && normalized_gap(p, c) > threshold;
1387                starts = shifted || gapped;
1388                // A baseline shift with the glyphs touching, inside a
1389                // bracket: docling-parse starts a word
1390                // (`word_baselines_compatible`) and its line text then reads
1391                // `Richtlinie 2003/71/EG ( 1 )` for a raised footnote marker
1392                // where the page shows `(1)` and pdftotext / pdfium read it
1393                // so (#992). The word stays its own cell; the line text
1394                // joins it as the page does. Only after an opening bracket
1395                // or before a closing one: elsewhere docling's space is the
1396                // more useful reading — `SynthTabNet 1 .`, `1 https://…`,
1397                // `상해 1) 나`, the `1 /4` fraction — and joining them cost
1398                // five groundtruth files when this rule had no bracket test.
1399                let opens = |s: &str| matches!(s.chars().last(), Some('(' | '[' | '{'));
1400                let closes = |s: &str| matches!(s.chars().next(), Some(')' | ']' | '}'));
1401                glued = shifted
1402                    && !gapped
1403                    && (words.last().is_some_and(|w| opens(&w.text)) || closes(&c.cell.text));
1404            }
1405            if starts {
1406                words.push(Agg::of(c.cell, glued));
1407            } else {
1408                let q = [
1409                    c.cell.rx0, c.cell.ry0, c.cell.rx1, c.cell.ry1, c.cell.rx2, c.cell.ry2,
1410                    c.cell.rx3, c.cell.ry3,
1411                ];
1412                words.last_mut().expect("a word is open").append(
1413                    &c.cell.text,
1414                    c.cell.ltr,
1415                    &q,
1416                    false,
1417                );
1418            }
1419            prev = Some(c);
1420            boundary = false;
1421        }
1422        let mut it = words.into_iter();
1423        let Some(first) = it.next() else {
1424            continue;
1425        };
1426        let mut line = Agg {
1427            text: first.text.clone(),
1428            ltr: first.ltr,
1429            q: first.q,
1430            glued: false,
1431        };
1432        words_out.push(first.into_cell(page_h));
1433        for w in it {
1434            line.append(&w.text, w.ltr, &w.q, !w.glued);
1435            words_out.push(w.into_cell(page_h));
1436        }
1437        lines_out.push(line.into_cell(page_h));
1438    }
1439    (lines_out, words_out)
1440}
1441
1442#[cfg(test)]
1443mod tests {
1444    use super::*;
1445
1446    fn glyph(ch: char, l: f32, r: f32) -> Glyph {
1447        Glyph {
1448            ch,
1449            l,
1450            b: 100.0,
1451            r,
1452            t: 110.0,
1453            ll: l,
1454            lb: 98.0,
1455            lr: r,
1456            lt: 110.0,
1457            font: 0,
1458            quad: None,
1459            pen: None,
1460            math_font: false,
1461            invisible: false,
1462        }
1463    }
1464
1465    /// Tight-set Latin (a table cell in a born-digital manual): the gap between
1466    /// `MODE` and `to` (1.84 pt) is under the 0.33 × average-width word gate (2.0 pt), so
1467    /// only the space glyph between them keeps the words apart. docling-parse
1468    /// erases spaces after the word contraction, not before.
1469    #[test]
1470    fn space_glyph_separates_tight_words() {
1471        let glyphs = [
1472            glyph('M', 137.66, 143.74),
1473            glyph('O', 143.74, 149.82),
1474            glyph('D', 149.82, 155.90),
1475            glyph('E', 155.90, 161.98),
1476            glyph(' ', 161.84, 164.09),
1477            glyph('t', 163.82, 166.60),
1478            glyph('o', 166.60, 171.60),
1479        ];
1480        let (lines, words) = line_and_word_cells(&glyphs, 792.0, true);
1481        let words: Vec<&str> = words.iter().map(|w| w.text.as_str()).collect();
1482        assert_eq!(words, ["MODE", "to"]);
1483        assert_eq!(lines.len(), 1);
1484        assert_eq!(lines[0].text, "MODE to");
1485    }
1486
1487    /// #609: a chart's y-axis ticks set one under another at the same x (each
1488    /// tick placed by its own `cm`, same `Tm`) are six line cells with their
1489    /// own boxes, as in docling-parse — not one `345678` cell with the first
1490    /// tick's box. A ligature decomposed at one box still recomposes.
1491    #[test]
1492    fn stacked_glyphs_at_one_x_stay_separate_cells() {
1493        let at = |ch: char, b: f32| Glyph {
1494            lb: b,
1495            lt: b + 10.0,
1496            b,
1497            t: b + 10.0,
1498            ..glyph(ch, 98.0, 103.0)
1499        };
1500        let ticks: Vec<Glyph> = "345678"
1501            .chars()
1502            .enumerate()
1503            .map(|(k, ch)| at(ch, 316.0 + 25.92 * k as f32))
1504            .collect();
1505        let lines = line_cells(&ticks, 792.0, true);
1506        let texts: Vec<&str> = lines.iter().map(|c| c.text.as_str()).collect();
1507        assert_eq!(texts, ["3", "4", "5", "6", "7", "8"]);
1508        assert!(lines.windows(2).all(|w| w[0].t > w[1].t));
1509
1510        let lig = [glyph('f', 10.0, 16.0), glyph('i', 10.0, 16.0)];
1511        let lines = line_cells(&lig, 792.0, true);
1512        assert_eq!(lines.len(), 1);
1513        assert_eq!(lines[0].text, "fi");
1514    }
1515
1516    /// The returned vectors own no more than their cells. Collecting straight
1517    /// from the per-glyph `Cell` buffer reused its allocation (std's in-place
1518    /// collect), so a page kept ~4 slots per *glyph* — on a dense table page,
1519    /// 30× the cells' size, for every page the text-layer path held.
1520    #[test]
1521    fn cells_do_not_keep_the_glyph_buffer() {
1522        // Ten rows of `777 777 …`: abutting glyphs, words split by space glyphs.
1523        let glyphs: Vec<Glyph> = (0..400)
1524            .map(|i| {
1525                let x = (i % 40) as f32 * 6.0;
1526                let ch = if i % 4 == 3 { ' ' } else { '7' };
1527                let mut g = glyph(ch, x, x + 6.0);
1528                let row = (i / 40) as f32 * 14.0;
1529                (g.b, g.t, g.lb, g.lt) = (100.0 + row, 110.0 + row, 98.0 + row, 110.0 + row);
1530                g
1531            })
1532            .collect();
1533        let (lines, words) = line_and_word_cells(&glyphs, 792.0, true);
1534        assert_eq!((lines.len(), words.len()), (10, 100));
1535        assert_eq!(lines.capacity(), lines.len());
1536        assert_eq!(words.capacity(), words.len());
1537    }
1538
1539    /// #921, page 8 of the reporter's collective agreement: `und dem` sits in
1540    /// a second font resource between runs of the body font, word gaps are
1541    /// cursor moves (no space glyph). Glyph boxes as the parser reads them.
1542    fn und_dem_line() -> Vec<Glyph> {
1543        let at = |ch: char, l: f32, r: f32, font: u64| Glyph {
1544            ch,
1545            l,
1546            b: 682.056,
1547            r,
1548            t: 691.05,
1549            ll: l,
1550            lb: 682.056,
1551            lr: r,
1552            lt: 691.05,
1553            font,
1554            quad: None,
1555            pen: None,
1556            math_font: false,
1557            invisible: false,
1558        };
1559        let mut g = Vec::new();
1560        let mut run = |text: &str, edges: &[f32], font: u64| {
1561            for (i, ch) in text.chars().enumerate() {
1562                g.push(at(ch, edges[i], edges[i + 1], font));
1563            }
1564        };
1565        run(
1566            "schaft",
1567            &[
1568                328.976, 333.216, 338.572, 344.325, 350.486, 353.920, 357.248,
1569            ],
1570            1,
1571        );
1572        run("und", &[359.261, 365.121, 370.875, 377.035], 2);
1573        run("dem", &[378.990, 385.151, 390.701, 399.287], 2);
1574        run("Öst", &[401.214, 409.092, 413.332, 416.660], 1);
1575        g
1576    }
1577
1578    #[test]
1579    fn legacy_rule_keeps_the_borderline_und_dem_glued() {
1580        // The baselines' rule: the cell restarts at the font change, so the
1581        // threshold is 0.33 × the mean advance of `und` alone (1.9553 pt)
1582        // and the 1.9550 pt gap stays inside the word.
1583        let (lines, words) = line_and_word_cells(&und_dem_line(), 792.0, true);
1584        assert!(lines.iter().any(|c| c.text == "unddem"), "{lines:?}");
1585        assert!(words.iter().any(|c| c.text == "unddem"), "{words:?}");
1586    }
1587
1588    #[test]
1589    fn line_local_word_gaps_split_und_dem() {
1590        for gap in [WordGap::Adaptive, WordGap::Factor(0.2)] {
1591            let (lines, words) = line_and_word_cells_with(&und_dem_line(), 792.0, true, gap);
1592            let texts: Vec<&str> = lines.iter().map(|c| c.text.as_str()).collect();
1593            assert_eq!(texts, ["schaft und dem Öst"], "{gap:?}");
1594            let texts: Vec<&str> = words.iter().map(|c| c.text.as_str()).collect();
1595            assert_eq!(texts, ["schaft", "und", "dem", "Öst"], "{gap:?}");
1596            // The word boxes are the glyphs' own extent.
1597            assert!((words[1].l - 359.261).abs() < 1e-3 && (words[1].r - 377.035).abs() < 1e-3);
1598        }
1599        // A factor above the normalized gaps (0.234 … 0.438) keeps them all.
1600        let (lines, _) =
1601            line_and_word_cells_with(&und_dem_line(), 792.0, true, WordGap::Factor(0.5));
1602        assert_eq!(lines[0].text, "schaftunddemÖst");
1603    }
1604
1605    #[test]
1606    fn a_superscript_attaches_by_pen_origin_and_math_face() {
1607        // `Lysak` at 10 pt, then `[0000` at 7 pt raised `rise` pt with no gap.
1608        // The baseline test reads the pens' origins and font sizes, as
1609        // docling-parse 7 does (`pen: None` falls back to the loose boxes).
1610        let at = |ch: char, l: f32, y: f32, size: f32, math: bool, pen: bool| Glyph {
1611            lb: y - 0.2 * size,
1612            lt: y + 0.8 * size,
1613            b: y - 0.2 * size,
1614            t: y + 0.8 * size,
1615            pen: pen.then_some([l, y, size]),
1616            math_font: math,
1617            ..glyph(ch, l, l + 0.5 * size)
1618        };
1619        let line = |rise: f32, math: bool, pen: bool| {
1620            let mut g: Vec<Glyph> = "Lysak"
1621                .chars()
1622                .enumerate()
1623                .map(|(k, ch)| at(ch, 100.0 + 5.0 * k as f32, 600.0, 10.0, math, pen))
1624                .collect();
1625            g.extend(
1626                "[0000"
1627                    .chars()
1628                    .enumerate()
1629                    .map(|(k, ch)| at(ch, 125.0 + 3.5 * k as f32, 600.0 + rise, 7.0, math, pen)),
1630            );
1631            let (lines, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1632            (
1633                lines[0].text.clone(),
1634                words.iter().map(|w| w.text.clone()).collect::<Vec<_>>(),
1635            )
1636        };
1637        let one = |s: &str| (s.to_string(), vec![s.to_string()]);
1638        let two = |s: &str| {
1639            (
1640                s.to_string(),
1641                vec!["Lysak".to_string(), "[0000".to_string()],
1642            )
1643        };
1644        // 2305.03393v1's ORCID: 3.6 pt up is more than 0.35 × 7 pt, a new word
1645        // unless it is a local attachment, which a TeX face (`cmr`) makes it.
1646        // Not a math face: two words, spaced — the raised run *opens* a
1647        // bracket, which is not the #992 join (that is for a run after an
1648        // opening bracket or before a closing one).
1649        assert_eq!(line(3.6, true, true), one("Lysak[0000"));
1650        assert_eq!(line(3.6, false, true), two("Lysak [0000"));
1651        // 2 pt up: on the pens 2.0 ≤ 0.35 × 7, one word; the boxes' bottoms
1652        // differ by the descents too (2.6 pt), which read it as two.
1653        assert_eq!(line(2.0, false, true), one("Lysak[0000"));
1654        assert_eq!(line(2.0, false, false), two("Lysak [0000"));
1655    }
1656
1657    /// #992: a raised footnote marker between parentheses — `(`, a 6.8 pt
1658    /// `1` 3.5 pt up, `)` — is three word cells (the baseline rule) but the
1659    /// line reads `(1)` as the page does; with a real gap before the marker
1660    /// (`EG (1)`) the space is the gap's, as before. The same raised `1`
1661    /// right after a letter keeps docling's space (`EG 1`): only a bracket
1662    /// joins.
1663    #[test]
1664    fn a_touching_superscript_joins_the_line_text_inside_brackets_only() {
1665        let at = |ch: char, l: f32, w: f32, y: f32, size: f32| Glyph {
1666            lb: y - 0.2 * size,
1667            lt: y + 0.8 * size,
1668            b: y - 0.2 * size,
1669            t: y + 0.8 * size,
1670            pen: Some([l, y, size]),
1671            ..glyph(ch, l, l + w)
1672        };
1673        let g = [
1674            at('E', 100.0, 6.0, 600.0, 10.5),
1675            at('G', 106.0, 6.9, 600.0, 10.5),
1676            at('(', 115.3, 3.2, 600.0, 10.5),
1677            at('1', 118.5, 3.1, 603.5, 6.8),
1678            at(')', 121.6, 3.2, 600.0, 10.5),
1679            at('e', 127.2, 5.0, 600.0, 10.5),
1680        ];
1681        let (lines, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1682        assert_eq!(lines[0].text, "EG (1) e");
1683        let words: Vec<&str> = words.iter().map(|w| w.text.as_str()).collect();
1684        assert_eq!(words, ["EG", "(", "1", ")", "e"]);
1685        // `EG` then the raised `1` touching the `G`: docling's `EG 1`.
1686        let g = [
1687            at('E', 100.0, 6.0, 600.0, 10.5),
1688            at('G', 106.0, 6.9, 600.0, 10.5),
1689            at('1', 112.9, 3.1, 603.5, 6.8),
1690        ];
1691        let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1692        assert_eq!(lines[0].text, "EG 1");
1693    }
1694
1695    #[test]
1696    fn a_factor_keeps_docling_parse_s_floor_on_lines_with_space_glyphs() {
1697        // `Verpf` + `lichtungen` 0.6 pt apart (0.24 of the flanking advances)
1698        // on a line whose word spaces are glyphs: below the 0.35 floor
1699        // docling-parse 7 keeps for such lines, so it is not a boundary even
1700        // under a factor of 0.2. The same gap on a space-less line splits.
1701        let mut g = Vec::new();
1702        let mut x = 100.0f32;
1703        let put = |g: &mut Vec<Glyph>, s: &str, x: &mut f32| {
1704            for ch in s.chars() {
1705                g.push(glyph(ch, *x, *x + 2.5));
1706                *x += 2.5;
1707            }
1708        };
1709        put(&mut g, "Die", &mut x);
1710        g.push(glyph(' ', x, x + 2.5));
1711        x += 2.5;
1712        put(&mut g, "Verpf", &mut x);
1713        x += 0.6;
1714        put(&mut g, "lichtungen", &mut x);
1715        let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Factor(0.2));
1716        assert_eq!(lines[0].text, "Die Verpflichtungen");
1717        let spaceless: Vec<Glyph> = g.into_iter().filter(|c| c.ch != ' ').collect();
1718        let (lines, _) = line_and_word_cells_with(&spaceless, 792.0, true, WordGap::Factor(0.2));
1719        assert_eq!(lines[0].text, "Die Verpf lichtungen");
1720    }
1721
1722    #[test]
1723    fn right_to_left_glyphs_in_visual_order_stay_one_line() {
1724        // Arabic drawn in visual order (the pen moves left to right, as most
1725        // producers store it): the gap runs along the pen, not against the
1726        // script — reversed, every glyph pair read as a step back of two
1727        // advances and each glyph became a line of its own.
1728        let mut g = Vec::new();
1729        let mut x = 100.0f32;
1730        for (k, word) in [
1731            "\u{0631}\u{0627}\u{0632}\u{0627}\u{0628}",
1732            "\u{0631}\u{062f}",
1733        ]
1734        .iter()
1735        .enumerate()
1736        {
1737            if k > 0 {
1738                x += 3.0;
1739            }
1740            for ch in word.chars() {
1741                g.push(glyph(ch, x, x + 5.0));
1742                x += 5.0;
1743            }
1744        }
1745        for gap in [WordGap::Adaptive, WordGap::Factor(0.2)] {
1746            let (lines, words) = line_and_word_cells_with(&g, 792.0, true, gap);
1747            assert_eq!(
1748                lines.len(),
1749                1,
1750                "{gap:?}: {:?}",
1751                lines.iter().map(|c| &c.text).collect::<Vec<_>>()
1752            );
1753            assert_eq!(words.len(), 2, "{gap:?}");
1754        }
1755    }
1756
1757    /// The line cells of `glyphs` under the adaptive rule, with
1758    /// `DOCLING_RS_PDF_ZERO_ADVANCE_RUN` as given.
1759    fn line_texts(glyphs: &[Glyph], zero_advance_run: bool) -> Vec<String> {
1760        line_and_word_cells_cut(glyphs, 792.0, true, WordGap::Adaptive, zero_advance_run)
1761            .0
1762            .into_iter()
1763            .map(|c| c.text)
1764            .collect()
1765    }
1766
1767    /// Glyphs set one after the other from x = 100, each with its advance.
1768    fn set(chars: &[(char, f32)]) -> Vec<Glyph> {
1769        let mut x = 100.0f32;
1770        chars
1771            .iter()
1772            .map(|&(ch, w)| {
1773                let g = glyph(ch, x, x + w);
1774                x += w;
1775                g
1776            })
1777            .collect()
1778    }
1779
1780    #[test]
1781    fn a_zero_advance_glyph_cuts_the_line_only_when_asked() {
1782        // An Arabic mark drawn before its base, as LibreOffice writes a
1783        // cluster: the mark has no advance, so docling-parse finds no
1784        // trailing edge for the base to face and starts a run there — a
1785        // word in two cells, which its line sort then sets apart. We keep
1786        // the line, and cut it as docling-parse does under the knob.
1787        let line = |mark_advance: f32| {
1788            set(&[
1789                ('\u{0627}', 3.0),
1790                ('\u{064b}', mark_advance),
1791                ('\u{0645}', 6.0),
1792                ('\u{0626}', 3.0),
1793                ('\u{0627}', 3.0),
1794                ('\u{062f}', 5.0),
1795            ])
1796        };
1797        let whole = "\u{062f}\u{0627}\u{0626}\u{0645}\u{064b}\u{0627}";
1798        assert_eq!(line_texts(&line(0.0), false), [whole]);
1799        assert_eq!(
1800            line_texts(&line(0.0), true),
1801            ["\u{064b}\u{0627}", "\u{062f}\u{0627}\u{0626}\u{0645}"]
1802        );
1803        // With any advance at all the mark is no cut for either.
1804        assert_eq!(line_texts(&line(0.5), true), [whole]);
1805    }
1806
1807    #[test]
1808    fn zero_advance_glyphs_of_other_scripts_stay_in_their_line() {
1809        // A decomposed Latin accent (`e` + U+0301, the mark with no advance):
1810        // one line by default; under the knob the line breaks after the
1811        // accent, as in docling-parse.
1812        let accent = set(&[
1813            ('c', 5.0),
1814            ('a', 5.0),
1815            ('f', 3.0),
1816            ('e', 5.0),
1817            ('\u{0301}', 0.0),
1818            ('s', 4.0),
1819        ]);
1820        assert_eq!(line_texts(&accent, false), ["cafe\u{0301}s"]);
1821        assert_eq!(line_texts(&accent, true), ["cafe\u{0301}", "s"]);
1822        // A font whose `/Widths` are all zero, every glyph on the one spot:
1823        // `build_cells` already joins them into one cell (glyphs sharing a
1824        // box are a decomposed ligature), so the line runs never see a
1825        // zero-advance pair and the knob changes nothing.
1826        let one_spot = set(&[('a', 0.0), ('b', 0.0), ('c', 0.0)]);
1827        assert_eq!(line_texts(&one_spot, false), ["abc"]);
1828        assert_eq!(line_texts(&one_spot, true), ["abc"]);
1829        // The same widths with the glyphs set apart by `TJ` kerning: each
1830        // a cell of no advance, so here the line runs do see the pairs. By
1831        // default the x-axis fallback keeps one line (three words: with no
1832        // advance, a 3 pt gap is measured against half the glyph height);
1833        // under the knob every glyph starts a run, as docling-parse has it —
1834        // which is why the knob stays off.
1835        let set_apart = vec![
1836            glyph('a', 100.0, 100.0),
1837            glyph('b', 103.0, 103.0),
1838            glyph('c', 106.0, 106.0),
1839        ];
1840        assert_eq!(line_texts(&set_apart, false), ["a b c"]);
1841        assert_eq!(line_texts(&set_apart, true), ["a", "b", "c"]);
1842    }
1843
1844    #[test]
1845    fn letter_spacing_stays_one_word_under_the_adaptive_rule() {
1846        // Sperrsatz: every letter 1.5 pt apart, the words 6 pt apart. The
1847        // line's gaps form two clusters, so the letters stay together.
1848        let mut g = Vec::new();
1849        let mut x = 100.0f32;
1850        for (k, word) in ["Allgemeine", "Bestimmungen"].iter().enumerate() {
1851            if k > 0 {
1852                x += 6.0;
1853            }
1854            for ch in word.chars() {
1855                g.push(glyph(ch, x, x + 5.0));
1856                x += 5.0 + 1.5;
1857            }
1858            x -= 1.5;
1859        }
1860        let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1861        assert_eq!(lines[0].text, "Allgemeine Bestimmungen");
1862    }
1863
1864    /// Glyphs 2.5 pt wide on a line at `y`, each `(text, gap before)` piece
1865    /// set after the previous one; `' '` pieces are space glyphs.
1866    fn set_line(pieces: &[(&str, f32)], y: f32) -> Vec<Glyph> {
1867        let mut g = Vec::new();
1868        let mut x = 100.0f32;
1869        for (text, gap) in pieces {
1870            x += gap;
1871            for ch in text.chars() {
1872                g.push(Glyph {
1873                    b: y,
1874                    t: y + 10.0,
1875                    lb: y - 2.0,
1876                    lt: y + 10.0,
1877                    ..glyph(ch, x, x + 2.5)
1878                });
1879                x += 2.5;
1880            }
1881        }
1882        g
1883    }
1884
1885    #[test]
1886    fn one_wide_gap_does_not_raise_the_line_s_word_gap() {
1887        // #921, EVU p. 3: word gaps of 0.32 advances in tight justified text
1888        // and one gap of 3.2 before a tab stop. Unclipped, the wide gap is
1889        // the high cluster alone, the midpoint caps at 0.35 and the line
1890        // reads `jedochwerdenweiterlaufende`.
1891        let g = set_line(
1892            &[
1893                ("jedoch", 0.0),
1894                ("werden", 0.8),
1895                ("weiterlaufende", 0.8),
1896                ("Quartierkosten", 8.0),
1897            ],
1898            600.0,
1899        );
1900        let (_, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1901        let texts: Vec<&str> = words.iter().map(|c| c.text.as_str()).collect();
1902        assert_eq!(
1903            texts,
1904            ["jedoch", "werden", "weiterlaufende", "Quartierkosten"]
1905        );
1906    }
1907
1908    #[test]
1909    fn a_lone_word_on_a_page_that_draws_spaces_keeps_its_kerning() {
1910        // #921, EUR-Lex: `Offenlegungspf` + `lichten` 0.8 pt apart (0.32
1911        // advances) in a one-word table cell. On a page whose lines carry
1912        // space glyphs the gap is kerning, not a word boundary; on a
1913        // space-less page (TeX, Arbortext) the same line splits.
1914        let lone = || set_line(&[("Offenlegungspf", 0.0), ("lichten", 0.8)], 500.0);
1915        let spaced = |y| {
1916            set_line(
1917                &[
1918                    ("Die", 0.0),
1919                    (" ", 0.0),
1920                    ("Taxonomie", 0.0),
1921                    (" ", 0.0),
1922                    ("gilt", 0.0),
1923                ],
1924                y,
1925            )
1926        };
1927        let mut page = lone();
1928        page.extend(spaced(600.0));
1929        page.extend(spaced(620.0));
1930        let texts = |g: &[Glyph]| {
1931            let (lines, _) = line_and_word_cells_with(g, 792.0, true, WordGap::Adaptive);
1932            lines.into_iter().map(|c| c.text).collect::<Vec<_>>()
1933        };
1934        assert!(texts(&page).contains(&"Offenlegungspflichten".to_string()));
1935        assert_eq!(texts(&lone()), ["Offenlegungspf lichten"]);
1936    }
1937
1938    #[test]
1939    fn a_line_whose_spaces_are_drawn_before_its_letters_infers_its_gap() {
1940        // LibreOffice's Arabic: the line's space glyphs first, then its
1941        // letters in visual order, the words 1.7 pt apart (0.34 advances).
1942        // The spaces fall to the run before, so the Arabic run has none of
1943        // its own; judged as a lone word on a spaced page, the 0.35 cap
1944        // glued every word, where docling-parse infers the line's gap.
1945        let mut page = set_line(&[("The", 0.0), (" ", 0.0), ("manual", 0.0)], 600.0);
1946        page.extend(set_line(
1947            &[("For", 0.0), (" ", 0.0), ("safety", 0.0)],
1948            620.0,
1949        ));
1950        let words = ["نشكرك", "على", "شراء"];
1951        let (mut spaces, mut letters) = (Vec::new(), Vec::new());
1952        let mut x = 100.0f32;
1953        for (k, word) in words.iter().rev().enumerate() {
1954            if k > 0 {
1955                spaces.push(glyph(' ', x, x + 1.7));
1956                x += 1.7;
1957            }
1958            for ch in word.chars().rev() {
1959                letters.push(glyph(ch, x, x + 5.0));
1960                x += 5.0;
1961            }
1962        }
1963        page.extend(spaces);
1964        page.extend(letters);
1965        let (lines, _) = line_and_word_cells_with(&page, 792.0, true, WordGap::Adaptive);
1966        let texts: Vec<&str> = lines.iter().map(|c| c.text.as_str()).collect();
1967        assert!(texts.contains(&"نشكرك على شراء"), "{texts:?}");
1968    }
1969
1970    #[test]
1971    fn a_lone_word_beside_another_line_s_space_keeps_its_kerning() {
1972        // #921's one-word cell on a spaced page, with a space glyph of
1973        // another line drawn near it but in none of its gaps: after the
1974        // word's end on its own height, or under its kerning gap with half
1975        // its height below the line. The word stays whole. The same glyph in
1976        // the gap, on the line, makes the line one whose spaces were drawn
1977        // apart, and its gap is inferred as docling-parse infers it.
1978        let spaced = |y| {
1979            set_line(
1980                &[
1981                    ("Die", 0.0),
1982                    (" ", 0.0),
1983                    ("Taxonomie", 0.0),
1984                    (" ", 0.0),
1985                    ("gilt", 0.0),
1986                ],
1987                y,
1988            )
1989        };
1990        // `Offenlegungspf` ends at 135, `lichten` starts at 135.8.
1991        let lone = || set_line(&[("Offenlegungspf", 0.0), ("lichten", 0.8)], 500.0);
1992        let space = |l: f32, r: f32, y: f32| Glyph {
1993            b: y,
1994            t: y + 10.0,
1995            lb: y - 2.0,
1996            lt: y + 10.0,
1997            ..glyph(' ', l, r)
1998        };
1999        let line_with = |stray: Glyph| {
2000            let mut page = spaced(600.0);
2001            page.extend(spaced(620.0));
2002            page.push(stray);
2003            page.extend(lone());
2004            let (lines, _) = line_and_word_cells_with(&page, 792.0, true, WordGap::Adaptive);
2005            lines
2006                .into_iter()
2007                .map(|c| c.text)
2008                .find(|t| t.starts_with("Offen"))
2009                .expect("the lone word's line")
2010        };
2011        assert_eq!(
2012            line_with(space(154.0, 155.7, 500.0)),
2013            "Offenlegungspflichten"
2014        );
2015        assert_eq!(
2016            line_with(space(135.0, 135.8, 494.0)),
2017            "Offenlegungspflichten"
2018        );
2019        assert_eq!(
2020            line_with(space(135.0, 135.8, 500.0)),
2021            "Offenlegungspf lichten"
2022        );
2023    }
2024
2025    #[test]
2026    fn a_space_drawn_apart_is_judged_on_both_glyphs_beside_it() {
2027        // A raised mark's box (104–110) is half the height of the space
2028        // after it (98–110): on the mark's band alone the space was not on
2029        // the line; with the letter after the gap it is.
2030        let mark = Glyph {
2031            lb: 104.0,
2032            ..glyph('\u{064b}', 100.0, 103.0)
2033        };
2034        let cells = build_cells(
2035            &[
2036                mark,
2037                glyph('\u{0644}', 105.0, 110.0),
2038                glyph(' ', 103.2, 104.8),
2039            ],
2040            true,
2041        );
2042        let run: Vec<RunCell> = cells[..2].iter().map(RunCell::new).collect();
2043        let spaces = [(0.5 * (cells[2].b_b + cells[2].b_t), &cells[2])];
2044        assert!(spaces_drawn_apart(&run, &spaces));
2045    }
2046
2047    #[test]
2048    fn word_gap_spellings() {
2049        assert_eq!(WordGap::parse("adaptive"), Ok(WordGap::Adaptive));
2050        assert_eq!(WordGap::parse(" Legacy "), Ok(WordGap::Legacy));
2051        assert_eq!(WordGap::parse("0.2"), Ok(WordGap::Factor(0.2)));
2052        for bad in ["0", "-1", "5", "nan", "wide"] {
2053            assert!(WordGap::parse(bad).is_err(), "{bad}");
2054        }
2055    }
2056}