pdf-untangle 0.3.0

Untangle garbled PDF text: layout-aware extraction that reconstructs reading order, strips page furniture, and splits documents into structured, citable sections
Documentation
//! Baseline-row assembly and width estimation.
//!
//! Runs are clustered onto shared baselines with a tolerance scaled by font
//! size, so small-caps fragments and superscripts join the line they visually
//! belong to. Everything horizontal is keyed on run **start** x0; the end-x a
//! backend reports is only trusted when it is plausible for the run's
//! character count (the pure backend substitutes 1000/em default widths when
//! a font's width table is missing, which drifts x1 badly in either
//! direction — see docs/DESIGN.md Phase 1).

use crate::extract::{PageRuns, TextRun};

/// Baseline tolerance, as a fraction of the larger font size involved.
const BASELINE_TOL_EMS: f32 = 0.45;
/// Inter-run gap (in ems) that reads as a word space. Run boundaries occur
/// at font/size changes where widths are estimates, so this is looser than
/// the backends' own intra-run word-gap thresholds.
const WORD_GAP_EMS: f32 = 0.25;

/// One physical row on a page: runs sharing a baseline, sorted by x0.
pub struct Row {
    /// Representative baseline (y of the first run clustered into the row).
    pub baseline: f32,
    pub runs: Vec<TextRun>,
}

/// Cluster a page's runs into baseline rows, top to bottom.
///
/// Runs are assigned to the nearest existing row within tolerance in the
/// order the PDF emitted them; within a row, emission order is preserved
/// when it is already left-to-right (some faces start a lowercase small-caps
/// run fractionally left of the capital it follows — re-sorting those swaps
/// the letters). A genuinely out-of-order row is sorted by x0.
pub fn assemble(page: &PageRuns, page_index: usize) -> Vec<Row> {
    let mut rows: Vec<Row> = Vec::new();
    for run in page
        .runs
        .iter()
        .filter(|r| r.page == page_index && !r.text.trim().is_empty())
    {
        let y = run.bbox.1;
        let mut best: Option<(usize, f32)> = None;
        for (i, row) in rows.iter().enumerate() {
            let d = (row.baseline - y).abs();
            if d <= baseline_tol(row, run) && best.map_or(true, |(_, bd)| d < bd) {
                best = Some((i, d));
            }
        }
        match best {
            Some((i, _)) => rows[i].runs.push(run.clone()),
            None => rows.push(Row {
                baseline: y,
                runs: vec![run.clone()],
            }),
        }
    }
    rows.sort_by(|a, b| b.baseline.total_cmp(&a.baseline));
    for row in &mut rows {
        let monotonic = row
            .runs
            .windows(2)
            .all(|w| w[1].bbox.0 >= w[0].bbox.0 - 1.0);
        if !monotonic {
            row.runs.sort_by(|a, b| a.bbox.0.total_cmp(&b.bbox.0));
        }
    }
    rows
}

fn baseline_tol(row: &Row, run: &TextRun) -> f32 {
    let row_size = row.runs.iter().map(|r| r.font_size).fold(0.0f32, f32::max);
    BASELINE_TOL_EMS * row_size.max(run.font_size)
}

/// Estimate a run's advance width from per-character width classes.
///
/// Deliberately errs slightly low: the estimate is used (a) to decide whether
/// a reported x1 is plausible, (b) as a veto against false column splits
/// (a full-width line must still cross the candidate gutter after
/// underestimation), and (c) for centered-line detection.
pub fn advance_est(text: &str, em: f32) -> f32 {
    text.chars().map(char_width_ems).sum::<f32>() * em
}

fn char_width_ems(c: char) -> f32 {
    match c {
        ' ' | '\u{a0}' => 0.24,
        'i' | 'j' | 'l' | 't' | 'f' | 'r' | '.' | ',' | ';' | ':' | '\'' | '\u{2018}'
        | '\u{2019}' | '!' | '(' | ')' | '[' | ']' | '|' | '-' => 0.30,
        'm' | 'w' => 0.72,
        'M' | 'W' => 0.85,
        '\u{2014}' => 0.90,
        c if c.is_ascii_uppercase() => 0.62,
        c if c.is_ascii_digit() => 0.50,
        _ => 0.46,
    }
}

