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