src/blib2to3/pytree.py

   1 # Copyright 2006 Google, Inc. All Rights Reserved.
   2 # Licensed to PSF under a Contributor Agreement.
   3
   4 """
   5 Python parse tree definitions.
   6
   7 This is a very concrete parse tree; we need to keep every token and
   8 even the comments and whitespace between tokens.
   9
  10 There's also a pattern matching implementation here.
  11 """
  12
  13 # mypy: allow-untyped-defs, allow-incomplete-defs
  14
  15 from typing import (
  16     Any,
  17     Dict,
  18     Iterator,
  19     List,
  20     Optional,
  21     Tuple,
  22     TypeVar,
  23     Union,
  24     Set,
  25     Iterable,
  26 )
  27 from blib2to3.pgen2.grammar import Grammar
  28
  29 __author__ = "Guido van Rossum <guido@python.org>"
  30
  31 import sys
  32 from io import StringIO
  33
  34 HUGE: int = 0x7FFFFFFF  # maximum repeat count, default max
  35
  36 _type_reprs: Dict[int, Union[str, int]] = {}
  37
  38
  39 def type_repr(type_num: int) -> Union[str, int]:
  40     global _type_reprs
  41     if not _type_reprs:
  42         from .pygram import python_symbols
  43
  44         # printing tokens is possible but not as useful
  45         # from .pgen2 import token // token.__dict__.items():
  46         for name in dir(python_symbols):
  47             val = getattr(python_symbols, name)
  48             if type(val) == int:
  49                 _type_reprs[val] = name
  50     return _type_reprs.setdefault(type_num, type_num)
  51
  52
  53 _P = TypeVar("_P", bound="Base")
  54
  55 NL = Union["Node", "Leaf"]
  56 Context = Tuple[str, Tuple[int, int]]
  57 RawNode = Tuple[int, Optional[str], Optional[Context], Optional[List[NL]]]
  58
  59
  60 class Base:
  61
  62     """
  63     Abstract base class for Node and Leaf.
  64
  65     This provides some default functionality and boilerplate using the
  66     template pattern.
  67
  68     A node may be a subnode of at most one parent.
  69     """
  70
  71     # Default values for instance variables
  72     type: int  # int: token number (< 256) or symbol number (>= 256)
  73     parent: Optional["Node"] = None  # Parent node pointer, or None
  74     children: List[NL]  # List of subnodes
  75     was_changed: bool = False
  76     was_checked: bool = False
  77
  78     def __new__(cls, *args, **kwds):
  79         """Constructor that prevents Base from being instantiated."""
  80         assert cls is not Base, "Cannot instantiate Base"
  81         return object.__new__(cls)
  82
  83     def __eq__(self, other: Any) -> bool:
  84         """
  85         Compare two nodes for equality.
  86
  87         This calls the method _eq().
  88         """
  89         if self.__class__ is not other.__class__:
  90             return NotImplemented
  91         return self._eq(other)
  92
  93     @property
  94     def prefix(self) -> str:
  95         raise NotImplementedError
  96
  97     def _eq(self: _P, other: _P) -> bool:
  98         """
  99         Compare two nodes for equality.
 100
 101         This is called by __eq__ and __ne__.  It is only called if the two nodes
 102         have the same type.  This must be implemented by the concrete subclass.
 103         Nodes should be considered equal if they have the same structure,
 104         ignoring the prefix string and other context information.
 105         """
 106         raise NotImplementedError
 107
 108     def __deepcopy__(self: _P, memo: Any) -> _P:
 109         return self.clone()
 110
 111     def clone(self: _P) -> _P:
 112         """
 113         Return a cloned (deep) copy of self.
 114
 115         This must be implemented by the concrete subclass.
 116         """
 117         raise NotImplementedError
 118
 119     def post_order(self) -> Iterator[NL]:
 120         """
 121         Return a post-order iterator for the tree.
 122
 123         This must be implemented by the concrete subclass.
 124         """
 125         raise NotImplementedError
 126
 127     def pre_order(self) -> Iterator[NL]:
 128         """
 129         Return a pre-order iterator for the tree.
 130
 131         This must be implemented by the concrete subclass.
 132         """
 133         raise NotImplementedError
 134
 135     def replace(self, new: Union[NL, List[NL]]) -> None:
 136         """Replace this node with a new one in the parent."""
 137         assert self.parent is not None, str(self)
 138         assert new is not None
 139         if not isinstance(new, list):
 140             new = [new]
 141         l_children = []
 142         found = False
 143         for ch in self.parent.children:
 144             if ch is self:
 145                 assert not found, (self.parent.children, self, new)
 146                 if new is not None:
 147                     l_children.extend(new)
 148                 found = True
 149             else:
 150                 l_children.append(ch)
 151         assert found, (self.children, self, new)
 152         self.parent.children = l_children
 153         self.parent.changed()
 154         self.parent.invalidate_sibling_maps()
 155         for x in new:
 156             x.parent = self.parent
 157         self.parent = None
 158
 159     def get_lineno(self) -> Optional[int]:
 160         """Return the line number which generated the invocant node."""
 161         node = self
 162         while not isinstance(node, Leaf):
 163             if not node.children:
 164                 return None
 165             node = node.children[0]
 166         return node.lineno
 167
 168     def changed(self) -> None:
 169         if self.was_changed:
 170             return
 171         if self.parent:
 172             self.parent.changed()
 173         self.was_changed = True
 174
 175     def remove(self) -> Optional[int]:
 176         """
 177         Remove the node from the tree. Returns the position of the node in its
 178         parent's children before it was removed.
 179         """
 180         if self.parent:
 181             for i, node in enumerate(self.parent.children):
 182                 if node is self:
 183                     del self.parent.children[i]
 184                     self.parent.changed()
 185                     self.parent.invalidate_sibling_maps()
 186                     self.parent = None
 187                     return i
 188         return None
 189
 190     @property
 191     def next_sibling(self) -> Optional[NL]:
 192         """
 193         The node immediately following the invocant in their parent's children
 194         list. If the invocant does not have a next sibling, it is None
 195         """
 196         if self.parent is None:
 197             return None
 198
 199         if self.parent.next_sibling_map is None:
 200             self.parent.update_sibling_maps()
 201         assert self.parent.next_sibling_map is not None
 202         return self.parent.next_sibling_map[id(self)]
 203
 204     @property
 205     def prev_sibling(self) -> Optional[NL]:
 206         """
 207         The node immediately preceding the invocant in their parent's children
 208         list. If the invocant does not have a previous sibling, it is None.
 209         """
 210         if self.parent is None:
 211             return None
 212
 213         if self.parent.prev_sibling_map is None:
 214             self.parent.update_sibling_maps()
 215         assert self.parent.prev_sibling_map is not None
 216         return self.parent.prev_sibling_map[id(self)]
 217
 218     def leaves(self) -> Iterator["Leaf"]:
 219         for child in self.children:
 220             yield from child.leaves()
 221
 222     def depth(self) -> int:
 223         if self.parent is None:
 224             return 0
 225         return 1 + self.parent.depth()
 226
 227     def get_suffix(self) -> str:
 228         """
 229         Return the string immediately following the invocant node. This is
 230         effectively equivalent to node.next_sibling.prefix
 231         """
 232         next_sib = self.next_sibling
 233         if next_sib is None:
 234             return ""
 235         prefix = next_sib.prefix
 236         return prefix
 237
 238
 239 class Node(Base):
 240
 241     """Concrete implementation for interior nodes."""
 242
 243     fixers_applied: Optional[List[Any]]
 244     used_names: Optional[Set[str]]
 245
 246     def __init__(
 247         self,
 248         type: int,
 249         children: List[NL],
 250         context: Optional[Any] = None,
 251         prefix: Optional[str] = None,
 252         fixers_applied: Optional[List[Any]] = None,
 253     ) -> None:
 254         """
 255         Initializer.
 256
 257         Takes a type constant (a symbol number >= 256), a sequence of
 258         child nodes, and an optional context keyword argument.
 259
 260         As a side effect, the parent pointers of the children are updated.
 261         """
 262         assert type >= 256, type
 263         self.type = type
 264         self.children = list(children)
 265         for ch in self.children:
 266             assert ch.parent is None, repr(ch)
 267             ch.parent = self
 268         self.invalidate_sibling_maps()
 269         if prefix is not None:
 270             self.prefix = prefix
 271         if fixers_applied:
 272             self.fixers_applied = fixers_applied[:]
 273         else:
 274             self.fixers_applied = None
 275
 276     def __repr__(self) -> str:
 277         """Return a canonical string representation."""
 278         assert self.type is not None
 279         return "{}({}, {!r})".format(
 280             self.__class__.__name__,
 281             type_repr(self.type),
 282             self.children,
 283         )
 284
 285     def __str__(self) -> str:
 286         """
 287         Return a pretty string representation.
 288
 289         This reproduces the input source exactly.
 290         """
 291         return "".join(map(str, self.children))
 292
 293     def _eq(self, other: Base) -> bool:
 294         """Compare two nodes for equality."""
 295         return (self.type, self.children) == (other.type, other.children)
 296
 297     def clone(self) -> "Node":
 298         assert self.type is not None
 299         """Return a cloned (deep) copy of self."""
 300         return Node(
 301             self.type,
 302             [ch.clone() for ch in self.children],
 303             fixers_applied=self.fixers_applied,
 304         )
 305
 306     def post_order(self) -> Iterator[NL]:
 307         """Return a post-order iterator for the tree."""
 308         for child in self.children:
 309             yield from child.post_order()
 310         yield self
 311
 312     def pre_order(self) -> Iterator[NL]:
 313         """Return a pre-order iterator for the tree."""
 314         yield self
 315         for child in self.children:
 316             yield from child.pre_order()
 317
 318     @property
 319     def prefix(self) -> str:
 320         """
 321         The whitespace and comments preceding this node in the input.
 322         """
 323         if not self.children:
 324             return ""
 325         return self.children[0].prefix
 326
 327     @prefix.setter
 328     def prefix(self, prefix: str) -> None:
 329         if self.children:
 330             self.children[0].prefix = prefix
 331
 332     def set_child(self, i: int, child: NL) -> None:
 333         """
 334         Equivalent to 'node.children[i] = child'. This method also sets the
 335         child's parent attribute appropriately.
 336         """
 337         child.parent = self
 338         self.children[i].parent = None
 339         self.children[i] = child
 340         self.changed()
 341         self.invalidate_sibling_maps()
 342
 343     def insert_child(self, i: int, child: NL) -> None:
 344         """
 345         Equivalent to 'node.children.insert(i, child)'. This method also sets
 346         the child's parent attribute appropriately.
 347         """
 348         child.parent = self
 349         self.children.insert(i, child)
 350         self.changed()
 351         self.invalidate_sibling_maps()
 352
 353     def append_child(self, child: NL) -> None:
 354         """
 355         Equivalent to 'node.children.append(child)'. This method also sets the
 356         child's parent attribute appropriately.
 357         """
 358         child.parent = self
 359         self.children.append(child)
 360         self.changed()
 361         self.invalidate_sibling_maps()
 362
 363     def invalidate_sibling_maps(self) -> None:
 364         self.prev_sibling_map: Optional[Dict[int, Optional[NL]]] = None
 365         self.next_sibling_map: Optional[Dict[int, Optional[NL]]] = None
 366
 367     def update_sibling_maps(self) -> None:
 368         _prev: Dict[int, Optional[NL]] = {}
 369         _next: Dict[int, Optional[NL]] = {}
 370         self.prev_sibling_map = _prev
 371         self.next_sibling_map = _next
 372         previous: Optional[NL] = None
 373         for current in self.children:
 374             _prev[id(current)] = previous
 375             _next[id(previous)] = current
 376             previous = current
 377         _next[id(current)] = None
 378
 379
 380 class Leaf(Base):
 381
 382     """Concrete implementation for leaf nodes."""
 383
 384     # Default values for instance variables
 385     value: str
 386     fixers_applied: List[Any]
 387     bracket_depth: int
 388     # Changed later in brackets.py
 389     opening_bracket: Optional["Leaf"] = None
 390     used_names: Optional[Set[str]]
 391     _prefix = ""  # Whitespace and comments preceding this token in the input
 392     lineno: int = 0  # Line where this token starts in the input
 393     column: int = 0  # Column where this token starts in the input
 394     # If not None, this Leaf is created by converting a block of fmt off/skip
 395     # code, and `fmt_pass_converted_first_leaf` points to the first Leaf in the
 396     # converted code.
 397     fmt_pass_converted_first_leaf: Optional["Leaf"] = None
 398
 399     def __init__(
 400         self,
 401         type: int,
 402         value: str,
 403         context: Optional[Context] = None,
 404         prefix: Optional[str] = None,
 405         fixers_applied: List[Any] = [],
 406         opening_bracket: Optional["Leaf"] = None,
 407         fmt_pass_converted_first_leaf: Optional["Leaf"] = None,
 408     ) -> None:
 409         """
 410         Initializer.
 411
 412         Takes a type constant (a token number < 256), a string value, and an
 413         optional context keyword argument.
 414         """
 415
 416         assert 0 <= type < 256, type
 417         if context is not None:
 418             self._prefix, (self.lineno, self.column) = context
 419         self.type = type
 420         self.value = value
 421         if prefix is not None:
 422             self._prefix = prefix
 423         self.fixers_applied: Optional[List[Any]] = fixers_applied[:]
 424         self.children = []
 425         self.opening_bracket = opening_bracket
 426         self.fmt_pass_converted_first_leaf = fmt_pass_converted_first_leaf
 427
 428     def __repr__(self) -> str:
 429         """Return a canonical string representation."""
 430         from .pgen2.token import tok_name
 431
 432         assert self.type is not None
 433         return "{}({}, {!r})".format(
 434             self.__class__.__name__,
 435             tok_name.get(self.type, self.type),
 436             self.value,
 437         )
 438
 439     def __str__(self) -> str:
 440         """
 441         Return a pretty string representation.
 442
 443         This reproduces the input source exactly.
 444         """
 445         return self._prefix + str(self.value)
 446
 447     def _eq(self, other: "Leaf") -> bool:
 448         """Compare two nodes for equality."""
 449         return (self.type, self.value) == (other.type, other.value)
 450
 451     def clone(self) -> "Leaf":
 452         assert self.type is not None
 453         """Return a cloned (deep) copy of self."""
 454         return Leaf(
 455             self.type,
 456             self.value,
 457             (self.prefix, (self.lineno, self.column)),
 458             fixers_applied=self.fixers_applied,
 459         )
 460
 461     def leaves(self) -> Iterator["Leaf"]:
 462         yield self
 463
 464     def post_order(self) -> Iterator["Leaf"]:
 465         """Return a post-order iterator for the tree."""
 466         yield self
 467
 468     def pre_order(self) -> Iterator["Leaf"]:
 469         """Return a pre-order iterator for the tree."""
 470         yield self
 471
 472     @property
 473     def prefix(self) -> str:
 474         """
 475         The whitespace and comments preceding this token in the input.
 476         """
 477         return self._prefix
 478
 479     @prefix.setter
 480     def prefix(self, prefix: str) -> None:
 481         self.changed()
 482         self._prefix = prefix
 483
 484
 485 def convert(gr: Grammar, raw_node: RawNode) -> NL:
 486     """
 487     Convert raw node information to a Node or Leaf instance.
 488
 489     This is passed to the parser driver which calls it whenever a reduction of a
 490     grammar rule produces a new complete node, so that the tree is build
 491     strictly bottom-up.
 492     """
 493     type, value, context, children = raw_node
 494     if children or type in gr.number2symbol:
 495         # If there's exactly one child, return that child instead of
 496         # creating a new node.
 497         assert children is not None
 498         if len(children) == 1:
 499             return children[0]
 500         return Node(type, children, context=context)
 501     else:
 502         return Leaf(type, value or "", context=context)
 503
 504
 505 _Results = Dict[str, NL]
 506
 507
 508 class BasePattern:
 509
 510     """
 511     A pattern is a tree matching pattern.
 512
 513     It looks for a specific node type (token or symbol), and
 514     optionally for a specific content.
 515
 516     This is an abstract base class.  There are three concrete
 517     subclasses:
 518
 519     - LeafPattern matches a single leaf node;
 520     - NodePattern matches a single node (usually non-leaf);
 521     - WildcardPattern matches a sequence of nodes of variable length.
 522     """
 523
 524     # Defaults for instance variables
 525     type: Optional[int]
 526     type = None  # Node type (token if < 256, symbol if >= 256)
 527     content: Any = None  # Optional content matching pattern
 528     name: Optional[str] = None  # Optional name used to store match in results dict
 529
 530     def __new__(cls, *args, **kwds):
 531         """Constructor that prevents BasePattern from being instantiated."""
 532         assert cls is not BasePattern, "Cannot instantiate BasePattern"
 533         return object.__new__(cls)
 534
 535     def __repr__(self) -> str:
 536         assert self.type is not None
 537         args = [type_repr(self.type), self.content, self.name]
 538         while args and args[-1] is None:
 539             del args[-1]
 540         return "{}({})".format(self.__class__.__name__, ", ".join(map(repr, args)))
 541
 542     def _submatch(self, node, results=None) -> bool:
 543         raise NotImplementedError
 544
 545     def optimize(self) -> "BasePattern":
 546         """
 547         A subclass can define this as a hook for optimizations.
 548
 549         Returns either self or another node with the same effect.
 550         """
 551         return self
 552
 553     def match(self, node: NL, results: Optional[_Results] = None) -> bool:
 554         """
 555         Does this pattern exactly match a node?
 556
 557         Returns True if it matches, False if not.
 558
 559         If results is not None, it must be a dict which will be
 560         updated with the nodes matching named subpatterns.
 561
 562         Default implementation for non-wildcard patterns.
 563         """
 564         if self.type is not None and node.type != self.type:
 565             return False
 566         if self.content is not None:
 567             r: Optional[_Results] = None
 568             if results is not None:
 569                 r = {}
 570             if not self._submatch(node, r):
 571                 return False
 572             if r:
 573                 assert results is not None
 574                 results.update(r)
 575         if results is not None and self.name:
 576             results[self.name] = node
 577         return True
 578
 579     def match_seq(self, nodes: List[NL], results: Optional[_Results] = None) -> bool:
 580         """
 581         Does this pattern exactly match a sequence of nodes?
 582
 583         Default implementation for non-wildcard patterns.
 584         """
 585         if len(nodes) != 1:
 586             return False
 587         return self.match(nodes[0], results)
 588
 589     def generate_matches(self, nodes: List[NL]) -> Iterator[Tuple[int, _Results]]:
 590         """
 591         Generator yielding all matches for this pattern.
 592
 593         Default implementation for non-wildcard patterns.
 594         """
 595         r: _Results = {}
 596         if nodes and self.match(nodes[0], r):
 597             yield 1, r
 598
 599
 600 class LeafPattern(BasePattern):
 601     def __init__(
 602         self,
 603         type: Optional[int] = None,
 604         content: Optional[str] = None,
 605         name: Optional[str] = None,
 606     ) -> None:
 607         """
 608         Initializer.  Takes optional type, content, and name.
 609
 610         The type, if given must be a token type (< 256).  If not given,
 611         this matches any *leaf* node; the content may still be required.
 612
 613         The content, if given, must be a string.
 614
 615         If a name is given, the matching node is stored in the results
 616         dict under that key.
 617         """
 618         if type is not None:
 619             assert 0 <= type < 256, type
 620         if content is not None:
 621             assert isinstance(content, str), repr(content)
 622         self.type = type
 623         self.content = content
 624         self.name = name
 625
 626     def match(self, node: NL, results=None) -> bool:
 627         """Override match() to insist on a leaf node."""
 628         if not isinstance(node, Leaf):
 629             return False
 630         return BasePattern.match(self, node, results)
 631
 632     def _submatch(self, node, results=None):
 633         """
 634         Match the pattern's content to the node's children.
 635
 636         This assumes the node type matches and self.content is not None.
 637
 638         Returns True if it matches, False if not.
 639
 640         If results is not None, it must be a dict which will be
 641         updated with the nodes matching named subpatterns.
 642
 643         When returning False, the results dict may still be updated.
 644         """
 645         return self.content == node.value
 646
 647
 648 class NodePattern(BasePattern):
 649
 650     wildcards: bool = False
 651
 652     def __init__(
 653         self,
 654         type: Optional[int] = None,
 655         content: Optional[Iterable[str]] = None,
 656         name: Optional[str] = None,
 657     ) -> None:
 658         """
 659         Initializer.  Takes optional type, content, and name.
 660
 661         The type, if given, must be a symbol type (>= 256).  If the
 662         type is None this matches *any* single node (leaf or not),
 663         except if content is not None, in which it only matches
 664         non-leaf nodes that also match the content pattern.
 665
 666         The content, if not None, must be a sequence of Patterns that
 667         must match the node's children exactly.  If the content is
 668         given, the type must not be None.
 669
 670         If a name is given, the matching node is stored in the results
 671         dict under that key.
 672         """
 673         if type is not None:
 674             assert type >= 256, type
 675         if content is not None:
 676             assert not isinstance(content, str), repr(content)
 677             newcontent = list(content)
 678             for i, item in enumerate(newcontent):
 679                 assert isinstance(item, BasePattern), (i, item)
 680                 # I don't even think this code is used anywhere, but it does cause
 681                 # unreachable errors from mypy. This function's signature does look
 682                 # odd though *shrug*.
 683                 if isinstance(item, WildcardPattern):  # type: ignore[unreachable]
 684                     self.wildcards = True  # type: ignore[unreachable]
 685         self.type = type
 686         self.content = newcontent  # TODO: this is unbound when content is None
 687         self.name = name
 688
 689     def _submatch(self, node, results=None) -> bool:
 690         """
 691         Match the pattern's content to the node's children.
 692
 693         This assumes the node type matches and self.content is not None.
 694
 695         Returns True if it matches, False if not.
 696
 697         If results is not None, it must be a dict which will be
 698         updated with the nodes matching named subpatterns.
 699
 700         When returning False, the results dict may still be updated.
 701         """
 702         if self.wildcards:
 703             for c, r in generate_matches(self.content, node.children):
 704                 if c == len(node.children):
 705                     if results is not None:
 706                         results.update(r)
 707                     return True
 708             return False
 709         if len(self.content) != len(node.children):
 710             return False
 711         for subpattern, child in zip(self.content, node.children):
 712             if not subpattern.match(child, results):
 713                 return False
 714         return True
 715
 716
 717 class WildcardPattern(BasePattern):
 718
 719     """
 720     A wildcard pattern can match zero or more nodes.
 721
 722     This has all the flexibility needed to implement patterns like:
 723
 724     .*      .+      .?      .{m,n}
 725     (a b c | d e | f)
 726     (...)*  (...)+  (...)?  (...){m,n}
 727
 728     except it always uses non-greedy matching.
 729     """
 730
 731     min: int
 732     max: int
 733
 734     def __init__(
 735         self,
 736         content: Optional[str] = None,
 737         min: int = 0,
 738         max: int = HUGE,
 739         name: Optional[str] = None,
 740     ) -> None:
 741         """
 742         Initializer.
 743
 744         Args:
 745             content: optional sequence of subsequences of patterns;
 746                      if absent, matches one node;
 747                      if present, each subsequence is an alternative [*]
 748             min: optional minimum number of times to match, default 0
 749             max: optional maximum number of times to match, default HUGE
 750             name: optional name assigned to this match
 751
 752         [*] Thus, if content is [[a, b, c], [d, e], [f, g, h]] this is
 753             equivalent to (a b c | d e | f g h); if content is None,
 754             this is equivalent to '.' in regular expression terms.
 755             The min and max parameters work as follows:
 756                 min=0, max=maxint: .*
 757                 min=1, max=maxint: .+
 758                 min=0, max=1: .?
 759                 min=1, max=1: .
 760             If content is not None, replace the dot with the parenthesized
 761             list of alternatives, e.g. (a b c | d e | f g h)*
 762         """
 763         assert 0 <= min <= max <= HUGE, (min, max)
 764         if content is not None:
 765             f = lambda s: tuple(s)
 766             wrapped_content = tuple(map(f, content))  # Protect against alterations
 767             # Check sanity of alternatives
 768             assert len(wrapped_content), repr(
 769                 wrapped_content
 770             )  # Can't have zero alternatives
 771             for alt in wrapped_content:
 772                 assert len(alt), repr(alt)  # Can have empty alternatives
 773         self.content = wrapped_content
 774         self.min = min
 775         self.max = max
 776         self.name = name
 777
 778     def optimize(self) -> Any:
 779         """Optimize certain stacked wildcard patterns."""
 780         subpattern = None
 781         if (
 782             self.content is not None
 783             and len(self.content) == 1
 784             and len(self.content[0]) == 1
 785         ):
 786             subpattern = self.content[0][0]
 787         if self.min == 1 and self.max == 1:
 788             if self.content is None:
 789                 return NodePattern(name=self.name)
 790             if subpattern is not None and self.name == subpattern.name:
 791                 return subpattern.optimize()
 792         if (
 793             self.min <= 1
 794             and isinstance(subpattern, WildcardPattern)
 795             and subpattern.min <= 1
 796             and self.name == subpattern.name
 797         ):
 798             return WildcardPattern(
 799                 subpattern.content,
 800                 self.min * subpattern.min,
 801                 self.max * subpattern.max,
 802                 subpattern.name,
 803             )
 804         return self
 805
 806     def match(self, node, results=None) -> bool:
 807         """Does this pattern exactly match a node?"""
 808         return self.match_seq([node], results)
 809
 810     def match_seq(self, nodes, results=None) -> bool:
 811         """Does this pattern exactly match a sequence of nodes?"""
 812         for c, r in self.generate_matches(nodes):
 813             if c == len(nodes):
 814                 if results is not None:
 815                     results.update(r)
 816                     if self.name:
 817                         results[self.name] = list(nodes)
 818                 return True
 819         return False
 820
 821     def generate_matches(self, nodes) -> Iterator[Tuple[int, _Results]]:
 822         """
 823         Generator yielding matches for a sequence of nodes.
 824
 825         Args:
 826             nodes: sequence of nodes
 827
 828         Yields:
 829             (count, results) tuples where:
 830             count: the match comprises nodes[:count];
 831             results: dict containing named submatches.
 832         """
 833         if self.content is None:
 834             # Shortcut for special case (see __init__.__doc__)
 835             for count in range(self.min, 1 + min(len(nodes), self.max)):
 836                 r = {}
 837                 if self.name:
 838                     r[self.name] = nodes[:count]
 839                 yield count, r
 840         elif self.name == "bare_name":
 841             yield self._bare_name_matches(nodes)
 842         else:
 843             # The reason for this is that hitting the recursion limit usually
 844             # results in some ugly messages about how RuntimeErrors are being
 845             # ignored. We only have to do this on CPython, though, because other
 846             # implementations don't have this nasty bug in the first place.
 847             if hasattr(sys, "getrefcount"):
 848                 save_stderr = sys.stderr
 849                 sys.stderr = StringIO()
 850             try:
 851                 for count, r in self._recursive_matches(nodes, 0):
 852                     if self.name:
 853                         r[self.name] = nodes[:count]
 854                     yield count, r
 855             except RuntimeError:
 856                 # We fall back to the iterative pattern matching scheme if the recursive
 857                 # scheme hits the recursion limit.
 858                 for count, r in self._iterative_matches(nodes):
 859                     if self.name:
 860                         r[self.name] = nodes[:count]
 861                     yield count, r
 862             finally:
 863                 if hasattr(sys, "getrefcount"):
 864                     sys.stderr = save_stderr
 865
 866     def _iterative_matches(self, nodes) -> Iterator[Tuple[int, _Results]]:
 867         """Helper to iteratively yield the matches."""
 868         nodelen = len(nodes)
 869         if 0 >= self.min:
 870             yield 0, {}
 871
 872         results = []
 873         # generate matches that use just one alt from self.content
 874         for alt in self.content:
 875             for c, r in generate_matches(alt, nodes):
 876                 yield c, r
 877                 results.append((c, r))
 878
 879         # for each match, iterate down the nodes
 880         while results:
 881             new_results = []
 882             for c0, r0 in results:
 883                 # stop if the entire set of nodes has been matched
 884                 if c0 < nodelen and c0 <= self.max:
 885                     for alt in self.content:
 886                         for c1, r1 in generate_matches(alt, nodes[c0:]):
 887                             if c1 > 0:
 888                                 r = {}
 889                                 r.update(r0)
 890                                 r.update(r1)
 891                                 yield c0 + c1, r
 892                                 new_results.append((c0 + c1, r))
 893             results = new_results
 894
 895     def _bare_name_matches(self, nodes) -> Tuple[int, _Results]:
 896         """Special optimized matcher for bare_name."""
 897         count = 0
 898         r = {}  # type: _Results
 899         done = False
 900         max = len(nodes)
 901         while not done and count < max:
 902             done = True
 903             for leaf in self.content:
 904                 if leaf[0].match(nodes[count], r):
 905                     count += 1
 906                     done = False
 907                     break
 908         assert self.name is not None
 909         r[self.name] = nodes[:count]
 910         return count, r
 911
 912     def _recursive_matches(self, nodes, count) -> Iterator[Tuple[int, _Results]]:
 913         """Helper to recursively yield the matches."""
 914         assert self.content is not None
 915         if count >= self.min:
 916             yield 0, {}
 917         if count < self.max:
 918             for alt in self.content:
 919                 for c0, r0 in generate_matches(alt, nodes):
 920                     for c1, r1 in self._recursive_matches(nodes[c0:], count + 1):
 921                         r = {}
 922                         r.update(r0)
 923                         r.update(r1)
 924                         yield c0 + c1, r
 925
 926
 927 class NegatedPattern(BasePattern):
 928     def __init__(self, content: Optional[BasePattern] = None) -> None:
 929         """
 930         Initializer.
 931
 932         The argument is either a pattern or None.  If it is None, this
 933         only matches an empty sequence (effectively '$' in regex
 934         lingo).  If it is not None, this matches whenever the argument
 935         pattern doesn't have any matches.
 936         """
 937         if content is not None:
 938             assert isinstance(content, BasePattern), repr(content)
 939         self.content = content
 940
 941     def match(self, node, results=None) -> bool:
 942         # We never match a node in its entirety
 943         return False
 944
 945     def match_seq(self, nodes, results=None) -> bool:
 946         # We only match an empty sequence of nodes in its entirety
 947         return len(nodes) == 0
 948
 949     def generate_matches(self, nodes: List[NL]) -> Iterator[Tuple[int, _Results]]:
 950         if self.content is None:
 951             # Return a match if there is an empty sequence
 952             if len(nodes) == 0:
 953                 yield 0, {}
 954         else:
 955             # Return a match if the argument pattern has no matches
 956             for c, r in self.content.generate_matches(nodes):
 957                 return
 958             yield 0, {}
 959
 960
 961 def generate_matches(
 962     patterns: List[BasePattern], nodes: List[NL]
 963 ) -> Iterator[Tuple[int, _Results]]:
 964     """
 965     Generator yielding matches for a sequence of patterns and nodes.
 966
 967     Args:
 968         patterns: a sequence of patterns
 969         nodes: a sequence of nodes
 970
 971     Yields:
 972         (count, results) tuples where:
 973         count: the entire sequence of patterns matches nodes[:count];
 974         results: dict containing named submatches.
 975     """
 976     if not patterns:
 977         yield 0, {}
 978     else:
 979         p, rest = patterns[0], patterns[1:]
 980         for c0, r0 in p.generate_matches(nodes):
 981             if not rest:
 982                 yield c0, r0
 983             else:
 984                 for c1, r1 in generate_matches(rest, nodes[c0:]):
 985                     r = {}
 986                     r.update(r0)
 987                     r.update(r1)
 988                     yield c0 + c1, r