1 /* 2 [The "BSD license"] 3 Copyright (c) 2005-2009 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.Token; 31 import org.antlr.runtime.TokenStream; 32 import org.antlr.runtime.RecognitionException; 33 34 import java.util.HashMap; 35 import java.util.Map; 36 37 /** A TreeAdaptor that works with any Tree implementation. */ 38 public abstract class BaseTreeAdaptor implements TreeAdaptor { 39 /** System.identityHashCode() is not always unique; we have to 40 * track ourselves. That's ok, it's only for debugging, though it's 41 * expensive: we have to create a hashtable with all tree nodes in it. 42 */ 43 protected Map<Object, Integer> treeToUniqueIDMap; 44 protected int uniqueNodeID = 1; 45 46 @Override 47 public Object nil() { 48 return create(null); 49 } 50 51 /** create tree node that holds the start and stop tokens associated 52 * with an error. 53 * 54 * If you specify your own kind of tree nodes, you will likely have to 55 * override this method. CommonTree returns Token.INVALID_TOKEN_TYPE 56 * if no token payload but you might have to set token type for diff 57 * node type. 58 * 59 * You don't have to subclass CommonErrorNode; you will likely need to 60 * subclass your own tree node class to avoid class cast exception. 61 */ 62 @Override 63 public Object errorNode(TokenStream input, Token start, Token stop, 64 RecognitionException e) 65 { 66 CommonErrorNode t = new CommonErrorNode(input, start, stop, e); 67 //System.out.println("returning error node '"+t+"' @index="+input.index()); 68 return t; 69 } 70 71 @Override 72 public boolean isNil(Object tree) { 73 return ((Tree)tree).isNil(); 74 } 75 76 @Override 77 public Object dupTree(Object tree) { 78 return dupTree(tree, null); 79 } 80 81 /** This is generic in the sense that it will work with any kind of 82 * tree (not just Tree interface). It invokes the adaptor routines 83 * not the tree node routines to do the construction. 84 */ 85 public Object dupTree(Object t, Object parent) { 86 if ( t==null ) { 87 return null; 88 } 89 Object newTree = dupNode(t); 90 // ensure new subtree root has parent/child index set 91 setChildIndex(newTree, getChildIndex(t)); // same index in new tree 92 setParent(newTree, parent); 93 int n = getChildCount(t); 94 for (int i = 0; i < n; i++) { 95 Object child = getChild(t, i); 96 Object newSubTree = dupTree(child, t); 97 addChild(newTree, newSubTree); 98 } 99 return newTree; 100 } 101 102 /** Add a child to the tree t. If child is a flat tree (a list), make all 103 * in list children of t. Warning: if t has no children, but child does 104 * and child isNil then you can decide it is ok to move children to t via 105 * t.children = child.children; i.e., without copying the array. Just 106 * make sure that this is consistent with have the user will build 107 * ASTs. 108 */ 109 @Override 110 public void addChild(Object t, Object child) { 111 if ( t!=null && child!=null ) { 112 ((Tree)t).addChild((Tree)child); 113 } 114 } 115 116 /** If oldRoot is a nil root, just copy or move the children to newRoot. 117 * If not a nil root, make oldRoot a child of newRoot. 118 * 119 * old=^(nil a b c), new=r yields ^(r a b c) 120 * old=^(a b c), new=r yields ^(r ^(a b c)) 121 * 122 * If newRoot is a nil-rooted single child tree, use the single 123 * child as the new root node. 124 * 125 * old=^(nil a b c), new=^(nil r) yields ^(r a b c) 126 * old=^(a b c), new=^(nil r) yields ^(r ^(a b c)) 127 * 128 * If oldRoot was null, it's ok, just return newRoot (even if isNil). 129 * 130 * old=null, new=r yields r 131 * old=null, new=^(nil r) yields ^(nil r) 132 * 133 * Return newRoot. Throw an exception if newRoot is not a 134 * simple node or nil root with a single child node--it must be a root 135 * node. If newRoot is ^(nil x) return x as newRoot. 136 * 137 * Be advised that it's ok for newRoot to point at oldRoot's 138 * children; i.e., you don't have to copy the list. We are 139 * constructing these nodes so we should have this control for 140 * efficiency. 141 */ 142 @Override 143 public Object becomeRoot(Object newRoot, Object oldRoot) { 144 //System.out.println("becomeroot new "+newRoot.toString()+" old "+oldRoot); 145 Tree newRootTree = (Tree)newRoot; 146 Tree oldRootTree = (Tree)oldRoot; 147 if ( oldRoot==null ) { 148 return newRoot; 149 } 150 // handle ^(nil real-node) 151 if ( newRootTree.isNil() ) { 152 int nc = newRootTree.getChildCount(); 153 if ( nc==1 ) newRootTree = newRootTree.getChild(0); 154 else if ( nc >1 ) { 155 // TODO: make tree run time exceptions hierarchy 156 throw new RuntimeException("more than one node as root (TODO: make exception hierarchy)"); 157 } 158 } 159 // add oldRoot to newRoot; addChild takes care of case where oldRoot 160 // is a flat list (i.e., nil-rooted tree). All children of oldRoot 161 // are added to newRoot. 162 newRootTree.addChild(oldRootTree); 163 return newRootTree; 164 } 165 166 /** Transform ^(nil x) to x and nil to null */ 167 @Override 168 public Object rulePostProcessing(Object root) { 169 //System.out.println("rulePostProcessing: "+((Tree)root).toStringTree()); 170 Tree r = (Tree)root; 171 if ( r!=null && r.isNil() ) { 172 if ( r.getChildCount()==0 ) { 173 r = null; 174 } 175 else if ( r.getChildCount()==1 ) { 176 r = r.getChild(0); 177 // whoever invokes rule will set parent and child index 178 r.setParent(null); 179 r.setChildIndex(-1); 180 } 181 } 182 return r; 183 } 184 185 @Override 186 public Object becomeRoot(Token newRoot, Object oldRoot) { 187 return becomeRoot(create(newRoot), oldRoot); 188 } 189 190 @Override 191 public Object create(int tokenType, Token fromToken) { 192 fromToken = createToken(fromToken); 193 //((ClassicToken)fromToken).setType(tokenType); 194 fromToken.setType(tokenType); 195 Tree t = (Tree)create(fromToken); 196 return t; 197 } 198 199 @Override 200 public Object create(int tokenType, Token fromToken, String text) { 201 if (fromToken == null) return create(tokenType, text); 202 fromToken = createToken(fromToken); 203 fromToken.setType(tokenType); 204 fromToken.setText(text); 205 Tree t = (Tree)create(fromToken); 206 return t; 207 } 208 209 @Override 210 public Object create(int tokenType, String text) { 211 Token fromToken = createToken(tokenType, text); 212 Tree t = (Tree)create(fromToken); 213 return t; 214 } 215 216 @Override 217 public int getType(Object t) { 218 return ((Tree)t).getType(); 219 } 220 221 @Override 222 public void setType(Object t, int type) { 223 throw new NoSuchMethodError("don't know enough about Tree node"); 224 } 225 226 @Override 227 public String getText(Object t) { 228 return ((Tree)t).getText(); 229 } 230 231 @Override 232 public void setText(Object t, String text) { 233 throw new NoSuchMethodError("don't know enough about Tree node"); 234 } 235 236 @Override 237 public Object getChild(Object t, int i) { 238 return ((Tree)t).getChild(i); 239 } 240 241 @Override 242 public void setChild(Object t, int i, Object child) { 243 ((Tree)t).setChild(i, (Tree)child); 244 } 245 246 @Override 247 public Object deleteChild(Object t, int i) { 248 return ((Tree)t).deleteChild(i); 249 } 250 251 @Override 252 public int getChildCount(Object t) { 253 return ((Tree)t).getChildCount(); 254 } 255 256 @Override 257 public int getUniqueID(Object node) { 258 if ( treeToUniqueIDMap==null ) { 259 treeToUniqueIDMap = new HashMap<Object, Integer>(); 260 } 261 Integer prevID = treeToUniqueIDMap.get(node); 262 if ( prevID!=null ) { 263 return prevID; 264 } 265 int ID = uniqueNodeID; 266 treeToUniqueIDMap.put(node, ID); 267 uniqueNodeID++; 268 return ID; 269 // GC makes these nonunique: 270 // return System.identityHashCode(node); 271 } 272 273 /** Tell me how to create a token for use with imaginary token nodes. 274 * For example, there is probably no input symbol associated with imaginary 275 * token DECL, but you need to create it as a payload or whatever for 276 * the DECL node as in ^(DECL type ID). 277 * 278 * If you care what the token payload objects' type is, you should 279 * override this method and any other createToken variant. 280 */ 281 public abstract Token createToken(int tokenType, String text); 282 283 /** Tell me how to create a token for use with imaginary token nodes. 284 * For example, there is probably no input symbol associated with imaginary 285 * token DECL, but you need to create it as a payload or whatever for 286 * the DECL node as in ^(DECL type ID). 287 * 288 * This is a variant of createToken where the new token is derived from 289 * an actual real input token. Typically this is for converting '{' 290 * tokens to BLOCK etc... You'll see 291 * 292 * r : lc='{' ID+ '}' -> ^(BLOCK[$lc] ID+) ; 293 * 294 * If you care what the token payload objects' type is, you should 295 * override this method and any other createToken variant. 296 */ 297 public abstract Token createToken(Token fromToken); 298 } 299 300
