1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver[The "BSD licence"] 3324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverCopyright (c) 2005-2008 Terence Parr 4324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverAll rights reserved. 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 6324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverRedistribution and use in source and binary forms, with or without 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvermodification, are permitted provided that the following conditions 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverare met: 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver1. Redistributions of source code must retain the above copyright 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvernotice, this list of conditions and the following disclaimer. 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver2. Redistributions in binary form must reproduce the above copyright 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvernotice, this list of conditions and the following disclaimer in the 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverdocumentation and/or other materials provided with the distribution. 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver3. The name of the author may not be used to endorse or promote products 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverderived from this software without specific prior written permission. 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 17324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverTHIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverIMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverOF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverIN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverINCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverNOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverDATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverTHEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverTHIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver*/ 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpackage org.antlr.runtime.misc; 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.List; 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.ArrayList; 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** A lookahead queue that knows how to mark/release locations 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * in the buffer for backtracking purposes. Any markers force the FastQueue 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * superclass to keep all tokens until no more markers; then can reset 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to avoid growing a huge buffer. 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpublic abstract class LookaheadStream<T> extends FastQueue<T> { 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int UNINITIALIZED_EOF_ELEMENT_INDEX = Integer.MAX_VALUE; 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Set to buffer index of eof when nextElement returns eof */ 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected int eofElementIndex = UNINITIALIZED_EOF_ELEMENT_INDEX; 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Returned by nextElement upon end of stream; we add to buffer also */ 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public T eof = null; 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Track the last mark() call result value for use in rewind(). */ 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected int lastMarker; 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** tracks how deep mark() calls are nested */ 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected int markDepth = 0; 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public LookaheadStream(T eof) { 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.eof = eof; 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void reset() { 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver eofElementIndex = UNINITIALIZED_EOF_ELEMENT_INDEX; 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver super.reset(); 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Implement nextElement to supply a stream of elements to this 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * lookahead buffer. Return eof upon end of the stream we're pulling from. 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public abstract T nextElement(); 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Get and remove first element in queue; override FastQueue.remove() */ 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public T remove() { 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver T o = get(0); 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver p++; 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // have we hit end of buffer and not backtracking? 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( p == data.size() && markDepth==0 ) { 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if so, it's an opportunity to start filling at index 0 again 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver clear(); // size goes to 0, but retains memory 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return o; 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Make sure we have at least one element to remove, even if EOF */ 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void consume() { sync(1); remove(); } 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Make sure we have 'need' elements from current position p. Last valid 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * p index is data.size()-1. p+need-1 is the data index 'need' elements 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * ahead. If we need 1 element, (p+1-1)==p must be < data.size(). 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void sync(int need) { 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = (p+need-1) - data.size() + 1; // how many more elements we need? 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( n > 0 ) fill(n); // out of elements? 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** add n elements to buffer */ 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void fill(int n) { 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i=1; i<=n; i++) { 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver T o = nextElement(); 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( o==eof ) { 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver data.add(eof); 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver eofElementIndex = data.size()-1; 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else data.add(o); 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //public boolean hasNext() { return eofElementIndex!=UNINITIALIZED_EOF_ELEMENT_INDEX; } 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Size of entire stream is unknown; we only know buffer size from FastQueue */ 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int size() { throw new UnsupportedOperationException("streams are of unknown size"); } 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Object LT(int k) { 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( k==0 ) { 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( k<0 ) { 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return LB(-k); 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.print("LT(p="+p+","+k+")="); 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( (p+k-1) >= eofElementIndex ) { // move to super.LT 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return eof; 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver sync(k); 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return get(k-1); 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Look backwards k nodes */ 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Object LB(int k) { 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( k==0 ) { 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( (p-k)<0 ) { 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return get(-k); 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Object getCurrentSymbol() { return LT(1); } 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int index() { return p; } 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int mark() { 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver markDepth++; 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver lastMarker = index(); 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return lastMarker; 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void release(int marker) { 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // no resources to release 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void rewind(int marker) { 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver markDepth--; 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver seek(marker); // assume marker is top 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // release(marker); // waste of call; it does nothing in this class 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void rewind() { 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver seek(lastMarker); // rewind but do not release marker 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Seek to a 0-indexed position within data buffer. Can't handle 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * case where you seek beyond end of existing buffer. Normally used 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to seek backwards in the buffer. Does not force loading of nodes. 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void seek(int index) { p = index; } 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver}