andodeki
a994213e8b
Phase 8 #7 of REVIEWS/DART_PDF_VS_MAKEPAD_PDF_GAP_ANALYSIS.md ("PDF/UA structure tree"). Design and merge criteria in REVIEWS/adr/0011-pdf-structure-tree.md. Investigating the accessibility gap surfaced four defects in the marked-content operators the structure tree depends on. The first is not an accessibility problem at all. 1. BMC never parsed, and corrupted the colour of everything after it. The dispatcher matched b'B'+b'M' only when the third byte was a delimiter; BMC's third byte is 'C', so the arm never fired. Because the operator was never recognised it never CLEARED ITS OPERAND, and the leftover /Tag shifted the operands of whatever came next: 1 0 0 rg -> RgbFill(1.0, 0.0, 0.0) red /Span BMC 1 0 0 rg -> RgbFill(0.0, 1.0, 0.0) green Tagged documents are precisely the ones containing BMC, so the documents that tried hardest to be accessible rendered wrong colours. This is the fifth instance of the operator-shadowing family already fixed for cm, rg, gs, b/b* and end-of-stream text operators. ADR 0009's every_multi_char_operator_parses_as_itself test exists to stop exactly this - and would have caught it, except BMC was one of two operators excluded from its table as "genuinely unimplemented". Excluding a known-broken operator from the test whose job is finding broken operators is how it survived. The exclusion list is gone. 2. BDC discarded its property list, which carries /MCID - the only link between a run of page content and the structure element describing it. Without it a tree can be parsed but never attached to anything. 3. The op produced by BDC was named MarkContentBmc, and BMC produced nothing. The names were the wrong way round, which is how the missing arm survived review: the enum looked like it had a BMC case. 4. Found while fixing 2: the content lexer had no dictionary support at all. It read `<` as a hex string without checking for a second `<`, so `<</MCID 0>>` parsed as the string "0C0D0". Content streams now parse direct objects properly, bounded at 16 levels; a single `<` is still a hex string and a test pins that. On top of that, new pdf-document/src/structure.rs: /StructTreeRoot, /StructElem trees, /RoleMap resolution, depth-first reading order, /Alt, /ActualText, /E, /Lang, and MCID-to-element lookup. Cycles in /K are cut at the first repeat and reported by object number rather than expanded to the depth bound. Accessibility findings are mechanical checks reported as findings, NOT a conformance verdict: there is no is_pdf_ua and no ComplianceReport, and a mutation-checked tripwire test fails if either appears. Real PDF/UA conformance needs human judgement - whether /Alt text is accurate is not mechanically decidable - so claiming it from six checks would be exactly the overclaim this codebase keeps removing. 7 corpus fixtures, 14 acceptance tests, 22 unit tests, and a parse_content_dict fuzz target for the new object parser. TEST_TARGET=pdf 536 -> 575, TEST_TARGET=pdf-ui 580 -> 619. rustfmt and clippy -D warnings clean.
209 lines
9.7 KiB
Markdown
209 lines
9.7 KiB
Markdown
# 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.
|