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
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
//! Paragraph flow: indent quantization, block assembly, de-hyphenation, and
//! paragraph merging across page/column breaks.
//!
//! # De-hyphenation heuristic (conservative, document-driven)
//!
//! A line ending in `-` is joined with the next line's first word only when
//! both fragments are purely alphabetic. Whether the hyphen itself survives
//! is decided by this cascade, in order:
//!
//! 1. the fused word occurs elsewhere in the document → drop the hyphen
//!    ("provi-" + "sion" → "provision"),
//! 2. the hyphenated form occurs intact elsewhere → keep it
//!    ("client-" + "lawyer" → "client-lawyer"),
//! 3. the second fragment is capitalized → keep it ("Anglo-American"),
//! 4. the first fragment is a common compound prefix (self-, non-, cross-,
//!    …) → keep it,
//! 5. otherwise drop it — end-of-line hyphens are overwhelmingly soft.
//!
//! Soft hyphens (U+00AD) are always dropped. When nothing plausible can be
//! joined, the line is left exactly as extracted (no invented words).
//!
//! # Cross-break paragraph merge
//!
//! A page or column break normally starts a new block. The interrupted
//! paragraph is merged back together only when punctuation and indentation
//! both say the sentence continues: the previous line does not end with
//! terminal punctuation (or ends hyphenated), and the next line is flush
//! (indent 0), not centered, and set in the same size.

use std::collections::HashSet;

use super::Line;

/// x0 values within this distance (points) are the same indent level.
const INDENT_TOL: f32 = 3.5;
/// Vertical gap, as a multiple of the running leading, that separates blocks.
const BLOCK_GAP_FACTOR: f32 = 1.7;
/// Font-size change (points) that separates blocks.
const SIZE_BREAK: f32 = 1.5;

/// Compound prefixes whose hyphen survives joining (cascade step 4).
const COMPOUND_PREFIXES: &[&str] = &[
    "self", "non", "cross", "well", "quasi", "anti", "semi", "ex", "half", "all", "co",
];

/// Quantize line-start x0 into per-page, per-column indent levels
/// (level 0 = the leftmost x0 cluster of that page/column).
pub fn quantize_indents(lines: &mut [Line]) {
    let mut keys: Vec<(usize, u8)> = lines
        .iter()
        .map(|l| (l.pages[0], l.column))
        .collect::<HashSet<_>>()
        .into_iter()
        .collect();
    keys.sort_unstable();
    for key in keys {
        let mut xs: Vec<f32> = lines
            .iter()
            .filter(|l| (l.pages[0], l.column) == key)
            .map(|l| l.x0)
            .collect();
        xs.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
        // 1-D cluster: a new level starts when the gap exceeds the tolerance.
        let mut levels: Vec<f32> = Vec::new();
        for x in xs {
            match levels.last() {
                Some(&last) if x - last <= INDENT_TOL => {}
                _ => levels.push(x),
            }
        }
        for line in lines.iter_mut().filter(|l| (l.pages[0], l.column) == key) {
            let level = levels
                .iter()
                .rposition(|&edge| line.x0 >= edge - 0.01)
                .unwrap_or(0);
            line.indent = level.min(u8::MAX as usize) as u8;
        }
    }
}

/// Group reading-ordered lines into blocks, repairing hyphenation and
/// merging paragraphs across page/column breaks. Consumes the lines.
pub fn into_blocks(lines: Vec<Line>) -> Vec<super::Block> {
    let vocab = Vocab::build(&lines);
    let mut blocks: Vec<super::Block> = Vec::new();
    let mut leading = LeadingEstimate::default();

    for line in lines {
        let start_new = match blocks.last().and_then(|b| b.lines.last()) {
            None => true,
            Some(prev) => is_block_break(prev, &line, &mut leading),
        };
        if start_new {
            blocks.push(super::Block { lines: vec![line] });
        } else {
            let block = blocks.last_mut().expect("non-empty on merge");
            block.lines.push(line);
            let n = block.lines.len();
            dehyphenate_pair(&mut block.lines, n - 2, &vocab);
        }
    }
    blocks.retain(|b| !b.lines.is_empty());
    blocks
}

