org.antlr.runtime.tree
Class UnBufferedTreeNodeStream

java.lang.Object
  org.antlr.runtime.tree.UnBufferedTreeNodeStream

All Implemented Interfaces:

IntStream, TreeNodeStream

public class UnBufferedTreeNodeStream
extends java.lang.Object
implements TreeNodeStream

A stream of tree nodes, accessing nodes from a tree of ANY kind. No new nodes should be created in tree 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.

See Also:

CommonTreeNodeStream

Nested Class Summary

protected class

UnBufferedTreeNodeStream.TreeWalkState When walking ahead with cyclic DFA or for syntactic predicates, we need to record the state of the tree node stream.

Field Summary

protected int	absoluteNodeIndex What node index did we just consume? i=0..n-1 for n node trees.
protected int	currentChildIndex Which child are we currently visiting? If -1 we have not visited this node yet; next consume() request will set currentIndex to 0.
protected java.lang.Object	currentNode Which node are we currently visiting?
protected java.lang.Object	down
protected java.lang.Object	eof
protected int	head lookahead[head] is the first symbol of lookahead, LT(1).
protected java.util.Stack	indexStack Track which child index you are visiting for each node we push.
static int	INITIAL_LOOKAHEAD_BUFFER_SIZE
protected int	lastMarker Track the last mark() call result value for use in rewind().
protected java.lang.Object[]	lookahead Buffer tree node stream for use with LT(i).
protected int	markDepth tracks how deep mark() calls are nested
protected java.util.List	markers Calls to mark() may be nested so we have to track a stack of them.
protected java.util.Stack	nodeStack 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.
protected java.lang.Object	previousNode Which node did we visit last? Used for LT(-1) calls.
protected java.lang.Object	root Pull nodes from which tree?
protected int	tail Add new lookahead at lookahead[tail].
protected TokenStream	tokens IF this tree (root) was created from a token stream, track it.
protected boolean	uniqueNavigationNodes Reuse same DOWN, UP navigation nodes unless this is true
protected java.lang.Object	up

Constructor Summary

UnBufferedTreeNodeStream(java.lang.Object tree)

UnBufferedTreeNodeStream(TreeAdaptor adaptor, java.lang.Object tree)

Method Summary

protected void	addLookahead(java.lang.Object node) Add a node to the lookahead buffer.
protected void	addNavigationNode(int ttype) As we flatten the tree, we use UP, DOWN nodes to represent the tree structure.
void	consume()
protected void	fill(int k) Make sure we have at least k symbols in lookahead buffer
java.lang.Object	get(int i) Get a tree node at an absolute index i; 0..n-1.
protected int	getLookaheadSize()
TokenStream	getTokenStream() If the tree associated with this stream was created from a TokenStream, you can specify it here.
TreeAdaptor	getTreeAdaptor() What adaptor can tell me how to interpret/navigate nodes and trees.
java.lang.Object	getTreeSource() Where is this stream pulling nodes from? This is not the name, but the object that provides node objects.
protected java.lang.Object	handleRootNode()
boolean	hasUniqueNavigationNodes()
int	index() Return the current input symbol index 0..n where n indicates the last symbol has been read.
int	LA(int i) Get int at current input pointer + i ahead where i=1 is next int.
java.lang.Object	LT(int k) Get tree node at current input pointer + i ahead where i=1 is next node.
int	mark() Record the current state of the tree walk which includes the current node and stack state as well as the lookahead buffer.
java.lang.Object	next() Return the next node found during a depth-first walk of root.
void	release(int marker) You may want to commit to a backtrack but don't want to force the stream to keep bookkeeping objects around for a marker that is no longer necessary.
void	reset()
void	rewind() Rewind to the input position of the last marker.
void	rewind(int marker) Rewind the current state of the tree walk to the state it was in when mark() was called and it returned marker.
void	seek(int index) consume() ahead until we hit index.
void	setTokenStream(TokenStream tokens)
void	setUniqueNavigationNodes(boolean uniqueNavigationNodes) As we flatten the tree, we use UP, DOWN nodes to represent the tree structure.
int	size() Expensive to compute; recursively walk tree to find size; include navigation nodes and EOF.
java.lang.String	toString() Print out the entire tree including DOWN/UP nodes.
java.lang.String	toString(java.lang.Object start, java.lang.Object stop) Return the text of all nodes from start to stop, inclusive.
protected void	toStringWork(java.lang.Object p, java.lang.Object stop, java.lang.StringBuffer buf)
protected java.lang.Object	visitChild(int child)
protected void	walkBackToMostRecentNodeWithUnvisitedChildren() Walk upwards looking for a node with more children to walk.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

