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