LAState


1   /*
2    * The contents of this file are subject to the terms of the Common Development
3    * and Distribution License (the License). You may not use this file except in
4    * compliance with the License.
5    *
6    * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7    * or http://www.netbeans.org/cddl.txt.
8    *
9    * When distributing Covered Code, include this CDDL Header Notice in each file
10   * and include the License file at http://www.netbeans.org/cddl.txt.
11   * If applicable, add the following below the CDDL Header, with the fields
12   * enclosed by brackets [] replaced by your own identifying information:
13   * "Portions Copyrighted [year] [name of copyright owner]"
14   *
15   * The Original Software is NetBeans. The Initial Developer of the Original
16   * Software is Sun Microsystems, Inc. Portions Copyright 1997-2007 Sun
17   * Microsystems, Inc. All Rights Reserved.
18   */
19  
20  package org.netbeans.lib.lexer;
21  
22  import java.util.List  ;
23  
24  /**
25   * A structure holding lookahead and state of a token list.
26   *
27   * @author Miloslav Metelka
28   * @version 1.00
29   */
30  
31  public abstract class LAState {
32  
33      private static final LAState EMPTY = new NoState(0);
34  
35      public static LAState empty() {
36          return EMPTY;
37      }
38  
39      static int withExtraCapacity(int capacity) {
40          return capacity * 3 / 2 + 4;
41      }
42  
43      static boolean isByteState(Object   state) {
44          int intState;
45          return (state.getClass() == Integer  .class
46                  && (intState = ((Integer  )state).intValue()) >= 0 && intState <= Byte.MAX_VALUE);
47      }
48  
49  
50      int gapStart;
51  
52      int gapLength;
53  
54      public LAState(int capacity) {
55          gapLength = capacity;
56      }
57  
58      /**
59       * Get lookahead at the particular index
60       * preparing the state as well.
61       */
62      public abstract int lookahead(int index);
63  
64      public abstract Object   state(int index);
65  
66      public final LAState trimToSize() {
67          if (gapLength > 0) {
68              LAState laState = upgrade(size(), getClass());
69              reallocate(laState, size());
70              return laState;
71          }
72          return this;
73      }
74  
75      public final int size() {
76          return capacity() - gapLength;
77      }
78  
79      public final LAState add(int lookahead, Object   state) {
80          LAState ret;
81          if (gapLength > 0) { // enough space
82              moveGap(size());
83              ret = this;
84          } else { // no more space
85              // Called when doing TokenSequence.moveNext() - tokens get created lazily
86              // Double the capacity - Token lists should call trimToSize() after finishing
87              ret = upgrade((capacity() + 1) << 1, getClass());
88              reallocate(ret, size());
89          }
90  
91          Class   laStateCls;
92          if ((laStateCls = ret.addToGapStart(lookahead, state)) != null) {
93              ret = upgrade(capacity() + 1, laStateCls);
94              reallocate(ret, size());
95              ret.addToGapStart(lookahead, state);
96          }
97  
98          ret.gapStart += 1;
99          ret.gapLength -= 1;
100         return ret;
101     }
102 
103     public final LAState addAll(int index, LAState laState) {
104         LAState ret;
105         int laStateSize = laState.size();
106         if (!isUpgrade(laState.getClass()) && gapLength > laStateSize) { // enough space
107             moveGap(index);
108             ret = this;
109         } else { // no more space
110             // Called when fixing token list by TokenListUpdater
111             // Leave 10% for growth
112             ret = upgrade((int)((capacity() + laStateSize) * 110L / 100), laState.getClass());
113             reallocate(ret, index);
114         }
115 
116         laState.copyData(0, ret, ret.gapStart, laState.gapStart);
117         int laStateGapEnd = laState.gapStart + laState.gapLength;
118         laState.copyData(laStateGapEnd, ret, ret.gapStart + laState.gapStart,
119                 laState.capacity() - laStateGapEnd);
120 
121         ret.gapStart += laStateSize;
122         ret.gapLength -= laStateSize;
123         return ret;
124     }
125 
126     protected abstract LAState upgrade(int capacity, Class   laStateClass);
127 
128     protected abstract boolean isUpgrade(Class   laStateClass);
129 
130     protected abstract Class   addToGapStart(int lookahead, Object   state);
131 
132     public final void remove(int index, int count) {
133         moveGap(index + count);
134         gapStart -= count;
135         gapLength += count;
136     }
137 
138     protected void removeUpdate(int index, int length) {
139         // Do nothing
140     }
141 
142     protected final int rawIndex(int index) {
143         return (index < gapStart) ? index : index + gapLength;
144     }
145 
146     final void reallocate(LAState tgt, int newGapStart) {
147         tgt.gapStart = newGapStart;
148         tgt.gapLength = gapLength + tgt.capacity() - capacity();
149         int gapEnd = gapStart + gapLength;
150         if (newGapStart < gapStart) { // only partly allocate
151             copyData(0, tgt, 0, newGapStart);
152             int tgtRawIndex = newGapStart + tgt.gapLength;
153             int len = gapStart - newGapStart;
154             copyData(newGapStart, tgt, tgtRawIndex, len);
155             tgtRawIndex += len;
156             copyData(gapEnd, tgt, tgtRawIndex, capacity() - gapEnd);
157 
158         } else { // index above or equals gapStart
159             copyData(0, tgt, 0, gapStart);
160             int len = newGapStart - gapStart;
161             copyData(gapEnd, tgt, gapStart, len);
162             gapEnd += len;
163             copyData(gapEnd, tgt, newGapStart + tgt.gapLength, capacity() - gapEnd);
164         }
165     }
166 
167     protected abstract void copyData(int srcRawIndex, LAState tgt, int dstRawIndex, int len);
168 
169     protected abstract int capacity();
170 
171     final void moveGap(int index) {
172         if (index == gapStart)
173             return;
174         if (gapLength > 0) {
175             if (index < gapStart) { // move gap down
176                 int moveSize = gapStart - index;
177                 moveData(index, gapStart + gapLength - moveSize, moveSize);
178                 //clearEmpty(index, Math.min(moveSize, gapLength));
179 
180             } else { // above gap
181                 int gapEnd = gapStart + gapLength;
182                 int moveSize = index - gapStart;
183                 moveData(gapEnd, gapStart, moveSize);
184                 if (index < gapEnd) {
185                     //clearEmpty(gapEnd, moveSize);
186                 } else {
187                     //clearEmpty(index, gapLength);
188                 }
189             }
190         }
191         gapStart = index;
192     }
193 
194     protected abstract void moveData(int srcRawIndex, int dstRawIndex, int len);
195 
196     public String   toString() {
197         StringBuilder   sb = new StringBuilder  ("[");
198         for (int i = 0; i < size(); i++) {
199             if (i > 0) {
200                 sb.append(", ");
201             }
202             sb.append(lookahead(i));
203             sb.append(", ");
204             sb.append(state(i));
205         }
206         sb.append(']');
207         return sb.toString();
208     }
209 
210 
211     static final class NoState extends LAState {
212 
213         byte[] laBytes;
214 
215         NoState(int capacity) {
216             super(capacity);
217             laBytes = new byte[capacity];
218         }
219 
220         public int lookahead(int index) {
221             int rawIndex = rawIndex(index);
222             return laBytes[rawIndex];
223         }
224 
225         public Object   state(int index) {
226             return null;
227         }
228 
229         protected LAState upgrade(int capacity, Class   laStateClass) {
230             if (laStateClass == LargeState.class) {
231                 return new LargeState(capacity);
232             } else if (laStateClass == ByteState.class) {
233                 return new ByteState(capacity);
234             } else {
235                 return new NoState(capacity);
236             }
237         }
238 
239         protected boolean isUpgrade(Class   laStateClass) {
240             return (laStateClass == LargeState.class) || (laStateClass == ByteState.class);
241         }
242 
243         protected void copyData(int srcRawIndex, LAState tgt, int dstRawIndex, int len) {
244             if (tgt.getClass() == getClass()) { // same type
245                 System.arraycopy(laBytes, srcRawIndex, ((NoState)tgt).laBytes, dstRawIndex, len);
246             } else if (tgt.getClass() == ByteState.class) {
247                 short[] laStateShorts = ((ByteState)tgt).laStateShorts;
248                 while (--len >= 0) {
249                     laStateShorts[dstRawIndex++] = (short)(laBytes[srcRawIndex++] | 0xFF00);
250                 }
251             } else { // large state
252                 int[] las = ((LargeState)tgt).lookaheads;
253                 // No need to operate on tgt.states as they will remain nulls
254                 while (--len >= 0) {
255                     las[dstRawIndex++] = laBytes[srcRawIndex++];
256                 }
257             }
258         }
259 
260         protected void moveData(int srcRawIndex, int dstRawIndex, int len) {
261             System.arraycopy(laBytes, srcRawIndex, laBytes, dstRawIndex, len);
262         }
263 
264         protected Class   addToGapStart(int lookahead, Object   state) {
265             if (lookahead <= Byte.MAX_VALUE) {
266                 if (state == null) {
267                     laBytes[gapStart] = (byte)lookahead;
268                     return null;
269                 } else if (isByteState(state)) {
270                     return ByteState.class;
271                 }
272             }
273             return LargeState.class;
274         }
275 
276         protected int capacity() {
277             return laBytes.length;
278         }
279 
280     }
281 
282 
283     static final class ByteState extends LAState {
284 
285         short[] laStateShorts;
286 
287         ByteState(int capacity) {
288             super(capacity);
289             laStateShorts = new short[capacity];
290         }
291 
292         public int lookahead(int index) {
293             return laStateShorts[rawIndex(index)] & 0xFF;
294         }
295 
296         public Object   state(int index) {
297             int val = laStateShorts[rawIndex(index)] & 0xFF00;
298             return (val == 0xFF00) ? null : IntegerCache.integer(val >> 8);
299         }
300 
301         protected LAState upgrade(int capacity, Class   laStateClass) {
302             if (laStateClass == LargeState.class) {
303                 return new LargeState(capacity);
304             } else {
305                 return new ByteState(capacity);
306             }
307         }
308 
309         protected boolean isUpgrade(Class   laStateClass) {
310             return (laStateClass == LargeState.class);
311         }
312 
313         protected void copyData(int srcRawIndex, LAState tgt, int dstRawIndex, int len) {
314             if (tgt.getClass() == getClass()) { // same type
315                 System.arraycopy(laStateShorts, srcRawIndex, ((ByteState)tgt).laStateShorts, dstRawIndex, len);
316             } else { // large state
317                 int[] las = ((LargeState)tgt).lookaheads;
318                 Object  [] states = ((LargeState)tgt).states;
319                 while (--len >= 0) {
320                     int val = laStateShorts[srcRawIndex++] & 0xFFFF;
321                     las[dstRawIndex] = val & 0xFF;
322                     val &= 0xFF00;
323                     if (val != 0xFF00) { // not null state
324                         states[dstRawIndex] = IntegerCache.integer(val >> 8);
325                     }
326                     dstRawIndex++;
327                 }
328             }
329         }
330 
331         protected void moveData(int srcRawIndex, int dstRawIndex, int len) {
332             System.arraycopy(laStateShorts, srcRawIndex, laStateShorts, dstRawIndex, len);
333         }
334 
335         protected Class   addToGapStart(int lookahead, Object   state) {
336             if (lookahead <= Byte.MAX_VALUE) {
337                 int intState;
338                 if (state == null) {
339                     intState = 0xFF00;
340                 } else if (isByteState(state)) {
341                     intState = (((Integer  )state).intValue() << 8);
342                 } else
343                     return LargeState.class;
344                 laStateShorts[gapStart] = (short)(intState | lookahead);
345                 return null;
346             }
347             return LargeState.class;
348         }
349 
350         protected int capacity() {
351             return laStateShorts.length;
352         }
353 
354     }
355 
356 
357     static final class LargeState extends LAState {
358 
359         int[] lookaheads;
360 
361         Object  [] states;
362 
363         LargeState(int capacity) {
364             super(capacity);
365             lookaheads = new int[capacity];
366             states = new Object  [capacity];
367         }
368 
369         public int lookahead(int index) {
370             return lookaheads[rawIndex(index)];
371         }
372 
373         public Object   state(int index) {
374             return states[rawIndex(index)];
375         }
376 
377         protected LAState upgrade(int capacity, Class   laStateClass) {
378             return new LargeState(capacity);
379         }
380 
381         protected boolean isUpgrade(Class   laStateClass) {
382             return false;
383         }
384 
385         protected void copyData(int srcRawIndex, LAState tgt, int dstRawIndex, int len) {
386             System.arraycopy(lookaheads, srcRawIndex, ((LargeState)tgt).lookaheads, dstRawIndex, len);
387             System.arraycopy(states, srcRawIndex, ((LargeState)tgt).states, dstRawIndex, len);
388         }
389 
390         protected void moveData(int srcRawIndex, int dstRawIndex, int len) {
391             System.arraycopy(lookaheads, srcRawIndex, lookaheads, dstRawIndex, len);
392             System.arraycopy(states, srcRawIndex, states, dstRawIndex, len);
393         }
394 
395         protected Class   addToGapStart(int lookahead, Object   state) {
396             lookaheads[gapStart] = lookahead;
397             states[gapStart] = state;
398             return null;
399         }
400 
401         protected void removeUpdate(int index, int length) {
402             while (--length >= 0) {
403                 states[index + length] = null; // clear the state to allow its gc
404             }
405         }
406 
407         protected int capacity() {
408             return lookaheads.length;
409         }
410 
411     }
412 
413 }
414
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags