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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
//! Column detection and per-page reading order.
//!
//! Court-rule PDFs are mostly single-column, so a page is treated as
//! two-column only when the evidence is strong: a cluster of line-start x0
//! values near mid-page that persists across many rows (the right column's
//! starts), and a run of consecutive rows in which no line's *estimated*
//! width crosses the candidate gutter. Width estimates err low (see
//! [`rows::advance_est`]), which keeps the crossing test reliable: a genuine
//! full-width line crosses mid-page even when underestimated, while true
//! two-column lines stop well short of the gutter.
//!
//! Pages are segmented vertically: rows whose text crosses the gutter form
//! full-width segments, and contiguous stretches of gutter-respecting rows
//! form two-column segments (the CT Practice Book mixes both on one page).
//! Reading order is segments top-to-bottom; within a two-column segment, the
//! left column is read before the right.
//!
//! Everything keys on run-start x0 — never on reported end-x, which drifts
//! under the pure backend (docs/DESIGN.md Phase 1). Only one- and two-column
//! layouts are recognized in v1; that covers the corpus.

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

use super::rows::{self, Row};
use super::Line;

/// x0 values within this distance cluster together (points).
const X0_CLUSTER_TOL: f32 = 4.0;
/// A candidate gutter must lie within this band of the page width.
const SPLIT_BAND: (f32, f32) = (0.33, 0.75);
/// Minimum rows on a page before a split is even considered.
const MIN_ROWS: usize = 8;
/// The right-column start cluster must cover at least this fraction of rows.
const MIN_CLUSTER_ROW_FRACTION: f32 = 0.35;
/// Minimum consecutive gutter-respecting rows for a two-column segment.
const MIN_SEGMENT_ROWS: usize = 6;
/// Clearance (points) treated as "inside the gutter" for the crossing test.
const GUTTER_CLEARANCE: f32 = 24.0;

/// Find the candidate gutter x for a page: a persistent cluster of run-start
/// x0 values near mid-page. Pure support test — the crossing evidence is
/// evaluated per row segment afterwards.
fn detect_candidate(page_rows: &[Row], page_width: f32) -> Option<f32> {
    if page_rows.len() < MIN_ROWS {
        return None;
    }
    let mut starts: Vec<(f32, usize)> = Vec::new(); // (x0, row index)
    for (i, row) in page_rows.iter().enumerate() {
        for run in &row.runs {
            starts.push((run.bbox.0, i));
        }
    }
    starts.sort_by(|a, b| a.0.total_cmp(&b.0));
    let mut clusters: Vec<(f32, Vec<usize>)> = Vec::new(); // (center, rows)
    for (x, row) in starts {
        match clusters.last_mut() {
            Some((center, members)) if (x - *center).abs() <= X0_CLUSTER_TOL => {
                if members.last() != Some(&row) {
                    members.push(row);
                }
            }
            _ => clusters.push((x, vec![row])),
        }
    }

    let min_rows = ((page_rows.len() as f32 * MIN_CLUSTER_ROW_FRACTION) as usize).max(6);
    let mut candidates: Vec<(f32, usize)> = clusters
        .iter()
        .filter(|(center, members)| {
            *center >= SPLIT_BAND.0 * page_width
                && *center <= SPLIT_BAND.1 * page_width
                && members.len() >= min_rows
        })
        .map(|(center, members)| (*center, members.len()))
        .collect();
    if candidates.is_empty() {
        return None;
    }
    // Prefer the leftmost strong cluster (the right column's flush margin,
    // not its indented paragraph starts).
    let best_count = candidates.iter().map(|c| c.1).max().unwrap_or(0);
    candidates.retain(|c| c.1 * 5 >= best_count * 3);
    candidates.sort_by(|a, b| a.0.total_cmp(&b.0));
    Some(candidates[0].0 - X0_CLUSTER_TOL)
}

