]> git.madduck.net Git - etc/vim.git/blob - src/blib2to3/pytree.py

madduck's git repository

Every one of the projects in this repository is available at the canonical URL git://git.madduck.net/madduck/pub/<projectpath> — see each project's metadata for the exact URL.

All patches and comments are welcome. Please squash your changes to logical commits before using git-format-patch and git-send-email to patches@git.madduck.net. If you'd read over the Git project's submission guidelines and adhered to them, I'd be especially grateful.

SSH access, as well as push access can be individually arranged.

If you use my repositories frequently, consider adding the following snippet to ~/.gitconfig and using the third clone URL listed for each project:

[url "git://git.madduck.net/madduck/"]
  insteadOf = madduck:

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