Ranked tree pattern matching with path automata

A tree pattern matches at a subject root when all its branches fit the subtree rooted there. The method described here decomposes a ranked ordered pattern into paths, recognises them with a shared Aho and Corasick automaton, and joins their outputs at a common subject root.

Pattern language

Let $\Sigma$ be a finite ranked alphabet, assigning each symbol a fixed arity. A root label then determines the exact number of ordered children in a $\Sigma$ term. A wildcard $\_$ accepts any subtree at its position, independently of other wildcard occurrences. Matching requires that substituting the corresponding subject subtree for each wildcard reconstructs the complete subtree at the candidate root. The reported positions are therefore roots of matching subtrees.

The pattern a(a(b, _), c) has two matches in f(a(a(b, a(a(b, d), c)), c), z): the outer a and the nested a within its wildcard position. The lighter region contains the darker subtree as its wildcard substitution, and the darker subtree independently matches with d at the wildcard. Ordered children distinguish a(b, c) from a(c, b). Including arity in each label also prevents a match from accepting additional children.

Path language

A path is encoded as a sequence of ranked labels and child indices. Labels identify constructors, while indices identify the branches followed through them. A wildcard terminates its path without contributing a label token, retaining the child index that leads to its position. The example yields these three path strings, with a/2 denoting a binary constructor and b/0 and c/0 denoting nullary constructors:

a/2  1  a/2  1  b/0
a/2  1  a/2  2
a/2  2  c/0

The trie shares the paths' initial transitions and branches where their next tokens differ. Each common prefix is represented once:

Enumerating each path separately repeats a shared prefix for every leaf beneath it and can produce a quadratic total path length. Direct trie construction shares the prefix associated with each pattern node, keeping label transitions distinct from child index transitions. Accepting states record path lengths measured in tree labels. This measurement agrees with the traversal stack, which contains one entry per node and no separate entries for edges.

Failure automaton

The Aho and Corasick construction gives each trie state a failure link to the longest proper suffix of its path that is also a represented prefix. If the next token has no outgoing transition, the automaton follows failure links until a transition is available or the root is reached. Accepting outputs are inherited along these links. In the figure, state 6 fails to state 7 because a/2 2 is a proper suffix of its path and a prefix of the path ending in c/0.

Solid edges represent token consumption, and dashed edges represent nontrivial failure links. Double outlines identify accepting states; failure links directly to state 0 are omitted for readability.

Subject traversal

Preorder traversal maintains the current subject node, automaton state and next child position on a stack. Entry to a node feeds its ranked label to the automaton. Descent through child $i$ feeds the child index followed by that child's label. Returning from a subtree restores the saved parent state, so processing the next sibling begins in the context of the parent.

For an accepting output of length $\ell$ , the path origin is stack[top - length + 1], since stack positions count tree labels and exclude child index tokens. A counter at that origin records each distinct recognised pattern path. Reaching the number of pattern leaves establishes a complete match. Joining the paths by origin is necessary because separate path matches describe one matching subtree only when they begin at the same node. Failure outputs can update several candidate roots when one pattern path is a suffix of another along the current subject path.

The OCaml traversal below assumes that step implements automaton transitions and that each state exposes its output lengths. The surrounding implementation supplies the traversal stack and completion counters:

let tabulate top current =
  List.iter
    (fun length ->
      let origin = stack.(top - length + 1) in
      let count = 1 + Option.value ~default:0 (Hashtbl.find_opt counts origin) in
      Hashtbl.replace counts origin count;
      if count = required then matches := origin :: !matches)
    (get automaton current).output
in
let rec visit incoming top (Node (id, label, children)) =
  stack.(top) <- id;
  let current = step automaton incoming (Label (label, List.length children)) in
  tabulate top current;
  List.iteri
    (fun index child ->
      let edge_state = step automaton current (Child (index + 1)) in
      tabulate top edge_state;
      visit edge_state (top + 1) child)
    children
in
visit 0 0 subject

Ranked and unranked trees

The constructor token Label(name, arity) incorporates the child count into constructor identity, allowing exact subtree matching without a separate terminal marker. With only Label name, all required paths might match while additional subject children remain unchecked because their indices do not occur in the pattern. This weaker relation can support structural queries, but exact matching requires the observed arity in the token stream when the node is processed.

A wildcard terminates its own path without restricting its substituted subtree. Thus the two wildcard occurrences in a(_, _) do not impose equality between the children. Repeated variables requiring equal substitutions need a binding environment and structural comparison after candidate recovery. The path automaton then provides a filter, with those additional checks required for unification.

Complexity

Let $p$ denote pattern size, $n$ subject size and $z$ the number of accepting path outputs during traversal. Prefix sharing limits the trie to $O(p)$ states, although failure construction and transition costs depend on the representation of edges and inherited outputs. A total transition table requires $O(p|\Gamma|)$ entries for token alphabet $\Gamma$ , providing constant time indexed transitions at an increased space cost. Each node supplies one label token and each edge one child index token, so constant time transitions and counter updates yield $O(n + z)$ matching time. Restoring parent states can repeat failure walks across siblings. Consequently, constant time access to individual trie edges does not by itself establish this bound.

For a single pattern, let $\mathit{suf}$ be the maximum number of its path strings that occur as suffixes of one path string, counting that string itself once. The output bound $z = O(n\mathit{suf})$ gives linear matching for equal-length paths, while the worst pattern shapes permit $O(np)$ output work. A pattern forest retains the output sensitive bound by associating each output with a pattern identifier and its completion counter. Subject node identifiers allow direct counter updates, and a stack proportional to tree depth permits constant time origin recovery. An alternative bit string formulation combines height indexed words from child subtrees. When pattern height fits a machine word and word operations take constant time, it avoids suffix dependent counter work and gives $O(n + m)$ matching for $m$ reported roots. For a DAG, each path through the tree unfolding needs its own context. Deduplicating visits by node identity would discard information needed by the automaton and origin recovery.

Compiler use

For instruction selection, ranked patterns represent machine rules, wildcards capture operands and accepting identifiers identify candidate instructions at recovered roots. Selecting a cover still requires dynamic programming or another cost policy over the rules applicable at each IR node. Term rewriting can use the recovered roots as rewrite sites and reuse the compiled automaton across subjects while the rule forest remains fixed. Incremental matching must additionally determine which saved states and counters a mutation invalidates.

Demo

The demo uses the examples' prefix notation, assigns preorder identifiers to subject nodes and highlights each matching root. Its implementation is a direct recursive matcher illustrating the matching relation, so the path automaton's complexity bound does not apply to it. Select Strict for exact arity checks, or clear it to permit additional subject children after the required ones. Results update as either input changes.

Pattern Subject Strict