StubIdList used instead of raw int[] to avoid Value mapping problems
authorMaxim.Mossienko <Maxim.Mossienko@jetbrains.com>
Fri, 13 Jul 2012 18:30:41 +0000 (22:30 +0400)
committerMaxim.Mossienko <Maxim.Mossienko@jetbrains.com>
Fri, 13 Jul 2012 18:30:41 +0000 (22:30 +0400)
platform/lang-impl/src/com/intellij/psi/stubs/StubIdList.java [new file with mode: 0644]
platform/lang-impl/src/com/intellij/psi/stubs/StubIndexImpl.java
platform/lang-impl/src/com/intellij/psi/stubs/StubUpdatingIndex.java

diff --git a/platform/lang-impl/src/com/intellij/psi/stubs/StubIdList.java b/platform/lang-impl/src/com/intellij/psi/stubs/StubIdList.java
new file mode 100644 (file)
index 0000000..b21f088
--- /dev/null
@@ -0,0 +1,81 @@
+/*
+ * Copyright 2000-2012 JetBrains s.r.o.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.intellij.psi.stubs;
+
+import com.intellij.util.IncorrectOperationException;
+
+// List of nonnegative ints, monotonically increasing, optimized for one int case (90% of our lists one element)
+final class StubIdList {
+  private final int myData;
+  private final int[] myArray;
+
+  public StubIdList() {
+    myData = -1;
+    myArray = null;
+  }
+
+  public StubIdList(int value) {
+    assert value >= 0;
+    myData = value;
+    myArray = null;
+  }
+
+  public StubIdList(int[] array, int size) {
+    myArray = array;
+    myData = size;
+  }
+
+  @Override
+  public int hashCode() {
+    if (myArray == null) return myData;
+    int value = 0;
+    for(int i = 0; i < myData; ++i) {
+      value = value * 37 + myArray[i];
+    }
+    return value;
+  }
+
+  @Override
+  public boolean equals(Object obj) {
+    if (obj == this) return true;
+    if (!(obj instanceof StubIdList)) return false;
+    StubIdList other = (StubIdList)obj;
+    if (myArray == null) {
+      return other.myArray == null && other.myData == myData;
+    } else {
+      if (other.myArray == null || myData != other.myData) return false;
+      for(int i = 0; i < myData; ++i) {
+        if (myArray[i] != other.myArray[i]) return false;
+      }
+      return true;
+    }
+  }
+
+  int size() {
+    return myArray == null ? myData > 0 ? 1 : 0: myData;
+  }
+
+  int get(int i) {
+    if (myArray == null) {
+      assert myData > 0;
+      if (i == 0) return myData;
+      throw new IncorrectOperationException();
+    } else {
+      if (i >= myData) throw new IncorrectOperationException();
+      return myArray[i];
+    }
+  }
+}
index 3557a4e6dad86a9c946d65833db126848874b14c..b6ee758b342237d7df42f7425ddaa809337a38d4 100644 (file)
@@ -105,7 +105,7 @@ public class StubIndexImpl extends StubIndex implements ApplicationComponent, Pe
     }
     return (StubIndexImpl)getInstance();
   }
-  
+
   private <K> boolean registerIndexer(@NotNull StubIndexExtension<K, ?> extension, final boolean forceClean) throws IOException {
     final StubIndexKey<K, ?> indexKey = extension.getKey();
     final int version = extension.getVersion();
@@ -127,14 +127,14 @@ public class StubIndexImpl extends StubIndex implements ApplicationComponent, Pe
 
     for (int attempt = 0; attempt < 2; attempt++) {
       try {
-        final MapIndexStorage<K, int[]> storage = new MapIndexStorage<K, int[]>(
+        final MapIndexStorage<K, StubIdList> storage = new MapIndexStorage<K, StubIdList>(
           IndexInfrastructure.getStorageFile(indexKey),
           extension.getKeyDescriptor(),
           new StubIdExternalizer(),
           extension.getCacheSize(),
           extension.isKeyHighlySelective()
         );
-        final MemoryIndexStorage<K, int[]> memStorage = new MemoryIndexStorage<K, int[]>(storage);
+        final MemoryIndexStorage<K, StubIdList> memStorage = new MemoryIndexStorage<K, StubIdList>(storage);
         myIndices.put(indexKey, new MyIndex<K>(memStorage));
         break;
       }
@@ -148,40 +148,40 @@ public class StubIndexImpl extends StubIndex implements ApplicationComponent, Pe
     return needRebuild;
   }
 
-  private static class StubIdExternalizer implements DataExternalizer<int[]> {
+  private static class StubIdExternalizer implements DataExternalizer<StubIdList> {
     @Override
-    public void save(final DataOutput out, @NotNull final int[] value) throws IOException {
-      int size = value.length;
+    public void save(final DataOutput out, @NotNull final StubIdList value) throws IOException {
+      int size = value.size();
       if (size == 0) {
         DataInputOutputUtil.writeSINT(out, Integer.MAX_VALUE);
       }
       else if (size == 1) {
-        DataInputOutputUtil.writeSINT(out, -value[0]);
+        DataInputOutputUtil.writeSINT(out, -value.get(0)); // todo we can store it unsigned and have 3M indices benefit!
       }
       else {
         DataInputOutputUtil.writeSINT(out, size);
-        for (int i = 0; i < size; i++) {
-          DataInputOutputUtil.writeINT(out, value[i]);
+        for(int i = 0; i < size; ++i) {
+          DataInputOutputUtil.writeINT(out, value.get(i));
         }
       }
     }
 
     @NotNull
     @Override
-    public int[] read(final DataInput in) throws IOException {
+    public StubIdList read(final DataInput in) throws IOException {
       int size = DataInputOutputUtil.readSINT(in);
       if (size == Integer.MAX_VALUE) {
-        return new int[0];
+        return new StubIdList();
       }
       else if (size <= 0) {
-        return new int[] {-size};
+        return new StubIdList(-size);
       }
       else {
         int[] result = new int[size];
-        for (int i = 0; i < size; i++) {
+        for(int i = 0; i < size; ++i) {
           result[i] = DataInputOutputUtil.readINT(in);
         }
-        return result;
+        return new StubIdList(result, size);
       }
     }
   }
@@ -216,13 +216,13 @@ public class StubIndexImpl extends StubIndex implements ApplicationComponent, Pe
         // disable up-to-date check to avoid locks on attempt to acquire index write lock while holding at the same time the readLock for this index
         FileBasedIndexImpl.disableUpToDateCheckForCurrentThread();
         index.getReadLock().lock();
-        final ValueContainer<int[]> container = index.getData(key);
+        final ValueContainer<StubIdList> container = index.getData(key);
 
         final FileBasedIndexImpl.ProjectIndexableFilesFilter projectFilesFilter = fileBasedIndex.projectIndexableFiles(project);
 
-        return container.forEach(new ValueContainer.ContainerAction<int[]>() {
+        return container.forEach(new ValueContainer.ContainerAction<StubIdList>() {
           @Override
-          public boolean perform(final int id, @NotNull final int[] value) {
+          public boolean perform(final int id, @NotNull final StubIdList value) {
             if (projectFilesFilter != null && !projectFilesFilter.contains(id)) return true;
             final VirtualFile file = IndexInfrastructure.findFileByIdIfCached(fs, id);
             if (file == null || scope != null && !scope.contains(file)) {
@@ -252,8 +252,8 @@ public class StubIndexImpl extends StubIndex implements ApplicationComponent, Pe
                 return true;
               }
               final List<StubElement<?>> plained = stubTree.getPlainList();
-              for (int i = 0; i < value.length; i++) {
-                final StubElement<?> stub = plained.get(value[i]);
+              for (int i = 0, size = value.size(); i < size; i++) {
+                final StubElement<?> stub = plained.get(value.get(i));
                 final ASTNode tree = psiFile.findTreeForStub(stubTree, stub);
 
                 if (tree != null) {
@@ -293,8 +293,8 @@ public class StubIndexImpl extends StubIndex implements ApplicationComponent, Pe
             }
             else {
               final List<StubElement<?>> plained = stubTree.getPlainList();
-              for (int i = 0; i < value.length; i++) {
-                final int stubTreeIndex = value[i];
+              for (int i = 0, size = value.size(); i < size; i++) {
+                final int stubTreeIndex = value.get(i);
                 if (stubTreeIndex >= plained.size()) {
                   final VirtualFile virtualFile = psiFile.getVirtualFile();
                   StubTree stubTreeFromIndex = StubTreeLoader.getInstance().readFromVFile(project, file);
@@ -473,7 +473,7 @@ public class StubIndexImpl extends StubIndex implements ApplicationComponent, Pe
     index.flush();
   }
 
-  public <K> void updateIndex(@NotNull StubIndexKey key, int fileId, @NotNull final Map<K, int[]> oldValues, @NotNull Map<K, int[]> newValues) {
+  public <K> void updateIndex(@NotNull StubIndexKey key, int fileId, @NotNull final Map<K, StubIdList> oldValues, @NotNull Map<K, StubIdList> newValues) {
     try {
       final MyIndex<K> index = (MyIndex<K>)myIndices.get(key);
       index.updateWithMap(fileId, newValues, new Callable<Collection<K>>() {
@@ -489,13 +489,13 @@ public class StubIndexImpl extends StubIndex implements ApplicationComponent, Pe
     }
   }
 
-  private static class MyIndex<K> extends MapReduceIndex<K, int[], Void> {
-    public MyIndex(final IndexStorage<K, int[]> storage) {
+  private static class MyIndex<K> extends MapReduceIndex<K, StubIdList, Void> {
+    public MyIndex(final IndexStorage<K, StubIdList> storage) {
       super(null, null, storage);
     }
 
     @Override
-    public void updateWithMap(final int inputId, @NotNull final Map<K, int[]> newData, @NotNull Callable<Collection<K>> oldKeysGetter) throws StorageException {
+    public void updateWithMap(final int inputId, @NotNull final Map<K, StubIdList> newData, @NotNull Callable<Collection<K>> oldKeysGetter) throws StorageException {
       super.updateWithMap(inputId, newData, oldKeysGetter);
     }
   }
index b4e6a7182b559892a438cafc55d6acb70cd29c2f..92040cb3a8d1642b20dc133dbd920fa95f3c2770 100644 (file)
@@ -206,21 +206,22 @@ public class StubUpdatingIndex extends CustomImplementationFileBasedIndexExtensi
     return new MyIndex(indexId, storage, getIndexer());
   }
 
-  private static void updateStubIndices(@NotNull final Collection<StubIndexKey> indexKeys, final int inputId, @NotNull final Map<StubIndexKey, Map<Object, int[]>> oldStubTree, @NotNull final Map<StubIndexKey, Map<Object, int[]>> newStubTree) {
+  private static void updateStubIndices(@NotNull final Collection<StubIndexKey> indexKeys, final int inputId, @NotNull final Map<StubIndexKey, Map<Object, StubIdList>> oldStubTree, @NotNull final Map<StubIndexKey, Map<Object, StubIdList>> newStubTree) {
     final StubIndexImpl stubIndex = (StubIndexImpl)StubIndex.getInstance();
     for (StubIndexKey key : indexKeys) {
-      final Map<Object, int[]> oldMap = oldStubTree.get(key);
-      final Map<Object, int[]> newMap = newStubTree.get(key);
+      final Map<Object, StubIdList> oldMap = oldStubTree.get(key);
+      final Map<Object, StubIdList> newMap = newStubTree.get(key);
 
-      final Map<Object, int[]> _oldMap = oldMap != null ? oldMap : Collections.<Object, int[]>emptyMap();
-      final Map<Object, int[]> _newMap = newMap != null ? newMap : Collections.<Object, int[]>emptyMap();
+      final Map<Object, StubIdList> _oldMap = oldMap != null ? oldMap : Collections.<Object, StubIdList>emptyMap();
+      final Map<Object, StubIdList> _newMap = newMap != null ? newMap : Collections.<Object, StubIdList>emptyMap();
 
       stubIndex.updateIndex(key, inputId, _oldMap, _newMap);
     }
   }
 
   @NotNull
-  private static Collection<StubIndexKey> getAffectedIndices(@NotNull final Map<StubIndexKey, Map<Object, int[]>> oldStubTree, @NotNull final Map<StubIndexKey, Map<Object, int[]>> newStubTree) {
+  private static Collection<StubIndexKey> getAffectedIndices(@NotNull final Map<StubIndexKey, Map<Object, StubIdList>> oldStubTree,
+                                                             @NotNull final Map<StubIndexKey, Map<Object, StubIdList>> newStubTree) {
     Set<StubIndexKey> allIndices = new HashSet<StubIndexKey>();
     allIndices.addAll(oldStubTree.keySet());
     allIndices.addAll(newStubTree.keySet());
@@ -253,7 +254,7 @@ public class StubUpdatingIndex extends CustomImplementationFileBasedIndexExtensi
       throws StorageException {
 
       checkNameStorage();
-      final Map<StubIndexKey, Map<Object, int[]>> newStubTree = getStubTree(newData);
+      final Map<StubIndexKey, Map<Object, StubIdList>> newStubTree = getStubTree(newData);
 
       final StubIndexImpl stubIndex = getStubIndex();
       final Collection<StubIndexKey> allStubIndices = stubIndex.getAllStubIndexKeys();
@@ -267,7 +268,7 @@ public class StubUpdatingIndex extends CustomImplementationFileBasedIndexExtensi
           getWriteLock().lock();
 
           final Map<Integer, SerializedStubTree> oldData = readOldData(inputId);
-          final Map<StubIndexKey, Map<Object, int[]>> oldStubTree = getStubTree(oldData);
+          final Map<StubIndexKey, Map<Object, StubIdList>> oldStubTree = getStubTree(oldData);
 
           super.updateWithMap(inputId, newData, oldKeysGetter);
 
@@ -301,11 +302,22 @@ public class StubUpdatingIndex extends CustomImplementationFileBasedIndexExtensi
       }
     }
 
-    private static Map<StubIndexKey, Map<Object, int[]>> getStubTree(@NotNull final Map<Integer, SerializedStubTree> data) {
-      final Map<StubIndexKey, Map<Object, int[]>> stubTree;
+    private static Map<StubIndexKey, Map<Object, StubIdList>> getStubTree(@NotNull final Map<Integer, SerializedStubTree> data) {
+      final Map<StubIndexKey, Map<Object, StubIdList>> stubTree;
       if (!data.isEmpty()) {
         final SerializedStubTree stub = data.values().iterator().next();
-        stubTree = new StubTree((PsiFileStub)stub.getStub(true), false).indexStubTree();
+        Map<StubIndexKey, Map<Object, int[]>> map = new StubTree((PsiFileStub)stub.getStub(true), false).indexStubTree();
+
+        // xxx:fix refs inplace
+        stubTree = (Map)map;
+        for(StubIndexKey key:map.keySet()) {
+          Map<Object, int[]> value = map.get(key);
+          for(Object k: value.keySet()) {
+            int[] ints = value.get(k);
+            StubIdList stubList = ints.length == 1 ? new StubIdList(ints[0]) : new StubIdList(ints, ints.length);
+            ((Map<Object, StubIdList>)(Map)value).put(k, stubList);
+          }
+        }
       }
       else {
         stubTree = Collections.emptyMap();