Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/blib2to3/pytree.py: 32%

1# Copyright 2006 Google, Inc. All Rights Reserved. 

2# Licensed to PSF under a Contributor Agreement. 

3 

4""" 

5Python parse tree definitions. 

6 

7This is a very concrete parse tree; we need to keep every token and 

8even the comments and whitespace between tokens. 

9 

10There's also a pattern matching implementation here. 

11""" 

12 

13# mypy: allow-untyped-defs, allow-incomplete-defs 

14 

15from collections.abc import Iterable, Iterator 

16from typing import Any, Optional, TypeVar, Union 

17 

18from blib2to3.pgen2.grammar import Grammar 

19 

20__author__ = "Guido van Rossum <guido@python.org>" 

21 

22import sys 

23from io import StringIO 

24 

25HUGE: int = 0x7FFFFFFF # maximum repeat count, default max 

26 

27_type_reprs: dict[int, Union[str, int]] = {} 

28 

29 

30def type_repr(type_num: int) -> Union[str, int]: 

31 global _type_reprs 

32 if not _type_reprs: 

33 from . import pygram 

34 

35 if not hasattr(pygram, "python_symbols"): 

36 pygram.initialize(cache_dir=None) 

37 

38 # printing tokens is possible but not as useful 

39 # from .pgen2 import token // token.__dict__.items(): 

40 for name in dir(pygram.python_symbols): 

41 val = getattr(pygram.python_symbols, name) 

42 if type(val) == int: 

43 _type_reprs[val] = name 

44 return _type_reprs.setdefault(type_num, type_num) 

45 

46 

47_P = TypeVar("_P", bound="Base") 

48 

49NL = Union["Node", "Leaf"] 

50Context = tuple[str, tuple[int, int]] 

51RawNode = tuple[int, Optional[str], Optional[Context], Optional[list[NL]]] 

52 

53 

54class Base: 

55 """ 

56 Abstract base class for Node and Leaf. 

57 

58 This provides some default functionality and boilerplate using the 

59 template pattern. 

60 

61 A node may be a subnode of at most one parent. 

62 """ 

63 

64 # Default values for instance variables 

65 type: int # int: token number (< 256) or symbol number (>= 256) 

66 parent: Optional["Node"] = None # Parent node pointer, or None 

67 children: list[NL] # List of subnodes 

68 was_changed: bool = False 

69 was_checked: bool = False 

70 

71 def __new__(cls, *args, **kwds): 

72 """Constructor that prevents Base from being instantiated.""" 

73 assert cls is not Base, "Cannot instantiate Base" 

74 return object.__new__(cls) 

75 

76 def __eq__(self, other: Any) -> bool: 

77 """ 

78 Compare two nodes for equality. 

79 

80 This calls the method _eq(). 

81 """ 

82 if self.__class__ is not other.__class__: 

83 return NotImplemented 

84 return self._eq(other) 

85 

86 @property 

87 def prefix(self) -> str: 

88 raise NotImplementedError 

89 

90 def _eq(self: _P, other: _P) -> bool: 

91 """ 

92 Compare two nodes for equality. 

93 

94 This is called by __eq__ and __ne__. It is only called if the two nodes 

95 have the same type. This must be implemented by the concrete subclass. 

96 Nodes should be considered equal if they have the same structure, 

97 ignoring the prefix string and other context information. 

98 """ 

99 raise NotImplementedError 

100 

101 def __deepcopy__(self: _P, memo: Any) -> _P: 

102 return self.clone() 

103 

104 def clone(self: _P) -> _P: 

105 """ 

106 Return a cloned (deep) copy of self. 

107 

108 This must be implemented by the concrete subclass. 

109 """ 

110 raise NotImplementedError 

111 

112 def post_order(self) -> Iterator[NL]: 

113 """ 

114 Return a post-order iterator for the tree. 

115 

116 This must be implemented by the concrete subclass. 

117 """ 

118 raise NotImplementedError 

119 

120 def pre_order(self) -> Iterator[NL]: 

121 """ 

122 Return a pre-order iterator for the tree. 

123 

124 This must be implemented by the concrete subclass. 

125 """ 

126 raise NotImplementedError 

