# ADR 0013: xref streams and object streams — read PDF 1.5+ at all

- **Status:** Accepted
- **Date:** 2026-08-02
- **Review item:** `NIGIG_PDF_FEATURE_PARITY_PLAN.md` §1 Phase 2,
  "Read-side xref modernisation … nigig `parser.rs` is only 67 LOC; this is
  the biggest parse-side gap"
- **Supersedes:** nothing
- **Related:** ADR 0003 (incremental save appends a *traditional* xref; that
  stays true and is now explicitly reconciled with hybrid files)

## Context

The parser cannot open a PDF 1.5 file. Not "renders it wrong" — cannot open
it. Probing a minimal document that uses an xref stream and an object
stream, which is the layout essentially every producer has emitted since
2005:

```
PARSE FAILED: PDF error at byte 382: expected xref keyword
```

`XRefTable::parse_section` requires the literal bytes `xref` at the
`startxref` offset. A PDF 1.5+ file has an **indirect object** there —
`5 0 obj << /Type /XRef … >> stream` — so the parse aborts immediately and
the whole document is unreadable.

Grepping the crate confirms the scale: `ObjStm`, `XRefStm`, `/Type /XRef`
and `object_stream` appear **nowhere** in any `.rs` file.

This is the correct next target because it is the only Phase 2 item that
makes whole real-world files unreadable. The remaining Phase 2 entries are
narrower than the plan implies — inline images, `Do`, shading and the full
text state (`Tc/Tw/TL/Tz/Ts/Td/TD/Tm/Tf`) are already implemented and
tested; Type 3 fonts and the streaming interpreter are genuine gaps but
degrade one feature each rather than the whole file.

## Decision

Implement the three modern cross-reference mechanisms of PDF 32000-1 §7.5.8
on the read side, in `pdf-cos`.

### Xref streams (`/Type /XRef`)

A stream whose decoded body is a packed binary table described by `/W`,
optionally sparse via `/Index`. Fields:

- **type 0** — free object.
- **type 1** — uncompressed: field 2 is a byte offset.
- **type 2** — compressed: field 2 is the *object stream number*, field 3
  the index within it.

`/W` entries may be zero-width, which means "use the default": type
defaults to 1, the others to 0. That rule is easy to miss and produces a
table of all-free entries if ignored, so it is implemented explicitly.

### Object streams (`/Type /ObjStm`)

A stream containing `N` objects concatenated after a header of `N` pairs
`objnum offset`, with `/First` giving the byte offset of the payload.
Objects inside carry no `obj`/`endobj` keywords.

Two constraints from the spec are enforced rather than assumed:

- An object stream **cannot contain another object stream**, and cannot
  contain the document's `/Encrypt` dictionary. A file claiming otherwise
  is malformed and is refused for that object rather than recursed into.
- Objects in an object stream always have **generation 0**.

### Hybrid-reference files (`/XRefStm`)

A traditional xref table whose trailer carries `/XRefStm` pointing at an
xref *stream* holding the entries a 1.4 reader cannot see. Both are read,
with the **traditional table taking precedence** for any object number in
both — that is what the hybrid layout is for: the old table is the
authoritative view for old readers, and the stream only *adds*.

### Decryption ordering

An xref stream is parsed **before** the decryptor exists, and per
PDF 32000-1 §7.5.8.2 it is never encrypted. Object streams *are*
encrypted, and must be decrypted as a whole stream before their contained
objects are extracted — the objects inside must not be decrypted again
individually, which would corrupt them. This ADR keeps object-stream
extraction on the plaintext bytes the existing decrypt-on-read path already
produces.

### Interaction with incremental save (ADR 0003)

ADR 0003 appends a traditional xref table. That remains correct: appending
a traditional section to a file whose previous revision used an xref stream
produces a hybrid-shaped chain that both this reader and any conforming
reader can follow, because our appended trailer carries `/Prev` pointing at
the stream. **Writing xref streams is out of scope**; nothing in this ADR
changes the writer.

## Non-negotiable rules

1. **A malformed xref stream must not be silently treated as an empty
   table.** An empty table looks like a valid document with no objects,
   which is the silent-degradation failure this codebase keeps removing.
2. **Recursion is bounded.** An object stream referencing itself, or a
   `/Prev` chain through xref streams, must terminate.
3. **`/W` widths are attacker-controlled**; every field read is bounds
   checked against the decoded buffer.
4. **The traditional table wins in a hybrid file**, per spec, and never the
   other way round.
5. **No writer change.** ADR 0003's append stays byte-for-byte as it is.

## Merge criteria

- [x] A PDF 1.5 file with an xref stream parses, and its pages are
      readable.
- [x] Objects stored in an object stream resolve.
- [x] `/W` with a zero-width first column defaults the type to 1.
- [x] `/Index` sparse subsections are honoured.
- [x] A hybrid file (`/XRefStm`) reads, with the traditional table winning
      on conflict.
- [x] `/Prev` chains that mix traditional and stream sections resolve.
- [x] A truncated, cyclic or over-wide xref stream is a typed error, never
      a silent empty table and never a hang.
- [x] An object stream that claims to contain an object stream is refused.
- [x] Corpus fixtures for each of the above, generated by the checked-in
      script.
- [x] Existing traditional-xref documents still parse unchanged.
- [x] `TEST_TARGET=pdf ./tools/test-rust-clean.sh` passes, rustfmt and
      clippy `-D warnings` clean.

All criteria met. `TEST_TARGET=pdf` went from 606 to 615 and
`TEST_TARGET=pdf-ui` from 651 to 660.

Mutation-checked: reverting the one-line dispatch in `parse_section` back to
`Err("expected xref keyword")` fails 5 of the 9 acceptance tests.

One fixture was wrong on the first attempt and is worth recording, because
the failure looked like a parser bug: `stream_default_width.pdf` originally
stored its catalog and page tree as **compressed** objects while declaring
`/W [0 4 2]`. With a zero-width type column every entry defaults to type 1,
so a compressed object cannot be expressed at all — the fixture was
unrepresentable, not the parser broken. It now stores those objects
uncompressed, which is what a real `/W [0 4 2]` file does.

`/Extends` on an object stream is parsed but deliberately not followed: every
object we need is listed in the stream's own header, so following the parent
chain would add recursion for no gain.

## Consequences

**Positive.** The parser can open files produced in the last twenty years.
Every downstream feature already built — encryption, signatures, forms,
structure tree — becomes reachable on modern documents, where before it was
all unreachable behind a failed parse.

**Negative.** `xref.rs` grows and gains a dependency on `filter.rs` for
Flate decoding at xref-parse time, which is earlier than decoding happened
before.

**Risk.** A subtly wrong `/W` decode yields plausible-looking offsets that
resolve to the wrong objects — worse than failing. Mitigated by fixtures
whose objects have asserted *content*, not merely a successful parse.

**Out of scope, deliberately:** writing xref streams or object streams,
cross-reference stream compression choices, and linearised-file
(`/Linearized`) fast-path reading.