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 Debug = System.Diagnostics.Debug; 37 using InvalidOperationException = System.InvalidOperationException; 38 using NotSupportedException = System.NotSupportedException; 39 using ArgumentOutOfRangeException = System.ArgumentOutOfRangeException; 40 41 /** <summary> 42 * A lookahead queue that knows how to mark/release locations in the buffer for 43 * backtracking purposes. Any markers force the {@link FastQueue} superclass to 44 * keep all elements until no more markers; then can reset to avoid growing a 45 * huge buffer. 46 * </summary> 47 */ 48 public abstract class LookaheadStream<T> 49 : FastQueue<T> 50 where T : class 51 { 52 /** Absolute token index. It's the index of the symbol about to be 53 * read via {@code LT(1)}. Goes from 0 to numtokens. 54 */ 55 private int _currentElementIndex = 0; 56 57 /** 58 * This is the {@code LT(-1)} element for the first element in {@link #data}. 59 */ 60 private T _previousElement; 61 62 /** Track object returned by nextElement upon end of stream; 63 * Return it later when they ask for LT passed end of input. 64 */ 65 T _eof = null; 66 67 /** <summary>Track the last mark() call result value for use in rewind().</summary> */ 68 int _lastMarker; 69 70 /** <summary>tracks how deep mark() calls are nested</summary> */ 71 int _markDepth; 72 73 public T EndOfFile 74 { 75 get 76 { 77 return _eof; 78 } 79 protected set 80 { 81 _eof = value; 82 } 83 } 84 85 public T PreviousElement 86 { 87 get 88 { 89 return _previousElement; 90 } 91 } 92 Reset()93 public virtual void Reset() 94 { 95 Clear(); 96 _currentElementIndex = 0; 97 _p = 0; 98 _previousElement = null; 99 } 100 101 /** <summary> 102 * Implement nextElement to supply a stream of elements to this 103 * lookahead buffer. Return EOF upon end of the stream we're pulling from. 104 * </summary> 105 */ NextElement()106 public abstract T NextElement(); 107 IsEndOfFile(T o)108 public abstract bool IsEndOfFile(T o); 109 110 /** <summary> 111 * Get and remove first element in queue; override 112 * {@link FastQueue#remove()}; it's the same, just checks for backtracking. 113 * </summary> */ Dequeue()114 public override T Dequeue() 115 { 116 T o = this[0]; 117 _p++; 118 // have we hit end of buffer and not backtracking? 119 if ( _p == _data.Count && _markDepth == 0 ) 120 { 121 _previousElement = o; 122 // if so, it's an opportunity to start filling at index 0 again 123 Clear(); // size goes to 0, but retains memory 124 } 125 return o; 126 } 127 128 /** <summary>Make sure we have at least one element to remove, even if EOF</summary> */ Consume()129 public virtual void Consume() 130 { 131 SyncAhead(1); 132 Dequeue(); 133 _currentElementIndex++; 134 } 135 136 /** <summary> 137 * Make sure we have 'need' elements from current position p. Last valid 138 * p index is data.size()-1. p+need-1 is the data index 'need' elements 139 * ahead. If we need 1 element, (p+1-1)==p must be < data.size(). 140 * </summary> 141 */ SyncAhead( int need )142 protected virtual void SyncAhead( int need ) 143 { 144 int n = ( _p + need - 1 ) - _data.Count + 1; // how many more elements we need? 145 if ( n > 0 ) 146 Fill( n ); // out of elements? 147 } 148 149 /** <summary>add n elements to buffer</summary> */ Fill( int n )150 public virtual void Fill( int n ) 151 { 152 for ( int i = 0; i < n; i++ ) 153 { 154 T o = NextElement(); 155 if ( IsEndOfFile(o) ) 156 _eof = o; 157 158 _data.Add( o ); 159 } 160 } 161 162 /** <summary>Size of entire stream is unknown; we only know buffer size from FastQueue</summary> */ 163 public override int Count 164 { 165 get 166 { 167 throw new System.NotSupportedException( "streams are of unknown size" ); 168 } 169 } 170 LT( int k )171 public virtual T LT( int k ) 172 { 173 if ( k == 0 ) 174 { 175 return null; 176 } 177 if ( k < 0 ) 178 { 179 return LB(-k); 180 } 181 182 SyncAhead( k ); 183 if ((_p + k - 1) > _data.Count) 184 return _eof; 185 186 return this[k - 1]; 187 } 188 189 public virtual int Index 190 { 191 get 192 { 193 return _currentElementIndex; 194 } 195 } 196 Mark()197 public virtual int Mark() 198 { 199 _markDepth++; 200 _lastMarker = _p; // track where we are in buffer, not absolute token index 201 return _lastMarker; 202 } 203 Release( int marker )204 public virtual void Release( int marker ) 205 { 206 if (_markDepth == 0) 207 throw new InvalidOperationException(); 208 209 _markDepth--; 210 } 211 Rewind( int marker )212 public virtual void Rewind( int marker ) 213 { 214 _markDepth--; 215 int delta = _p - marker; 216 _currentElementIndex -= delta; 217 _p = marker; 218 } 219 Rewind()220 public virtual void Rewind() 221 { 222 // rewind but do not release marker 223 int delta = _p - _lastMarker; 224 _currentElementIndex -= delta; 225 _p = _lastMarker; 226 } 227 228 /** <summary> 229 * Seek to a 0-indexed absolute token index. Normally used to seek backwards 230 * in the buffer. Does not force loading of nodes. 231 * </summary> 232 * <remarks> 233 * To preserve backward compatibility, this method allows seeking past the 234 * end of the currently buffered data. In this case, the input pointer will 235 * be moved but the data will only actually be loaded upon the next call to 236 * {@link #consume} or {@link #LT} for {@code k>0}. 237 * </remarks> 238 */ Seek( int index )239 public virtual void Seek( int index ) 240 { 241 if (index < 0) 242 throw new ArgumentOutOfRangeException("index"); 243 244 int delta = _currentElementIndex - index; 245 if (_p - delta < 0) 246 throw new NotSupportedException("can't seek before the beginning of this stream's buffer"); 247 248 _p -= delta; 249 _currentElementIndex = index; 250 } 251 LB(int k)252 protected virtual T LB(int k) 253 { 254 Debug.Assert(k > 0); 255 256 int index = _p - k; 257 if (index == -1) 258 return _previousElement; 259 260 // if k>0 then we know index < data.size(). avoid the double-check for 261 // performance. 262 if (index >= 0 /*&& index < data.size()*/) 263 return _data[index]; 264 265 if (index < -1) 266 throw new NotSupportedException("can't look more than one token before the beginning of this stream's buffer"); 267 268 throw new NotSupportedException("can't look past the end of this stream's buffer using LB(int)"); 269 } 270 } 271 } 272