]> git.madduck.net Git - etc/vim.git/blob - 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:

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