Coverage for /pythoncovmergedfiles/medio/medio/src/black/src/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, str | int] = {} 

28 

29 

30def type_repr(type_num: int) -> 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 

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

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

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

73 return object.__new__(cls) 

74 

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

76 """ 

77 Compare two nodes for equality. 

78 

79 This calls the method _eq(). 

80 """ 

81 if self.__class__ is not other.__class__: 

82 return NotImplemented 

83 return self._eq(other) 

84 

85 @property 

86 def prefix(self) -> str: 

87 raise NotImplementedError 

88 

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

90 """ 

91 Compare two nodes for equality. 

92 

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

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

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

96 ignoring the prefix string and other context information. 

97 """ 

98 raise NotImplementedError 

99 

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

101 return self.clone() 

102 

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

104 """ 

105 Return a cloned (deep) copy of self. 

106 

107 This must be implemented by the concrete subclass. 

108 """ 

109 raise NotImplementedError 

110 

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

112 """ 

113 Return a post-order iterator for the tree. 

114 

115 This must be implemented by the concrete subclass. 

116 """ 

117 raise NotImplementedError 

118 

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

120 """ 

121 Return a pre-order iterator for the tree. 

122 

123 This must be implemented by the concrete subclass. 

124 """ 

125 raise NotImplementedError 

126 

127 def replace(self, new: NL | list[NL]) -> None: 

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

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

130 assert new is not None 

131 if not isinstance(new, list): 

132 new = [new] 

133 l_children = [] 

134 found = False 

135 for ch in self.parent.children: 

136 if ch is self: 

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

138 if new is not None: 

139 l_children.extend(new) 

140 found = True 

141 else: 

142 l_children.append(ch) 

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

144 self.parent.children = l_children 

145 self.parent.changed() 

146 self.parent.invalidate_sibling_maps() 

147 for x in new: 

148 x.parent = self.parent 

149 self.parent = None 

150 

151 def get_lineno(self) -> int | None: 

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

153 node = self 

154 while not isinstance(node, Leaf): 

155 if not node.children: 

156 return None 

157 node = node.children[0] 

158 return node.lineno 

159 

160 def changed(self) -> None: 

161 if self.was_changed: 

162 return 

163 if self.parent: 

164 self.parent.changed() 

165 self.was_changed = True 

166 

167 def remove(self) -> int | None: 

168 """ 

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

170 parent's children before it was removed. 

171 """ 

172 if self.parent: 

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

174 if node is self: 

175 del self.parent.children[i] 

176 self.parent.changed() 

177 self.parent.invalidate_sibling_maps() 

178 self.parent = None 

179 return i 

180 return None 

181 

182 @property 

183 def next_sibling(self) -> NL | None: 

184 """ 

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

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

187 """ 

188 if self.parent is None: 

189 return None 

190 

191 if self.parent.next_sibling_map is None: 

192 self.parent.update_sibling_maps() 

193 assert self.parent.next_sibling_map is not None 

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

195 

196 @property 

197 def prev_sibling(self) -> NL | None: 

198 """ 

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

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

201 """ 

202 if self.parent is None: 

203 return None 

204 

205 if self.parent.prev_sibling_map is None: 

206 self.parent.update_sibling_maps() 

207 assert self.parent.prev_sibling_map is not None 

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

209 

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

211 for child in self.children: 

212 yield from child.leaves() 

213 

214 def depth(self) -> int: 

215 if self.parent is None: 

216 return 0 

217 return 1 + self.parent.depth() 

218 

219 def get_suffix(self) -> str: 

220 """ 

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

222 effectively equivalent to node.next_sibling.prefix 

223 """ 

224 next_sib = self.next_sibling 

225 if next_sib is None: 

226 return "" 

227 prefix = next_sib.prefix 

228 return prefix 

229 

230 

231class Node(Base): 

232 """Concrete implementation for interior nodes.""" 

233 

234 fixers_applied: list[Any] | None 

235 used_names: set[str] | None 

236 

237 def __init__( 

238 self, 

239 type: int, 

240 children: list[NL], 

241 context: Any | None = None, 

242 prefix: str | None = None, 

243 fixers_applied: list[Any] | None = None, 

244 ) -> None: 

