]> 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:

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