Package org.antlr.runtime.tree
Class BufferedTreeNodeStream
- java.lang.Object
-
- org.antlr.runtime.tree.BufferedTreeNodeStream
-
- All Implemented Interfaces:
IntStream
,TreeNodeStream
public class BufferedTreeNodeStream extends Object implements TreeNodeStream
A buffered stream of tree nodes. Nodes can be from a tree of ANY kind. This node stream sucks all nodes out of the tree specified in the constructor during construction and makes pointers into the tree using an array of Object pointers. The stream necessarily includes pointers to DOWN and UP and EOF nodes. This stream knows how to mark/release for backtracking. This stream is most suitable for tree interpreters that need to jump around a lot or for tree parsers requiring speed (at cost of memory). There is some duplicated functionality here with UnBufferedTreeNodeStream but just in bookkeeping, not tree walking etc... TARGET DEVELOPERS: This is the old CommonTreeNodeStream that buffered up entire node stream. No need to implement really as new CommonTreeNodeStream is much better and covers what we need.- See Also:
CommonTreeNodeStream
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected class
BufferedTreeNodeStream.StreamIterator
-
Field Summary
Fields Modifier and Type Field Description protected IntArray
calls
Stack of indexes used for push/pop callsstatic int
DEFAULT_INITIAL_BUFFER_SIZE
protected Object
down
protected Object
eof
static int
INITIAL_CALL_STACK_SIZE
protected int
lastMarker
Track the last mark() call result value for use in rewind().protected List<Object>
nodes
The complete mapping from stream index to tree node.protected int
p
The index into the nodes list of the current node (next node to consume).protected Object
root
Pull nodes from which tree?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 trueprotected Object
up
-
Constructor Summary
Constructors Constructor Description BufferedTreeNodeStream(Object tree)
BufferedTreeNodeStream(TreeAdaptor adaptor, Object tree)
BufferedTreeNodeStream(TreeAdaptor adaptor, Object tree, int initialBufferSize)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected void
addNavigationNode(int ttype)
As we flatten the tree, we use UP, DOWN nodes to represent the tree structure.void
consume()
protected void
fillBuffer()
Walk tree with depth-first-search and fill nodes buffer.void
fillBuffer(Object t)
Object
get(int i)
Get a tree node at an absolute indexi
; 0..n-1.Object
getCurrentSymbol()
protected int
getNodeIndex(Object node)
What is the stream index for node? 0..n-1 Return -1 if node not found.String
getSourceName()
Where are you getting symbols from? Normally, implementations will pass the buck all the way to the lexer who can ask its input stream for the file name or whatever.TokenStream
getTokenStream()
If the tree associated with this stream was created from aTokenStream
, you can specify it here.TreeAdaptor
getTreeAdaptor()
What adaptor can tell me how to interpret/navigate nodes and trees.Object
getTreeSource()
Where is this stream pulling nodes from? This is not the name, but the object that provides node objects.boolean
hasUniqueNavigationNodes()
int
index()
Return the current input symbol index 0..n where n indicates the last symbol has been read.Iterator<Object>
iterator()
int
LA(int i)
Get int at current input pointer + i ahead where i=1 is next int.protected Object
LB(int k)
Look backwards k nodesObject
LT(int k)
Get tree node at current input pointer +k
ahead wherek==1
is next node.int
mark()
Tell the stream to start buffering if it hasn't already.int
pop()
Seek back to previous index saved during last push() call.void
push(int index)
Make stream jump to a new location, saving old location.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
replaceChildren(Object parent, int startChildIndex, int stopChildIndex, Object t)
Replace children ofparent
from indexstartChildIndex
tostopChildIndex
witht
, which might be a list.void
reset()
Reset the tree node stream in such a way that it acts like a freshly constructed stream.void
rewind()
Rewind to the input position of the last marker.void
rewind(int marker)
Reset the stream so that next call to index would return marker.void
seek(int index)
Set the input cursor to the position indicated by index.void
setTokenStream(TokenStream tokens)
void
setTreeAdaptor(TreeAdaptor adaptor)
void
setUniqueNavigationNodes(boolean uniqueNavigationNodes)
As we flatten the tree, we useToken.UP
,Token.DOWN
nodes to represent the tree structure.int
size()
Only makes sense for streams that buffer everything up probably, but might be useful to display the entire stream or for testing.String
toString(Object start, Object stop)
Return the text of all nodes fromstart
tostop
, inclusive.String
toTokenString(int start, int stop)
DebuggingString
toTokenTypeString()
Used for testing, just return the token type stream
-
-
-
Field Detail
-
DEFAULT_INITIAL_BUFFER_SIZE
public static final int DEFAULT_INITIAL_BUFFER_SIZE
- See Also:
- Constant Field Values
-
INITIAL_CALL_STACK_SIZE
public static final int INITIAL_CALL_STACK_SIZE
- See Also:
- Constant Field Values
-
down
protected Object down
-
up
protected Object up
-
eof
protected Object eof
-
nodes
protected List<Object> nodes
The complete mapping from stream index to tree node. This buffer includes pointers to DOWN, UP, and EOF nodes. It is built upon ctor invocation. The elements are type Object as we don't what the trees look like. Load upon first need of the buffer so we can set token types of interest for reverseIndexing. Slows us down a wee bit to do all of the if p==-1 testing everywhere though.
-
root
protected Object root
Pull nodes from which tree?
-
tokens
protected TokenStream tokens
IF this tree (root) was created from a token stream, track it.
-
uniqueNavigationNodes
protected boolean uniqueNavigationNodes
Reuse same DOWN, UP navigation nodes unless this is true
-
p
protected int p
The index into the nodes list of the current node (next node to consume). If -1, nodes array not filled yet.
-
lastMarker
protected int lastMarker
Track the last mark() call result value for use in rewind().
-
calls
protected IntArray calls
Stack of indexes used for push/pop calls
-
-
Constructor Detail
-
BufferedTreeNodeStream
public BufferedTreeNodeStream(Object tree)
-
BufferedTreeNodeStream
public BufferedTreeNodeStream(TreeAdaptor adaptor, Object tree)
-
BufferedTreeNodeStream
public BufferedTreeNodeStream(TreeAdaptor adaptor, Object tree, int initialBufferSize)
-
-
Method Detail
-
fillBuffer
protected void fillBuffer()
Walk tree with depth-first-search and fill nodes buffer. Don't do DOWN, UP nodes if its a list (t is isNil).
-
fillBuffer
public void fillBuffer(Object t)
-
getNodeIndex
protected int getNodeIndex(Object node)
What is the stream index for node? 0..n-1 Return -1 if node not found.
-
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.
-
get
public Object get(int i)
Description copied from interface:TreeNodeStream
Get a tree node at an absolute indexi
; 0..n-1. If you don't want to buffer up nodes, then this method makes no sense for you.- Specified by:
get
in interfaceTreeNodeStream
-
LT
public Object LT(int k)
Description copied from interface:TreeNodeStream
Get tree node at current input pointer +k
ahead wherek==1
is next node.k<0
indicates nodes in the past. SoLT(-1)
is previous node, but implementations are not required to provide results fork < -1
.LT(0)
is undefined. Fork<=n
, returnnull
. Returnnull
forLT(0)
and any index that results in an absolute address that is negative.This is analogous to
TokenStream.LT(int)
, but this returns a tree node instead of aToken
. Makes code generation identical for both parser and tree grammars.- Specified by:
LT
in interfaceTreeNodeStream
-
getCurrentSymbol
public Object getCurrentSymbol()
-
LB
protected Object LB(int k)
Look backwards k nodes
-
getTreeSource
public Object getTreeSource()
Description copied from interface:TreeNodeStream
Where is this stream pulling nodes from? This is not the name, but the object that provides node objects.- Specified by:
getTreeSource
in interfaceTreeNodeStream
-
getSourceName
public String getSourceName()
Description copied from interface:IntStream
Where are you getting symbols from? Normally, implementations will pass the buck all the way to the lexer who can ask its input stream for the file name or whatever.- Specified by:
getSourceName
in interfaceIntStream
-
getTokenStream
public TokenStream getTokenStream()
Description copied from interface:TreeNodeStream
If the tree associated with this stream was created from aTokenStream
, you can specify it here. Used to do rule$text
attribute in tree parser. Optional unless you use tree parser rule$text
attribute oroutput=template
andrewrite=true
options.- Specified by:
getTokenStream
in interfaceTreeNodeStream
-
setTokenStream
public void setTokenStream(TokenStream tokens)
-
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 interfaceTreeNodeStream
-
setTreeAdaptor
public void setTreeAdaptor(TreeAdaptor adaptor)
-
hasUniqueNavigationNodes
public boolean hasUniqueNavigationNodes()
-
setUniqueNavigationNodes
public void setUniqueNavigationNodes(boolean uniqueNavigationNodes)
Description copied from interface:TreeNodeStream
As we flatten the tree, we useToken.UP
,Token.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 befalse
.- Specified by:
setUniqueNavigationNodes
in interfaceTreeNodeStream
-
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.
-
mark
public int mark()
Description copied from interface:IntStream
Tell the stream to start buffering if it hasn't already. Return current input position, index(), or some other marker so that when passed to rewind() you get back to the same spot. rewind(mark()) should not affect the input cursor. The Lexer track line/col info as well as input index so its markers are not pure input indexes. Same for tree node streams.
-
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.
-
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.
-
rewind
public void rewind(int marker)
Description copied from interface:IntStream
Reset the stream so that next call to index would return marker. The marker will usually be index() but it doesn't have to be. It's just a marker to indicate what state the stream was in. This is essentially calling release() and seek(). If there are markers created after this marker argument, this routine must unroll them like a stack. Assume the state the stream was in when this marker was created.
-
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).
-
seek
public void seek(int index)
Description copied from interface:IntStream
Set the input cursor to the position indicated by index. This is normally used to seek ahead in the input stream. No buffering is required to do this unless you know your stream will use seek to move backwards such as when backtracking. This is different from rewind in its multi-directional requirement and in that its argument is strictly an input cursor (index). For char streams, seeking forward must update the stream state such as line number. For seeking backwards, you will be presumably backtracking using the mark/rewind mechanism that restores state and so this method does not need to update state when seeking backwards. Currently, this method is only used for efficient backtracking using memoization, but in the future it may be used for incremental parsing. The index is 0..n-1. A seek to position i means that LA(1) will return the ith symbol. So, seeking to 0 means LA(1) will return the first element in the stream.
-
push
public void push(int index)
Make stream jump to a new location, saving old location. Switch back with pop().
-
pop
public int pop()
Seek back to previous index saved during last push() call. Return top of stack (return index).
-
reset
public void reset()
Description copied from interface:TreeNodeStream
Reset the tree node stream in such a way that it acts like a freshly constructed stream.- Specified by:
reset
in interfaceTreeNodeStream
-
size
public int size()
Description copied from interface:IntStream
Only makes sense for streams that buffer everything up probably, but might be useful to display the entire stream or for testing. This value includes a single EOF.
-
replaceChildren
public void replaceChildren(Object parent, int startChildIndex, int stopChildIndex, Object t)
Description copied from interface:TreeNodeStream
Replace children ofparent
from indexstartChildIndex
tostopChildIndex
witht
, which might be a list. Number of children may be different after this call. The stream is notified because it is walking the tree and might need to know you are monkeying with the underlying tree. Also, it might be able to modify the node stream to avoid restreaming for future phases.If
parent
isnull
, don't do anything; must be at root of overall tree. Can't replace whatever points to the parent externally. Do nothing.- Specified by:
replaceChildren
in interfaceTreeNodeStream
-
toTokenTypeString
public String toTokenTypeString()
Used for testing, just return the token type stream
-
toTokenString
public String toTokenString(int start, int stop)
Debugging
-
toString
public String toString(Object start, Object stop)
Description copied from interface:TreeNodeStream
Return the text of all nodes fromstart
tostop
, inclusive. If the stream does not buffer all the nodes then it can still walk recursively from start until stop. You can always returnnull
or""
too, but users should not access$ruleLabel.text
in an action of course in that case.- Specified by:
toString
in interfaceTreeNodeStream
-
-