127 

128 def replace(self, new: Union[NL, list[NL]]) -> None: 

129 """Replace this node with a new one in the parent.""" 

130 assert self.parent is not None, str(self) 

131 assert new is not None 

132 if not isinstance(new, list): 

133 new = [new] 

134 l_children = [] 

135 found = False 

136 for ch in self.parent.children: 

137 if ch is self: 

138 assert not found, (self.parent.children, self, new) 

139 if new is not None: 

140 l_children.extend(new) 

141 found = True 

142 else: 

143 l_children.append(ch) 

144 assert found, (self.children, self, new) 

145 self.parent.children = l_children 

146 self.parent.changed() 

147 self.parent.invalidate_sibling_maps() 

148 for x in new: 

149 x.parent = self.parent 

150 self.parent = None 

151 

152 def get_lineno(self) -> Optional[int]: 

153 """Return the line number which generated the invocant node.""" 

154 node = self 

155 while not isinstance(node, Leaf): 

156 if not node.children: 

157 return None 

158 node = node.children[0] 

159 return node.lineno 

160 

161 def changed(self) -> None: 

162 if self.was_changed: 

163 return 

164 if self.parent: 

165 self.parent.changed() 

166 self.was_changed = True 

167 

168 def remove(self) -> Optional[int]: 

169 """ 

170 Remove the node from the tree. Returns the position of the node in its 

171 parent's children before it was removed. 

172 """ 

173 if self.parent: 

174 for i, node in enumerate(self.parent.children): 

175 if node is self: 

176 del self.parent.children[i] 

177 self.parent.changed() 

178 self.parent.invalidate_sibling_maps() 

179 self.parent = None 

180 return i 

181 return None 

182 

183 @property 

184 def next_sibling(self) -> Optional[NL]: 

185 """ 

186 The node immediately following the invocant in their parent's children 

187 list. If the invocant does not have a next sibling, it is None 

188 """ 

189 if self.parent is None: 

190 return None 

191 

192 if self.parent.next_sibling_map is None: 

193 self.parent.update_sibling_maps() 

194 assert self.parent.next_sibling_map is not None 

195 return self.parent.next_sibling_map[id(self)] 

196 

197 @property 

198 def prev_sibling(self) -> Optional[NL]: 

199 """ 

200 The node immediately preceding the invocant in their parent's children 

201 list. If the invocant does not have a previous sibling, it is None. 

202 """ 

203 if self.parent is None: 

204 return None 

205 

206 if self.parent.prev_sibling_map is None: 

207 self.parent.update_sibling_maps() 

208 assert self.parent.prev_sibling_map is not None 

209 return self.parent.prev_sibling_map[id(self)] 

210 

211 def leaves(self) -> Iterator["Leaf"]: 

212 for child in self.children: 

213 yield from child.leaves() 

214 

215 def depth(self) -> int: 

216 if self.parent is None: 

217 return 0 

218 return 1 + self.parent.depth() 

219 

220 def get_suffix(self) -> str: 

221 """ 

222 Return the string immediately following the invocant node. This is 

223 effectively equivalent to node.next_sibling.prefix 

224 """ 

225 next_sib = self.next_sibling 

226 if next_sib is None: 

227 return "" 

228 prefix = next_sib.prefix 

229 return prefix 

230 

231 

232class Node(Base): 

233 """Concrete implementation for interior nodes.""" 

234 

235 fixers_applied: Optional[list[Any]] 

236 used_names: Optional[set[str]] 

237 

238 def __init__( 

239 self, 

240 type: int, 

241 children: list[NL], 

242 context: Optional[Any] = None, 

243 prefix: Optional[str] = None, 

244 fixers_applied: Optional[list[Any]] = None, 

245 ) -> None: 

246 """ 

247 Initializer. 

248 

249 Takes a type constant (a symbol number >= 256), a sequence of 

250 child nodes, and an optional context keyword argument. 

251 

252 As a side effect, the parent pointers of the children are updated. 

253 """ 

254 assert type >= 256, type 

255 self.type = type 

256 self.children = list(children) 

257 for ch in self.children: 

258 assert ch.parent is None, repr(ch) 

259 ch.parent = self 

260 self.invalidate_sibling_maps() 

261 if prefix is not None: 

262 self.prefix = prefix 

263 if fixers_applied: 

264 self.fixers_applied = fixers_applied[:] 

265 else: 

266 self.fixers_applied = None 

267 

268 def __repr__(self) -> str: 

269 """Return a canonical string representation.""" 

270 assert self.type is not None 

271 return f"{self.__class__.__name__}({type_repr(self.type)}, {self.children!r})" 

272 

273 def __str__(self) -> str: 

274 """ 

275 Return a pretty string representation. 

276 

277 This reproduces the input source exactly. 

278 """ 

279 return "".join(map(str, self.children)) 

280 

281 def _eq(self, other: Base) -> bool: 

282 """Compare two nodes for equality.""" 

283 return (self.type, self.children) == (other.type, other.children) 

284 

285 def clone(self) -> "Node": 

286 assert self.type is not None 

287 """Return a cloned (deep) copy of self.""" 

288 return Node( 

289 self.type, 

290 [ch.clone() for ch in self.children], 

291 fixers_applied=self.fixers_applied, 

292 ) 

293 

294 def post_order(self) -> Iterator[NL]: 

295 """Return a post-order iterator for the tree.""" 

296 for child in self.children: 

297 yield from child.post_order() 

298 yield self 

299 

300 def pre_order(self) -> Iterator[NL]: 

301 """Return a pre-order iterator for the tree.""" 

302 yield self 

303 for child in self.children: 

304 yield from child.pre_order() 

305 

306 @property 

307 def prefix(self) -> str: 

308 """ 

309 The whitespace and comments preceding this node in the input. 

310 """ 

311 if not self.children: 

312 return "" 

313 return self.children[0].prefix 

314 

315 @prefix.setter 

316 def prefix(self, prefix: str) -> None: 

317 if self.children: 

318 self.children[0].prefix = prefix 

319 

320 def set_child(self, i: int, child: NL) -> None: 

321 """ 

322 Equivalent to 'node.children[i] = child'. This method also sets the 

323 child's parent attribute appropriately. 

324 """ 

325 child.parent = self 

326 self.children[i].parent = None 

327 self.children[i] = child 

328 self.changed() 

329 self.invalidate_sibling_maps() 

330 

331 def insert_child(self, i: int, child: NL) -> None: 

332 """ 

333 Equivalent to 'node.children.insert(i, child)'. This method also sets 

334 the child's parent attribute appropriately. 

335 """ 

336 child.parent = self 

337 self.children.insert(i, child) 

338 self.changed() 

339 self.invalidate_sibling_maps() 

340 

341 def append_child(self, child: NL) -> None: 

342 """ 

343 Equivalent to 'node.children.append(child)'. This method also sets the 

344 child's parent attribute appropriately. 

345 """ 

346 child.parent = self 

347 self.children.append(child) 

348 self.changed() 

349 self.invalidate_sibling_maps() 

350 

351 def invalidate_sibling_maps(self) -> None: 

352 self.prev_sibling_map: Optional[dict[int, Optional[NL]]] = None 

353 self.next_sibling_map: Optional[dict[int, Optional[NL]]] = None 

354 

355 def update_sibling_maps(self) -> None: 

356 _prev: dict[int, Optional[NL]] = {} 

357 _next: dict[int, Optional[NL]] = {} 

358 self.prev_sibling_map = _prev 

359 self.next_sibling_map = _next 

360 previous: Optional[NL] = None 

361 for current in self.children: 

362 _prev[id(current)] = previous 

363 _next[id(previous)] = current 

364 previous = current 

365 _next[id(current)] = None 

366 

367 

368class Leaf(Base): 

369 """Concrete implementation for leaf nodes.""" 

370 

371 # Default values for instance variables 

372 value: str 

373 fixers_applied: list[Any] 

374 bracket_depth: int 

375 # Changed later in brackets.py 

376 opening_bracket: Optional["Leaf"] = None 

377 used_names: Optional[set[str]] 

378 _prefix = "" # Whitespace and comments preceding this token in the input 

379 lineno: int = 0 # Line where this token starts in the input 

