commontreenodestream.java

ANTLR(ANother Tool for Language Recognition)它是这样的一种工具

/*
[The "BSD licence"]
Copyright (c) 2005-2006 Terence Parr
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.
3. The name of the author may not be used to endorse or promote products
derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
package org.antlr.runtime.tree;

import org.antlr.runtime.Token;

import java.util.Iterator;
import java.util.Stack;
import java.util.List;
import java.util.ArrayList;

/** A stream of tree nodes, accessing nodes from a tree of some kind.
 *  The stream can be accessed as an Iterator or via LT(1)/consume or
 *  LT(i).  No new nodes should be created during the walk.  A small buffer
 *  of tokens is kept to efficiently and easily handle LT(i) calls, though
 *  the lookahead mechanism is fairly complicated.
 *
 *  For tree rewriting during tree parsing, this must also be able
 *  to replace a set of children without "losing its place".
 *  That part is not yet implemented.  Will permit a rule to return
 *  a different tree and have it stitched into the output tree probably.
 *
 *  Because this class implements Iterator you can walk a tree with
 *  a for loop looking for nodes.  When using the Iterator
 *  interface methods you do not get DOWN and UP imaginary nodes that
 *  are used for parsing via TreeNodeStream interface.
 */
public class CommonTreeNodeStream implements TreeNodeStream, Iterator {
	public static final int INITIAL_LOOKAHEAD_BUFFER_SIZE = 5;

	protected static abstract class DummyTree extends BaseTree {
		public Tree dupNode() {return null;}
	}

	// all these navigation nodes are shared and hence they
	// cannot contain any line/column info

	public static class NavDownNode extends DummyTree {
		public int getType() {return Token.DOWN;}
		public String getText() {return "DOWN";}
		public String toString() {return "DOWN";}
	};

	public static class NavUpNode extends DummyTree {
		public int getType() {return Token.UP;}
		public String getText() {return "UP";}
		public String toString() {return "UP";}
	};

	public static class EOFNode extends DummyTree {
		public int getType() {return Token.EOF;}
		public String getText() {return "EOF";}
		public String toString() {return "EOF";}
	};

	public static final DummyTree DOWN = new NavDownNode();

	public static final DummyTree UP = new NavUpNode();

	public static final DummyTree EOF_NODE = new EOFNode();

	/** Reuse same DOWN, UP navigation nodes unless this is true */
	protected boolean uniqueNavigationNodes = false;

	/** Pull nodes from which tree? */
	protected Tree root;

	/** What tree adaptor was used to build these trees */
	TreeAdaptor adaptor;

	/** As we walk down the nodes, we must track parent nodes so we know
	 *  where to go after walking the last child of a node.  When visiting
	 *  a child, push current node and current index.
	 */
	protected Stack nodeStack = new Stack();

	/** Track which child index you are visiting for each node we push.
	 *  TODO: pretty inefficient...use int[] when you have time
	 */
	protected Stack indexStack = new Stack();

	/** Track the last mark() call result value for use in rewind(). */
	protected int lastMarker;

	/** Which node are we currently visiting? */
	protected Tree currentNode;

	/** Which node did we visit last?  Used for LT(-1) calls. */
	protected Tree previousNode;

	/** Which child are we currently visiting?  If -1 we have not visited
	 *  this node yet; next consume() request will set currentIndex to 0.
	 */
	protected int currentChildIndex;

	/** What node index did we just consume?  i=0..n-1 for n node trees.
	 *  IntStream.next is hence 1 + this value.  Size will be same.
	 */
	protected int absoluteNodeIndex;

	/** Buffer tree node stream for use with LT(i).  This list grows
	 *  to fit new lookahead depths, but consume() wraps like a circular
	 *  buffer.
	 */
	protected Tree[] lookahead = new Tree[INITIAL_LOOKAHEAD_BUFFER_SIZE];

	/** lookahead[head] is the first symbol of lookahead, LT(1). */
	protected int head;

	/** Add new lookahead at lookahead[tail].  tail wraps around at the
	 *  end of the lookahead buffer so tail could be less than head.
	  */
	protected int tail;

