13447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein/* 23447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein [The "BSD license"] 33447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Copyright (c) 2005-2009 Terence Parr 43447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein All rights reserved. 53447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 63447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Redistribution and use in source and binary forms, with or without 73447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein modification, are permitted provided that the following conditions 83447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein are met: 93447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1. Redistributions of source code must retain the above copyright 103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein notice, this list of conditions and the following disclaimer. 113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2. Redistributions in binary form must reproduce the above copyright 123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein notice, this list of conditions and the following disclaimer in the 133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein documentation and/or other materials provided with the distribution. 143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 3. The name of the author may not be used to endorse or promote products 153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein derived from this software without specific prior written permission. 163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinpackage org.antlr.runtime.tree; 293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport org.antlr.runtime.Token; 313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport java.util.List; 333447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 343447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein/** What does a tree look like? ANTLR has a number of support classes 353447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * such as CommonTreeNodeStream that work on these kinds of trees. You 363447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * don't have to make your trees implement this interface, but if you do, 373447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * you'll be able to use more support code. 383447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 393447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * NOTE: When constructing trees, ANTLR can build any kind of tree; it can 403447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * even use Token objects as trees if you add a child list to your tokens. 413447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 423447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * This is a tree node without any payload; just navigation and factory stuff. 433447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 443447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinpublic interface Tree { 453447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public static final Tree INVALID_NODE = new CommonTree(Token.INVALID_TOKEN); 463447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 473447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Tree getChild(int i); 483447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 493447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int getChildCount(); 503447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 513447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // Tree tracks parent and child index now > 3.0 523447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 533447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Tree getParent(); 543447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 553447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void setParent(Tree t); 563447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 573447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Is there is a node above with token type ttype? */ 583447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public boolean hasAncestor(int ttype); 593447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 603447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Walk upwards and get first ancestor with this token type. */ 613447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Tree getAncestor(int ttype); 623447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 633447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Return a list of all ancestors of this node. The first node of 643447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * list is the root and the last is the parent of this node. 653447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 663447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public List getAncestors(); 673447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 683447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** This node is what child index? 0..n-1 */ 693447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public int getChildIndex(); 703447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 713447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void setChildIndex(int index); 723447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 733447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Set the parent and child index values for all children */ 743447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void freshenParentAndChildIndexes(); 753447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 763447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Add t as a child to this node. If t is null, do nothing. If t 773447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * is nil, add all children of t to this' children. 783447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 793447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein void addChild(Tree t); 803447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 813447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Set ith child (0..n-1) to t; t must be non-null and non-nil node */ 823447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void setChild(int i, Tree t); 833447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 843447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Object deleteChild(int i); 853447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 863447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Delete children from start to stop and replace with t even if t is 873447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * a list (nil-root tree). num of children can increase or decrease. 883447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * For huge child lists, inserting children can force walking rest of 893447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * children to set their childindex; could be slow. 903447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 913447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void replaceChildren(int startChildIndex, int stopChildIndex, Object t); 923447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 933447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Indicates the node is a nil node but may still have children, meaning 943447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * the tree is a flat list. 953447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 963447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein boolean isNil(); 973447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 983447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** What is the smallest token index (indexing from 0) for this node 993447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * and its children? 1003447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 1013447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int getTokenStartIndex(); 1023447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1033447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein void setTokenStartIndex(int index); 1043447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1053447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** What is the largest token index (indexing from 0) for this node 1063447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * and its children? 1073447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 1083447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int getTokenStopIndex(); 1093447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein void setTokenStopIndex(int index); 1113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Tree dupNode(); 1133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Return a token type; needed for tree parsing */ 1153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int getType(); 1163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein String getText(); 1183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** In case we don't have a token payload, what is the line for errors? */ 1203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int getLine(); 1213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int getCharPositionInLine(); 1233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein String toStringTree(); 1253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein String toString(); 1273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein} 128