google_appengine/lib/antlr3/antlr3/tree.py

   1 """ @package antlr3.tree
   2 @brief ANTLR3 runtime package, tree module
   3
   4 This module contains all support classes for AST construction and tree parsers.
   5
   6 """
   7
   8 # begin[licence]
   9 #
  10 # [The "BSD licence"]
  11 # Copyright (c) 2005-2008 Terence Parr
  12 # All rights reserved.
  13 #
  14 # Redistribution and use in source and binary forms, with or without
  15 # modification, are permitted provided that the following conditions
  16 # are met:
  17 # 1. Redistributions of source code must retain the above copyright
  18 #    notice, this list of conditions and the following disclaimer.
  19 # 2. Redistributions in binary form must reproduce the above copyright
  20 #    notice, this list of conditions and the following disclaimer in the
  21 #    documentation and/or other materials provided with the distribution.
  22 # 3. The name of the author may not be used to endorse or promote products
  23 #    derived from this software without specific prior written permission.
  24 #
  25 # THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  26 # IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  27 # OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  28 # IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  29 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  30 # NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  31 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  32 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  33 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  34 # THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  35 #
  36 # end[licence]
  37
  38 # lot's of docstrings are missing, don't complain for now...
  39 # pylint: disable-msg=C0111
  40
  41 from antlr3.constants import UP, DOWN, EOF, INVALID_TOKEN_TYPE
  42 from antlr3.recognizers import BaseRecognizer, RuleReturnScope
  43 from antlr3.streams import IntStream
  44 from antlr3.tokens import CommonToken, Token, INVALID_TOKEN
  45 from antlr3.exceptions import MismatchedTreeNodeException, \
  46      MissingTokenException, UnwantedTokenException, MismatchedTokenException, \
  47      NoViableAltException
  48
  49
  50 ############################################################################
  51 #
  52 # tree related exceptions
  53 #
  54 ############################################################################
  55
  56
  57 class RewriteCardinalityException(RuntimeError):
  58     """
  59     @brief Base class for all exceptions thrown during AST rewrite construction.
  60
  61     This signifies a case where the cardinality of two or more elements
  62     in a subrule are different: (ID INT)+ where |ID|!=|INT|
  63     """
  64
  65     def __init__(self, elementDescription):
  66         RuntimeError.__init__(self, elementDescription)
  67
  68         self.elementDescription = elementDescription
  69
  70
  71     def getMessage(self):
  72         return self.elementDescription
  73
  74
  75 class RewriteEarlyExitException(RewriteCardinalityException):
  76     """@brief No elements within a (...)+ in a rewrite rule"""
  77
  78     def __init__(self, elementDescription=None):
  79         RewriteCardinalityException.__init__(self, elementDescription)
  80
  81
  82 class RewriteEmptyStreamException(RewriteCardinalityException):
  83     """
  84     @brief Ref to ID or expr but no tokens in ID stream or subtrees in expr stream
  85     """
  86
  87     pass
  88
  89
  90 ############################################################################
  91 #
  92 # basic Tree and TreeAdaptor interfaces
  93 #
  94 ############################################################################
  95
  96 class Tree(object):
  97     """
  98     @brief Abstract baseclass for tree nodes.
  99
 100     What does a tree look like?  ANTLR has a number of support classes
 101     such as CommonTreeNodeStream that work on these kinds of trees.  You
 102     don't have to make your trees implement this interface, but if you do,
 103     you'll be able to use more support code.
 104
 105     NOTE: When constructing trees, ANTLR can build any kind of tree; it can
 106     even use Token objects as trees if you add a child list to your tokens.
 107
 108     This is a tree node without any payload; just navigation and factory stuff.
 109     """
 110
 111
 112     def getChild(self, i):
 113         raise NotImplementedError
 114
 115
 116     def getChildCount(self):
 117         raise NotImplementedError
 118
 119
 120     def getParent(self):
 121         """Tree tracks parent and child index now > 3.0"""
 122
 123         raise NotImplementedError
 124
 125     def setParent(self, t):
 126         """Tree tracks parent and child index now > 3.0"""
 127
 128         raise NotImplementedError
 129
 130
 131     def getChildIndex(self):
 132         """This node is what child index? 0..n-1"""
 133
 134         raise NotImplementedError
 135
 136     def setChildIndex(self, index):
 137         """This node is what child index? 0..n-1"""
 138
 139         raise NotImplementedError
 140
 141
 142     def freshenParentAndChildIndexes(self):
 143         """Set the parent and child index values for all children"""
 144
 145         raise NotImplementedError
 146
 147
 148     def addChild(self, t):
 149         """
 150         Add t as a child to this node.  If t is null, do nothing.  If t
 151         is nil, add all children of t to this' children.
 152         """
 153
 154         raise NotImplementedError
 155
 156
 157     def setChild(self, i, t):
 158         """Set ith child (0..n-1) to t; t must be non-null and non-nil node"""
 159
 160         raise NotImplementedError
 161
 162
 163     def deleteChild(self, i):
 164         raise NotImplementedError
 165
 166
 167     def replaceChildren(self, startChildIndex, stopChildIndex, t):
 168         """
 169         Delete children from start to stop and replace with t even if t is
 170         a list (nil-root tree).  num of children can increase or decrease.
 171         For huge child lists, inserting children can force walking rest of
 172         children to set their childindex; could be slow.
 173         """
 174
 175         raise NotImplementedError
 176
 177
 178     def isNil(self):
 179         """
 180         Indicates the node is a nil node but may still have children, meaning
 181         the tree is a flat list.
 182         """
 183
 184         raise NotImplementedError
 185
 186
 187     def getTokenStartIndex(self):
 188         """
 189         What is the smallest token index (indexing from 0) for this node
 190            and its children?
 191         """
 192
 193         raise NotImplementedError
 194
 195
 196     def setTokenStartIndex(self, index):
 197         raise NotImplementedError
 198
 199
 200     def getTokenStopIndex(self):
 201         """
 202         What is the largest token index (indexing from 0) for this node
 203         and its children?
 204         """
 205
 206         raise NotImplementedError
 207
 208
 209     def setTokenStopIndex(self, index):
 210         raise NotImplementedError
 211
 212
 213     def dupNode(self):
 214         raise NotImplementedError
 215
 216
 217     def getType(self):
 218         """Return a token type; needed for tree parsing."""
 219
 220         raise NotImplementedError
 221
 222
 223     def getText(self):
 224         raise NotImplementedError
 225
 226
 227     def getLine(self):
 228         """
 229         In case we don't have a token payload, what is the line for errors?
 230         """
 231
 232         raise NotImplementedError
 233
 234
 235     def getCharPositionInLine(self):
 236         raise NotImplementedError
 237
 238
 239     def toStringTree(self):
 240         raise NotImplementedError
 241
 242
 243     def toString(self):
 244         raise NotImplementedError
 245
 246
 247
 248 class TreeAdaptor(object):
 249     """
 250     @brief Abstract baseclass for tree adaptors.
 251
 252     How to create and navigate trees.  Rather than have a separate factory
 253     and adaptor, I've merged them.  Makes sense to encapsulate.
 254
 255     This takes the place of the tree construction code generated in the
 256     generated code in 2.x and the ASTFactory.
 257
 258     I do not need to know the type of a tree at all so they are all
 259     generic Objects.  This may increase the amount of typecasting needed. :(
 260     """
 261
 262     # C o n s t r u c t i o n
 263
 264     def createWithPayload(self, payload):
 265         """
 266         Create a tree node from Token object; for CommonTree type trees,
 267         then the token just becomes the payload.  This is the most
 268         common create call.
 269
 270         Override if you want another kind of node to be built.
 271         """
 272
 273         raise NotImplementedError
 274
 275
 276     def dupNode(self, treeNode):
 277         """Duplicate a single tree node.
 278
 279         Override if you want another kind of node to be built."""
 280
 281         raise NotImplementedError
 282
 283
 284     def dupTree(self, tree):
 285         """Duplicate tree recursively, using dupNode() for each node"""
 286
 287         raise NotImplementedError
 288
 289
 290     def nil(self):
 291         """
 292         Return a nil node (an empty but non-null node) that can hold
 293         a list of element as the children.  If you want a flat tree (a list)
 294         use "t=adaptor.nil(); t.addChild(x); t.addChild(y);"
 295         """
 296
 297         raise NotImplementedError
 298
 299
 300     def errorNode(self, input, start, stop, exc):
 301         """
 302         Return a tree node representing an error.  This node records the
 303         tokens consumed during error recovery.  The start token indicates the
 304         input symbol at which the error was detected.  The stop token indicates
 305         the last symbol consumed during recovery.
 306
 307         You must specify the input stream so that the erroneous text can
 308         be packaged up in the error node.  The exception could be useful
 309         to some applications; default implementation stores ptr to it in
 310         the CommonErrorNode.
 311
 312         This only makes sense during token parsing, not tree parsing.
 313         Tree parsing should happen only when parsing and tree construction
 314         succeed.
 315         """
 316
 317         raise NotImplementedError
 318
 319
 320     def isNil(self, tree):
 321         """Is tree considered a nil node used to make lists of child nodes?"""
 322
 323         raise NotImplementedError
 324
 325
 326     def addChild(self, t, child):
 327         """
 328         Add a child to the tree t.  If child is a flat tree (a list), make all
 329         in list children of t.  Warning: if t has no children, but child does
 330         and child isNil then you can decide it is ok to move children to t via
 331         t.children = child.children; i.e., without copying the array.  Just
 332         make sure that this is consistent with have the user will build
 333         ASTs. Do nothing if t or child is null.
 334         """
 335
 336         raise NotImplementedError
 337
 338
 339     def becomeRoot(self, newRoot, oldRoot):
 340         """
 341         If oldRoot is a nil root, just copy or move the children to newRoot.
 342         If not a nil root, make oldRoot a child of newRoot.
 343
 344            old=^(nil a b c), new=r yields ^(r a b c)
 345            old=^(a b c), new=r yields ^(r ^(a b c))
 346
 347         If newRoot is a nil-rooted single child tree, use the single
 348         child as the new root node.
 349
 350            old=^(nil a b c), new=^(nil r) yields ^(r a b c)
 351            old=^(a b c), new=^(nil r) yields ^(r ^(a b c))
 352
 353         If oldRoot was null, it's ok, just return newRoot (even if isNil).
 354
 355            old=null, new=r yields r
 356            old=null, new=^(nil r) yields ^(nil r)
 357
 358         Return newRoot.  Throw an exception if newRoot is not a
 359         simple node or nil root with a single child node--it must be a root
 360         node.  If newRoot is ^(nil x) return x as newRoot.
 361
 362         Be advised that it's ok for newRoot to point at oldRoot's
 363         children; i.e., you don't have to copy the list.  We are
 364         constructing these nodes so we should have this control for
 365         efficiency.
 366         """
 367
 368         raise NotImplementedError
 369
 370
 371     def rulePostProcessing(self, root):
 372         """
 373         Given the root of the subtree created for this rule, post process
 374         it to do any simplifications or whatever you want.  A required
 375         behavior is to convert ^(nil singleSubtree) to singleSubtree
 376         as the setting of start/stop indexes relies on a single non-nil root
 377         for non-flat trees.
 378
 379         Flat trees such as for lists like "idlist : ID+ ;" are left alone
 380         unless there is only one ID.  For a list, the start/stop indexes
 381         are set in the nil node.
 382
 383         This method is executed after all rule tree construction and right
 384         before setTokenBoundaries().
 385         """
 386
 387         raise NotImplementedError
 388
 389
 390     def getUniqueID(self, node):
 391         """For identifying trees.
 392
 393         How to identify nodes so we can say "add node to a prior node"?
 394         Even becomeRoot is an issue.  Use System.identityHashCode(node)
 395         usually.
 396         """
 397
 398         raise NotImplementedError
 399
 400
 401     # R e w r i t e  R u l e s
 402
 403     def createFromToken(self, tokenType, fromToken, text=None):
 404         """
 405         Create a new node derived from a token, with a new token type and
 406         (optionally) new text.
 407
 408         This is invoked from an imaginary node ref on right side of a
 409         rewrite rule as IMAG[$tokenLabel] or IMAG[$tokenLabel "IMAG"].
 410
 411         This should invoke createToken(Token).
 412         """
 413
 414         raise NotImplementedError
 415
 416
 417     def createFromType(self, tokenType, text):
 418         """Create a new node derived from a token, with a new token type.
 419
 420         This is invoked from an imaginary node ref on right side of a
 421         rewrite rule as IMAG["IMAG"].
 422
 423         This should invoke createToken(int,String).
 424         """
 425
 426         raise NotImplementedError
 427
 428
 429     # C o n t e n t
 430
 431     def getType(self, t):
 432         """For tree parsing, I need to know the token type of a node"""
 433
 434         raise NotImplementedError
 435
 436
 437     def setType(self, t, type):
 438         """Node constructors can set the type of a node"""
 439
 440         raise NotImplementedError
 441
 442
 443     def getText(self, t):
 444         raise NotImplementedError
 445
 446     def setText(self, t, text):
 447         """Node constructors can set the text of a node"""
 448
 449         raise NotImplementedError
 450
 451
 452     def getToken(self, t):
 453         """Return the token object from which this node was created.
 454
 455         Currently used only for printing an error message.
 456         The error display routine in BaseRecognizer needs to
 457         display where the input the error occurred. If your
 458         tree of limitation does not store information that can
 459         lead you to the token, you can create a token filled with
 460         the appropriate information and pass that back.  See
 461         BaseRecognizer.getErrorMessage().
 462         """
 463
 464         raise NotImplementedError
 465
 466
 467     def setTokenBoundaries(self, t, startToken, stopToken):
 468         """
 469         Where are the bounds in the input token stream for this node and
 470         all children?  Each rule that creates AST nodes will call this
 471         method right before returning.  Flat trees (i.e., lists) will
 472         still usually have a nil root node just to hold the children list.
 473         That node would contain the start/stop indexes then.
 474         """
 475
 476         raise NotImplementedError
 477
 478
 479     def getTokenStartIndex(self, t):
 480         """
 481         Get the token start index for this subtree; return -1 if no such index
 482         """
 483
 484         raise NotImplementedError
 485
 486
 487     def getTokenStopIndex(self, t):
 488         """
 489         Get the token stop index for this subtree; return -1 if no such index
 490         """
 491
 492         raise NotImplementedError
 493
 494
 495     # N a v i g a t i o n  /  T r e e  P a r s i n g
 496
 497     def getChild(self, t, i):
 498         """Get a child 0..n-1 node"""
 499
 500         raise NotImplementedError
 501
 502
 503     def setChild(self, t, i, child):
 504         """Set ith child (0..n-1) to t; t must be non-null and non-nil node"""
 505
 506         raise NotImplementedError
 507
 508
 509     def deleteChild(self, t, i):
 510         """Remove ith child and shift children down from right."""
 511
 512         raise NotImplementedError
 513
 514
 515     def getChildCount(self, t):
 516         """How many children?  If 0, then this is a leaf node"""
 517
 518         raise NotImplementedError
 519
 520
 521     def getParent(self, t):
 522         """
 523         Who is the parent node of this node; if null, implies node is root.
 524         If your node type doesn't handle this, it's ok but the tree rewrites
 525         in tree parsers need this functionality.
 526         """
 527
 528         raise NotImplementedError
 529
 530
 531     def setParent(self, t, parent):
 532         """
 533         Who is the parent node of this node; if null, implies node is root.
 534         If your node type doesn't handle this, it's ok but the tree rewrites
 535         in tree parsers need this functionality.
 536         """
 537
 538         raise NotImplementedError
 539
 540
 541     def getChildIndex(self, t):
 542         """
 543         What index is this node in the child list? Range: 0..n-1
 544         If your node type doesn't handle this, it's ok but the tree rewrites
 545         in tree parsers need this functionality.
 546         """
 547
 548         raise NotImplementedError
 549
 550
 551     def setChildIndex(self, t, index):
 552         """
 553         What index is this node in the child list? Range: 0..n-1
 554         If your node type doesn't handle this, it's ok but the tree rewrites
 555         in tree parsers need this functionality.
 556         """
 557
 558         raise NotImplementedError
 559
 560
 561     def replaceChildren(self, parent, startChildIndex, stopChildIndex, t):
 562         """
 563         Replace from start to stop child index of parent with t, which might
 564         be a list.  Number of children may be different
 565         after this call.
 566
 567         If parent is null, don't do anything; must be at root of overall tree.
 568         Can't replace whatever points to the parent externally.  Do nothing.
 569         """
 570
 571         raise NotImplementedError
 572
 573
 574     # Misc
 575
 576     def create(self, *args):
 577         """
 578         Deprecated, use createWithPayload, createFromToken or createFromType.
 579
 580         This method only exists to mimic the Java interface of TreeAdaptor.
 581
 582         """
 583
 584         if len(args) == 1 and isinstance(args[0], Token):
 585             # Object create(Token payload);
 586 ##             warnings.warn(
 587 ##                 "Using create() is deprecated, use createWithPayload()",
 588 ##                 DeprecationWarning,
 589 ##                 stacklevel=2
 590 ##                 )
 591             return self.createWithPayload(args[0])
 592
 593         if (len(args) == 2
 594             and isinstance(args[0], (int, long))
 595             and isinstance(args[1], Token)
 596             ):
 597             # Object create(int tokenType, Token fromToken);
 598 ##             warnings.warn(
 599 ##                 "Using create() is deprecated, use createFromToken()",
 600 ##                 DeprecationWarning,
 601 ##                 stacklevel=2
 602 ##                 )
 603             return self.createFromToken(args[0], args[1])
 604
 605         if (len(args) == 3
 606             and isinstance(args[0], (int, long))
 607             and isinstance(args[1], Token)
 608             and isinstance(args[2], basestring)
 609             ):
 610             # Object create(int tokenType, Token fromToken, String text);
 611 ##             warnings.warn(
 612 ##                 "Using create() is deprecated, use createFromToken()",
 613 ##                 DeprecationWarning,
 614 ##                 stacklevel=2
 615 ##                 )
 616             return self.createFromToken(args[0], args[1], args[2])
 617
 618         if (len(args) == 2
 619             and isinstance(args[0], (int, long))
 620             and isinstance(args[1], basestring)
 621             ):
 622             # Object create(int tokenType, String text);
 623 ##             warnings.warn(
 624 ##                 "Using create() is deprecated, use createFromType()",
 625 ##                 DeprecationWarning,
 626 ##                 stacklevel=2
 627 ##                 )
 628             return self.createFromType(args[0], args[1])
 629
 630         raise TypeError(
 631             "No create method with this signature found: %s"
 632             % (', '.join(type(v).__name__ for v in args))
 633             )
 634
 635
 636 ############################################################################
 637 #
 638 # base implementation of Tree and TreeAdaptor
 639 #
 640 # Tree
 641 # \- BaseTree
 642 #
 643 # TreeAdaptor
 644 # \- BaseTreeAdaptor
 645 #
 646 ############################################################################
 647
 648
 649 class BaseTree(Tree):
 650     """
 651     @brief A generic tree implementation with no payload.
 652
 653     You must subclass to
 654     actually have any user data.  ANTLR v3 uses a list of children approach
 655     instead of the child-sibling approach in v2.  A flat tree (a list) is
 656     an empty node whose children represent the list.  An empty, but
 657     non-null node is called "nil".
 658     """
 659
 660     # BaseTree is abstract, no need to complain about not implemented abstract
 661     # methods
 662     # pylint: disable-msg=W0223
 663
 664     def __init__(self, node=None):
 665         """
 666         Create a new node from an existing node does nothing for BaseTree
 667         as there are no fields other than the children list, which cannot
 668         be copied as the children are not considered part of this node.
 669         """
 670
 671         Tree.__init__(self)
 672         self.children = []
 673         self.parent = None
 674         self.childIndex = 0
 675
 676
 677     def getChild(self, i):
 678         try:
 679             return self.children[i]
 680         except IndexError:
 681             return None
 682
 683
 684     def getChildren(self):
 685         """@brief Get the children internal List
 686
 687         Note that if you directly mess with
 688         the list, do so at your own risk.
 689         """
 690
 691         # FIXME: mark as deprecated
 692         return self.children
 693
 694
 695     def getFirstChildWithType(self, treeType):
 696         for child in self.children:
 697             if child.getType() == treeType:
 698                 return child
 699
 700         return None
 701
 702
 703     def getChildCount(self):
 704         return len(self.children)
 705
 706
 707     def addChild(self, childTree):
 708         """Add t as child of this node.
 709
 710         Warning: if t has no children, but child does
 711         and child isNil then this routine moves children to t via
 712         t.children = child.children; i.e., without copying the array.
 713         """
 714
 715         # this implementation is much simpler and probably less efficient
 716         # than the mumbo-jumbo that Ter did for the Java runtime.
 717
 718         if childTree is None:
 719             return
 720
 721         if childTree.isNil():
 722             # t is an empty node possibly with children
 723
 724             if self.children is childTree.children:
 725                 raise ValueError("attempt to add child list to itself")
 726
 727             # fix parent pointer and childIndex for new children
 728             for idx, child in enumerate(childTree.children):
 729                 child.parent = self
 730                 child.childIndex = len(self.children) + idx
 731
 732             self.children += childTree.children
 733
 734         else:
 735             # child is not nil (don't care about children)
 736             self.children.append(childTree)
 737             childTree.parent = self
 738             childTree.childIndex = len(self.children) - 1
 739
 740
 741     def addChildren(self, children):
 742         """Add all elements of kids list as children of this node"""
 743
 744         self.children += children
 745
 746
 747     def setChild(self, i, t):
 748         if t is None:
 749             return
 750
 751         if t.isNil():
 752             raise ValueError("Can't set single child to a list")
 753
 754         self.children[i] = t
 755         t.parent = self
 756         t.childIndex = i
 757
 758
 759     def deleteChild(self, i):
 760         killed = self.children[i]
 761
 762         del self.children[i]
 763
 764         # walk rest and decrement their child indexes
 765         for idx, child in enumerate(self.children[i:]):
 766             child.childIndex = i + idx
 767
 768         return killed
 769
 770
 771     def replaceChildren(self, startChildIndex, stopChildIndex, newTree):
 772         """
 773         Delete children from start to stop and replace with t even if t is
 774         a list (nil-root tree).  num of children can increase or decrease.
 775         For huge child lists, inserting children can force walking rest of
 776         children to set their childindex; could be slow.
 777         """
 778
 779         if (startChildIndex >= len(self.children)
 780             or stopChildIndex >= len(self.children)
 781             ):
 782             raise IndexError("indexes invalid")
 783
 784         replacingHowMany = stopChildIndex - startChildIndex + 1
 785
 786         # normalize to a list of children to add: newChildren
 787         if newTree.isNil():
 788             newChildren = newTree.children
 789
 790         else:
 791             newChildren = [newTree]
 792
 793         replacingWithHowMany = len(newChildren)
 794         delta = replacingHowMany - replacingWithHowMany
 795
 796
 797         if delta == 0:
 798             # if same number of nodes, do direct replace
 799             for idx, child in enumerate(newChildren):
 800                 self.children[idx + startChildIndex] = child
 801                 child.parent = self
 802                 child.childIndex = idx + startChildIndex
 803
 804         else:
 805             # length of children changes...
 806
 807             # ...delete replaced segment...
 808             del self.children[startChildIndex:stopChildIndex+1]
 809
 810             # ...insert new segment...
 811             self.children[startChildIndex:startChildIndex] = newChildren
 812
 813             # ...and fix indeces
 814             self.freshenParentAndChildIndexes(startChildIndex)
 815
 816
 817     def isNil(self):
 818         return False
 819
 820
 821     def freshenParentAndChildIndexes(self, offset=0):
 822         for idx, child in enumerate(self.children[offset:]):
 823             child.childIndex = idx + offset
 824             child.parent = self
 825
 826
 827     def sanityCheckParentAndChildIndexes(self, parent=None, i=-1):
 828         if parent != self.parent:
 829             raise ValueError(
 830                 "parents don't match; expected %r found %r"
 831                 % (parent, self.parent)
 832                 )
 833
 834         if i != self.childIndex:
 835             raise ValueError(
 836                 "child indexes don't match; expected %d found %d"
 837                 % (i, self.childIndex)
 838                 )
 839
 840         for idx, child in enumerate(self.children):
 841             child.sanityCheckParentAndChildIndexes(self, idx)
 842
 843
 844     def getChildIndex(self):
 845         """BaseTree doesn't track child indexes."""
 846
 847         return 0
 848
 849
 850     def setChildIndex(self, index):
 851         """BaseTree doesn't track child indexes."""
 852
 853         pass
 854
 855
 856     def getParent(self):
 857         """BaseTree doesn't track parent pointers."""
 858
 859         return None
 860
 861     def setParent(self, t):
 862         """BaseTree doesn't track parent pointers."""
 863
 864         pass
 865
 866
 867     def toStringTree(self):
 868         """Print out a whole tree not just a node"""
 869
 870         if len(self.children) == 0:
 871             return self.toString()
 872
 873         buf = []
 874         if not self.isNil():
 875             buf.append('(')
 876             buf.append(self.toString())
 877             buf.append(' ')
 878
 879         for i, child in enumerate(self.children):
 880             if i > 0:
 881                 buf.append(' ')
 882             buf.append(child.toStringTree())
 883
 884         if not self.isNil():
 885             buf.append(')')
 886
 887         return ''.join(buf)
 888
 889
 890     def getLine(self):
 891         return 0
 892
 893
 894     def getCharPositionInLine(self):
 895         return 0
 896
 897
 898     def toString(self):
 899         """Override to say how a node (not a tree) should look as text"""
 900
 901         raise NotImplementedError
 902
 903
 904
 905 class BaseTreeAdaptor(TreeAdaptor):
 906     """
 907     @brief A TreeAdaptor that works with any Tree implementation.
 908     """
 909
 910     # BaseTreeAdaptor is abstract, no need to complain about not implemented
 911     # abstract methods
 912     # pylint: disable-msg=W0223
 913
 914     def nil(self):
 915         return self.createWithPayload(None)
 916
 917
 918     def errorNode(self, input, start, stop, exc):
 919         """
 920         create tree node that holds the start and stop tokens associated
 921         with an error.
 922
 923         If you specify your own kind of tree nodes, you will likely have to
 924         override this method. CommonTree returns Token.INVALID_TOKEN_TYPE
 925         if no token payload but you might have to set token type for diff
 926         node type.
 927         """
 928
 929         return CommonErrorNode(input, start, stop, exc)
 930
 931
 932     def isNil(self, tree):
 933         return tree.isNil()
 934
 935
 936     def dupTree(self, t, parent=None):
 937         """
 938         This is generic in the sense that it will work with any kind of
 939         tree (not just Tree interface).  It invokes the adaptor routines
 940         not the tree node routines to do the construction.
 941         """
 942
 943         if t is None:
 944             return None
 945
 946         newTree = self.dupNode(t)
 947
 948         # ensure new subtree root has parent/child index set
 949
 950         # same index in new tree
 951         self.setChildIndex(newTree, self.getChildIndex(t))
 952
 953         self.setParent(newTree, parent)
 954
 955         for i in range(self.getChildCount(t)):
 956             child = self.getChild(t, i)
 957             newSubTree = self.dupTree(child, t)
 958             self.addChild(newTree, newSubTree)
 959
 960         return newTree
 961
 962
 963     def addChild(self, tree, child):
 964         """
 965         Add a child to the tree t.  If child is a flat tree (a list), make all
 966         in list children of t.  Warning: if t has no children, but child does
 967         and child isNil then you can decide it is ok to move children to t via
 968         t.children = child.children; i.e., without copying the array.  Just
 969         make sure that this is consistent with have the user will build
 970         ASTs.
 971         """
 972
 973         #if isinstance(child, Token):
 974         #    child = self.createWithPayload(child)
 975
 976         if tree is not None and child is not None:
 977             tree.addChild(child)
 978
 979
 980     def becomeRoot(self, newRoot, oldRoot):
 981         """
 982         If oldRoot is a nil root, just copy or move the children to newRoot.
 983         If not a nil root, make oldRoot a child of newRoot.
 984
 985           old=^(nil a b c), new=r yields ^(r a b c)
 986           old=^(a b c), new=r yields ^(r ^(a b c))
 987
 988         If newRoot is a nil-rooted single child tree, use the single
 989         child as the new root node.
 990
 991           old=^(nil a b c), new=^(nil r) yields ^(r a b c)
 992           old=^(a b c), new=^(nil r) yields ^(r ^(a b c))
 993
 994         If oldRoot was null, it's ok, just return newRoot (even if isNil).
 995
 996           old=null, new=r yields r
 997           old=null, new=^(nil r) yields ^(nil r)
 998
 999         Return newRoot.  Throw an exception if newRoot is not a
1000         simple node or nil root with a single child node--it must be a root
1001         node.  If newRoot is ^(nil x) return x as newRoot.
1002
1003         Be advised that it's ok for newRoot to point at oldRoot's
1004         children; i.e., you don't have to copy the list.  We are
1005         constructing these nodes so we should have this control for
1006         efficiency.
1007         """
1008
1009         if isinstance(newRoot, Token):
1010             newRoot = self.create(newRoot)
1011
1012         if oldRoot is None:
1013             return newRoot
1014
1015         if not isinstance(newRoot, CommonTree):
1016             newRoot = self.createWithPayload(newRoot)
1017
1018         # handle ^(nil real-node)
1019         if newRoot.isNil():
1020             nc = newRoot.getChildCount()
1021             if nc == 1:
1022                 newRoot = newRoot.getChild(0)
1023
1024             elif nc > 1:
1025                 # TODO: make tree run time exceptions hierarchy
1026                 raise RuntimeError("more than one node as root")
1027
1028         # add oldRoot to newRoot; addChild takes care of case where oldRoot
1029         # is a flat list (i.e., nil-rooted tree).  All children of oldRoot
1030         # are added to newRoot.
1031         newRoot.addChild(oldRoot)
1032         return newRoot
1033
1034
1035     def rulePostProcessing(self, root):
1036         """Transform ^(nil x) to x and nil to null"""
1037
1038         if root is not None and root.isNil():
1039             if root.getChildCount() == 0:
1040                 root = None
1041
1042             elif root.getChildCount() == 1:
1043                 root = root.getChild(0)
1044                 # whoever invokes rule will set parent and child index
1045                 root.setParent(None)
1046                 root.setChildIndex(-1)
1047
1048         return root
1049
1050
1051     def createFromToken(self, tokenType, fromToken, text=None):
1052         assert isinstance(tokenType, (int, long)), type(tokenType).__name__
1053         assert isinstance(fromToken, Token), type(fromToken).__name__
1054         assert text is None or isinstance(text, basestring), type(text).__name__
1055
1056         fromToken = self.createToken(fromToken)
1057         fromToken.type = tokenType
1058         if text is not None:
1059             fromToken.text = text
1060         t = self.createWithPayload(fromToken)
1061         return t
1062
1063
1064     def createFromType(self, tokenType, text):
1065         assert isinstance(tokenType, (int, long)), type(tokenType).__name__
1066         assert isinstance(text, basestring), type(text).__name__
1067
1068         fromToken = self.createToken(tokenType=tokenType, text=text)
1069         t = self.createWithPayload(fromToken)
1070         return t
1071
1072
1073     def getType(self, t):
1074         return t.getType()
1075
1076
1077     def setType(self, t, type):
1078         raise RuntimeError("don't know enough about Tree node")
1079
1080
1081     def getText(self, t):
1082         return t.getText()
1083
1084
1085     def setText(self, t, text):
1086         raise RuntimeError("don't know enough about Tree node")
1087
1088
1089     def getChild(self, t, i):
1090         return t.getChild(i)
1091
1092
1093     def setChild(self, t, i, child):
1094         t.setChild(i, child)
1095
1096
1097     def deleteChild(self, t, i):
1098         return t.deleteChild(i)
1099
1100
1101     def getChildCount(self, t):
1102         return t.getChildCount()
1103
1104
1105     def getUniqueID(self, node):
1106         return hash(node)
1107
1108
1109     def createToken(self, fromToken=None, tokenType=None, text=None):
1110         """
1111         Tell me how to create a token for use with imaginary token nodes.
1112         For example, there is probably no input symbol associated with imaginary
1113         token DECL, but you need to create it as a payload or whatever for
1114         the DECL node as in ^(DECL type ID).
1115
1116         If you care what the token payload objects' type is, you should
1117         override this method and any other createToken variant.
1118         """
1119
1120         raise NotImplementedError
1121
1122
1123 ############################################################################
1124 #
1125 # common tree implementation
1126 #
1127 # Tree
1128 # \- BaseTree
1129 #    \- CommonTree
1130 #       \- CommonErrorNode
1131 #
1132 # TreeAdaptor
1133 # \- BaseTreeAdaptor
1134 #    \- CommonTreeAdaptor
1135 #
1136 ############################################################################
1137
1138
1139 class CommonTree(BaseTree):
1140     """@brief A tree node that is wrapper for a Token object.
1141
1142     After 3.0 release
1143     while building tree rewrite stuff, it became clear that computing
1144     parent and child index is very difficult and cumbersome.  Better to
1145     spend the space in every tree node.  If you don't want these extra
1146     fields, it's easy to cut them out in your own BaseTree subclass.
1147
1148     """
1149
1150     def __init__(self, payload):
1151         BaseTree.__init__(self)
1152
1153         # What token indexes bracket all tokens associated with this node
1154         # and below?
1155         self.startIndex = -1
1156         self.stopIndex = -1
1157
1158         # Who is the parent node of this node; if null, implies node is root
1159         self.parent = None
1160
1161         # What index is this node in the child list? Range: 0..n-1
1162         self.childIndex = -1
1163
1164         # A single token is the payload
1165         if payload is None:
1166             self.token = None
1167
1168         elif isinstance(payload, CommonTree):
1169             self.token = payload.token
1170             self.startIndex = payload.startIndex
1171             self.stopIndex = payload.stopIndex
1172
1173         elif payload is None or isinstance(payload, Token):
1174             self.token = payload
1175
1176         else:
1177             raise TypeError(type(payload).__name__)
1178
1179
1180
1181     def getToken(self):
1182         return self.token
1183
1184
1185     def dupNode(self):
1186         return CommonTree(self)
1187
1188
1189     def isNil(self):
1190         return self.token is None
1191
1192
1193     def getType(self):
1194         if self.token is None:
1195             return INVALID_TOKEN_TYPE
1196
1197         return self.token.getType()
1198
1199     type = property(getType)
1200
1201
1202     def getText(self):
1203         if self.token is None:
1204             return None
1205
1206         return self.token.text
1207
1208     text = property(getText)
1209
1210
1211     def getLine(self):
1212         if self.token is None or self.token.getLine() == 0:
1213             if self.getChildCount():
1214                 return self.getChild(0).getLine()
1215             else:
1216                 return 0
1217
1218         return self.token.getLine()
1219
1220     line = property(getLine)
1221
1222
1223     def getCharPositionInLine(self):
1224         if self.token is None or self.token.getCharPositionInLine() == -1:
1225             if self.getChildCount():
1226                 return self.getChild(0).getCharPositionInLine()
1227             else:
1228                 return 0
1229
1230         else:
1231             return self.token.getCharPositionInLine()
1232
1233     charPositionInLine = property(getCharPositionInLine)
1234
1235
1236     def getTokenStartIndex(self):
1237         if self.startIndex == -1 and self.token is not None:
1238             return self.token.getTokenIndex()
1239
1240         return self.startIndex
1241
1242     def setTokenStartIndex(self, index):
1243         self.startIndex = index
1244
1245     tokenStartIndex = property(getTokenStartIndex, setTokenStartIndex)
1246
1247
1248     def getTokenStopIndex(self):
1249         if self.stopIndex == -1 and self.token is not None:
1250             return self.token.getTokenIndex()
1251
1252         return self.stopIndex
1253
1254     def setTokenStopIndex(self, index):
1255         self.stopIndex = index
1256
1257     tokenStopIndex = property(getTokenStopIndex, setTokenStopIndex)
1258
1259
1260     def getChildIndex(self):
1261         #FIXME: mark as deprecated
1262         return self.childIndex
1263
1264
1265     def setChildIndex(self, idx):
1266         #FIXME: mark as deprecated
1267         self.childIndex = idx
1268
1269
1270     def getParent(self):
1271         #FIXME: mark as deprecated
1272         return self.parent
1273
1274
1275     def setParent(self, t):
1276         #FIXME: mark as deprecated
1277         self.parent = t
1278
1279
1280     def toString(self):
1281         if self.isNil():
1282             return "nil"
1283
1284         if self.getType() == INVALID_TOKEN_TYPE:
1285             return "<errornode>"
1286
1287         return self.token.text
1288
1289     __str__ = toString
1290
1291
1292
1293     def toStringTree(self):
1294         if not self.children:
1295             return self.toString()
1296
1297         ret = ''
1298         if not self.isNil():
1299             ret += '(%s ' % (self.toString())
1300
1301         ret += ' '.join([child.toStringTree() for child in self.children])
1302
1303         if not self.isNil():
1304             ret += ')'
1305
1306         return ret
1307
1308
1309 INVALID_NODE = CommonTree(INVALID_TOKEN)
1310
1311
1312 class CommonErrorNode(CommonTree):
1313     """A node representing erroneous token range in token stream"""
1314
1315     def __init__(self, input, start, stop, exc):
1316         CommonTree.__init__(self, None)
1317
1318         if (stop is None or
1319             (stop.getTokenIndex() < start.getTokenIndex() and
1320              stop.getType() != EOF
1321              )
1322             ):
1323             # sometimes resync does not consume a token (when LT(1) is
1324             # in follow set.  So, stop will be 1 to left to start. adjust.
1325             # Also handle case where start is the first token and no token
1326             # is consumed during recovery; LT(-1) will return null.
1327             stop = start
1328
1329         self.input = input
1330         self.start = start
1331         self.stop = stop
1332         self.trappedException = exc
1333
1334
1335     def isNil(self):
1336         return False
1337
1338
1339     def getType(self):
1340         return INVALID_TOKEN_TYPE
1341
1342
1343     def getText(self):
1344         if isinstance(self.start, Token):
1345             i = self.start.getTokenIndex()
1346             j = self.stop.getTokenIndex()
1347             if self.stop.getType() == EOF:
1348                 j = self.input.size()
1349
1350             badText = self.input.toString(i, j)
1351
1352         elif isinstance(self.start, Tree):
1353             badText = self.input.toString(self.start, self.stop)
1354
1355         else:
1356             # people should subclass if they alter the tree type so this
1357             # next one is for sure correct.
1358             badText = "<unknown>"
1359
1360         return badText
1361
1362
1363     def toString(self):
1364         if isinstance(self.trappedException, MissingTokenException):
1365             return ("<missing type: "
1366                     + str(self.trappedException.getMissingType())
1367                     + ">")
1368
1369         elif isinstance(self.trappedException, UnwantedTokenException):
1370             return ("<extraneous: "
1371                     + str(self.trappedException.getUnexpectedToken())
1372                     + ", resync=" + self.getText() + ">")
1373
1374         elif isinstance(self.trappedException, MismatchedTokenException):
1375             return ("<mismatched token: "
1376                     + str(self.trappedException.token)
1377                     + ", resync=" + self.getText() + ">")
1378
1379         elif isinstance(self.trappedException, NoViableAltException):
1380             return ("<unexpected: "
1381                     + str(self.trappedException.token)
1382                     + ", resync=" + self.getText() + ">")
1383
1384         return "<error: "+self.getText()+">"
1385
1386
1387 class CommonTreeAdaptor(BaseTreeAdaptor):
1388     """
1389     @brief A TreeAdaptor that works with any Tree implementation.
1390
1391     It provides
1392     really just factory methods; all the work is done by BaseTreeAdaptor.
1393     If you would like to have different tokens created than ClassicToken
1394     objects, you need to override this and then set the parser tree adaptor to
1395     use your subclass.
1396
1397     To get your parser to build nodes of a different type, override
1398     create(Token).
1399     """
1400
1401     def dupNode(self, treeNode):
1402         """
1403         Duplicate a node.  This is part of the factory;
1404         override if you want another kind of node to be built.
1405
1406         I could use reflection to prevent having to override this
1407         but reflection is slow.
1408         """
1409
1410         if treeNode is None:
1411             return None
1412
1413         return treeNode.dupNode()
1414
1415
1416     def createWithPayload(self, payload):
1417         return CommonTree(payload)
1418
1419
1420     def createToken(self, fromToken=None, tokenType=None, text=None):
1421         """
1422         Tell me how to create a token for use with imaginary token nodes.
1423         For example, there is probably no input symbol associated with imaginary
1424         token DECL, but you need to create it as a payload or whatever for
1425         the DECL node as in ^(DECL type ID).
1426
1427         If you care what the token payload objects' type is, you should
1428         override this method and any other createToken variant.
1429         """
1430
1431         if fromToken is not None:
1432             return CommonToken(oldToken=fromToken)
1433
1434         return CommonToken(type=tokenType, text=text)
1435
1436
1437     def setTokenBoundaries(self, t, startToken, stopToken):
1438         """
1439         Track start/stop token for subtree root created for a rule.
1440         Only works with Tree nodes.  For rules that match nothing,
1441         seems like this will yield start=i and stop=i-1 in a nil node.
1442         Might be useful info so I'll not force to be i..i.
1443         """
1444
1445         if t is None:
1446             return
1447
1448         start = 0
1449         stop = 0
1450
1451         if startToken is not None:
1452             start = startToken.index
1453
1454         if stopToken is not None:
1455             stop = stopToken.index
1456
1457         t.setTokenStartIndex(start)
1458         t.setTokenStopIndex(stop)
1459
1460
1461     def getTokenStartIndex(self, t):
1462         if t is None:
1463             return -1
1464         return t.getTokenStartIndex()
1465
1466
1467     def getTokenStopIndex(self, t):
1468         if t is None:
1469             return -1
1470         return t.getTokenStopIndex()
1471
1472
1473     def getText(self, t):
1474         if t is None:
1475             return None
1476         return t.getText()
1477
1478
1479     def getType(self, t):
1480         if t is None:
1481             return INVALID_TOKEN_TYPE
1482
1483         return t.getType()
1484
1485
1486     def getToken(self, t):
1487         """
1488         What is the Token associated with this node?  If
1489         you are not using CommonTree, then you must
1490         override this in your own adaptor.
1491         """
1492
1493         if isinstance(t, CommonTree):
1494             return t.getToken()
1495
1496         return None # no idea what to do
1497
1498
1499     def getChild(self, t, i):
1500         if t is None:
1501             return None
1502         return t.getChild(i)
1503
1504
1505     def getChildCount(self, t):
1506         if t is None:
1507             return 0
1508         return t.getChildCount()
1509
1510
1511     def getParent(self, t):
1512         return t.getParent()
1513
1514
1515     def setParent(self, t, parent):
1516         t.setParent(parent)
1517
1518
1519     def getChildIndex(self, t):
1520         return t.getChildIndex()
1521
1522
1523     def setChildIndex(self, t, index):
1524         t.setChildIndex(index)
1525
1526
1527     def replaceChildren(self, parent, startChildIndex, stopChildIndex, t):
1528         if parent is not None:
1529             parent.replaceChildren(startChildIndex, stopChildIndex, t)
1530
1531
1532 ############################################################################
1533 #
1534 # streams
1535 #
1536 # TreeNodeStream
1537 # \- BaseTree
1538 #    \- CommonTree
1539 #
1540 # TreeAdaptor
1541 # \- BaseTreeAdaptor
1542 #    \- CommonTreeAdaptor
1543 #
1544 ############################################################################
1545
1546
1547
1548 class TreeNodeStream(IntStream):
1549     """@brief A stream of tree nodes
1550
1551     It accessing nodes from a tree of some kind.
1552     """
1553
1554     # TreeNodeStream is abstract, no need to complain about not implemented
1555     # abstract methods
1556     # pylint: disable-msg=W0223
1557
1558     def get(self, i):
1559         """Get a tree node at an absolute index i; 0..n-1.
1560         If you don't want to buffer up nodes, then this method makes no
1561         sense for you.
1562         """
1563
1564         raise NotImplementedError
1565
1566
1567     def LT(self, k):
1568         """
1569         Get tree node at current input pointer + i ahead where i=1 is next node.
1570         i<0 indicates nodes in the past.  So LT(-1) is previous node, but
1571         implementations are not required to provide results for k < -1.
1572         LT(0) is undefined.  For i>=n, return null.
1573         Return null for LT(0) and any index that results in an absolute address
1574         that is negative.
1575
1576         This is analogus to the LT() method of the TokenStream, but this
1577         returns a tree node instead of a token.  Makes code gen identical
1578         for both parser and tree grammars. :)
1579         """
1580
1581         raise NotImplementedError
1582
1583
1584     def getTreeSource(self):
1585         """
1586         Where is this stream pulling nodes from?  This is not the name, but
1587         the object that provides node objects.
1588         """
1589
1590         raise NotImplementedError
1591
1592
1593     def getTokenStream(self):
1594         """
1595         If the tree associated with this stream was created from a TokenStream,
1596         you can specify it here.  Used to do rule $text attribute in tree
1597         parser.  Optional unless you use tree parser rule text attribute
1598         or output=template and rewrite=true options.
1599         """
1600
1601         raise NotImplementedError
1602
1603
1604     def getTreeAdaptor(self):
1605         """
1606         What adaptor can tell me how to interpret/navigate nodes and
1607         trees.  E.g., get text of a node.
1608         """
1609
1610         raise NotImplementedError
1611
1612
1613     def setUniqueNavigationNodes(self, uniqueNavigationNodes):
1614         """
1615         As we flatten the tree, we use UP, DOWN nodes to represent
1616         the tree structure.  When debugging we need unique nodes
1617         so we have to instantiate new ones.  When doing normal tree
1618         parsing, it's slow and a waste of memory to create unique
1619         navigation nodes.  Default should be false;
1620         """
1621
1622         raise NotImplementedError
1623
1624
1625     def toString(self, start, stop):
1626         """
1627         Return the text of all nodes from start to stop, inclusive.
1628         If the stream does not buffer all the nodes then it can still
1629         walk recursively from start until stop.  You can always return
1630         null or "" too, but users should not access $ruleLabel.text in
1631         an action of course in that case.
1632         """
1633
1634         raise NotImplementedError
1635
1636
1637     # REWRITING TREES (used by tree parser)
1638     def replaceChildren(self, parent, startChildIndex, stopChildIndex, t):
1639         """
1640         Replace from start to stop child index of parent with t, which might
1641         be a list.  Number of children may be different
1642         after this call.  The stream is notified because it is walking the
1643         tree and might need to know you are monkeying with the underlying
1644         tree.  Also, it might be able to modify the node stream to avoid
1645         restreaming for future phases.
1646
1647         If parent is null, don't do anything; must be at root of overall tree.
1648         Can't replace whatever points to the parent externally.  Do nothing.
1649         """
1650
1651         raise NotImplementedError
1652
1653
1654 class CommonTreeNodeStream(TreeNodeStream):
1655     """@brief A buffered stream of tree nodes.
1656
1657     Nodes can be from a tree of ANY kind.
1658
1659     This node stream sucks all nodes out of the tree specified in
1660     the constructor during construction and makes pointers into
1661     the tree using an array of Object pointers. The stream necessarily
1662     includes pointers to DOWN and UP and EOF nodes.
1663
1664     This stream knows how to mark/release for backtracking.
1665
1666     This stream is most suitable for tree interpreters that need to
1667     jump around a lot or for tree parsers requiring speed (at cost of memory).
1668     There is some duplicated functionality here with UnBufferedTreeNodeStream
1669     but just in bookkeeping, not tree walking etc...
1670
1671     @see UnBufferedTreeNodeStream
1672     """
1673
1674     def __init__(self, *args):
1675         TreeNodeStream.__init__(self)
1676
1677         if len(args) == 1:
1678             adaptor = CommonTreeAdaptor()
1679             tree = args[0]
1680
1681         elif len(args) == 2:
1682             adaptor = args[0]
1683             tree = args[1]
1684
1685         else:
1686             raise TypeError("Invalid arguments")
1687
1688         # all these navigation nodes are shared and hence they
1689         # cannot contain any line/column info
1690         self.down = adaptor.createFromType(DOWN, "DOWN")
1691         self.up = adaptor.createFromType(UP, "UP")
1692         self.eof = adaptor.createFromType(EOF, "EOF")
1693
1694         # The complete mapping from stream index to tree node.
1695         # This buffer includes pointers to DOWN, UP, and EOF nodes.
1696         # It is built upon ctor invocation.  The elements are type
1697         #  Object as we don't what the trees look like.
1698
1699         # Load upon first need of the buffer so we can set token types
1700         # of interest for reverseIndexing.  Slows us down a wee bit to
1701         # do all of the if p==-1 testing everywhere though.
1702         self.nodes = []
1703
1704         # Pull nodes from which tree?
1705         self.root = tree
1706
1707         # IF this tree (root) was created from a token stream, track it.
1708         self.tokens = None
1709
1710         # What tree adaptor was used to build these trees
1711         self.adaptor = adaptor
1712
1713         # Reuse same DOWN, UP navigation nodes unless this is true
1714         self.uniqueNavigationNodes = False
1715
1716         # The index into the nodes list of the current node (next node
1717         # to consume).  If -1, nodes array not filled yet.
1718         self.p = -1
1719
1720         # Track the last mark() call result value for use in rewind().
1721         self.lastMarker = None
1722
1723         # Stack of indexes used for push/pop calls
1724         self.calls = []
1725
1726
1727     def fillBuffer(self):
1728         """Walk tree with depth-first-search and fill nodes buffer.
1729         Don't do DOWN, UP nodes if its a list (t is isNil).
1730         """
1731
1732         self._fillBuffer(self.root)
1733         self.p = 0 # buffer of nodes intialized now
1734
1735
1736     def _fillBuffer(self, t):
1737         nil = self.adaptor.isNil(t)
1738
1739         if not nil:
1740             self.nodes.append(t) # add this node
1741
1742         # add DOWN node if t has children
1743         n = self.adaptor.getChildCount(t)
1744         if not nil and n > 0:
1745             self.addNavigationNode(DOWN)
1746
1747         # and now add all its children
1748         for c in range(n):
1749             self._fillBuffer(self.adaptor.getChild(t, c))
1750
1751         # add UP node if t has children
1752         if not nil and n > 0:
1753             self.addNavigationNode(UP)
1754
1755
1756     def getNodeIndex(self, node):
1757         """What is the stream index for node? 0..n-1
1758         Return -1 if node not found.
1759         """
1760
1761         if self.p == -1:
1762             self.fillBuffer()
1763
1764         for i, t in enumerate(self.nodes):
1765             if t == node:
1766                 return i
1767
1768         return -1
1769
1770
1771     def addNavigationNode(self, ttype):
1772         """
1773         As we flatten the tree, we use UP, DOWN nodes to represent
1774         the tree structure.  When debugging we need unique nodes
1775         so instantiate new ones when uniqueNavigationNodes is true.
1776         """
1777
1778         navNode = None
1779
1780         if ttype == DOWN:
1781             if self.hasUniqueNavigationNodes():
1782                 navNode = self.adaptor.createFromType(DOWN, "DOWN")
1783
1784             else:
1785                 navNode = self.down
1786
1787         else:
1788             if self.hasUniqueNavigationNodes():
1789                 navNode = self.adaptor.createFromType(UP, "UP")
1790
1791             else:
1792                 navNode = self.up
1793
1794         self.nodes.append(navNode)
1795
1796
1797     def get(self, i):
1798         if self.p == -1:
1799             self.fillBuffer()
1800
1801         return self.nodes[i]
1802
1803
1804     def LT(self, k):
1805         if self.p == -1:
1806             self.fillBuffer()
1807
1808         if k == 0:
1809             return None
1810
1811         if k < 0:
1812             return self.LB(-k)
1813
1814         #System.out.print("LT(p="+p+","+k+")=");
1815         if self.p + k - 1 >= len(self.nodes):
1816             return self.eof
1817
1818         return self.nodes[self.p + k - 1]
1819
1820
1821     def getCurrentSymbol(self):
1822         return self.LT(1)
1823
1824
1825     def LB(self, k):
1826         """Look backwards k nodes"""
1827
1828         if k == 0:
1829             return None
1830
1831         if self.p - k < 0:
1832             return None
1833
1834         return self.nodes[self.p - k]
1835
1836
1837     def getTreeSource(self):
1838         return self.root
1839
1840
1841     def getSourceName(self):
1842         return self.getTokenStream().getSourceName()
1843
1844
1845     def getTokenStream(self):
1846         return self.tokens
1847
1848
1849     def setTokenStream(self, tokens):
1850         self.tokens = tokens
1851
1852
1853     def getTreeAdaptor(self):
1854         return self.adaptor
1855
1856
1857     def hasUniqueNavigationNodes(self):
1858         return self.uniqueNavigationNodes
1859
1860
1861     def setUniqueNavigationNodes(self, uniqueNavigationNodes):
1862         self.uniqueNavigationNodes = uniqueNavigationNodes
1863
1864
1865     def consume(self):
1866         if self.p == -1:
1867             self.fillBuffer()
1868
1869         self.p += 1
1870
1871
1872     def LA(self, i):
1873         return self.adaptor.getType(self.LT(i))
1874
1875
1876     def mark(self):
1877         if self.p == -1:
1878             self.fillBuffer()
1879
1880
1881         self.lastMarker = self.index()
1882         return self.lastMarker
1883
1884
1885     def release(self, marker=None):
1886         # no resources to release
1887
1888         pass
1889
1890
1891     def index(self):
1892         return self.p
1893
1894
1895     def rewind(self, marker=None):
1896         if marker is None:
1897             marker = self.lastMarker
1898
1899         self.seek(marker)
1900
1901
1902     def seek(self, index):
1903         if self.p == -1:
1904             self.fillBuffer()
1905
1906         self.p = index
1907
1908
1909     def push(self, index):
1910         """
1911         Make stream jump to a new location, saving old location.
1912         Switch back with pop().
1913         """
1914
1915         self.calls.append(self.p) # save current index
1916         self.seek(index)
1917
1918
1919     def pop(self):
1920         """
1921         Seek back to previous index saved during last push() call.
1922         Return top of stack (return index).
1923         """
1924
1925         ret = self.calls.pop(-1)
1926         self.seek(ret)
1927         return ret
1928
1929
1930     def reset(self):
1931         self.p = 0
1932         self.lastMarker = 0
1933         self.calls = []
1934
1935
1936     def size(self):
1937         if self.p == -1:
1938             self.fillBuffer()
1939
1940         return len(self.nodes)
1941
1942
1943     # TREE REWRITE INTERFACE
1944
1945     def replaceChildren(self, parent, startChildIndex, stopChildIndex, t):
1946         if parent is not None:
1947             self.adaptor.replaceChildren(
1948                 parent, startChildIndex, stopChildIndex, t
1949                 )
1950
1951
1952     def __str__(self):
1953         """Used for testing, just return the token type stream"""
1954
1955         if self.p == -1:
1956             self.fillBuffer()
1957
1958         return ' '.join([str(self.adaptor.getType(node))
1959                          for node in self.nodes
1960                          ])
1961
1962
1963     def toString(self, start, stop):
1964         if start is None or stop is None:
1965             return None
1966
1967         if self.p == -1:
1968             self.fillBuffer()
1969
1970         #System.out.println("stop: "+stop);
1971         #if ( start instanceof CommonTree )
1972         #    System.out.print("toString: "+((CommonTree)start).getToken()+", ");
1973         #else
1974         #    System.out.println(start);
1975         #if ( stop instanceof CommonTree )
1976         #    System.out.println(((CommonTree)stop).getToken());
1977         #else
1978         #    System.out.println(stop);
1979
1980         # if we have the token stream, use that to dump text in order
1981         if self.tokens is not None:
1982             beginTokenIndex = self.adaptor.getTokenStartIndex(start)
1983             endTokenIndex = self.adaptor.getTokenStopIndex(stop)
1984
1985             # if it's a tree, use start/stop index from start node
1986             # else use token range from start/stop nodes
1987             if self.adaptor.getType(stop) == UP:
1988                 endTokenIndex = self.adaptor.getTokenStopIndex(start)
1989
1990             elif self.adaptor.getType(stop) == EOF:
1991                 endTokenIndex = self.size() -2 # don't use EOF
1992
1993             return self.tokens.toString(beginTokenIndex, endTokenIndex)
1994
1995         # walk nodes looking for start
1996         i, t = 0, None
1997         for i, t in enumerate(self.nodes):
1998             if t == start:
1999                 break
2000
2001         # now walk until we see stop, filling string buffer with text
2002         buf = []
2003         t = self.nodes[i]
2004         while t != stop:
2005             text = self.adaptor.getText(t)
2006             if text is None:
2007                 text = " " + self.adaptor.getType(t)
2008
2009             buf.append(text)
2010             i += 1
2011             t = self.nodes[i]
2012
2013         # include stop node too
2014         text = self.adaptor.getText(stop)
2015         if text is None:
2016             text = " " +self.adaptor.getType(stop)
2017
2018         buf.append(text)
2019
2020         return ''.join(buf)
2021
2022
2023     ## iterator interface
2024     def __iter__(self):
2025         if self.p == -1:
2026             self.fillBuffer()
2027
2028         for node in self.nodes:
2029             yield node
2030
2031
2032 #############################################################################
2033 #
2034 # tree parser
2035 #
2036 #############################################################################
2037
2038 class TreeParser(BaseRecognizer):
2039     """@brief Baseclass for generated tree parsers.
2040
2041     A parser for a stream of tree nodes.  "tree grammars" result in a subclass
2042     of this.  All the error reporting and recovery is shared with Parser via
2043     the BaseRecognizer superclass.
2044     """
2045
2046     def __init__(self, input, state=None):
2047         BaseRecognizer.__init__(self, state)
2048
2049         self.input = None
2050         self.setTreeNodeStream(input)
2051
2052
2053     def reset(self):
2054         BaseRecognizer.reset(self) # reset all recognizer state variables
2055         if self.input is not None:
2056             self.input.seek(0) # rewind the input
2057
2058
2059     def setTreeNodeStream(self, input):
2060         """Set the input stream"""
2061
2062         self.input = input
2063
2064
2065     def getTreeNodeStream(self):
2066         return self.input
2067
2068
2069     def getSourceName(self):
2070         return self.input.getSourceName()
2071
2072
2073     def getCurrentInputSymbol(self, input):
2074         return input.LT(1)
2075
2076
2077     def getMissingSymbol(self, input, e, expectedTokenType, follow):
2078         tokenText = "<missing " + self.tokenNames[expectedTokenType] + ">"
2079         return CommonTree(CommonToken(type=expectedTokenType, text=tokenText))
2080
2081
2082     def matchAny(self, ignore): # ignore stream, copy of this.input
2083         """
2084         Match '.' in tree parser has special meaning.  Skip node or
2085         entire tree if node has children.  If children, scan until
2086         corresponding UP node.
2087         """
2088
2089         self._state.errorRecovery = False
2090
2091         look = self.input.LT(1)
2092         if self.input.getTreeAdaptor().getChildCount(look) == 0:
2093             self.input.consume() # not subtree, consume 1 node and return
2094             return
2095
2096         # current node is a subtree, skip to corresponding UP.
2097         # must count nesting level to get right UP
2098         level = 0
2099         tokenType = self.input.getTreeAdaptor().getType(look)
2100         while tokenType != EOF and not (tokenType == UP and level==0):
2101             self.input.consume()
2102             look = self.input.LT(1)
2103             tokenType = self.input.getTreeAdaptor().getType(look)
2104             if tokenType == DOWN:
2105                 level += 1
2106
2107             elif tokenType == UP:
2108                 level -= 1
2109
2110         self.input.consume() # consume UP
2111
2112
2113     def mismatch(self, input, ttype, follow):
2114         """
2115         We have DOWN/UP nodes in the stream that have no line info; override.
2116         plus we want to alter the exception type. Don't try to recover
2117         from tree parser errors inline...
2118         """
2119
2120         raise MismatchedTreeNodeException(ttype, input)
2121
2122
2123     def getErrorHeader(self, e):
2124         """
2125         Prefix error message with the grammar name because message is
2126         always intended for the programmer because the parser built
2127         the input tree not the user.
2128         """
2129
2130         return (self.getGrammarFileName() +
2131                 ": node from %sline %s:%s"
2132                 % (['', "after "][e.approximateLineInfo],
2133                    e.line,
2134                    e.charPositionInLine
2135                    )
2136                 )
2137
2138     def getErrorMessage(self, e, tokenNames):
2139         """
2140         Tree parsers parse nodes they usually have a token object as
2141         payload. Set the exception token and do the default behavior.
2142         """
2143
2144         if isinstance(self, TreeParser):
2145             adaptor = e.input.getTreeAdaptor()
2146             e.token = adaptor.getToken(e.node)
2147             if e.token is not None: # could be an UP/DOWN node
2148                 e.token = CommonToken(
2149                     type=adaptor.getType(e.node),
2150                     text=adaptor.getText(e.node)
2151                     )
2152
2153         return BaseRecognizer.getErrorMessage(self, e, tokenNames)
2154
2155
2156     def traceIn(self, ruleName, ruleIndex):
2157         BaseRecognizer.traceIn(self, ruleName, ruleIndex, self.input.LT(1))
2158
2159
2160     def traceOut(self, ruleName, ruleIndex):
2161         BaseRecognizer.traceOut(self, ruleName, ruleIndex, self.input.LT(1))
2162
2163
2164 #############################################################################
2165 #
2166 # streams for rule rewriting
2167 #
2168 #############################################################################
2169
2170 class RewriteRuleElementStream(object):
2171     """@brief Internal helper class.
2172
2173     A generic list of elements tracked in an alternative to be used in
2174     a -> rewrite rule.  We need to subclass to fill in the next() method,
2175     which returns either an AST node wrapped around a token payload or
2176     an existing subtree.
2177
2178     Once you start next()ing, do not try to add more elements.  It will
2179     break the cursor tracking I believe.
2180
2181     @see org.antlr.runtime.tree.RewriteRuleSubtreeStream
2182     @see org.antlr.runtime.tree.RewriteRuleTokenStream
2183
2184     TODO: add mechanism to detect/puke on modification after reading from
2185     stream
2186     """
2187
2188     def __init__(self, adaptor, elementDescription, elements=None):
2189         # Cursor 0..n-1.  If singleElement!=null, cursor is 0 until you next(),
2190         # which bumps it to 1 meaning no more elements.
2191         self.cursor = 0
2192
2193         # Track single elements w/o creating a list.  Upon 2nd add, alloc list
2194         self.singleElement = None
2195
2196         # The list of tokens or subtrees we are tracking
2197         self.elements = None
2198
2199         # Once a node / subtree has been used in a stream, it must be dup'd
2200         # from then on.  Streams are reset after subrules so that the streams
2201         # can be reused in future subrules.  So, reset must set a dirty bit.
2202         # If dirty, then next() always returns a dup.
2203         self.dirty = False
2204
2205         # The element or stream description; usually has name of the token or
2206         # rule reference that this list tracks.  Can include rulename too, but
2207         # the exception would track that info.
2208         self.elementDescription = elementDescription
2209
2210         self.adaptor = adaptor
2211
2212         if isinstance(elements, (list, tuple)):
2213             # Create a stream, but feed off an existing list
2214             self.singleElement = None
2215             self.elements = elements
2216
2217         else:
2218             # Create a stream with one element
2219             self.add(elements)
2220
2221
2222     def reset(self):
2223         """
2224         Reset the condition of this stream so that it appears we have
2225         not consumed any of its elements.  Elements themselves are untouched.
2226         Once we reset the stream, any future use will need duplicates.  Set
2227         the dirty bit.
2228         """
2229
2230         self.cursor = 0
2231         self.dirty = True
2232
2233
2234     def add(self, el):
2235         if el is None:
2236             return
2237
2238         if self.elements is not None: # if in list, just add
2239             self.elements.append(el)
2240             return
2241
2242         if self.singleElement is None: # no elements yet, track w/o list
2243             self.singleElement = el
2244             return
2245
2246         # adding 2nd element, move to list
2247         self.elements = []
2248         self.elements.append(self.singleElement)
2249         self.singleElement = None
2250         self.elements.append(el)
2251
2252
2253     def nextTree(self):
2254         """
2255         Return the next element in the stream.  If out of elements, throw
2256         an exception unless size()==1.  If size is 1, then return elements[0].
2257
2258         Return a duplicate node/subtree if stream is out of elements and
2259         size==1. If we've already used the element, dup (dirty bit set).
2260         """
2261
2262         if (self.dirty
2263             or (self.cursor >= len(self) and len(self) == 1)
2264             ):
2265             # if out of elements and size is 1, dup
2266             el = self._next()
2267             return self.dup(el)
2268
2269         # test size above then fetch
2270         el = self._next()
2271         return el
2272
2273
2274     def _next(self):
2275         """
2276         do the work of getting the next element, making sure that it's
2277         a tree node or subtree.  Deal with the optimization of single-
2278         element list versus list of size > 1.  Throw an exception
2279         if the stream is empty or we're out of elements and size>1.
2280         protected so you can override in a subclass if necessary.
2281         """
2282
2283         if len(self) == 0:
2284             raise RewriteEmptyStreamException(self.elementDescription)
2285
2286         if self.cursor >= len(self): # out of elements?
2287             if len(self) == 1: # if size is 1, it's ok; return and we'll dup
2288                 return self.toTree(self.singleElement)
2289
2290             # out of elements and size was not 1, so we can't dup
2291             raise RewriteCardinalityException(self.elementDescription)
2292
2293         # we have elements
2294         if self.singleElement is not None:
2295             self.cursor += 1 # move cursor even for single element list
2296             return self.toTree(self.singleElement)
2297
2298         # must have more than one in list, pull from elements
2299         o = self.toTree(self.elements[self.cursor])
2300         self.cursor += 1
2301         return o
2302
2303
2304     def dup(self, el):
2305         """
2306         When constructing trees, sometimes we need to dup a token or AST
2307         subtree.  Dup'ing a token means just creating another AST node
2308         around it.  For trees, you must call the adaptor.dupTree() unless
2309         the element is for a tree root; then it must be a node dup.
2310         """
2311
2312         raise NotImplementedError
2313
2314
2315     def toTree(self, el):
2316         """
2317         Ensure stream emits trees; tokens must be converted to AST nodes.
2318         AST nodes can be passed through unmolested.
2319         """
2320
2321         return el
2322
2323
2324     def hasNext(self):
2325         return ( (self.singleElement is not None and self.cursor < 1)
2326                  or (self.elements is not None
2327                      and self.cursor < len(self.elements)
2328                      )
2329                  )
2330
2331
2332     def size(self):
2333         if self.singleElement is not None:
2334             return 1
2335
2336         if self.elements is not None:
2337             return len(self.elements)
2338
2339         return 0
2340
2341     __len__ = size
2342
2343
2344     def getDescription(self):
2345         """Deprecated. Directly access elementDescription attribute"""
2346
2347         return self.elementDescription
2348
2349
2350 class RewriteRuleTokenStream(RewriteRuleElementStream):
2351     """@brief Internal helper class."""
2352
2353     def toTree(self, el):
2354         # Don't convert to a tree unless they explicitly call nextTree.
2355         # This way we can do hetero tree nodes in rewrite.
2356         return el
2357
2358
2359     def nextNode(self):
2360         t = self._next()
2361         return self.adaptor.createWithPayload(t)
2362
2363
2364     def nextToken(self):
2365         return self._next()
2366
2367
2368     def dup(self, el):
2369         raise TypeError("dup can't be called for a token stream.")
2370
2371
2372 class RewriteRuleSubtreeStream(RewriteRuleElementStream):
2373     """@brief Internal helper class."""
2374
2375     def nextNode(self):
2376         """
2377         Treat next element as a single node even if it's a subtree.
2378         This is used instead of next() when the result has to be a
2379         tree root node.  Also prevents us from duplicating recently-added
2380         children; e.g., ^(type ID)+ adds ID to type and then 2nd iteration
2381         must dup the type node, but ID has been added.
2382
2383         Referencing a rule result twice is ok; dup entire tree as
2384         we can't be adding trees as root; e.g., expr expr.
2385
2386         Hideous code duplication here with super.next().  Can't think of
2387         a proper way to refactor.  This needs to always call dup node
2388         and super.next() doesn't know which to call: dup node or dup tree.
2389         """
2390
2391         if (self.dirty
2392             or (self.cursor >= len(self) and len(self) == 1)
2393             ):
2394             # if out of elements and size is 1, dup (at most a single node
2395             # since this is for making root nodes).
2396             el = self._next()
2397             return self.adaptor.dupNode(el)
2398
2399         # test size above then fetch
2400         el = self._next()
2401         return el
2402
2403
2404     def dup(self, el):
2405         return self.adaptor.dupTree(el)
2406
2407
2408
2409 class RewriteRuleNodeStream(RewriteRuleElementStream):
2410     """
2411     Queues up nodes matched on left side of -> in a tree parser. This is
2412     the analog of RewriteRuleTokenStream for normal parsers.
2413     """
2414
2415     def nextNode(self):
2416         return self._next()
2417
2418
2419     def toTree(self, el):
2420         return self.adaptor.dupNode(el)
2421
2422
2423     def dup(self, el):
2424         # we dup every node, so don't have to worry about calling dup; short-
2425         #circuited next() so it doesn't call.
2426         raise TypeError("dup can't be called for a node stream.")
2427
2428
2429 class TreeRuleReturnScope(RuleReturnScope):
2430     """
2431     This is identical to the ParserRuleReturnScope except that
2432     the start property is a tree nodes not Token object
2433     when you are parsing trees.  To be generic the tree node types
2434     have to be Object.
2435     """
2436
2437     def __init__(self):
2438         self.start = None
2439         self.tree = None
2440
2441
2442     def getStart(self):
2443         return self.start
2444
2445
2446     def getTree(self):
2447         return self.tree
2448