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