1/** A generic tree implementation with no payload. You must subclass to 2 * actually have any user data. ANTLR v3 uses a list of children approach 3 * instead of the child-sibling approach in v2. A flat tree (a list) is 4 * an empty node whose children represent the list. An empty, but 5 * non-null node is called "nil". 6 */ 7org.antlr.runtime.tree.BaseTree = function() {}; 8 9org.antlr.lang.extend(org.antlr.runtime.tree.BaseTree, 10 org.antlr.runtime.tree.Tree, 11{ 12 getChild: function(i) { 13 if ( !this.children || i>=this.children.length ) { 14 return null; 15 } 16 return this.children[i]; 17 }, 18 19 /** Get the children internal List; note that if you directly mess with 20 * the list, do so at your own risk. 21 */ 22 getChildren: function() { 23 return this.children; 24 }, 25 26 getFirstChildWithType: function(type) { 27 var i, t; 28 for (i = 0; this.children && i < this.children.length; i++) { 29 t = this.children[i]; 30 if ( t.getType()===type ) { 31 return t; 32 } 33 } 34 return null; 35 }, 36 37 getChildCount: function() { 38 if ( !this.children ) { 39 return 0; 40 } 41 return this.children.length; 42 }, 43 44 /** Add t as child of this node. 45 * 46 * Warning: if t has no children, but child does 47 * and child isNil then this routine moves children to t via 48 * t.children = child.children; i.e., without copying the array. 49 */ 50 addChild: function(t) { 51 if ( !org.antlr.lang.isValue(t) ) { 52 return; // do nothing upon addChild(null) 53 } 54 var childTree = t, n, i, c; 55 if ( childTree.isNil() ) { // t is an empty node possibly with children 56 if ( this.children && this.children == childTree.children ) { 57 throw new Error("attempt to add child list to itself"); 58 } 59 // just add all of childTree's children to this 60 if ( childTree.children ) { 61 if ( this.children ) { // must copy, this has children already 62 n = childTree.children.length; 63 for (i = 0; i < n; i++) { 64 c = childTree.children[i]; 65 this.children.push(c); 66 // handle double-link stuff for each child of nil root 67 c.setParent(this); 68 c.setChildIndex(this.children.length-1); 69 } 70 } 71 else { 72 // no children for this but t has children; just set pointer 73 // call general freshener routine 74 this.children = childTree.children; 75 this.freshenParentAndChildIndexes(); 76 } 77 } 78 } 79 else { // child is not nil (don't care about children) 80 if ( !this.children ) { 81 this.children = this.createChildrenList(); // create children list on demand 82 } 83 this.children.push(t); 84 childTree.setParent(this); 85 childTree.setChildIndex(this.children.length-1); 86 } 87 }, 88 89 /** Add all elements of kids list as children of this node */ 90 addChildren: function(kids) { 91 var i, t; 92 for (i = 0; i < kids.length; i++) { 93 t = kids[i]; 94 this.addChild(t); 95 } 96 }, 97 98 setChild: function(i, t) { 99 if ( !t ) { 100 return; 101 } 102 if ( t.isNil() ) { 103 throw new Error("Can't set single child to a list"); 104 } 105 if ( !this.children ) { 106 this.children = this.createChildrenList(); 107 } 108 this.children[i] = t; 109 t.setParent(this); 110 t.setChildIndex(i); 111 }, 112 113 deleteChild: function(i) { 114 if ( !this.children ) { 115 return null; 116 } 117 if (i<0 || i>=this.children.length) { 118 throw new Error("Index out of bounds."); 119 } 120 var killed = this.children.splice(i, 1)[0]; 121 // walk rest and decrement their child indexes 122 this.freshenParentAndChildIndexes(i); 123 return killed; 124 }, 125 126 /** Delete children from start to stop and replace with t even if t is 127 * a list (nil-root tree). num of children can increase or decrease. 128 * For huge child lists, inserting children can force walking rest of 129 * children to set their childindex; could be slow. 130 */ 131 replaceChildren: function(startChildIndex, stopChildIndex, t) { 132 if ( !this.children ) { 133 throw new Error("indexes invalid; no children in list"); 134 } 135 var replacingHowMany = stopChildIndex - startChildIndex + 1; 136 var replacingWithHowMany; 137 var newTree = t; 138 var newChildren = null; 139 // normalize to a list of children to add: newChildren 140 if ( newTree.isNil() ) { 141 newChildren = newTree.children; 142 } 143 else { 144 newChildren = []; 145 newChildren.push(newTree); 146 } 147 replacingWithHowMany = newChildren.length; 148 var numNewChildren = newChildren.length; 149 var delta = replacingHowMany - replacingWithHowMany; 150 var j, i, child, indexToDelete, c, killed, numToInsert; 151 // if same number of nodes, do direct replace 152 if ( delta === 0 ) { 153 j = 0; // index into new children 154 for (i=startChildIndex; i<=stopChildIndex; i++) { 155 child = newChildren[j]; 156 this.children[i] = child; 157 child.setParent(this); 158 child.setChildIndex(i); 159 j++; 160 } 161 } 162 else if ( delta > 0 ) { // fewer new nodes than there were 163 // set children and then delete extra 164 for (j=0; j<numNewChildren; j++) { 165 this.children[startChildIndex+j] = newChildren[j]; 166 } 167 indexToDelete = startChildIndex+numNewChildren; 168 for (c=indexToDelete; c<=stopChildIndex; c++) { 169 // delete same index, shifting everybody down each time 170 killed = this.children.splice(indexToDelete, 1)[0]; 171 } 172 this.freshenParentAndChildIndexes(startChildIndex); 173 } 174 else { // more new nodes than were there before 175 // fill in as many children as we can (replacingHowMany) w/o moving data 176 for (j=0; j<replacingHowMany; j++) { 177 this.children[startChildIndex+j] = newChildren[j]; 178 } 179 numToInsert = replacingWithHowMany-replacingHowMany; 180 for (j=replacingHowMany; j<replacingWithHowMany; j++) { 181 this.children.splice(startChildIndex+j, 0, newChildren[j]); 182 } 183 this.freshenParentAndChildIndexes(startChildIndex); 184 } 185 }, 186 187 /** Override in a subclass to change the impl of children list */ 188 createChildrenList: function() { 189 return []; 190 }, 191 192 isNil: function() { 193 return false; 194 }, 195 196 freshenParentAndChildIndexes: function(offset) { 197 if (!org.antlr.lang.isNumber(offset)) { 198 offset = 0; 199 } 200 var n = this.getChildCount(), 201 c, 202 child; 203 for (c = offset; c < n; c++) { 204 child = this.getChild(c); 205 child.setChildIndex(c); 206 child.setParent(this); 207 } 208 }, 209 210 sanityCheckParentAndChildIndexes: function(parent, i) { 211 if (arguments.length===0) { 212 parent = null; 213 i = -1; 214 } 215 216 if ( parent!==this.getParent() ) { 217 throw new Error("parents don't match; expected "+parent+" found "+this.getParent()); 218 } 219 if ( i!==this.getChildIndex() ) { 220 throw new Error("child indexes don't match; expected "+i+" found "+this.getChildIndex()); 221 } 222 var n = this.getChildCount(), 223 c, 224 child; 225 for (c = 0; c < n; c++) { 226 child = this.getChild(c); 227 child.sanityCheckParentAndChildIndexes(this, c); 228 } 229 }, 230 231 /** BaseTree doesn't track child indexes. */ 232 getChildIndex: function() { 233 return 0; 234 }, 235 setChildIndex: function(index) { 236 }, 237 238 /** BaseTree doesn't track parent pointers. */ 239 getParent: function() { 240 return null; 241 }, 242 setParent: function(t) { 243 }, 244 245 getTree: function() { 246 return this; 247 }, 248 249 /** Print out a whole tree not just a node */ 250 toStringTree: function() { 251 if ( !this.children || this.children.length===0 ) { 252 return this.toString(); 253 } 254 var buf = "", 255 i, 256 t; 257 if ( !this.isNil() ) { 258 buf += "("; 259 buf += this.toString(); 260 buf += ' '; 261 } 262 for (i = 0; this.children && i < this.children.length; i++) { 263 t = this.children[i]; 264 if ( i>0 ) { 265 buf += ' '; 266 } 267 buf += t.toStringTree(); 268 } 269 if ( !this.isNil() ) { 270 buf += ")"; 271 } 272 return buf; 273 }, 274 275 getLine: function() { 276 return 0; 277 }, 278 279 getCharPositionInLine: function() { 280 return 0; 281 } 282}); 283