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/// Whether one of the page's space glyphs sits in a gap between two
1186/// consecutive glyphs of `run` (its middle inside the gap along the run's
1187/// writing direction, most of its height within the band of the two glyphs
1188/// beside it). Such a line draws its
1189/// word spaces, only not between its letters: LibreOffice sets an Arabic
1190/// line's spaces first and then its letters in visual order, so the spaces
1191/// fall to the run open before them and this run has none of its own.
1192/// `spaces` are the page's space cells by the middle of their height.
1193fn spaces_drawn_apart(run: &[RunCell], spaces: &[(f64, &Cell)]) -> bool {
1194    let mut visible = run.iter().filter(|c| !c.space);
1195    let Some(first) = visible.next() else {
1196        return false;
1197    };
1198    // The spaces inside the run's extent; most runs have none.
1199    let (mut l, mut r, mut b, mut t) = bounds(first.cell);
1200    for c in visible.clone() {
1201        let (cl, cr, cb, ct) = bounds(c.cell);
1202        (l, r, b, t) = (l.min(cl), r.max(cr), b.min(cb), t.max(ct));
1203    }
1204    let (lo, hi) = (
1205        spaces.partition_point(|&(y, _)| y < b),
1206        spaces.partition_point(|&(y, _)| y <= t),
1207    );
1208    let inside: Vec<&Cell> = spaces[lo..hi]
1209        .iter()
1210        .map(|&(_, c)| c)
1211        .filter(|c| (l..=r).contains(&(0.5 * (c.b_l + c.b_r))))
1212        .collect();
1213    if inside.is_empty() {
1214        return false;
1215    }
1216    let (ux, uy) = (first.ux, first.uy);
1217    let along = |x: f64, y: f64| x * ux + y * uy;
1218    let across = |c: &Cell| {
1219        let v = [
1220            c.rx0 * -uy + c.ry0 * ux,
1221            c.rx1 * -uy + c.ry1 * ux,
1222            c.rx2 * -uy + c.ry2 * ux,
1223            c.rx3 * -uy + c.ry3 * ux,
1224        ];
1225        let lo = v.iter().copied().fold(f64::INFINITY, f64::min);
1226        let hi = v.iter().copied().fold(f64::NEG_INFINITY, f64::max);
1227        (lo, hi)
1228    };
1229    // The open gaps, as (trailing edge, leading edge, the band of the two
1230    // glyphs beside the gap: an Arabic mark's box can be shorter than the
1231    // space after it).
1232    let mut gaps = Vec::new();
1233    let mut prev = first;
1234    for c in visible {
1235        let (lhs, rhs) = (prev.cell, c.cell);
1236        let tail = along(0.5 * (lhs.rx1 + lhs.rx2), 0.5 * (lhs.ry1 + lhs.ry2));
1237        let head = along(0.5 * (rhs.rx0 + rhs.rx3), 0.5 * (rhs.ry0 + rhs.ry3));
1238        if head > tail {
1239            let ((l0, l1), (r0, r1)) = (across(lhs), across(rhs));
1240            gaps.push((tail, head, (l0.min(r0), l1.max(r1))));
1241        }
1242        prev = c;
1243    }
1244    inside.iter().any(|c| {
1245        let mid = along(0.5 * (c.rx0 + c.rx2), 0.5 * (c.ry0 + c.ry2));
1246        let (s0, s1) = across(c);
1247        gaps.iter().any(|&(tail, head, (b0, b1))| {
1248            tail <= mid && mid <= head && s1.min(b1) - s0.max(b0) > 0.5 * (s1 - s0)
1249        })
1250    })
1251}
1252
1253/// docling-parse ≥ 7's contraction (`cells.h::contract`) over our char
1254/// cells, with the word threshold `gap` picks: the line runs, their words,
1255/// and the lines as the words joined by single spaces.
1256fn contract_runs(cells: &[Cell], gap: WordGap, page_h: f32) -> (Vec<TextCell>, Vec<TextCell>) {
1257    // Line runs, in source order. Explicit spaces belong to the open run as
1258    // boundary markers and take no part in the geometry test.
1259    let mut runs: Vec<Vec<RunCell>> = Vec::new();
1260    for c in cells.iter().filter(|c| !c.text.is_empty()) {
1261        let rc = RunCell::new(c);
1262        if rc.space {
1263            match runs.last_mut() {
1264                Some(run) => run.push(rc),
1265                None => runs.push(vec![rc]),
1266            }
1267            continue;
1268        }
1269        let starts = match runs.last().and_then(|r| r.iter().rev().find(|c| !c.space)) {
1270            Some(prev) => !continues_line(prev, &rc),
1271            None => runs.is_empty(),
1272        };
1273        if starts {
1274            runs.push(Vec::new());
1275        }
1276        runs.last_mut().expect("a run is open").push(rc);
1277    }
1278
1279    let (mut words_out, mut lines_out) = (Vec::new(), Vec::new());
1280    let page_spaced = page_draws_spaces(&runs);
1281    let mut spaces: Vec<(f64, &Cell)> = Vec::new();
1282    if page_spaced {
1283        spaces.extend(
1284            runs.iter()
1285                .flatten()
1286                .filter(|c| c.space)
1287                .map(|c| (0.5 * (c.cell.b_b + c.cell.b_t), c.cell)),
1288        );
1289        spaces.sort_by(|a, b| a.0.total_cmp(&b.0));
1290    }
1291    for run in &runs {
1292        // A line on a page whose producer draws its word spaces as glyphs is
1293        // judged like a line that draws them (below), even when it has none
1294        // of its own: a lone word in a table cell or a heading carries no
1295        // space glyph, and its only open gap is kerning — EUR-Lex's
1296        // `Offenlegungspf|lichten` at 0.22–0.25, cut by the line-local
1297        // threshold of 0.18 (docling-parse 7 cuts it too; #921). Not a line
1298        // whose spaces were drawn apart from its letters: it is no lone word,
1299        // and like docling-parse we infer its gap — under the cap its word
1300        // gaps of a third of an advance stayed glued (`علىشراء`).
1301        let has_spaces =
1302            run.iter().any(|c| c.space) || (page_spaced && !spaces_drawn_apart(run, &spaces));
1303        let tracked = tracked_gaps(run);
1304        // A line that draws its word spaces as glyphs marks its boundaries
1305        // itself; docling-parse 7 splits an unmarked gap there only above
1306        // 0.35 (`min(0.35, 1.0)`). A fixed factor keeps that floor: its job
1307        // is the space-less lines (#921), and below it a spaced line's
1308        // loosely kerned pairs fall apart — EUR-Lex's `f|l` at 0.24 read
1309        // `Verpf lichtungen` under 0.2.
1310        let threshold = match gap {
1311            WordGap::Factor(f) if has_spaces => f.max(0.35),
1312            WordGap::Factor(f) => f,
1313            _ => (if has_spaces {
1314                1.0
1315            } else {
1316                infer_word_gap(run, &tracked)
1317            })
1318            .min(0.35),
1319        };
1320        let mut words: Vec<Agg> = Vec::new();
1321        let mut prev: Option<&RunCell> = None;
1322        let mut boundary = false;
1323        for (i, c) in run.iter().enumerate() {
1324            if c.space {
1325                boundary = true;
1326                continue;
1327            }
1328            let mut starts = words.is_empty() || boundary;
1329            let mut glued = false;
1330            // A TOC leader may omit the boundary before its first dot while
1331            // spacing every later one: keep that dot with the leader.
1332            if !starts
1333                && c.cell.text == "."
1334                && i + 4 < run.len()
1335                && run[i + 1].space
1336                && run[i + 2].cell.text == "."
1337                && run[i + 3].space
1338                && run[i + 4].cell.text == "."
1339                && prev.is_some_and(|p| p.cell.text != ".")
1340            {
1341                starts = true;
1342            }
1343            if let (false, Some(p)) = (starts, prev) {
1344                let shifted = !baselines_compatible(p, c);
1345                let gapped = !tracked[i] && normalized_gap(p, c) > threshold;
1346                starts = shifted || gapped;
1347                // A baseline shift with the glyphs touching, inside a
1348                // bracket: docling-parse starts a word
1349                // (`word_baselines_compatible`) and its line text then reads
1350                // `Richtlinie 2003/71/EG ( 1 )` for a raised footnote marker
1351                // where the page shows `(1)` and pdftotext / pdfium read it
1352                // so (#992). The word stays its own cell; the line text
1353                // joins it as the page does. Only after an opening bracket
1354                // or before a closing one: elsewhere docling's space is the
1355                // more useful reading — `SynthTabNet 1 .`, `1 https://…`,
1356                // `상해 1) 나`, the `1 /4` fraction — and joining them cost
1357                // five groundtruth files when this rule had no bracket test.
1358                let opens = |s: &str| matches!(s.chars().last(), Some('(' | '[' | '{'));
1359                let closes = |s: &str| matches!(s.chars().next(), Some(')' | ']' | '}'));
1360                glued = shifted
1361                    && !gapped
1362                    && (words.last().is_some_and(|w| opens(&w.text)) || closes(&c.cell.text));
1363            }
1364            if starts {
1365                words.push(Agg::of(c.cell, glued));
1366            } else {
1367                let q = [
1368                    c.cell.rx0, c.cell.ry0, c.cell.rx1, c.cell.ry1, c.cell.rx2, c.cell.ry2,
1369                    c.cell.rx3, c.cell.ry3,
1370                ];
1371                words.last_mut().expect("a word is open").append(
1372                    &c.cell.text,
1373                    c.cell.ltr,
1374                    &q,
1375                    false,
1376                );
1377            }
1378            prev = Some(c);
1379            boundary = false;
1380        }
1381        let mut it = words.into_iter();
1382        let Some(first) = it.next() else {
1383            continue;
1384        };
1385        let mut line = Agg {
1386            text: first.text.clone(),
1387            ltr: first.ltr,
1388            q: first.q,
1389            glued: false,
1390        };
1391        words_out.push(first.into_cell(page_h));
1392        for w in it {
1393            line.append(&w.text, w.ltr, &w.q, !w.glued);
1394            words_out.push(w.into_cell(page_h));
1395        }
1396        lines_out.push(line.into_cell(page_h));
1397    }
1398    (lines_out, words_out)
1399}
1400
1401#[cfg(test)]
1402mod tests {
1403    use super::*;
1404
1405    fn glyph(ch: char, l: f32, r: f32) -> Glyph {
1406        Glyph {
1407            ch,
1408            l,
1409            b: 100.0,
1410            r,
1411            t: 110.0,
1412            ll: l,
1413            lb: 98.0,
1414            lr: r,
1415            lt: 110.0,
1416            font: 0,
1417            quad: None,
1418            pen: None,
1419            math_font: false,
1420            invisible: false,
1421        }
1422    }
1423
1424    /// Tight-set Latin (a table cell in a born-digital manual): the gap between
1425    /// `MODE` and `to` (1.84 pt) is under the 0.33 × average-width word gate (2.0 pt), so
1426    /// only the space glyph between them keeps the words apart. docling-parse
1427    /// erases spaces after the word contraction, not before.
1428    #[test]
1429    fn space_glyph_separates_tight_words() {
1430        let glyphs = [
1431            glyph('M', 137.66, 143.74),
1432            glyph('O', 143.74, 149.82),
1433            glyph('D', 149.82, 155.90),
1434            glyph('E', 155.90, 161.98),
1435            glyph(' ', 161.84, 164.09),
1436            glyph('t', 163.82, 166.60),
1437            glyph('o', 166.60, 171.60),
1438        ];
1439        let (lines, words) = line_and_word_cells(&glyphs, 792.0, true);
1440        let words: Vec<&str> = words.iter().map(|w| w.text.as_str()).collect();
1441        assert_eq!(words, ["MODE", "to"]);
1442        assert_eq!(lines.len(), 1);
1443        assert_eq!(lines[0].text, "MODE to");
1444    }
1445
1446    /// #609: a chart's y-axis ticks set one under another at the same x (each
1447    /// tick placed by its own `cm`, same `Tm`) are six line cells with their
1448    /// own boxes, as in docling-parse — not one `345678` cell with the first
1449    /// tick's box. A ligature decomposed at one box still recomposes.
1450    #[test]
1451    fn stacked_glyphs_at_one_x_stay_separate_cells() {
1452        let at = |ch: char, b: f32| Glyph {
1453            lb: b,
1454            lt: b + 10.0,
1455            b,
1456            t: b + 10.0,
1457            ..glyph(ch, 98.0, 103.0)
1458        };
1459        let ticks: Vec<Glyph> = "345678"
1460            .chars()
1461            .enumerate()
1462            .map(|(k, ch)| at(ch, 316.0 + 25.92 * k as f32))
1463            .collect();
1464        let lines = line_cells(&ticks, 792.0, true);
1465        let texts: Vec<&str> = lines.iter().map(|c| c.text.as_str()).collect();
1466        assert_eq!(texts, ["3", "4", "5", "6", "7", "8"]);
1467        assert!(lines.windows(2).all(|w| w[0].t > w[1].t));
1468
1469        let lig = [glyph('f', 10.0, 16.0), glyph('i', 10.0, 16.0)];
1470        let lines = line_cells(&lig, 792.0, true);
1471        assert_eq!(lines.len(), 1);
1472        assert_eq!(lines[0].text, "fi");
1473    }
1474
1475    /// The returned vectors own no more than their cells. Collecting straight
1476    /// from the per-glyph `Cell` buffer reused its allocation (std's in-place
1477    /// collect), so a page kept ~4 slots per *glyph* — on a dense table page,
1478    /// 30× the cells' size, for every page the text-layer path held.
1479    #[test]
1480    fn cells_do_not_keep_the_glyph_buffer() {
1481        // Ten rows of `777 777 …`: abutting glyphs, words split by space glyphs.
1482        let glyphs: Vec<Glyph> = (0..400)
1483            .map(|i| {
1484                let x = (i % 40) as f32 * 6.0;
1485                let ch = if i % 4 == 3 { ' ' } else { '7' };
1486                let mut g = glyph(ch, x, x + 6.0);
1487                let row = (i / 40) as f32 * 14.0;
1488                (g.b, g.t, g.lb, g.lt) = (100.0 + row, 110.0 + row, 98.0 + row, 110.0 + row);
1489                g
1490            })
1491            .collect();
1492        let (lines, words) = line_and_word_cells(&glyphs, 792.0, true);
1493        assert_eq!((lines.len(), words.len()), (10, 100));
1494        assert_eq!(lines.capacity(), lines.len());
1495        assert_eq!(words.capacity(), words.len());
1496    }
1497
1498    /// #921, page 8 of the reporter's collective agreement: `und dem` sits in
1499    /// a second font resource between runs of the body font, word gaps are
1500    /// cursor moves (no space glyph). Glyph boxes as the parser reads them.
1501    fn und_dem_line() -> Vec<Glyph> {
1502        let at = |ch: char, l: f32, r: f32, font: u64| Glyph {
1503            ch,
1504            l,
1505            b: 682.056,
1506            r,
1507            t: 691.05,
1508            ll: l,
1509            lb: 682.056,
1510            lr: r,
1511            lt: 691.05,
1512            font,
1513            quad: None,
1514            pen: None,
1515            math_font: false,
1516            invisible: false,
1517        };
1518        let mut g = Vec::new();
1519        let mut run = |text: &str, edges: &[f32], font: u64| {
1520            for (i, ch) in text.chars().enumerate() {
1521                g.push(at(ch, edges[i], edges[i + 1], font));
1522            }
1523        };
1524        run(
1525            "schaft",
1526            &[
1527                328.976, 333.216, 338.572, 344.325, 350.486, 353.920, 357.248,
1528            ],
1529            1,
1530        );
1531        run("und", &[359.261, 365.121, 370.875, 377.035], 2);
1532        run("dem", &[378.990, 385.151, 390.701, 399.287], 2);
1533        run("Öst", &[401.214, 409.092, 413.332, 416.660], 1);
1534        g
1535    }
1536
1537    #[test]
1538    fn legacy_rule_keeps_the_borderline_und_dem_glued() {
1539        // The baselines' rule: the cell restarts at the font change, so the
1540        // threshold is 0.33 × the mean advance of `und` alone (1.9553 pt)
1541        // and the 1.9550 pt gap stays inside the word.
1542        let (lines, words) = line_and_word_cells(&und_dem_line(), 792.0, true);
1543        assert!(lines.iter().any(|c| c.text == "unddem"), "{lines:?}");
1544        assert!(words.iter().any(|c| c.text == "unddem"), "{words:?}");
1545    }
1546
1547    #[test]
1548    fn line_local_word_gaps_split_und_dem() {
1549        for gap in [WordGap::Adaptive, WordGap::Factor(0.2)] {
1550            let (lines, words) = line_and_word_cells_with(&und_dem_line(), 792.0, true, gap);
1551            let texts: Vec<&str> = lines.iter().map(|c| c.text.as_str()).collect();
1552            assert_eq!(texts, ["schaft und dem Öst"], "{gap:?}");
1553            let texts: Vec<&str> = words.iter().map(|c| c.text.as_str()).collect();
1554            assert_eq!(texts, ["schaft", "und", "dem", "Öst"], "{gap:?}");
1555            // The word boxes are the glyphs' own extent.
1556            assert!((words[1].l - 359.261).abs() < 1e-3 && (words[1].r - 377.035).abs() < 1e-3);
1557        }
1558        // A factor above the normalized gaps (0.234 … 0.438) keeps them all.
1559        let (lines, _) =
1560            line_and_word_cells_with(&und_dem_line(), 792.0, true, WordGap::Factor(0.5));
1561        assert_eq!(lines[0].text, "schaftunddemÖst");
1562    }
1563
1564    #[test]
1565    fn a_superscript_attaches_by_pen_origin_and_math_face() {
1566        // `Lysak` at 10 pt, then `[0000` at 7 pt raised `rise` pt with no gap.
1567        // The baseline test reads the pens' origins and font sizes, as
1568        // docling-parse 7 does (`pen: None` falls back to the loose boxes).
1569        let at = |ch: char, l: f32, y: f32, size: f32, math: bool, pen: bool| Glyph {
1570            lb: y - 0.2 * size,
1571            lt: y + 0.8 * size,
1572            b: y - 0.2 * size,
1573            t: y + 0.8 * size,
1574            pen: pen.then_some([l, y, size]),
1575            math_font: math,
1576            ..glyph(ch, l, l + 0.5 * size)
1577        };
1578        let line = |rise: f32, math: bool, pen: bool| {
1579            let mut g: Vec<Glyph> = "Lysak"
1580                .chars()
1581                .enumerate()
1582                .map(|(k, ch)| at(ch, 100.0 + 5.0 * k as f32, 600.0, 10.0, math, pen))
1583                .collect();
1584            g.extend(
1585                "[0000"
1586                    .chars()
1587                    .enumerate()
1588                    .map(|(k, ch)| at(ch, 125.0 + 3.5 * k as f32, 600.0 + rise, 7.0, math, pen)),
1589            );
1590            let (lines, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1591            (
1592                lines[0].text.clone(),
1593                words.iter().map(|w| w.text.clone()).collect::<Vec<_>>(),
1594            )
1595        };
1596        let one = |s: &str| (s.to_string(), vec![s.to_string()]);
1597        let two = |s: &str| {
1598            (
1599                s.to_string(),
1600                vec!["Lysak".to_string(), "[0000".to_string()],
1601            )
1602        };
1603        // 2305.03393v1's ORCID: 3.6 pt up is more than 0.35 × 7 pt, a new word
1604        // unless it is a local attachment, which a TeX face (`cmr`) makes it.
1605        // Not a math face: two words, spaced — the raised run *opens* a
1606        // bracket, which is not the #992 join (that is for a run after an
1607        // opening bracket or before a closing one).
1608        assert_eq!(line(3.6, true, true), one("Lysak[0000"));
1609        assert_eq!(line(3.6, false, true), two("Lysak [0000"));
1610        // 2 pt up: on the pens 2.0 ≤ 0.35 × 7, one word; the boxes' bottoms
1611        // differ by the descents too (2.6 pt), which read it as two.
1612        assert_eq!(line(2.0, false, true), one("Lysak[0000"));
1613        assert_eq!(line(2.0, false, false), two("Lysak [0000"));
1614    }
1615
1616    /// #992: a raised footnote marker between parentheses — `(`, a 6.8 pt
1617    /// `1` 3.5 pt up, `)` — is three word cells (the baseline rule) but the
1618    /// line reads `(1)` as the page does; with a real gap before the marker
1619    /// (`EG (1)`) the space is the gap's, as before. The same raised `1`
1620    /// right after a letter keeps docling's space (`EG 1`): only a bracket
1621    /// joins.
1622    #[test]
1623    fn a_touching_superscript_joins_the_line_text_inside_brackets_only() {
1624        let at = |ch: char, l: f32, w: f32, y: f32, size: f32| Glyph {
1625            lb: y - 0.2 * size,
1626            lt: y + 0.8 * size,
1627            b: y - 0.2 * size,
1628            t: y + 0.8 * size,
1629            pen: Some([l, y, size]),
1630            ..glyph(ch, l, l + w)
1631        };
1632        let g = [
1633            at('E', 100.0, 6.0, 600.0, 10.5),
1634            at('G', 106.0, 6.9, 600.0, 10.5),
1635            at('(', 115.3, 3.2, 600.0, 10.5),
1636            at('1', 118.5, 3.1, 603.5, 6.8),
1637            at(')', 121.6, 3.2, 600.0, 10.5),
1638            at('e', 127.2, 5.0, 600.0, 10.5),
1639        ];
1640        let (lines, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1641        assert_eq!(lines[0].text, "EG (1) e");
1642        let words: Vec<&str> = words.iter().map(|w| w.text.as_str()).collect();
1643        assert_eq!(words, ["EG", "(", "1", ")", "e"]);
1644        // `EG` then the raised `1` touching the `G`: docling's `EG 1`.
1645        let g = [
1646            at('E', 100.0, 6.0, 600.0, 10.5),
1647            at('G', 106.0, 6.9, 600.0, 10.5),
1648            at('1', 112.9, 3.1, 603.5, 6.8),
1649        ];
1650        let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1651        assert_eq!(lines[0].text, "EG 1");
1652    }
1653
1654    #[test]
1655    fn a_factor_keeps_docling_parse_s_floor_on_lines_with_space_glyphs() {
1656        // `Verpf` + `lichtungen` 0.6 pt apart (0.24 of the flanking advances)
1657        // on a line whose word spaces are glyphs: below the 0.35 floor
1658        // docling-parse 7 keeps for such lines, so it is not a boundary even
1659        // under a factor of 0.2. The same gap on a space-less line splits.
1660        let mut g = Vec::new();
1661        let mut x = 100.0f32;
1662        let put = |g: &mut Vec<Glyph>, s: &str, x: &mut f32| {
1663            for ch in s.chars() {
1664                g.push(glyph(ch, *x, *x + 2.5));
1665                *x += 2.5;
1666            }
1667        };
1668        put(&mut g, "Die", &mut x);
1669        g.push(glyph(' ', x, x + 2.5));
1670        x += 2.5;
1671        put(&mut g, "Verpf", &mut x);
1672        x += 0.6;
1673        put(&mut g, "lichtungen", &mut x);
1674        let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Factor(0.2));
1675        assert_eq!(lines[0].text, "Die Verpflichtungen");
1676        let spaceless: Vec<Glyph> = g.into_iter().filter(|c| c.ch != ' ').collect();
1677        let (lines, _) = line_and_word_cells_with(&spaceless, 792.0, true, WordGap::Factor(0.2));
1678        assert_eq!(lines[0].text, "Die Verpf lichtungen");
1679    }
1680
1681    #[test]
1682    fn right_to_left_glyphs_in_visual_order_stay_one_line() {
1683        // Arabic drawn in visual order (the pen moves left to right, as most
1684        // producers store it): the gap runs along the pen, not against the
1685        // script — reversed, every glyph pair read as a step back of two
1686        // advances and each glyph became a line of its own.
1687        let mut g = Vec::new();
1688        let mut x = 100.0f32;
1689        for (k, word) in [
1690            "\u{0631}\u{0627}\u{0632}\u{0627}\u{0628}",
1691            "\u{0631}\u{062f}",
1692        ]
1693        .iter()
1694        .enumerate()
1695        {
1696            if k > 0 {
1697                x += 3.0;
1698            }
1699            for ch in word.chars() {
1700                g.push(glyph(ch, x, x + 5.0));
1701                x += 5.0;
1702            }
1703        }
1704        for gap in [WordGap::Adaptive, WordGap::Factor(0.2)] {
1705            let (lines, words) = line_and_word_cells_with(&g, 792.0, true, gap);
1706            assert_eq!(
1707                lines.len(),
1708                1,
1709                "{gap:?}: {:?}",
1710                lines.iter().map(|c| &c.text).collect::<Vec<_>>()
1711            );
1712            assert_eq!(words.len(), 2, "{gap:?}");
1713        }
1714    }
1715
1716    #[test]
1717    fn letter_spacing_stays_one_word_under_the_adaptive_rule() {
1718        // Sperrsatz: every letter 1.5 pt apart, the words 6 pt apart. The
1719        // line's gaps form two clusters, so the letters stay together.
1720        let mut g = Vec::new();
1721        let mut x = 100.0f32;
1722        for (k, word) in ["Allgemeine", "Bestimmungen"].iter().enumerate() {
1723            if k > 0 {
1724                x += 6.0;
1725            }
1726            for ch in word.chars() {
1727                g.push(glyph(ch, x, x + 5.0));
1728                x += 5.0 + 1.5;
1729            }
1730            x -= 1.5;
1731        }
1732        let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1733        assert_eq!(lines[0].text, "Allgemeine Bestimmungen");
1734    }
1735
1736    /// Glyphs 2.5 pt wide on a line at `y`, each `(text, gap before)` piece
1737    /// set after the previous one; `' '` pieces are space glyphs.
1738    fn set_line(pieces: &[(&str, f32)], y: f32) -> Vec<Glyph> {
1739        let mut g = Vec::new();
1740        let mut x = 100.0f32;
1741        for (text, gap) in pieces {
1742            x += gap;
1743            for ch in text.chars() {
1744                g.push(Glyph {
1745                    b: y,
1746                    t: y + 10.0,
1747                    lb: y - 2.0,
1748                    lt: y + 10.0,
1749                    ..glyph(ch, x, x + 2.5)
1750                });
1751                x += 2.5;
1752            }
1753        }
1754        g
1755    }
1756
1757    #[test]
1758    fn one_wide_gap_does_not_raise_the_line_s_word_gap() {
1759        // #921, EVU p. 3: word gaps of 0.32 advances in tight justified text
1760        // and one gap of 3.2 before a tab stop. Unclipped, the wide gap is
1761        // the high cluster alone, the midpoint caps at 0.35 and the line
1762        // reads `jedochwerdenweiterlaufende`.
1763        let g = set_line(
1764            &[
1765                ("jedoch", 0.0),
1766                ("werden", 0.8),
1767                ("weiterlaufende", 0.8),
1768                ("Quartierkosten", 8.0),
1769            ],
1770            600.0,
1771        );
1772        let (_, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1773        let texts: Vec<&str> = words.iter().map(|c| c.text.as_str()).collect();
1774        assert_eq!(
1775            texts,
1776            ["jedoch", "werden", "weiterlaufende", "Quartierkosten"]
1777        );
1778    }
1779
1780    #[test]
1781    fn a_lone_word_on_a_page_that_draws_spaces_keeps_its_kerning() {
1782        // #921, EUR-Lex: `Offenlegungspf` + `lichten` 0.8 pt apart (0.32
1783        // advances) in a one-word table cell. On a page whose lines carry
1784        // space glyphs the gap is kerning, not a word boundary; on a
1785        // space-less page (TeX, Arbortext) the same line splits.
1786        let lone = || set_line(&[("Offenlegungspf", 0.0), ("lichten", 0.8)], 500.0);
1787        let spaced = |y| {
1788            set_line(
1789                &[
1790                    ("Die", 0.0),
1791                    (" ", 0.0),
1792                    ("Taxonomie", 0.0),
1793                    (" ", 0.0),
1794                    ("gilt", 0.0),
1795                ],
1796                y,
1797            )
1798        };
1799        let mut page = lone();
1800        page.extend(spaced(600.0));
1801        page.extend(spaced(620.0));
1802        let texts = |g: &[Glyph]| {
1803            let (lines, _) = line_and_word_cells_with(g, 792.0, true, WordGap::Adaptive);
1804            lines.into_iter().map(|c| c.text).collect::<Vec<_>>()
1805        };
1806        assert!(texts(&page).contains(&"Offenlegungspflichten".to_string()));
1807        assert_eq!(texts(&lone()), ["Offenlegungspf lichten"]);
1808    }
1809
1810    #[test]
1811    fn a_line_whose_spaces_are_drawn_before_its_letters_infers_its_gap() {
1812        // LibreOffice's Arabic: the line's space glyphs first, then its
1813        // letters in visual order, the words 1.7 pt apart (0.34 advances).
1814        // The spaces fall to the run before, so the Arabic run has none of
1815        // its own; judged as a lone word on a spaced page, the 0.35 cap
1816        // glued every word, where docling-parse infers the line's gap.
1817        let mut page = set_line(&[("The", 0.0), (" ", 0.0), ("manual", 0.0)], 600.0);
1818        page.extend(set_line(
1819            &[("For", 0.0), (" ", 0.0), ("safety", 0.0)],
1820            620.0,
1821        ));
1822        let words = ["نشكرك", "على", "شراء"];
1823        let (mut spaces, mut letters) = (Vec::new(), Vec::new());
1824        let mut x = 100.0f32;
1825        for (k, word) in words.iter().rev().enumerate() {
1826            if k > 0 {
1827                spaces.push(glyph(' ', x, x + 1.7));
1828                x += 1.7;
1829            }
1830            for ch in word.chars().rev() {
1831                letters.push(glyph(ch, x, x + 5.0));
1832                x += 5.0;
1833            }
1834        }
1835        page.extend(spaces);
1836        page.extend(letters);
1837        let (lines, _) = line_and_word_cells_with(&page, 792.0, true, WordGap::Adaptive);
1838        let texts: Vec<&str> = lines.iter().map(|c| c.text.as_str()).collect();
1839        assert!(texts.contains(&"نشكرك على شراء"), "{texts:?}");
1840    }
1841
1842    #[test]
1843    fn a_lone_word_beside_another_line_s_space_keeps_its_kerning() {
1844        // #921's one-word cell on a spaced page, with a space glyph of
1845        // another line drawn near it but in none of its gaps: after the
1846        // word's end on its own height, or under its kerning gap with half
1847        // its height below the line. The word stays whole. The same glyph in
1848        // the gap, on the line, makes the line one whose spaces were drawn
1849        // apart, and its gap is inferred as docling-parse infers it.
1850        let spaced = |y| {
1851            set_line(
1852                &[
1853                    ("Die", 0.0),
1854                    (" ", 0.0),
1855                    ("Taxonomie", 0.0),
1856                    (" ", 0.0),
1857                    ("gilt", 0.0),
1858                ],
1859                y,
1860            )
1861        };
1862        // `Offenlegungspf` ends at 135, `lichten` starts at 135.8.
1863        let lone = || set_line(&[("Offenlegungspf", 0.0), ("lichten", 0.8)], 500.0);
1864        let space = |l: f32, r: f32, y: f32| Glyph {
1865            b: y,
1866            t: y + 10.0,
1867            lb: y - 2.0,
1868            lt: y + 10.0,
1869            ..glyph(' ', l, r)
1870        };
1871        let line_with = |stray: Glyph| {
1872            let mut page = spaced(600.0);
1873            page.extend(spaced(620.0));
1874            page.push(stray);
1875            page.extend(lone());
1876            let (lines, _) = line_and_word_cells_with(&page, 792.0, true, WordGap::Adaptive);
1877            lines
1878                .into_iter()
1879                .map(|c| c.text)
1880                .find(|t| t.starts_with("Offen"))
1881                .expect("the lone word's line")
1882        };
1883        assert_eq!(
1884            line_with(space(154.0, 155.7, 500.0)),
1885            "Offenlegungspflichten"
1886        );
1887        assert_eq!(
1888            line_with(space(135.0, 135.8, 494.0)),
1889            "Offenlegungspflichten"
1890        );
1891        assert_eq!(
1892            line_with(space(135.0, 135.8, 500.0)),
1893            "Offenlegungspf lichten"
1894        );
1895    }
1896
1897    #[test]
1898    fn a_space_drawn_apart_is_judged_on_both_glyphs_beside_it() {
1899        // A raised mark's box (104–110) is half the height of the space
1900        // after it (98–110): on the mark's band alone the space was not on
1901        // the line; with the letter after the gap it is.
1902        let mark = Glyph {
1903            lb: 104.0,
1904            ..glyph('\u{064b}', 100.0, 103.0)
1905        };
1906        let cells = build_cells(
1907            &[
1908                mark,
1909                glyph('\u{0644}', 105.0, 110.0),
1910                glyph(' ', 103.2, 104.8),
1911            ],
1912            true,
1913        );
1914        let run: Vec<RunCell> = cells[..2].iter().map(RunCell::new).collect();
1915        let spaces = [(0.5 * (cells[2].b_b + cells[2].b_t), &cells[2])];
1916        assert!(spaces_drawn_apart(&run, &spaces));
1917    }
1918
1919    #[test]
1920    fn word_gap_spellings() {
1921        assert_eq!(WordGap::parse("adaptive"), Ok(WordGap::Adaptive));
1922        assert_eq!(WordGap::parse(" Legacy "), Ok(WordGap::Legacy));
1923        assert_eq!(WordGap::parse("0.2"), Ok(WordGap::Factor(0.2)));
1924        for bad in ["0", "-1", "5", "nan", "wide"] {
1925            assert!(WordGap::parse(bad).is_err(), "{bad}");
1926        }
1927    }
1928}