1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [The "BSD licence"] 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Copyright (c) 2005-2008 Terence Parr 4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * All rights reserved. 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Conversion to C#: 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc. 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * All rights reserved. 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Redistribution and use in source and binary forms, with or without 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * modification, are permitted provided that the following conditions 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * are met: 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1. Redistributions of source code must retain the above copyright 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer. 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 2. Redistributions in binary form must reproduce the above copyright 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer in the 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * documentation and/or other materials provided with the distribution. 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 3. The name of the author may not be used to endorse or promote products 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * derived from this software without specific prior written permission. 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvernamespace Antlr.Runtime.Misc { 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver using IndexOutOfRangeException = System.IndexOutOfRangeException; 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A lookahead queue that knows how to mark/release locations 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * in the buffer for backtracking purposes. Any markers force the FastQueue 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * superclass to keep all tokens until no more markers; then can reset 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to avoid growing a huge buffer. 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public abstract class LookaheadStream<T> 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver : FastQueue<T> 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver where T : class { 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Absolute token index. It's the index of the symbol about to be 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * read via LT(1). Goes from 0 to numtokens. 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver private int _currentElementIndex = 0; 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver private T _previousElement; 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Track object returned by nextElement upon end of stream; 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Return it later when they ask for LT passed end of input. 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver T _eof = null; 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Track the last mark() call result value for use in rewind().</summary> */ 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int _lastMarker; 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>tracks how deep mark() calls are nested</summary> */ 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int _markDepth; 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public T EndOfFile { 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get { 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return _eof; 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected set { 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _eof = value; 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public override void Clear() { 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver base.Clear(); 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _currentElementIndex = 0; 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _p = 0; 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _previousElement = null; 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Implement nextElement to supply a stream of elements to this 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * lookahead buffer. Return eof upon end of the stream we're pulling from. 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public abstract T NextElement(); 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public abstract bool IsEndOfFile(T o); 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Get and remove first element in queue; override FastQueue.remove()</summary> */ 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public override T Dequeue() { 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver T o = this[0]; 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _p++; 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // have we hit end of buffer and not backtracking? 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (_p == _data.Count && _markDepth == 0) { 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if so, it's an opportunity to start filling at index 0 again 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Clear(); // size goes to 0, but retains memory 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return o; 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Make sure we have at least one element to remove, even if EOF</summary> */ 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void Consume() { 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SyncAhead(1); 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _previousElement = Dequeue(); 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _currentElementIndex++; 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Make sure we have 'need' elements from current position p. Last valid 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * p index is data.size()-1. p+need-1 is the data index 'need' elements 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * ahead. If we need 1 element, (p+1-1)==p must be < data.size(). 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected virtual void SyncAhead(int need) { 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = (_p + need - 1) - _data.Count + 1; // how many more elements we need? 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (n > 0) 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Fill(n); // out of elements? 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>add n elements to buffer</summary> */ 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void Fill(int n) { 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n; i++) { 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver T o = NextElement(); 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (IsEndOfFile(o)) 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _eof = o; 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _data.Add(o); 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Size of entire stream is unknown; we only know buffer size from FastQueue</summary> */ 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public override int Count { 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get { 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new System.NotSupportedException("streams are of unknown size"); 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual T LT(int k) { 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (k == 0) { 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (k < 0) { 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return LB(-k); 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SyncAhead(k); 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ((_p + k - 1) > _data.Count) 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return _eof; 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return this[k - 1]; 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual int Index { 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get { 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return _currentElementIndex; 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual int Mark() { 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _markDepth++; 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _lastMarker = _p; // track where we are in buffer, not absolute token index 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return _lastMarker; 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void Release(int marker) { 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _markDepth--; 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void Rewind(int marker) { 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Seek(marker); 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Release(marker); 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void Rewind() { 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Seek(_lastMarker); 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Seek to a 0-indexed position within data buffer. Can't handle 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * case where you seek beyond end of existing buffer. Normally used 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to seek backwards in the buffer. Does not force loading of nodes. 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Doesn't see to absolute position in input stream since this stream 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is unbuffered. Seeks only into our moving window of elements. 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void Seek(int index) { 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _p = index; 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected virtual T LB(int k) { 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (k == 1) 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return _previousElement; 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new IndexOutOfRangeException("can't look backwards more than one token in this stream"); 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 198