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

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 typing import ( 

16 Any, 

17 Dict, 

18 Iterator, 

19 List, 

20 Optional, 

21 Text, 

22 Tuple, 

23 TypeVar, 

24 Union, 

25 Set, 

26 Iterable, 

27) 

28from blib2to3.pgen2.grammar import Grammar 

29 

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

31 

32import sys 

33from io import StringIO 

34 

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

36 

37_type_reprs: Dict[int, Union[Text, int]] = {} 

38 

39 

40def type_repr(type_num: int) -> Union[Text, int]: 

41 global _type_reprs 

42 if not _type_reprs: 

43 from .pygram import python_symbols 

44 

45 # printing tokens is possible but not as useful 

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

47 for name in dir(python_symbols): 

48 val = getattr(python_symbols, name) 

49 if type(val) == int: 

50 _type_reprs[val] = name 

51 return _type_reprs.setdefault(type_num, type_num) 

52 

53 

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

55 

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

57Context = Tuple[Text, Tuple[int, int]] 

58RawNode = Tuple[int, Optional[Text], Optional[Context], Optional[List[NL]]] 

59 

60 

61class Base(object): 

62 

63 """ 

64 Abstract base class for Node and Leaf. 

65 

66 This provides some default functionality and boilerplate using the 

67 template pattern. 

68 

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

70 """ 

71 

72 # Default values for instance variables 

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

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

75 children: List[NL] # List of subnodes 

76 was_changed: bool = False 

77 was_checked: bool = False 

78 

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

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

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

82 return object.__new__(cls) 

83 

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

85 """ 

86 Compare two nodes for equality. 

87 

88 This calls the method _eq(). 

89 """ 

90 if self.__class__ is not other.__class__: 

91 return NotImplemented 

92 return self._eq(other) 

93 

94 @property 

95 def prefix(self) -> Text: 

96 raise NotImplementedError 

97 

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

99 """ 

100 Compare two nodes for equality. 

101 

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

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

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

105 ignoring the prefix string and other context information. 

106 """ 

107 raise NotImplementedError 

108 

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

110 return self.clone() 

111 

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

113 """ 

114 Return a cloned (deep) copy of self. 

115 

116 This must be implemented by the concrete subclass. 

117 """ 

118 raise NotImplementedError 

119 

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

121 """ 

122 Return a post-order iterator for the tree. 

123 

124 This must be implemented by the concrete subclass. 

125 """ 

126 raise NotImplementedError 

127 

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

129 """ 

130 Return a pre-order iterator for the tree. 

131 

132 This must be implemented by the concrete subclass. 

133 """ 

134 raise NotImplementedError 

135 

136 def replace(self, new: Union[NL, List[NL]]) -> None: 

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

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

139 assert new is not None 

140 if not isinstance(new, list): 

141 new = [new] 

142 l_children = [] 

143 found = False 

144 for ch in self.parent.children: 

145 if ch is self: 

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

147 if new is not None: 

148 l_children.extend(new) 

149 found = True 

150 else: 

151 l_children.append(ch) 

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

153 self.parent.children = l_children 

154 self.parent.changed() 

155 self.parent.invalidate_sibling_maps() 

156 for x in new: 

157 x.parent = self.parent 

158 self.parent = None 

159 

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

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

162 node = self 

163 while not isinstance(node, Leaf): 

164 if not node.children: 

165 return None 

166 node = node.children[0] 

167 return node.lineno 

168 

169 def changed(self) -> None: 

170 if self.was_changed: 

171 return 

172 if self.parent: 

173 self.parent.changed() 

174 self.was_changed = True 

175 

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

177 """ 

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

179 parent's children before it was removed. 

180 """ 

181 if self.parent: 

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

183 if node is self: 

184 del self.parent.children[i] 

185 self.parent.changed() 

186 self.parent.invalidate_sibling_maps() 

187 self.parent = None 

188 return i 

189 return None 

190 

191 @property 

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

193 """ 

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

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

196 """ 

197 if self.parent is None: 

198 return None 

199 

200 if self.parent.next_sibling_map is None: 

201 self.parent.update_sibling_maps() 

202 assert self.parent.next_sibling_map is not None 

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

204 

205 @property 

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

207 """ 

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

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

210 """ 

211 if self.parent is None: 

212 return None 

213 

214 if self.parent.prev_sibling_map is None: 

215 self.parent.update_sibling_maps() 

216 assert self.parent.prev_sibling_map is not None 

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

218 

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

220 for child in self.children: 

221 yield from child.leaves() 

222 

223 def depth(self) -> int: 

224 if self.parent is None: 

225 return 0 

226 return 1 + self.parent.depth() 

227 

