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

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