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

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 

6 

7"""AI: Pattern matching engine that finds AST nodes matching a given pattern.""" 

8 

9from collections.abc import Iterable, Sequence 

10from typing import Any, Self 

11 

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 

16 

17IRRELEVANT_PROPS = {"macro_expansion", "start_point", "end_point", "source_code", "location", "type"} 

18 

19MIS_MATCH = -12 

20INCOMPLETE_MATCH = -11 

21_TOP_LEVEL_KINDS = {"Module", "TRANSLATION_UNIT"} 

22 

23 

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 

34 

35 

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 

46 

47 

48class Variant: 

49 """AI: Track one candidate pattern-match state (bound expansions, greedy position) during matching.""" 

50 

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 

65 

66 def reset_greedy(self) -> None: 

67 """AI: Clear the current greedy-expansion tracking state.""" 

68 self.greedy = None 

69 self.expansion_start = -1 

70 

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() 

76 

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) 

80 

81 

82class PatternMatch: 

83 """AI: Represent a successful match of a pattern against a sequence of AST nodes.""" 

84 

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 

90 

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) 

94 

95 @property 

96 def signature(self): 

97 """AI: Return the newline-joined signatures of the matched nodes.""" 

98 return str(self) 

99 

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]) 

103 

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) 

107 

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) 

111 

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 ] 

120 

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 

124 

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 

128 

129 

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 

136 

137 

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 

141 

142 

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 [] 

154 

155 

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 

176 

177 

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 

195 

196 

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 

219 

220 

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 

255 

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 

276 

277 

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 

289 

290 

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) != [] 

294 

295 

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 = {} 

300 

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 

309 

310 return all(match_property(n) for n in (src.keys() | cmp.keys()) - IRRELEVANT_PROPS) 

311 

312 

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 

328 

329 

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)] 

333 

334 

335class MatchFinder: 

336 """AI: Static entry points for finding pattern matches against source AST nodes.""" 

337 

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) 

346 

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) 

355 

356 

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.