Module matcher 

The matching engine (#46): anchor-based structural matching of Patterns against parsed docstrings.

A pattern matches by structural unification of a reading’s fragment tree (in pattern coordinates) against candidate subtrees of the target (in target coordinates). Pattern::matches searches the whole document; Pattern::matches_in scopes the search to an anchor node and derives the grammar binding from it (the maintainer’s parent-node design from the #46 discussion). Rewriting is #47.

Style strictness

Matching is style-strict: a pattern only matches targets of the exact Style it was parsed with (Pattern::style==Parsed::style); on a mismatch both entry points return no matches. Cross-style “smart” matching (a Google-spelled pattern matching a NumPy document via the unified kinds) is explicitly deferred, per the #46 design notes.

Unification rules

Fragment and candidate trees unify element-by-element:

• Nodes unify when their kinds are equal and their child lists unify (below).
• Trivia is skipped on both sides: WHITESPACE and NEWLINE tokens are invisible to matching. Combined with the per-line TEXT_LINE design (whose ranges exclude leading indentation), this makes matching indentation-relative: a pattern written at one indent matches the same content at any other indent (spaces or tabs). Note that this also means interior extra indentation of continuation lines is layout, not structure — only line content is compared.
• BLANK_LINE is structure, not trivia, for matching: a blank line inside a text block is a paragraph break, so a multi-paragraph pattern only matches a multi-paragraph target. Blank lines pair up one-to-one (consecutive blank lines produce one token per line), but their text is not compared — the bytes of a blank line are invisible layout.
• UNDERLINE text is not compared either (kinds must still pair up): a NumPy header underline’s length is presentation, not content.
• Every other token pairs with a target token of the same kind and byte-identical text. In particular a zero-length (missing placeholder) pattern token only matches a zero-length target token: missing matches missing (x (): matches exactly the targets whose TYPE is missing too). The same holds for zero-length placeholder nodes (e.g. the empty DESCRIPTION of a Google x: entry): their empty child lists unify only with empty child lists.

Metavariable binding

• A $X site binds one target element of the same SyntaxKind as the pattern element it landed on (a NAME token binds a NAME token, a node site binds a node of that kind). The bound element’s subtree is not inspected. $X never binds a missing (zero-length) placeholder — to match a missing element, spell the missing form literally.
• A $$$X site is a hole in its sibling list: literal siblings before it match forward, literal siblings after it match backwards, and the hole binds the (possibly empty) contiguous middle of the target’s sibling list — whatever the kinds of those siblings. When a $$$X covers a whole fragment root (e.g. the entry reading of a lone $$$X line), it binds that single candidate fragment.
• An empty $$$X capture has a zero-length range positioned at the end of the last sibling matched before the hole; if the hole is first in its list, at the start of the first sibling matched after it; if the list is empty, at the start of the parent node. This is the exact offset where sequence content would be inserted (#47).
• Repeated metavariables (the same name at several sites, $X or $$$X) must all bind byte-identical target text; the reported capture is the first occurrence’s binding, in pattern source order.

Readings the matcher cannot use (documented v1 limits)

Both limits are per-reading, panic-free, and silent: an affected reading simply contributes no matches, while the pattern’s other readings match normally.

• A reading with an inexact site — a metavariable amid literal prose inside one TEXT_LINE token, i.e. one whose MetaVarSite::is_exact is false — is not matchable: sub-line text matching is regex territory and is deferred.
• A reading with two or more $$$ holes in the same sibling list is not matchable: the split of the middle would be ambiguous. (#45 deliberately inventories such patterns instead of rejecting them, so the matcher — the layer that gives $$$ its sequence semantics — enforces the limit at match time.)

Candidate enumeration and grammar binding

Each reading is tried against the target sites its FragmentKind and Reading::section_kinds admit. Section roles are resolved with the same section-kind resolution the unified views use (Section::kind):

• Entry readings unify against each ENTRY (or, for the References reading, CITATION) child of every SECTION whose resolved kind is in the reading’s section_kinds.
• Body readings unify against the DESCRIPTION body of every free-text section — any SectionKind::FreeText, including Unknown-named sections (the free-text body grammar is the same for all of them; the reading’s section_kinds can only list the known names).
• Section readings unify against every SECTION node. Section readings are concrete syntax: the header NAME must match literally (case-sensitively) unless it is a metavariable.
• Document readings unify against the DOCUMENT root only. Policy: Pattern::matches skips Document readings unless the pattern has no other reading (a Document reading of a short prose pattern could only ever match a whole document of exactly that shape — noise for a global search); Pattern::matches_in uses them exactly when the anchor is the document root (explicitly anchoring at the root opts in).

Anchored matching

Pattern::matches_in restricts the search to the subtree of anchor (the anchor node itself included) and derives the grammar binding from it: anchored at a SECTION, only the readings admitted by that section’s role can bind ($TYPE: $DESC anchored at a Raises: section selects the Raises-shape reading — $TYPE binds a TYPE token — where the same pattern anchored at an Args: section selects the parameter-shape reading binding a NAME token). Anchored at the document root it behaves like Pattern::matches plus Document readings. An anchor that is not a node of target’s tree yields no matches.

Match order and overlap

Candidate sites are visited in document pre-order (a section before its entries), and at each site the readings are tried in the pattern’s documented enumeration order. A candidate whose span overlaps an already-accepted match is skipped — first match wins — so the returned matches are non-overlapping and in document order. Ties at the same site are resolved by reading order.

Structs

Capture

What a metavariable bound in one Match.

Match

One non-overlapping match of a Pattern against a target document, produced by Pattern::matches / Pattern::matches_in.

Enums

CapturedElement

A reference to one captured target element — a node or a token of the target tree.