228 def get_suffix(self) -> Text: 

229 """ 

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

231 effectively equivalent to node.next_sibling.prefix 

232 """ 

233 next_sib = self.next_sibling 

234 if next_sib is None: 

235 return "" 

236 prefix = next_sib.prefix 

237 return prefix 

238 

239 

240class Node(Base): 

241 

242 """Concrete implementation for interior nodes.""" 

243 

244 fixers_applied: Optional[List[Any]] 

245 used_names: Optional[Set[Text]] 

246 

247 def __init__( 

248 self, 

249 type: int, 

250 children: List[NL], 

251 context: Optional[Any] = None, 

252 prefix: Optional[Text] = None, 

253 fixers_applied: Optional[List[Any]] = None, 

254 ) -> None: 

255 """ 

256 Initializer. 

257 

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

259 child nodes, and an optional context keyword argument. 

260 

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

262 """ 

263 assert type >= 256, type 

264 self.type = type 

265 self.children = list(children) 

266 for ch in self.children: 

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

268 ch.parent = self 

269 self.invalidate_sibling_maps() 

270 if prefix is not None: 

271 self.prefix = prefix 

272 if fixers_applied: 

273 self.fixers_applied = fixers_applied[:] 

274 else: 

275 self.fixers_applied = None 

276 

277 def __repr__(self) -> Text: 

278 """Return a canonical string representation.""" 

279 assert self.type is not None 

280 return "%s(%s, %r)" % ( 

281 self.__class__.__name__, 

282 type_repr(self.type), 

283 self.children, 

284 ) 

285 

286 def __str__(self) -> Text: 

287 """ 

288 Return a pretty string representation. 

289 

290 This reproduces the input source exactly. 

291 """ 

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

293 

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

295 """Compare two nodes for equality.""" 

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

297 

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

299 assert self.type is not None 

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

301 return Node( 

302 self.type, 

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

304 fixers_applied=self.fixers_applied, 

305 ) 

306 

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

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

309 for child in self.children: 

310 yield from child.post_order() 

311 yield self 

312 

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

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

315 yield self 

316 for child in self.children: 

317 yield from child.pre_order() 

318 

319 @property 

320 def prefix(self) -> Text: 

321 """ 

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

323 """ 

324 if not self.children: 

325 return "" 

326 return self.children[0].prefix 

327 

328 @prefix.setter 

329 def prefix(self, prefix: Text) -> None: 

330 if self.children: 

331 self.children[0].prefix = prefix 

332 

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

334 """ 

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

336 child's parent attribute appropriately. 

337 """ 

338 child.parent = self 

339 self.children[i].parent = None 

340 self.children[i] = child 

341 self.changed() 

342 self.invalidate_sibling_maps() 

343 

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

345 """ 

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

347 the child's parent attribute appropriately. 

348 """ 

349 child.parent = self 

350 self.children.insert(i, child) 

351 self.changed() 

352 self.invalidate_sibling_maps() 

353 

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

355 """ 

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

357 child's parent attribute appropriately. 

358 """ 

359 child.parent = self 

360 self.children.append(child) 

361 self.changed() 

362 self.invalidate_sibling_maps() 

363 

364 def invalidate_sibling_maps(self) -> None: 

365 self.prev_sibling_map: Optional[Dict[int, Optional[NL]]] = None 

366 self.next_sibling_map: Optional[Dict[int, Optional[NL]]] = None 

367 

368 def update_sibling_maps(self) -> None: 

369 _prev: Dict[int, Optional[NL]] = {} 

370 _next: Dict[int, Optional[NL]] = {} 

371 self.prev_sibling_map = _prev 

372 self.next_sibling_map = _next 

373 previous: Optional[NL] = None 

374 for current in self.children: 

375 _prev[id(current)] = previous 

376 _next[id(previous)] = current 

377 previous = current 

378 _next[id(current)] = None 

379 

380 

381class Leaf(Base): 

382 

383 """Concrete implementation for leaf nodes.""" 

384 

385 # Default values for instance variables 

386 value: Text 

387 fixers_applied: List[Any] 

388 bracket_depth: int 

389 # Changed later in brackets.py 

390 opening_bracket: Optional["Leaf"] = None 

391 used_names: Optional[Set[Text]] 

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

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

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

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

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

397 # converted code. 

398 fmt_pass_converted_first_leaf: Optional["Leaf"] = None 

399 

400 def __init__( 

401 self, 

402 type: int, 

403 value: Text, 

404 context: Optional[Context] = None, 

405 prefix: Optional[Text] = None, 

406 fixers_applied: List[Any] = [], 

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

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

409 ) -> None: 

