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 33 namespace Antlr.Runtime.Tree 34 { 35 using System.Collections.Generic; 36 37 using ArgumentNullException = System.ArgumentNullException; 38 using Exception = System.Exception; 39 using IDictionary = System.Collections.IDictionary; 40 using NotSupportedException = System.NotSupportedException; 41 42 /** <summary>A TreeAdaptor that works with any Tree implementation.</summary> */ 43 public abstract class BaseTreeAdaptor : ITreeAdaptor 44 { 45 /** <summary> 46 * System.identityHashCode() is not always unique; we have to 47 * track ourselves. That's ok, it's only for debugging, though it's 48 * expensive: we have to create a hashtable with all tree nodes in it. 49 * </summary> 50 */ 51 protected IDictionary<object, int> treeToUniqueIDMap; 52 protected int uniqueNodeID = 1; 53 Nil()54 public virtual object Nil() 55 { 56 return Create( null ); 57 } 58 59 /** <summary> 60 * Create tree node that holds the start and stop tokens associated 61 * with an error. 62 * </summary> 63 * 64 * <remarks> 65 * If you specify your own kind of tree nodes, you will likely have to 66 * override this method. CommonTree returns Token.INVALID_TOKEN_TYPE 67 * if no token payload but you might have to set token type for diff 68 * node type. 69 * 70 * You don't have to subclass CommonErrorNode; you will likely need to 71 * subclass your own tree node class to avoid class cast exception. 72 * </remarks> 73 */ ErrorNode( ITokenStream input, IToken start, IToken stop, RecognitionException e )74 public virtual object ErrorNode( ITokenStream input, IToken start, IToken stop, 75 RecognitionException e ) 76 { 77 CommonErrorNode t = new CommonErrorNode( input, start, stop, e ); 78 //System.out.println("returning error node '"+t+"' @index="+input.index()); 79 return t; 80 } 81 IsNil( object tree )82 public virtual bool IsNil( object tree ) 83 { 84 return ( (ITree)tree ).IsNil; 85 } 86 DupNode(int type, object treeNode)87 public virtual object DupNode(int type, object treeNode) 88 { 89 object t = DupNode(treeNode); 90 SetType(t, type); 91 return t; 92 } 93 DupNode(object treeNode, string text)94 public virtual object DupNode(object treeNode, string text) 95 { 96 object t = DupNode(treeNode); 97 SetText(t, text); 98 return t; 99 } 100 DupNode(int type, object treeNode, string text)101 public virtual object DupNode(int type, object treeNode, string text) 102 { 103 object t = DupNode(treeNode); 104 SetType(t, type); 105 SetText(t, text); 106 return t; 107 } 108 DupTree( object tree )109 public virtual object DupTree( object tree ) 110 { 111 return DupTree( tree, null ); 112 } 113 114 /** <summary> 115 * This is generic in the sense that it will work with any kind of 116 * tree (not just ITree interface). It invokes the adaptor routines 117 * not the tree node routines to do the construction. 118 * </summary> 119 */ DupTree( object t, object parent )120 public virtual object DupTree( object t, object parent ) 121 { 122 if ( t == null ) 123 { 124 return null; 125 } 126 object newTree = DupNode( t ); 127 // ensure new subtree root has parent/child index set 128 SetChildIndex( newTree, GetChildIndex( t ) ); // same index in new tree 129 SetParent( newTree, parent ); 130 int n = GetChildCount( t ); 131 for ( int i = 0; i < n; i++ ) 132 { 133 object child = GetChild( t, i ); 134 object newSubTree = DupTree( child, t ); 135 AddChild( newTree, newSubTree ); 136 } 137 return newTree; 138 } 139 140 /** <summary> 141 * Add a child to the tree t. If child is a flat tree (a list), make all 142 * in list children of t. Warning: if t has no children, but child does 143 * and child isNil then you can decide it is ok to move children to t via 144 * t.children = child.children; i.e., without copying the array. Just 145 * make sure that this is consistent with have the user will build 146 * ASTs. 147 * </summary> 148 */ AddChild( object t, object child )149 public virtual void AddChild( object t, object child ) 150 { 151 if ( t != null && child != null ) 152 { 153 ( (ITree)t ).AddChild( (ITree)child ); 154 } 155 } 156 157 /** <summary> 158 * If oldRoot is a nil root, just copy or move the children to newRoot. 159 * If not a nil root, make oldRoot a child of newRoot. 160 * </summary> 161 * 162 * <remarks> 163 * old=^(nil a b c), new=r yields ^(r a b c) 164 * old=^(a b c), new=r yields ^(r ^(a b c)) 165 * 166 * If newRoot is a nil-rooted single child tree, use the single 167 * child as the new root node. 168 * 169 * old=^(nil a b c), new=^(nil r) yields ^(r a b c) 170 * old=^(a b c), new=^(nil r) yields ^(r ^(a b c)) 171 * 172 * If oldRoot was null, it's ok, just return newRoot (even if isNil). 173 * 174 * old=null, new=r yields r 175 * old=null, new=^(nil r) yields ^(nil r) 176 * 177 * Return newRoot. Throw an exception if newRoot is not a 178 * simple node or nil root with a single child node--it must be a root 179 * node. If newRoot is ^(nil x) return x as newRoot. 180 * 181 * Be advised that it's ok for newRoot to point at oldRoot's 182 * children; i.e., you don't have to copy the list. We are 183 * constructing these nodes so we should have this control for 184 * efficiency. 185 * </remarks> 186 */ BecomeRoot( object newRoot, object oldRoot )187 public virtual object BecomeRoot( object newRoot, object oldRoot ) 188 { 189 //System.out.println("becomeroot new "+newRoot.toString()+" old "+oldRoot); 190 ITree newRootTree = (ITree)newRoot; 191 ITree oldRootTree = (ITree)oldRoot; 192 if ( oldRoot == null ) 193 { 194 return newRoot; 195 } 196 // handle ^(nil real-node) 197 if ( newRootTree.IsNil ) 198 { 199 int nc = newRootTree.ChildCount; 200 if ( nc == 1 ) 201 newRootTree = (ITree)newRootTree.GetChild( 0 ); 202 else if ( nc > 1 ) 203 { 204 // TODO: make tree run time exceptions hierarchy 205 throw new Exception( "more than one node as root (TODO: make exception hierarchy)" ); 206 } 207 } 208 // add oldRoot to newRoot; addChild takes care of case where oldRoot 209 // is a flat list (i.e., nil-rooted tree). All children of oldRoot 210 // are added to newRoot. 211 newRootTree.AddChild( oldRootTree ); 212 return newRootTree; 213 } 214 215 /** <summary>Transform ^(nil x) to x and nil to null</summary> */ RulePostProcessing( object root )216 public virtual object RulePostProcessing( object root ) 217 { 218 //System.out.println("rulePostProcessing: "+((Tree)root).toStringTree()); 219 ITree r = (ITree)root; 220 if ( r != null && r.IsNil ) 221 { 222 if ( r.ChildCount == 0 ) 223 { 224 r = null; 225 } 226 else if ( r.ChildCount == 1 ) 227 { 228 r = (ITree)r.GetChild( 0 ); 229 // whoever invokes rule will set parent and child index 230 r.Parent = null; 231 r.ChildIndex = -1; 232 } 233 } 234 return r; 235 } 236 BecomeRoot( IToken newRoot, object oldRoot )237 public virtual object BecomeRoot( IToken newRoot, object oldRoot ) 238 { 239 return BecomeRoot( Create( newRoot ), oldRoot ); 240 } 241 Create( int tokenType, IToken fromToken )242 public virtual object Create( int tokenType, IToken fromToken ) 243 { 244 fromToken = CreateToken( fromToken ); 245 fromToken.Type = tokenType; 246 object t = Create( fromToken ); 247 return t; 248 } 249 Create( int tokenType, IToken fromToken, string text )250 public virtual object Create( int tokenType, IToken fromToken, string text ) 251 { 252 if ( fromToken == null ) 253 return Create( tokenType, text ); 254 255 fromToken = CreateToken( fromToken ); 256 fromToken.Type = tokenType; 257 fromToken.Text = text; 258 object result = Create(fromToken); 259 return result; 260 } 261 Create(IToken fromToken, string text)262 public virtual object Create(IToken fromToken, string text) 263 { 264 if (fromToken == null) 265 throw new ArgumentNullException("fromToken"); 266 267 fromToken = CreateToken(fromToken); 268 fromToken.Text = text; 269 object result = Create(fromToken); 270 return result; 271 } 272 Create( int tokenType, string text )273 public virtual object Create( int tokenType, string text ) 274 { 275 IToken fromToken = CreateToken( tokenType, text ); 276 object t = Create( fromToken ); 277 return t; 278 } 279 GetType( object t )280 public virtual int GetType( object t ) 281 { 282 ITree tree = GetTree(t); 283 if (tree == null) 284 return TokenTypes.Invalid; 285 286 return tree.Type; 287 } 288 SetType( object t, int type )289 public virtual void SetType( object t, int type ) 290 { 291 throw new NotSupportedException( "don't know enough about Tree node" ); 292 } 293 GetText( object t )294 public virtual string GetText( object t ) 295 { 296 ITree tree = GetTree(t); 297 if (tree == null) 298 return null; 299 300 return tree.Text; 301 } 302 SetText( object t, string text )303 public virtual void SetText( object t, string text ) 304 { 305 throw new NotSupportedException( "don't know enough about Tree node" ); 306 } 307 GetChild( object t, int i )308 public virtual object GetChild( object t, int i ) 309 { 310 ITree tree = GetTree(t); 311 if (tree == null) 312 return null; 313 314 return tree.GetChild(i); 315 } 316 SetChild( object t, int i, object child )317 public virtual void SetChild( object t, int i, object child ) 318 { 319 ITree tree = GetTree(t); 320 if (tree == null) 321 return; 322 323 ITree childTree = GetTree(child); 324 tree.SetChild(i, childTree); 325 } 326 DeleteChild( object t, int i )327 public virtual object DeleteChild( object t, int i ) 328 { 329 return ( (ITree)t ).DeleteChild( i ); 330 } 331 GetChildCount( object t )332 public virtual int GetChildCount( object t ) 333 { 334 ITree tree = GetTree(t); 335 if (tree == null) 336 return 0; 337 338 return tree.ChildCount; 339 } 340 GetUniqueID( object node )341 public virtual int GetUniqueID( object node ) 342 { 343 if ( treeToUniqueIDMap == null ) 344 { 345 treeToUniqueIDMap = new Dictionary<object, int>(); 346 } 347 int id; 348 if ( treeToUniqueIDMap.TryGetValue( node, out id ) ) 349 return id; 350 351 id = uniqueNodeID; 352 treeToUniqueIDMap[node] = id; 353 uniqueNodeID++; 354 return id; 355 // GC makes these nonunique: 356 // return System.identityHashCode(node); 357 } 358 359 /** <summary> 360 * Tell me how to create a token for use with imaginary token nodes. 361 * For example, there is probably no input symbol associated with imaginary 362 * token DECL, but you need to create it as a payload or whatever for 363 * the DECL node as in ^(DECL type ID). 364 * </summary> 365 * 366 * <remarks> 367 * If you care what the token payload objects' type is, you should 368 * override this method and any other createToken variant. 369 * </remarks> 370 */ CreateToken( int tokenType, string text )371 public abstract IToken CreateToken( int tokenType, string text ); 372 373 /** <summary> 374 * Tell me how to create a token for use with imaginary token nodes. 375 * For example, there is probably no input symbol associated with imaginary 376 * token DECL, but you need to create it as a payload or whatever for 377 * the DECL node as in ^(DECL type ID). 378 * </summary> 379 * 380 * <remarks> 381 * This is a variant of createToken where the new token is derived from 382 * an actual real input token. Typically this is for converting '{' 383 * tokens to BLOCK etc... You'll see 384 * 385 * r : lc='{' ID+ '}' -> ^(BLOCK[$lc] ID+) ; 386 * 387 * If you care what the token payload objects' type is, you should 388 * override this method and any other createToken variant. 389 * </remarks> 390 */ CreateToken( IToken fromToken )391 public abstract IToken CreateToken( IToken fromToken ); 392 Create( IToken payload )393 public abstract object Create( IToken payload ); 394 395 /** <summary> 396 * Duplicate a node. This is part of the factory; 397 * override if you want another kind of node to be built. 398 * </summary> 399 * 400 * <remarks> 401 * I could use reflection to prevent having to override this 402 * but reflection is slow. 403 * </remarks> 404 */ DupNode(object treeNode)405 public virtual object DupNode(object treeNode) 406 { 407 ITree tree = GetTree(treeNode); 408 if (tree == null) 409 return null; 410 411 return tree.DupNode(); 412 } 413 GetToken( object t )414 public abstract IToken GetToken( object t ); 415 416 /** <summary> 417 * Track start/stop token for subtree root created for a rule. 418 * Only works with Tree nodes. For rules that match nothing, 419 * seems like this will yield start=i and stop=i-1 in a nil node. 420 * Might be useful info so I'll not force to be i..i. 421 * </summary> 422 */ SetTokenBoundaries(object t, IToken startToken, IToken stopToken)423 public virtual void SetTokenBoundaries(object t, IToken startToken, IToken stopToken) 424 { 425 ITree tree = GetTree(t); 426 if (tree == null) 427 return; 428 429 int start = 0; 430 int stop = 0; 431 432 if (startToken != null) 433 start = startToken.TokenIndex; 434 if (stopToken != null) 435 stop = stopToken.TokenIndex; 436 437 tree.TokenStartIndex = start; 438 tree.TokenStopIndex = stop; 439 } 440 GetTokenStartIndex(object t)441 public virtual int GetTokenStartIndex(object t) 442 { 443 ITree tree = GetTree(t); 444 if (tree == null) 445 return -1; 446 447 return tree.TokenStartIndex; 448 } 449 GetTokenStopIndex(object t)450 public virtual int GetTokenStopIndex(object t) 451 { 452 ITree tree = GetTree(t); 453 if (tree == null) 454 return -1; 455 456 return tree.TokenStopIndex; 457 } 458 GetParent(object t)459 public virtual object GetParent(object t) 460 { 461 ITree tree = GetTree(t); 462 if (tree == null) 463 return null; 464 465 return tree.Parent; 466 } 467 SetParent(object t, object parent)468 public virtual void SetParent(object t, object parent) 469 { 470 ITree tree = GetTree(t); 471 if (tree == null) 472 return; 473 474 ITree parentTree = GetTree(parent); 475 tree.Parent = parentTree; 476 } 477 GetChildIndex(object t)478 public virtual int GetChildIndex(object t) 479 { 480 ITree tree = GetTree(t); 481 if (tree == null) 482 return 0; 483 484 return tree.ChildIndex; 485 } 486 SetChildIndex(object t, int index)487 public virtual void SetChildIndex(object t, int index) 488 { 489 ITree tree = GetTree(t); 490 if (tree == null) 491 return; 492 493 tree.ChildIndex = index; 494 } 495 ReplaceChildren(object parent, int startChildIndex, int stopChildIndex, object t)496 public virtual void ReplaceChildren(object parent, int startChildIndex, int stopChildIndex, object t) 497 { 498 ITree tree = GetTree(parent); 499 if (tree == null) 500 return; 501 502 tree.ReplaceChildren(startChildIndex, stopChildIndex, t); 503 } 504 GetTree(object t)505 protected virtual ITree GetTree(object t) 506 { 507 if (t == null) 508 return null; 509 510 ITree tree = t as ITree; 511 if (tree == null) 512 throw new NotSupportedException(); 513 514 return tree; 515 } 516 } 517 } 518