245 """ 

246 Initializer. 

247 

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

249 child nodes, and an optional context keyword argument. 

250 

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

252 """ 

253 assert type >= 256, type 

254 self.type = type 

255 self.children = list(children) 

256 for ch in self.children: 

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

258 ch.parent = self 

259 self.invalidate_sibling_maps() 

260 if prefix is not None: 

261 self.prefix = prefix 

262 if fixers_applied: 

263 self.fixers_applied = fixers_applied[:] 

264 else: 

265 self.fixers_applied = None 

266 

267 def __repr__(self) -> str: 

268 """Return a canonical string representation.""" 

269 assert self.type is not None 

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

271 

272 def __str__(self) -> str: 

273 """ 

274 Return a pretty string representation. 

275 

276 This reproduces the input source exactly. 

277 """ 

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

279 

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

281 """Compare two nodes for equality.""" 

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

283 

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

285 assert self.type is not None 

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

287 return Node( 

288 self.type, 

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

290 fixers_applied=self.fixers_applied, 

291 ) 

292 

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

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

295 for child in self.children: 

296 yield from child.post_order() 

297 yield self 

298 

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

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

301 yield self 

302 for child in self.children: 

303 yield from child.pre_order() 

304 

305 @property 

306 def prefix(self) -> str: 

307 """ 

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

309 """ 

310 if not self.children: 

311 return "" 

312 return self.children[0].prefix 

313 

314 @prefix.setter 

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

316 if self.children: 

317 self.children[0].prefix = prefix 

318 

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

320 """ 

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

322 child's parent attribute appropriately. 

323 """ 

324 child.parent = self 

325 self.children[i].parent = None 

326 self.children[i] = child 

327 self.changed() 

328 self.invalidate_sibling_maps() 

329 

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

331 """ 

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

333 the child's parent attribute appropriately. 

334 """ 

335 child.parent = self 

336 self.children.insert(i, child) 

337 self.changed() 

338 self.invalidate_sibling_maps() 

339 

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

341 """ 

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

343 child's parent attribute appropriately. 

344 """ 

345 child.parent = self 

346 self.children.append(child) 

347 self.changed() 

348 self.invalidate_sibling_maps() 

349 

350 def invalidate_sibling_maps(self) -> None: 

351 self.prev_sibling_map: dict[int, NL | None] | None = None 

352 self.next_sibling_map: dict[int, NL | None] | None = None 

353 

354 def update_sibling_maps(self) -> None: 

355 _prev: dict[int, NL | None] = {} 

356 _next: dict[int, NL | None] = {} 

357 self.prev_sibling_map = _prev 

358 self.next_sibling_map = _next 

359 previous: NL | None = None 

360 for current in self.children: 

361 _prev[id(current)] = previous 

362 _next[id(previous)] = current 

363 previous = current 

364 _next[id(current)] = None 

365 

366 

367class Leaf(Base): 

368 """Concrete implementation for leaf nodes.""" 

369 

370 # Default values for instance variables 

371 value: str 

372 fixers_applied: list[Any] 

373 bracket_depth: int 

374 # Changed later in brackets.py 

375 opening_bracket: Optional["Leaf"] = None 

376 used_names: set[str] | None 

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

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

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

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

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

382 # converted code. 

383 fmt_pass_converted_first_leaf: Optional["Leaf"] = None 

384 

385 def __init__( 

386 self, 

387 type: int, 

388 value: str, 

389 context: Context | None = None, 

390 prefix: str | None = None, 

391 fixers_applied: list[Any] = [], 

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

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

394 ) -> None: 

395 """ 

396 Initializer. 

397 

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

399 optional context keyword argument. 

400 """ 

401 

402 assert 0 <= type < 256, type 

403 if context is not None: 

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

405 self.type = type 

406 self.value = value 

407 if prefix is not None: 

408 self._prefix = prefix 

409 self.fixers_applied: list[Any] | None = fixers_applied[:] 

410 self.children = [] 

411 self.opening_bracket = opening_bracket 

412 self.fmt_pass_converted_first_leaf = fmt_pass_converted_first_leaf 

413 

414 def __repr__(self) -> str: 

415 """Return a canonical string representation.""" 

416 from .pgen2.token import tok_name 

417 

418 assert self.type is not None 

419 return ( 

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

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

422 ) 