/// Running estimate of the leading (baseline-to-baseline distance) within
/// the current page/column, so block-gap detection scales with the document.
#[derive(Default)]
struct LeadingEstimate {
    key: Option<(usize, u8)>,
    value: Option<f32>,
}

impl LeadingEstimate {
    /// Feed a consecutive line pair; returns the leading to judge `gap` by.
    fn observe(&mut self, prev: &Line, cur: &Line) -> f32 {
        let key = (cur.pages[0], cur.column);
        if self.key != Some(key) {
            self.key = Some(key);
            self.value = None;
        }
        let gap = prev.baseline - cur.baseline;
        let fallback = 1.25 * cur.font_size.max(1.0);
        let current = self.value.unwrap_or(fallback);
        if gap > 0.0 && gap <= BLOCK_GAP_FACTOR * current {
            // A plausible in-paragraph gap updates the estimate (smoothed).
            let updated = if self.value.is_some() {
                0.7 * current + 0.3 * gap
            } else {
                gap
            };
            self.value = Some(updated);
        }
        self.value.unwrap_or(fallback)
    }
}

fn is_block_break(prev: &Line, cur: &Line, leading: &mut LeadingEstimate) -> bool {
    // A merged line's last page is where the flow currently stands.
    let prev_page = prev.pages.last().copied().unwrap_or(0);
    let same_flow = prev_page == cur.pages[0] && prev.column == cur.column;
    if !same_flow {
        // Merge across the break only when punctuation + indentation say the
        // paragraph continues.
        let continues = !ends_terminal(&prev.text)
            && !cur.centered
            && cur.indent == 0
            && (cur.font_size - prev.font_size).abs() <= 0.7;
        return !continues;
    }
    if (cur.font_size - prev.font_size).abs() > SIZE_BREAK {
        return true;
    }
    if cur.centered != prev.centered {
        return true;
    }
    // A trailing hyphen means the previous line stopped mid-word: the
    // strongest possible continuation signal, overriding gap and indent
    // evidence (columns sometimes carry extra vertical space mid-paragraph).
    if trailing_hyphen(&prev.text).is_some() {
        return false;
    }
    // Indent jump to the right starts a new paragraph/subdivision — unless
    // the previous line is mid-sentence (hanging-indent continuations, e.g.
    // TOC entries, indent their wrapped lines to the right).
    if cur.x0 > prev.x0 + INDENT_TOL && ends_terminal(&prev.text) {
        return true;
    }
    let expected = leading.observe(prev, cur);
    let gap = prev.baseline - cur.baseline;
    gap > BLOCK_GAP_FACTOR * expected
}

/// Terminal punctuation test for the cross-break merge: closing quotes and
/// brackets are skipped, then `. ? ! : ;` end a sentence.
fn ends_terminal(text: &str) -> bool {
    let trimmed = text.trim_end();
    let Some(last) = trimmed
        .chars()
        .rev()
        .find(|c| !matches!(c, '"' | '\'' | '\u{2019}' | '\u{201d}' | ')' | ']' | '}'))
    else {
        return true; // empty or pure closers: do not merge
    };
    matches!(last, '.' | '?' | '!' | ':' | ';')
}

/// Word sets harvested from the whole document, driving the hyphen cascade.
struct Vocab {
    words: HashSet<String>,
    hyphenated: HashSet<String>,
}

impl Vocab {
    fn build(lines: &[Line]) -> Self {
        let mut words = HashSet::new();
        let mut hyphenated = HashSet::new();
        for line in lines {
            for (i, token) in line.text.split_whitespace().enumerate() {
                let is_last = line.text.split_whitespace().count() == i + 1;
                let cleaned: String = token
                    .trim_matches(|c: char| !c.is_alphabetic() && c != '-')
                    .to_lowercase();
                if cleaned.is_empty() {
                    continue;
                }
                if let Some((a, b)) = cleaned.split_once('-') {
                    // A hyphenated compound seen intact mid-line (a trailing
                    // hyphen at line end is a break, not a compound).
                    if !is_last
                        && !a.is_empty()
                        && !b.is_empty()
                        && a.chars().all(char::is_alphabetic)
                        && b.chars().all(char::is_alphabetic)
                    {
                        hyphenated.insert(cleaned.clone());
                    }
                } else if cleaned.chars().all(char::is_alphabetic) && cleaned.len() >= 3 {
                    words.insert(cleaned);
                }
            }
        }
        Self { words, hyphenated }
    }
}

