# ADR 0011: PDF/UA structure tree — tagged content, reading order, accessibility

- **Status:** Accepted
- **Date:** 2026-08-01
- **Review item:** Phase 8, `DART_PDF_VS_MAKEPAD_PDF_GAP_ANALYSIS.md`
  ("PDF/UA structure tree", 3–4 weeks, "Tagged PDF model, accessibility
  tree")
- **Supersedes:** nothing
- **Related:** ADR 0009 (transparency — its operator-shadowing guard is what
  should have caught the `BMC` bug below, and now does)

## Context

Nothing in this codebase reads a structure tree. `/StructTreeRoot`,
`/StructElem`, `/MarkInfo`, `/Alt`, `/ActualText` and `/Lang` appear
nowhere. A tagged PDF — one that has gone to the trouble of describing its
own reading order and semantics — is treated exactly like an untagged scan.

That is the accessibility gap the review names. But investigating it
surfaced three defects in the marked-content operators that the structure
tree depends on, and one of them is not an accessibility problem at all.

### 1. `BMC` does not parse, and corrupts the colour of everything after it

The dispatcher matches `b'B'` + `b'M'` only when the third byte is a
delimiter. For `BMC` the third byte is `C`, so the arm never fires and the
operator is never recognised. Because it is never recognised, its `/Tag`
operand is **never cleared from the operand stack**, and it shifts the
operands of whatever comes next:

```
1 0 0 rg            -> RgbFill(1.0, 0.0, 0.0)   red, correct
/Span BMC 1 0 0 rg  -> RgbFill(0.0, 1.0, 0.0)   green
```

A page containing a single `BMC` renders **red as green**, and every
subsequent operator with operands is shifted too. Tagged documents are
exactly the ones that contain `BMC`, so the documents that tried hardest to
be accessible are the ones that render with wrong colours.

This is the fifth instance of the operator-shadowing family already fixed
for `cm`, `rg`, `gs`, `b`/`b*` and the end-of-stream `T*` case. ADR 0009's
`every_multi_char_operator_parses_as_itself` test was written precisely to
prevent a fifth — and it would have caught this, except `BMC` was one of the
two operators deliberately excluded from its table as "genuinely
unimplemented". Excluding a known-broken operator from the test that exists
to find broken operators is how it survived. That exclusion is removed here.

### 2. `BDC` discards `/MCID`, which is the entire link to the structure tree

```
/P <</MCID 0>> BDC  ->  MarkContentBmc("P")
```

The properties dictionary is dropped. `/MCID` is the marked-content
identifier: it is the *only* thing connecting a run of page content to the
structure element that describes it. Without it a structure tree can be
parsed but never attached to anything, which would make the whole feature
decorative.

### 3. The op is named `MarkContentBmc` but is produced by `BDC`

`BDC` produces `PdfOp::MarkContentBmc`, and `BMC` produces nothing. The
names are the wrong way round, which is how the missing `BMC` arm stayed
invisible during review: the enum looked like it had a `BMC` case.

## Decision

Fix the marked-content operators, then build the structure tree on top.

### Operators

- `BMC` gets an arm, clears its operand, and produces `BeginMarkedContent`.
- `BDC` produces `BeginMarkedContentProps { tag, properties }`, retaining
  the properties dictionary, which may be inline or a `/Properties` resource
  name.
- The misnamed `MarkContentBmc` / `MarkContentEmc` variants are removed
  rather than left as confusing aliases.
- `BMC` and `BDC` are added to ADR 0009's operator table, and the two
  "genuinely unimplemented" exclusions are removed, because an exclusion
  list on that test is a place for bugs to hide.

### Structure tree, in `pdf-document`

- Parse `/StructTreeRoot`: `/K`, `/IDTree`, `/ParentTree`, `/RoleMap`,
  `/ClassMap`.
- Parse `/StructElem` nodes recursively into a real tree, carrying `/S`
  (type), `/P` (parent), `/Pg` (page), `/K` (kids), `/Alt`, `/ActualText`,
  `/E` (expansion), `/Lang`, `/T` (title), `/A`/`/C` attributes.
- Resolve `/RoleMap` so a custom tag maps to its standard equivalent, and
  classify standard types into a `StructRole` enum (document, part,
  headings H1–H6, paragraph, list, table, figure, link, and so on).
- Extract the **reading order**: the depth-first order of the tree is the
  logical reading order, which is what a screen reader follows and is
  frequently different from the geometric order text appears in.
- Map `/MCID` to structure elements per page, so a content run can be
  asked "what am I part of".

### Accessibility checks, reported not enforced

A small set of checks that are *mechanically decidable* from the tree:

- Is the document tagged at all (`/MarkInfo /Marked true`)?
- Does it declare a `/Lang`?
- Do figures have `/Alt` text?
- Is the heading hierarchy well-formed (no level skipped, e.g. H1 → H3)?
- Do table cells sit inside rows inside a table?
- Are there structure elements pointing at pages that do not exist?

These are reported as typed findings. They are **not** a PDF/UA conformance
claim: real conformance has dozens of requirements, many needing human
judgement (is this `/Alt` text *accurate*?), and asserting conformance from
six mechanical checks would be exactly the kind of overclaim this codebase
keeps removing. The type is named `AccessibilityFindings`, not
`ComplianceReport`, and there is no boolean called `is_pdf_ua`.

### Not implemented, and not faked

- **Writing or repairing tags.** Generating a structure tree for an untagged
  document is a heuristic content-analysis problem, not a parsing one.
- **PDF/UA conformance certification**, per above.
- Reading order *inference* for untagged documents. If a document has no
  structure tree, the honest answer is "untagged", not a guess.

## Non-negotiable rules

1. **No operator may be silently unrecognised.** An unmatched operator that
   leaves operands on the stack corrupts every operator after it; that is
   how `BMC` turned red into green.
2. **The operator table test has no exclusion list.** An operator that does
   not parse gets fixed or gets an explicitly failing test, not an omission.
3. **A cyclic or deep `/K` graph must not recurse without bound.** Structure
   trees are attacker-controlled and `/P`/`/K` can point at each other.
4. **No PDF/UA conformance claim** from mechanical checks alone.
5. **An untagged document reports as untagged**, never as an empty tree that
   looks like a tagged document with no content.

## Merge criteria

- [x] `BMC` parses, clears its operand, and no longer shifts the operands of
      following operators.
- [x] A regression test proves `/Span BMC 1 0 0 rg` still fills red.
- [x] `BDC` retains its `/MCID` and properties dictionary.
- [x] `BMC` and `BDC` are in ADR 0009's operator table and its exclusion
      list is gone.
- [x] `/StructTreeRoot` parses into a tree with parent/child links.
- [x] `/RoleMap` maps a custom tag to its standard role.
- [x] Reading order is extracted depth-first and differs from geometric
      order in a fixture where it should.
- [x] `/Alt`, `/ActualText`, `/E` and `/Lang` are exposed.
- [x] `/MCID` resolves to its structure element.
- [x] A cyclic `/K` graph terminates with a typed error rather than a stack
      overflow.
- [x] Accessibility findings: missing `/Alt`, skipped heading level, absent
      `/Lang`, untagged document.
- [x] No API reports PDF/UA conformance, and a test asserts that absence.
- [x] Corpus fixtures for a tagged document, a role-mapped document, a
      cyclic tree, an untagged document and an inaccessible one, generated
      by the checked-in script.
- [x] `TEST_TARGET=pdf ./tools/test-rust-clean.sh` passes, rustfmt and
      clippy `-D warnings` clean.

All criteria met. `TEST_TARGET=pdf` went from 536 to 575 and
`TEST_TARGET=pdf-ui` from 580 to 619.

### A fourth bug, found while fixing the third

`BDC`'s property list could not be read even once `BDC` retained it,
because the content-stream lexer had **no dictionary support at all**: it
treated `<` as the start of a hex string without checking for a second
`<`. `<</MCID 0>>` therefore parsed as the hex string `"0C0D0"`, so every
property list in every document was unreadable. Content streams now parse
dictionaries, arrays, strings, names, numbers and booleans as direct
objects, bounded at 16 levels of nesting because the bytes are
attacker-controlled. A single `<` is still a hex string, and a test pins
that.

### Cycle handling was tightened after first implementation

The first version relied on the depth bound alone, which terminated
safely but expanded a two-element cycle into 65 nonsense elements before
stopping. It now tracks the ancestor path and cuts at the first repeat,
reporting the object number through `AccessibilityIssue::CyclicStructure`
rather than pruning silently.

The `nothing_claims_pdf_ua_conformance` tripwire was mutation-checked:
adding an `is_pdf_ua` method to `AccessibilityFindings` fails it. It
skips comment lines, so the module documentation can go on explaining why
no such verdict exists without tripping the test that enforces it.

## Consequences

**Positive.** The `BMC` fix repairs colour on every tagged document, which
is a rendering correctness win far outside accessibility. Screen-reader
reading order, alternative text and language become available to a host. The
`/MCID` map is the prerequisite for accessible text extraction and for
content redaction that respects structure.

**Negative.** `PdfOp` gains a variant and loses two misnamed ones, so
`RecordingDevice` and the Makepad device must handle it. That is the
correct cost of the enum having been wrong.

**Risk.** Treating the mechanical checks as a conformance verdict.
Mitigated by rule 4, by the naming, and by a test asserting no conformance
API exists.

**Out of scope, deliberately:** tag generation and repair, PDF/UA
certification, `/AF` associated files, MathML, and structure-aware
redaction.