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