-
Notifications
You must be signed in to change notification settings - Fork 378
/
ChainFinder.java
188 lines (161 loc) · 8.13 KB
/
ChainFinder.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
package org.eclipse.jdt.ls.core.internal.contentassist;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import org.eclipse.jdt.core.IJavaElement;
import org.eclipse.jdt.core.IType;
import org.eclipse.jdt.core.compiler.CharOperation;
import org.eclipse.jdt.internal.ui.text.Chain;
import org.eclipse.jdt.internal.ui.text.ChainElement;
import org.eclipse.jdt.internal.ui.text.ChainElement.ElementType;
import org.eclipse.jdt.internal.ui.text.ChainElementAnalyzer;
import org.eclipse.jdt.internal.ui.text.ChainType;
// this class is copied from org.eclipse.jdt.internal.ui.text.ChainFinder to try out the token search concept.
public class ChainFinder {
private final List<ChainType> expectedTypes;
private final List<String> excludedTypes;
private final IType receiverType;
private final List<Chain> chains = new LinkedList<>();
private final Map<IJavaElement, ChainElement> edgeCache = new HashMap<>();
private final Map<String, List<IJavaElement>> fieldsAndMethodsCache = new HashMap<>();
private final Map<String, Boolean> assignableCache = new HashMap<>();
private volatile boolean isCanceled;
private String token;
public ChainFinder(final List<ChainType> expectedTypes, final List<String> excludedTypes, final IType receiverType, final String token) {
this.expectedTypes = expectedTypes;
this.excludedTypes = excludedTypes;
this.receiverType = receiverType;
this.token = token;
}
public void startChainSearch(final List<ChainElement> entrypoints, final int maxChains, final int minDepth, final int maxDepth) {
for (final ChainType expected : expectedTypes) {
if (expected != null && !ChainFinder.isFromExcludedType(excludedTypes, expected)) {
ChainType expectedType = expected;
int expectedDimension = 0;
if (expectedType.getDimension() > 0) {
expectedDimension = expectedType.getDimension();
}
searchChainsForExpectedType(expectedType, expectedDimension, entrypoints, maxChains, minDepth, maxDepth);
}
}
}
public void cancel() {
isCanceled = true;
}
private void searchChainsForExpectedType(final ChainType expectedType, final int expectedDimensions, final List<ChainElement> entrypoints, final int maxChains, final int minDepth, final int maxDepth) {
final LinkedList<LinkedList<ChainElement>> incompleteChains = prepareQueue(entrypoints);
while (!incompleteChains.isEmpty() && !isCanceled) {
final LinkedList<ChainElement> chain = incompleteChains.poll();
final ChainElement edge = chain.getLast();
final ChainElement start = chain.getFirst();
if (isValidEndOfChain(edge, start, expectedType, expectedDimensions)) {
if (chain.size() >= minDepth) {
chains.add(new Chain(chain, expectedDimensions));
if (chains.size() == maxChains) {
break;
}
}
continue;
}
if (chain.size() < maxDepth && incompleteChains.size() <= 50000) {
searchDeeper(chain, incompleteChains, edge.getReturnType());
}
}
}
/**
* Returns the potentially incomplete list of call chains that could be found
* before a time out happened. The contents of this list are mutable and may
* change as the search makes progress.
*
* @return The list of call chains
*/
public List<Chain> getChains() {
return chains;
}
private static LinkedList<LinkedList<ChainElement>> prepareQueue(final List<ChainElement> entrypoints) {
final LinkedList<LinkedList<ChainElement>> incompleteChains = new LinkedList<>();
for (final ChainElement entrypoint : entrypoints) {
final LinkedList<ChainElement> chain = new LinkedList<>();
chain.add(entrypoint);
incompleteChains.add(chain);
}
return incompleteChains;
}
public static boolean isFromExcludedType(final List<String> excluded, final IJavaElement element) {
if (element instanceof IType) {
return excluded.contains(((IType) element).getFullyQualifiedName());
} else {
return excluded.contains(element.getElementName());
}
}
public static boolean isFromExcludedType(final List<String> excluded, final ChainType element) {
if (element.getType() != null) {
return isFromExcludedType(excluded, element.getType());
}
return excluded.contains(element.getPrimitiveType());
}
private boolean isValidEndOfChain(final ChainElement edge, ChainElement start, final ChainType expectedType, final int expectedDimension) {
if (edge.getElementType() == ElementType.TYPE) {
return false;
}
if (token != null && !token.isBlank() && !CharOperation.subWordMatch(token.toCharArray(), edge.getElement().getElementName().toCharArray())
&& !CharOperation.subWordMatch(token.toCharArray(), start.getElement().getElementName().toCharArray())) {
return false;
}
if ((edge.getReturnType().getPrimitiveType() != null)) {
return edge.getReturnType().getPrimitiveType().equals(expectedType.getPrimitiveType());
}
if (expectedType.getPrimitiveType() != null) {
return expectedType.getPrimitiveType().equals(edge.getReturnType().getPrimitiveType());
}
Boolean isAssignable = assignableCache.get(edge.toString() + expectedType.toString());
if (isAssignable == null) {
isAssignable = ChainElementAnalyzer.isAssignable(edge, expectedType.getType(), expectedDimension);
assignableCache.put(edge.toString() + expectedType.toString(), isAssignable);
}
return isAssignable;
}
private void searchDeeper(final LinkedList<ChainElement> chain, final List<LinkedList<ChainElement>> incompleteChains, final ChainType currentlyVisitedType) {
boolean staticOnly = false;
if (chain.getLast().getElementType() == ElementType.TYPE) {
staticOnly = true;
}
for (final IJavaElement element : findAllFieldsAndMethods(currentlyVisitedType, staticOnly)) {
final ChainElement newEdge = createEdge(element);
if (newEdge.getElementType() != null && !chain.contains(newEdge)) {
incompleteChains.add(cloneChainAndAppendEdge(chain, newEdge));
}
}
}
private List<IJavaElement> findAllFieldsAndMethods(final ChainType chainElementType, boolean staticOnly) {
List<IJavaElement> cached = fieldsAndMethodsCache.get(chainElementType.toString() + Boolean.toString(staticOnly));
if (cached == null) {
cached = new LinkedList<>();
Collection<IJavaElement> candidates = staticOnly ? ChainElementAnalyzer.findAllPublicStaticFieldsAndNonVoidNonPrimitiveStaticMethods(chainElementType, new ChainType(receiverType))
: ChainElementAnalyzer.findVisibleInstanceFieldsAndRelevantInstanceMethods(chainElementType, new ChainType(receiverType));
for (final IJavaElement e : candidates) {
if (!ChainFinder.isFromExcludedType(excludedTypes, e)) {
cached.add(e);
}
}
fieldsAndMethodsCache.put(chainElementType.toString() + Boolean.toString(staticOnly), cached);
}
return cached;
}
private ChainElement createEdge(final IJavaElement member) {
ChainElement cached = edgeCache.get(member);
if (cached == null) {
cached = new ChainElement(member, false);
edgeCache.put(member, cached);
}
return cached;
}
private static LinkedList<ChainElement> cloneChainAndAppendEdge(final LinkedList<ChainElement> chain, final ChainElement newEdge) {
@SuppressWarnings("unchecked")
final LinkedList<ChainElement> chainCopy = (LinkedList<ChainElement>) chain.clone();
chainCopy.add(newEdge);
return chainCopy;
}
}