commontreenodestream.java

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

			markers = new ArrayList();
		}
		TreeWalkState state = new TreeWalkState();
		state.absoluteNodeIndex = absoluteNodeIndex;
		state.currentChildIndex = currentChildIndex;
		state.currentNode = currentNode;
		state.previousNode = previousNode;
		state.nodeStackSize = nodeStack.size();
		state.indexStackSize = indexStack.size();
		// take snapshot of lookahead buffer
		int n = getLookaheadSize();
		int i=0;
		state.lookahead = new Tree[n];
		for (int k=1; k<=n; k++,i++) {
			state.lookahead[i] = (Tree)LT(k);
		}
		markers.add(state);
		return markers.size(); // markers go 1..depth
	}

	public void release(int marker) {
		throw new NoSuchMethodError("can't release tree parse; email [e-mail]");
	}

	/** Rewind the current state of the tree walk to the state it
	 *  was in when mark() was called and it returned marker.  Also,
	 *  wipe out the lookahead which will force reloading a few nodes
	 *  but it is better than making a copy of the lookahead buffer
	 *  upon mark().
	 */
	public void rewind(int marker) {
		if ( markers==null || markers.size()<marker ) {
			return; // do nothing upon error; perhaps this should throw exception?
		}
		TreeWalkState state = (TreeWalkState)markers.get(marker-1);
		markers.remove(marker-1); // "pop" state from stack
		absoluteNodeIndex = state.absoluteNodeIndex;
		currentChildIndex = state.currentChildIndex;
		currentNode = state.currentNode;
		previousNode = state.previousNode;
		// drop node and index stacks back to old size
		nodeStack.setSize(state.nodeStackSize);
		indexStack.setSize(state.indexStackSize);
		head = tail = 0; // wack lookahead buffer and then refill
		for (; tail<state.lookahead.length; tail++) {
			lookahead[tail] = state.lookahead[tail];
		}
	}

	public void rewind() {
		rewind(lastMarker);
	}

	/** consume() ahead until we hit index.  Can't just jump ahead--must
	 *  spit out the navigation nodes.
	 */
	public void seek(int index) {
		if ( index<this.index() ) {
			throw new IllegalArgumentException("can't seek backwards in node stream");
		}
		// seek forward, consume until we hit index
		while ( this.index()<index ) {
			consume();
		}
	}

	public int index() {
		return absoluteNodeIndex+1;
	}

	/** Expensive to compute so I won't bother doing the right thing.
	 *  This method only returns how much input has been seen so far.  So
	 *  after parsing it returns true size.
	 */
	public int size() {
		return absoluteNodeIndex+1;
	}

	// Satisfy Java's Iterator interface

	public boolean hasNext() {
		return currentNode!=null;
	}

	/** Return the next node found during a depth-first walk of root.
	 *  Also, add these nodes and DOWN/UP imaginary nodes into the lokoahead
	 *  buffer as a side-effect.  Normally side-effects are bad, but because
	 *  we can emit many tokens for every next() call, it's pretty hard to
	 *  use a single return value for that.  We must add these tokens to
	 *  the lookahead buffer.
	 *
	 *  This does *not* return the DOWN/UP nodes; those are only returned
	 *  by the LT() method.
	 *
	 *  Ugh.  This mechanism is much more complicated than a recursive
	 *  solution, but it's the only way to provide nodes on-demand instead
	 *  of walking once completely through and buffering up the nodes. :(
	 */
	public Object next() {
		// already walked entire tree; nothing to return
		if ( currentNode==null ) {
			addLookahead(EOF_NODE);
			// this is infinite stream returning EOF at end forever
			// so don't throw NoSuchElementException
			return null;
		}

		// initial condition (first time method is called)
		if ( currentChildIndex==-1 ) {
			return handleRootNode();
		}

		// index is in the child list?
		if ( currentChildIndex<currentNode.getChildCount() ) {
			return visitChild(currentChildIndex);
		}

		// hit end of child list, return to parent node or its parent ...
		walkBackToMostRecentNodeWithUnvisitedChildren();
		if ( currentNode!=null ) {
			return visitChild(currentChildIndex);
		}

		return null;
	}

	protected Tree handleRootNode() {
		Tree node;
		node = currentNode;
		// point to first child in prep for subsequent next()
		currentChildIndex = 0;
		if ( node.isNil() ) {
			// don't count this root nil node
			node = visitChild(currentChildIndex);
		}
		else {
			addLookahead(node);
			if ( currentNode.getChildCount()==0 ) {
				// single node case
				currentNode = null; // say we're done
			}
		}
		return node;
	}

	protected Tree visitChild(int child) {
		Tree node = null;
		// save state
		nodeStack.push(currentNode);
		indexStack.push(new Integer(child));
		if ( child==0 && !currentNode.isNil() ) {
			addNavigationNode(Token.DOWN);
		}
		// visit child
		currentNode = (Tree)currentNode.getChild(child);
		currentChildIndex = 0;
		node = currentNode;  // record node to return
		addLookahead(node);
		walkBackToMostRecentNodeWithUnvisitedChildren();
		return node;
	}

	/** As we flatten the tree, we use UP, DOWN nodes to represent
	 *  the tree structure.  When debugging we need unique nodes
	 *  so instantiate new ones when uniqueNavigationNodes is true.
	 */
	protected void addNavigationNode(final int ttype) {
		Tree node = null;
		if ( ttype==Token.DOWN ) {
			if ( hasUniqueNavigationNodes() ) node = new NavDownNode();
			else node = DOWN;
		}
		else {
			if ( hasUniqueNavigationNodes() ) node = new NavUpNode();
			else node = UP;
		}
		addLookahead(node);
	}

	/** Walk upwards looking for a node with more children to walk. */
	protected void walkBackToMostRecentNodeWithUnvisitedChildren() {
		while ( currentNode!=null &&
				currentChildIndex>=currentNode.getChildCount() )
		{
			currentNode = (Tree)nodeStack.pop();
			currentChildIndex = ((Integer)indexStack.pop()).intValue();
			currentChildIndex++; // move to next child
			if ( currentChildIndex>=currentNode.getChildCount() ) {
				if ( !currentNode.isNil() ) {
					addNavigationNode(Token.UP);
				}
				if ( currentNode==root ) { // we done yet?
					currentNode = null;
				}
			}
		}
	}

	/** Just here to satisfy Iterator interface */
	public void remove() {
		throw new NoSuchMethodError();
	}

	public TreeAdaptor getTreeAdaptor() {
		return adaptor;
	}

	public boolean hasUniqueNavigationNodes() {
		return uniqueNavigationNodes;
	}

	public void setUniqueNavigationNodes(boolean uniqueNavigationNodes) {
		this.uniqueNavigationNodes = uniqueNavigationNodes;
	}

	/** Using the Iterator interface, return a list of all the token types
	 *  as text.  Used for testing.
	 */
	public String toNodesOnlyString() {
		StringBuffer buf = new StringBuffer();
		while (hasNext()) {
			CommonTree x = (CommonTree)next();
			buf.append(" ");
			buf.append(x.getType());
		}
		return buf.toString();
	}

	/** Print out the entire tree including DOWN/UP nodes.  Uses
	 *  a recursive walk.  Mostly useful for testing as it yields
	 *  the token types not text.
	 */
	public String toString() {
		return toString(root, null);
	}

	protected int getLookaheadSize() {
		return tail<head?(lookahead.length-head+tail):(tail-head);
	}

	public String toString(Object start, Object stop) {
		StringBuffer buf = new StringBuffer();
		toStringWork((Tree)start, (Tree)stop, buf);
		return buf.toString();
	}

	protected void toStringWork(Tree p, Tree stop, StringBuffer buf) {
		if ( !p.isNil() ) {
			String text = p.toString();
			if ( text==null ) {
				text = " "+String.valueOf(p.getType());
			}
			buf.append(text); // ask the node to go to string
		}
		if ( p==stop ) {
			return;
		}
		int n = p.getChildCount();
		if ( n>0 && !p.isNil() ) {
			buf.append(" ");
			buf.append(Token.DOWN);
		}
		for (int c=0; c<n; c++) {
			Tree child = p.getChild(c);
			toStringWork(child, stop, buf);
		}
		if ( n>0 && !p.isNil() ) {
			buf.append(" ");
			buf.append(Token.UP);
		}
	}
}