/// Does any of the row's text start left of the gutter and (by estimated
/// extent) reach into or past it? Such a row is full-width, not columnar.
fn crosses_gutter(row: &Row, split: f32) -> bool {
    row.runs.iter().any(|run| {
        let x0 = run.bbox.0;
        if x0 < split - GUTTER_CLEARANCE {
            x0 + rows::width_est(run) > split
        } else {
            x0 < split // starts inside the gutter clearance
        }
    })
}

/// A maximal stretch of rows sharing a layout: full-width or two-column.
struct Segment {
    start: usize,
    end: usize, // exclusive
    columnar: bool,
}

/// Segment a page's rows at the candidate gutter. Returns `None` when the
/// page has no two-column region worth the name (the single-column case).
fn segment(page_rows: &[Row], split: f32) -> Option<Vec<Segment>> {
    let mut classes: Vec<bool> = page_rows
        .iter()
        .map(|row| !crosses_gutter(row, split))
        .collect();
    // Smooth: one or two "crossing" rows inside a columnar stretch are
    // almost always long column lines whose width estimate overflowed, not
    // genuine full-width banners — chopping the columns there loses lines
    // from the reading flow. Flip them back to columnar.
    let mut i = 0;
    while i < classes.len() {
        if !classes[i] {
            let start = i;
            while i < classes.len() && !classes[i] {
                i += 1;
            }
            let sandwiched = start > 0 && i < classes.len();
            if sandwiched && i - start <= 2 {
                for class in &mut classes[start..i] {
                    *class = true;
                }
            }
        } else {
            i += 1;
        }
    }

    let mut segments: Vec<Segment> = Vec::new();
    for (i, &columnar) in classes.iter().enumerate() {
        match segments.last_mut() {
            Some(seg) if seg.columnar == columnar => seg.end = i + 1,
            _ => segments.push(Segment {
                start: i,
                end: i + 1,
                columnar,
            }),
        }
    }
    // Columnar stretches too short to be trusted fold into full-width flow.
    for seg in &mut segments {
        if seg.columnar && seg.end - seg.start < MIN_SEGMENT_ROWS {
            seg.columnar = false;
        }
    }
    segments.iter().any(|s| s.columnar).then_some(segments)
}

/// Turn a page's rows into [`Line`]s in reading order: segments top to
/// bottom; within a two-column segment, left column before right. Sets every
/// field except `indent` (quantized later, document-wide pass).
pub fn lines_in_reading_order(
    page_rows: Vec<Row>,
    page: &PageRuns,
    page_index: usize,
) -> Vec<Line> {
    let split = detect_candidate(&page_rows, page.width);
    let segments = split.and_then(|s| segment(&page_rows, s));

    // (line, right edge of its column) in reading order.
    let mut placed: Vec<(Line, f32)> = Vec::new();
    let page_left = page_rows
        .iter()
        .flat_map(|r| &r.runs)
        .map(|r| r.bbox.0)
        .fold(f32::INFINITY, f32::min);
    let page_right = (page.width - page_left).max(page_left + 1.0);

    match (split, segments) {
        (Some(split_x), Some(segments)) => {
            for seg in segments {
                let seg_rows = &page_rows[seg.start..seg.end];
                if seg.columnar {
                    for column in 0..2u8 {
                        for row in seg_rows {
                            let runs: Vec<TextRun> = row
                                .runs
                                .iter()
                                .filter(|r| (r.bbox.0 < split_x) == (column == 0))
                                .cloned()
                                .collect();
                            if let Some(line) = make_line(row.baseline, &runs, column, page_index) {
                                let right = if column == 0 { split_x } else { page_right };
                                placed.push((line, right));
                            }
                        }
                    }
                } else {
                    for row in seg_rows {
                        if let Some(line) = make_line(row.baseline, &row.runs, 0, page_index) {
                            placed.push((line, page_right));
                        }
                    }
                }
            }
        }
        _ => {
            for row in &page_rows {
                if let Some(line) = make_line(row.baseline, &row.runs, 0, page_index) {
                    placed.push((line, page_right));
                }
            }
        }
    }

    // Centered flags need column geometry plus x0 popularity: lines starting
    // at a popular x0 (a shared indent stop) are indented text, not centered
    // — a truly centered line's start position is a function of its own
    // width and rarely repeats.
    let x0s: Vec<f32> = placed.iter().map(|(l, _)| l.x0).collect();
    let popular = |x0: f32| {
        x0s.iter()
            .filter(|&&x| (x - x0).abs() <= X0_CLUSTER_TOL)
            .count()
            >= 3
    };
    let mut col_lefts: Vec<f32> = Vec::new();
    for (line, right) in &placed {
        let left = placed
            .iter()
            .filter(|(l, r)| l.column == line.column && r == right)
            .map(|(l, _)| l.x0)
            .fold(f32::INFINITY, f32::min);
        col_lefts.push(left);
    }
    let mut out = Vec::with_capacity(placed.len());
    for (i, (mut line, right)) in placed.into_iter().enumerate() {
        line.centered = is_centered(&line, col_lefts[i], right) && !popular(line.x0);
        out.push(line);
    }
    out
}

