Appendix C - 1. Canonical walkers (one traversal per tree)

The Structure of Canonical walkers (one traversal per tree) — its shape at a glance:

Every call site that needs to walk the tree reaches it through the one canonical walker. The walker owns the traversal invariants; a lint bans the direct edge — hand-rolled recursion or a regex reaching into the tree fails the build.

flowchart LR
  C1[Visitor A] --> W
  C2[Visitor B] --> W
  C3[Visitor C] --> W
  W["Canonical walker<br/>(owns invariants)"] --> T[(Tree model)]
  C1 -. banned raw recursion .-> T
  L{{Ban-lint}} -. fails build .-> C1

Accessible description: three visitors all reach the tree through one canonical walker that owns the traversal invariants. A dashed edge marks a visitor recursing into the tree directly; the ban-lint fails the build on that edge, so every surviving path to the tree runs through the walker.

Projected from the catalogue entry canonical-models-and-seams / Canonical walkers (one traversal per tree).

On this page: Intent · Motivation · Applicability · Structure · Sample Code · Consequences · Example use within DocAble · Related Patterns

Intent

Intent — Give each tree exactly one canonical walker that owns its traversal invariants, and route all traversal through it instead of ad hoc recursion, so those invariants live in one place (our instances: one walker for the PDF structure tree, one for the checking pass, one per Office part: PdfStructTreeWalker, the RuleWalkers, DocxTopLevelPartWalker).

Motivation

Ad hoc tree recursion re-implements traversal at every site, and each copy is subtly wrong in its own way. One misses a node type, another visits in the wrong order, a third forgets link annotations. The same traversal bug recurs per site, and because each is hand-rolled, a fix to one never reaches the others.

Applicability

A walker per tree type, exposing the traversal shape callers actually need.
A discipline (and lint coverage) that routes traversal through it, closing the raw-recursion and regex-into-tree escapes.

Structure

The Structure diagram appears at the top of this page.

Sample Code

A canonical walker holds the traversal invariants once — visit order, node-type coverage, reference resolution — and hands each node to a visitor callback. Callers supply a visitor; they never write the recursion. The value is that the "forgot to resolve the reference" bug now lives in exactly one place, so fixing it once fixes every caller.

from typing import Callable, Iterator

class TreeWalker:
    """The one sanctioned traversal over the tree. It owns the invariants every
    ad hoc recursion kept getting wrong: visit every node type, in document order,
    following indirect references to their target."""

    def __init__(self, resolve: Callable[[object], object]):
        self._resolve = resolve  # turns an indirect ref into the node it points at

    def walk(self, root) -> Iterator[object]:
        stack = [root]
        while stack:
            node = self._resolve(stack.pop())   # invariant: always resolve first
            yield node
            # invariant: children in document order, so pushed reversed
            stack.extend(reversed(getattr(node, "children", [])))


def collect_alt_text(root, walker: TreeWalker) -> list[str]:
    # a visitor: it never recurses itself — it just consumes the canonical order
    return [n.alt for n in walker.walk(root) if getattr(n, "alt", None)]

Consequences

The walker must expose what callers need. A missing traversal shape pushes a caller back to raw recursion; coverage matters here, same as the models.
Low novelty. This is a well-understood pattern; its value is DRY + invariant-centralization, not invention.

Example use within DocAble

PdfStructTreeWalker, the RuleWalkers, DocxTopLevelPartWalker, and the other per-tree walkers.
The canonical-walker discipline (traversal routed through the walker, raw recursion banned).

See also — pdf-model, office-models: walkers are how you traverse those typed models; they are part of the same typed-seam discipline.
Enabler — a canonical walker makes routing traversal through the typed models practical; without it, callers reach for raw recursion and re-open the ban-lint's door.