fef3a5487f3d14b2282f12024c3df81a634db7d0
[idea/community.git] / java / java-impl / src / com / intellij / slicer / SliceUtil.java
1 /*
2  * Copyright 2000-2009 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.slicer;
17
18 import com.intellij.codeInspection.dataFlow.DfaUtil;
19 import com.intellij.openapi.project.Project;
20 import com.intellij.openapi.util.Comparing;
21 import com.intellij.psi.*;
22 import com.intellij.psi.impl.PsiSubstitutorImpl;
23 import com.intellij.psi.impl.source.DummyHolder;
24 import com.intellij.psi.search.SearchScope;
25 import com.intellij.psi.search.searches.MethodReferencesSearch;
26 import com.intellij.psi.search.searches.OverridingMethodsSearch;
27 import com.intellij.psi.search.searches.ReferencesSearch;
28 import com.intellij.psi.tree.IElementType;
29 import com.intellij.psi.util.MethodSignatureUtil;
30 import com.intellij.psi.util.PsiUtil;
31 import com.intellij.psi.util.TypeConversionUtil;
32 import com.intellij.slicer.forward.SliceFUtil;
33 import com.intellij.util.ArrayUtil;
34 import com.intellij.util.Processor;
35 import gnu.trove.THashMap;
36 import gnu.trove.THashSet;
37 import org.jetbrains.annotations.NotNull;
38 import org.jetbrains.annotations.Nullable;
39
40 import java.util.Arrays;
41 import java.util.Collection;
42 import java.util.Map;
43 import java.util.Set;
44
45 /**
46  * @author cdr
47  */
48 public class SliceUtil {
49   public static boolean processUsagesFlownDownTo(@NotNull PsiElement expression,
50                                                  @NotNull Processor<SliceUsage> processor,
51                                                  @NotNull SliceUsage parent,
52                                                  @NotNull PsiSubstitutor parentSubstitutor) {
53     expression = simplify(expression);
54     PsiElement original = expression;
55     if (expression instanceof PsiReferenceExpression) {
56       PsiElement element = SliceFUtil.complexify(expression);
57       if (element instanceof PsiExpression && PsiUtil.isOnAssignmentLeftHand((PsiExpression)element)) {
58         PsiExpression rightSide = ((PsiAssignmentExpression)element.getParent()).getRExpression();
59         return rightSide == null || handToProcessor(rightSide, processor, parent, parentSubstitutor);
60       }
61       PsiReferenceExpression ref = (PsiReferenceExpression)expression;
62       JavaResolveResult result = ref.advancedResolve(false);
63       parentSubstitutor = result.getSubstitutor().putAll(parentSubstitutor);
64       PsiElement resolved = result.getElement();
65       if (resolved instanceof PsiCompiledElement) {
66         resolved = resolved.getNavigationElement();
67       }
68       if (resolved instanceof PsiMethod && expression.getParent() instanceof PsiMethodCallExpression) {
69         return processUsagesFlownDownTo(expression.getParent(), processor, parent, parentSubstitutor);
70       }
71       if (!(resolved instanceof PsiVariable)) return true;
72       expression = resolved;
73     }
74     if (expression instanceof PsiVariable) {
75       PsiVariable variable = (PsiVariable)expression;
76       Collection<PsiExpression> values = DfaUtil.getCachedVariableValues(variable, original);
77       if (values == null) {
78         SliceUsage stopUsage = createTooComplexDFAUsage(expression, parent, parentSubstitutor);
79         return processor.process(stopUsage);
80       }
81       final Set<PsiExpression> expressions = new THashSet<PsiExpression>(values);
82       PsiExpression initializer = variable.getInitializer();
83       if (initializer != null && expressions.isEmpty()) expressions.add(initializer);
84       for (PsiExpression exp : expressions) {
85         if (!handToProcessor(exp, processor, parent, parentSubstitutor)) return false;
86       }
87       if (variable instanceof PsiField) {
88         return processFieldUsages((PsiField)variable, processor, parent, parentSubstitutor);
89       }
90       else if (variable instanceof PsiParameter) {
91         return processParameterUsages((PsiParameter)variable, processor, parent, parentSubstitutor);
92       }
93     }
94     if (expression instanceof PsiMethodCallExpression) {
95       return processMethodReturnValue((PsiMethodCallExpression)expression, processor, parent, parentSubstitutor);
96     }
97     if (expression instanceof PsiConditionalExpression) {
98       PsiConditionalExpression conditional = (PsiConditionalExpression)expression;
99       PsiExpression thenE = conditional.getThenExpression();
100       PsiExpression elseE = conditional.getElseExpression();
101       if (thenE != null && !handToProcessor(thenE, processor, parent, parentSubstitutor)) return false;
102       if (elseE != null && !handToProcessor(elseE, processor, parent, parentSubstitutor)) return false;
103     }
104     if (expression instanceof PsiAssignmentExpression) {
105       PsiAssignmentExpression assignment = (PsiAssignmentExpression)expression;
106       IElementType tokenType = assignment.getOperationTokenType();
107       PsiExpression rExpression = assignment.getRExpression();
108
109       if (tokenType == JavaTokenType.EQ && rExpression != null) {
110         return processUsagesFlownDownTo(rExpression, processor, parent, parentSubstitutor);
111       }
112     }
113     return true;
114   }
115
116   private static PsiElement simplify(@NotNull PsiElement expression) {
117     if (expression instanceof PsiParenthesizedExpression) {
118       return simplify(((PsiParenthesizedExpression)expression).getExpression());
119     }
120     if (expression instanceof PsiTypeCastExpression) {
121       return simplify(((PsiTypeCastExpression)expression).getOperand());
122     }
123     return expression;
124   }
125
126   private static boolean handToProcessor(@NotNull PsiExpression exp,
127                                          @NotNull Processor<SliceUsage> processor,
128                                          @NotNull SliceUsage parent,
129                                          @NotNull PsiSubstitutor substitutor) {
130     final PsiExpression realExpression =
131       exp.getParent() instanceof DummyHolder ? (PsiExpression)((DummyHolder)exp.getParent()).getContext() : exp;
132     assert realExpression != null;
133     if (!(realExpression instanceof PsiCompiledElement)) {
134       SliceUsage usage = createSliceUsage(realExpression, parent, substitutor);
135       if (!processor.process(usage)) return false;
136     }
137     return true;
138   }
139
140   private static boolean processMethodReturnValue(@NotNull final PsiMethodCallExpression methodCallExpr,
141                                                   @NotNull final Processor<SliceUsage> processor,
142                                                   @NotNull final SliceUsage parent,
143                                                   @NotNull final PsiSubstitutor parentSubstitutor) {
144     final JavaResolveResult resolved = methodCallExpr.resolveMethodGenerics();
145     PsiElement r = resolved.getElement();
146     if (r instanceof PsiCompiledElement) {
147       r = r.getNavigationElement();
148     }
149     if (!(r instanceof PsiMethod)) return true;
150     PsiMethod methodCalled = (PsiMethod)r;
151
152     PsiType returnType = methodCalled.getReturnType();
153     if (returnType == null) return true;
154
155     final PsiType parentType = parentSubstitutor.substitute(methodCallExpr.getType());
156     final PsiSubstitutor substitutor = resolved.getSubstitutor().putAll(parentSubstitutor);
157     Collection<PsiMethod> overrides = new THashSet<PsiMethod>(OverridingMethodsSearch.search(methodCalled, parent.getScope().toSearchScope(), true).findAll());
158     overrides.add(methodCalled);
159
160     final boolean[] result = {true};
161     for (PsiMethod override : overrides) {
162       if (!result[0]) break;
163       if (override instanceof PsiCompiledElement) {
164         override = (PsiMethod)override.getNavigationElement();
165       }
166       if (!parent.getScope().contains(override)) continue;
167
168       final PsiCodeBlock body = override.getBody();
169       if (body == null) continue;
170
171       final PsiSubstitutor superSubstitutor = methodCalled == override ? substitutor :
172         MethodSignatureUtil.getSuperMethodSignatureSubstitutor(methodCalled.getSignature(substitutor), override.getSignature(substitutor));
173
174       body.accept(new JavaRecursiveElementWalkingVisitor() {
175         @Override
176         public void visitAnonymousClass(PsiAnonymousClass aClass) {
177           // do not look for returns there
178         }
179
180         public void visitReturnStatement(final PsiReturnStatement statement) {
181           PsiExpression returnValue = statement.getReturnValue();
182           if (returnValue == null) return;
183           if (!TypeConversionUtil.isAssignable(parentType, superSubstitutor.substitute(superSubstitutor.substitute(returnValue.getType())))) return;
184           if (!handToProcessor(returnValue, processor, parent, substitutor)) {
185             stopWalking();
186             result[0] = false;
187           }
188         }
189       });
190     }
191
192     return result[0];
193   }
194
195   private static boolean processFieldUsages(@NotNull final PsiField field, @NotNull final Processor<SliceUsage> processor, @NotNull final SliceUsage parent,
196                                             @NotNull final PsiSubstitutor parentSubstitutor) {
197     if (field.hasInitializer()) {
198       PsiExpression initializer = field.getInitializer();
199       if (initializer != null && !(field instanceof PsiCompiledElement)) {
200         if (!handToProcessor(initializer, processor, parent, parentSubstitutor)) return false;
201       }
202     }
203     SearchScope searchScope = parent.getScope().toSearchScope();
204     return ReferencesSearch.search(field, searchScope).forEach(new Processor<PsiReference>() {
205       public boolean process(final PsiReference reference) {
206         SliceManager.getInstance(field.getProject()).checkCanceled();
207         PsiElement element = reference.getElement();
208         if (!(element instanceof PsiReferenceExpression)) return true;
209         if (element instanceof PsiCompiledElement) {
210           element = element.getNavigationElement();
211           if (!parent.getScope().contains(element)) return true;
212         }
213         final PsiReferenceExpression referenceExpression = (PsiReferenceExpression)element;
214         PsiElement parentExpr = referenceExpression.getParent();
215         if (PsiUtil.isOnAssignmentLeftHand(referenceExpression)) {
216           PsiExpression rExpression = ((PsiAssignmentExpression)parentExpr).getRExpression();
217           PsiType rtype = rExpression.getType();
218           PsiType ftype = field.getType();
219           if (TypeConversionUtil.isAssignable(parentSubstitutor.substitute(ftype), parentSubstitutor.substitute(rtype))) {
220             return handToProcessor(rExpression, processor, parent, parentSubstitutor);
221           }
222         }
223         if (parentExpr instanceof PsiPrefixExpression && ((PsiPrefixExpression)parentExpr).getOperand() == referenceExpression && ( ((PsiPrefixExpression)parentExpr).getOperationTokenType() == JavaTokenType.PLUSPLUS || ((PsiPrefixExpression)parentExpr).getOperationTokenType() == JavaTokenType.MINUSMINUS)) {
224           PsiPrefixExpression prefixExpression = (PsiPrefixExpression)parentExpr;
225           return handToProcessor(prefixExpression, processor, parent, parentSubstitutor);
226         }
227         if (parentExpr instanceof PsiPostfixExpression && ((PsiPostfixExpression)parentExpr).getOperand() == referenceExpression && ( ((PsiPostfixExpression)parentExpr).getOperationTokenType() == JavaTokenType.PLUSPLUS || ((PsiPostfixExpression)parentExpr).getOperationTokenType() == JavaTokenType.MINUSMINUS)) {
228           PsiPostfixExpression postfixExpression = (PsiPostfixExpression)parentExpr;
229           return handToProcessor(postfixExpression, processor, parent, parentSubstitutor);
230         }
231         return true;
232       }
233     });
234   }
235
236   public static SliceUsage createSliceUsage(@NotNull PsiElement element, @NotNull SliceUsage parent, @NotNull PsiSubstitutor substitutor) {
237     return new SliceUsage(simplify(element), parent, substitutor);
238   }
239   public static SliceUsage createTooComplexDFAUsage(@NotNull PsiElement element, @NotNull SliceUsage parent, @NotNull PsiSubstitutor substitutor) {
240     return new SliceTooComplexDFAUsage(simplify(element), parent, substitutor);
241   }
242
243   static boolean processParameterUsages(@NotNull final PsiParameter parameter, @NotNull final Processor<SliceUsage> processor, @NotNull final SliceUsage parent,
244                                         @NotNull final PsiSubstitutor parentSubstitutor) {
245     PsiElement declarationScope = parameter.getDeclarationScope();
246     if (!(declarationScope instanceof PsiMethod)) return true;
247     final PsiMethod method = (PsiMethod)declarationScope;
248     final PsiType actualType = parameter.getType();
249
250     final PsiParameter[] actualParameters = method.getParameterList().getParameters();
251     final int paramSeqNo = ArrayUtil.find(actualParameters, parameter);
252     assert paramSeqNo != -1;
253
254     Collection<PsiMethod> superMethods = new THashSet<PsiMethod>(Arrays.asList(method.findDeepestSuperMethods()));
255     superMethods.add(method);
256
257     final Set<PsiReference> processed = new THashSet<PsiReference>(); //usages of super method and overridden method can overlap
258     for (final PsiMethod superMethod : superMethods) {
259       if (!MethodReferencesSearch.search(superMethod, parent.getScope().toSearchScope(), true).forEach(new Processor<PsiReference>() {
260         public boolean process(final PsiReference reference) {
261           SliceManager.getInstance(parameter.getProject()).checkCanceled();
262           synchronized (processed) {
263             if (!processed.add(reference)) return true;
264           }
265           PsiElement refElement = reference.getElement();
266           PsiExpressionList argumentList;
267           JavaResolveResult result;
268           if (refElement instanceof PsiCall) {
269             // the case of enum constant decl
270             PsiCall call = (PsiCall)refElement;
271             argumentList = call.getArgumentList();
272             result = call.resolveMethodGenerics();
273           }
274           else {
275             PsiElement element = refElement.getParent();
276             if (element instanceof PsiCompiledElement) return true;
277             if (element instanceof PsiAnonymousClass) {
278               PsiAnonymousClass anon = (PsiAnonymousClass)element;
279               argumentList = anon.getArgumentList();
280               PsiElement callExp = element.getParent();
281               if (!(callExp instanceof PsiCallExpression)) return true;
282               result = ((PsiCall)callExp).resolveMethodGenerics();
283             }
284             else {
285               if (!(element instanceof PsiCall)) return true;
286               PsiCall call = (PsiCall)element;
287               argumentList = call.getArgumentList();
288               result = call.resolveMethodGenerics();
289             }
290           }
291           PsiSubstitutor substitutor = result.getSubstitutor();
292
293           PsiExpression[] expressions = argumentList.getExpressions();
294           if (paramSeqNo >= expressions.length) {
295             return true;
296           }
297           PsiExpression passExpression = expressions[paramSeqNo];
298
299           Project project = argumentList.getProject();
300           PsiElement element = result.getElement();
301           if (element instanceof PsiCompiledElement) {
302             element = element.getNavigationElement();
303           }
304
305           // for erased method calls for which we cannot determine target substitutor,
306           // rely on call argument types. I.e. new Pair(1,2) -> Pair<Integer, Integer>
307           if (element instanceof PsiTypeParameterListOwner && PsiUtil.isRawSubstitutor((PsiTypeParameterListOwner)element, substitutor)) {
308             PsiTypeParameter[] typeParameters = substitutor.getSubstitutionMap().keySet().toArray(new PsiTypeParameter[0]);
309
310             PsiResolveHelper resolveHelper = JavaPsiFacade.getInstance(project).getResolveHelper();
311             substitutor = resolveHelper.inferTypeArguments(typeParameters, actualParameters, expressions, parentSubstitutor, argumentList, false);
312           }
313
314           substitutor = removeRawMappingsLeftFromResolve(substitutor);
315
316           PsiSubstitutor combined = unify(substitutor, parentSubstitutor, project);
317           if (combined == null) return true;
318           PsiType substitited = combined.substitute(passExpression.getType());
319           if (substitited == null || !TypeConversionUtil.areTypesConvertible(substitited, actualType)) return true;
320
321           return handToProcessor(passExpression, processor, parent, combined);
322         }
323       })) {
324         return false;
325       }
326     }
327
328     return true;
329   }
330
331   @NotNull
332   private static PsiSubstitutor removeRawMappingsLeftFromResolve(@NotNull PsiSubstitutor substitutor) {
333     Map<PsiTypeParameter, PsiType> map = null;
334     for (Map.Entry<PsiTypeParameter, PsiType> entry : substitutor.getSubstitutionMap().entrySet()) {
335       if (entry.getValue() == null) {
336         if (map == null) map = new THashMap<PsiTypeParameter, PsiType>();
337         map.put(entry.getKey(), entry.getValue());
338       }
339     }
340     if (map == null) return substitutor;
341     Map<PsiTypeParameter, PsiType> newmap = new THashMap<PsiTypeParameter, PsiType>(substitutor.getSubstitutionMap());
342     newmap.keySet().removeAll(map.keySet());
343     return PsiSubstitutorImpl.createSubstitutor(newmap);
344   }
345
346   @Nullable
347   private static PsiSubstitutor unify(@NotNull PsiSubstitutor substitutor, @NotNull PsiSubstitutor parentSubstitutor, @NotNull Project project) {
348     Map<PsiTypeParameter,PsiType> newMap = new THashMap<PsiTypeParameter, PsiType>(substitutor.getSubstitutionMap());
349
350     for (Map.Entry<PsiTypeParameter, PsiType> entry : substitutor.getSubstitutionMap().entrySet()) {
351       PsiTypeParameter typeParameter = entry.getKey();
352       PsiType type = entry.getValue();
353       PsiClass resolved = PsiUtil.resolveClassInType(type);
354       if (!parentSubstitutor.getSubstitutionMap().containsKey(typeParameter)) continue;
355       PsiType parentType = parentSubstitutor.substitute(parentSubstitutor.substitute(typeParameter));
356
357       if (resolved instanceof PsiTypeParameter) {
358         PsiTypeParameter res = (PsiTypeParameter)resolved;
359         newMap.put(res, parentType);
360       }
361       else if (!Comparing.equal(type, parentType)) {
362         return null; // cannot unify
363       }
364     }
365     return JavaPsiFacade.getElementFactory(project).createSubstitutor(newMap);
366   }
367 }