380 column: int = 0 # Column where this token starts in the input 

381 # If not None, this Leaf is created by converting a block of fmt off/skip 

382 # code, and `fmt_pass_converted_first_leaf` points to the first Leaf in the 

383 # converted code. 

384 fmt_pass_converted_first_leaf: Optional["Leaf"] = None 

385 

386 def __init__( 

387 self, 

388 type: int, 

389 value: str, 

390 context: Optional[Context] = None, 

391 prefix: Optional[str] = None, 

392 fixers_applied: list[Any] = [], 

393 opening_bracket: Optional["Leaf"] = None, 

394 fmt_pass_converted_first_leaf: Optional["Leaf"] = None, 

395 ) -> None: 

396 """ 

397 Initializer. 

398 

399 Takes a type constant (a token number < 256), a string value, and an 

400 optional context keyword argument. 

401 """ 

402 

403 assert 0 <= type < 256, type 

404 if context is not None: 

405 self._prefix, (self.lineno, self.column) = context 

406 self.type = type 

407 self.value = value 

408 if prefix is not None: 

409 self._prefix = prefix 

410 self.fixers_applied: Optional[list[Any]] = fixers_applied[:] 

411 self.children = [] 

412 self.opening_bracket = opening_bracket 

413 self.fmt_pass_converted_first_leaf = fmt_pass_converted_first_leaf 

414 

415 def __repr__(self) -> str: 

416 """Return a canonical string representation.""" 

417 from .pgen2.token import tok_name 

418 

419 assert self.type is not None 

420 return ( 

421 f"{self.__class__.__name__}({tok_name.get(self.type, self.type)}," 

422 f" {self.value!r})" 

423 ) 

424 

425 def __str__(self) -> str: 

426 """ 

427 Return a pretty string representation. 

428 

429 This reproduces the input source exactly. 

430 """ 

431 return self._prefix + str(self.value) 

432 

433 def _eq(self, other: "Leaf") -> bool: 

434 """Compare two nodes for equality.""" 

435 return (self.type, self.value) == (other.type, other.value) 

436 

437 def clone(self) -> "Leaf": 

438 assert self.type is not None 

439 """Return a cloned (deep) copy of self.""" 

440 return Leaf( 

441 self.type, 

442 self.value, 

443 (self.prefix, (self.lineno, self.column)), 

444 fixers_applied=self.fixers_applied, 

445 ) 

446 

447 def leaves(self) -> Iterator["Leaf"]: 

448 yield self 

449 

450 def post_order(self) -> Iterator["Leaf"]: 

451 """Return a post-order iterator for the tree.""" 

452 yield self 

453 

454 def pre_order(self) -> Iterator["Leaf"]: 

455 """Return a pre-order iterator for the tree.""" 

456 yield self 

457 

458 @property 

459 def prefix(self) -> str: 

460 """ 

461 The whitespace and comments preceding this token in the input. 

462 """ 

463 return self._prefix 

464 

465 @prefix.setter 

466 def prefix(self, prefix: str) -> None: 

467 self.changed() 

468 self._prefix = prefix 

469 

470 

471def convert(gr: Grammar, raw_node: RawNode) -> NL: 

472 """ 

473 Convert raw node information to a Node or Leaf instance. 

474 

475 This is passed to the parser driver which calls it whenever a reduction of a 

476 grammar rule produces a new complete node, so that the tree is build 

477 strictly bottom-up. 

478 """ 

479 type, value, context, children = raw_node 

480 if children or type in gr.number2symbol: 

481 # If there's exactly one child, return that child instead of 

482 # creating a new node. 

483 assert children is not None 

484 if len(children) == 1: 

485 return children[0] 

486 return Node(type, children, context=context) 

487 else: 

488 return Leaf(type, value or "", context=context) 

489 

490 

491_Results = dict[str, NL] 

492 

493 

494class BasePattern: 

495 """ 

496 A pattern is a tree matching pattern. 

497 

498 It looks for a specific node type (token or symbol), and 

499 optionally for a specific content. 

500 

501 This is an abstract base class. There are three concrete 

502 subclasses: 

503 

504 - LeafPattern matches a single leaf node; 

505 - NodePattern matches a single node (usually non-leaf); 

506 - WildcardPattern matches a sequence of nodes of variable length. 

507 """ 

