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}