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

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