13447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein/* 23447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein [The "BSD license"] 33447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Copyright (c) 2005-2009 Terence Parr 43447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein All rights reserved. 53447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 63447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Redistribution and use in source and binary forms, with or without 73447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein modification, are permitted provided that the following conditions 83447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein are met: 93447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1. Redistributions of source code must retain the above copyright 103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein notice, this list of conditions and the following disclaimer. 113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2. Redistributions in binary form must reproduce the above copyright 123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein notice, this list of conditions and the following disclaimer in the 133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein documentation and/or other materials provided with the distribution. 143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 3. The name of the author may not be used to endorse or promote products 153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein derived from this software without specific prior written permission. 163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinpackage org.antlr.runtime.misc; 293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport org.antlr.runtime.Token; 313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport java.util.NoSuchElementException; 333447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 343447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein/** A lookahead queue that knows how to mark/release locations 353447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * in the buffer for backtracking purposes. Any markers force the FastQueue 363447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * superclass to keep all tokens until no more markers; then can reset 373447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * to avoid growing a huge buffer. 383447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 393447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinpublic abstract class LookaheadStream<T> extends FastQueue<T> { 403447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public static final int UNINITIALIZED_EOF_ELEMENT_INDEX = Integer.MAX_VALUE; 413447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 423447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Absolute token index. It's the index of the symbol about to be 433447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * read via LT(1). Goes from 0 to numtokens. 443447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 453447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected int currentElementIndex = 0; 463447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 473447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected T prevElement; 483447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 493447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Track object returned by nextElement upon end of stream; 503447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * Return it later when they ask for LT passed end of input. 513447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 523447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public T eof = null; 533447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 543447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Track the last mark() call result value for use in rewind(). */ 553447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected int lastMarker; 563447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 573447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** tracks how deep mark() calls are nested */ 583447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected int markDepth = 0; 593447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 603447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void reset() { 613447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein super.reset(); 623447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein currentElementIndex = 0; 633447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein p = 0; 643447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein prevElement=null; 653447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 663447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 673447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Implement nextElement to supply a stream of elements to this 683447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * lookahead buffer. Return eof upon end of the stream we're pulling from. 693447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 703447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public abstract T nextElement(); 713447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 723447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public abstract boolean isEOF(T o); 733447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 743447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Get and remove first element in queue; override FastQueue.remove(); 753447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * it's the same, just checks for backtracking. 763447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 773447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public T remove() { 783447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein T o = elementAt(0); 793447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein p++; 803447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // have we hit end of buffer and not backtracking? 813447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( p == data.size() && markDepth==0 ) { 823447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // if so, it's an opportunity to start filling at index 0 again 833447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein clear(); // size goes to 0, but retains memory 843447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 853447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return o; 863447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 873447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 883447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Make sure we have at least one element to remove, even if EOF */ 893447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void consume() { 903447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein syncAhead(1); 913447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein prevElement = remove(); 923447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein currentElementIndex++; 933447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 943447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 953447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Make sure we have 'need' elements from current position p. Last valid 963447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * p index is data.size()-1. p+need-1 is the data index 'need' elements 973447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * ahead. If we need 1 element, (p+1-1)==p must be < data.size(). 983447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 993447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected void syncAhead(int need) { 1003447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int n = (p+need-1) - data.size() + 1; // how many more elements we need? 1013447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( n > 0 ) fill(n); // out of elements? 1023447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1033447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1043447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** add n elements to buffer */ 1053447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void fill(int n) { 1063447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int i=1; i<=n; i++) { 1073447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein T o = nextElement(); 1083447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( isEOF(o) ) eof = o; 1093447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein data.add(o); 1103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Size of entire stream is unknown; we only know buffer size from FastQueue */ 1143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public int size() { throw new UnsupportedOperationException("streams are of unknown size"); } 1153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public T LT(int k) { 1173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( k==0 ) { 1183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return null; 1193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( k<0 ) return LB(-k); 1213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein //System.out.print("LT(p="+p+","+k+")="); 1223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein syncAhead(k); 1233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( (p+k-1) > data.size() ) return eof; 1243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return elementAt(k-1); 1253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public int index() { return currentElementIndex; } 1283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public int mark() { 1303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein markDepth++; 1313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein lastMarker = p; // track where we are in buffer not absolute token index 1323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return lastMarker; 1333447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1343447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1353447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void release(int marker) { 1363447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // no resources to release 1373447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1383447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1393447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void rewind(int marker) { 1403447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein markDepth--; 1413447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein seek(marker); // assume marker is top 1423447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // release(marker); // waste of call; it does nothing in this class 1433447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1443447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1453447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void rewind() { 1463447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein seek(lastMarker); // rewind but do not release marker 1473447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1483447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1493447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Seek to a 0-indexed position within data buffer. Can't handle 1503447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * case where you seek beyond end of existing buffer. Normally used 1513447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * to seek backwards in the buffer. Does not force loading of nodes. 1523447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * Doesn't see to absolute position in input stream since this stream 1533447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * is unbuffered. Seeks only into our moving window of elements. 1543447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 1553447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void seek(int index) { p = index; } 1563447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1573447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected T LB(int k) { 1583447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( k==1 ) return prevElement; 1593447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein throw new NoSuchElementException("can't look backwards more than one token in this stream"); 1603447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1613447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein}