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 &lt; 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