/// A run's effective width: the reported extent when plausible for the
/// character count, otherwise the character-class estimate.
pub fn width_est(run: &TextRun) -> f32 {
    let reported = run.bbox.2 - run.bbox.0;
    let estimated = advance_est(run.text.trim_end(), run.font_size);
    if reported >= 0.5 * estimated && reported <= 1.6 * estimated {
        reported
    } else {
        estimated
    }
}

/// Join a row's (already x-sorted) runs into a single text, inserting a space
/// wherever the estimated gap between runs reads as a word break.
pub fn join_runs(runs: &[TextRun]) -> String {
    let mut text = String::new();
    let mut prev_end: Option<(f32, f32)> = None; // (x, em)
    for run in runs {
        if let Some((end_x, em)) = prev_end {
            let gap = run.bbox.0 - end_x;
            let em = em.min(run.font_size);
            // Sentence punctuation is always followed by a space in running
            // text, so a run boundary after it needs only a modest gap (the
            // width estimate can eat most of a real space).
            let threshold = if text.trim_end().ends_with([':', ';']) {
                0.12 * em
            } else {
                WORD_GAP_EMS * em
            };
            if gap > threshold && !text.ends_with(' ') && !run.text.starts_with(' ') {
                text.push(' ');
            }
        }
        // Control characters are extraction noise (broken ToUnicode maps
        // occasionally yield NULs), never layout.
        text.extend(run.text.chars().filter(|c| !c.is_control() || *c == '\t'));
        prev_end = Some((run.bbox.0 + width_est(run), run.font_size));
    }
    text
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::layout::testutil::{page, run};

    #[test]
    fn rows_cluster_by_baseline_scaled_tolerance() {
        let p = page(vec![
            run("alpha", 72.0, 700.0, 10.0, 0),
            run("beta", 150.0, 701.5, 10.0, 0), // same line, slight wobble
            run("gamma", 72.0, 688.0, 10.0, 0), // next line, 12pt leading
        ]);
        let rows = assemble(&p, 0);
        assert_eq!(rows.len(), 2);
        assert_eq!(rows[0].runs.len(), 2);
        assert_eq!(rows[1].runs[0].text, "gamma");
    }

    #[test]
    fn superscript_joins_its_line() {
        let p = page(vec![
            run("see note", 72.0, 500.0, 10.0, 0),
            run("1", 120.0, 503.5, 6.0, 0), // raised superscript
        ]);
        let rows = assemble(&p, 0);
        assert_eq!(rows.len(), 1);
    }

    #[test]
    fn join_inserts_spaces_only_at_real_gaps() {
        // "Wo" + "rd" abut; "next" starts a word-space away.
        let a = run("Wo", 100.0, 700.0, 10.0, 0);
        let b = run("rd", 100.0 + width_est(&a), 700.0, 10.0, 0);
        let c = run("next", b.bbox.0 + width_est(&b) + 3.0, 700.0, 10.0, 0);
        assert_eq!(join_runs(&[a, b, c]), "Word next");
    }

    #[test]
    fn implausible_reported_extent_falls_back_to_estimate() {
        // Mimic the pure backend's x1 drift: a 24-char run whose reported
        // width is 3x plausible (missing width table, 1000/em defaults).
        let mut r = run("twenty four characters!!", 72.0, 700.0, 10.0, 0);
        r.bbox.2 = r.bbox.0 + 400.0;
        let w = width_est(&r);
        assert!(w < 150.0, "drifted x1 must not be trusted, got {w}");
        // And the under-drift direction (x1 barely advances).
        r.bbox.2 = r.bbox.0 + 10.0;
        let w = width_est(&r);
        assert!(w > 60.0, "collapsed x1 must not be trusted, got {w}");
    }
}