/// Assemble one line from a row's runs (all in one column). `None` when the
/// runs are empty or hold no visible text.
fn make_line(baseline: f32, runs: &[TextRun], column: u8, page_index: usize) -> Option<Line> {
    if runs.is_empty() {
        return None;
    }
    let text = rows::join_runs(runs);
    if text.trim().is_empty() {
        return None;
    }
    let x0 = runs[0].bbox.0;
    // Dominant font size and bold flag, weighted by character count.
    let total_chars: usize = runs.iter().map(|r| r.text.chars().count()).sum();
    let mut best = (0usize, runs[0].font_size);
    for run in runs {
        let same: usize = runs
            .iter()
            .filter(|r| (r.font_size - run.font_size).abs() <= 0.25)
            .map(|r| r.text.chars().count())
            .sum();
        if same > best.0 {
            best = (same, run.font_size);
        }
    }
    let bold_chars: usize = runs
        .iter()
        .filter(|r| r.bold)
        .map(|r| r.text.chars().count())
        .sum();
    Some(Line {
        text,
        x0,
        baseline,
        indent: 0,
        font_size: best.1,
        bold: total_chars > 0 && bold_chars * 2 > total_chars,
        centered: false,
        column,
        pages: vec![page_index],
    })
}

/// A line is centered when its estimated width falls well short of the
/// column and its midpoint sits near the column midpoint. Works without
/// backend style flags; tolerances are loose because widths are estimates.
fn is_centered(line: &Line, col_left: f32, col_right: f32) -> bool {
    let col_width = col_right - col_left;
    if col_width <= 0.0 || line.text.trim().len() < 2 {
        return false;
    }
    let width = rows::advance_est(line.text.trim_end(), line.font_size);
    if width >= 0.75 * col_width {
        return false;
    }
    if line.x0 - col_left < 0.08 * col_width {
        return false; // flush-left short lines are not centered
    }
    let line_mid = line.x0 + width / 2.0;
    let col_mid = (col_left + col_right) / 2.0;
    (line_mid - col_mid).abs() <= (0.045 * col_width).max(6.0)
}

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

    /// A synthetic two-column page shaped like the CT Practice Book body:
    /// left column at x=80, right column at x=313, page 612pt wide.
    fn two_column_page() -> crate::extract::PageRuns {
        let mut runs = Vec::new();
        for i in 0..12 {
            let y = 700.0 - i as f32 * 11.0;
            runs.push(run(
                &format!("left column line {i} of body"),
                80.0,
                y,
                10.0,
                0,
            ));
            runs.push(run(
                &format!("right column line {i} of body"),
                313.0,
                y,
                10.0,
                0,
            ));
        }
        page(runs)
    }

    fn full_text(layout: &Layout) -> String {
        layout.text()
    }

    #[test]
    fn two_column_page_reads_left_column_first() {
        let layout = reconstruct(&[two_column_page()]);
        let text = full_text(&layout);
        let left_last = text.find("left column line 11").expect("left col present");
        let right_first = text.find("right column line 0").expect("right col present");
        assert!(
            left_last < right_first,
            "left column must be read before the right column:\n{text}"
        );
    }

    #[test]
    fn full_width_lines_veto_a_false_split() {
        // Single-column page whose lines happen to contain runs starting
        // near mid-page (size-change fragments): must stay one column.
        let mut runs = Vec::new();
        for i in 0..12 {
            let y = 700.0 - i as f32 * 12.0;
            let left = run(
                "a full width single column line of text that runs on",
                72.0,
                y,
                10.0,
                0,
            );
            let right_x = 72.0 + rows::width_est(&left) + 3.0;
            runs.push(left);
            runs.push(run(
                "and keeps going to the right margin",
                right_x,
                y,
                10.0,
                0,
            ));
        }
        let layout = reconstruct(&[page(runs)]);
        assert_eq!(layout.blocks.iter().flat_map(|b| &b.lines).count(), 12);
        let first = &layout.blocks[0].lines[0];
        assert!(
            first.text.contains("that runs on and keeps going"),
            "row fragments must join into one line, got {:?}",
            first.text
        );
    }

    #[test]
    fn mixed_page_keeps_full_width_band_above_columns() {
        // A full-width paragraph on top, a two-column region below — like
        // the CT Practice Book's oath page. The band must be read first and
        // stay uninterleaved.
        let mut runs = Vec::new();
        for i in 0..7 {
            runs.push(run(
                &format!("full width oath sentence number {i} spanning the whole page width here"),
                95.0,
                700.0 - i as f32 * 11.0,
                10.0,
                0,
            ));
        }
        for i in 0..8 {
            let y = 600.0 - i as f32 * 11.0;
            runs.push(run(&format!("narrow left {i} text"), 84.0, y, 10.0, 0));
            runs.push(run(&format!("narrow right {i} text"), 317.0, y, 10.0, 0));
        }
        let layout = reconstruct(&[page(runs)]);
        let text = full_text(&layout);
        let oath_end = text.find("oath sentence number 6").expect("band present");
        let left_start = text.find("narrow left 0").expect("left col present");
        let left_end = text.find("narrow left 7").expect("left col present");
        let right_start = text.find("narrow right 0").expect("right col present");
        assert!(
            oath_end < left_start,
            "band reads before the columns:\n{text}"
        );
        assert!(left_end < right_start, "left column before right:\n{text}");
        assert!(
            !text.contains("narrow left 0 text narrow right 0"),
            "columns must not interleave:\n{text}"
        );
    }

    #[test]
    fn short_pages_are_never_split() {
        let runs = vec![
            run("left", 80.0, 700.0, 10.0, 0),
            run("right", 313.0, 700.0, 10.0, 0),
        ];
        let rows_v = rows::assemble(&page(runs), 0);
        assert_eq!(detect_candidate(&rows_v, 612.0), None);
    }

    #[test]
    fn tab_layout_near_left_margin_is_not_a_column() {
        // Guam-style TOC: "§ 100." at x=72, heading text at x=136.8 — the
        // second cluster is left of the split band, so no split.
        let mut runs = Vec::new();
        for i in 0..12 {
            let y = 700.0 - i as f32 * 12.0;
            runs.push(run(&format!("§ 10{i}."), 72.0, y, 11.0, 0));
            runs.push(run("Some Section Heading Here.", 136.8, y, 11.0, 0));
        }
        let rows_v = rows::assemble(&page(runs), 0);
        assert_eq!(detect_candidate(&rows_v, 612.0), None);
    }

    #[test]
    fn centered_heading_is_flagged() {
        let mut runs = vec![run("PART 2. OFFICE OF THE GOVERNOR", 216.6, 700.0, 10.0, 0)];
        for i in 1..5 {
            runs.push(run(
                "body text line that is long enough to reach toward the right margin",
                126.0,
                700.0 - i as f32 * 12.0,
                10.0,
                0,
            ));
        }
        let layout = reconstruct(&[page(runs)]);
        let lines: Vec<&Line> = layout.blocks.iter().flat_map(|b| &b.lines).collect();
        assert!(lines[0].centered, "heading should be centered");
        assert!(!lines[1].centered, "body must not be centered");
    }
}