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 |