| /* |
| * [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(); |
| } |
| } |
| } |