001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2007 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041:
042: package org.netbeans.lib.lexer;
043:
044: /**
045: * A structure holding lookahead and state of a token list.
046: *
047: * @author Miloslav Metelka
048: * @version 1.00
049: */
050:
051: public abstract class LAState {
052:
053: private static final LAState EMPTY = new NoState(0);
054:
055: private static final LAState INIT_STATE = new NoState(0);
056:
057: public static LAState empty() {
058: return EMPTY;
059: }
060:
061: /**
062: * Special state for marking that an embedded token list was not inited yet.
063: */
064: public static LAState initState() {
065: return INIT_STATE;
066: }
067:
068: static int withExtraCapacity(int capacity) {
069: return capacity * 3 / 2 + 4;
070: }
071:
072: static boolean isByteState(Object state) {
073: int intState;
074: return (state.getClass() == Integer.class
075: && (intState = ((Integer) state).intValue()) >= 0 && intState <= Byte.MAX_VALUE);
076: }
077:
078: int gapStart;
079:
080: int gapLength;
081:
082: public LAState(int capacity) {
083: gapLength = capacity;
084: }
085:
086: /**
087: * Get lookahead at the particular index
088: * preparing the state as well.
089: */
090: public abstract int lookahead(int index);
091:
092: public abstract Object state(int index);
093:
094: public final LAState trimToSize() {
095: if (gapLength > 0) {
096: LAState laState = upgrade(size(), getClass());
097: reallocate(laState, size());
098: return laState;
099: }
100: return this ;
101: }
102:
103: public final int size() {
104: return capacity() - gapLength;
105: }
106:
107: public final LAState add(int lookahead, Object state) {
108: LAState ret;
109: if (gapLength > 0) { // enough space
110: moveGap(size());
111: ret = this ;
112: } else { // no more space
113: // Called when doing TokenSequence.moveNext() - tokens get created lazily
114: // Double the capacity - Token lists should call trimToSize() after finishing
115: ret = upgrade((capacity() + 1) << 1, getClass());
116: reallocate(ret, size());
117: }
118:
119: Class laStateCls;
120: if ((laStateCls = ret.addToGapStart(lookahead, state)) != null) {
121: ret = upgrade(capacity() + 1, laStateCls);
122: reallocate(ret, size());
123: ret.addToGapStart(lookahead, state);
124: }
125:
126: ret.gapStart += 1;
127: ret.gapLength -= 1;
128: return ret;
129: }
130:
131: public final LAState addAll(int index, LAState laState) {
132: LAState ret;
133: int laStateSize = laState.size();
134: if (!isUpgrade(laState.getClass()) && gapLength > laStateSize) { // enough space
135: moveGap(index);
136: ret = this ;
137: } else { // no more space
138: // Called when fixing token list by TokenListUpdater
139: // Leave 10% for growth
140: ret = upgrade(
141: (int) ((capacity() + laStateSize) * 110L / 100),
142: laState.getClass());
143: reallocate(ret, index);
144: }
145:
146: laState.copyData(0, ret, ret.gapStart, laState.gapStart);
147: int laStateGapEnd = laState.gapStart + laState.gapLength;
148: laState.copyData(laStateGapEnd, ret, ret.gapStart
149: + laState.gapStart, laState.capacity() - laStateGapEnd);
150:
151: ret.gapStart += laStateSize;
152: ret.gapLength -= laStateSize;
153: return ret;
154: }
155:
156: protected abstract LAState upgrade(int capacity, Class laStateClass);
157:
158: protected abstract boolean isUpgrade(Class laStateClass);
159:
160: protected abstract Class addToGapStart(int lookahead, Object state);
161:
162: public final void remove(int index, int count) {
163: moveGap(index + count);
164: removeUpdate(index, count); // Perform fully below gap
165: gapStart -= count;
166: gapLength += count;
167: }
168:
169: protected void removeUpdate(int index, int count) {
170: // Do nothing
171: }
172:
173: protected final int rawIndex(int index) {
174: return (index < gapStart) ? index : index + gapLength;
175: }
176:
177: final void reallocate(LAState tgt, int newGapStart) {
178: tgt.gapStart = newGapStart;
179: tgt.gapLength = gapLength + tgt.capacity() - capacity();
180: int gapEnd = gapStart + gapLength;
181: if (newGapStart < gapStart) { // only partly allocate
182: copyData(0, tgt, 0, newGapStart);
183: int tgtRawIndex = newGapStart + tgt.gapLength;
184: int len = gapStart - newGapStart;
185: copyData(newGapStart, tgt, tgtRawIndex, len);
186: tgtRawIndex += len;
187: copyData(gapEnd, tgt, tgtRawIndex, capacity() - gapEnd);
188:
189: } else { // index above or equals gapStart
190: copyData(0, tgt, 0, gapStart);
191: int len = newGapStart - gapStart;
192: copyData(gapEnd, tgt, gapStart, len);
193: gapEnd += len;
194: copyData(gapEnd, tgt, newGapStart + tgt.gapLength,
195: capacity() - gapEnd);
196: }
197: }
198:
199: protected abstract void copyData(int srcRawIndex, LAState tgt,
200: int dstRawIndex, int len);
201:
202: protected abstract int capacity();
203:
204: final void moveGap(int index) {
205: if (index == gapStart)
206: return;
207: if (gapLength > 0) {
208: if (index < gapStart) { // move gap down
209: int moveSize = gapStart - index;
210: moveData(index, gapStart + gapLength - moveSize,
211: moveSize);
212: //clearEmpty(index, Math.min(moveSize, gapLength));
213:
214: } else { // above gap
215: int gapEnd = gapStart + gapLength;
216: int moveSize = index - gapStart;
217: moveData(gapEnd, gapStart, moveSize);
218: if (index < gapEnd) {
219: //clearEmpty(gapEnd, moveSize);
220: } else {
221: //clearEmpty(index, gapLength);
222: }
223: }
224: }
225: gapStart = index;
226: }
227:
228: protected abstract void moveData(int srcRawIndex, int dstRawIndex,
229: int len);
230:
231: public String toString() {
232: StringBuilder sb = new StringBuilder("[");
233: for (int i = 0; i < size(); i++) {
234: if (i > 0) {
235: sb.append(", ");
236: }
237: sb.append(lookahead(i));
238: sb.append(", ");
239: sb.append(state(i));
240: }
241: sb.append(']');
242: return sb.toString();
243: }
244:
245: static final class NoState extends LAState {
246:
247: byte[] laBytes;
248:
249: NoState(int capacity) {
250: super (capacity);
251: laBytes = new byte[capacity];
252: }
253:
254: public int lookahead(int index) {
255: int rawIndex = rawIndex(index);
256: return laBytes[rawIndex];
257: }
258:
259: public Object state(int index) {
260: return null;
261: }
262:
263: protected LAState upgrade(int capacity, Class laStateClass) {
264: if (laStateClass == LargeState.class) {
265: return new LargeState(capacity);
266: } else if (laStateClass == ByteState.class) {
267: return new ByteState(capacity);
268: } else {
269: return new NoState(capacity);
270: }
271: }
272:
273: protected boolean isUpgrade(Class laStateClass) {
274: return (laStateClass == LargeState.class)
275: || (laStateClass == ByteState.class);
276: }
277:
278: protected void copyData(int srcRawIndex, LAState tgt,
279: int dstRawIndex, int len) {
280: if (tgt.getClass() == getClass()) { // same type
281: System.arraycopy(laBytes, srcRawIndex,
282: ((NoState) tgt).laBytes, dstRawIndex, len);
283: } else if (tgt.getClass() == ByteState.class) {
284: short[] laStateShorts = ((ByteState) tgt).laStateShorts;
285: while (--len >= 0) {
286: laStateShorts[dstRawIndex++] = (short) (laBytes[srcRawIndex++] | 0xFF00);
287: }
288: } else { // large state
289: int[] las = ((LargeState) tgt).lookaheads;
290: // No need to operate on tgt.states as they will remain nulls
291: while (--len >= 0) {
292: las[dstRawIndex++] = laBytes[srcRawIndex++];
293: }
294: }
295: }
296:
297: protected void moveData(int srcRawIndex, int dstRawIndex,
298: int len) {
299: System.arraycopy(laBytes, srcRawIndex, laBytes,
300: dstRawIndex, len);
301: }
302:
303: protected Class addToGapStart(int lookahead, Object state) {
304: if (lookahead <= Byte.MAX_VALUE) {
305: if (state == null) {
306: laBytes[gapStart] = (byte) lookahead;
307: return null;
308: } else if (isByteState(state)) {
309: return ByteState.class;
310: }
311: }
312: return LargeState.class;
313: }
314:
315: protected int capacity() {
316: return laBytes.length;
317: }
318:
319: }
320:
321: static final class ByteState extends LAState {
322:
323: short[] laStateShorts;
324:
325: ByteState(int capacity) {
326: super (capacity);
327: laStateShorts = new short[capacity];
328: }
329:
330: public int lookahead(int index) {
331: return laStateShorts[rawIndex(index)] & 0xFF;
332: }
333:
334: public Object state(int index) {
335: int val = laStateShorts[rawIndex(index)] & 0xFF00;
336: return (val == 0xFF00) ? null : IntegerCache
337: .integer(val >> 8);
338: }
339:
340: protected LAState upgrade(int capacity, Class laStateClass) {
341: if (laStateClass == LargeState.class) {
342: return new LargeState(capacity);
343: } else {
344: return new ByteState(capacity);
345: }
346: }
347:
348: protected boolean isUpgrade(Class laStateClass) {
349: return (laStateClass == LargeState.class);
350: }
351:
352: protected void copyData(int srcRawIndex, LAState tgt,
353: int dstRawIndex, int len) {
354: if (tgt.getClass() == getClass()) { // same type
355: System.arraycopy(laStateShorts, srcRawIndex,
356: ((ByteState) tgt).laStateShorts, dstRawIndex,
357: len);
358: } else { // large state
359: int[] las = ((LargeState) tgt).lookaheads;
360: Object[] states = ((LargeState) tgt).states;
361: while (--len >= 0) {
362: int val = laStateShorts[srcRawIndex++] & 0xFFFF;
363: las[dstRawIndex] = val & 0xFF;
364: val &= 0xFF00;
365: if (val != 0xFF00) { // not null state
366: states[dstRawIndex] = IntegerCache
367: .integer(val >> 8);
368: }
369: dstRawIndex++;
370: }
371: }
372: }
373:
374: protected void moveData(int srcRawIndex, int dstRawIndex,
375: int len) {
376: System.arraycopy(laStateShorts, srcRawIndex, laStateShorts,
377: dstRawIndex, len);
378: }
379:
380: protected Class addToGapStart(int lookahead, Object state) {
381: if (lookahead <= Byte.MAX_VALUE) {
382: int intState;
383: if (state == null) {
384: intState = 0xFF00;
385: } else if (isByteState(state)) {
386: intState = (((Integer) state).intValue() << 8);
387: } else
388: return LargeState.class;
389: laStateShorts[gapStart] = (short) (intState | lookahead);
390: return null;
391: }
392: return LargeState.class;
393: }
394:
395: protected int capacity() {
396: return laStateShorts.length;
397: }
398:
399: }
400:
401: static final class LargeState extends LAState {
402:
403: int[] lookaheads;
404:
405: Object[] states;
406:
407: LargeState(int capacity) {
408: super (capacity);
409: lookaheads = new int[capacity];
410: states = new Object[capacity];
411: }
412:
413: public int lookahead(int index) {
414: return lookaheads[rawIndex(index)];
415: }
416:
417: public Object state(int index) {
418: return states[rawIndex(index)];
419: }
420:
421: protected LAState upgrade(int capacity, Class laStateClass) {
422: return new LargeState(capacity);
423: }
424:
425: protected boolean isUpgrade(Class laStateClass) {
426: return false;
427: }
428:
429: protected void copyData(int srcRawIndex, LAState tgt,
430: int dstRawIndex, int len) {
431: System.arraycopy(lookaheads, srcRawIndex,
432: ((LargeState) tgt).lookaheads, dstRawIndex, len);
433: System.arraycopy(states, srcRawIndex,
434: ((LargeState) tgt).states, dstRawIndex, len);
435: }
436:
437: protected void moveData(int srcRawIndex, int dstRawIndex,
438: int len) {
439: System.arraycopy(lookaheads, srcRawIndex, lookaheads,
440: dstRawIndex, len);
441: System.arraycopy(states, srcRawIndex, states, dstRawIndex,
442: len);
443: }
444:
445: protected Class addToGapStart(int lookahead, Object state) {
446: lookaheads[gapStart] = lookahead;
447: states[gapStart] = state;
448: return null;
449: }
450:
451: @Override
452: protected void removeUpdate(int index, int count) {
453: while (--count >= 0) {
454: states[index + count] = null; // clear the state to allow its gc
455: }
456: }
457:
458: protected int capacity() {
459: return lookaheads.length;
460: }
461:
462: }
463:
464: }
|