nigig-org/REVIEWS/adr/0011-pdf-structure-tree.md

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

• BMC parses, clears its operand, and no longer shifts the operands of following operators.
• A regression test proves /Span BMC 1 0 0 rg still fills red.
• BDC retains its /MCID and properties dictionary.
• BMC and BDC are in ADR 0009's operator table and its exclusion list is gone.
• /StructTreeRoot parses into a tree with parent/child links.
• /RoleMap maps a custom tag to its standard role.
• Reading order is extracted depth-first and differs from geometric order in a fixture where it should.
• /Alt, /ActualText, /E and /Lang are exposed.
• /MCID resolves to its structure element.
• A cyclic /K graph terminates with a typed error rather than a stack overflow.
• Accessibility findings: missing /Alt, skipped heading level, absent /Lang, untagged document.
• No API reports PDF/UA conformance, and a test asserts that absence.
• 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.
• 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.