508 

509 # Defaults for instance variables 

510 type: Optional[int] 

511 type = None # Node type (token if < 256, symbol if >= 256) 

512 content: Any = None # Optional content matching pattern 

513 name: Optional[str] = None # Optional name used to store match in results dict 

514 

515 def __new__(cls, *args, **kwds): 

516 """Constructor that prevents BasePattern from being instantiated.""" 

517 assert cls is not BasePattern, "Cannot instantiate BasePattern" 

518 return object.__new__(cls) 

519 

520 def __repr__(self) -> str: 

521 assert self.type is not None 

522 args = [type_repr(self.type), self.content, self.name] 

523 while args and args[-1] is None: 

524 del args[-1] 

525 return f"{self.__class__.__name__}({', '.join(map(repr, args))})" 

526 

527 def _submatch(self, node, results=None) -> bool: 

528 raise NotImplementedError 

529 

530 def optimize(self) -> "BasePattern": 

531 """ 

532 A subclass can define this as a hook for optimizations. 

533 

534 Returns either self or another node with the same effect. 

535 """ 

536 return self 

537 

538 def match(self, node: NL, results: Optional[_Results] = None) -> bool: 

539 """ 

540 Does this pattern exactly match a node? 

541 

542 Returns True if it matches, False if not. 

543 

544 If results is not None, it must be a dict which will be 

545 updated with the nodes matching named subpatterns. 

546 

547 Default implementation for non-wildcard patterns. 

548 """ 

549 if self.type is not None and node.type != self.type: 

550 return False 

551 if self.content is not None: 

552 r: Optional[_Results] = None 

553 if results is not None: 

554 r = {} 

555 if not self._submatch(node, r): 

556 return False 

557 if r: 

558 assert results is not None 

559 results.update(r) 

560 if results is not None and self.name: 

561 results[self.name] = node 

562 return True 

563 

564 def match_seq(self, nodes: list[NL], results: Optional[_Results] = None) -> bool: 

565 """ 

566 Does this pattern exactly match a sequence of nodes? 

567 

568 Default implementation for non-wildcard patterns. 

569 """ 

570 if len(nodes) != 1: 

571 return False 

572 return self.match(nodes[0], results) 

573 

574 def generate_matches(self, nodes: list[NL]) -> Iterator[tuple[int, _Results]]: 

575 """ 

576 Generator yielding all matches for this pattern. 

577 

578 Default implementation for non-wildcard patterns. 

579 """ 

580 r: _Results = {} 

581 if nodes and self.match(nodes[0], r): 

582 yield 1, r 

583 

584 

585class LeafPattern(BasePattern): 

586 def __init__( 

587 self, 

588 type: Optional[int] = None, 

589 content: Optional[str] = None, 

590 name: Optional[str] = None, 

591 ) -> None: 

592 """ 

593 Initializer. Takes optional type, content, and name. 

594 

595 The type, if given must be a token type (< 256). If not given, 

596 this matches any *leaf* node; the content may still be required. 

597 

598 The content, if given, must be a string. 

599 

600 If a name is given, the matching node is stored in the results 

601 dict under that key. 

602 """ 

603 if type is not None: 

604 assert 0 <= type < 256, type 

605 if content is not None: 

606 assert isinstance(content, str), repr(content) 

607 self.type = type 

608 self.content = content 

609 self.name = name 

610 

611 def match(self, node: NL, results=None) -> bool: 

612 """Override match() to insist on a leaf node.""" 

613 if not isinstance(node, Leaf): 

614 return False 

615 return BasePattern.match(self, node, results) 

616 

617 def _submatch(self, node, results=None): 

618 """ 

619 Match the pattern's content to the node's children. 

620 

621 This assumes the node type matches and self.content is not None. 

622 

623 Returns True if it matches, False if not. 

624 

625 If results is not None, it must be a dict which will be 

626 updated with the nodes matching named subpatterns. 

627 

628 When returning False, the results dict may still be updated. 

629 """ 

630 return self.content == node.value 

