diff options
Diffstat (limited to 'runtime/CSharp3/Sources/Antlr3.Runtime/Misc')
4 files changed, 515 insertions, 0 deletions
diff --git a/runtime/CSharp3/Sources/Antlr3.Runtime/Misc/FastQueue.cs b/runtime/CSharp3/Sources/Antlr3.Runtime/Misc/FastQueue.cs new file mode 100644 index 0000000..2dc5bfc --- /dev/null +++ b/runtime/CSharp3/Sources/Antlr3.Runtime/Misc/FastQueue.cs @@ -0,0 +1,143 @@ +/* + * [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.Misc +{ + using System.Collections.Generic; + using ArgumentException = System.ArgumentException; + using InvalidOperationException = System.InvalidOperationException; + + /** A queue that can dequeue and get(i) in O(1) and grow arbitrarily large. + * A linked list is fast at dequeue but slow at get(i). An array is + * the reverse. This is O(1) for both operations. + * + * List grows until you dequeue last element at end of buffer. Then + * it resets to start filling at 0 again. If adds/removes are balanced, the + * buffer will not grow too large. + * + * No iterator stuff as that's not how we'll use it. + */ + public class FastQueue<T> + { + /** <summary>dynamically-sized buffer of elements</summary> */ + internal List<T> _data = new List<T>(); + /** <summary>index of next element to fill</summary> */ + internal int _p = 0; + + public virtual int Count + { + get + { + return _data.Count - _p; + } + } + + /// <summary> + /// How deep have we gone? + /// </summary> + public virtual int Range + { + get; + protected set; + } + + /** <summary> + * Return element i elements ahead of current element. i==0 gets + * current element. This is not an absolute index into the data list + * since p defines the start of the real list. + * </summary> + */ + public virtual T this[int i] + { + get + { + int absIndex = _p + i; + if (absIndex >= _data.Count) + throw new ArgumentException(string.Format("queue index {0} > last index {1}", absIndex, _data.Count - 1)); + if (absIndex < 0) + throw new ArgumentException(string.Format("queue index {0} < 0", absIndex)); + + if (absIndex > Range) + Range = absIndex; + + return _data[absIndex]; + } + } + + /** <summary>Get and remove first element in queue</summary> */ + public virtual T Dequeue() + { + if (Count == 0) + throw new InvalidOperationException(); + + T o = this[0]; + _p++; + // have we hit end of buffer? + if ( _p == _data.Count ) + { + // if so, it's an opportunity to start filling at index 0 again + Clear(); // size goes to 0, but retains memory + } + return o; + } + + public virtual void Enqueue( T o ) + { + _data.Add( o ); + } + + public virtual T Peek() + { + return this[0]; + } + + public virtual void Clear() + { + _p = 0; + _data.Clear(); + } + + /** <summary>Return string of current buffer contents; non-destructive</summary> */ + public override string ToString() + { + System.Text.StringBuilder buf = new System.Text.StringBuilder(); + int n = Count; + for ( int i = 0; i < n; i++ ) + { + buf.Append( this[i] ); + if ( ( i + 1 ) < n ) + buf.Append( " " ); + } + return buf.ToString(); + } + } +} diff --git a/runtime/CSharp3/Sources/Antlr3.Runtime/Misc/FunctionDelegates.cs b/runtime/CSharp3/Sources/Antlr3.Runtime/Misc/FunctionDelegates.cs new file mode 100644 index 0000000..4fb91bf --- /dev/null +++ b/runtime/CSharp3/Sources/Antlr3.Runtime/Misc/FunctionDelegates.cs @@ -0,0 +1,40 @@ +/* + * [The "BSD license"] + * Copyright (c) 2011 Terence Parr + * All rights reserved. + * + * Conversion to C#: + * Copyright (c) 2011 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.Misc +{ + public delegate void Action(); + + public delegate TResult Func<TResult>(); + + public delegate TResult Func<T, TResult>(T arg); +} diff --git a/runtime/CSharp3/Sources/Antlr3.Runtime/Misc/ListStack`1.cs b/runtime/CSharp3/Sources/Antlr3.Runtime/Misc/ListStack`1.cs new file mode 100644 index 0000000..e66adcb --- /dev/null +++ b/runtime/CSharp3/Sources/Antlr3.Runtime/Misc/ListStack`1.cs @@ -0,0 +1,98 @@ +/* + * [The "BSD license"] + * Copyright (c) 2011 Terence Parr + * All rights reserved. + * + * Conversion to C#: + * Copyright (c) 2011 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.Misc +{ + using System.Collections.Generic; + using InvalidOperationException = System.InvalidOperationException; + + public class ListStack<T> : List<T> + { + public T Peek() + { + return Peek(0); + } + + public T Peek(int depth) + { + T item; + if (!TryPeek(depth, out item)) + throw new InvalidOperationException(); + + return item; + } + + public bool TryPeek(out T item) + { + return TryPeek(0, out item); + } + + public bool TryPeek(int depth, out T item) + { + if (depth >= Count) + { + item = default(T); + return false; + } + + item = this[Count - depth - 1]; + return true; + } + + public T Pop() + { + T result; + if (!TryPop(out result)) + throw new InvalidOperationException(); + + return result; + } + + public bool TryPop(out T item) + { + if (Count == 0) + { + item = default(T); + return false; + } + + item = this[Count - 1]; + RemoveAt(Count - 1); + return true; + } + + public void Push(T item) + { + Add(item); + } + } +} diff --git a/runtime/CSharp3/Sources/Antlr3.Runtime/Misc/LookaheadStream.cs b/runtime/CSharp3/Sources/Antlr3.Runtime/Misc/LookaheadStream.cs new file mode 100644 index 0000000..24dc0cb --- /dev/null +++ b/runtime/CSharp3/Sources/Antlr3.Runtime/Misc/LookaheadStream.cs @@ -0,0 +1,234 @@ +/* + * [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.Misc +{ + using ArgumentException = System.ArgumentException; + using InvalidOperationException = System.InvalidOperationException; + + /** <summary> + * A lookahead queue that knows how to mark/release locations + * in the buffer for backtracking purposes. Any markers force the FastQueue + * superclass to keep all tokens until no more markers; then can reset + * to avoid growing a huge buffer. + * </summary> + */ + public abstract class LookaheadStream<T> + : FastQueue<T> + where T : class + { + /** Absolute token index. It's the index of the symbol about to be + * read via LT(1). Goes from 0 to numtokens. + */ + private int _currentElementIndex = 0; + + private T _previousElement; + + /** Track object returned by nextElement upon end of stream; + * Return it later when they ask for LT passed end of input. + */ + T _eof = null; + + /** <summary>Track the last mark() call result value for use in rewind().</summary> */ + int _lastMarker; + + /** <summary>tracks how deep mark() calls are nested</summary> */ + int _markDepth; + + public T EndOfFile + { + get + { + return _eof; + } + protected set + { + _eof = value; + } + } + + public T PreviousElement + { + get + { + return _previousElement; + } + } + + public override void Clear() + { + base.Clear(); + _currentElementIndex = 0; + _p = 0; + _previousElement = null; + } + + /** <summary> + * Implement nextElement to supply a stream of elements to this + * lookahead buffer. Return eof upon end of the stream we're pulling from. + * </summary> + */ + public abstract T NextElement(); + + public abstract bool IsEndOfFile(T o); + + /** <summary>Get and remove first element in queue; override FastQueue.remove()</summary> */ + public override T Dequeue() + { + T o = this[0]; + _p++; + // have we hit end of buffer and not backtracking? + if ( _p == _data.Count && _markDepth == 0 ) + { + // if so, it's an opportunity to start filling at index 0 again + Clear(); // size goes to 0, but retains memory + } + return o; + } + + /** <summary>Make sure we have at least one element to remove, even if EOF</summary> */ + public virtual void Consume() + { + SyncAhead(1); + _previousElement = Dequeue(); + _currentElementIndex++; + } + + /** <summary> + * Make sure we have 'need' elements from current position p. Last valid + * p index is data.size()-1. p+need-1 is the data index 'need' elements + * ahead. If we need 1 element, (p+1-1)==p must be < data.size(). + * </summary> + */ + protected virtual void SyncAhead( int need ) + { + int n = ( _p + need - 1 ) - _data.Count + 1; // how many more elements we need? + if ( n > 0 ) + Fill( n ); // out of elements? + } + + /** <summary>add n elements to buffer</summary> */ + public virtual void Fill( int n ) + { + for ( int i = 0; i < n; i++ ) + { + T o = NextElement(); + if ( IsEndOfFile(o) ) + _eof = o; + + _data.Add( o ); + } + } + + /** <summary>Size of entire stream is unknown; we only know buffer size from FastQueue</summary> */ + public override int Count + { + get + { + throw new System.NotSupportedException( "streams are of unknown size" ); + } + } + + public virtual T LT( int k ) + { + if ( k == 0 ) + { + return null; + } + if ( k < 0 ) + { + return LB(-k); + } + + SyncAhead( k ); + if ((_p + k - 1) > _data.Count) + return _eof; + + return this[k - 1]; + } + + public virtual int Index + { + get + { + return _currentElementIndex; + } + } + + public virtual int Mark() + { + _markDepth++; + _lastMarker = _p; // track where we are in buffer, not absolute token index + return _lastMarker; + } + + public virtual void Release( int marker ) + { + if (_markDepth == 0) + throw new InvalidOperationException(); + + _markDepth--; + } + + public virtual void Rewind( int marker ) + { + Seek( marker ); + Release( marker ); + } + + public virtual void Rewind() + { + Rewind( _lastMarker ); + } + + /** <summary> + * Seek to a 0-indexed position within data buffer. Can't handle + * case where you seek beyond end of existing buffer. Normally used + * to seek backwards in the buffer. Does not force loading of nodes. + * Doesn't see to absolute position in input stream since this stream + * is unbuffered. Seeks only into our moving window of elements. + * </summary> + */ + public virtual void Seek( int index ) + { + _p = index; + } + + protected virtual T LB(int k) + { + if (k == 1) + return _previousElement; + + throw new ArgumentException("can't look backwards more than one token in this stream"); + } + } +} |