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