631 

632 

633class NodePattern(BasePattern): 

634 wildcards: bool = False 

635 

636 def __init__( 

637 self, 

638 type: Optional[int] = None, 

639 content: Optional[Iterable[str]] = None, 

640 name: Optional[str] = None, 

641 ) -> None: 

642 """ 

643 Initializer. Takes optional type, content, and name. 

644 

645 The type, if given, must be a symbol type (>= 256). If the 

646 type is None this matches *any* single node (leaf or not), 

647 except if content is not None, in which it only matches 

648 non-leaf nodes that also match the content pattern. 

649 

650 The content, if not None, must be a sequence of Patterns that 

651 must match the node's children exactly. If the content is 

652 given, the type must not be None. 

653 

654 If a name is given, the matching node is stored in the results 

655 dict under that key. 

656 """ 

657 if type is not None: 

658 assert type >= 256, type 

659 if content is not None: 

660 assert not isinstance(content, str), repr(content) 

661 newcontent = list(content) 

662 for i, item in enumerate(newcontent): 

663 assert isinstance(item, BasePattern), (i, item) 

664 # I don't even think this code is used anywhere, but it does cause 

665 # unreachable errors from mypy. This function's signature does look 

666 # odd though *shrug*. 

667 if isinstance(item, WildcardPattern): # type: ignore[unreachable] 

668 self.wildcards = True # type: ignore[unreachable] 

669 self.type = type 

670 self.content = newcontent # TODO: this is unbound when content is None 

671 self.name = name 

672 

673 def _submatch(self, node, results=None) -> bool: 

674 """ 

675 Match the pattern's content to the node's children. 

676 

677 This assumes the node type matches and self.content is not None. 

678 

679 Returns True if it matches, False if not. 

680 

681 If results is not None, it must be a dict which will be 

682 updated with the nodes matching named subpatterns. 

683 

684 When returning False, the results dict may still be updated. 

685 """ 

686 if self.wildcards: 

687 for c, r in generate_matches(self.content, node.children): 

688 if c == len(node.children): 

689 if results is not None: 

690 results.update(r) 

691 return True 

692 return False 

693 if len(self.content) != len(node.children): 

694 return False 

695 for subpattern, child in zip(self.content, node.children): 

696 if not subpattern.match(child, results): 

697 return False 

698 return True 

699 

700 

701class WildcardPattern(BasePattern): 

702 """ 

703 A wildcard pattern can match zero or more nodes. 

704 

705 This has all the flexibility needed to implement patterns like: 

706 

707 .* .+ .? .{m,n} 

708 (a b c | d e | f) 

709 (...)* (...)+ (...)? (...){m,n} 

710 

711 except it always uses non-greedy matching. 

712 """ 

713 

714 min: int 

715 max: int 

716 

717 def __init__( 

718 self, 

719 content: Optional[str] = None, 

720 min: int = 0, 

721 max: int = HUGE, 

722 name: Optional[str] = None, 

723 ) -> None: 

724 """ 

725 Initializer. 

726 

727 Args: 

728 content: optional sequence of subsequences of patterns; 

729 if absent, matches one node; 

730 if present, each subsequence is an alternative [*] 

731 min: optional minimum number of times to match, default 0 

732 max: optional maximum number of times to match, default HUGE 

733 name: optional name assigned to this match 

734 

735 [*] Thus, if content is [[a, b, c], [d, e], [f, g, h]] this is 

736 equivalent to (a b c | d e | f g h); if content is None, 

737 this is equivalent to '.' in regular expression terms. 

738 The min and max parameters work as follows: 

739 min=0, max=maxint: .* 

740 min=1, max=maxint: .+ 

741 min=0, max=1: .? 

742 min=1, max=1: . 

743 If content is not None, replace the dot with the parenthesized 

744 list of alternatives, e.g. (a b c | d e | f g h)* 

745 """ 

746 assert 0 <= min <= max <= HUGE, (min, max) 

747 if content is not None: 

748 f = lambda s: tuple(s) 

749 wrapped_content = tuple(map(f, content)) # Protect against alterations 

750 # Check sanity of alternatives 