INITIAL_LOOKAHEAD_BUFFER_SIZE

public static final int INITIAL_LOOKAHEAD_BUFFER_SIZE

See Also:

Constant Field Values

uniqueNavigationNodes

protected boolean uniqueNavigationNodes

Reuse same DOWN, UP navigation nodes unless this is true

root

protected java.lang.Object root

Pull nodes from which tree?

tokens

protected TokenStream tokens

IF this tree (root) was created from a token stream, track it.

nodeStack

protected java.util.Stack nodeStack

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.

indexStack

protected java.util.Stack indexStack

Track which child index you are visiting for each node we push. TODO: pretty inefficient...use int[] when you have time

currentNode

protected java.lang.Object currentNode

Which node are we currently visiting?

previousNode

protected java.lang.Object previousNode

Which node did we visit last? Used for LT(-1) calls.

currentChildIndex

protected int currentChildIndex

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

absoluteNodeIndex

protected int absoluteNodeIndex

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.

lookahead

protected java.lang.Object[] lookahead

Buffer tree node stream for use with LT(i). This list grows to fit new lookahead depths, but consume() wraps like a circular buffer.

head

protected int head

lookahead[head] is the first symbol of lookahead, LT(1).

tail

protected int tail

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

markers

protected java.util.List markers

Calls to mark() may be nested so we have to track a stack of them. The marker is an index into this stack. This is a List. Indexed from 1..markDepth. A null is kept @ index 0. Create upon first call to mark().

markDepth

protected int markDepth

tracks how deep mark() calls are nested

lastMarker

protected int lastMarker

Track the last mark() call result value for use in rewind().

down

protected java.lang.Object down

up

protected java.lang.Object up

eof

protected java.lang.Object eof

Constructor Detail

UnBufferedTreeNodeStream

public UnBufferedTreeNodeStream(java.lang.Object tree)

UnBufferedTreeNodeStream

public UnBufferedTreeNodeStream(TreeAdaptor adaptor,
                                java.lang.Object tree)

Method Detail

reset

public void reset()

get

public java.lang.Object get(int i)

Description copied from interface: TreeNodeStream

Get a tree node at an absolute index i; 0..n-1. If you don't want to buffer up nodes, then this method makes no sense for you.

Specified by:

get in interface TreeNodeStream

LT

public java.lang.Object LT(int k)

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. :)

Specified by:

LT in interface TreeNodeStream

getTreeSource

public java.lang.Object getTreeSource()

Where is this stream pulling nodes from? This is not the name, but the object that provides node objects.

Specified by:

getTreeSource in interface TreeNodeStream

getTokenStream

public TokenStream getTokenStream()

Description copied from interface: TreeNodeStream

If the tree associated with this stream was created from a TokenStream, you can specify it here. Used to do rule $text attribute in tree parser. Optional unless you use tree parser rule text attribute or output=template and rewrite=true options.

Specified by:

getTokenStream in interface TreeNodeStream

setTokenStream

public void setTokenStream(TokenStream tokens)

fill

protected void fill(int k)

Make sure we have at least k symbols in lookahead buffer

addLookahead

protected void addLookahead(java.lang.Object node)

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].

consume

public void consume()

