Coverage for src/renaissance/syntax_tree/match_finder.py: 98%
222 statements
« prev ^ index » next coverage.py v7.16.2, created at 2026-10-15 10:34 +0000
1# Copyright (C) 2024-2026 TNO
2#
3# Licensed under the terms specified in the LICENSE file in the root directory
4# of this repository, also available at:
5# https://github.com/TNO/Renaissance.Py/blob/main/LICENSE
7"""AI: Pattern matching engine that finds AST nodes matching a given pattern."""
9from collections.abc import Iterable, Sequence
10from typing import Any, Self
12from renaissance.utils.ast_utils import use_dollar
14from .node_protocol import NodeProtocol
15from .pattern_kind import PatternKind
16from .semantic_kind import SemanticKind
18IRRELEVANT_PROPS = {"macro_expansion", "start_point", "end_point", "source_code", "location", "type"}
20MIS_MATCH = -12
21INCOMPLETE_MATCH = -11
22_TOP_LEVEL_KINDS = {"Module", "TRANSLATION_UNIT"}
25def pattern_kind(node: NodeProtocol) -> PatternKind | None:
26 """AI: Return the pattern kind (MATCH_ONE/MATCH_ALL) of a pattern placeholder node, or None if not one."""
27 value = getattr(node, "pattern_kind", None)
28 if value is not None:
29 return value
30 if node.parser_kind in {"MatchOne", "_MatchOne__"}:
31 return PatternKind.MATCH_ONE
32 if node.parser_kind in {"MatchAll", "_MatchAll__"}:
33 return PatternKind.MATCH_ALL
34 return None
37def node_kinds_match(source: NodeProtocol, pattern: NodeProtocol) -> bool:
38 """AI: Return True if source and pattern nodes have the same semantic kind (or parser kind as fallback)."""
39 if (
40 source.semantic_kind is not None
41 and pattern.semantic_kind is not None
42 and source.semantic_kind is not SemanticKind.NODE
43 and pattern.semantic_kind is not SemanticKind.NODE
44 ):
45 return source.semantic_kind == pattern.semantic_kind
46 return source.parser_kind == pattern.parser_kind
49class Variant:
50 """AI: Track one candidate pattern-match state (bound expansions, greedy position) during matching."""
52 def __init__(
53 self,
54 index: int,
55 exp: dict[str, Sequence[NodeProtocol]],
56 greedy: str | None,
57 expansion_start: int,
58 end_index: int = INCOMPLETE_MATCH,
59 ) -> None:
60 """AI: Track one candidate pattern-match state (bound expansions, greedy position) during matching."""
61 self.exp: dict[str, Sequence[NodeProtocol]] = exp
62 self.index: int = index
63 self.greedy: str | None = greedy
64 self.end_index: int = end_index
65 self.expansion_start: int = expansion_start
67 def reset_greedy(self) -> None:
68 """AI: Clear the current greedy-expansion tracking state."""
69 self.greedy = None
70 self.expansion_start = -1
72 def close_greedy(self, key, nodes, start, end) -> None:
73 """Store a completed greedy expansion and reset greedy state."""
74 value = nodes[start:end]
75 self.exp[key] = value
76 self.reset_greedy()
78 def fork(self) -> Variant:
79 """Return a copy of this variant at the same position (for backtracking)."""
80 return Variant(self.index, self.exp.copy(), self.greedy, self.expansion_start)
83class PatternMatch:
84 """AI: Represent a successful match of a pattern against a sequence of AST nodes."""
86 def __init__(self, nodes, expansions, patterns) -> None:
87 """AI: Represent a successful match of a pattern against a sequence of AST nodes."""
88 self.nodes = nodes
89 self.expansions = expansions
90 self.patterns = patterns
92 def __str__(self) -> str:
93 """AI: Return the newline-joined signatures of the matched nodes."""
94 return "\n".join(node.signature for node in self.nodes)
96 @property
97 def signature(self):
98 """AI: Return the newline-joined signatures of the matched nodes."""
99 return str(self)
101 def __getitem__(self, key) -> str:
102 """AI: Return the newline-joined expansion text for the given placeholder key."""
103 return "\n".join(node.signature if isinstance(node, NodeProtocol) else node for node in self.expansions[key])
105 def match_referenced_by(self, patterns: Sequence[list], recursive: bool = True) -> Sequence[Self]:
106 """AI: Return matches of patterns against the nodes that reference this match's nodes."""
107 return self._match_relations("referenced_by", patterns, recursive)
109 def match_references(self, patterns: Iterable[list], recursive: bool = True) -> Sequence[Self]:
110 """AI: Return matches of patterns against the nodes that this match's nodes reference."""
111 return self._match_relations("references", patterns, recursive)
113 def _match_relations(self, attr: str, patterns, recursive: bool) -> list:
114 return [
115 m
116 for node in self.nodes
117 for ref in getattr(node, attr)
118 for pattern in patterns
119 for m in MatchFinder.match_pattern([ref.node], pattern, recursive)
120 ]
122 def offset_of(self, key):
123 """AI: Return the source offset of the first node bound to the given expansion key."""
124 return self.expansions[key][0].offset
126 def length_of(self, key):
127 """AI: Return the total source span length covered by the nodes bound to the given expansion key."""
128 return self.expansions[key][-1].offset + self.expansions[key][-1].length - self.expansions[key][0].offset
131def _resolve_match_one(name: str, src: NodeProtocol, expansions: dict):
132 """Handle a MATCH_ONE pattern node: bind or verify the named expansion. Returns True if matched."""
133 if name in expansions:
134 return src == expansions[name][0]
135 expansions[name] = [src]
136 return True
139def is_match_tree(src: Sequence | None, cmp: Sequence | None, expansions=None):
140 """AI: Return True if the entire src sequence matches the cmp pattern sequence."""
141 return find_in_list(src, cmp, expansions, 0) == len(src) - 1
144def variant_in_match_stmt(src: NodeProtocol, cmp: NodeProtocol, expansions) -> list:
145 """AI: Return the list of matching Variants of a single src node against a single cmp pattern node."""
146 if pattern_kind(cmp) is PatternKind.MATCH_ONE and cmp.name:
147 matched = _resolve_match_one(cmp.name, src, expansions)
148 return [Variant(0, expansions, None, 0, 0)] if matched else []
149 if is_match_dict(src.properties, cmp.properties, expansions) and node_kinds_match(src, cmp):
150 if not cmp.children and src.children:
151 return []
152 variants = find_variants(src.children, cmp.children, expansions)
153 return [v for v in variants if v.end_index == len(src.children) - 1]
154 return []
157def _advance_match_all(variant: Variant, cmp: Sequence, src: Sequence, i: int, new_variants: list) -> None:
158 """Advance variant.index past consecutive MATCH_ALL pattern nodes, forking new_variants as needed."""
159 while pattern_kind(cmp[variant.index]) is PatternKind.MATCH_ALL:
160 current_name = cmp[variant.index].name
161 if variant.expansion_start == -1:
162 variant.expansion_start = i
163 variant.greedy = current_name
164 elif current_name != variant.greedy and variant.greedy not in variant.exp:
165 new_variants.append(variant.fork())
166 variant.close_greedy(variant.greedy, src, variant.expansion_start, i)
167 variant.greedy = current_name
168 variant.expansion_start = i
169 else:
170 break
171 has_next = (variant.index + 1) < len(cmp)
172 not_yet_expanded = current_name not in variant.exp or variant.exp[current_name] == []
173 if has_next and not_yet_expanded:
174 variant.index += 1
175 else:
176 break
179def _apply_child_match(variant: Variant, child_variants: list, cmp: Sequence, src: Sequence, i: int, new_variants: list) -> None:
180 """Apply a successful child match, forking if there are multiple child variants."""
181 greedy_open = variant.greedy is not None and variant.expansion_start != -1 and variant.greedy not in variant.exp
182 if greedy_open:
183 forked = variant.fork()
184 forked.exp.pop(cmp[variant.index].name, None)
185 new_variants.append(forked)
186 variant.close_greedy(variant.greedy, src, variant.expansion_start, i)
187 if len(child_variants) > 1:
188 new_variants.extend(Variant(variant.index + 1, v.exp, variant.greedy, variant.expansion_start) for v in child_variants)
189 variant.end_index = MIS_MATCH
190 else:
191 variant.exp = child_variants[0].exp
192 variant.index += 1
193 reached_end = i == len(src) - 1 and variant.index == len(cmp)
194 if reached_end:
195 variant.end_index = len(src) - 1
198def _advance_greedy(variant: Variant, cmp: Sequence, src: Sequence, i: int) -> None:
199 """Accumulate or verify greedy expansion for the current source node."""
200 exp_for_key = variant.exp.get(cmp[variant.index].name)
201 exp_index = i - variant.expansion_start
202 if exp_for_key is None:
203 at_last_src_node = i == len(src) - 1
204 greedy_matches_pattern = variant.greedy == cmp[variant.index].name
205 if at_last_src_node and greedy_matches_pattern:
206 variant.close_greedy(variant.greedy, src, variant.expansion_start, i + 1)
207 variant.end_index = i
208 variant.index += 1
209 elif exp_index < len(exp_for_key):
210 src_node_matches = src[i] == exp_for_key[exp_index]
211 expansion_complete = exp_index == len(exp_for_key) - 1
212 if not src_node_matches:
213 variant.end_index = MIS_MATCH
214 elif expansion_complete:
215 variant.reset_greedy()
216 variant.index += 1
217 else:
218 variant.reset_greedy()
219 variant.index += 1
222def find_variants(src: Sequence, cmp: Sequence, expansion=None, start: int = 0, parent=None):
223 """AI: Compute all candidate Variant matches of the cmp pattern sequence against the src node sequence."""
224 if expansion is None:
225 expansion = {}
226 if cmp is None:
227 return []
228 i = start
229 variants = [Variant(0, expansion, None, -1)]
230 while i < len(src):
231 next_variants = []
232 for variant in variants:
233 if variant.end_index is not INCOMPLETE_MATCH:
234 next_variants.append(variant)
235 continue
236 if variant.index == len(cmp):
237 variant.end_index = i - 1
238 next_variants.append(variant)
239 continue
240 _advance_match_all(variant, cmp, src, i, next_variants)
241 if variant.index == len(cmp):
242 next_variants.append(variant)
243 continue
244 if pattern_kind(cmp[variant.index]) is not PatternKind.MATCH_ALL and (
245 child_variants := variant_in_match_stmt(src[i], cmp[variant.index], variant.exp)
246 ):
247 _apply_child_match(variant, child_variants, cmp, src, i, next_variants)
248 elif variant.greedy:
249 _advance_greedy(variant, cmp, src, i)
250 else:
251 variant.end_index = MIS_MATCH
252 if variant.end_index != MIS_MATCH:
253 next_variants.append(variant)
254 variants = next_variants
255 i += 1
257 full_match = len(src) - 1
258 valid_variants = []
259 for variant in variants:
260 if variant.end_index == MIS_MATCH or variant.index < len(cmp) - 1:
261 continue
262 if variant.index == len(cmp) - 1:
263 last_cmp = cmp[variant.index]
264 trailing_wildcard = pattern_kind(last_cmp) is PatternKind.MATCH_ALL and last_cmp.name not in variant.exp
265 if not trailing_wildcard:
266 continue
267 key = variant.greedy if variant.expansion_start != -1 else last_cmp.name
268 variant.close_greedy(key, src, variant.expansion_start, -1 if variant.expansion_start != -1 else variant.expansion_start)
269 elif variant.index == len(cmp):
270 greedy_unresolved = variant.greedy and variant.greedy not in variant.exp
271 if greedy_unresolved:
272 variant.close_greedy(variant.greedy, src, variant.expansion_start, -1)
273 if variant.end_index == INCOMPLETE_MATCH:
274 variant.end_index = full_match
275 valid_variants.append(variant)
276 return valid_variants
279def find_in_list(src: Sequence, cmp: Sequence, exp=None, start: int = 0) -> int:
280 """AI: Return the end index of the first full match of cmp within src starting at start, or MIS_MATCH if none."""
281 if exp is None:
282 exp = {}
283 variants = find_variants(src, cmp, exp, start)
284 if not variants:
285 return MIS_MATCH
286 exp.update(variants[0].exp)
287 # [0] most greedy
288 # [-1] least greedy
289 return variants[0].end_index
292def is_match(src: NodeProtocol, cmp: NodeProtocol, expansions=None) -> bool:
293 """AI: Return True if the single src node matches the single cmp pattern node."""
294 return variant_in_match_stmt(src, cmp, expansions) != []
297def is_match_dict(src: dict, cmp: dict, expansions: dict | None = None) -> bool:
298 """AI: Return True if all cmp properties match the corresponding src properties, binding $-placeholders."""
299 if expansions is None:
300 expansions = {}
302 def match_property(n):
303 c = cmp.get(n)
304 s = src.get(n)
305 if isinstance(c, str) and (key := use_dollar(c)).startswith("$"):
306 return s == expansions[key][0] if key in expansions else (expansions.update({key: [s]}) or True)
307 return s == c
309 return all(match_property(n) for n in (src.keys() | cmp.keys()) - IRRELEVANT_PROPS)
312def match_pattern(src_nodes, patterns, recursive=True) -> Sequence[PatternMatch]:
313 """AI: Find all matches of patterns within src_nodes, recursing into children when recursive is True."""
314 found_statements = []
315 to_do = 0
316 while to_do < len(src_nodes):
317 found_expansions = {}
318 found_position = find_in_list(src_nodes, patterns, found_expansions, to_do)
319 if found_position >= 0:
320 found_statements.append(PatternMatch(src_nodes[to_do : found_position + 1], found_expansions, patterns))
321 to_do = found_position + 1
322 else:
323 if recursive:
324 found_statements.extend(match_pattern(getattr(src_nodes[to_do], "children", []), patterns, recursive))
325 to_do += 1
326 return found_statements
329def find_all(src_nodes, *patterns: Any, recursive: bool = True) -> Sequence[PatternMatch]:
330 """AI: Find all matches of any of the given patterns within src_nodes."""
331 return [m for pattern in patterns for m in match_pattern(src_nodes, pattern, recursive)]
334class MatchFinder:
335 """AI: Static entry points for finding pattern matches against source AST nodes."""
337 @staticmethod
338 def find_all(
339 src_nodes: Sequence[NodeProtocol],
340 *patterns: Sequence[NodeProtocol],
341 recursive: bool = True,
342 ) -> Sequence[PatternMatch]:
343 """Find all pattern matches in the given source nodes."""
344 return find_all(src_nodes, *patterns, recursive=recursive)
346 @staticmethod
347 def match_pattern(
348 src_nodes: Sequence[NodeProtocol],
349 patterns: Sequence[NodeProtocol],
350 recursive: bool = True,
351 ) -> Sequence[PatternMatch]:
352 """Match source nodes against a list of pattern nodes, optionally recursing into children."""
353 return match_pattern(src_nodes, patterns, recursive)
356# We should find the highest possible match.
357# For example in C++:
358# "int $x; $x;" matches "int x; x;"
359# "int $x = 1; int y = $x;" matches "int x = 1; int y = x;"
360# "typedef enum { $x } E; void f() { g($x); }" matches "typedef enum { x } E; void f() { g(x); }"
361# The highest shared type should be chosen as the type of $x.