751 assert len(wrapped_content), repr( 

752 wrapped_content 

753 ) # Can't have zero alternatives 

754 for alt in wrapped_content: 

755 assert len(alt), repr(alt) # Can have empty alternatives 

756 self.content = wrapped_content 

757 self.min = min 

758 self.max = max 

759 self.name = name 

760 

761 def optimize(self) -> Any: 

762 """Optimize certain stacked wildcard patterns.""" 

763 subpattern = None 

764 if ( 

765 self.content is not None 

766 and len(self.content) == 1 

767 and len(self.content[0]) == 1 

768 ): 

769 subpattern = self.content[0][0] 

770 if self.min == 1 and self.max == 1: 

771 if self.content is None: 

772 return NodePattern(name=self.name) 

773 if subpattern is not None and self.name == subpattern.name: 

774 return subpattern.optimize() 

775 if ( 

776 self.min <= 1 

777 and isinstance(subpattern, WildcardPattern) 

778 and subpattern.min <= 1 

779 and self.name == subpattern.name 

780 ): 

781 return WildcardPattern( 

782 subpattern.content, 

783 self.min * subpattern.min, 

784 self.max * subpattern.max, 

785 subpattern.name, 

786 ) 

787 return self 

788 

789 def match(self, node, results=None) -> bool: 

790 """Does this pattern exactly match a node?""" 

791 return self.match_seq([node], results) 

792 

793 def match_seq(self, nodes, results=None) -> bool: 

794 """Does this pattern exactly match a sequence of nodes?""" 

795 for c, r in self.generate_matches(nodes): 

796 if c == len(nodes): 

797 if results is not None: 

798 results.update(r) 

799 if self.name: 

800 results[self.name] = list(nodes) 

801 return True 

802 return False 

803 

804 def generate_matches(self, nodes) -> Iterator[tuple[int, _Results]]: 

805 """ 

806 Generator yielding matches for a sequence of nodes. 

807 

808 Args: 

809 nodes: sequence of nodes 

810 

811 Yields: 

812 (count, results) tuples where: 

813 count: the match comprises nodes[:count]; 

814 results: dict containing named submatches. 

815 """ 

816 if self.content is None: 

817 # Shortcut for special case (see __init__.__doc__) 

818 for count in range(self.min, 1 + min(len(nodes), self.max)): 

819 r = {} 

820 if self.name: 

821 r[self.name] = nodes[:count] 

822 yield count, r 

823 elif self.name == "bare_name": 

824 yield self._bare_name_matches(nodes) 

825 else: 

826 # The reason for this is that hitting the recursion limit usually 

827 # results in some ugly messages about how RuntimeErrors are being 

828 # ignored. We only have to do this on CPython, though, because other 

829 # implementations don't have this nasty bug in the first place. 

830 if hasattr(sys, "getrefcount"): 

831 save_stderr = sys.stderr 

832 sys.stderr = StringIO() 

833 try: 

834 for count, r in self._recursive_matches(nodes, 0): 

835 if self.name: 

836 r[self.name] = nodes[:count] 

837 yield count, r 

838 except RuntimeError: 

839 # We fall back to the iterative pattern matching scheme if the recursive 

840 # scheme hits the recursion limit. 

841 for count, r in self._iterative_matches(nodes): 

842 if self.name: 

843 r[self.name] = nodes[:count] 

844 yield count, r 

845 finally: 

846 if hasattr(sys, "getrefcount"): 

847 sys.stderr = save_stderr 

848 

849 def _iterative_matches(self, nodes) -> Iterator[tuple[int, _Results]]: 

850 """Helper to iteratively yield the matches.""" 

851 nodelen = len(nodes) 

852 if 0 >= self.min: 

853 yield 0, {} 

854 

855 results = [] 

856 # generate matches that use just one alt from self.content 

857 for alt in self.content: 

858 for c, r in generate_matches(alt, nodes): 

859 yield c, r 

860 results.append((c, r)) 

861 

862 # for each match, iterate down the nodes 

863 while results: 

864 new_results = [] 

865 for c0, r0 in results: 

866 # stop if the entire set of nodes has been matched 

867 if c0 < nodelen and c0 <= self.max: