nigig-org/REVIEWS/adr/0034-pdf-text-search-and-layout.md

ADR 0034: text search and layout — a word you can see and cannot find

• Status: Accepted
• Date: 2026-08-19
• Review item: NIGIG_PDF_FEATURE_PARITY_PLAN.md §1 Phase 8, "Text search: Unicode-aware search with hit rects" and "Selection improvement: layout-aware (multi-line, multi-column) hit-testing"
• Supersedes: the per-run search in PageText::find
• Related: ADR 0031 (per-glyph pen offsets, which these rectangles use), ADR 0017 (declared versus delivered)

Context

PageText::find searched one run at a time, and its doc comment said so plainly:

A match split across two segments is not reported, which is a known limitation recorded here rather than papered over with an approximate rectangle.

Honest — and a search that does not work. A PDF writer starts a new run wherever it adjusts kerning, so a perfectly ordinary word arrives as two runs. Probing the existing code before changing it:

SPLIT MATCH 'Hello': 0 hits
  plain_text: "Hello"

The page displays Hello. Extraction returns Hello. Search returns nothing. From the user's side there is no limitation to understand: the word is right there and the find bar says it is not.

The same probe found four more:

PRECOMPOSED 'café': 0 hits          (document has cafe + U+0301)
COLUMNS plain_text: "LeftTopRightTop\nLeftBotRightBot"
OUT OF ORDER plain_text: "second\nfirst"

• Accents. A document using a combining-accent font is unsearchable with the precomposed spelling, and vice versa. The two look identical on screen.
• Columns. Reading order was content-stream order. A two-column page glued each left line to the line beside it.
• Emission order. A writer that emits runs bottom-up produced reversed text, because nothing sorted.

Decision

Search a page-level flattened string, not each run

SearchIndex builds one character vector for the page with a map back to (run, character index). A match is found in the flat string and projected back onto runs, which is what makes a cross-run match findable and highlightable: one rectangle per run it touches, never one merged box, since a merged box across a line break covers half the paragraph.

The separator between runs is a geometric question

Three cases, and the third is the one a naive implementation misses:

Runs	Join with	Because
Abutting on a line	nothing	one word split by kerning
Separated on a line	a space	two words
Different line or column	a newline	a query must not span the break

The newline matters as much as the empty join. Joining lines with a space lets "one Right" match the last word of the left column and the first of the right — text that appears nowhere and that no highlight can honestly draw. A newline is a character a find-bar query does not contain, so the match stops at the boundary.

Whether two runs are in the same column is asked of the layout analysis, not re-derived from the gap. Measuring twice means the extracted text and the searched text can disagree about where a column ends, and then a user searching for what they can see gets nothing — the original defect wearing a different hat. the_extracted_text_and_the_searched_text_agree is that invariant as a test.

NFD, never NFC

Composition is not a per-character operation: turning e + U+0301 into é requires the next character. Decomposition is — é always becomes e + U+0301 regardless of neighbours — so decomposing both document and query makes the two spellings identical with no lookahead, and the index stays a simple character-to-character map.

This was a real bug in the first draft, caught by a_decomposed_accent_matches_its_precomposed_spelling: an NFC fold applied one character at a time composes nothing and the two spellings stay different.

Case folding, not lowercasing

char::to_lowercase is not case folding. Rust lowercases ß to ß — it is already lower case — so "Strasse" never finds "Straße". Unicode case folding maps ß to ss. fold_case handles the multi-character folds a Latin document produces, including the fi/fl ligatures a PDF emits as single code points, and falls through to to_lowercase otherwise.

Because a fold can be one-to-many, the index maps each folded character back to the one source character it came from, so ß still highlights one letter rather than shifting every rectangle after it.

Columns from runs, lines within columns

Ordering matters and is the whole difficulty: two columns share their baselines — that is what makes them columns — so grouping into lines first merges a left run with the run beside it and the boundary is gone. Columns are detected first, from horizontal extents; lines are detected within each column.

Bands are separated by a gutter, not by bare non-overlap: two runs abutting on one line do not overlap either, and treating that as a column boundary splits every kerned line on the page. Two ems separates a gutter from the widest ordinary word space and scales with the type size.

Bands that a later run bridges are merged, so a full-width heading pulls the page into one column. That is correct — a page with a heading across the top is not two independent columns — and it is why the gutter threshold turns out not to be load-bearing on a realistic page, which the merge criteria below record rather than hide.

Diacritic folding is opt-in

