1 /*
   2  * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package jdk.nashorn.internal.parser;
  27 
  28 /**
  29  *
  30  */
  31 
  32 /**
  33  * Handles streaming of tokens between lexer and parser.
  34  *
  35  */
  36 public class TokenStream {
  37     /** Initial buffer size. */
  38     private static final int INITIAL_SIZE = 256;
  39 
  40     /** Token buffer. */
  41     private long[] buffer;
  42 
  43     /** Token count. */
  44     private int count;
  45 
  46     /** Cursor to write position in buffer */
  47     private int in;
  48 
  49     /** Cursor to read position in buffer */
  50     private int out;
  51 
  52     /** Base index in buffer */
  53     private int base;
  54 
  55     /**
  56      * Constructor.
  57      */
  58     public TokenStream() {
  59         buffer = new long[INITIAL_SIZE];
  60         count = 0;
  61         in = 0;
  62         out = 0;
  63         base = 0;
  64     }
  65 
  66     /**
  67      * Get the next position in the buffer.
  68      * @param position Current position in buffer.
  69      * @return Next position in buffer.
  70      */
  71     private int next(final int position) {
  72         // Next position.
  73         int next = position + 1;
  74 
  75         // If exceeds buffer length.
  76         if (next >= buffer.length) {
  77             // Wrap around.
  78             next = 0;
  79         }
  80 
  81         return next;
  82     }
  83 
  84      /**
  85      * Get the index position in the buffer.
  86      * @param k Seek position.
  87      * @return Position in buffer.
  88      */
  89     private int index(final int k) {
  90         // Bias k.
  91         int index = k - (base - out);
  92 
  93         // If wrap around.
  94         if (index >= buffer.length) {
  95             index -= buffer.length;
  96         }
  97 
  98         return index;
  99     }
 100 
 101     /**
 102      * Test to see if stream is empty.
 103      * @return True if stream is empty.
 104      */
 105     public boolean isEmpty() {
 106         return count == 0;
 107     }
 108 
 109     /**
 110      * Test to see if stream is full.
 111      * @return True if stream is full.
 112      */
 113     public boolean isFull() {
 114         return count == buffer.length;
 115     }
 116 
 117     /**
 118      * Get the number of tokens in the buffer.
 119      * @return Number of tokens.
 120      */
 121     public int count() {
 122         return count;
 123     }
 124 
 125     /**
 126      * Get the index of the first token in the stream.
 127      * @return Index of first buffered token in the stream.
 128      */
 129     public int first() {
 130         return base;
 131     }
 132 
 133     /**
 134      * Get the index of the last token in the stream.
 135      * @return Index of last buffered token in the stream.
 136      */
 137     public int last() {
 138         return base + count - 1;
 139     }
 140 
 141     /**
 142      * Remove the last token in the stream.
 143      */
 144     public void removeLast() {
 145         if (count != 0) {
 146             count--;
 147             in--;
 148 
 149             if (in < 0) {
 150                 in = buffer.length - 1;
 151             }
 152         }
 153     }
 154 
 155     /**
 156      * Put a token descriptor to the stream.
 157      * @param token Token descriptor to add.
 158      */
 159     public void put(final long token) {
 160         if (count == buffer.length) {
 161             grow();
 162         }
 163 
 164         buffer[in] = token;
 165         count++;
 166         in = next(in);
 167     }
 168 
 169     /**
 170      * Get the kth token descriptor from the stream.
 171      * @param k index
 172      * @return Token descriptor.
 173      */
 174     public long get(final int k) {
 175         return buffer[index(k)];
 176     }
 177 
 178     /**
 179      * Advances the base of the stream.
 180      * @param k Position of token to be the new base.
 181      */
 182     public void commit(final int k) {
 183         // Advance out.
 184         out = index(k);
 185         // Adjust count.
 186         count -= k - base;
 187         // Set base.
 188         base = k;
 189     }
 190 
 191     /**
 192      * Grow the buffer to accommodate more token descriptors.
 193      */
 194     public void grow() {
 195         // Allocate new buffer.
 196         final long[] newBuffer = new long[buffer.length * 2];
 197 
 198         // If single chunk.
 199         if (in > out) {
 200             System.arraycopy(buffer, out, newBuffer, 0, count);
 201         } else {
 202             final int portion = buffer.length - out;
 203             System.arraycopy(buffer, out, newBuffer, 0, portion);
 204             System.arraycopy(buffer, 0, newBuffer, portion, count - portion);
 205         }
 206 
 207         // Update buffer and indices.
 208         out = 0;
 209         in = count;
 210         buffer = newBuffer;
 211     }
 212 
 213     void reset() {
 214         in = out = count = base = 0;
 215     }
 216 }