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