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

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 parent = self.parent 

134 for i, ch in enumerate(parent.children): 

135 if ch is self: 

136 break 

137 else: 

138 raise AssertionError((parent.children, self, new)) 

139 # Splice the new children in place of `self` and keep the cached sibling 

140 # maps valid without rebuilding them, which would be O(len(children)) per 

141 # call and quadratic when many children are replaced while siblings are 

142 # read in between (e.g. merging implicitly concatenated strings). 

143 parent._replace_child_in_sibling_maps(self, new) 

144 parent.children[i : i + 1] = new 

145 parent.changed() 

146 for x in new: 

147 x.parent = parent 

148 self.parent = None 

149 

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

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

152 node = self 

153 while not isinstance(node, Leaf): 

154 if not node.children: 

155 return None 

156 node = node.children[0] 

157 return node.lineno 

158 

159 def changed(self) -> None: 

160 if self.was_changed: 

161 return 

162 if self.parent: 

163 self.parent.changed() 

164 self.was_changed = True 

165 

166 def remove(self, search_start: int = 0) -> int | None: 

167 """ 

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

169 parent's children before it was removed. 

170 

171 ``search_start`` hints where to begin looking in the parent's children. 

172 A caller that removes many siblings of the same parent in left-to-right 

173 order can pass the last returned position to avoid rescanning the whole 

174 list from index 0 every time, which is quadratic over the parent. The 

175 entire list is still searched (starting at the hint and wrapping around), 

176 so an inaccurate hint only costs a little extra scanning. 

177 """ 

178 if self.parent: 

179 children = self.parent.children 

180 count = len(children) 

181 for offset in range(count): 

182 i = (search_start + offset) % count 

183 if children[i] is self: 

184 del children[i] 

185 self.parent.changed() 

186 self.parent._remove_from_sibling_maps(self) 

187 self.parent = None 

188 return i 

189 return None 

190 

191 @property 

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

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) -> NL | None: 

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 # Walk iteratively rather than recursing with `yield from`, whose per-node 

221 # generator delegation is O(depth) and makes a full traversal quadratic on 

222 # deeply nested trees (e.g. a long `a ** b ** c ** ...` chain). 

223 stack: list[NL] = list(reversed(self.children)) 

224 while stack: 

225 node = stack.pop() 

226 if isinstance(node, Leaf): 

227 yield node 

228 else: 

229 stack.extend(reversed(node.children)) 

230 

231 def depth(self) -> int: 

232 if self.parent is None: 

233 return 0 

234 return 1 + self.parent.depth() 

235 

236 def get_suffix(self) -> str: 

237 """ 

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

239 effectively equivalent to node.next_sibling.prefix 

240 """ 

241 next_sib = self.next_sibling 

242 if next_sib is None: 

243 return "" 

244 prefix = next_sib.prefix 

245 return prefix 

246 

247 

248class Node(Base): 

249 """Concrete implementation for interior nodes.""" 

250 

251 fixers_applied: list[Any] | None 

252 used_names: set[str] | None 

253 

254 def __init__( 

255 self, 

256 type: int, 

257 children: list[NL], 

258 context: Any | None = None, 

259 prefix: str | None = None, 

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

261 ) -> None: 

262 """ 

263 Initializer. 

264 

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

266 child nodes, and an optional context keyword argument. 

267 

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

269 """ 

270 assert type >= 256, type 

271 self.type = type 

272 self.children = list(children) 

273 for ch in self.children: 

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

275 ch.parent = self 

276 self.invalidate_sibling_maps() 

277 if prefix is not None: 

278 self.prefix = prefix 

279 if fixers_applied: 

280 self.fixers_applied = fixers_applied[:] 

281 else: 

282 self.fixers_applied = None 

283 

284 def __repr__(self) -> str: 

285 """Return a canonical string representation.""" 

286 assert self.type is not None 

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

288 

289 def __str__(self) -> str: 

290 """ 

291 Return a pretty string representation. 

292 

293 This reproduces the input source exactly. 

294 """ 

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

296 

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

298 """Compare two nodes for equality.""" 

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

300 

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

302 assert self.type is not None 

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

304 return Node( 

305 self.type, 

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

307 fixers_applied=self.fixers_applied, 

308 ) 

309 

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

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

312 # Walk iteratively rather than recursing with `yield from`. The recursive 

313 # form resumes one delegating generator per level on every step, so a full 

314 # traversal costs O(depth) per node and is quadratic on deeply nested trees. 

315 stack: list[tuple[NL, bool]] = [(self, False)] 

316 while stack: 

317 node, expanded = stack.pop() 

318 if expanded: 

319 yield node 

320 else: 

321 stack.append((node, True)) 

322 stack.extend((child, False) for child in reversed(node.children)) 

323 

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

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

326 # See `post_order` for why this is iterative instead of recursive. 

327 stack: list[NL] = [self] 

328 while stack: 

329 node = stack.pop() 

330 yield node 

331 stack.extend(reversed(node.children)) 

332 

333 @property 

334 def prefix(self) -> str: 

335 """ 

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

337 """ 

338 if not self.children: 

339 return "" 

340 return self.children[0].prefix 

341 

342 @prefix.setter 

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

344 if self.children: 

345 self.children[0].prefix = prefix 

346 

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

348 """ 

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

350 child's parent attribute appropriately. 

351 """ 

352 child.parent = self 

353 old = self.children[i] 

354 old.parent = None 

355 self.children[i] = child 

356 self.changed() 

357 self._replace_in_sibling_maps(old, child) 

358 

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

360 """ 

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

362 the child's parent attribute appropriately. 

363 """ 

364 child.parent = self 

365 self.children.insert(i, child) 

366 self.changed() 

367 if 0 <= i < len(self.children) and self.children[i] is child: 

368 self._insert_into_sibling_maps(i, child) 

369 else: 

370 self.invalidate_sibling_maps() 

371 

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

373 """ 

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

375 child's parent attribute appropriately. 

376 """ 

377 child.parent = self 

378 self.children.append(child) 

379 self.changed() 

380 self._insert_into_sibling_maps(len(self.children) - 1, child) 

381 

382 def invalidate_sibling_maps(self) -> None: 

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

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

385 

386 def _insert_into_sibling_maps(self, i: int, child: NL) -> None: 

387 """Splice a newly inserted child into the cached sibling maps. 

388 

389 Keeps the maps valid without rebuilding them from scratch, which would 

390 be O(len(children)) per call and quadratic when many children are 

391 inserted while siblings are read in between (e.g. ``append_leaves``). 

392 """ 

393 prev_map = self.prev_sibling_map 

394 next_map = self.next_sibling_map 

395 if prev_map is None or next_map is None: 

396 return 

397 before = self.children[i - 1] if i > 0 else None 

398 after = self.children[i + 1] if i + 1 < len(self.children) else None 

399 prev_map[id(child)] = before 

400 next_map[id(child)] = after 

401 next_map[id(before)] = child 

402 if after is not None: 

403 prev_map[id(after)] = child 

404 

405 def _remove_from_sibling_maps(self, child: NL) -> None: 

406 """Splice a removed child out of the cached sibling maps.""" 

407 prev_map = self.prev_sibling_map 

408 next_map = self.next_sibling_map 

409 if prev_map is None or next_map is None: 

410 return 

411 if id(child) not in prev_map: 

412 self.invalidate_sibling_maps() 

413 return 

414 before = prev_map.pop(id(child)) 

415 after = next_map.pop(id(child)) 

416 next_map[id(before)] = after 

417 if after is not None: 

418 prev_map[id(after)] = before 

419 

420 def _replace_in_sibling_maps(self, old: NL, child: NL) -> None: 

421 """Swap ``old`` for ``child`` at the same position in the sibling maps.""" 

422 prev_map = self.prev_sibling_map 

423 next_map = self.next_sibling_map 

424 if prev_map is None or next_map is None: 

425 return 

426 if id(old) not in prev_map: 

427 self.invalidate_sibling_maps() 

428 return 

429 before = prev_map.pop(id(old)) 

430 after = next_map.pop(id(old)) 

431 prev_map[id(child)] = before 

432 next_map[id(child)] = after 

433 next_map[id(before)] = child 

434 if after is not None: 

435 prev_map[id(after)] = child 

436 

437 def _replace_child_in_sibling_maps(self, old: NL, new_children: list[NL]) -> None: 

