Matching patterns over ranked trees

Matching a tree pattern means finding a root where all of the branches of the pattern fit together, which makes the problem a little different from searching for one string inside another. The approach here breaks a ranked ordered pattern into paths and recognises them with a shared Aho and Corasick automaton before joining the successful paths at their common subject root.

Pattern language

Let \(\Sigma\) be a finite ranked alphabet where each symbol has a fixed arity, so the root label determines how many ordered children a \(\Sigma\) term must contain. Adding the wildcard \(\_\) lets a pattern accept an arbitrary subtree at that position without requiring separate wildcard occurrences to consume equal subtrees. A match exists when replacing every wildcard with its corresponding subject subtree produces the complete subtree at the candidate node, which is why the result identifies roots rather than leaves.

For the pattern a(a(b, _), c) in f(a(a(b, a(a(b, d), c)), c), z) both the outer a and the nested a inside its wildcard position are valid match roots. The green region uses the amber subtree as its wildcard substitution while the amber region independently matches the same pattern with d filling that position. Child order still matters because a(b, c) and a(c, b) are different trees, and carrying arity with each label prevents an extra child from slipping through unnoticed.

The pattern, subject and matching subject roots generated as one Graphviz composition.

Path language

Each path becomes a string of ranked labels and child indices so the automaton can recognise both the constructors it passes through and the branch it takes at each node. A wildcard stops the structural obligation without adding a label token of its own, although the child index leading to that position stays in the path. The example produces the following three strings, where a/2 names a binary constructor and b/0 and c/0 name constructors with no children:

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

These paths share their initial transitions in the trie below, with branches introduced only where their next token differs rather than duplicating the prefix for every obligation.

A Graphviz diagram showing the ranked tree pattern transformed into a trie of root to leaf path tokens.

Writing out each path independently repeats a shared prefix once for every leaf beneath it and can make the total path length quadratic even though the pattern remains small. Building the trie directly avoids that repetition by sharing the prefix represented by each pattern node and keeping label transitions separate from child index transitions. Accepting states record completed path lengths in tree labels rather than raw tokens because the subject traversal stack has one entry per node and no extra entry for an edge.

Failure automaton

The trie becomes an Aho and Corasick automaton by giving each state a failure link to its longest proper suffix that is also a prefix represented in the trie. A missing transition follows those links until it finds a usable edge or reaches the root, with accepting outputs inherited through the same failure relation. In the drawing 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 consume input tokens and dashed edges show nontrivial failure links, with double outlines marking accepting states and links straight back to state 0 omitted to keep the drawing readable.

A monochrome Graphviz diagram of the Aho-Corasick automaton with solid input transitions, dashed failure links and double outlined accepting states.

Subject traversal

The subject traversal runs in preorder and keeps the current node and automaton state on a stack together with the position of the next child to visit. Entering a node feeds its ranked label into the automaton, while descending through child \(i\) feeds the child index first and then the label of the child. Returning from a subtree restores the saved parent state so the next sibling starts from the correct path rather than inheriting the state reached inside the previous sibling.

When an accepting state emits a path length \(\ell\), its origin is stack[top - length + 1] because that stack counts tree labels while child index tokens contribute no entries. A counter at the origin records each distinct pattern path recognised from that node and reports a complete match once the count reaches the number of pattern leaves. This join is the extra work that tree matching needs because independently accepted paths only describe one matching tree when they agree on where that tree starts. Failure outputs can update several candidate roots at the same state when one pattern path occurs as a suffix of another along the current subject path.

The central traversal can be written directly in OCaml once step supplies the automaton transition and each state exposes its output lengths, with the surrounding code providing the stack and 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

Encoding a constructor as Label(name, arity) makes its number of children part of its identity, which gives exact subtree matching without adding a separate terminal marker. If an unranked representation emits only Label name then the required paths may all match while extra children remain unexamined because their indices never appeared in the pattern. That weaker relation can be useful for structural queries, but exact matching requires the observed arity to enter the token stream before the automaton processes the node.

A wildcard stops only its own path and leaves the consumed subtree unrestricted, so repeated underscores in a(_, _) do not require those two children to be equal. Adding variables that must agree across occurrences needs a binding environment and structural comparisons after a candidate root is found, leaving the path automaton as a filter rather than a complete unifier.

Complexity

Let \(p\) be the pattern size and \(n\) the subject size, with \(z\) counting accepting path outputs produced during the subject traversal. Sharing prefixes keeps the trie itself to \(O(p)\) states, while the cost of constructing and following failure transitions depends on how transitions and inherited outputs are represented. A total transition table uses \(O(p|\Gamma|)\) entries for token alphabet \(\Gamma\) and makes each step an indexed lookup, trading additional space for a predictable traversal cost. Since each node contributes one label token and each edge contributes one child index token, constant time transitions and counter updates give \(O(n + z)\) matching time. That assumption matters for a tree traversal because restoring the state of a parent can repeat failure walks across siblings, so constant time lookup of individual trie edges alone does not establish the same bound.

For one pattern let \(\mathit{suf}\) count the largest number of its path strings that occur as suffixes of any one path string, including the string itself. Then \(z = O(n\mathit{suf})\) gives linear matching when all paths have the same length but permits \(O(np)\) output work for the worst shaped patterns. A forest keeps the same output sensitive bound by attaching a pattern identifier to each output so the matcher can select the correct completion counter. Subject identifiers make counter updates direct and a stack sized to the tree depth makes root recovery constant time, while a different bit string formulation combines height indexed words from the children. When the pattern height fits a machine word and those operations take constant time, that formulation removes the suffix dependent counter work and gives \(O(n + m)\) matching for \(m\) reported roots. A DAG needs separate contexts for paths through its tree unfolding because suppressing revisits by node identity would lose the path information used by both the automaton and origin recovery.

Compiler use

Instruction selection can represent a machine rule as a ranked tree pattern whose wildcards capture operands and whose accepting identifier names a candidate instruction at the recovered root. The matcher only finds applicable rules, so choosing a cover still needs dynamic programming or another cost policy over the candidates associated with each IR node. Term rewriting can use the same roots as rewrite sites and retain the automaton across subjects when the rule forest stays fixed, avoiding repeated pattern compilation. Incremental matching also needs to track which saved states and counters a mutation invalidates, which is more involved than rerunning the traversal over an unchanged subject.

Demo

The demo accepts the same prefix notation as the examples and assigns preorder identifiers to subject nodes, then highlights every root that satisfies the entered pattern. It uses a direct recursive matcher to demonstrate the matching relation rather than running the path automaton, so its behaviour illustrates the examples without claiming the complexity bound of the automaton. Keep Strict selected for exact arity checks or clear it to allow additional subject children after those required by the pattern, with results updating as you edit either input.

Pattern Subject Strict