SnapshotTokenList


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.inc;
21  
22  import java.util.Set  ;
23  import org.netbeans.api.lexer.InputAttributes;
24  import org.netbeans.api.lexer.LanguagePath;
25  import org.netbeans.api.lexer.Token;
26  import org.netbeans.api.lexer.TokenId;
27  import org.netbeans.lib.editor.util.CompactMap;
28  import org.netbeans.lib.lexer.EmbeddedTokenList;
29  import org.netbeans.lib.lexer.EmbeddingContainer;
30  import org.netbeans.lib.lexer.LexerUtilsConstants;
31  import org.netbeans.lib.lexer.TokenHierarchyOperation;
32  import org.netbeans.lib.lexer.TokenList;
33  import org.netbeans.lib.lexer.token.AbstractToken;
34  import org.netbeans.lib.lexer.token.TextToken;
35  
36  
37  /**
38   * Token list used by token hierarchy snapshot.
39   *
40   * @author Miloslav Metelka
41   * @version 1.00
42   */
43  
44  public final class SnapshotTokenList<T extends TokenId> implements TokenList<T> {
45  
46      /** Due to debugging purposes - dumpInfo() use. */
47      private TokenHierarchyOperation<?,T> snapshot;
48  
49      private IncTokenList<T> liveTokenList;
50  
51      private int liveTokenGapStart = -1;
52  
53      private int liveTokenGapEnd;
54  
55      private int liveTokenGapStartOffset;
56  
57      private int liveTokenOffsetDiff;
58  
59      /** Captured original tokens or branches. */
60      private Object  [] origTokensOrBranches;
61  
62      /** Original token's offsets. The array is occupied
63       * and maintained in the same way like origTokensOrBranches.
64       */
65      private int[] origOffsets;
66  
67      /** Index where tokens start in tokens array. */
68      private int origTokenStartIndex;
69  
70      /** Number of original tokens. */
71      private int origTokenCount;
72  
73      /** Overrides of tokens' offset. */
74      private CompactMap<AbstractToken<T>, Token2OffsetEntry<T>> token2offset;
75  
76      public int liveTokenGapStart() {
77          return liveTokenGapStart;
78      }
79  
80      public int liveTokenGapEnd() {
81          return liveTokenGapEnd;
82      }
83      
84      public SnapshotTokenList(TokenHierarchyOperation<?,T> snapshot) {
85          this.snapshot = snapshot;
86          this.liveTokenList = (IncTokenList<T>)snapshot.
87                  liveTokenHierarchyOperation().tokenList();
88          token2offset = new CompactMap<AbstractToken<T>,Token2OffsetEntry<T>>();
89      }
90  
91      public TokenHierarchyOperation<?,T> snapshot() {
92          return snapshot;
93      }
94      
95      public LanguagePath languagePath() {
96          return liveTokenList.languagePath();
97      }
98      
99      public Object   tokenOrEmbeddingContainer(int index) {
100         if (liveTokenGapStart == -1 || index < liveTokenGapStart) {
101             return liveTokenList.tokenOrEmbeddingContainer(index);
102         }
103         index -= liveTokenGapStart;
104         if (index < origTokenCount) {
105             return origTokensOrBranches[origTokenStartIndex + index];
106         }
107         return liveTokenList.tokenOrEmbeddingContainer(liveTokenGapEnd + index - origTokenCount);
108     }
109 
110     public int lookahead(int index) {
111         // Lookahead not supported for certain snapshot's tokens
112         // so better don't return it for any of them.
113         return -1;
114     }
115 
116     public Object   state(int index) {
117         // Lookahead not supported for certain snapshot's tokens
118         // so better don't return it for any of them.
119         return null;
120     }
121 
122     public int tokenOffset(int index) {
123         if (liveTokenGapStart == -1 || index < liveTokenGapStart) {
124             return liveTokenList.tokenOffset(index);
125         }
126         index -= liveTokenGapStart;
127         if (index < origTokenCount) {
128             return origOffsets[origTokenStartIndex + index];
129         }
130         index -= origTokenCount;
131 
132         AbstractToken<T> token = LexerUtilsConstants.token(liveTokenList.
133                 tokenOrEmbeddingContainerUnsync(liveTokenGapEnd + index));
134         int offset;
135         if (token.isFlyweight()) {
136             offset = token.length();
137             while (--index >= 0) {
138                 token = LexerUtilsConstants.token(liveTokenList.
139                         tokenOrEmbeddingContainerUnsync(liveTokenGapEnd + index));
140                 if (token.isFlyweight()) {
141                     offset += token.length();
142                 } else { // non-flyweight element
143                     offset += tokenOffset(token, liveTokenList, token.rawOffset());
144                     break;
145                 }
146             }
147             if (index == -1) { // below the boundary of above-gap live tokens
148                 index += liveTokenGapStart + origTokenCount;
149                 if (index >= 0) {
150                     offset += tokenOffset(index);
151                 }
152             }
153             
154         } else { // non-flyweight
155             offset = tokenOffset(token, liveTokenList, token.rawOffset());
156         }
157         return offset;
158     }
159 
160     /**
161      * @param token non-null token for which the offset is being computed.
162      * @param tokenList non-null token list to which the token belongs.
163      * @param rawOffset raw offset of the token.
164      * @return offset for the particular token.
165      */
166     public <TT extends TokenId> int tokenOffset(
167     AbstractToken<TT> token, TokenList<TT> tokenList, int rawOffset) {
168         // The following situations can happen:
169         // 1. Token instance is contained in token2offset map so the token's
170         //    offset is overriden by the information in the map.
171         // 2. Token instance is not contained in token2offset map
172         //    and the token's tokenList is IncTokenList. In that case
173         //    it needs to be checked whether the regularly computed offset
174         //    is above liveTokenGapStartOffset and if so then
175         //    liveTokenOffsetDiff must be added to it.
176         // 3. Token instance is not contained in token2offset map
177         //    and the token's tokenList is not IncTokenList.
178         //    It happens for removed tokens that were removed but
179         //    do not need the offset correction.
180         //    In that case the computed offset is simply returned.
181         // 4. Token from branch token list is passed.
182         //    In this case the offset of the corresponding rootBranchToken
183         //    needs to be corrected if necessary.
184         if (tokenList.getClass() == EmbeddedTokenList.class) {
185             EmbeddedTokenList<TT> etl = (EmbeddedTokenList<TT>)tokenList;
186             AbstractToken<? extends TokenId> rootBranchToken = etl.rootToken();
187             Token2OffsetEntry<T> entry = token2offset.get(rootBranchToken);
188             if (entry != null) {
189                 return entry.offset() + etl.childTokenOffsetShift(rawOffset);
190             } else { // no special entry => check whether the regular offset is below liveTokenGapStartOffset
191                 int offset = etl.childTokenOffset(rawOffset);
192                 TokenList rootTokenList = etl.root();
193                 if (rootTokenList != null && rootTokenList.getClass() == IncTokenList.class) {
194                     if (offset >= liveTokenGapStartOffset) {
195                         offset += liveTokenOffsetDiff;
196                     }
197                 }
198                 return offset;
199             }
200 
201         } else { // queried token list is the root list genericsed by <T>
202             @SuppressWarnings  ("unchecked")
203             Token2OffsetEntry<T> entry = token2offset.get((AbstractToken<T>)token);
204             if (entry != null) {
205                 return entry.offset();
206             } else {
207                 if (tokenList.getClass() == IncTokenList.class) {
208                     rawOffset = tokenList.childTokenOffset(rawOffset);
209                     if (rawOffset >= liveTokenGapStartOffset) {
210                         rawOffset += liveTokenOffsetDiff;
211                     }
212                     return rawOffset;
213                 }
214                 return tokenList.childTokenOffset(rawOffset);
215             }
216         }
217     }
218     
219     public int tokenCount() {
220         return (liveTokenGapStart == -1)
221                 ? liveTokenList.tokenCount()
222                 : liveTokenList.tokenCount() - (liveTokenGapEnd - liveTokenGapStart)
223                     + origTokenCount;
224     }
225 
226     public int tokenCountCurrent() {
227         return (liveTokenGapStart == -1)
228                 ? liveTokenList.tokenCountCurrent()
229                 : liveTokenList.tokenCountCurrent() - (liveTokenGapEnd - liveTokenGapStart)
230                     + origTokenCount;
231     }
232 
233     public int modCount() {
234         return -1;
235     }
236     
237     public int childTokenOffset(int rawOffset) {
238         // Offset of the standalone token is absolute
239         return rawOffset;
240     }
241     
242     public char childTokenCharAt(int rawOffset, int index) {
243         // No tokens expected to be parented to this token list
244         throw new IllegalStateException  ("Not expected to be called"); // NOI18N
245     }
246 
247     public void wrapToken(int index, EmbeddingContainer embeddingContainer) {
248         // Allow branching
249         if (liveTokenGapStart == -1 || index < liveTokenGapStart) {
250             liveTokenList.wrapToken(index, embeddingContainer);
251         } else {
252             index -= liveTokenGapStart;
253             if (index < origTokenCount) {
254                 origTokensOrBranches[origTokenStartIndex + index] = embeddingContainer;
255             } else {
256                 liveTokenList.wrapToken(liveTokenGapEnd + index - origTokenCount, embeddingContainer);
257             }
258         }
259     }
260 
261     public AbstractToken<T> replaceFlyToken(int index, AbstractToken<T> flyToken, int offset) {
262         AbstractToken<T> nonFlyToken;
263         if (liveTokenGapStart == -1 || index < liveTokenGapStart) {
264             nonFlyToken = liveTokenList.replaceFlyToken(index, flyToken, offset);
265         } else {
266             index -= liveTokenGapStart;
267             if (index < origTokenCount) {
268                 nonFlyToken = ((TextToken<T>)flyToken).createCopy(this, offset);
269                 origTokensOrBranches[origTokenStartIndex + index] = nonFlyToken;
270             } else {
271                 nonFlyToken = liveTokenList.replaceFlyToken(
272                         liveTokenGapEnd + index - origTokenCount,
273                         flyToken, offset - liveTokenOffsetDiff);
274             }
275         }
276         return nonFlyToken;
277     }
278     
279     public TokenList<? extends TokenId> root() {
280         return this;
281     }
282     
283     public TokenHierarchyOperation<?,? extends TokenId> tokenHierarchyOperation() {
284         return snapshot;
285     }
286     
287     public InputAttributes inputAttributes() {
288         return liveTokenList.inputAttributes();
289     }
290 
291     public boolean isContinuous() {
292         return true;
293     }
294 
295     public Set  <T> skipTokenIds() {
296         return null;
297     }
298 
299     public boolean canModifyToken(int index, AbstractToken token) {
300         return liveTokenGapStart != -1
301                 && index >= liveTokenGapStart
302                 && index < liveTokenGapEnd
303                 && !token2offset.containsKey(token);
304     }
305 
306     public void update(TokenHierarchyEventInfo eventInfo, TokenListChange<T> change) {
307         TokenList<T> removedTokenList = change.tokenChangeInfo().removedTokenList();
308         int startRemovedIndex = change.index();
309         int endRemovedIndex = startRemovedIndex + removedTokenList.tokenCount();
310         if (liveTokenGapStart == -1) { // no modifications yet
311             liveTokenGapStart = startRemovedIndex;
312             liveTokenGapEnd = startRemovedIndex;
313             liveTokenGapStartOffset = change.offset();
314             origTokensOrBranches = new Object  [removedTokenList.tokenCount()];
315             origOffsets = new int[origTokensOrBranches.length];
316         }
317 
318         int liveTokenIndexDiff = change.tokenChangeInfo().addedTokenCount()
319                 - removedTokenList.tokenCount();
320         if (startRemovedIndex < liveTokenGapStart) { // will affect initial shared tokens
321             int extraOrigTokenCount = liveTokenGapStart - startRemovedIndex;
322             ensureOrigTokensStartCapacity(extraOrigTokenCount);
323             origTokenStartIndex -= extraOrigTokenCount;
324             origTokenCount += extraOrigTokenCount;
325 
326             int bound = Math.min(endRemovedIndex, liveTokenGapStart);
327             int index;
328             int offset = change.offset();
329             liveTokenGapStartOffset = offset;
330             for (index = startRemovedIndex; index < bound; index++) {
331                 Object   tokenOrEmbeddingContainer = removedTokenList.tokenOrEmbeddingContainer(index - startRemovedIndex);
332                 AbstractToken<T> token = LexerUtilsConstants.token(tokenOrEmbeddingContainer);
333                 if (!token.isFlyweight()) {
334                     TokenList<T> tokenList = token.tokenList();
335                     if (tokenList == null) {
336                         tokenList = new StandaloneTokenList<T>(change.languagePath(),
337                                 eventInfo.originalText().toCharArray(offset, offset + token.length()));
338                         token.setTokenList(tokenList);
339                     }
340                 }
341                 origOffsets[origTokenStartIndex] = offset;
342                 origTokensOrBranches[origTokenStartIndex++] = tokenOrEmbeddingContainer;
343                 offset += token.length();
344             }
345 
346             while (index < liveTokenGapStart) {
347                 Object   tokenOrEmbeddingContainer = liveTokenList.tokenOrEmbeddingContainerUnsync(index + liveTokenIndexDiff);
348                 AbstractToken<T> t = LexerUtilsConstants.token(tokenOrEmbeddingContainer);
349                 if (!t.isFlyweight()) {
350                     token2offset.putEntry(new Token2OffsetEntry<T>(t, offset));
351                 }
352                 origOffsets[origTokenStartIndex] = offset;
353                 origTokensOrBranches[origTokenStartIndex++] = tokenOrEmbeddingContainer;
354                 offset += t.length();
355                 index++;
356             }
357             liveTokenGapStart = startRemovedIndex;
358         }
359 
360         if (endRemovedIndex > liveTokenGapEnd) { // will affect ending shared tokens
361             int extraOrigTokenCount = endRemovedIndex - liveTokenGapEnd;
362             ensureOrigTokensEndCapacity(extraOrigTokenCount);
363             origTokenCount += extraOrigTokenCount;
364             int origTokenIndex = origTokenStartIndex + origTokenCount - 1;
365 
366             int bound = Math.max(startRemovedIndex, liveTokenGapEnd);
367             int index = endRemovedIndex;
368             int offset = change.removedEndOffset();
369             for (index = endRemovedIndex - 1; index >= bound; index--) {
370                 Object   tokenOrEmbeddingContainer = removedTokenList.tokenOrEmbeddingContainer(index - startRemovedIndex);
371                 AbstractToken<T> token = LexerUtilsConstants.token(tokenOrEmbeddingContainer);
372                 offset -= token.length();
373                 if (!token.isFlyweight()) {
374                     TokenList<T> tokenList = token.tokenList();
375                     if (tokenList == null) {
376                         tokenList = new StandaloneTokenList<T>(change.languagePath(),
377                                 eventInfo.originalText().toCharArray(offset, offset + token.length()));
378                         token.setTokenList(tokenList);
379                     }
380                 }
381                 origOffsets[origTokenIndex] = offset + liveTokenOffsetDiff;
382                 // If the token's offset had to be diff-ed already then a map entry is necessary
383                 if (liveTokenOffsetDiff != 0) {
384                     token2offset.putEntry(new Token2OffsetEntry<T>(token, origOffsets[origTokenIndex]));
385                 }
386                 origTokensOrBranches[origTokenIndex--] = tokenOrEmbeddingContainer;
387             }
388 
389             while (index >= liveTokenGapEnd) {
390                 Object   tokenOrEmbeddingContainer = liveTokenList.tokenOrEmbeddingContainerUnsync(index + liveTokenIndexDiff);
391                 AbstractToken<T> token = LexerUtilsConstants.token(tokenOrEmbeddingContainer);
392                 offset -= token.length();
393                 if (!token.isFlyweight()) {
394                     token2offset.putEntry(new Token2OffsetEntry<T>(token, offset));
395                 }
396                 origOffsets[origTokenIndex] = offset + liveTokenOffsetDiff;
397                 token2offset.putEntry(new Token2OffsetEntry<T>(token, origOffsets[origTokenIndex]));
398                 origTokensOrBranches[origTokenIndex--] = tokenOrEmbeddingContainer;
399                 index--;
400             }
401             liveTokenGapEnd = endRemovedIndex;
402         }
403 
404         liveTokenOffsetDiff += eventInfo.removedLength() - eventInfo.insertedLength();
405         liveTokenGapEnd += liveTokenIndexDiff;
406     }
407 
408     private void ensureOrigTokensStartCapacity(int extraOrigTokenCount) {
409         if (extraOrigTokenCount > origTokensOrBranches.length - origTokenCount) { // will need to reallocate
410             // Could check for maximum possible token count (origTokenCount + below-and-above live token counts)
411             // but would cause init of live tokens above gap which is undesirable
412             Object  [] newOrigTokensOrBranches = new Object  [(origTokensOrBranches.length * 3 / 2) + extraOrigTokenCount];
413             int[] newOrigOffsets = new int[newOrigTokensOrBranches.length];
414             int newIndex = Math.max(extraOrigTokenCount, (newOrigTokensOrBranches.length
415                     - (origTokenCount + extraOrigTokenCount)) / 2);
416             System.arraycopy(origTokensOrBranches, origTokenStartIndex,
417                     newOrigTokensOrBranches, newIndex, origTokenCount);
418             System.arraycopy(origOffsets, origTokenStartIndex,
419                     newOrigOffsets, newIndex, origTokenCount);
420             origTokensOrBranches = newOrigTokensOrBranches;
421             origOffsets = newOrigOffsets;
422             origTokenStartIndex = newIndex;
423 
424         } else if (extraOrigTokenCount > origTokenStartIndex) { // only move
425             // Move to the end of the array
426             int newIndex = origTokensOrBranches.length - origTokenCount;
427             System.arraycopy(origTokensOrBranches, origTokenStartIndex,
428                     origTokensOrBranches, newIndex, origTokenCount);
429             System.arraycopy(origOffsets, origTokenStartIndex,
430                     origOffsets, newIndex, origTokenCount);
431             origTokenStartIndex = origTokensOrBranches.length - origTokenCount;
432         }
433     }
434     
435     private void ensureOrigTokensEndCapacity(int extraOrigTokenCount) {
436         if (extraOrigTokenCount > origTokensOrBranches.length - origTokenCount) { // will need to reallocate
437             // Could check for maximum possible token count (origTokenCount + below-and-above live token counts)
438             // but would cause init of live tokens above gap which is undesirable
439             Object  [] newOrigTokensOrBranches = new Object  [(origTokensOrBranches.length * 3 / 2) + extraOrigTokenCount];
440             int[] newOrigOffsets = new int[newOrigTokensOrBranches.length];
441             int newIndex = (newOrigTokensOrBranches.length
442                     - (origTokenCount + extraOrigTokenCount)) / 2;
443             System.arraycopy(origTokensOrBranches, origTokenStartIndex,
444                     newOrigTokensOrBranches, newIndex, origTokenCount);
445             System.arraycopy(origOffsets, origTokenStartIndex,
446                     newOrigOffsets, newIndex, origTokenCount);
447             origTokensOrBranches = newOrigTokensOrBranches;
448             origOffsets = newOrigOffsets;
449             origTokenStartIndex = newIndex;
450 
451         } else if (extraOrigTokenCount > origTokensOrBranches.length - origTokenCount - origTokenStartIndex) { // only move
452             // Move to the end of the array
453             System.arraycopy(origTokensOrBranches, origTokenStartIndex,
454                     origTokensOrBranches, 0, origTokenCount);
455             System.arraycopy(origOffsets, origTokenStartIndex,
456                     origOffsets, 0, origTokenCount);
457             origTokenStartIndex = 0;
458         }
459     }
460 
461     public String   toString() {
462         return "liveTokenGapStart=" + liveTokenGapStart +
463                 ", liveTokenGapEnd=" + liveTokenGapEnd +
464                 ", liveTokenGapStartOffset=" + liveTokenGapStartOffset +
465                 ", liveTokenOffsetDiff=" + liveTokenOffsetDiff +
466                 ",\n origTokenStartIndex=" + origTokenStartIndex +
467                 ", origTokenCount=" + origTokenCount +
468                 ", token2offset: " + token2offset;
469 
470     }
471 
472     public int tokenShiftStartOffset() {
473         return liveTokenGapStartOffset;
474     }
475     
476     public int tokenShiftEndOffset() {
477         return liveTokenGapStartOffset + liveTokenOffsetDiff;
478     }
479 
480     private static final class Token2OffsetEntry<T extends TokenId>
481     extends CompactMap.MapEntry<AbstractToken<T>,Token2OffsetEntry<T>> {
482         
483         private final AbstractToken<T> token; // 20 bytes (16-super + 4)
484         
485         private final int offset; // 24 bytes
486         
487         Token2OffsetEntry(AbstractToken<T> token, int offset) {
488             this.token = token;
489             this.offset = offset;
490         }
491         
492         public AbstractToken<T> getKey() {
493             return token;
494         }
495 
496         public Token2OffsetEntry<T> getValue() {
497             return this;
498         }
499         
500         protected int valueHashCode() {
501             return offset;
502         }
503 
504         protected boolean valueEquals(Object   value2) {
505             // In fact the second entry would have to be of <T> because
506             // the tokens (as keys) must be the same objects to be equal
507             return (value2 instanceof Token2OffsetEntry
508                     && ((Token2OffsetEntry<? extends TokenId>)value2).offset() == offset());
509         }
510         
511         public int offset() {
512             return offset;
513         }
514 
515         public Token2OffsetEntry<T> setValue(Token2OffsetEntry<T> value) {
516             throw new IllegalStateException  ("Prohibited"); // NOI18N
517         }
518 
519         public String   toString() {
520             // Debug the offset being held
521             return String.valueOf(offset);
522         }
523 
524     }
525     
526 }
527
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags