/*
* [The "BSD licence"]
* Copyright (c) 2005-2008 Terence Parr
* All rights reserved.
*
* Conversion to C#:
* Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc.
* 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.
*/
namespace Antlr.Runtime.Tree
{
using System.Collections.Generic;
using Console = System.Console;
using IList = System.Collections.IList;
using InvalidOperationException = System.InvalidOperationException;
using StringBuilder = System.Text.StringBuilder;
/** <summary>A buffered stream of tree nodes. Nodes can be from a tree of ANY kind.</summary>
*
* 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 CommonTreeNodeStream
*/
public class BufferedTreeNodeStream : ITreeNodeStream, ITokenStreamInformation
{
public const int DEFAULT_INITIAL_BUFFER_SIZE = 100;
public const int INITIAL_CALL_STACK_SIZE = 10;
protected sealed class StreamIterator : IEnumerator<object>
{
BufferedTreeNodeStream _outer;
int _index;
public StreamIterator( BufferedTreeNodeStream outer )
{
_outer = outer;
_index = -1;
}
#region IEnumerator<object> Members
public object Current
{
get
{
if ( _index < _outer.nodes.Count )
return _outer.nodes[_index];
return _outer.eof;
}
}
#endregion
#region IDisposable Members
public void Dispose()
{
}
#endregion
#region IEnumerator Members
public bool MoveNext()
{
if ( _index < _outer.nodes.Count )
_index++;
return _index < _outer.nodes.Count;
}
public void Reset()
{
_index = -1;
}
#endregion
}
// all these navigation nodes are shared and hence they
// cannot contain any line/column info
protected object down;
protected object up;
protected object eof;
/** <summary>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.</summary>
*
* 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.
*/
protected IList nodes;
/** <summary>Pull nodes from which tree?</summary> */
protected object root;
/** <summary>IF this tree (root) was created from a token stream, track it.</summary> */
protected ITokenStream tokens;
/** <summary>What tree adaptor was used to build these trees</summary> */
ITreeAdaptor adaptor;
/** <summary>Reuse same DOWN, UP navigation nodes unless this is true</summary> */
bool uniqueNavigationNodes = false;
/** <summary>The index into the nodes list of the current node (next node
* to consume). If -1, nodes array not filled yet.</summary>
*/
protected int p = -1;
/** <summary>Track the last mark() call result value for use in rewind().</summary> */
protected int lastMarker;
/** <summary>Stack of indexes used for push/pop calls</summary> */
protected Stack<int> calls;
public BufferedTreeNodeStream( object tree )
: this( new CommonTreeAdaptor(), tree )
{
}
public BufferedTreeNodeStream( ITreeAdaptor adaptor, object tree )
: this( adaptor, tree, DEFAULT_INITIAL_BUFFER_SIZE )
{
}
public BufferedTreeNodeStream( ITreeAdaptor adaptor, object tree, int initialBufferSize )
{
this.root = tree;
this.adaptor = adaptor;
nodes = new List<object>( initialBufferSize );
down = adaptor.Create( TokenTypes.Down, "DOWN" );
up = adaptor.Create( TokenTypes.Up, "UP" );
eof = adaptor.Create( TokenTypes.EndOfFile, "EOF" );
}
#region Properties
public virtual int Count
{
get
{
if ( p == -1 )
{
throw new InvalidOperationException( "Cannot determine the Count before the buffer is filled." );
}
return nodes.Count;
}
}
public virtual object TreeSource
{
get
{
return root;
}
}
public virtual string SourceName
{
get
{
return TokenStream.SourceName;
}
}
public virtual ITokenStream TokenStream
{
get
{
return tokens;
}
set
{
tokens = value;
}
}
public virtual ITreeAdaptor TreeAdaptor
{
get
{
return adaptor;
}
set
{
adaptor = value;
}
}
public virtual bool UniqueNavigationNodes
{
get
{
return uniqueNavigationNodes;
}
set
{
uniqueNavigationNodes = value;
}
}
public virtual IToken LastToken
{
get
{
return TreeAdaptor.GetToken(LB(1));
}
}
public virtual IToken LastRealToken
{
get
{
int i = 0;
IToken token;
do
{
i++;
token = TreeAdaptor.GetToken(LB(i));
} while (token != null && token.Line <= 0);
return token;
}
}
public virtual int MaxLookBehind
{
get
{
return int.MaxValue;
}
}
#endregion
/** Walk tree with depth-first-search and fill nodes buffer.
* Don't do DOWN, UP nodes if its a list (t is isNil).
*/
protected virtual void FillBuffer()
{
FillBuffer( root );
//Console.Out.WriteLine( "revIndex=" + tokenTypeToStreamIndexesMap );
p = 0; // buffer of nodes intialized now
}
public virtual void FillBuffer( object t )
{
bool nil = adaptor.IsNil( t );
if ( !nil )
{
nodes.Add( t ); // add this node
}
// add DOWN node if t has children
int n = adaptor.GetChildCount( t );
if ( !nil && n > 0 )
{
AddNavigationNode( TokenTypes.Down );
}
// and now add all its children
for ( int c = 0; c < n; c++ )
{
object child = adaptor.GetChild( t, c );
FillBuffer( child );
}
// add UP node if t has children
if ( !nil && n > 0 )
{
AddNavigationNode( TokenTypes.Up );
}
}
/** What is the stream index for node? 0..n-1
* Return -1 if node not found.
*/
protected virtual int GetNodeIndex( object node )
{
if ( p == -1 )
{
FillBuffer();
}
for ( int i = 0; i < nodes.Count; i++ )
{
object t = nodes[i];
if ( t == node )
{
return i;
}
}
return -1;
}
/** 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 virtual void AddNavigationNode( int ttype )
{
object navNode = null;
if ( ttype == TokenTypes.Down )
{
if ( UniqueNavigationNodes )
{
navNode = adaptor.Create( TokenTypes.Down, "DOWN" );
}
else
{
navNode = down;
}
}
else
{
if ( UniqueNavigationNodes )
{
navNode = adaptor.Create( TokenTypes.Up, "UP" );
}
else
{
navNode = up;
}
}
nodes.Add( navNode );
}
public virtual object this[int i]
{
get
{
if ( p == -1 )
{
throw new InvalidOperationException( "Cannot get the node at index i before the buffer is filled." );
}
return nodes[i];
}
}
public virtual object LT( int k )
{
if ( p == -1 )
{
FillBuffer();
}
if ( k == 0 )
{
return null;
}
if ( k < 0 )
{
return LB( -k );
}
//System.out.print("LT(p="+p+","+k+")=");
if ( ( p + k - 1 ) >= nodes.Count )
{
return eof;
}
return nodes[p + k - 1];
}
public virtual object GetCurrentSymbol()
{
return LT( 1 );
}
#if false
public virtual object getLastTreeNode()
{
int i = Index;
if ( i >= size() )
{
i--; // if at EOF, have to start one back
}
Console.Out.WriteLine( "start last node: " + i + " size==" + nodes.Count );
while ( i >= 0 &&
( adaptor.getType( this[i] ) == TokenTypes.EOF ||
adaptor.getType( this[i] ) == TokenTypes.UP ||
adaptor.getType( this[i] ) == TokenTypes.DOWN ) )
{
i--;
}
Console.Out.WriteLine( "stop at node: " + i + " " + nodes[i] );
return nodes[i];
}
#endif
/** <summary>Look backwards k nodes</summary> */
protected virtual object LB( int k )
{
if ( k == 0 )
{
return null;
}
if ( ( p - k ) < 0 )
{
return null;
}
return nodes[p - k];
}
public virtual void Consume()
{
if ( p == -1 )
{
FillBuffer();
}
p++;
}
public virtual int LA( int i )
{
return adaptor.GetType( LT( i ) );
}
public virtual int Mark()
{
if ( p == -1 )
{
FillBuffer();
}
lastMarker = Index;
return lastMarker;
}
public virtual void Release( int marker )
{
// no resources to release
}
public virtual int Index
{
get
{
return p;
}
}
public virtual void Rewind( int marker )
{
Seek( marker );
}
public virtual void Rewind()
{
Seek( lastMarker );
}
public virtual void Seek( int index )
{
if ( p == -1 )
{
FillBuffer();
}
p = index;
}
/** <summary>
* Make stream jump to a new location, saving old location.
* Switch back with pop().
* </summary>
*/
public virtual void Push( int index )
{
if ( calls == null )
{
calls = new Stack<int>();
}
calls.Push( p ); // save current index
Seek( index );
}
/** <summary>
* Seek back to previous index saved during last push() call.
* Return top of stack (return index).
* </summary>
*/
public virtual int Pop()
{
int ret = calls.Pop();
Seek( ret );
return ret;
}
public virtual void Reset()
{
p = 0;
lastMarker = 0;
if ( calls != null )
{
calls.Clear();
}
}
public virtual IEnumerator<object> Iterator()
{
if ( p == -1 )
{
FillBuffer();
}
return new StreamIterator( this );
}
// TREE REWRITE INTERFACE
public virtual void ReplaceChildren( object parent, int startChildIndex, int stopChildIndex, object t )
{
if ( parent != null )
{
adaptor.ReplaceChildren( parent, startChildIndex, stopChildIndex, t );
}
}
/** <summary>Used for testing, just return the token type stream</summary> */
public virtual string ToTokenTypeString()
{
if ( p == -1 )
{
FillBuffer();
}
StringBuilder buf = new StringBuilder();
for ( int i = 0; i < nodes.Count; i++ )
{
object t = nodes[i];
buf.Append( " " );
buf.Append( adaptor.GetType( t ) );
}
return buf.ToString();
}
/** <summary>Debugging</summary> */
public virtual string ToTokenString( int start, int stop )
{
if ( p == -1 )
{
FillBuffer();
}
StringBuilder buf = new StringBuilder();
for ( int i = start; i < nodes.Count && i <= stop; i++ )
{
object t = nodes[i];
buf.Append( " " );
buf.Append( adaptor.GetToken( t ) );
}
return buf.ToString();
}
public virtual string ToString( object start, object stop )
{
Console.Out.WriteLine( "toString" );
if ( start == null || stop == null )
{
return null;
}
if ( p == -1 )
{
throw new InvalidOperationException( "Buffer is not yet filled." );
}
//Console.Out.WriteLine( "stop: " + stop );
if ( start is CommonTree )
Console.Out.Write( "toString: " + ( (CommonTree)start ).Token + ", " );
else
Console.Out.WriteLine( start );
if ( stop is CommonTree )
Console.Out.WriteLine( ( (CommonTree)stop ).Token );
else
Console.Out.WriteLine( stop );
// if we have the token stream, use that to dump text in order
if ( tokens != null )
{
int beginTokenIndex = adaptor.GetTokenStartIndex( start );
int endTokenIndex = adaptor.GetTokenStopIndex( stop );
// if it's a tree, use start/stop index from start node
// else use token range from start/stop nodes
if ( adaptor.GetType( stop ) == TokenTypes.Up )
{
endTokenIndex = adaptor.GetTokenStopIndex( start );
}
else if ( adaptor.GetType( stop ) == TokenTypes.EndOfFile )
{
endTokenIndex = Count - 2; // don't use EOF
}
return tokens.ToString( beginTokenIndex, endTokenIndex );
}
// walk nodes looking for start
object t = null;
int i = 0;
for ( ; i < nodes.Count; i++ )
{
t = nodes[i];
if ( t == start )
{
break;
}
}
// now walk until we see stop, filling string buffer with text
StringBuilder buf = new StringBuilder();
t = nodes[i];
while ( t != stop )
{
string text = adaptor.GetText( t );
if ( text == null )
{
text = " " + adaptor.GetType( t ).ToString();
}
buf.Append( text );
i++;
t = nodes[i];
}
// include stop node too
string text2 = adaptor.GetText( stop );
if ( text2 == null )
{
text2 = " " + adaptor.GetType( stop ).ToString();
}
buf.Append( text2 );
return buf.ToString();
}
}
}