1/* 2[The "BSD licence"] 3Copyright (c) 2005-2006 Terence Parr 4All rights reserved. 5 6Redistribution and use in source and binary forms, with or without 7modification, are permitted provided that the following conditions 8are met: 91. Redistributions of source code must retain the above copyright 10notice, this list of conditions and the following disclaimer. 112. Redistributions in binary form must reproduce the above copyright 12notice, this list of conditions and the following disclaimer in the 13documentation and/or other materials provided with the distribution. 143. The name of the author may not be used to endorse or promote products 15derived from this software without specific prior written permission. 16 17THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27*/ 28package org.antlr.runtime.tree { 29 30 import org.antlr.runtime.TokenConstants; 31 import org.antlr.runtime.TokenStream; 32 33 34 /** A buffered stream of tree nodes. Nodes can be from a tree of ANY kind. 35 * 36 * This node stream sucks all nodes out of the tree specified in 37 * the constructor during construction and makes pointers into 38 * the tree using an array of Object pointers. The stream necessarily 39 * includes pointers to DOWN and UP and EOF nodes. 40 * 41 * This stream knows how to mark/release for backtracking. 42 * 43 * This stream is most suitable for tree interpreters that need to 44 * jump around a lot or for tree parsers requiring speed (at cost of memory). 45 * There is some duplicated functionality here with UnBufferedTreeNodeStream 46 * but just in bookkeeping, not tree walking etc... 47 * 48 * @see UnBufferedTreeNodeStream 49 */ 50 public class CommonTreeNodeStream implements TreeNodeStream { 51 public static const DEFAULT_INITIAL_BUFFER_SIZE:int = 100; 52 public static const INITIAL_CALL_STACK_SIZE:int = 10; 53 54 // all these navigation nodes are shared and hence they 55 // cannot contain any line/column info 56 57 protected var down:Object; 58 protected var up:Object; 59 protected var eof:Object; 60 61 /** The complete mapping from stream index to tree node. 62 * This buffer includes pointers to DOWN, UP, and EOF nodes. 63 * It is built upon ctor invocation. The elements are type 64 * Object as we don't what the trees look like. 65 * 66 * Load upon first need of the buffer so we can set token types 67 * of interest for reverseIndexing. Slows us down a wee bit to 68 * do all of the if p==-1 testing everywhere though. 69 */ 70 protected var nodes:Array; 71 72 /** Pull nodes from which tree? */ 73 protected var root:Object; 74 75 /** IF this tree (root) was created from a token stream, track it. */ 76 protected var tokens:TokenStream; 77 78 /** What tree adaptor was used to build these trees */ 79 internal var adaptor:TreeAdaptor; 80 81 /** Reuse same DOWN, UP navigation nodes unless this is true */ 82 protected var uniqueNavigationNodes:Boolean = false; 83 84 /** The index into the nodes list of the current node (next node 85 * to consume). If -1, nodes array not filled yet. 86 */ 87 protected var p:int = -1; 88 89 /** Track the last mark() call result value for use in rewind(). */ 90 protected var lastMarker:int; 91 92 /** Stack of indexes used for push/pop calls */ 93 protected var calls:Array; 94 95 public function CommonTreeNodeStream(tree:Object, adaptor:TreeAdaptor = null, initialBufferSize:int = DEFAULT_INITIAL_BUFFER_SIZE) { 96 if (tree == null) { 97 // return uninitalized for static resuse function 98 return; 99 } 100 this.root = tree; 101 this.adaptor = adaptor == null ? new CommonTreeAdaptor() : adaptor; 102 103 nodes = new Array(); 104 down = this.adaptor.createFromType(TokenConstants.DOWN, "DOWN"); 105 up = this.adaptor.createFromType(TokenConstants.UP, "UP"); 106 eof = this.adaptor.createFromType(TokenConstants.EOF, "EOF"); 107 } 108 109 /** Reuse an existing node stream's buffer of nodes. Do not point at a 110 * node stream that can change. Must have static node list. start/stop 111 * are indexes into the parent.nodes stream. We avoid making a new 112 * list of nodes like this. 113 */ 114 public static function reuse(parent:CommonTreeNodeStream, start:int, stop:int):CommonTreeNodeStream { 115 var stream:CommonTreeNodeStream = new CommonTreeNodeStream(null); 116 stream.root = parent.root; 117 stream.adaptor = parent.adaptor; 118 stream.nodes = parent.nodes.slice(start, stop); 119 stream.down = parent.down; 120 stream.up = parent.up; 121 stream.eof = parent.eof; 122 return stream; 123 } 124 125 /** Walk tree with depth-first-search and fill nodes buffer. 126 * Don't do DOWN, UP nodes if its a list (t is isNil). 127 */ 128 protected function fillBuffer():void { 129 fillBufferTo(root); 130 //System.out.println("revIndex="+tokenTypeToStreamIndexesMap); 131 p = 0; // buffer of nodes intialized now 132 } 133 134 public function fillBufferTo(t:Object):void { 135 var nil:Boolean = adaptor.isNil(t); 136 if ( !nil ) { 137 nodes.push(t); // add this node 138 } 139 // add DOWN node if t has children 140 var n:int = adaptor.getChildCount(t); 141 if ( !nil && n>0 ) { 142 addNavigationNode(TokenConstants.DOWN); 143 } 144 // and now add all its children 145 for (var c:int=0; c<n; c++) { 146 var child:Object = adaptor.getChild(t,c); 147 fillBufferTo(child); 148 } 149 // add UP node if t has children 150 if ( !nil && n>0 ) { 151 addNavigationNode(TokenConstants.UP); 152 } 153 } 154 155 /** What is the stream index for node? 0..n-1 156 * Return -1 if node not found. 157 */ 158 protected function getNodeIndex(node:Object):int { 159 if ( p==-1 ) { 160 fillBuffer(); 161 } 162 for (var i:int = 0; i < nodes.length; i++) { 163 var t:Object = nodes[i]; 164 if ( t===node ) { 165 return i; 166 } 167 } 168 return -1; 169 } 170 171 /** As we flatten the tree, we use UP, DOWN nodes to represent 172 * the tree structure. When debugging we need unique nodes 173 * so instantiate new ones when uniqueNavigationNodes is true. 174 */ 175 protected function addNavigationNode(ttype:int):void { 176 var navNode:Object = null; 177 if ( ttype==TokenConstants.DOWN ) { 178 if ( hasUniqueNavigationNodes) { 179 navNode = adaptor.createFromType(TokenConstants.DOWN, "DOWN"); 180 } 181 else { 182 navNode = down; 183 } 184 } 185 else { 186 if ( hasUniqueNavigationNodes ) { 187 navNode = adaptor.createFromType(TokenConstants.UP, "UP"); 188 } 189 else { 190 navNode = up; 191 } 192 } 193 nodes.push(navNode); 194 } 195 196 public function getNode(i:int):Object { 197 if ( p==-1 ) { 198 fillBuffer(); 199 } 200 return nodes[i]; 201 } 202 203 public function LT(k:int):Object { 204 if ( p==-1 ) { 205 fillBuffer(); 206 } 207 if ( k==0 ) { 208 return null; 209 } 210 if ( k<0 ) { 211 return LB(-k); 212 } 213 //System.out.print("LT(p="+p+","+k+")="); 214 if ( (p+k-1) >= nodes.length ) { 215 return eof; 216 } 217 return nodes[p+k-1]; 218 } 219 220 public function get currentSymbol():Object { return LT(1); } 221 222 /** Look backwards k nodes */ 223 protected function LB(k:int):Object { 224 if ( k==0 ) { 225 return null; 226 } 227 if ( (p-k)<0 ) { 228 return null; 229 } 230 return nodes[p-k]; 231 } 232 233 public function get treeSource():Object { 234 return root; 235 } 236 237 public function get sourceName():String { 238 return tokenStream.sourceName; 239 } 240 241 public function get tokenStream():TokenStream { 242 return tokens; 243 } 244 245 public function set tokenStream(tokens:TokenStream):void { 246 this.tokens = tokens; 247 } 248 249 public function get treeAdaptor():TreeAdaptor { 250 return adaptor; 251 } 252 253 public function set treeAdaptor(adaptor:TreeAdaptor):void { 254 this.adaptor = adaptor; 255 } 256 257 public function get hasUniqueNavigationNodes():Boolean { 258 return uniqueNavigationNodes; 259 } 260 261 public function set hasUniqueNavigationNodes(uniqueNavigationNodes:Boolean):void { 262 this.uniqueNavigationNodes = uniqueNavigationNodes; 263 } 264 265 public function consume():void { 266 if ( p==-1 ) { 267 fillBuffer(); 268 } 269 p++; 270 } 271 272 public function LA(i:int):int { 273 return adaptor.getType(LT(i)); 274 } 275 276 public function mark():int { 277 if ( p==-1 ) { 278 fillBuffer(); 279 } 280 lastMarker = index; 281 return lastMarker; 282 } 283 284 public function release(marker:int):void { 285 // no resources to release 286 } 287 288 public function get index():int { 289 return p; 290 } 291 292 public function rewindTo(marker:int):void { 293 seek(marker); 294 } 295 296 public function rewind():void { 297 seek(lastMarker); 298 } 299 300 public function seek(index:int):void { 301 if ( p==-1 ) { 302 fillBuffer(); 303 } 304 p = index; 305 } 306 307 /** Make stream jump to a new location, saving old location. 308 * Switch back with pop(). 309 */ 310 public function push(index:int):void { 311 if ( calls==null ) { 312 calls = new Array(); 313 } 314 calls.push(p); // save current index 315 seek(index); 316 } 317 318 /** Seek back to previous index saved during last push() call. 319 * Return top of stack (return index). 320 */ 321 public function pop():int { 322 var ret:int = calls.pop(); 323 seek(ret); 324 return ret; 325 } 326 327 public function reset():void { 328 p = 0; 329 lastMarker = 0; 330 if (calls != null) { 331 calls = new Array(); 332 } 333 } 334 335 public function get size():int { 336 if ( p==-1 ) { 337 fillBuffer(); 338 } 339 return nodes.length; 340 } 341 342 // TREE REWRITE INTERFACE 343 public function replaceChildren(parent:Object, startChildIndex:int, stopChildIndex:int, t:Object):void { 344 if ( parent!=null ) { 345 adaptor.replaceChildren(parent, startChildIndex, stopChildIndex, t); 346 } 347 } 348 349 /** Used for testing, just return the token type stream */ 350 public function toString():String { 351 if ( p==-1 ) { 352 fillBuffer(); 353 } 354 var buf:String = ""; 355 for (var i:int = 0; i < nodes.length; i++) { 356 var t:Object = nodes[i]; 357 buf += " "; 358 buf += (adaptor.getType(t)); 359 } 360 return buf.toString(); 361 } 362 363 /** Debugging */ 364 public function toTokenString(start:int, stop:int):String { 365 if ( p==-1 ) { 366 fillBuffer(); 367 } 368 var buf:String = ""; 369 for (var i:int = start; i < nodes.length && i <= stop; i++) { 370 var t:Object = nodes[i]; 371 buf += " "; 372 buf += adaptor.getToken(t); 373 } 374 return buf; 375 } 376 377 public function toStringWithRange(start:Object, stop:Object):String { 378 if ( start==null || stop==null ) { 379 return null; 380 } 381 if ( p==-1 ) { 382 fillBuffer(); 383 } 384 trace("stop: "+stop); 385 if ( start is CommonTree ) 386 trace("toString: "+CommonTree(start).token+", "); 387 else 388 trace(start); 389 if ( stop is CommonTree ) 390 trace(CommonTree(stop).token); 391 else 392 trace(stop); 393 // if we have the token stream, use that to dump text in order 394 if ( tokens!=null ) { 395 var beginTokenIndex:int = adaptor.getTokenStartIndex(start); 396 var endTokenIndex:int = adaptor.getTokenStopIndex(stop); 397 // if it's a tree, use start/stop index from start node 398 // else use token range from start/stop nodes 399 if ( adaptor.getType(stop)==TokenConstants.UP ) { 400 endTokenIndex = adaptor.getTokenStopIndex(start); 401 } 402 else if ( adaptor.getType(stop)==TokenConstants.EOF ) { 403 endTokenIndex = size-2; // don't use EOF 404 } 405 return tokens.toStringWithRange(beginTokenIndex, endTokenIndex); 406 } 407 // walk nodes looking for start 408 var t:Object = null; 409 var i:int = 0; 410 for (; i < nodes.length; i++) { 411 t = nodes[i]; 412 if ( t==start ) { 413 break; 414 } 415 } 416 // now walk until we see stop, filling string buffer with text 417 var buf:String = ""; 418 t = nodes[i]; 419 while ( t!=stop ) { 420 var text:String = adaptor.getText(t); 421 if ( text==null ) { 422 text = " "+ adaptor.getType(t); 423 } 424 buf += text; 425 i++; 426 t = nodes[i]; 427 } 428 // include stop node too 429 text = adaptor.getText(stop); 430 if ( text==null ) { 431 text = " " + adaptor.getType(stop); 432 } 433 buf += text; 434 return buf.toString(); 435 } 436 } 437 438}