Specified by:

consume in interface IntStream

LA

public int LA(int i)

Description copied from interface: IntStream

Get int at current input pointer + i ahead where i=1 is next int. Negative indexes are allowed. LA(-1) is previous token (token just matched). LA(-i) where i is before first token should yield -1, invalid char / EOF.

Specified by:

LA in interface IntStream

mark

public int mark()

Record the current state of the tree walk which includes the current node and stack state as well as the lookahead buffer.

Specified by:

mark in interface IntStream

release

public void release(int marker)

Description copied from interface: IntStream

You may want to commit to a backtrack but don't want to force the stream to keep bookkeeping objects around for a marker that is no longer necessary. This will have the same behavior as rewind() except it releases resources without the backward seek. This must throw away resources for all markers back to the marker argument. So if you're nested 5 levels of mark(), and then release(2) you have to release resources for depths 2..5.

Specified by:

release in interface IntStream

rewind

public void rewind(int marker)

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().

Specified by:

rewind in interface IntStream

rewind

public void rewind()

Description copied from interface: IntStream

Rewind to the input position of the last marker. Used currently only after a cyclic DFA and just before starting a sem/syn predicate to get the input position back to the start of the decision. Do not "pop" the marker off the state. mark(i) and rewind(i) should balance still. It is like invoking rewind(last marker) but it should not "pop" the marker off. It's like seek(last marker's input position).

Specified by:

rewind in interface IntStream

seek

public void seek(int index)

consume() ahead until we hit index. Can't just jump ahead--must spit out the navigation nodes.

Specified by:

seek in interface IntStream

index

public int index()

Description copied from interface: IntStream

Return the current input symbol index 0..n where n indicates the last symbol has been read. The index is the symbol about to be read not the most recently read symbol.

Specified by:

index in interface IntStream

size

public int size()

Expensive to compute; recursively walk tree to find size; include navigation nodes and EOF. Reuse functionality in CommonTreeNodeStream as we only really use this for testing.

Specified by:

size in interface IntStream

next

public java.lang.Object next()

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. :(

handleRootNode

protected java.lang.Object handleRootNode()

visitChild

protected java.lang.Object visitChild(int child)

addNavigationNode

protected void addNavigationNode(int ttype)

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.

walkBackToMostRecentNodeWithUnvisitedChildren

protected void walkBackToMostRecentNodeWithUnvisitedChildren()

Walk upwards looking for a node with more children to walk.

getTreeAdaptor

public TreeAdaptor getTreeAdaptor()

Description copied from interface: TreeNodeStream

What adaptor can tell me how to interpret/navigate nodes and trees. E.g., get text of a node.

Specified by:

getTreeAdaptor in interface TreeNodeStream

hasUniqueNavigationNodes

public boolean hasUniqueNavigationNodes()

setUniqueNavigationNodes

public void setUniqueNavigationNodes(boolean uniqueNavigationNodes)

Description copied from interface: TreeNodeStream

As we flatten the tree, we use UP, DOWN nodes to represent the tree structure. When debugging we need unique nodes so we have to instantiate new ones. When doing normal tree parsing, it's slow and a waste of memory to create unique navigation nodes. Default should be false;

Specified by:

setUniqueNavigationNodes in interface TreeNodeStream

toString

public java.lang.String 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.

Overrides:

toString in class java.lang.Object

getLookaheadSize

protected int getLookaheadSize()

toString

public java.lang.String toString(java.lang.Object start,
                                 java.lang.Object stop)

Description copied from interface: TreeNodeStream

Return the text of all nodes from start to stop, inclusive. If the stream does not buffer all the nodes then it can still walk recursively from start until stop. You can always return null or "" too, but users should not access $ruleLabel.text in an action of course in that case.

Specified by:

toString in interface TreeNodeStream

toStringWork

protected void toStringWork(java.lang.Object p,
                            java.lang.Object stop,
                            java.lang.StringBuffer buf)