423 

424 def __str__(self) -> str: 

425 """ 

426 Return a pretty string representation. 

427 

428 This reproduces the input source exactly. 

429 """ 

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

431 

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

433 """Compare two nodes for equality.""" 

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

435 

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

437 assert self.type is not None 

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

439 return Leaf( 

440 self.type, 

441 self.value, 

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

443 fixers_applied=self.fixers_applied, 

444 ) 

445 

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

447 yield self 

448 

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

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

451 yield self 

452 

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

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

455 yield self 

456 

457 @property 

458 def prefix(self) -> str: 

459 """ 

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

461 """ 

462 return self._prefix 

463 

464 @prefix.setter 

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

466 self.changed() 

467 self._prefix = prefix 

468 

469 

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

471 """ 

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

473 

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

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

476 strictly bottom-up. 

477 """ 

478 type, value, context, children = raw_node 

479 if children or type in gr.number2symbol: 

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

481 # creating a new node. 

482 assert children is not None 

483 if len(children) == 1: 

484 return children[0] 

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

486 else: 

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

488 

489 

490_Results = dict[str, NL] 

491 

492 

493class BasePattern: 

494 """ 

495 A pattern is a tree matching pattern. 

496 

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

498 optionally for a specific content. 

499 

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

501 subclasses: 

502 

503 - LeafPattern matches a single leaf node; 

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

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

506 """ 

507 

508 # Defaults for instance variables 

509 type: int | None 

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

511 content: Any = None # Optional content matching pattern 

512 name: str | None = None # Optional name used to store match in results dict 

513 

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

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

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

517 return object.__new__(cls) 

518 

519 def __repr__(self) -> str: 

520 assert self.type is not None 

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

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

523 del args[-1] 

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

525 

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

527 raise NotImplementedError 

528 

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

530 """ 

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

532 

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

534 """ 

535 return self 

536 

537 def match(self, node: NL, results: _Results | None = None) -> bool: 

538 """ 

539 Does this pattern exactly match a node? 

540 

541 Returns True if it matches, False if not. 

542 

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

544 updated with the nodes matching named subpatterns. 

545 

546 Default implementation for non-wildcard patterns. 

547 """ 

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

549 return False 

550 if self.content is not None: 

551 r: _Results | None = None 

552 if results is not None: 

553 r = {} 

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

555 return False 

556 if r: 

557 assert results is not None 

558 results.update(r) 

559 if results is not None and self.name: 

560 results[self.name] = node 

561 return True 

562 

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

564 """ 

565 Does this pattern exactly match a sequence of nodes? 

566 

567 Default implementation for non-wildcard patterns. 

568 """ 

569 if len(nodes) != 1: 

570 return False 

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

572 

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

574 """ 

575 Generator yielding all matches for this pattern. 

576 

577 Default implementation for non-wildcard patterns. 

578 """ 

579 r: _Results = {} 

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

581 yield 1, r 

582 

583 

584class LeafPattern(BasePattern): 

585 def __init__( 

586 self, 

587 type: int | None = None, 

588 content: str | None = None, 

589 name: str | None = None, 

590 ) -> None: 

591 """ 

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

593 

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

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

596 

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

598 

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

600 dict under that key. 

601 """ 

602 if type is not None: 

603 assert 0 <= type < 256, type 

604 if content is not None: 

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

606 self.type = type 

607 self.content = content 

608 self.name = name 

609 

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

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

612 if not isinstance(node, Leaf): 

613 return False 

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

615 

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

617 """ 

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

619 

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

621 

622 Returns True if it matches, False if not. 

623 

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

625 updated with the nodes matching named subpatterns. 

626 

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

628 """ 

629 return self.content == node.value 

630 

631 

632class NodePattern(BasePattern): 

633 wildcards: bool = False 

634 

635 def __init__( 

636 self, 

637 type: int | None = None, 

638 content: Iterable[str] | None = None, 

639 name: str | None = None, 

640 ) -> None: 

641 """ 

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

643 

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

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

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

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

648 

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

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

651 given, the type must not be None. 

652 

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

654 dict under that key. 

655 """ 

656 if type is not None: 

657 assert type >= 256, type 

658 if content is not None: 

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

660 newcontent = list(content) 

661 for i, item in enumerate(newcontent): 

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

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

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

665 # odd though *shrug*. 

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

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

668 self.type = type 

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

670 self.name = name 

671 

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

673 """ 

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

675 

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

677 

678 Returns True if it matches, False if not. 

679 

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

681 updated with the nodes matching named subpatterns. 

682 

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

684 """ 

685 if self.wildcards: 

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

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

688 if results is not None: 

689 results.update(r) 

690 return True 

691 return False 

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

693 return False 

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

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

696 return False 

697 return True 

698 

699 

700class WildcardPattern(BasePattern): 

701 """ 

702 A wildcard pattern can match zero or more nodes. 

703 

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

705 

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

707 (a b c | d e | f) 

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

709 

710 except it always uses non-greedy matching. 

711 """ 

712 

713 min: int 

714 max: int 

715 

716 def __init__( 

717 self, 

718 content: str | None = None, 

719 min: int = 0, 

720 max: int = HUGE, 

721 name: str | None = None, 

722 ) -> None: 

723 """ 

724 Initializer. 

725 

726 Args: 

727 content: optional sequence of subsequences of patterns; 

728 if absent, matches one node; 

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

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

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

732 name: optional name assigned to this match 

733 

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

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

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

737 The min and max parameters work as follows: 

738 min=0, max=maxint: .* 

739 min=1, max=maxint: .+ 

740 min=0, max=1: .? 

741 min=1, max=1: . 

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

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

744 """ 

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

746 if content is not None: 

747 f = lambda s: tuple(s) 

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

749 # Check sanity of alternatives 

750 assert len(wrapped_content), repr( 

751 wrapped_content 

752 ) # Can't have zero alternatives 

753 for alt in wrapped_content: 

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

755 self.content = wrapped_content 

756 self.min = min 

757 self.max = max 

758 self.name = name 

759 

760 def optimize(self) -> Any: 

761 """Optimize certain stacked wildcard patterns.""" 

762 subpattern = None 

763 if ( 

764 self.content is not None 

765 and len(self.content) == 1 

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

767 ): 

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

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

770 if self.content is None: 

771 return NodePattern(name=self.name) 

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

773 return subpattern.optimize() 

774 if ( 

775 self.min <= 1 

776 and isinstance(subpattern, WildcardPattern) 

777 and subpattern.min <= 1 

778 and self.name == subpattern.name 

779 ): 

780 return WildcardPattern( 

781 subpattern.content, 

782 self.min * subpattern.min, 

783 self.max * subpattern.max, 

784 subpattern.name, 

785 ) 

786 return self 

787 

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

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

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

791 

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

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

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

795 if c == len(nodes): 

796 if results is not None: 

797 results.update(r) 

798 if self.name: 

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

800 return True 

801 return False 

802 

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

804 """ 

805 Generator yielding matches for a sequence of nodes. 

806 

807 Args: 

808 nodes: sequence of nodes 

809 

810 Yields: 

811 (count, results) tuples where: 

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

813 results: dict containing named submatches. 

814 """ 

815 if self.content is None: 

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

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

818 r = {} 

819 if self.name: 

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

821 yield count, r 

822 elif self.name == "bare_name": 

823 yield self._bare_name_matches(nodes) 

824 else: 

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

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

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

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

829 if hasattr(sys, "getrefcount"): 

830 save_stderr = sys.stderr 

831 sys.stderr = StringIO() 

832 try: 

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

834 if self.name: 

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

836 yield count, r 

837 except RuntimeError: 

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

839 # scheme hits the recursion limit. 

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

841 if self.name: 

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

843 yield count, r 

844 finally: 

845 if hasattr(sys, "getrefcount"): 

846 sys.stderr = save_stderr 

847 

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

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

850 nodelen = len(nodes) 

851 if 0 >= self.min: 

852 yield 0, {} 

853 

854 results = [] 

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

856 for alt in self.content: 

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

858 yield c, r 

859 results.append((c, r)) 

860 

861 # for each match, iterate down the nodes 

862 while results: 

863 new_results = [] 

864 for c0, r0 in results: 

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

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

867 for alt in self.content: 

868 for c1, r1 in generate_matches(alt, nodes[c0:]): 

869 if c1 > 0: 

870 r = {}