/// Hyphen characters that mark an end-of-line break.
fn trailing_hyphen(text: &str) -> Option<(usize, char)> {
    let trimmed = text.trim_end();
    let c = trimmed.chars().last()?;
    if matches!(c, '-' | '\u{2010}' | '\u{ad}') {
        Some((trimmed.len() - c.len_utf8(), c))
    } else {
        None
    }
}

/// If `lines[i]` ends hyphenated and `lines[i + 1]` starts with a plausible
/// completion, pull the completion up into `lines[i]` (dropping or keeping
/// the hyphen per the module-level cascade). Removes `lines[i + 1]` when it
/// empties, folding its page into the merged line.
fn dehyphenate_pair(lines: &mut Vec<Line>, i: usize, vocab: &Vocab) {
    let (head_line, tail_line) = (&lines[i], &lines[i + 1]);
    let Some((hyphen_at, hyphen_char)) = trailing_hyphen(&head_line.text) else {
        return;
    };
    let head: String = head_line.text[..hyphen_at]
        .chars()
        .rev()
        .take_while(|c| c.is_alphabetic())
        .collect::<Vec<_>>()
        .into_iter()
        .rev()
        .collect();
    let Some(first_token) = tail_line.text.split_whitespace().next().map(String::from) else {
        return;
    };
    let tail: String = first_token
        .chars()
        .take_while(|c| c.is_alphabetic())
        .collect();
    let rest = tail_line
        .text
        .trim_start()
        .strip_prefix(&first_token)
        .unwrap_or("")
        .trim_start()
        .to_string();
    let tail_page = tail_line.pages[0];
    let soft = hyphen_char == '\u{ad}';
    // Plausibility gate: letters on both sides, real fragments.
    if !soft && (head.chars().count() < 2 || tail.chars().count() < 2) {
        return;
    }
    if head.is_empty() || tail.is_empty() {
        return;
    }

    let fused = format!("{}{}", head.to_lowercase(), tail.to_lowercase());
    let compound = format!("{}-{}", head.to_lowercase(), tail.to_lowercase());
    let keep_hyphen = if soft || vocab.words.contains(&fused) {
        false
    } else {
        vocab.hyphenated.contains(&compound)
            || tail.chars().next().is_some_and(char::is_uppercase)
            || COMPOUND_PREFIXES.contains(&head.to_lowercase().as_str())
    };

    // Rebuild the head line: text up to the hyphen (+ hyphen if kept) + the
    // next line's whole first token (with any trailing punctuation).
    let mut new_head = lines[i].text[..hyphen_at].to_string();
    if keep_hyphen {
        new_head.push('-');
    }
    new_head.push_str(&first_token);
    lines[i].text = new_head;

    if !lines[i].pages.contains(&tail_page) {
        lines[i].pages.push(tail_page);
    }
    if rest.is_empty() {
        lines.remove(i + 1);
    } else {
        lines[i + 1].text = rest;
    }
}

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

    fn all_lines(layout: &crate::layout::Layout) -> Vec<&Line> {
        layout.blocks.iter().flat_map(|b| &b.lines).collect()
    }

    #[test]
    fn indents_quantize_per_column() {
        let runs = vec![
            run("flush line", 72.0, 700.0, 10.0, 0),
            run("flush again with wobble", 72.3, 688.0, 10.0, 0),
            run("one level in", 90.0, 676.0, 10.0, 0),
            run("two levels in", 108.0, 664.0, 10.0, 0),
        ];
        let layout = reconstruct(&[page(runs)]);
        let indents: Vec<u8> = all_lines(&layout).iter().map(|l| l.indent).collect();
        assert_eq!(indents, vec![0, 0, 1, 2]);
    }

    #[test]
    fn default_hyphen_break_is_repaired() {
        let runs = body_lines(
            &[
                "the office of the Governor, com-",
                "posed of the Governor and offices",
            ],
            72.0,
            700.0,
            12.0,
            0,
        );
        let layout = reconstruct(&[page(runs)]);
        let text = layout.text();
        assert!(
            text.contains("composed"),
            "soft line-break hyphen must be repaired: {text}"
        );
        assert!(text.contains("composed\nof the Governor"));
    }

    #[test]
    fn known_compound_keeps_its_hyphen() {
        let runs = body_lines(
            &[
                "continue the client-lawyer relationship after",
                "retention and also the client-",
                "lawyer privilege discussion here",
            ],
            72.0,
            700.0,
            12.0,
            0,
        );
        let layout = reconstruct(&[page(runs)]);
        let text = layout.text();
        assert!(
            text.contains("the client-lawyer\nprivilege"),
            "compound seen intact elsewhere keeps its hyphen: {text}"
        );
    }

    #[test]
    fn fused_word_seen_elsewhere_drops_the_hyphen() {
        let runs = body_lines(
            &[
                "the commission met yesterday and the com-",
                "mission adjourned quickly",
            ],
            72.0,
            700.0,
            12.0,
            0,
        );
        let layout = reconstruct(&[page(runs)]);
        assert!(layout.text().contains("the commission\nadjourned"));
    }

    #[test]
    fn capitalized_tail_keeps_hyphen() {
        let runs = body_lines(
            &["a treaty between the Anglo-", "American parties was signed"],
            72.0,
            700.0,
            12.0,
            0,
        );
        let layout = reconstruct(&[page(runs)]);
        assert!(layout.text().contains("Anglo-American"));
    }

    #[test]
    fn compound_prefix_keeps_hyphen() {
        let runs = body_lines(
            &["this was a non-", "party subpoena served on the firm"],
            72.0,
            700.0,
            12.0,
            0,
        );
        let layout = reconstruct(&[page(runs)]);
        assert!(layout.text().contains("non-party"));
    }

    #[test]
    fn implausible_join_is_left_alone() {
        let runs = body_lines(
            &["see sections 12-", "14 of the code for details"],
            72.0,
            700.0,
            12.0,
            0,
        );
        let layout = reconstruct(&[page(runs)]);
        assert!(
            layout.text().contains("12-\n14"),
            "numeric ranges must never be fused: {}",
            layout.text()
        );
    }

    #[test]
    fn paragraph_merges_across_pages_when_sentence_continues() {
        let p1 = page(body_lines(
            &[
                "the powers of the office extend to",
                "matters concerning the",
            ],
            72.0,
            120.0,
            12.0,
            0,
        ));
        let p2 = page(body_lines(
            &[
                "administration of justice generally.",
                "A new paragraph starts.",
            ],
            72.0,
            700.0,
            12.0,
            1,
        ));
        let layout = reconstruct(&[p1, p2]);
        assert!(
            layout.blocks[0]
                .lines
                .iter()
                .any(|l| l.text.contains("administration of justice")),
            "continuation must merge into the same block"
        );
    }

    #[test]
    fn terminal_punctuation_blocks_the_cross_page_merge() {
        let p1 = page(body_lines(
            &["the previous provision ends here."],
            72.0,
            120.0,
            12.0,
            0,
        ));
        let p2 = page(body_lines(
            &["The next provision begins now"],
            72.0,
            700.0,
            12.0,
            1,
        ));
        let layout = reconstruct(&[p1, p2]);
        assert_eq!(layout.blocks.len(), 2, "terminal stop = separate blocks");
    }

    #[test]
    fn hyphen_pull_across_pages_records_both_pages() {
        let p1 = page(body_lines(
            &["this provision was under con-"],
            72.0,
            120.0,
            12.0,
            0,
        ));
        let p2 = page(body_lines(
            &["sideration by the committee today"],
            72.0,
            700.0,
            12.0,
            1,
        ));
        let layout = reconstruct(&[p1, p2]);
        let text = layout.text();
        assert!(text.contains("consideration"), "got: {text}");
        let first = &layout.blocks[0].lines[0];
        assert_eq!(first.pages, vec![0, 1], "merged line spans both pages");
    }

    #[test]
    fn indent_jump_starts_a_new_block() {
        let runs = vec![
            run(
                "Section 101. Something is stated here",
                146.0,
                700.0,
                10.0,
                0,
            ),
            run(
                "and continues at the flush margin left.",
                134.0,
                688.0,
                10.0,
                0,
            ),
            run(
                "Section 102. A new subdivision starts",
                146.0,
                676.0,
                10.0,
                0,
            ),
        ];
        let layout = reconstruct(&[page(runs)]);
        assert_eq!(layout.blocks.len(), 2, "indent jump right = new block");
    }

    #[test]
    fn hanging_indent_continuation_stays_in_its_block() {
        // TOC style: the wrapped part of an entry is indented right, and the
        // entry is mid-sentence (even mid-word) at the wrap.
        let runs = vec![
            run(
                "Chapter 33 Hearings concerning Termina-",
                80.0,
                700.0,
                10.0,
                0,
            ),
            run("tion of Parental Rights . . . 356", 100.0, 688.0, 10.0, 0),
        ];
        let layout = reconstruct(&[page(runs)]);
        assert_eq!(layout.blocks.len(), 1, "hanging indent is a continuation");
        assert!(
            layout.text().contains("Termination"),
            "hyphen repaired across the hanging indent: {}",
            layout.text()
        );
    }

    #[test]
    fn vertical_gap_starts_a_new_block() {
        let runs = vec![
            run("first paragraph line one here", 72.0, 700.0, 10.0, 0),
            run("first paragraph line two here", 72.0, 688.0, 10.0, 0),
            run("second paragraph after a gap", 72.0, 652.0, 10.0, 0),
        ];
        let layout = reconstruct(&[page(runs)]);
        assert_eq!(layout.blocks.len(), 2);
    }

    /// Property-ish round trip: a word stream laid out with varying line
    /// widths, page breaks, and per-page furniture must come back in order
    /// with nothing lost or invented.
    #[test]
    fn word_stream_round_trips_through_layout() {
        let words: Vec<String> = (0..600).map(|i| format!("word{i}")).collect();
        let mut rng = 0x2545f4914f6cdd1du64;
        let mut next = |bound: usize| {
            rng ^= rng << 13;
            rng ^= rng >> 7;
            rng ^= rng << 17;
            (rng % bound as u64) as usize
        };
        for _trial in 0..5 {
            let mut pages_vec = Vec::new();
            let mut remaining = words.clone();
            let mut page_index = 0;
            while !remaining.is_empty() {
                let mut runs = vec![run("REPEATED HEADER", 220.0, 772.0, 9.0, page_index)];
                let mut y = 690.0; // below the top furniture band
                while !remaining.is_empty() && y > 100.0 {
                    let take = (3 + next(6)).min(remaining.len());
                    let line: Vec<String> = remaining.drain(..take).collect();
                    runs.push(run(&line.join(" "), 72.0, y, 10.0, page_index));
                    y -= 12.0;
                }
                runs.push(run(
                    &format!("{}", page_index + 1),
                    300.0,
                    40.0,
                    10.0,
                    page_index,
                ));
                pages_vec.push(page(runs));
                page_index += 1;
            }
            let layout = reconstruct(&pages_vec);
            let text = layout.text();
            let got: Vec<&str> = text.split_whitespace().collect();
            let want: Vec<&str> = words.iter().map(String::as_str).collect();
            assert_eq!(got, want, "word stream must survive the round trip");
            assert_eq!(
                layout.furniture.len(),
                2 * pages_vec.len(),
                "header + page number accounted per page"
            );
        }
    }
}