1/* 2 * [The "BSD licence"] 3 * Copyright (c) 2011 Terence Parr 4 * All rights reserved. 5 * 6 * Conversion to C#: 7 * Copyright (c) 2011 Sam Harwell, Pixel Mine, Inc. 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. The name of the author may not be used to endorse or promote products 19 * derived from this software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 22 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 23 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 24 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 26 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 30 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33namespace Antlr.Runtime.Tree 34{ 35 36 /** <summary> 37 * How to create and navigate trees. Rather than have a separate factory 38 * and adaptor, I've merged them. Makes sense to encapsulate. 39 * </summary> 40 * 41 * <remarks> 42 * This takes the place of the tree construction code generated in the 43 * generated code in 2.x and the ASTFactory. 44 * 45 * I do not need to know the type of a tree at all so they are all 46 * generic Objects. This may increase the amount of typecasting needed. :( 47 * </remarks> 48 */ 49 public interface ITreeAdaptor 50 { 51 #region Construction 52 53 /** <summary> 54 * Create a tree node from Token object; for CommonTree type trees, 55 * then the token just becomes the payload. This is the most 56 * common create call. 57 * </summary> 58 * 59 * <remarks> 60 * Override if you want another kind of node to be built. 61 * </remarks> 62 */ 63 object Create(IToken payload); 64 65 /** <summary> 66 * Create a new node derived from a token, with a new token type. 67 * This is invoked from an imaginary node ref on right side of a 68 * rewrite rule as IMAG[$tokenLabel]. 69 * </summary> 70 * 71 * <remarks> 72 * This should invoke createToken(Token). 73 * </remarks> 74 */ 75 object Create(int tokenType, IToken fromToken); 76 77 /** <summary> 78 * Same as create(tokenType,fromToken) except set the text too. 79 * This is invoked from an imaginary node ref on right side of a 80 * rewrite rule as IMAG[$tokenLabel, "IMAG"]. 81 * </summary> 82 * 83 * <remarks> 84 * This should invoke createToken(Token). 85 * </remarks> 86 */ 87 object Create(int tokenType, IToken fromToken, string text); 88 89 /** <summary> 90 * Same as create(fromToken) except set the text too. 91 * This is invoked when the <c>text</c> terminal option is set, as in 92 * IMAG<text='IMAG'>. 93 * </summary> 94 * 95 * <remarks> 96 * This should invoke createToken(Token). 97 * </remarks> 98 */ 99 object Create(IToken fromToken, string text); 100 101 /** <summary> 102 * Create a new node derived from a token, with a new token type. 103 * This is invoked from an imaginary node ref on right side of a 104 * rewrite rule as IMAG["IMAG"]. 105 * </summary> 106 * 107 * <remarks> 108 * This should invoke createToken(int,String). 109 * </remarks> 110 */ 111 object Create(int tokenType, string text); 112 113 /** <summary>Duplicate a single tree node.</summary> 114 * <remarks>Override if you want another kind of node to be built.</remarks> 115 */ 116 object DupNode(object treeNode); 117 118 object DupNode(int type, object treeNode); 119 120 object DupNode(object treeNode, string text); 121 122 object DupNode(int type, object treeNode, string text); 123 124 /** <summary>Duplicate tree recursively, using dupNode() for each node</summary> */ 125 object DupTree( object tree ); 126 127 /** <summary> 128 * Return a nil node (an empty but non-null node) that can hold 129 * a list of element as the children. If you want a flat tree (a list) 130 * use "t=adaptor.nil(); t.addChild(x); t.addChild(y);" 131 * </summary> 132 */ 133 object Nil(); 134 135 /** <summary> 136 * Return a tree node representing an error. This node records the 137 * tokens consumed during error recovery. The start token indicates the 138 * input symbol at which the error was detected. The stop token indicates 139 * the last symbol consumed during recovery. 140 * </summary> 141 * 142 * </remarks> 143 * You must specify the input stream so that the erroneous text can 144 * be packaged up in the error node. The exception could be useful 145 * to some applications; default implementation stores ptr to it in 146 * the CommonErrorNode. 147 * 148 * This only makes sense during token parsing, not tree parsing. 149 * Tree parsing should happen only when parsing and tree construction 150 * succeed. 151 * </remarks> 152 */ 153 object ErrorNode( ITokenStream input, IToken start, IToken stop, RecognitionException e ); 154 155 /** <summary>Is tree considered a nil node used to make lists of child nodes?</summary> */ 156 bool IsNil( object tree ); 157 158 /** <summary> 159 * Add a child to the tree t. If child is a flat tree (a list), make all 160 * in list children of t. Warning: if t has no children, but child does 161 * and child isNil then you can decide it is ok to move children to t via 162 * t.children = child.children; i.e., without copying the array. Just 163 * make sure that this is consistent with have the user will build 164 * ASTs. Do nothing if t or child is null. 165 * </summary> 166 */ 167 void AddChild( object t, object child ); 168 169 /** <summary> 170 * If oldRoot is a nil root, just copy or move the children to newRoot. 171 * If not a nil root, make oldRoot a child of newRoot. 172 * </summary> 173 * 174 * <remarks> 175 * old=^(nil a b c), new=r yields ^(r a b c) 176 * old=^(a b c), new=r yields ^(r ^(a b c)) 177 * 178 * If newRoot is a nil-rooted single child tree, use the single 179 * child as the new root node. 180 * 181 * old=^(nil a b c), new=^(nil r) yields ^(r a b c) 182 * old=^(a b c), new=^(nil r) yields ^(r ^(a b c)) 183 * 184 * If oldRoot was null, it's ok, just return newRoot (even if isNil). 185 * 186 * old=null, new=r yields r 187 * old=null, new=^(nil r) yields ^(nil r) 188 * 189 * Return newRoot. Throw an exception if newRoot is not a 190 * simple node or nil root with a single child node--it must be a root 191 * node. If newRoot is ^(nil x) return x as newRoot. 192 * 193 * Be advised that it's ok for newRoot to point at oldRoot's 194 * children; i.e., you don't have to copy the list. We are 195 * constructing these nodes so we should have this control for 196 * efficiency. 197 * </remarks> 198 */ 199 object BecomeRoot( object newRoot, object oldRoot ); 200 201 /** <summary> 202 * Given the root of the subtree created for this rule, post process 203 * it to do any simplifications or whatever you want. A required 204 * behavior is to convert ^(nil singleSubtree) to singleSubtree 205 * as the setting of start/stop indexes relies on a single non-nil root 206 * for non-flat trees. 207 * </summary> 208 * 209 * <remarks> 210 * Flat trees such as for lists like "idlist : ID+ ;" are left alone 211 * unless there is only one ID. For a list, the start/stop indexes 212 * are set in the nil node. 213 * 214 * This method is executed after all rule tree construction and right 215 * before setTokenBoundaries(). 216 * </remarks> 217 */ 218 object RulePostProcessing( object root ); 219 220 /** <summary>For identifying trees.</summary> 221 * 222 * <remarks> 223 * How to identify nodes so we can say "add node to a prior node"? 224 * Even becomeRoot is an issue. Use System.identityHashCode(node) 225 * usually. 226 * </remarks> 227 */ 228 int GetUniqueID( object node ); 229 230 231 // R e w r i t e R u l e s 232 233 /** <summary> 234 * Create a node for newRoot make it the root of oldRoot. 235 * If oldRoot is a nil root, just copy or move the children to newRoot. 236 * If not a nil root, make oldRoot a child of newRoot. 237 * </summary> 238 * 239 * <returns> 240 * Return node created for newRoot. 241 * </returns> 242 * 243 * <remarks> 244 * Be advised: when debugging ASTs, the DebugTreeAdaptor manually 245 * calls create(Token child) and then plain becomeRoot(node, node) 246 * because it needs to trap calls to create, but it can't since it delegates 247 * to not inherits from the TreeAdaptor. 248 * </remarks> 249 */ 250 object BecomeRoot( IToken newRoot, object oldRoot ); 251 252 #endregion 253 254 255 #region Content 256 257 /** <summary>For tree parsing, I need to know the token type of a node</summary> */ 258 int GetType( object t ); 259 260 /** <summary>Node constructors can set the type of a node</summary> */ 261 void SetType( object t, int type ); 262 263 string GetText( object t ); 264 265 /** <summary>Node constructors can set the text of a node</summary> */ 266 void SetText( object t, string text ); 267 268 /** <summary> 269 * Return the token object from which this node was created. 270 * Currently used only for printing an error message. 271 * The error display routine in BaseRecognizer needs to 272 * display where the input the error occurred. If your 273 * tree of limitation does not store information that can 274 * lead you to the token, you can create a token filled with 275 * the appropriate information and pass that back. See 276 * BaseRecognizer.getErrorMessage(). 277 * </summary> 278 */ 279 IToken GetToken( object t ); 280 281 /** <summary> 282 * Where are the bounds in the input token stream for this node and 283 * all children? Each rule that creates AST nodes will call this 284 * method right before returning. Flat trees (i.e., lists) will 285 * still usually have a nil root node just to hold the children list. 286 * That node would contain the start/stop indexes then. 287 * </summary> 288 */ 289 void SetTokenBoundaries( object t, IToken startToken, IToken stopToken ); 290 291 /** <summary>Get the token start index for this subtree; return -1 if no such index</summary> */ 292 int GetTokenStartIndex( object t ); 293 294 /** <summary>Get the token stop index for this subtree; return -1 if no such index</summary> */ 295 int GetTokenStopIndex( object t ); 296 297 #endregion 298 299 300 #region Navigation / Tree Parsing 301 302 /** <summary>Get a child 0..n-1 node</summary> */ 303 object GetChild( object t, int i ); 304 305 /** <summary>Set ith child (0..n-1) to t; t must be non-null and non-nil node</summary> */ 306 void SetChild( object t, int i, object child ); 307 308 /** <summary>Remove ith child and shift children down from right.</summary> */ 309 object DeleteChild( object t, int i ); 310 311 /** <summary>How many children? If 0, then this is a leaf node</summary> */ 312 int GetChildCount( object t ); 313 314 /** <summary> 315 * Who is the parent node of this node; if null, implies node is root. 316 * If your node type doesn't handle this, it's ok but the tree rewrites 317 * in tree parsers need this functionality. 318 * </summary> 319 */ 320 object GetParent( object t ); 321 void SetParent( object t, object parent ); 322 323 /** <summary> 324 * What index is this node in the child list? Range: 0..n-1 325 * If your node type doesn't handle this, it's ok but the tree rewrites 326 * in tree parsers need this functionality. 327 * </summary> 328 */ 329 int GetChildIndex( object t ); 330 void SetChildIndex( object t, int index ); 331 332 /** <summary> 333 * Replace from start to stop child index of parent with t, which might 334 * be a list. Number of children may be different after this call. 335 * </summary> 336 * 337 * <remarks> 338 * If parent is null, don't do anything; must be at root of overall tree. 339 * Can't replace whatever points to the parent externally. Do nothing. 340 * </remarks> 341 */ 342 void ReplaceChildren( object parent, int startChildIndex, int stopChildIndex, object t ); 343 344 #endregion 345 } 346} 347