410 """ 

411 Initializer. 

412 

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

414 optional context keyword argument. 

415 """ 

416 

417 assert 0 <= type < 256, type 

418 if context is not None: 

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

420 self.type = type 

421 self.value = value 

422 if prefix is not None: 

423 self._prefix = prefix 

424 self.fixers_applied: Optional[List[Any]] = fixers_applied[:] 

425 self.children = [] 

426 self.opening_bracket = opening_bracket 

427 self.fmt_pass_converted_first_leaf = fmt_pass_converted_first_leaf 

428 

429 def __repr__(self) -> str: 

430 """Return a canonical string representation.""" 

431 from .pgen2.token import tok_name 

432 

433 assert self.type is not None 

434 return "%s(%s, %r)" % ( 

435 self.__class__.__name__, 

436 tok_name.get(self.type, self.type), 

437 self.value, 

438 ) 

439 

440 def __str__(self) -> Text: 

441 """ 

442 Return a pretty string representation. 

443 

444 This reproduces the input source exactly. 

445 """ 

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

447 

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

449 """Compare two nodes for equality.""" 

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

451 

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

453 assert self.type is not None 

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

455 return Leaf( 

456 self.type, 

457 self.value, 

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

459 fixers_applied=self.fixers_applied, 

460 ) 

461 

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

463 yield self 

464 

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

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

467 yield self 

468 

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

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

471 yield self 

472 

473 @property 

474 def prefix(self) -> Text: 

475 """ 

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

477 """ 

478 return self._prefix 

479 

480 @prefix.setter 

481 def prefix(self, prefix: Text) -> None: 

482 self.changed() 

483 self._prefix = prefix 

484 

485 

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

487 """ 

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

489 

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

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

492 strictly bottom-up. 

493 """ 

494 type, value, context, children = raw_node 

495 if children or type in gr.number2symbol: 

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

497 # creating a new node. 

498 assert children is not None 

499 if len(children) == 1: 

500 return children[0] 

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

502 else: 

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

504 

505 

506_Results = Dict[Text, NL] 

507 

508 

509class BasePattern(object): 

510 

511 """ 

512 A pattern is a tree matching pattern. 

513 

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

515 optionally for a specific content. 

516 

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

518 subclasses: 

519 

520 - LeafPattern matches a single leaf node; 

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

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

523 """ 

524 

525 # Defaults for instance variables 

526 type: Optional[int] 

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

528 content: Any = None # Optional content matching pattern 

529 name: Optional[Text] = None # Optional name used to store match in results dict 

530 

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

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

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

534 return object.__new__(cls) 

535 

536 def __repr__(self) -> Text: 

537 assert self.type is not None 

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

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

540 del args[-1] 

541 return "%s(%s)" % (self.__class__.__name__, ", ".join(map(repr, args))) 

542 

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

544 raise NotImplementedError 

545 

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

547 """ 

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

549 

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

551 """ 

552 return self 

553 

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

555 """ 

556 Does this pattern exactly match a node? 

557 

558 Returns True if it matches, False if not. 

559 

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

561 updated with the nodes matching named subpatterns. 

562 

563 Default implementation for non-wildcard patterns. 

564 """ 

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

566 return False 

567 if self.content is not None: 

568 r: Optional[_Results] = None 

569 if results is not None: 

570 r = {} 

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

572 return False 

573 if r: 

574 assert results is not None 

575 results.update(r) 

576 if results is not None and self.name: 

577 results[self.name] = node 

578 return True 

579 

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

581 """ 

582 Does this pattern exactly match a sequence of nodes? 

583 

584 Default implementation for non-wildcard patterns. 

585 """ 

586 if len(nodes) != 1: 

587 return False 

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

589 

590 def generate_matches(self, nodes: List[NL]) -> Iterator[Tuple[int, _Results]]: 

591 """ 

592 Generator yielding all matches for this pattern. 

593 

594 Default implementation for non-wildcard patterns. 

595 """ 

596 r: _Results = {} 

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

598 yield 1, r 

599 

600 

601class LeafPattern(BasePattern): 

602 def __init__( 

603 self, 

604 type: Optional[int] = None, 

605 content: Optional[Text] = None, 

606 name: Optional[Text] = None, 

607 ) -> None: 

608 """ 

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

610 

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

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

613 

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

615 

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

617 dict under that key. 

618 """ 

619 if type is not None: 

620 assert 0 <= type < 256, type 

621 if content is not None: 

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

623 self.type = type 

624 self.content = content 

625 self.name = name 

626 

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

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

629 if not isinstance(node, Leaf): 

630 return False 

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

632 

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

634 """ 

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

636 

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

638 

639 Returns True if it matches, False if not. 

640 

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

642 updated with the nodes matching named subpatterns. 

643 

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

645 """ 

