mark as internal
[idea/community.git] / platform / core-impl / src / com / intellij / psi / stubs / ObjectStubTree.java
1 // Copyright 2000-2020 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license that can be found in the LICENSE file.
2 package com.intellij.psi.stubs;
3
4 import com.intellij.openapi.util.Key;
5 import com.intellij.util.ArrayUtil;
6 import com.intellij.util.containers.ContainerUtil;
7 import gnu.trove.THashMap;
8 import gnu.trove.TObjectHashingStrategy;
9 import gnu.trove.TObjectObjectProcedure;
10 import gnu.trove.TObjectProcedure;
11 import org.jetbrains.annotations.ApiStatus;
12 import org.jetbrains.annotations.NotNull;
13 import org.jetbrains.annotations.Nullable;
14
15 import java.util.ArrayList;
16 import java.util.List;
17 import java.util.Map;
18 import java.util.function.Function;
19
20 /**
21  * @author Dmitry Avdeev
22  */
23 public class ObjectStubTree<T extends Stub> {
24   private static final Key<ObjectStubTree<?>> STUB_TO_TREE_REFERENCE = Key.create("stub to tree reference");
25   protected final ObjectStubBase<?> myRoot;
26   private String myDebugInfo;
27   private boolean myHasBackReference;
28   private final List<T> myPlainList;
29
30   public ObjectStubTree(final @NotNull ObjectStubBase<?> root, boolean withBackReference) {
31     myRoot = root;
32     myPlainList = enumerateStubs(root);
33     if (withBackReference) {
34       myRoot.putUserData(STUB_TO_TREE_REFERENCE, this); // This will prevent soft references to stub tree to be collected before all of the stubs are collected.
35     }
36   }
37
38   public @NotNull Stub getRoot() {
39     return myRoot;
40   }
41
42   public @NotNull List<T> getPlainList() {
43     return myPlainList;
44   }
45
46   @NotNull
47   List<T> getPlainListFromAllRoots() {
48     return getPlainList();
49   }
50
51   @Deprecated
52   @ApiStatus.Internal
53   public @NotNull Map<StubIndexKey<?, ?>, Map<Object, int[]>> indexStubTree() {
54     return indexStubTree(key -> ContainerUtil.canonicalStrategy());
55   }
56
57   @ApiStatus.Internal
58   public @NotNull Map<StubIndexKey<?, ?>, Map<Object, int[]>> indexStubTree(@NotNull Function<StubIndexKey<?, ?>, TObjectHashingStrategy<?>> keyHashingStrategyFunction) {
59     StubIndexSink sink = new StubIndexSink(keyHashingStrategyFunction);
60     final List<T> plainList = getPlainListFromAllRoots();
61     for (int i = 0, plainListSize = plainList.size(); i < plainListSize; i++) {
62       final Stub stub = plainList.get(i);
63       sink.myStubIdx = i;
64       StubSerializationUtil.getSerializer(stub).indexStub(stub, sink);
65     }
66
67     return sink.getResult();
68   }
69
70   protected @NotNull List<T> enumerateStubs(@NotNull Stub root) {
71     List<T> result = new ArrayList<>();
72     //noinspection unchecked
73     enumerateStubsInto(root, (List)result);
74     return result;
75   }
76
77   private static void enumerateStubsInto(@NotNull Stub root, @NotNull List<? super Stub> result) {
78     ((ObjectStubBase)root).id = result.size();
79     result.add(root);
80     List<? extends Stub> childrenStubs = root.getChildrenStubs();
81     //noinspection ForLoopReplaceableByForEach
82     for (int i = 0; i < childrenStubs.size(); i++) {
83       Stub child = childrenStubs.get(i);
84       enumerateStubsInto(child, result);
85     }
86   }
87
88   public void setDebugInfo(@NotNull String info) {
89     ObjectStubTree<?> ref = getStubTree(myRoot);
90     if (ref != null) {
91       assert ref == this;
92     }
93     myHasBackReference = ref != null;
94     myDebugInfo = info;
95   }
96
97   public static @Nullable ObjectStubTree getStubTree(@NotNull ObjectStubBase root) {
98     return root.getUserData(STUB_TO_TREE_REFERENCE);
99   }
100
101   public String getDebugInfo() {
102     return myHasBackReference ? myDebugInfo + "; with backReference" : myDebugInfo;
103   }
104
105   @Override
106   public String toString() {
107     return getClass().getSimpleName() + "{myDebugInfo='" + getDebugInfo() + '\'' + ", myRoot=" + myRoot + '}' + hashCode();
108   }
109
110   private static final class StubIndexSink implements IndexSink, TObjectProcedure<Map<Object, int[]>>, TObjectObjectProcedure<Object,int[]> {
111     private final THashMap<StubIndexKey<?, ?>, Map<Object, int[]>> myResult = new THashMap<>();
112     private final Function<StubIndexKey<?, ?>, TObjectHashingStrategy<?>> myHashingStrategyFunction;
113     private int myStubIdx;
114     private Map<Object, int[]> myProcessingMap;
115
116     private StubIndexSink(@NotNull Function<StubIndexKey<?, ?>, TObjectHashingStrategy<?>> hashingStrategyFunction) {
117       myHashingStrategyFunction = hashingStrategyFunction;
118     }
119
120     @Override
121     public void occurrence(final @NotNull StubIndexKey indexKey, final @NotNull Object value) {
122       Map<Object, int[]> map = myResult.get(indexKey);
123       if (map == null) {
124         //noinspection unchecked
125         map = new THashMap<>((TObjectHashingStrategy<Object>)myHashingStrategyFunction.apply(indexKey));
126         myResult.put(indexKey, map);
127       }
128
129       int[] list = map.get(value);
130       if (list == null) {
131         map.put(value, new int[] {myStubIdx});
132       }
133       else {
134         int lastNonZero = ArrayUtil.lastIndexOfNot(list, 0);
135         if (lastNonZero >= 0 && list[lastNonZero] == myStubIdx) {
136           // second and subsequent occurrence calls for the same value are no op
137           return;
138         }
139         int lastZero = lastNonZero + 1;
140
141         if (lastZero == list.length) {
142           list = ArrayUtil.realloc(list, Math.max(4, list.length << 1));
143           map.put(value, list);
144         }
145         list[lastZero] = myStubIdx;
146       }
147     }
148
149     public @NotNull Map<StubIndexKey<?, ?>, Map<Object, int[]>> getResult() {
150       myResult.forEachValue(this);
151       return myResult;
152     }
153
154     @Override
155     public boolean execute(Map<Object, int[]> object) {
156       myProcessingMap = object;
157       ((THashMap<Object, int[]>)object).forEachEntry(this);
158       return true;
159     }
160
161     @Override
162     public boolean execute(Object a, int[] b) {
163       if (b.length == 1) return true;
164       int firstZero = ArrayUtil.indexOf(b, 0);
165       if (firstZero != -1) {
166         int[] shorterList = ArrayUtil.realloc(b, firstZero);
167         myProcessingMap.put(a, shorterList);
168       }
169       return true;
170     }
171   }
172 }