	/** When walking ahead with cyclic DFA or for syntactic predicates,
	  *  we need to record the state of the tree node stream.  This
	 *  class wraps up the current state of the CommonTreeNodeStream.
	 *  Calling mark() will push another of these on the markers stack.
	 */
	protected class TreeWalkState {
		int currentChildIndex;
		int absoluteNodeIndex;
		Tree currentNode;
		Tree previousNode;
		/** Record state of the nodeStack */
		int nodeStackSize;
		/** Record state of the indexStack */
		int indexStackSize;
		Tree[] lookahead;
	}

	/** Calls to mark() may be nested so we have to track a stack of
	 *  them.  The marker is an index into this stack.  Index 0 is
	 *  the first marker.  This is a List<TreeWalkState>
	 */
	protected List markers;

	public CommonTreeNodeStream(Tree tree) {
		this(new CommonTreeAdaptor(), tree);
	}

	public CommonTreeNodeStream(TreeAdaptor adaptor, Tree tree) {
		this.root = tree;
		this.adaptor = adaptor;
		reset();
	}

	public void reset() {
		currentNode = root;
		previousNode = null;
		currentChildIndex = -1;
		absoluteNodeIndex = -1;
		head = tail = 0;
	}

	// Satisfy TreeNodeStream

	/** Get tree node at current input pointer + i ahead where i=1 is next node.
	 *  i<0 indicates nodes in the past.  So -1 is previous node and -2 is
	 *  two nodes ago. LT(0) is undefined.  For i>=n, return null.
	 *  Return null for LT(0) and any index that results in an absolute address
	 *  that is negative.
	 *
	 *  This is analogus to the LT() method of the TokenStream, but this
	 *  returns a tree node instead of a token.  Makes code gen identical
	 *  for both parser and tree grammars. :)
	 */
	public Object LT(int k) {
		//System.out.println("LT("+k+"); head="+head+", tail="+tail);
		if ( k==-1 ) {
			return previousNode;
		}
		if ( k<0 ) {
			throw new IllegalArgumentException("tree node streams cannot look backwards more than 1 node");
		}
		if ( k==0 ) {
			return Tree.INVALID_NODE;
		}
		fill(k);
		return lookahead[(head+k-1)%lookahead.length];
	}

	/** Where is this stream pulling nodes from?  This is not the name, but
	 *  the object that provides node objects.
	 */
	public Object getTreeSource() {
		return root;
	}

	/** Make sure we have at least k symbols in lookahead buffer */
	protected void fill(int k) {
		int n = getLookaheadSize();
		//System.out.println("we have "+n+" nodes; need "+(k-n));
		for (int i=1; i<=k-n; i++) {
			next(); // get at least k-depth lookahead nodes
		}
	}

	/** Add a node to the lookahead buffer.  Add at lookahead[tail].
	 *  If you tail+1 == head, then we must create a bigger buffer
	 *  and copy all the nodes over plus reset head, tail.  After
	 *  this method, LT(1) will be lookahead[0].
	 */
	protected void addLookahead(Tree node) {
		//System.out.println("addLookahead head="+head+", tail="+tail);
		lookahead[tail] = node;
		tail = (tail+1)%lookahead.length;
		if ( tail==head ) {
			// buffer overflow: tail caught up with head
			// allocate a buffer 2x as big
			Tree[] bigger = new Tree[2*lookahead.length];
			// copy head to end of buffer to beginning of bigger buffer
			int remainderHeadToEnd = lookahead.length-head;
			System.arraycopy(lookahead, head, bigger, 0, remainderHeadToEnd);
			// copy 0..tail to after that
			System.arraycopy(lookahead, 0, bigger, remainderHeadToEnd, tail);
			lookahead = bigger; // reset to bigger buffer
			head = 0;
			tail += remainderHeadToEnd;
		}
	}

	// Satisfy IntStream interface

	public void consume() {
		/*
		System.out.println("consume: currentNode="+currentNode.getType()+
						   " childIndex="+currentChildIndex+
						   " nodeIndex="+absoluteNodeIndex);
						   */
		// make sure there is something in lookahead buf, which might call next()
		fill(1);
		absoluteNodeIndex++;
		previousNode = lookahead[head]; // track previous node before moving on
		head = (head+1) % lookahead.length;
	}

	public int LA(int i) {
		Tree t = (Tree)LT(i);
		if ( t==null ) {
			return Token.INVALID_TOKEN_TYPE;
		}
		return t.getType();
	}

	/** Record the current state of the tree walk which includes
	 *  the current node and stack state.
	 */
	public int mark() {
		if ( markers==null ) {