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