CPP-7551 Splitting [name] and [symbol name] entities ([=] vs [operator=], [S] vs...
[idea/community.git] / platform / core-api / src / com / intellij / psi / tree / TokenSet.java
1 /*
2  * Copyright 2000-2015 JetBrains s.r.o.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.intellij.psi.tree;
17
18 import com.intellij.openapi.diagnostic.LogUtil;
19 import com.intellij.util.ArrayUtil;
20 import org.jetbrains.annotations.NotNull;
21 import org.jetbrains.annotations.Nullable;
22
23 import java.util.ArrayList;
24 import java.util.Arrays;
25 import java.util.List;
26
27 /**
28  * A set of element types.
29  */
30 public class TokenSet {
31   public static final TokenSet EMPTY = new TokenSet(Short.MAX_VALUE, (short)0) {
32     @Override public boolean contains(IElementType t) { return false; }
33   };
34   public static final TokenSet ANY = new TokenSet(Short.MAX_VALUE, (short)0) {
35     @Override public boolean contains(IElementType t) { return true; }
36   };
37
38   private final short myShift;
39   private final short myMax;
40   private final long[] myWords;
41   private volatile IElementType[] myTypes;
42
43   private TokenSet(short shift, short max) {
44     myShift = shift;
45     myMax = max;
46     final int size = (max >> 6) + 1 - shift;
47     myWords = size > 0 ? new long[size] : ArrayUtil.EMPTY_LONG_ARRAY;
48   }
49
50   private boolean get(int index) {
51     final int wordIndex = (index >> 6) - myShift;
52     return wordIndex >= 0 && wordIndex < myWords.length && (myWords[wordIndex] & (1L << index)) != 0;
53   }
54
55   /**
56    * Checks if the specified element type is contained in the set.
57    *
58    * @param t the element type to search for.
59    * @return true if the element type is found in the set, false otherwise.
60    */
61   public boolean contains(@Nullable IElementType t) {
62     if (t == null) return false;
63     final short i = t.getIndex();
64     return 0 <= i && i <= myMax && get(i);
65   }
66
67   /**
68    * Returns the array of element types contained in the set.
69    *
70    * @return the contents of the set.
71    */
72   @NotNull
73   public IElementType[] getTypes() {
74     IElementType[] types = myTypes;
75
76     if (types == null) {
77       if (myWords.length == 0) {
78         types = IElementType.EMPTY_ARRAY;
79       }
80       else {
81         List<IElementType> list = new ArrayList<IElementType>();
82         for (short i = (short)Math.max(1, myShift << 6); i <= myMax; i++) {
83           if (!get(i)) continue;
84           IElementType type = IElementType.find(i);
85           if (type != null) {
86             list.add(type);
87           }
88         }
89         types = list.toArray(new IElementType[list.size()]);
90       }
91       myTypes = types;
92     }
93
94     return types;
95   }
96
97   @Override
98   public String toString() {
99     return Arrays.toString(getTypes());
100   }
101
102   /**
103    * Returns a new token set containing the specified element types.
104    *
105    * @param types the element types contained in the set.
106    * @return the new token set.
107    */
108   @NotNull
109   public static TokenSet create(@NotNull IElementType... types) {
110     if (types.length == 0) return EMPTY;
111
112     short min = Short.MAX_VALUE;
113     short max = 0;
114     for (IElementType type : types) {
115       if (type != null) {
116         final short index = type.getIndex();
117         assert index >= 0 : "Unregistered elements are not allowed here: " + LogUtil.objectAndClass(type);
118         if (min > index) min = index;
119         if (max < index) max = index;
120       }
121     }
122
123     final short shift = (short)(min >> 6);
124     final TokenSet set = new TokenSet(shift, max);
125     for (IElementType type : types) {
126       if (type != null) {
127         final short index = type.getIndex();
128         final int wordIndex = (index >> 6) - shift;
129         set.myWords[wordIndex] |= 1L << index;
130       }
131     }
132     return set;
133   }
134
135   /**
136    * Returns a token set containing the union of the specified token sets.
137    *
138    * @param sets the token sets to unite.
139    * @return the new token set.
140    */
141   @NotNull
142   public static TokenSet orSet(@NotNull TokenSet... sets) {
143     if (sets.length == 0) return EMPTY;
144
145     short shift = sets[0].myShift;
146     short max = sets[0].myMax;
147     for (int i = 1; i < sets.length; i++) {
148       if (shift > sets[i].myShift) shift = sets[i].myShift;
149       if (max < sets[i].myMax) max = sets[i].myMax;
150     }
151
152     final TokenSet newSet = new TokenSet(shift, max);
153     for (TokenSet set : sets) {
154       final int shiftDiff = set.myShift - newSet.myShift;
155       for (int i = 0; i < set.myWords.length; i++) {
156         newSet.myWords[i + shiftDiff] |= set.myWords[i];
157       }
158     }
159     return newSet;
160   }
161
162   /**
163    * Returns a token set containing the intersection of the specified token sets.
164    *
165    * @param a the first token set to intersect.
166    * @param b the second token set to intersect.
167    * @return the new token set.
168    */
169   @NotNull
170   public static TokenSet andSet(@NotNull TokenSet a, @NotNull TokenSet b) {
171     final TokenSet newSet = new TokenSet((short)Math.min(a.myShift, b.myShift), (short)Math.max(a.myMax, b.myMax));
172     for (int i = 0; i < newSet.myWords.length; i++) {
173       final int ai = newSet.myShift - a.myShift + i;
174       final int bi = newSet.myShift - b.myShift + i;
175       newSet.myWords[i] = (0 <= ai && ai < a.myWords.length ? a.myWords[ai] : 0L) & (0 <= bi && bi < b.myWords.length ? b.myWords[bi] : 0L);
176     }
177     return newSet;
178   }
179
180   /**
181    * Returns a token set containing a result of "set subtraction" of set B from set A.
182    *
183    * @param a the basic token set.
184    * @param b the token set to subtract.
185    * @return the new token set.
186    */
187   @NotNull
188   public static TokenSet andNot(@NotNull TokenSet a, @NotNull TokenSet b) {
189     final TokenSet newSet = new TokenSet((short)Math.min(a.myShift, b.myShift), (short)Math.max(a.myMax, b.myMax));
190     for (int i = 0; i < newSet.myWords.length; i++) {
191       final int ai = newSet.myShift - a.myShift + i;
192       final int bi = newSet.myShift - b.myShift + i;
193       newSet.myWords[i] = (0 <= ai && ai < a.myWords.length ? a.myWords[ai] : 0L) & ~(0 <= bi && bi < b.myWords.length ? b.myWords[bi] : 0L);
194     }
195     return newSet;
196   }
197 }