1 /* 2 * [The "BSD licence"] 3 * Copyright (c) 2005-2008 Terence Parr 4 * All rights reserved. 5 * 6 * Conversion to C#: 7 * Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc. 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. The name of the author may not be used to endorse or promote products 19 * derived from this software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 22 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 23 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 24 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 26 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 30 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33 namespace Antlr.Runtime.Misc 34 { 35 using ArgumentException = System.ArgumentException; 36 using InvalidOperationException = System.InvalidOperationException; 37 38 /** <summary> 39 * A lookahead queue that knows how to mark/release locations 40 * in the buffer for backtracking purposes. Any markers force the FastQueue 41 * superclass to keep all tokens until no more markers; then can reset 42 * to avoid growing a huge buffer. 43 * </summary> 44 */ 45 public abstract class LookaheadStream<T> 46 : FastQueue<T> 47 where T : class 48 { 49 /** Absolute token index. It's the index of the symbol about to be 50 * read via LT(1). Goes from 0 to numtokens. 51 */ 52 private int _currentElementIndex = 0; 53 54 private T _previousElement; 55 56 /** Track object returned by nextElement upon end of stream; 57 * Return it later when they ask for LT passed end of input. 58 */ 59 T _eof = null; 60 61 /** <summary>Track the last mark() call result value for use in rewind().</summary> */ 62 int _lastMarker; 63 64 /** <summary>tracks how deep mark() calls are nested</summary> */ 65 int _markDepth; 66 67 public T EndOfFile 68 { 69 get 70 { 71 return _eof; 72 } 73 protected set 74 { 75 _eof = value; 76 } 77 } 78 79 public T PreviousElement 80 { 81 get 82 { 83 return _previousElement; 84 } 85 } 86 Clear()87 public override void Clear() 88 { 89 base.Clear(); 90 _currentElementIndex = 0; 91 _p = 0; 92 _previousElement = null; 93 } 94 95 /** <summary> 96 * Implement nextElement to supply a stream of elements to this 97 * lookahead buffer. Return eof upon end of the stream we're pulling from. 98 * </summary> 99 */ NextElement()100 public abstract T NextElement(); 101 IsEndOfFile(T o)102 public abstract bool IsEndOfFile(T o); 103 104 /** <summary>Get and remove first element in queue; override FastQueue.remove()</summary> */ Dequeue()105 public override T Dequeue() 106 { 107 T o = this[0]; 108 _p++; 109 // have we hit end of buffer and not backtracking? 110 if ( _p == _data.Count && _markDepth == 0 ) 111 { 112 // if so, it's an opportunity to start filling at index 0 again 113 Clear(); // size goes to 0, but retains memory 114 } 115 return o; 116 } 117 118 /** <summary>Make sure we have at least one element to remove, even if EOF</summary> */ Consume()119 public virtual void Consume() 120 { 121 SyncAhead(1); 122 _previousElement = Dequeue(); 123 _currentElementIndex++; 124 } 125 126 /** <summary> 127 * Make sure we have 'need' elements from current position p. Last valid 128 * p index is data.size()-1. p+need-1 is the data index 'need' elements 129 * ahead. If we need 1 element, (p+1-1)==p must be < data.size(). 130 * </summary> 131 */ SyncAhead( int need )132 protected virtual void SyncAhead( int need ) 133 { 134 int n = ( _p + need - 1 ) - _data.Count + 1; // how many more elements we need? 135 if ( n > 0 ) 136 Fill( n ); // out of elements? 137 } 138 139 /** <summary>add n elements to buffer</summary> */ Fill( int n )140 public virtual void Fill( int n ) 141 { 142 for ( int i = 0; i < n; i++ ) 143 { 144 T o = NextElement(); 145 if ( IsEndOfFile(o) ) 146 _eof = o; 147 148 _data.Add( o ); 149 } 150 } 151 152 /** <summary>Size of entire stream is unknown; we only know buffer size from FastQueue</summary> */ 153 public override int Count 154 { 155 get 156 { 157 throw new System.NotSupportedException( "streams are of unknown size" ); 158 } 159 } 160 LT( int k )161 public virtual T LT( int k ) 162 { 163 if ( k == 0 ) 164 { 165 return null; 166 } 167 if ( k < 0 ) 168 { 169 return LB(-k); 170 } 171 172 SyncAhead( k ); 173 if ((_p + k - 1) > _data.Count) 174 return _eof; 175 176 return this[k - 1]; 177 } 178 179 public virtual int Index 180 { 181 get 182 { 183 return _currentElementIndex; 184 } 185 } 186 Mark()187 public virtual int Mark() 188 { 189 _markDepth++; 190 _lastMarker = _p; // track where we are in buffer, not absolute token index 191 return _lastMarker; 192 } 193 Release( int marker )194 public virtual void Release( int marker ) 195 { 196 if (_markDepth == 0) 197 throw new InvalidOperationException(); 198 199 _markDepth--; 200 } 201 Rewind( int marker )202 public virtual void Rewind( int marker ) 203 { 204 Seek( marker ); 205 Release( marker ); 206 } 207 Rewind()208 public virtual void Rewind() 209 { 210 Rewind( _lastMarker ); 211 } 212 213 /** <summary> 214 * Seek to a 0-indexed position within data buffer. Can't handle 215 * case where you seek beyond end of existing buffer. Normally used 216 * to seek backwards in the buffer. Does not force loading of nodes. 217 * Doesn't see to absolute position in input stream since this stream 218 * is unbuffered. Seeks only into our moving window of elements. 219 * </summary> 220 */ Seek( int index )221 public virtual void Seek( int index ) 222 { 223 _p = index; 224 } 225 LB(int k)226 protected virtual T LB(int k) 227 { 228 if (k == 1) 229 return _previousElement; 230 231 throw new ArgumentException("can't look backwards more than one token in this stream"); 232 } 233 } 234 } 235