Dropping accents by default silently widens a search the user did not ask to widen: searching a name for "Muller" and getting "Müller" is a decision. Case folding is on by default because that is what a find bar does.

Consequences

• A word visible on the page is findable, whatever the writer did to it.
• Highlights land on real glyph positions, using ADR 0031's per-glyph offsets.
• PageText::find is left alone. It is per-run by design and several tests assert the old behaviour deliberately, as the thing being improved on; deleting it would remove the evidence that the defect was real.
• is_combining_mark is a range table, not a Unicode general-category lookup. A mark outside the listed blocks is kept, so the failure mode is a search that is too strict rather than one matching the wrong word.
• Right-to-left and vertical writing are not handled. Lines are ordered by x ascending, which is wrong for Arabic and Hebrew.

Addendum: a flaky encryption test, found by running the gates

The coverage run failed in encryption_write.rs — a test with nothing to do with search. It passed five times in isolation, which is exactly the point at which "flaky, not mine" is the tempting conclusion. Running it forty times gave 2 failures, so it was reproducible and therefore real.

The cause was in xref.rs, not in the encryption code. A stream reader trims a trailing CR or LF before endstream, because that is how a writer separates the data from the keyword — and it cannot tell that separator from a data byte that happens to be CR. Binary data ends in CR about one time in 256.

When it happened, the reader returned a stream one byte short. The declared /Length was right, the file was right, and the stream was no longer a multiple of the AES block size, so decryption produced garbage and Flate then failed with "cannot make progress". Roughly one encrypted document in 250 was silently corrupt on read.

The fix is that a /Length consistent with the file is the authority: if the declared length lands on the scanned end, or on it minus a one- or two-byte separator, it is used as written. Only a length that genuinely does not fit falls back to the scan, which is the case the trim exists for.

Both stream readers had the flaw and both are fixed, with a test that reads the same file through each and asserts they agree — a file that reads correctly through one path and short through the other is worse than one that fails in both, because which answer you get is not reproducible from the file.

The general lesson, recorded because this project keeps meeting it: a lenient reader hides a broken writer, and a heuristic that repairs broken files corrupts correct ones. The trim was added to recover from a wrong /Length; it silently damaged files whose /Length was right.

Merge criteria

Enumerated from the plan bullets first, per ADR 0021.

Criterion	State
A match split across runs is found	✅ a_word_split_by_kerning_is_found_in_a_real_document
One hit rectangle per run, not a merged box	✅ asserted on a real page
Hit rectangles use real glyph offsets	✅ via ADR 0031; extents asserted
Decomposed and precomposed accents match each other	✅ both directions
Case-insensitive by default	✅ and switchable
Case folding (ß → ss, fi → fi)	✅ mutation-killed
A one-to-many fold still highlights one letter	✅
Diacritic-insensitive search, opt-in	✅ default asserted to be strict
Whole-word search	✅ mutation-killed at unit and integration level
Overlapping matches reported once	✅ mutation-killed
A query cannot span a line break	✅ mutation-killed
A query cannot span a column gutter	✅
Lines grouped by baseline, ordered left to right	✅
Columns detected before lines	✅ two columns sharing a baseline stay separate
Reading order is a permutation — no run dropped or duplicated	✅ across three fixtures
A single-column page is unchanged by the analysis	✅
Extracted text and searched text agree	✅ every extracted line is findable
Selection across lines	✅ asserted to be a contiguous slice
Hit-testing lands on the run under the point	✅ every run of a real page
A click in the gutter hits nothing	✅
Gutter threshold is load-bearing on a real page	⚠️ no — band merging makes a longer line bridge the gap anyway. Killed by the unit test, survives the integration test, and both are kept with the reason written in the test
Right-to-left and vertical writing	❌ not handled — lines are ordered by x ascending
Unicode general-category table for combining marks	❌ deferred — range table; errs toward too strict
Mutation-checked	✅ 7 mutations, all killed by the unit suite; 6 of 7 also by the integration suite, and the seventh is explained above

Incidental fix, verified separately:

Criterion	State
A stream whose data ends in CR, LF or CRLF is not trimmed	✅ three tests; was corrupting ~1 encrypted document in 250
A /Length short by one or two bytes is trusted over the scan	✅ the case the two rules differ on
A badly short /Length still loses to endstream	✅ the case the trim exists for, unchanged
A /Length past the end of the file falls back to the scan	✅
Both stream readers agree	✅ same file through each
Mutation-checked	✅ 3 mutations, all killed