Home | History | Annotate | Download | only in tree 
      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.misc.IntArray;
     33 import java.util.*;
     34 
     35 /** A buffered stream of tree nodes.  Nodes can be from a tree of ANY kind.
     36  *
     37  *  This node stream sucks all nodes out of the tree specified in
     38  *  the constructor during construction and makes pointers into
     39  *  the tree using an array of Object pointers. The stream necessarily
     40  *  includes pointers to DOWN and UP and EOF nodes.
     41  *
     42  *  This stream knows how to mark/release for backtracking.
     43  *
     44  *  This stream is most suitable for tree interpreters that need to
     45  *  jump around a lot or for tree parsers requiring speed (at cost of memory).
     46  *  There is some duplicated functionality here with UnBufferedTreeNodeStream
     47  *  but just in bookkeeping, not tree walking etc...
     48  *
     49  *  TARGET DEVELOPERS:
     50  *
     51  *  This is the old CommonTreeNodeStream that buffered up entire node stream.
     52  *  No need to implement really as new CommonTreeNodeStream is much better
     53  *  and covers what we need.
     54  *
     55  *  @see CommonTreeNodeStream
     56  */
     57 public class BufferedTreeNodeStream implements TreeNodeStream {
     58 	public static final int DEFAULT_INITIAL_BUFFER_SIZE = 100;
     59 	public static final int INITIAL_CALL_STACK_SIZE = 10;
     60 
     61     protected class StreamIterator implements Iterator {
     62 		int i = 0;
     63 		public boolean hasNext() {
     64 			return i<nodes.size();
     65 		}
     66 
     67 		public Object next() {
     68 			int current = i;
     69 			i++;
     70 			if ( current < nodes.size() ) {
     71 				return nodes.get(current);
     72 			}
     73 			return eof;
     74 		}
     75 
     76 		public void remove() {
     77 			throw new RuntimeException("cannot remove nodes from stream");
     78 		}
     79 	}
     80 
     81 	// all these navigation nodes are shared and hence they
     82 	// cannot contain any line/column info
     83 
     84 	protected Object down;
     85 	protected Object up;
     86 	protected Object eof;
     87 
     88 	/** The complete mapping from stream index to tree node.
     89 	 *  This buffer includes pointers to DOWN, UP, and EOF nodes.
     90 	 *  It is built upon ctor invocation.  The elements are type
     91 	 *  Object as we don't what the trees look like.
     92 	 *
     93 	 *  Load upon first need of the buffer so we can set token types
     94 	 *  of interest for reverseIndexing.  Slows us down a wee bit to
     95 	 *  do all of the if p==-1 testing everywhere though.
     96 	 */
     97 	protected List nodes;
     98 
     99 	/** Pull nodes from which tree? */
    100 	protected Object root;
    101 
    102 	/** IF this tree (root) was created from a token stream, track it. */
    103 	protected TokenStream tokens;
    104 
    105 	/** What tree adaptor was used to build these trees */
    106 	TreeAdaptor adaptor;
    107 
    108 	/** Reuse same DOWN, UP navigation nodes unless this is true */
    109 	protected boolean uniqueNavigationNodes = false;
    110 
    111 	/** The index into the nodes list of the current node (next node
    112 	 *  to consume).  If -1, nodes array not filled yet.
    113 	 */
    114 	protected int p = -1;
    115 
    116 	/** Track the last mark() call result value for use in rewind(). */
    117 	protected int lastMarker;
    118 
    119 	/** Stack of indexes used for push/pop calls */
    120 	protected IntArray calls;
    121 
    122 	public BufferedTreeNodeStream(Object tree) {
    123 		this(new CommonTreeAdaptor(), tree);
    124 	}
    125 
    126 	public BufferedTreeNodeStream(TreeAdaptor adaptor, Object tree) {
    127 		this(adaptor, tree, DEFAULT_INITIAL_BUFFER_SIZE);
    128 	}
    129 
    130 	public BufferedTreeNodeStream(TreeAdaptor adaptor, Object tree, int initialBufferSize) {
    131 		this.root = tree;
    132 		this.adaptor = adaptor;
    133 		nodes = new ArrayList(initialBufferSize);
    134 		down = adaptor.create(Token.DOWN, "DOWN");
    135 		up = adaptor.create(Token.UP, "UP");
    136 		eof = adaptor.create(Token.EOF, "EOF");
    137 	}
    138 
    139 	/** Walk tree with depth-first-search and fill nodes buffer.
    140 	 *  Don't do DOWN, UP nodes if its a list (t is isNil).
    141 	 */
    142 	protected void fillBuffer() {
    143 		fillBuffer(root);
    144 		//System.out.println("revIndex="+tokenTypeToStreamIndexesMap);
    145 		p = 0; // buffer of nodes intialized now
    146 	}
    147 
    148 	public void fillBuffer(Object t) {
    149 		boolean nil = adaptor.isNil(t);
    150 		if ( !nil ) {
    151 			nodes.add(t); // add this node
    152 		}
    153 		// add DOWN node if t has children
    154 		int n = adaptor.getChildCount(t);
    155 		if ( !nil && n>0 ) {
    156 			addNavigationNode(Token.DOWN);
    157 		}
    158 		// and now add all its children
    159 		for (int c=0; c<n; c++) {
    160 			Object child = adaptor.getChild(t,c);
    161 			fillBuffer(child);
    162 		}
    163 		// add UP node if t has children
    164 		if ( !nil && n>0 ) {
    165 			addNavigationNode(Token.UP);
    166 		}
    167 	}
    168 
    169 	/** What is the stream index for node? 0..n-1
    170 	 *  Return -1 if node not found.
    171 	 */
    172 	protected int getNodeIndex(Object node) {
    173 		if ( p==-1 ) {
    174 			fillBuffer();
    175 		}
    176 		for (int i = 0; i < nodes.size(); i++) {
    177 			Object t = (Object) nodes.get(i);
    178 			if ( t==node ) {
    179 				return i;
    180 			}
    181 		}
    182 		return -1;
    183 	}
    184 
    185 	/** As we flatten the tree, we use UP, DOWN nodes to represent
    186 	 *  the tree structure.  When debugging we need unique nodes
    187 	 *  so instantiate new ones when uniqueNavigationNodes is true.
    188 	 */
    189 	protected void addNavigationNode(final int ttype) {
    190 		Object navNode = null;
    191 		if ( ttype==Token.DOWN ) {
    192 			if ( hasUniqueNavigationNodes() ) {
    193 				navNode = adaptor.create(Token.DOWN, "DOWN");
    194 			}
    195 			else {
    196 				navNode = down;
    197 			}
    198 		}
    199 		else {
    200 			if ( hasUniqueNavigationNodes() ) {
    201 				navNode = adaptor.create(Token.UP, "UP");
    202 			}
    203 			else {
    204 				navNode = up;
    205 			}
    206 		}
    207 		nodes.add(navNode);
    208 	}
    209 
    210 	public Object get(int i) {
    211 		if ( p==-1 ) {
    212 			fillBuffer();
    213 		}
    214 		return nodes.get(i);
    215 	}
    216 
    217 	public Object LT(int k) {
    218 		if ( p==-1 ) {
    219 			fillBuffer();
    220 		}
    221 		if ( k==0 ) {
    222 			return null;
    223 		}
    224 		if ( k<0 ) {
    225 			return LB(-k);
    226 		}
    227 		//System.out.print("LT(p="+p+","+k+")=");
    228 		if ( (p+k-1) >= nodes.size() ) {
    229 			return eof;
    230 		}
    231 		return nodes.get(p+k-1);
    232 	}
    233 
    234 	public Object getCurrentSymbol() { return LT(1); }
    235 
    236 /*
    237 	public Object getLastTreeNode() {
    238 		int i = index();
    239 		if ( i>=size() ) {
    240 			i--; // if at EOF, have to start one back
    241 		}
    242 		System.out.println("start last node: "+i+" size=="+nodes.size());
    243 		while ( i>=0 &&
    244 			(adaptor.getType(get(i))==Token.EOF ||
    245 			 adaptor.getType(get(i))==Token.UP ||
    246 			 adaptor.getType(get(i))==Token.DOWN) )
    247 		{
    248 			i--;
    249 		}
    250 		System.out.println("stop at node: "+i+" "+nodes.get(i));
    251 		return nodes.get(i);
    252 	}
    253 */
    254 
    255 	/** Look backwards k nodes */
    256 	protected Object LB(int k) {
    257 		if ( k==0 ) {
    258 			return null;
    259 		}
    260 		if ( (p-k)<0 ) {
    261 			return null;
    262 		}
    263 		return nodes.get(p-k);
    264 	}
    265 
    266 	public Object getTreeSource() {
    267 		return root;
    268 	}
    269 
    270 	public String getSourceName() {
    271 		return getTokenStream().getSourceName();
    272 	}
    273 
    274 	public TokenStream getTokenStream() {
    275 		return tokens;
    276 	}
    277 
    278 	public void setTokenStream(TokenStream tokens) {
    279 		this.tokens = tokens;
    280 	}
    281 
    282 	public TreeAdaptor getTreeAdaptor() {
    283 		return adaptor;
    284 	}
    285 
    286 	public void setTreeAdaptor(TreeAdaptor adaptor) {
    287 		this.adaptor = adaptor;
    288 	}
    289 
    290 	public boolean hasUniqueNavigationNodes() {
    291 		return uniqueNavigationNodes;
    292 	}
    293 
    294 	public void setUniqueNavigationNodes(boolean uniqueNavigationNodes) {
    295 		this.uniqueNavigationNodes = uniqueNavigationNodes;
    296 	}
    297 
    298 	public void consume() {
    299 		if ( p==-1 ) {
    300 			fillBuffer();
    301 		}
    302 		p++;
    303 	}
    304 
    305 	public int LA(int i) {
    306 		return adaptor.getType(LT(i));
    307 	}
    308 
    309 	public int mark() {
    310 		if ( p==-1 ) {
    311 			fillBuffer();
    312 		}
    313 		lastMarker = index();
    314 		return lastMarker;
    315 	}
    316 
    317 	public void release(int marker) {
    318 		// no resources to release
    319 	}
    320 
    321 	public int index() {
    322 		return p;
    323 	}
    324 
    325 	public void rewind(int marker) {
    326 		seek(marker);
    327 	}
    328 
    329 	public void rewind() {
    330 		seek(lastMarker);
    331 	}
    332 
    333 	public void seek(int index) {
    334 		if ( p==-1 ) {
    335 			fillBuffer();
    336 		}
    337 		p = index;
    338 	}
    339 
    340 	/** Make stream jump to a new location, saving old location.
    341 	 *  Switch back with pop().
    342 	 */
    343 	public void push(int index) {
    344 		if ( calls==null ) {
    345 			calls = new IntArray();
    346 		}
    347 		calls.push(p); // save current index
    348 		seek(index);
    349 	}
    350 
    351 	/** Seek back to previous index saved during last push() call.
    352 	 *  Return top of stack (return index).
    353 	 */
    354 	public int pop() {
    355 		int ret = calls.pop();
    356 		seek(ret);
    357 		return ret;
    358 	}
    359 
    360 	public void reset() {
    361 		p = 0;
    362 		lastMarker = 0;
    363         if (calls != null) {
    364             calls.clear();
    365         }
    366     }
    367 
    368 	public int size() {
    369 		if ( p==-1 ) {
    370 			fillBuffer();
    371 		}
    372 		return nodes.size();
    373 	}
    374 
    375 	public Iterator iterator() {
    376 		if ( p==-1 ) {
    377 			fillBuffer();
    378 		}
    379 		return new StreamIterator();
    380 	}
    381 
    382 	// TREE REWRITE INTERFACE
    383 
    384 	public void replaceChildren(Object parent, int startChildIndex, int stopChildIndex, Object t) {
    385 		if ( parent!=null ) {
    386 			adaptor.replaceChildren(parent, startChildIndex, stopChildIndex, t);
    387 		}
    388 	}
    389 
    390 	/** Used for testing, just return the token type stream */
    391 	public String toTokenTypeString() {
    392 		if ( p==-1 ) {
    393 			fillBuffer();
    394 		}
    395 		StringBuffer buf = new StringBuffer();
    396 		for (int i = 0; i < nodes.size(); i++) {
    397 			Object t = (Object) nodes.get(i);
    398 			buf.append(" ");
    399 			buf.append(adaptor.getType(t));
    400 		}
    401 		return buf.toString();
    402 	}
    403 
    404 	/** Debugging */
    405 	public String toTokenString(int start, int stop) {
    406 		if ( p==-1 ) {
    407 			fillBuffer();
    408 		}
    409 		StringBuffer buf = new StringBuffer();
    410 		for (int i = start; i < nodes.size() && i <= stop; i++) {
    411 			Object t = (Object) nodes.get(i);
    412 			buf.append(" ");
    413 			buf.append(adaptor.getToken(t));
    414 		}
    415 		return buf.toString();
    416 	}
    417 
    418 	public String toString(Object start, Object stop) {
    419 		System.out.println("toString");
    420 		if ( start==null || stop==null ) {
    421 			return null;
    422 		}
    423 		if ( p==-1 ) {
    424 			fillBuffer();
    425 		}
    426 		//System.out.println("stop: "+stop);
    427 		if ( start instanceof CommonTree )
    428 			System.out.print("toString: "+((CommonTree)start).getToken()+", ");
    429 		else
    430 			System.out.println(start);
    431 		if ( stop instanceof CommonTree )
    432 			System.out.println(((CommonTree)stop).getToken());
    433 		else
    434 			System.out.println(stop);
    435 		// if we have the token stream, use that to dump text in order
    436 		if ( tokens!=null ) {
    437 			int beginTokenIndex = adaptor.getTokenStartIndex(start);
    438 			int endTokenIndex = adaptor.getTokenStopIndex(stop);
    439 			// if it's a tree, use start/stop index from start node
    440 			// else use token range from start/stop nodes
    441 			if ( adaptor.getType(stop)==Token.UP ) {
    442 				endTokenIndex = adaptor.getTokenStopIndex(start);
    443 			}
    444 			else if ( adaptor.getType(stop)==Token.EOF ) {
    445 				endTokenIndex = size()-2; // don't use EOF
    446 			}
    447 			return tokens.toString(beginTokenIndex, endTokenIndex);
    448 		}
    449 		// walk nodes looking for start
    450 		Object t = null;
    451 		int i = 0;
    452 		for (; i < nodes.size(); i++) {
    453 			t = nodes.get(i);
    454 			if ( t==start ) {
    455 				break;
    456 			}
    457 		}
    458 		// now walk until we see stop, filling string buffer with text
    459 		 StringBuffer buf = new StringBuffer();
    460 		t = nodes.get(i);
    461 		while ( t!=stop ) {
    462 			String text = adaptor.getText(t);
    463 			if ( text==null ) {
    464 				text = " "+String.valueOf(adaptor.getType(t));
    465 			}
    466 			buf.append(text);
    467 			i++;
    468 			t = nodes.get(i);
    469 		}
    470 		// include stop node too
    471 		String text = adaptor.getText(stop);
    472 		if ( text==null ) {
    473 			text = " "+String.valueOf(adaptor.getType(stop));
    474 		}
    475 		buf.append(text);
    476 		return buf.toString();
    477 	}
    478 }
    479