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