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     # Changed later in brackets.py
 390     opening_bracket: Optional["Leaf"] = None
 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         opening_bracket: Optional["Leaf"] = None,
 404     ) -> None:
 405         """
 406         Initializer.
 407
 408         Takes a type constant (a token number < 256), a string value, and an
 409         optional context keyword argument.
 410         """
 411
 412         assert 0 <= type < 256, type
 413         if context is not None:
 414             self._prefix, (self.lineno, self.column) = context
 415         self.type = type
 416         self.value = value
 417         if prefix is not None:
 418             self._prefix = prefix
 419         self.fixers_applied: Optional[List[Any]] = fixers_applied[:]
 420         self.children = []
 421         self.opening_bracket = opening_bracket
 422
 423     def __repr__(self) -> str:
 424         """Return a canonical string representation."""
 425         from .pgen2.token import tok_name
 426
 427         assert self.type is not None
 428         return "%s(%s, %r)" % (
 429             self.__class__.__name__,
 430             tok_name.get(self.type, self.type),
 431             self.value,
 432         )
 433
 434     def __str__(self) -> Text:
 435         """
 436         Return a pretty string representation.
 437
 438         This reproduces the input source exactly.
 439         """
 440         return self._prefix + str(self.value)
 441
 442     def _eq(self, other) -> bool:
 443         """Compare two nodes for equality."""
 444         return (self.type, self.value) == (other.type, other.value)
 445
 446     def clone(self) -> "Leaf":
 447         assert self.type is not None
 448         """Return a cloned (deep) copy of self."""
 449         return Leaf(
 450             self.type,
 451             self.value,
 452             (self.prefix, (self.lineno, self.column)),
 453             fixers_applied=self.fixers_applied,
 454             opening_bracket=self.opening_bracket,
 455         )
 456
 457     def leaves(self) -> Iterator["Leaf"]:
 458         yield self
 459
 460     def post_order(self) -> Iterator["Leaf"]:
 461         """Return a post-order iterator for the tree."""
 462         yield self
 463
 464     def pre_order(self) -> Iterator["Leaf"]:
 465         """Return a pre-order iterator for the tree."""
 466         yield self
 467
 468     @property
 469     def prefix(self) -> Text:
 470         """
 471         The whitespace and comments preceding this token in the input.
 472         """
 473         return self._prefix
 474
 475     @prefix.setter
 476     def prefix(self, prefix) -> None:
 477         self.changed()
 478         self._prefix = prefix
 479
 480
 481 def convert(gr: Grammar, raw_node: RawNode) -> NL:
 482     """
 483     Convert raw node information to a Node or Leaf instance.
 484
 485     This is passed to the parser driver which calls it whenever a reduction of a
 486     grammar rule produces a new complete node, so that the tree is build
 487     strictly bottom-up.
 488     """
 489     type, value, context, children = raw_node
 490     if children or type in gr.number2symbol:
 491         # If there's exactly one child, return that child instead of
 492         # creating a new node.
 493         assert children is not None
 494         if len(children) == 1:
 495             return children[0]
 496         return Node(type, children, context=context)
 497     else:
 498         return Leaf(type, value or "", context=context)
 499
 500
 501 _Results = Dict[Text, NL]
 502
 503
 504 class BasePattern(object):
 505
 506     """
 507     A pattern is a tree matching pattern.
 508
 509     It looks for a specific node type (token or symbol), and
 510     optionally for a specific content.
 511
 512     This is an abstract base class.  There are three concrete
 513     subclasses:
 514
 515     - LeafPattern matches a single leaf node;
 516     - NodePattern matches a single node (usually non-leaf);
 517     - WildcardPattern matches a sequence of nodes of variable length.
 518     """
 519
 520     # Defaults for instance variables
 521     type: Optional[int]
 522     type = None  # Node type (token if < 256, symbol if >= 256)
 523     content: Any = None  # Optional content matching pattern
 524     name: Optional[Text] = None  # Optional name used to store match in results dict
 525
 526     def __new__(cls, *args, **kwds):
 527         """Constructor that prevents BasePattern from being instantiated."""
 528         assert cls is not BasePattern, "Cannot instantiate BasePattern"
 529         return object.__new__(cls)
 530
 531     def __repr__(self) -> Text:
 532         assert self.type is not None
 533         args = [type_repr(self.type), self.content, self.name]
 534         while args and args[-1] is None:
 535             del args[-1]
 536         return "%s(%s)" % (self.__class__.__name__, ", ".join(map(repr, args)))
 537
 538     def _submatch(self, node, results=None) -> bool:
 539         raise NotImplementedError
 540
 541     def optimize(self) -> "BasePattern":
 542         """
 543         A subclass can define this as a hook for optimizations.
 544
 545         Returns either self or another node with the same effect.
 546         """
 547         return self
 548
 549     def match(self, node: NL, results: Optional[_Results] = None) -> bool:
 550         """
 551         Does this pattern exactly match a node?
 552
 553         Returns True if it matches, False if not.
 554
 555         If results is not None, it must be a dict which will be
 556         updated with the nodes matching named subpatterns.
 557
 558         Default implementation for non-wildcard patterns.
 559         """
 560         if self.type is not None and node.type != self.type:
 561             return False
 562         if self.content is not None:
 563             r: Optional[_Results] = None
 564             if results is not None:
 565                 r = {}
 566             if not self._submatch(node, r):
 567                 return False
 568             if r:
 569                 assert results is not None
 570                 results.update(r)
 571         if results is not None and self.name:
 572             results[self.name] = node
 573         return True
 574
 575     def match_seq(self, nodes: List[NL], results: Optional[_Results] = None) -> bool:
 576         """
 577         Does this pattern exactly match a sequence of nodes?
 578
 579         Default implementation for non-wildcard patterns.
 580         """
 581         if len(nodes) != 1:
 582             return False
 583         return self.match(nodes[0], results)
 584
 585     def generate_matches(self, nodes: List[NL]) -> Iterator[Tuple[int, _Results]]:
 586         """
 587         Generator yielding all matches for this pattern.
 588
 589         Default implementation for non-wildcard patterns.
 590         """
 591         r: _Results = {}
 592         if nodes and self.match(nodes[0], r):
 593             yield 1, r
 594
 595
 596 class LeafPattern(BasePattern):
 597     def __init__(
 598         self,
 599         type: Optional[int] = None,
 600         content: Optional[Text] = None,
 601         name: Optional[Text] = None,
 602     ) -> None:
 603         """
 604         Initializer.  Takes optional type, content, and name.
 605
 606         The type, if given must be a token type (< 256).  If not given,
 607         this matches any *leaf* node; the content may still be required.
 608
 609         The content, if given, must be a string.
 610
 611         If a name is given, the matching node is stored in the results
 612         dict under that key.
 613         """
 614         if type is not None:
 615             assert 0 <= type < 256, type
 616         if content is not None:
 617             assert isinstance(content, str), repr(content)
 618         self.type = type
 619         self.content = content
 620         self.name = name
 621
 622     def match(self, node: NL, results=None):
 623         """Override match() to insist on a leaf node."""
 624         if not isinstance(node, Leaf):
 625             return False
 626         return BasePattern.match(self, node, results)
 627
 628     def _submatch(self, node, results=None):
 629         """
 630         Match the pattern's content to the node's children.
 631
 632         This assumes the node type matches and self.content is not None.
 633
 634         Returns True if it matches, False if not.
 635
 636         If results is not None, it must be a dict which will be
 637         updated with the nodes matching named subpatterns.
 638
 639         When returning False, the results dict may still be updated.
 640         """
 641         return self.content == node.value
 642
 643
 644 class NodePattern(BasePattern):
 645
 646     wildcards: bool = False
 647
 648     def __init__(
 649         self,
 650         type: Optional[int] = None,
 651         content: Optional[Iterable[Text]] = None,
 652         name: Optional[Text] = None,
 653     ) -> None:
 654         """
 655         Initializer.  Takes optional type, content, and name.
 656
 657         The type, if given, must be a symbol type (>= 256).  If the
 658         type is None this matches *any* single node (leaf or not),
 659         except if content is not None, in which it only matches
 660         non-leaf nodes that also match the content pattern.
 661
 662         The content, if not None, must be a sequence of Patterns that
 663         must match the node's children exactly.  If the content is
 664         given, the type must not be None.
 665
 666         If a name is given, the matching node is stored in the results
 667         dict under that key.
 668         """
 669         if type is not None:
 670             assert type >= 256, type
 671         if content is not None:
 672             assert not isinstance(content, str), repr(content)
 673             newcontent = list(content)
 674             for i, item in enumerate(newcontent):
 675                 assert isinstance(item, BasePattern), (i, item)
 676                 # I don't even think this code is used anywhere, but it does cause
 677                 # unreachable errors from mypy. This function's signature does look
 678                 # odd though *shrug*.
 679                 if isinstance(item, WildcardPattern):  # type: ignore[unreachable]
 680                     self.wildcards = True  # type: ignore[unreachable]
 681         self.type = type
 682         self.content = newcontent
 683         self.name = name
 684
 685     def _submatch(self, node, results=None) -> bool:
 686         """
 687         Match the pattern's content to the node's children.
 688
 689         This assumes the node type matches and self.content is not None.
 690
 691         Returns True if it matches, False if not.
 692
 693         If results is not None, it must be a dict which will be
 694         updated with the nodes matching named subpatterns.
 695
 696         When returning False, the results dict may still be updated.
 697         """
 698         if self.wildcards:
 699             for c, r in generate_matches(self.content, node.children):
 700                 if c == len(node.children):
 701                     if results is not None:
 702                         results.update(r)
 703                     return True
 704             return False
 705         if len(self.content) != len(node.children):
 706             return False
 707         for subpattern, child in zip(self.content, node.children):
 708             if not subpattern.match(child, results):
 709                 return False
 710         return True
 711
 712
 713 class WildcardPattern(BasePattern):
 714
 715     """
 716     A wildcard pattern can match zero or more nodes.
 717
 718     This has all the flexibility needed to implement patterns like:
 719
 720     .*      .+      .?      .{m,n}
 721     (a b c | d e | f)
 722     (...)*  (...)+  (...)?  (...){m,n}
 723
 724     except it always uses non-greedy matching.
 725     """
 726
 727     min: int
 728     max: int
 729
 730     def __init__(
 731         self,
 732         content: Optional[Text] = None,
 733         min: int = 0,
 734         max: int = HUGE,
 735         name: Optional[Text] = None,
 736     ) -> None:
 737         """
 738         Initializer.
 739
 740         Args:
 741             content: optional sequence of subsequences of patterns;
 742                      if absent, matches one node;
 743                      if present, each subsequence is an alternative [*]
 744             min: optional minimum number of times to match, default 0
 745             max: optional maximum number of times to match, default HUGE
 746             name: optional name assigned to this match
 747
 748         [*] Thus, if content is [[a, b, c], [d, e], [f, g, h]] this is
 749             equivalent to (a b c | d e | f g h); if content is None,
 750             this is equivalent to '.' in regular expression terms.
 751             The min and max parameters work as follows:
 752                 min=0, max=maxint: .*
 753                 min=1, max=maxint: .+
 754                 min=0, max=1: .?
 755                 min=1, max=1: .
 756             If content is not None, replace the dot with the parenthesized
 757             list of alternatives, e.g. (a b c | d e | f g h)*
 758         """
 759         assert 0 <= min <= max <= HUGE, (min, max)
 760         if content is not None:
 761             f = lambda s: tuple(s)
 762             wrapped_content = tuple(map(f, content))  # Protect against alterations
 763             # Check sanity of alternatives
 764             assert len(wrapped_content), repr(
 765                 wrapped_content
 766             )  # Can't have zero alternatives
 767             for alt in wrapped_content:
 768                 assert len(alt), repr(alt)  # Can have empty alternatives
 769         self.content = wrapped_content
 770         self.min = min
 771         self.max = max
 772         self.name = name
 773
 774     def optimize(self) -> Any:
 775         """Optimize certain stacked wildcard patterns."""
 776         subpattern = None
 777         if (
 778             self.content is not None
 779             and len(self.content) == 1
 780             and len(self.content[0]) == 1
 781         ):
 782             subpattern = self.content[0][0]
 783         if self.min == 1 and self.max == 1:
 784             if self.content is None:
 785                 return NodePattern(name=self.name)
 786             if subpattern is not None and self.name == subpattern.name:
 787                 return subpattern.optimize()
 788         if (
 789             self.min <= 1
 790             and isinstance(subpattern, WildcardPattern)
 791             and subpattern.min <= 1
 792             and self.name == subpattern.name
 793         ):
 794             return WildcardPattern(
 795                 subpattern.content,
 796                 self.min * subpattern.min,
 797                 self.max * subpattern.max,
 798                 subpattern.name,
 799             )
 800         return self
 801
 802     def match(self, node, results=None) -> bool:
 803         """Does this pattern exactly match a node?"""
 804         return self.match_seq([node], results)
 805
 806     def match_seq(self, nodes, results=None) -> bool:
 807         """Does this pattern exactly match a sequence of nodes?"""
 808         for c, r in self.generate_matches(nodes):
 809             if c == len(nodes):
 810                 if results is not None:
 811                     results.update(r)
 812                     if self.name:
 813                         results[self.name] = list(nodes)
 814                 return True
 815         return False
 816
 817     def generate_matches(self, nodes) -> Iterator[Tuple[int, _Results]]:
 818         """
 819         Generator yielding matches for a sequence of nodes.
 820
 821         Args:
 822             nodes: sequence of nodes
 823
 824         Yields:
 825             (count, results) tuples where:
 826             count: the match comprises nodes[:count];
 827             results: dict containing named submatches.
 828         """
 829         if self.content is None:
 830             # Shortcut for special case (see __init__.__doc__)
 831             for count in range(self.min, 1 + min(len(nodes), self.max)):
 832                 r = {}
 833                 if self.name:
 834                     r[self.name] = nodes[:count]
 835                 yield count, r
 836         elif self.name == "bare_name":
 837             yield self._bare_name_matches(nodes)
 838         else:
 839             # The reason for this is that hitting the recursion limit usually
 840             # results in some ugly messages about how RuntimeErrors are being
 841             # ignored. We only have to do this on CPython, though, because other
 842             # implementations don't have this nasty bug in the first place.
 843             if hasattr(sys, "getrefcount"):
 844                 save_stderr = sys.stderr
 845                 sys.stderr = StringIO()
 846             try:
 847                 for count, r in self._recursive_matches(nodes, 0):
 848                     if self.name:
 849                         r[self.name] = nodes[:count]
 850                     yield count, r
 851             except RuntimeError:
 852                 # We fall back to the iterative pattern matching scheme if the recursive
 853                 # scheme hits the recursion limit.
 854                 for count, r in self._iterative_matches(nodes):
 855                     if self.name:
 856                         r[self.name] = nodes[:count]
 857                     yield count, r
 858             finally:
 859                 if hasattr(sys, "getrefcount"):
 860                     sys.stderr = save_stderr
 861
 862     def _iterative_matches(self, nodes) -> Iterator[Tuple[int, _Results]]:
 863         """Helper to iteratively yield the matches."""
 864         nodelen = len(nodes)
 865         if 0 >= self.min:
 866             yield 0, {}
 867
 868         results = []
 869         # generate matches that use just one alt from self.content
 870         for alt in self.content:
 871             for c, r in generate_matches(alt, nodes):
 872                 yield c, r
 873                 results.append((c, r))
 874
 875         # for each match, iterate down the nodes
 876         while results:
 877             new_results = []
 878             for c0, r0 in results:
 879                 # stop if the entire set of nodes has been matched
 880                 if c0 < nodelen and c0 <= self.max:
 881                     for alt in self.content:
 882                         for c1, r1 in generate_matches(alt, nodes[c0:]):
 883                             if c1 > 0:
 884                                 r = {}
 885                                 r.update(r0)
 886                                 r.update(r1)
 887                                 yield c0 + c1, r
 888                                 new_results.append((c0 + c1, r))
 889             results = new_results
 890
 891     def _bare_name_matches(self, nodes) -> Tuple[int, _Results]:
 892         """Special optimized matcher for bare_name."""
 893         count = 0
 894         r = {}  # type: _Results
 895         done = False
 896         max = len(nodes)
 897         while not done and count < max:
 898             done = True
 899             for leaf in self.content:
 900                 if leaf[0].match(nodes[count], r):
 901                     count += 1
 902                     done = False
 903                     break
 904         assert self.name is not None
 905         r[self.name] = nodes[:count]
 906         return count, r
 907
 908     def _recursive_matches(self, nodes, count) -> Iterator[Tuple[int, _Results]]:
 909         """Helper to recursively yield the matches."""
 910         assert self.content is not None
 911         if count >= self.min:
 912             yield 0, {}
 913         if count < self.max:
 914             for alt in self.content:
 915                 for c0, r0 in generate_matches(alt, nodes):
 916                     for c1, r1 in self._recursive_matches(nodes[c0:], count + 1):
 917                         r = {}
 918                         r.update(r0)
 919                         r.update(r1)
 920                         yield c0 + c1, r
 921
 922
 923 class NegatedPattern(BasePattern):
 924     def __init__(self, content: Optional[Any] = None) -> None:
 925         """
 926         Initializer.
 927
 928         The argument is either a pattern or None.  If it is None, this
 929         only matches an empty sequence (effectively '$' in regex
 930         lingo).  If it is not None, this matches whenever the argument
 931         pattern doesn't have any matches.
 932         """
 933         if content is not None:
 934             assert isinstance(content, BasePattern), repr(content)
 935         self.content = content
 936
 937     def match(self, node, results=None) -> bool:
 938         # We never match a node in its entirety
 939         return False
 940
 941     def match_seq(self, nodes, results=None) -> bool:
 942         # We only match an empty sequence of nodes in its entirety
 943         return len(nodes) == 0
 944
 945     def generate_matches(self, nodes) -> Iterator[Tuple[int, _Results]]:
 946         if self.content is None:
 947             # Return a match if there is an empty sequence
 948             if len(nodes) == 0:
 949                 yield 0, {}
 950         else:
 951             # Return a match if the argument pattern has no matches
 952             for c, r in self.content.generate_matches(nodes):
 953                 return
 954             yield 0, {}
 955
 956
 957 def generate_matches(
 958     patterns: List[BasePattern], nodes: List[NL]
 959 ) -> Iterator[Tuple[int, _Results]]:
 960     """
 961     Generator yielding matches for a sequence of patterns and nodes.
 962
 963     Args:
 964         patterns: a sequence of patterns
 965         nodes: a sequence of nodes
 966
 967     Yields:
 968         (count, results) tuples where:
 969         count: the entire sequence of patterns matches nodes[:count];
 970         results: dict containing named submatches.
 971     """
 972     if not patterns:
 973         yield 0, {}
 974     else:
 975         p, rest = patterns[0], patterns[1:]
 976         for c0, r0 in p.generate_matches(nodes):
 977             if not rest:
 978                 yield c0, r0
 979             else:
 980                 for c1, r1 in generate_matches(rest, nodes[c0:]):
 981                     r = {}
 982                     r.update(r0)
 983                     r.update(r1)
 984                     yield c0 + c1, r