1 /* 2 [The "BSD licence"] 3 Copyright (c) 2005-2007 Terence Parr 4 All rights reserved. 5 6 Redistribution and use in source and binary forms, with or without 7 modification, are permitted provided that the following conditions 8 are met: 9 1. Redistributions of source code must retain the above copyright 10 notice, this list of conditions and the following disclaimer. 11 2. Redistributions in binary form must reproduce the above copyright 12 notice, this list of conditions and the following disclaimer in the 13 documentation and/or other materials provided with the distribution. 14 3. The name of the author may not be used to endorse or promote products 15 derived from this software without specific prior written permission. 16 17 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 package org.antlr.runtime.tree { 29 30 import org.antlr.runtime.*; 31 32 /** How to create and navigate trees. Rather than have a separate factory 33 * and adaptor, I've merged them. Makes sense to encapsulate. 34 * 35 * This takes the place of the tree construction code generated in the 36 * generated code in 2.x and the ASTFactory. 37 * 38 * I do not need to know the type of a tree at all so they are all 39 * generic Objects. This may increase the amount of typecasting needed. :( 40 */ 41 public interface TreeAdaptor { 42 // C o n s t r u c t i o n 43 44 /** Create a tree node from Token object; for CommonTree type trees, 45 * then the token just becomes the payload. This is the most 46 * common create call. 47 * 48 * Override if you want another kind of node to be built. 49 */ 50 function createWithPayload(payload:Token):Object; 51 52 /** Duplicate a single tree node. 53 * Override if you want another kind of node to be built. 54 */ 55 function dupNode(treeNode:Object):Object; 56 57 /** Duplicate tree recursively, using dupNode() for each node */ 58 function dupTree(tree:Object):Object; 59 60 /** Return a nil node (an empty but non-null node) that can hold 61 * a list of element as the children. If you want a flat tree (a list) 62 * use "t=adaptor.nil(); t.addChild(x); t.addChild(y);" 63 */ 64 function nil():Object; 65 66 /** Return a tree node representing an error. This node records the 67 * tokens consumed during error recovery. The start token indicates the 68 * input symbol at which the error was detected. The stop token indicates 69 * the last symbol consumed during recovery. 70 * 71 * You must specify the input stream so that the erroneous text can 72 * be packaged up in the error node. The exception could be useful 73 * to some applications; default implementation stores ptr to it in 74 * the CommonErrorNode. 75 * 76 * This only makes sense during token parsing, not tree parsing. 77 * Tree parsing should happen only when parsing and tree construction 78 * succeed. 79 */ 80 function errorNode(input:TokenStream, start:Token, stop:Token, e:RecognitionException):Object; 81 82 /** Is tree considered a nil node used to make lists of child nodes? */ 83 function isNil(tree:Object):Boolean; 84 85 /** Add a child to the tree t. If child is a flat tree (a list), make all 86 * in list children of t. Warning: if t has no children, but child does 87 * and child isNil then you can decide it is ok to move children to t via 88 * t.children = child.children; i.e., without copying the array. Just 89 * make sure that this is consistent with have the user will build 90 * ASTs. Do nothing if t or child is null. 91 */ 92 function addChild(t:Object, child:Object):void; 93 94 /** If oldRoot is a nil root, just copy or move the children to newRoot. 95 * If not a nil root, make oldRoot a child of newRoot. 96 * 97 * old=^(nil a b c), new=r yields ^(r a b c) 98 * old=^(a b c), new=r yields ^(r ^(a b c)) 99 * 100 * If newRoot is a nil-rooted single child tree, use the single 101 * child as the new root node. 102 * 103 * old=^(nil a b c), new=^(nil r) yields ^(r a b c) 104 * old=^(a b c), new=^(nil r) yields ^(r ^(a b c)) 105 * 106 * If oldRoot was null, it's ok, just return newRoot (even if isNil). 107 * 108 * old=null, new=r yields r 109 * old=null, new=^(nil r) yields ^(nil r) 110 * 111 * Return newRoot. Throw an exception if newRoot is not a 112 * simple node or nil root with a single child node--it must be a root 113 * node. If newRoot is ^(nil x) return x as newRoot. 114 * 115 * Be advised that it's ok for newRoot to point at oldRoot's 116 * children; i.e., you don't have to copy the list. We are 117 * constructing these nodes so we should have this control for 118 * efficiency. 119 */ 120 function becomeRoot(newRoot:Object, oldRoot:Object):Object; 121 122 /** Given the root of the subtree created for this rule, post process 123 * it to do any simplifications or whatever you want. A required 124 * behavior is to convert ^(nil singleSubtree) to singleSubtree 125 * as the setting of start/stop indexes relies on a single non-nil root 126 * for non-flat trees. 127 * 128 * Flat trees such as for lists like "idlist : ID+ ;" are left alone 129 * unless there is only one ID. For a list, the start/stop indexes 130 * are set in the nil node. 131 * 132 * This method is executed after all rule tree construction and right 133 * before setTokenBoundaries(). 134 */ 135 function rulePostProcessing(root:Object):Object; 136 137 /** For identifying trees. 138 * 139 * How to identify nodes so we can say "add node to a prior node"? 140 * Even becomeRoot is an issue. Use System.identityHashCode(node) 141 * usually. 142 */ 143 function getUniqueID(node:Object):int; 144 145 146 // R e w r i t e R u l e s 147 148 /** Create a new node derived from a token, with a new token type. 149 * This is invoked from an imaginary node ref on right side of a 150 * rewrite rule as IMAG[$tokenLabel] or IMAG[$tokenLabel, "IMAG"]. 151 * 152 * This should invoke createToken(Token). 153 */ 154 function createFromToken(tokenType:int, fromToken:Token, text:String = null):Object; 155 156 /** Create a new node derived from a token, with a new token type. 157 * This is invoked from an imaginary node ref on right side of a 158 * rewrite rule as IMAG["IMAG"]. 159 * 160 * This should invoke createToken(int,String). 161 */ 162 function createFromType(tokenType:int, text:String):Object; 163 164 165 // C o n t e n t 166 167 /** For tree parsing, I need to know the token type of a node */ 168 function getType(t:Object):int; 169 170 /** Node constructors can set the type of a node */ 171 function setType(t:Object, type:int):void; 172 173 function getText(t:Object):String; 174 175 /** Node constructors can set the text of a node */ 176 function setText(t:Object, text:String):void; 177 178 /** Return the token object from which this node was created. 179 * Currently used only for printing an error message. 180 * The error display routine in BaseRecognizer needs to 181 * display where the input the error occurred. If your 182 * tree of limitation does not store information that can 183 * lead you to the token, you can create a token filled with 184 * the appropriate information and pass that back. See 185 * BaseRecognizer.getErrorMessage(). 186 */ 187 function getToken(t:Object):Token; 188 189 /** Where are the bounds in the input token stream for this node and 190 * all children? Each rule that creates AST nodes will call this 191 * method right before returning. Flat trees (i.e., lists) will 192 * still usually have a nil root node just to hold the children list. 193 * That node would contain the start/stop indexes then. 194 */ 195 function setTokenBoundaries(t:Object, startToken:Token, stopToken:Token):void; 196 197 /** Get the token start index for this subtree; return -1 if no such index */ 198 function getTokenStartIndex(t:Object):int; 199 200 /** Get the token stop index for this subtree; return -1 if no such index */ 201 function getTokenStopIndex(t:Object):int; 202 203 204 // N a v i g a t i o n / T r e e P a r s i n g 205 206 /** Get a child 0..n-1 node */ 207 function getChild(t:Object, i:int):Object; 208 209 /** Set ith child (0..n-1) to t; t must be non-null and non-nil node */ 210 function setChild(t:Object, i:int, child:Object):void; 211 212 /** Remove ith child and shift children down from right. */ 213 function deleteChild(t:Object, i:int):Object; 214 215 /** How many children? If 0, then this is a leaf node */ 216 function getChildCount(t:Object):int; 217 218 /** Who is the parent node of this node; if null, implies node is root. 219 * If your node type doesn't handle this, it's ok but the tree rewrites 220 * in tree parsers need this functionality. 221 */ 222 function getParent(t:Object):Object; 223 function setParent(t:Object, parent:Object):void; 224 225 /** What index is this node in the child list? Range: 0..n-1 226 * If your node type doesn't handle this, it's ok but the tree rewrites 227 * in tree parsers need this functionality. 228 */ 229 function getChildIndex(t:Object):int; 230 function setChildIndex(t:Object, index:int):void; 231 232 /** Replace from start to stop child index of parent with t, which might 233 * be a list. Number of children may be different 234 * after this call. 235 * 236 * If parent is null, don't do anything; must be at root of overall tree. 237 * Can't replace whatever points to the parent externally. Do nothing. 238 */ 239 function replaceChildren(parent:Object, startChildIndex:int, stopChildIndex:int, t:Object):void; 240 241 242 // Code - generator support - TODO place in separate namespace 243 244 /** 245 * Private method used by generated code. Based on type and number of arguments will call one of: 246 * 247 * * createWithPayload 248 * * createFromToken 249 * * createFromType 250 */ 251 function create(... args):Object; 252 } 253 }