646 return self.content == node.value 

647 

648 

649class NodePattern(BasePattern): 

650 

651 wildcards: bool = False 

652 

653 def __init__( 

654 self, 

655 type: Optional[int] = None, 

656 content: Optional[Iterable[Text]] = None, 

657 name: Optional[Text] = None, 

658 ) -> None: 

659 """ 

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

661 

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

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

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

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

666 

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

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

669 given, the type must not be None. 

670 

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

672 dict under that key. 

673 """ 

674 if type is not None: 

675 assert type >= 256, type 

676 if content is not None: 

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

678 newcontent = list(content) 

679 for i, item in enumerate(newcontent): 

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

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

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

683 # odd though *shrug*. 

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

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

686 self.type = type 

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

688 self.name = name 

689 

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

691 """ 

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

693 

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

695 

696 Returns True if it matches, False if not. 

697 

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

699 updated with the nodes matching named subpatterns. 

700 

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

702 """ 

703 if self.wildcards: 

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

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

706 if results is not None: 

707 results.update(r) 

708 return True 

709 return False 

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

711 return False 

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

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

714 return False 

715 return True 

716 

717 

718class WildcardPattern(BasePattern): 

719 

720 """ 

721 A wildcard pattern can match zero or more nodes. 

722 

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

724 

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

726 (a b c | d e | f) 

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

728 

729 except it always uses non-greedy matching. 

730 """ 

731 

732 min: int 

733 max: int 

734 

735 def __init__( 

736 self, 

737 content: Optional[Text] = None, 

738 min: int = 0, 

739 max: int = HUGE, 

740 name: Optional[Text] = None, 

741 ) -> None: 

742 """ 

743 Initializer. 

744 

745 Args: 

746 content: optional sequence of subsequences of patterns; 

747 if absent, matches one node; 

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

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

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

751 name: optional name assigned to this match 

752 

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

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

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

756 The min and max parameters work as follows: 

757 min=0, max=maxint: .* 

758 min=1, max=maxint: .+ 

759 min=0, max=1: .? 

760 min=1, max=1: . 

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

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

763 """ 

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

765 if content is not None: 

766 f = lambda s: tuple(s) 

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

768 # Check sanity of alternatives 

769 assert len(wrapped_content), repr( 

770 wrapped_content 

771 ) # Can't have zero alternatives 

772 for alt in wrapped_content: 

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

774 self.content = wrapped_content 

775 self.min = min 

776 self.max = max 

777 self.name = name 

778 

779 def optimize(self) -> Any: 

780 """Optimize certain stacked wildcard patterns.""" 

781 subpattern = None 

782 if ( 

783 self.content is not None 

784 and len(self.content) == 1 

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

786 ): 

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

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

789 if self.content is None: 

790 return NodePattern(name=self.name) 

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

792 return subpattern.optimize() 

793 if ( 

794 self.min <= 1 

795 and isinstance(subpattern, WildcardPattern) 

796 and subpattern.min <= 1 

797 and self.name == subpattern.name 

798 ): 

799 return WildcardPattern( 

800 subpattern.content, 

801 self.min * subpattern.min, 

802 self.max * subpattern.max, 

803 subpattern.name, 

804 ) 

805 return self 

806 

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

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

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

810 

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

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

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

814 if c == len(nodes): 

815 if results is not None: 

816 results.update(r) 

817 if self.name: 

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

819 return True 

820 return False 

821 

822 def generate_matches(self, nodes) -> Iterator[Tuple[int, _Results]]: 

823 """ 

824 Generator yielding matches for a sequence of nodes. 

825 

826 Args: 

827 nodes: sequence of nodes 

828 

829 Yields: 

830 (count, results) tuples where: 

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

832 results: dict containing named submatches. 

833 """ 

834 if self.content is None: 

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

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

837 r = {} 

838 if self.name: 

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

840 yield count, r 

841 elif self.name == "bare_name": 

842 yield self._bare_name_matches(nodes) 

843 else: 

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

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

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

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

848 if hasattr(sys, "getrefcount"): 

849 save_stderr = sys.stderr 

850 sys.stderr = StringIO() 

851 try: 

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

853 if self.name: 

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

855 yield count, r 

856 except RuntimeError: 

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

858 # scheme hits the recursion limit. 

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

860 if self.name: 

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

862 yield count, r 

863 finally: 

864 if hasattr(sys, "getrefcount"): 

865 sys.stderr = save_stderr 

866 

867 def _iterative_matches(self, nodes) -> Iterator[Tuple[int, _Results]]: 

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

869 nodelen = len(nodes) 

870 if 0 >= self.min: