pdf-engine 1.2.0

//! A row whose every cell holds the same number of lines is that many rows
//! (#714).
//!
//! A statement that sets no rule between its lines sometimes came out of
//! the grid with two or three of them in one row: `Interest income
//! Interest expense` in the stub and `$2,145,392 526,587` in each figure
//! column, the lines of the page stacked in one cell. Every table corpus
//! this engine is measured on writes a row per line, and TEDS charged
//! every cell of the merged row and every row it swallowed.
//!
//! THE RULE, ON THE FINAL CELLS, FROM THE SPANS. A row with no spanning
//! cell, at least two cells with text, whose every cell with text has the
//! same number of baselines -- two or more, a baseline being a run of
//! spans within half an em of each other in `y` -- is split into that many
//! rows, each taking from each cell the spans of one baseline, top to
//! bottom, the text rebuilt from those spans left to right. A row whose
//! stub wraps to two lines over one line of figures keeps its cells: the
//! counts differ. A head row keeps its cells too, flagged as one or with
//! no cell of figures in it: it wraps its column names on purpose, and the grid was
//! right to read them as one. The rows under the split move down.
//!
//! The text is rebuilt from the spans, so a cell the earlier passes tidied
//! is written as the page wrote it; `crate::cell_tidy` runs after this
//! pass and tidies it again.

// Copyright (c) 2026 Innovation Trigger B.V.
//
// PDFluent is available under two licences, at your option: the GNU AGPLv3, or
// the PDFluent Commercial Licence. See the LICENSE file in this repository --
// that file travels with the copy you received, which a URL does not.

use std::collections::HashMap;

use crate::blocks::{Block, BlockKind};
use crate::header_rows::tables_in;
use crate::text::TextSpan;

/// Split every merged row of every table in place.
pub(crate) fn split_merged_rows(blocks: &mut Vec<Block>) {
    // For each cell of a row that splits: the new row its old row starts at
    // and how many rows the old row becomes.
    let mut plan: HashMap<usize, (u16, u16)> = HashMap::new();
    let tables = tables_in(blocks);
    for &(first, end) in &tables {
        let table = &blocks[first..end];
        let rows = table
            .iter()
            .filter_map(|b| match b.kind {
                BlockKind::TableCell { row, .. } => Some(row + 1),
                _ => None,
            })
            .max()
            .unwrap_or(0);
        let mut lines_of: Vec<u16> = vec![1; rows as usize];
        // The cells of each row, once.
        let mut by_row: Vec<Vec<&Block>> = vec![Vec::new(); rows as usize];
        for b in table {
            if let BlockKind::TableCell { row, .. } = b.kind {
                by_row[row as usize].push(b);
            }
        }
        for (row, cells) in by_row.iter().enumerate() {
            // A spanning cell is a grid of its own; a head row wraps its
            // column names on purpose (`Change in / Interest Rates / (in
            // basis points)` over one column of figures) and is one row.
            let spans_or_head = cells.iter().any(|b| {
                matches!(b.kind, BlockKind::TableCell { row_span, column_span, header, .. }
                    if row_span > 1 || column_span > 1 || header)
            });
            if spans_or_head {
                continue;
            }
            // A row without a cell of figures in it is a head too, flagged
            // or not: `At December 31, 2012` names a column, `$2,145 526`
            // fills one.
            if !cells.iter().any(|b| is_figures(&b.text)) {
                continue;
            }
            let counts: Vec<usize> = cells
                .iter()
                .filter(|b| !b.text.trim().is_empty())
                .map(|b| baselines(&b.spans).len())
                .collect();
            if counts.len() < 2 {
                continue;
            }
            let k = counts[0];
            if k >= 2 && counts.iter().all(|&c| c == k) {
                lines_of[row] = k as u16;
            }
        }
        if lines_of.iter().all(|&k| k == 1) {
            continue;
        }
        let mut starts = vec![0u16; rows as usize + 1];
        for r in 0..rows as usize {
            starts[r + 1] = starts[r] + lines_of[r];
        }
        for (i, b) in table.iter().enumerate() {
            if let BlockKind::TableCell { row, .. } = b.kind {
                plan.insert(first + i, (starts[row as usize], lines_of[row as usize]));
            }
        }
    }
    if plan.is_empty() {
        return;
    }
    let mut out: Vec<Block> = Vec::with_capacity(blocks.len());
    // Where each block landed in `out`, so the tables keep their ranges.
    let mut out_pos: Vec<usize> = Vec::with_capacity(blocks.len() + 1);
    for (i, block) in blocks.drain(..).enumerate() {
        out_pos.push(out.len());
        let Some(&(start, k)) = plan.get(&i) else {
            out.push(block);
            continue;
        };
        let lines = if k > 1 {
            baselines(&block.spans)
        } else {
            Vec::new()
        };
        if lines.len() < 2 {
            // A row that stays one row, or an empty cell of one that splits:
            // on the first of the new rows.
            let mut block = block;
            if let BlockKind::TableCell { row, .. } = &mut block.kind {
                *row = start;
            }
            out.push(block);
            continue;
        }
        for (j, line) in lines.into_iter().enumerate() {
            let mut piece = block.clone();
            // In the order the block kept them, which is the page's: a
            // right-to-left line sorted by `x` would read backwards.
            let spans: Vec<TextSpan> = line.iter().map(|&s| block.spans[s].clone()).collect();
            let words: Vec<&str> = spans.iter().map(|s| s.text.trim()).collect();
            piece.text = words
                .join(" ")
                .split_whitespace()
                .collect::<Vec<_>>()
                .join(" ");
            piece.bbox = spans.iter().fold(
                [
                    f64::INFINITY,
                    f64::INFINITY,
                    f64::NEG_INFINITY,
                    f64::NEG_INFINITY,
                ],
                |a, s| {
                    [
                        a[0].min(s.x),
                        a[1].min(s.y),
                        a[2].max(s.x + s.width),
                        a[3].max(s.y + s.height),
                    ]
                },
            );
            piece.spans = spans;
            if let BlockKind::TableCell { row, .. } = &mut piece.kind {
                *row = start + j as u16;
            }
            out.push(piece);
        }
    }
    out_pos.push(out.len());
    // Every table's cells row-major again, the index counted again.
    let mut order: Vec<usize> = (0..out.len()).collect();
    for (first, end) in tables {
        let (first, end) = (out_pos[first], out_pos[end]);
        order[first..end].sort_by_key(|&i| match out[i].kind {
            BlockKind::TableCell { row, column, .. } => (row, column),
            _ => (u16::MAX, u16::MAX),
        });
    }
    let mut taken: Vec<Option<Block>> = out.into_iter().map(Some).collect();
    let mut sorted = Vec::with_capacity(taken.len());
    for i in order {
        if let Some(mut block) = taken[i].take() {
            block.index = sorted.len();
            sorted.push(block);
        }
    }
    *blocks = sorted;
}

/// Whether a cell holds figures and nothing else: digits with the signs,
/// separators and white space a statement sets round them.
fn is_figures(text: &str) -> bool {
    let mut digit = false;
    for c in text.chars() {
        if c.is_ascii_digit() {
            digit = true;
        } else if !(c.is_whitespace()
            || matches!(
                c,
                '$' | '(' | ')' | '%' | ',' | '.' | '-' | '\u{2014}' | '\u{2013}'
            )
            || matches!(c, '\u{20ac}' | '\u{a3}' | '\u{a5}'))
        {
            return false;
        }
    }
    digit
}

/// The spans of a cell grouped by baseline, top line first: each group the
/// indices of spans within half an em of the group's first span in `y`.
fn baselines(spans: &[TextSpan]) -> Vec<Vec<usize>> {
    let mut order: Vec<usize> = (0..spans.len())
        .filter(|&i| !spans[i].text.trim().is_empty())
        .collect();
    order.sort_by(|&a, &b| spans[b].y.total_cmp(&spans[a].y));
    let mut groups: Vec<Vec<usize>> = Vec::new();
    for i in order {
        let tolerance = (spans[i].font_size.max(spans[i].height) * 0.5).max(1.0);
        match groups
            .last()
            .filter(|g| (spans[g[0]].y - spans[i].y).abs() <= tolerance)
        {
            Some(_) => groups.last_mut().unwrap().push(i),
            None => groups.push(vec![i]),
        }
    }
    // Within a line, the block's own order of the spans.
    for group in &mut groups {
        group.sort_unstable();
    }
    groups
}

#[cfg(test)]
mod tests {
    use super::*;

    fn span(text: &str, x: f64, y: f64) -> TextSpan {
        TextSpan {
            text: text.to_string(),
            x,
            y,
            width: 6.0 * text.len() as f64,
            height: 10.0,
            font_size: 10.0,
            ..Default::default()
        }
    }

    fn cell(row: u16, column: u16, spans: Vec<TextSpan>) -> Block {
        let text: Vec<&str> = spans.iter().map(|s| s.text.as_str()).collect();
        Block {
            kind: BlockKind::TableCell {
                row,
                column,
                row_span: 1,
                column_span: 1,
                header: false,
            },
            page: 0,
            bbox: [0.0, 0.0, 1.0, 1.0],
            text: text.join(" "),
            spans,
            index: 0,
            continues_previous: false,
            confidence: None,
            grid: None,
            table_origin: Default::default(),
            trace_learned: None,
        }
    }

    fn grid(blocks: &[Block]) -> Vec<(u16, u16, String)> {
        blocks
            .iter()
            .filter_map(|b| match b.kind {
                BlockKind::TableCell { row, column, .. } => Some((row, column, b.text.clone())),
                _ => None,
            })
            .collect()
    }

    #[test]
    fn two_lines_in_every_cell_are_two_rows() {
        let mut blocks = vec![
            cell(0, 0, vec![span("Item", 10.0, 700.0)]),
            cell(0, 1, vec![span("2010", 200.0, 700.0)]),
            cell(
                1,
                0,
                vec![
                    span("Interest", 10.0, 688.0),
                    span("income", 50.0, 688.0),
                    span("Interest expense", 10.0, 676.0),
                ],
            ),
            cell(
                1,
                1,
                vec![span("2,145", 200.0, 688.0), span("526", 200.0, 676.0)],
            ),
            cell(2, 0, vec![span("Net", 10.0, 664.0)]),
            cell(2, 1, vec![span("1,618", 200.0, 664.0)]),
        ];
        split_merged_rows(&mut blocks);
        assert_eq!(
            grid(&blocks),
            vec![
                (0, 0, "Item".to_string()),
                (0, 1, "2010".to_string()),
                (1, 0, "Interest income".to_string()),
                (1, 1, "2,145".to_string()),
                (2, 0, "Interest expense".to_string()),
                (2, 1, "526".to_string()),
                (3, 0, "Net".to_string()),
                (3, 1, "1,618".to_string()),
            ]
        );
        assert!(blocks.iter().enumerate().all(|(i, b)| b.index == i));
    }

    #[test]
    fn a_wrapped_stub_over_one_line_of_figures_stays_one_row() {
        let mut blocks = vec![
            cell(
                0,
                0,
                vec![
                    span("Net earnings attributable", 10.0, 700.0),
                    span("to BorgWarner", 10.0, 688.0),
                ],
            ),
            cell(0, 1, vec![span("609.7", 200.0, 688.0)]),
            cell(1, 0, vec![span("Cash", 10.0, 676.0)]),
            cell(1, 1, vec![span("577.7", 200.0, 676.0)]),
        ];
        split_merged_rows(&mut blocks);
        assert_eq!(blocks.len(), 4);
        assert_eq!(
            grid(&blocks)[0].2,
            "Net earnings attributable to BorgWarner"
        );
    }

    #[test]
    fn a_head_row_is_not_split() {
        let mut blocks = vec![
            cell(
                0,
                0,
                vec![
                    span("Change in", 10.0, 700.0),
                    span("Interest Rates", 10.0, 688.0),
                ],
            ),
            cell(
                0,
                1,
                vec![span("At", 200.0, 700.0), span("2012", 200.0, 688.0)],
            ),
            cell(1, 0, vec![span("-200", 10.0, 676.0)]),
            cell(1, 1, vec![span("17,216", 200.0, 676.0)]),
        ];
        for b in &mut blocks[..2] {
            if let BlockKind::TableCell { header, .. } = &mut b.kind {
                *header = true;
            }
        }
        split_merged_rows(&mut blocks);
        assert_eq!(blocks.len(), 4);
    }

    #[test]
    fn a_row_without_a_figure_is_not_split() {
        let mut blocks = vec![
            cell(
                0,
                0,
                vec![
                    span("Beginning", 10.0, 700.0),
                    span("of Period", 10.0, 688.0),
                ],
            ),
            cell(
                0,
                1,
                vec![
                    span("Costs and", 200.0, 700.0),
                    span("Expenses", 200.0, 688.0),
                ],
            ),
            cell(1, 0, vec![span("Reserve", 10.0, 676.0)]),
            cell(1, 1, vec![span("17,216", 200.0, 676.0)]),
        ];
        split_merged_rows(&mut blocks);
        assert_eq!(blocks.len(), 4);
        // A date in a column name is not a cell of figures.
        let mut blocks = vec![
            cell(
                0,
                0,
                vec![span("Change in", 10.0, 700.0), span("rates", 10.0, 688.0)],
            ),
            cell(
                0,
                1,
                vec![
                    span("At December 31,", 200.0, 700.0),
                    span("2012", 200.0, 688.0),
                ],
            ),
            cell(1, 0, vec![span("-200", 10.0, 676.0)]),
            cell(1, 1, vec![span("$17,216", 200.0, 676.0)]),
        ];
        split_merged_rows(&mut blocks);
        assert_eq!(blocks.len(), 4);
        assert!(is_figures("$2,145,392 526,587"));
        assert!(is_figures("(4)% (35)"));
        assert!(!is_figures("At December 31, 2012"));
    }

    #[test]
    fn a_right_to_left_line_keeps_its_span_order() {
        // The block keeps its spans as the page draws them; a Hebrew stub
        // whose spans run right to left must come out in that order, not
        // sorted by `x`.
        let mut blocks = vec![
            cell(
                0,
                0,
                vec![
                    span("\u{5d4}\u{5db}\u{5e0}\u{5e1}\u{5d4}", 60.0, 700.0),
                    span("\u{5e0}\u{5d8}\u{5d5}", 10.0, 700.0),
                    span("\u{5d4}\u{5d5}\u{5e6}\u{5d0}\u{5d4}", 10.0, 688.0),
                ],
            ),
            cell(
                0,
                1,
                vec![span("12", 200.0, 700.0), span("13", 200.0, 688.0)],
            ),
        ];
        split_merged_rows(&mut blocks);
        let g = grid(&blocks);
        assert_eq!(g.len(), 4);
        assert_eq!(
            g[0].2,
            "\u{5d4}\u{5db}\u{5e0}\u{5e1}\u{5d4} \u{5e0}\u{5d8}\u{5d5}"
        );
        assert_eq!(blocks[0].spans[0].x, 60.0);
        assert_eq!(g[2].2, "\u{5d4}\u{5d5}\u{5e6}\u{5d0}\u{5d4}");
    }

    #[test]
    fn a_row_with_one_filled_cell_is_not_split() {
        let mut blocks = vec![
            cell(
                0,
                0,
                vec![span("Revenues", 10.0, 700.0), span("Expenses", 10.0, 688.0)],
            ),
            cell(0, 1, Vec::new()),
            cell(1, 0, vec![span("Total", 10.0, 676.0)]),
            cell(1, 1, vec![span("12", 200.0, 676.0)]),
        ];
        split_merged_rows(&mut blocks);
        assert_eq!(blocks.len(), 4);
    }
}