Skip to main content

docling_pdf/
tf_core.rs

1//! ONNX-free half of the TableFormer pipeline: the 448 encoder-input
2//! preprocessing, the autoregressive loop's structure corrections and bbox
3//! bookkeeping, span merging, and the OTSL→grid layout. Everything here is pure
4//! Rust (no `ort`), so the browser build (#157 stage 3) runs the *same*
5//! conformance-critical logic the native pipeline does and delegates only the
6//! three ONNX graphs (encoder / decoder / bbox) to ONNX Runtime Web. Keeping
7//! one implementation is what keeps the wasm table structure identical to the
8//! native CPU path; drift can only come from the runtime kernels.
9//!
10//! `tableformer.rs` (native, `ml` feature) owns the `ort` sessions and the
11//! owned-value KV-cache fast path; it calls into here for the parts that don't
12//! touch the runtime.
13
14pub use crate::assemble::TableGrid;
15use image::RgbImage;
16
17/// The encoder's fixed square input side.
18pub const SIDE: u32 = 448;
19// Verbatim from docling's tm_config.json image_normalization (more digits than
20// f32 holds; kept exact for provenance).
21#[allow(clippy::excessive_precision)]
22pub const MEAN: [f32; 3] = [0.94247851, 0.94254675, 0.94292611];
23#[allow(clippy::excessive_precision)]
24pub const STD: [f32; 3] = [0.17910956, 0.17940403, 0.17931663];
25/// Cap on decode steps (docling's generation limit).
26pub const MAX_STEPS: usize = 1024;
27/// A row this many OTSL tags wide means the decoder has stopped emitting row
28/// breaks (it repeats `lcel` until [`MAX_STEPS`]): decoding stops there and
29/// the structure is rejected, so the table falls back to geometric
30/// reconstruction (see [`BboxBook::runaway`]). A 448-px encoder input cannot
31/// resolve 256 columns (< 2 px each); real tables stay far below this (the
32/// PDF groundtruth corpus peaks at 12 columns).
33pub const MAX_ROW_TAGS: usize = 256;
34/// The decoder hidden width, and the bbox decoder's per-cell `tag_h` stride.
35pub const EMBED_DIM: usize = 512;
36
37/// OTSL structure tokens (TableModel04_rs wordmap indices).
38pub const START: i64 = 2;
39pub const END: i64 = 3;
40pub const ECEL: i64 = 4; // empty cell
41pub const FCEL: i64 = 5; // full (content) cell
42pub const LCEL: i64 = 6; // left-looking: extends the cell to its left (colspan)
43pub const UCEL: i64 = 7; // up-looking: extends the cell above (rowspan)
44pub const XCEL: i64 = 8; // cross: spans both ways
45pub const NL: i64 = 9; // new row
46pub const CHED: i64 = 10; // column header
47pub const RHED: i64 = 11; // row header
48pub const SROW: i64 = 12; // section row
49
50const CELL_TAGS: [i64; 6] = [FCEL, ECEL, XCEL, CHED, RHED, SROW];
51
52/// A predicted table cell: an OTSL grid position (with spans) + its box in the
53/// 448 image normalized cxcywh, the OTSL tag, and the bbox decoder's cell
54/// class (docling's `cell_class`; 2 = full, ≤1 = predicted empty).
55#[derive(Debug, Clone)]
56pub struct TableCell {
57    pub row: usize,
58    pub col: usize,
59    pub colspan: usize,
60    pub rowspan: usize,
61    pub tag: i64,
62    pub class: i64,
63    pub cx: f32,
64    pub cy: f32,
65    pub w: f32,
66    pub h: f32,
67}
68
69/// Resize `img` to `SIDE×SIDE` (bilinear, aligned to docling's half-pixel
70/// centers) and normalize, laid out `(C, W, H)` as the exported encoder expects
71/// — the raw `[1,3,SIDE,SIDE]` float buffer. The native path wraps this in an
72/// `ort` tensor; the browser path hands it to ONNX Runtime Web directly.
73pub fn preprocess_input(img: &RgbImage) -> Vec<f32> {
74    let nn = (SIDE * SIDE) as usize;
75    let side = SIDE as usize;
76    let (sw, sh) = (img.width() as i32, img.height() as i32);
77    let sxr = sw as f32 / SIDE as f32;
78    let syr = sh as f32 / SIDE as f32;
79    let mut data = vec![0f32; 3 * nn];
80    for h in 0..side {
81        let fy = (h as f32 + 0.5) * syr - 0.5;
82        let wy = fy - fy.floor();
83        let y0c = (fy.floor() as i32).clamp(0, sh - 1) as u32;
84        let y1c = (fy.floor() as i32 + 1).clamp(0, sh - 1) as u32;
85        for w in 0..side {
86            let fx = (w as f32 + 0.5) * sxr - 0.5;
87            let wx = fx - fx.floor();
88            let x0c = (fx.floor() as i32).clamp(0, sw - 1) as u32;
89            let x1c = (fx.floor() as i32 + 1).clamp(0, sw - 1) as u32;
90            let p00 = img.get_pixel(x0c, y0c);
91            let p01 = img.get_pixel(x1c, y0c);
92            let p10 = img.get_pixel(x0c, y1c);
93            let p11 = img.get_pixel(x1c, y1c);
94            let idx = w * side + h; // (C, W, H): c*n + w*H + h
95            for c in 0..3 {
96                let top = p00[c] as f32 * (1.0 - wx) + p01[c] as f32 * wx;
97                let bot = p10[c] as f32 * (1.0 - wx) + p11[c] as f32 * wx;
98                let v = top * (1.0 - wy) + bot * wy;
99                data[c * nn + idx] = (v / 255.0 - MEAN[c]) / STD[c];
100            }
101        }
102    }
103    data
104}
105
106/// docling's two structure corrections, applied to a raw argmax tag: `xcel`
107/// collapses to `lcel` (its `line_num` is never incremented, so this fires on
108/// every row), and an `lcel` right after a `ucel` becomes a full cell.
109pub fn correct(raw: i64, prev_ucel: bool) -> i64 {
110    let mut tag = raw;
111    if tag == XCEL {
112        tag = LCEL;
113    }
114    if prev_ucel && tag == LCEL {
115        tag = FCEL;
116    }
117    tag
118}
119
120/// The autoregressive loop's per-step state, mirroring docling's `predict`
121/// bookkeeping (`tag_H_buf` / `bboxes_to_merge`): which decoder hidden states
122/// feed the bbox decoder and how horizontal spans merge. Both the native and
123/// browser loops step the decoder themselves (sync vs async `ort`) and feed
124/// each result through [`step`](Self::step); everything else stays here so the
125/// two paths can't drift.
126#[derive(Default)]
127pub struct BboxBook {
128    /// The decoder input prefix (`[START]`, then every emitted tag).
129    pub tags: Vec<i64>,
130    /// The emitted OTSL structure tokens (no `START`/`END`).
131    pub otsl: Vec<i64>,
132    /// Per-bbox-cell decoder hidden states, flattened `[n, EMBED_DIM]`.
133    pub hiddens: Vec<f32>,
134    /// Number of hidden states collected (`hiddens.len() / EMBED_DIM`).
135    pub n: usize,
136    /// Span merges: `cur_bbox_ind → partner` (`-1` → the last box).
137    pub merge: std::collections::HashMap<usize, i64>,
138    prev_ucel: bool,
139    skip: bool,
140    first_lcel: bool,
141    bbox_ind: usize,
142    cur_bbox_ind: usize,
143    /// Tags emitted since the last `nl` (the current row's width so far).
144    row_len: usize,
145}
146
147impl BboxBook {
148    pub fn new() -> Self {
149        Self {
150            tags: vec![START],
151            skip: true, // first tag after <start> is skipped
152            first_lcel: true,
153            ..Default::default()
154        }
155    }
156
157    /// Feed one raw decoded tag and its hidden state. Returns `false` to stop
158    /// decoding: when the corrected tag is `END` (not recorded), or when the
159    /// current row reached [`MAX_ROW_TAGS`] ([`runaway`](Self::runaway)).
160    pub fn step(&mut self, raw: i64, hidden: &[f32]) -> bool {
161        let tag = correct(raw, self.prev_ucel);
162        if tag == END {
163            return false;
164        }
165        // docling's tag_H_buf / bboxes_to_merge bookkeeping.
166        if !self.skip && matches!(tag, FCEL | ECEL | CHED | RHED | SROW | NL | UCEL) {
167            self.hiddens.extend_from_slice(hidden);
168            self.n += 1;
169            if !self.first_lcel {
170                self.merge.insert(self.cur_bbox_ind, self.bbox_ind as i64);
171            }
172            self.bbox_ind += 1;
173        }
174        if tag != LCEL {
175            self.first_lcel = true;
176        } else if self.first_lcel {
177            self.hiddens.extend_from_slice(hidden);
178            self.n += 1;
179            self.first_lcel = false;
180            self.cur_bbox_ind = self.bbox_ind;
181            self.merge.insert(self.cur_bbox_ind, -1);
182            self.bbox_ind += 1;
183        }
184        self.skip = matches!(tag, NL | UCEL | XCEL);
185        self.prev_ucel = tag == UCEL;
186        self.otsl.push(tag);
187        self.tags.push(tag);
188        self.row_len = if tag == NL { 0 } else { self.row_len + 1 };
189        self.row_len < MAX_ROW_TAGS
190    }
191
192    /// The decode degenerated into one endless row (no `nl` for
193    /// [`MAX_ROW_TAGS`] tags). docling keeps such a sequence, but its span
194    /// recovery (`html_to_otsl` knows colspans 2–20 only) and orphan pickup
195    /// then drop most of the table's words; callers reject the structure so
196    /// the region takes the geometric fallback instead. A long table that
197    /// merely hits [`MAX_STEPS`] with ordinary rows is not a runaway.
198    pub fn runaway(&self) -> bool {
199        self.row_len >= MAX_ROW_TAGS
200    }
201
202    /// Why the decoded structure cannot describe a table, or `None` — the
203    /// [`runaway`](Self::runaway) early stop plus docling's
204    /// `degenerate_structure_reason` (docling#4592) over [`otsl`](Self::otsl).
205    pub fn degenerate_reason(&self) -> Option<String> {
206        if self.runaway() {
207            return Some(format!("no row break in {MAX_ROW_TAGS} tags"));
208        }
209        degenerate_structure_reason(&self.otsl, MAX_STEPS)
210    }
211}
212
213/// docling's `degenerate_structure_reason` (docling#4592): a complete table
214/// always ends with a row break, so a sequence with no `nl` at all (30 `fcel`
215/// would lay out as a 1 × 30 grid the matcher drops most words from), or one
216/// that stops within two tokens of the step budget without a final `nl` (cut
217/// mid-row), is rejected. An empty sequence is not degenerate — it is the
218/// no-structure case callers already handle.
219pub fn degenerate_structure_reason(otsl: &[i64], max_steps: usize) -> Option<String> {
220    if otsl.is_empty() {
221        return None;
222    }
223    if !otsl.contains(&NL) {
224        return Some("the predicted structure has no row break".into());
225    }
226    if otsl.len() + 2 >= max_steps && otsl.last() != Some(&NL) {
227        return Some(format!(
228            "the predicted structure hit the {max_steps}-step decode limit"
229        ));
230    }
231    None
232}
233
234/// docling's `mergebboxes` (cxcywh): the union box of a horizontal span's first
235/// and last cell.
236fn mergebboxes(b1: [f32; 4], b2: [f32; 4]) -> [f32; 4] {
237    let new_w = (b2[0] + b2[2] / 2.0) - (b1[0] - b1[2] / 2.0);
238    let new_h = (b2[1] + b2[3] / 2.0) - (b1[1] - b1[3] / 2.0);
239    let new_left = b1[0] - b1[2] / 2.0;
240    let new_top = (b2[1] - b2[3] / 2.0).min(b1[1] - b1[3] / 2.0);
241    [new_left + new_w / 2.0, new_top + new_h / 2.0, new_w, new_h]
242}
243
244/// Apply docling's span merges: each merge key combines its box with the partner
245/// (`-1` → the last box); partners are dropped. The merged cell keeps the
246/// *first* box's class, matching docling's `outputs_class1.append(cls1)`.
247pub fn merge_spans(
248    boxes: &[[f32; 4]],
249    classes: &[i64],
250    merge: &std::collections::HashMap<usize, i64>,
251) -> (Vec<[f32; 4]>, Vec<i64>) {
252    let skip: std::collections::HashSet<usize> = merge
253        .values()
254        .filter(|&&v| v >= 0)
255        .map(|&v| v as usize)
256        .collect();
257    let mut out = Vec::new();
258    let mut out_classes = Vec::new();
259    for (i, &b) in boxes.iter().enumerate() {
260        let class = classes.get(i).copied().unwrap_or(2);
261        if let Some(&j) = merge.get(&i) {
262            let partner = if j < 0 { boxes.len() - 1 } else { j as usize };
263            out.push(mergebboxes(b, boxes[partner.min(boxes.len() - 1)]));
264            out_classes.push(class);
265        } else if !skip.contains(&i) {
266            out.push(b);
267            out_classes.push(class);
268        }
269    }
270    (out, out_classes)
271}
272
273/// Lay the OTSL tag stream onto a grid (docling's `_build_table_cells`, OTSL
274/// mode): cell tags create cells at (row, col); `lcel`/`ucel`/`xcel` are spans
275/// (counted toward the column index but not cells). Colspan/rowspan are read off
276/// the grid (consecutive `lcel`/`ucel` to the right/below). `boxes` are indexed
277/// by cell order and aligned with the cells.
278pub fn build_table_cells(otsl: &[i64], boxes: &[[f32; 4]], classes: &[i64]) -> Vec<TableCell> {
279    // 2D grid of tags (rows split on NL) for span lookups.
280    let mut grid: Vec<Vec<i64>> = vec![Vec::new()];
281    for &t in otsl {
282        if t == NL {
283            grid.push(Vec::new());
284        } else {
285            grid.last_mut().unwrap().push(t);
286        }
287    }
288    let mut cells = Vec::new();
289    let mut cell_id = 0usize;
290    for (r, row) in grid.iter().enumerate() {
291        for (c, &tag) in row.iter().enumerate() {
292            if !CELL_TAGS.contains(&tag) {
293                continue;
294            }
295            let mut colspan = 1;
296            while c + colspan < row.len() && matches!(row[c + colspan], LCEL | XCEL) {
297                colspan += 1;
298            }
299            let mut rowspan = 1;
300            while r + rowspan < grid.len()
301                && grid[r + rowspan]
302                    .get(c)
303                    .is_some_and(|&t| matches!(t, UCEL | XCEL))
304            {
305                rowspan += 1;
306            }
307            let b = boxes.get(cell_id).copied().unwrap_or([0.0; 4]);
308            // docling defaults a class-less cell to 2 (full).
309            let class = classes.get(cell_id).copied().unwrap_or(2);
310            cells.push(TableCell {
311                row: r,
312                col: c,
313                colspan,
314                rowspan,
315                tag,
316                class,
317                cx: b[0],
318                cy: b[1],
319                w: b[2],
320                h: b[3],
321            });
322            cell_id += 1;
323        }
324    }
325    cells
326}
327
328/// Index of the maximum. Uses Rust's `max_by` (ties resolve to the *last*
329/// index; the decoder/bbox float logits don't produce exact ties in practice).
330/// Kept verbatim from the native path so the two stay bit-identical.
331pub fn argmax(v: &[f32]) -> usize {
332    v.iter()
333        .enumerate()
334        .max_by(|a, b| a.1.total_cmp(b.1))
335        .map(|(i, _)| i)
336        .unwrap_or(0)
337}
338
339use crate::pdfium_backend::TextCell;
340use crate::tf_match::{PdfWord, TfCell};
341
342/// The ONNX-free tail of TableFormer row prediction: match the page's word
343/// cells into the predicted structure `cells` and expand spans into a dense
344/// `rows × cols` text grid. `region` is `(l, t, r, b)` in page points; `cells`
345/// are in the 448 image (normalized cxcywh). Shared by the native pipeline
346/// (after `predict_table_structure`) and the browser path (after the ort-web
347/// decode loop) — identical from here on. `None` when nothing matched.
348pub fn table_rows(cells: &[TableCell], region: [f32; 4], words: &[TextCell]) -> Option<TableGrid> {
349    // Words that belong to the table: non-empty text, ≥80 % of the word's area
350    // inside the table region (docling's `get_cells_in_bbox` ios test). Ids stay
351    // the page-level word indices so text joins in stream order.
352    let table_words: Vec<PdfWord> = words
353        .iter()
354        .enumerate()
355        .filter(|(_, w)| !w.text.trim().is_empty())
356        .filter_map(|(wi, w)| {
357            let (l, t, r, b) = (w.l as f64, w.t as f64, w.r as f64, w.b as f64);
358            let area = (r - l) * (b - t);
359            let iw = (r.min(region[2] as f64) - l.max(region[0] as f64)).max(0.0);
360            let ih = (b.min(region[3] as f64) - t.max(region[1] as f64)).max(0.0);
361            if area > 0.0 && iw * ih / area > 0.8 {
362                Some(PdfWord {
363                    id: wi,
364                    bbox: [l, t, r, b],
365                    text: w.text.trim().to_string(),
366                })
367            } else {
368                None
369            }
370        })
371        .collect();
372
373    if !table_words.is_empty() && !simple_match() {
374        return docling_match_rows(cells, region, &table_words, words);
375    }
376
377    let (rw, rh) = (region[2] - region[0], region[3] - region[1]);
378
379    // Cell boxes in page points (top-left), aligned with `cells`.
380    let boxes: Vec<[f32; 4]> = cells
381        .iter()
382        .map(|c| {
383            [
384                region[0] + (c.cx - c.w / 2.0) * rw,
385                region[1] + (c.cy - c.h / 2.0) * rh,
386                region[0] + (c.cx + c.w / 2.0) * rw,
387                region[1] + (c.cy + c.h / 2.0) * rh,
388            ]
389        })
390        .collect();
391
392    // Assign each word to the cell it overlaps most (intersection / word area).
393    let mut cell_words: Vec<Vec<usize>> = vec![Vec::new(); cells.len()];
394    for (wi, w) in words.iter().enumerate() {
395        let wa = ((w.r - w.l) * (w.b - w.t)).max(1.0);
396        let mut best: Option<(f32, usize)> = None;
397        for (ci, b) in boxes.iter().enumerate() {
398            let ix = (w.r.min(b[2]) - w.l.max(b[0])).max(0.0);
399            let iy = (w.b.min(b[3]) - w.t.max(b[1])).max(0.0);
400            let io = ix * iy / wa;
401            if io > 0.0 && best.is_none_or(|(bo, _)| io > bo) {
402                best = Some((io, ci));
403            }
404        }
405        if let Some((_, ci)) = best {
406            cell_words[ci].push(wi);
407        }
408    }
409
410    let num_rows = cells.iter().map(|c| c.row + c.rowspan).max().unwrap_or(0);
411    let num_cols = cells.iter().map(|c| c.col + c.colspan).max().unwrap_or(0);
412    if num_rows == 0 || num_cols == 0 {
413        return None;
414    }
415    let mut grid = vec![vec![String::new(); num_cols]; num_rows];
416    let mut out_cells = Vec::with_capacity(cells.len());
417    for (ci, c) in cells.iter().enumerate() {
418        // Keep words in text-stream order (their word index), matching docling's
419        // cell text assembly — geometric re-sorting scrambles wrapped cells.
420        let wis = std::mem::take(&mut cell_words[ci]);
421        let text = wis
422            .iter()
423            .map(|&i| words[i].text.trim())
424            .collect::<Vec<_>>()
425            .join(" ");
426        let text = normalize_cell_text(text);
427        // Spanned cells repeat their text across the covered grid positions.
428        for row in grid.iter_mut().skip(c.row).take(c.rowspan) {
429            for cell in row.iter_mut().skip(c.col).take(c.colspan) {
430                *cell = text.clone();
431            }
432        }
433        out_cells.push(first_class_cell(text, Some(boxes[ci]), c, c.tag));
434    }
435    Some(TableGrid {
436        rows: grid,
437        cells: out_cells,
438    })
439}
440
441/// A public first-class cell (#240) from a predicted OTSL cell: the span
442/// rectangle comes from the grid layout, the header roles from the OTSL tag.
443fn first_class_cell(
444    text: String,
445    bbox: Option<[f32; 4]>,
446    c: &TableCell,
447    tag: i64,
448) -> docling_core::TableCell {
449    docling_core::TableCell {
450        text,
451        bbox,
452        start_row: c.row,
453        start_col: c.col,
454        row_span: c.rowspan.max(1),
455        col_span: c.colspan.max(1),
456        column_header: tag == CHED,
457        row_header: tag == RHED,
458        row_section: tag == SROW,
459    }
460}
461
462/// `DOCLING_RS_TF_SIMPLE_MATCH=1` reverts to the pre-#60 best-overlap word
463/// assignment (A/B escape hatch for the docling matching post-processor).
464fn simple_match() -> bool {
465    docling_core::env::flag("DOCLING_RS_TF_SIMPLE_MATCH")
466}
467
468/// docling glues `@` to whatever follows it (`mAP @0.5`, an email): the PDF's
469/// word cells split `@` from the next token, and joining with a space would
470/// widen the cell and — via the column pad — shift every row. The groundtruth
471/// never contains "@ ", so this is always the right normalization.
472fn normalize_cell_text(text: String) -> String {
473    text.replace("@ ", "@")
474}
475
476/// docling's matched-cell grid assembly (`tf_predictor.predict` with
477/// `do_cell_matching=True`): run the ported matching post-processor, group the
478/// word→cell assignments per grid position, compress the surviving row/column
479/// ids to sequential indexes, and expand spans into a dense `rows × cols` text
480/// grid. Matching runs in docling's coordinate space — the table bbox rounded
481/// to integers, everything ×2 (its page scale) — so the post-processor's
482/// absolute rounding agrees.
483fn docling_match_rows(
484    cells: &[TableCell],
485    region: [f32; 4],
486    table_words: &[PdfWord],
487    words: &[TextCell],
488) -> Option<TableGrid> {
489    const SCALE: f64 = 2.0; // docling's table-structure page scale
490    let sl = (region[0] as f64).round_ties_even() * SCALE;
491    let st = (region[1] as f64).round_ties_even() * SCALE;
492    let sr = (region[2] as f64).round_ties_even() * SCALE;
493    let sb = (region[3] as f64).round_ties_even() * SCALE;
494    let (w2, h2) = (sr - sl, sb - st);
495
496    let tf_cells: Vec<TfCell> = cells
497        .iter()
498        .enumerate()
499        .map(|(i, c)| {
500            let (cx, cy) = (c.cx as f64, c.cy as f64);
501            let (w, h) = (c.w as f64, c.h as f64);
502            TfCell {
503                bbox: [
504                    sl + (cx - w / 2.0) * w2,
505                    st + (cy - h / 2.0) * h2,
506                    sl + (cx + w / 2.0) * w2,
507                    st + (cy + h / 2.0) * h2,
508                ],
509                cell_id: i,
510                row_id: c.row,
511                column_id: c.col,
512                cell_class: c.class,
513                colspan_val: if c.colspan > 1 { c.colspan } else { 0 },
514                rowspan_val: if c.rowspan > 1 { c.rowspan } else { 0 },
515            }
516        })
517        .collect();
518
519    let scaled_words: Vec<PdfWord> = table_words
520        .iter()
521        .map(|w| PdfWord {
522            id: w.id,
523            bbox: [
524                w.bbox[0] * SCALE,
525                w.bbox[1] * SCALE,
526                w.bbox[2] * SCALE,
527                w.bbox[3] * SCALE,
528            ],
529            text: w.text.clone(),
530        })
531        .collect();
532
533    // Debug (native only): dump the matcher inputs as JSON lines for a
534    // side-by-side run against docling's Python post-processor.
535    #[cfg(feature = "ml")]
536    if let Some(dir) = docling_core::env::nonempty("DOCLING_RS_TF_MATCH_DUMP") {
537        dump_match_inputs(&dir, &tf_cells, &scaled_words);
538    }
539
540    let (cells_wo, final_matches) =
541        crate::tf_match::match_and_post_process(tf_cells, &scaled_words);
542
543    // `_merge_tf_output`: group per (column, row) in ascending-pdf-id order; the
544    // first word's table cell fixes the group's offsets and spans.
545    struct Merged {
546        start_row: usize,
547        start_col: usize,
548        row_span: usize,
549        col_span: usize,
550        word_ids: Vec<usize>,
551        /// The matched table cell's bbox, back in page points (the matcher
552        /// runs in docling's ×2 space).
553        bbox: [f32; 4],
554        /// The predicted cell's OTSL tag (header roles for #240).
555        tag: i64,
556    }
557    let mut merged: Vec<Merged> = Vec::new();
558    let mut key_ix: std::collections::HashMap<(usize, usize), usize> =
559        std::collections::HashMap::new();
560    for (&pdf_id, list) in &final_matches {
561        let tm = list[0].table_cell_id;
562        let Some(cell) = cells_wo.iter().find(|c| c.cell_id == tm) else {
563            continue;
564        };
565        match key_ix.entry((cell.column_id, cell.row_id)) {
566            std::collections::hash_map::Entry::Occupied(e) => {
567                merged[*e.get()].word_ids.push(pdf_id);
568            }
569            std::collections::hash_map::Entry::Vacant(e) => {
570                e.insert(merged.len());
571                merged.push(Merged {
572                    start_row: cell.row_id,
573                    start_col: cell.column_id,
574                    row_span: cell.rowspan_val.max(1),
575                    col_span: cell.colspan_val.max(1),
576                    word_ids: vec![pdf_id],
577                    bbox: [
578                        (cell.bbox[0] / 2.0) as f32,
579                        (cell.bbox[1] / 2.0) as f32,
580                        (cell.bbox[2] / 2.0) as f32,
581                        (cell.bbox[3] / 2.0) as f32,
582                    ],
583                    tag: cells.get(cell.cell_id).map_or(FCEL, |c| c.tag),
584                });
585            }
586        }
587    }
588    if merged.is_empty() {
589        return None;
590    }
591
592    // `multi_table_predict`'s sort_row_col_indexes: compress the surviving
593    // row/column ids to gap-free indexes.
594    let mut start_cols: Vec<usize> = merged.iter().map(|m| m.start_col).collect();
595    start_cols.sort_unstable();
596    start_cols.dedup();
597    let mut start_rows: Vec<usize> = merged.iter().map(|m| m.start_row).collect();
598    start_rows.sort_unstable();
599    start_rows.dedup();
600    let mut num_rows = 0;
601    let mut num_cols = 0;
602    for m in &mut merged {
603        m.start_col = start_cols.binary_search(&m.start_col).expect("own value");
604        m.start_row = start_rows.binary_search(&m.start_row).expect("own value");
605        num_cols = num_cols.max(m.start_col + m.col_span);
606        num_rows = num_rows.max(m.start_row + m.row_span);
607    }
608    if num_rows == 0 || num_cols == 0 {
609        return None;
610    }
611
612    let mut grid = vec![vec![String::new(); num_cols]; num_rows];
613    let mut out_cells = Vec::with_capacity(merged.len());
614    for m in &merged {
615        let text = m
616            .word_ids
617            .iter()
618            .map(|&i| words[i].text.trim())
619            .collect::<Vec<_>>()
620            .join(" ");
621        let text = normalize_cell_text(text);
622        for row in grid.iter_mut().skip(m.start_row).take(m.row_span) {
623            for cell in row.iter_mut().skip(m.start_col).take(m.col_span) {
624                *cell = text.clone();
625            }
626        }
627        out_cells.push(docling_core::TableCell {
628            text,
629            bbox: Some(m.bbox),
630            start_row: m.start_row,
631            start_col: m.start_col,
632            row_span: m.row_span,
633            col_span: m.col_span,
634            column_header: m.tag == CHED,
635            row_header: m.tag == RHED,
636            row_section: m.tag == SROW,
637        });
638    }
639    Some(TableGrid {
640        rows: grid,
641        cells: out_cells,
642    })
643}
644
645/// Append one JSON line per table into `<dir>/tf_match_dump.jsonl` with the
646/// exact matcher inputs (hand-rolled JSON to avoid a serde dependency).
647#[cfg(feature = "ml")]
648fn dump_match_inputs(dir: &str, tf_cells: &[TfCell], words: &[PdfWord]) {
649    use std::io::Write;
650    let cells: Vec<String> = tf_cells
651        .iter()
652        .map(|c| {
653            format!(
654                r#"{{"bbox":[{},{},{},{}],"cell_id":{},"row_id":{},"column_id":{},"cell_class":{},"colspan_val":{},"rowspan_val":{}}}"#,
655                c.bbox[0], c.bbox[1], c.bbox[2], c.bbox[3],
656                c.cell_id, c.row_id, c.column_id, c.cell_class,
657                c.colspan_val, c.rowspan_val
658            )
659        })
660        .collect();
661    let ws: Vec<String> = words
662        .iter()
663        .map(|w| {
664            format!(
665                r#"{{"id":{},"bbox":[{},{},{},{}],"text":{}}}"#,
666                w.id,
667                w.bbox[0],
668                w.bbox[1],
669                w.bbox[2],
670                w.bbox[3],
671                serde_json_escape(&w.text)
672            )
673        })
674        .collect();
675    let line = format!(
676        r#"{{"table_cells":[{}],"pdf_cells":[{}]}}"#,
677        cells.join(","),
678        ws.join(",")
679    );
680    if let Ok(mut f) = std::fs::OpenOptions::new()
681        .create(true)
682        .append(true)
683        .open(format!("{dir}/tf_match_dump.jsonl"))
684    {
685        let _ = writeln!(f, "{line}");
686    }
687}
688
689/// Minimal JSON string escaping for the parity dump.
690#[cfg(feature = "ml")]
691fn serde_json_escape(s: &str) -> String {
692    let mut out = String::with_capacity(s.len() + 2);
693    out.push('"');
694    for ch in s.chars() {
695        match ch {
696            '"' => out.push_str("\\\""),
697            '\\' => out.push_str("\\\\"),
698            '\n' => out.push_str("\\n"),
699            '\r' => out.push_str("\\r"),
700            '\t' => out.push_str("\\t"),
701            c if (c as u32) < 0x20 => out.push_str(&format!("\\u{:04x}", c as u32)),
702            c => out.push(c),
703        }
704    }
705    out.push('"');
706    out
707}
708
709#[cfg(test)]
710mod tests {
711    use super::*;
712
713    #[test]
714    fn corrections() {
715        assert_eq!(correct(XCEL, false), LCEL); // xcel → lcel
716        assert_eq!(correct(LCEL, true), FCEL); // lcel after ucel → fcel
717        assert_eq!(correct(XCEL, true), FCEL); // xcel → lcel → fcel
718        assert_eq!(correct(FCEL, false), FCEL);
719        assert_eq!(correct(LCEL, false), LCEL);
720    }
721
722    #[test]
723    fn argmax_behaviour() {
724        assert_eq!(argmax(&[0.1, 0.9, 0.3]), 1);
725        assert_eq!(argmax(&[0.5, 0.5]), 1); // Rust max_by ties to the last index
726        assert_eq!(argmax(&[]), 0);
727    }
728
729    #[test]
730    fn book_skips_first_and_collects_hiddens() {
731        // <start> then a 2x1 row: FCEL FCEL NL, END. The first FCEL after start
732        // is NOT skipped (skip only guards the tag right after start-consumed
733        // rows); verify hidden collection count and merge stays empty.
734        let mut b = BboxBook::new();
735        let h = [1.0f32; EMBED_DIM];
736        assert!(b.step(FCEL, &h)); // skip=true initially → not collected
737        assert!(b.step(FCEL, &h));
738        assert!(b.step(NL, &h));
739        assert!(!b.step(END, &h)); // stop
740        assert_eq!(b.otsl, vec![FCEL, FCEL, NL]);
741        // first FCEL skipped (skip=true), second FCEL + NL collected → n=2
742        assert_eq!(b.n, 2);
743        assert_eq!(b.hiddens.len(), 2 * EMBED_DIM);
744        assert!(b.merge.is_empty());
745    }
746
747    #[test]
748    fn book_merges_horizontal_span() {
749        // FCEL LCEL: the LCEL is the first-lcel of a horizontal span → records a
750        // merge partner (-1 placeholder) for the span's leading cell.
751        let mut b = BboxBook::new();
752        let h = [0.0f32; EMBED_DIM];
753        b.step(FCEL, &h); // skipped (skip=true)
754        b.step(FCEL, &h); // collected, bbox_ind 0→1
755        b.step(LCEL, &h); // first-lcel: cur=1, merge{1:-1}, bbox_ind 1→2
756        assert_eq!(b.merge.get(&1), Some(&-1));
757    }
758
759    #[test]
760    fn book_stops_runaway_row() {
761        // A dense multi-level-header table decodes as ched ched, then lcel
762        // until the step cap, never a row break.
763        let mut b = BboxBook::new();
764        let h = [0.0f32; EMBED_DIM];
765        assert!(b.step(CHED, &h));
766        assert!(b.step(CHED, &h));
767        while b.step(LCEL, &h) {
768            assert!(b.otsl.len() < MAX_STEPS);
769        }
770        assert_eq!(b.otsl.len(), MAX_ROW_TAGS);
771        assert!(b.runaway());
772    }
773
774    #[test]
775    fn book_long_table_is_not_runaway() {
776        // A tall table that fills MAX_STEPS with ordinary rows (docling
777        // truncates it the same way) keeps its structure; so does a table
778        // that ends normally.
779        let mut b = BboxBook::new();
780        let h = [0.0f32; EMBED_DIM];
781        for i in 0..MAX_STEPS {
782            assert!(b.step(if i % 32 == 31 { NL } else { FCEL }, &h));
783        }
784        assert!(!b.runaway());
785        assert_eq!(b.degenerate_reason(), None);
786        let mut b = BboxBook::new();
787        for t in [FCEL, LCEL, NL, FCEL, FCEL, NL] {
788            assert!(b.step(t, &h));
789        }
790        assert!(!b.step(END, &h));
791        assert!(!b.runaway());
792        assert_eq!(b.degenerate_reason(), None);
793    }
794
795    #[test]
796    fn book_cut_mid_row_at_the_step_budget_is_degenerate() {
797        // docling#4592: the same tall table cut mid-row by MAX_STEPS lost its
798        // last row's tail — rejected, where the runaway check alone kept it.
799        let mut b = BboxBook::new();
800        let h = [0.0f32; EMBED_DIM];
801        for i in 0..MAX_STEPS {
802            assert!(b.step(if i % 22 == 21 { NL } else { FCEL }, &h));
803        }
804        assert!(!b.runaway());
805        assert!(b.degenerate_reason().unwrap().contains("1024-step"));
806        // A short sequence without any row break: a 1 × 30 grid.
807        let mut b = BboxBook::new();
808        for _ in 0..30 {
809            assert!(b.step(FCEL, &h));
810        }
811        assert!(!b.step(END, &h));
812        assert!(b.degenerate_reason().unwrap().contains("no row break"));
813        // The runaway early stop reports as such.
814        let mut b = BboxBook::new();
815        while b.step(LCEL, &h) {}
816        assert!(b.degenerate_reason().unwrap().contains("256 tags"));
817    }
818
819    /// docling#4592 `test_degenerate_structure_reason`'s six cases.
820    #[test]
821    fn degenerate_structure_reason_cases() {
822        use super::degenerate_structure_reason as reason;
823        let rows = |n: usize, tail: &[i64]| {
824            let mut v = Vec::new();
825            for _ in 0..n {
826                v.extend(std::iter::repeat_n(FCEL, 33));
827                v.push(NL);
828            }
829            v.extend_from_slice(tail);
830            v
831        };
832        assert_eq!(reason(&[], 1024), None);
833        assert_eq!(reason(&[FCEL, FCEL, NL, FCEL, ECEL, NL], 1024), None);
834        // Cut two tags short of the budget mid-row …
835        assert!(reason(&rows(30, &[FCEL, FCEL]), 1024)
836            .unwrap()
837            .contains("limit"));
838        // … but long and complete: ends with a row break.
839        assert_eq!(reason(&rows(30, &[FCEL, NL]), 1024), None);
840        assert!(reason(&[ECEL; 1023], 1024).unwrap().contains("row break"));
841        assert!(reason(&[LCEL; 1023], 1024).unwrap().contains("row break"));
842    }
843
844    #[test]
845    fn build_cells_spans() {
846        // Row 0: FCEL LCEL  (a 1x2 colspan)
847        // Row 1: FCEL ECEL
848        let otsl = vec![FCEL, LCEL, NL, FCEL, ECEL];
849        let boxes = vec![[0.0; 4]; 3];
850        let classes = vec![2, 2, 2];
851        let cells = build_table_cells(&otsl, &boxes, &classes);
852        assert_eq!(cells.len(), 3);
853        assert_eq!((cells[0].colspan, cells[0].rowspan), (2, 1));
854        assert_eq!((cells[0].row, cells[0].col), (0, 0));
855        assert_eq!((cells[1].row, cells[1].col), (1, 0));
856    }
857}