438 """Swap ``old`` for ``new_children`` at the same position in the maps.""" 

439 prev_map = self.prev_sibling_map 

440 next_map = self.next_sibling_map 

441 if prev_map is None or next_map is None: 

442 return 

443 if id(old) not in prev_map: 

444 self.invalidate_sibling_maps() 

445 return 

446 before = prev_map.pop(id(old)) 

447 after = next_map.pop(id(old)) 

448 previous = before 

449 for child in new_children: 

450 prev_map[id(child)] = previous 

451 next_map[id(previous)] = child 

452 previous = child 

453 next_map[id(previous)] = after 

454 if after is not None: 

455 prev_map[id(after)] = previous 

456 

457 def update_sibling_maps(self) -> None: 

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

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

460 self.prev_sibling_map = _prev 

461 self.next_sibling_map = _next 

462 previous: NL | None = None 

463 for current in self.children: 

464 _prev[id(current)] = previous 

465 _next[id(previous)] = current 

466 previous = current 

467 _next[id(current)] = None 

468 

469 

470class Leaf(Base): 

471 """Concrete implementation for leaf nodes.""" 

472 

473 # Default values for instance variables 

474 value: str 

475 fixers_applied: list[Any] 

476 bracket_depth: int 

477 # Changed later in brackets.py 

478 opening_bracket: Optional["Leaf"] = None 

479 used_names: set[str] | None 

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

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

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

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

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

485 # converted code. 

486 fmt_pass_converted_first_leaf: Optional["Leaf"] = None 

487 

488 def __init__( 

489 self, 

490 type: int, 

491 value: str, 

492 context: Context | None = None, 

493 prefix: str | None = None, 

494 fixers_applied: list[Any] = [], 

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

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

497 ) -> None: 

498 """ 

499 Initializer. 

500 

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

502 optional context keyword argument. 

503 """ 

504 

505 assert 0 <= type < 256, type 

506 if context is not None: 

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

508 self.type = type 

509 self.value = value 

510 if prefix is not None: 

511 self._prefix = prefix 

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

513 self.children = [] 

514 self.opening_bracket = opening_bracket 

515 self.fmt_pass_converted_first_leaf = fmt_pass_converted_first_leaf 

516 

517 def __repr__(self) -> str: 

518 """Return a canonical string representation.""" 

519 from .pgen2.token import tok_name 

520 

521 assert self.type is not None 

522 return ( 

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

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

525 ) 

526 

527 def __str__(self) -> str: 

528 """ 

529 Return a pretty string representation. 

530 

531 This reproduces the input source exactly. 

532 """ 

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

534 

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

536 """Compare two nodes for equality.""" 

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

538 

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

540 assert self.type is not None 

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

542 return Leaf( 

543 self.type, 

544 self.value, 

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

546 fixers_applied=self.fixers_applied, 

547 ) 

548 

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

550 yield self 

551 

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

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

554 yield self 

555 

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

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

558 yield self 

559 

560 @property 

561 def prefix(self) -> str: 

562 """ 

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

564 """ 

565 return self._prefix 

566 

567 @prefix.setter 

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

569 self.changed() 

570 self._prefix = prefix 

571 

572 

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

574 """ 

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

576 

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

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

579 strictly bottom-up. 

580 """ 

581 type, value, context, children = raw_node 

582 if children or type in gr.number2symbol: 

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

584 # creating a new node. 

585 assert children is not None 

586 if len(children) == 1: 

587 return children[0] 

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

589 else: 

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

591 

592 

593_Results = dict[str, NL] 

594 

595 

596class BasePattern: 

597 """ 

598 A pattern is a tree matching pattern. 

599 

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

601 optionally for a specific content. 

602 

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

604 subclasses: 

605 

606 - LeafPattern matches a single leaf node; 

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

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

609 """ 

610 

611 # Defaults for instance variables 

612 type: int | None 

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

614 content: Any = None # Optional content matching pattern 

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

616 

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

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

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

620 return object.__new__(cls) 

621 

622 def __repr__(self) -> str: 

623 assert self.type is not None 

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

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

626 del args[-1] 

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

628 

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

630 raise NotImplementedError 

631 

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

633 """ 

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

635 

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

637 """ 

638 return self 

639 

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

641 """ 

642 Does this pattern exactly match a node? 

643 

644 Returns True if it matches, False if not. 

645 

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

647 updated with the nodes matching named subpatterns. 

648 

649 Default implementation for non-wildcard patterns. 

650 """ 

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

652 return False 

653 if self.content is not None: 

654 r: _Results | None = None 

655 if results is not None: 

656 r = {} 

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

658 return False 

659 if r: 

660 assert results is not None 

661 results.update(r) 

662 if results is not None and self.name: 

663 results[self.name] = node 

664 return True 

665 

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

667 """ 

668 Does this pattern exactly match a sequence of nodes? 

669 

670 Default implementation for non-wildcard patterns. 

671 """ 

672 if len(nodes) != 1: 

673 return False 

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

675 

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

677 """ 

678 Generator yielding all matches for this pattern. 

679 

680 Default implementation for non-wildcard patterns. 

681 """ 

682 r: _Results = {} 

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

684 yield 1, r 

685 

686 

687class LeafPattern(BasePattern): 

688 def __init__( 

689 self, 

690 type: int | None = None, 

691 content: str | None = None, 

692 name: str | None = None, 

693 ) -> None: 

694 """ 

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

696 

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

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

699 

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

701 

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

703 dict under that key. 

704 """ 

705 if type is not None: 

706 assert 0 <= type < 256, type 

707 if content is not None: 

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

709 self.type = type 

710 self.content = content 

711 self.name = name 

712 

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

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

715 if not isinstance(node, Leaf): 

716 return False 

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

718 

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

720 """ 

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

722 

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

724 

725 Returns True if it matches, False if not. 

726 

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

728 updated with the nodes matching named subpatterns. 

729 

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

731 """ 

732 return self.content == node.value 

733 

734 

735class NodePattern(BasePattern): 

736 wildcards: bool = False 

737 

738 def __init__( 

739 self, 

740 type: int | None = None, 

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

742 name: str | None = None, 

743 ) -> None: 

744 """ 

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

746 

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

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

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

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

751 

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

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

754 given, the type must not be None. 

755 

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

757 dict under that key. 

758 """ 

759 if type is not None: 

760 assert type >= 256, type 

761 if content is not None: 

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

763 newcontent = list(content) 

764 for i, item in enumerate(newcontent): 

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

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

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

768 # odd though *shrug*. 

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

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

771 self.type = type 

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

773 self.name = name 

774 

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

776 """ 

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

778 

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

780 

781 Returns True if it matches, False if not. 

782 

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

784 updated with the nodes matching named subpatterns. 

785 

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

787 """ 

788 if self.wildcards: 

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

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

791 if results is not None: 

792 results.update(r) 

793 return True 

794 return False 

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

796 return False 

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

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

799 return False 

800 return True 

801 

802 

803class WildcardPattern(BasePattern): 

804 """ 

805 A wildcard pattern can match zero or more nodes. 

806 

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

808 

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

810 (a b c | d e | f) 

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

812 

813 except it always uses non-greedy matching. 

814 """ 

815 

816 min: int 

817 max: int 

818 

819 def __init__( 

820 self, 

821 content: str | None = None, 

822 min: int = 0, 

823 max: int = HUGE, 

824 name: str | None = None, 

825 ) -> None: 

826 """ 

827 Initializer. 

828 

829 Args: 

830 content: optional sequence of subsequences of patterns; 

831 if absent, matches one node; 

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

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

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

835 name: optional name assigned to this match 

836 

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

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

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

840 The min and max parameters work as follows: 

841 min=0, max=maxint: .* 

842 min=1, max=maxint: .+ 

843 min=0, max=1: .? 

844 min=1, max=1: . 

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

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

847 """ 

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

849 if content is not None: 

850 f = lambda s: tuple(s) 

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

852 # Check sanity of alternatives 

853 assert len(wrapped_content), repr( 

854 wrapped_content 

855 ) # Can't have zero alternatives 

856 for alt in wrapped_content: 

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

858 self.content = wrapped_content 

859 self.min = min 

860 self.max = max 

861 self.name = name 

862 

863 def optimize(self) -> Any: 

864 """Optimize certain stacked wildcard patterns."""