NPE
[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 s = methodCalled == override ? substitutor :
172         MethodSignatureUtil.getSuperMethodSignatureSubstitutor(methodCalled.getSignature(substitutor), override.getSignature(substitutor));
173       final PsiSubstitutor superSubstitutor = s == null ? parentSubstitutor : s;
174
175       body.accept(new JavaRecursiveElementWalkingVisitor() {
176         @Override
177         public void visitAnonymousClass(PsiAnonymousClass aClass) {
178           // do not look for returns there
179         }
180
181         public void visitReturnStatement(final PsiReturnStatement statement) {
182           PsiExpression returnValue = statement.getReturnValue();
183           if (returnValue == null) return;
184           if (!TypeConversionUtil.isAssignable(parentType, superSubstitutor.substitute(superSubstitutor.substitute(returnValue.getType())))) return;
185           if (!handToProcessor(returnValue, processor, parent, substitutor)) {
186             stopWalking();
187             result[0] = false;
188           }
189         }
190       });
191     }
192
193     return result[0];
194   }
195
196   private static boolean processFieldUsages(@NotNull final PsiField field, @NotNull final Processor<SliceUsage> processor, @NotNull final SliceUsage parent,
197                                             @NotNull final PsiSubstitutor parentSubstitutor) {
198     if (field.hasInitializer()) {
199       PsiExpression initializer = field.getInitializer();
200       if (initializer != null && !(field instanceof PsiCompiledElement)) {
201         if (!handToProcessor(initializer, processor, parent, parentSubstitutor)) return false;
202       }
203     }
204     SearchScope searchScope = parent.getScope().toSearchScope();
205     return ReferencesSearch.search(field, searchScope).forEach(new Processor<PsiReference>() {
206       public boolean process(final PsiReference reference) {
207         SliceManager.getInstance(field.getProject()).checkCanceled();
208         PsiElement element = reference.getElement();
209         if (!(element instanceof PsiReferenceExpression)) return true;
210         if (element instanceof PsiCompiledElement) {
211           element = element.getNavigationElement();
212           if (!parent.getScope().contains(element)) return true;
213         }
214         final PsiReferenceExpression referenceExpression = (PsiReferenceExpression)element;
215         PsiElement parentExpr = referenceExpression.getParent();
216         if (PsiUtil.isOnAssignmentLeftHand(referenceExpression)) {
217           PsiExpression rExpression = ((PsiAssignmentExpression)parentExpr).getRExpression();
218           PsiType rtype = rExpression.getType();
219           PsiType ftype = field.getType();
220           if (TypeConversionUtil.isAssignable(parentSubstitutor.substitute(ftype), parentSubstitutor.substitute(rtype))) {
221             return handToProcessor(rExpression, processor, parent, parentSubstitutor);
222           }
223         }
224         if (parentExpr instanceof PsiPrefixExpression && ((PsiPrefixExpression)parentExpr).getOperand() == referenceExpression && ( ((PsiPrefixExpression)parentExpr).getOperationTokenType() == JavaTokenType.PLUSPLUS || ((PsiPrefixExpression)parentExpr).getOperationTokenType() == JavaTokenType.MINUSMINUS)) {
225           PsiPrefixExpression prefixExpression = (PsiPrefixExpression)parentExpr;
226           return handToProcessor(prefixExpression, processor, parent, parentSubstitutor);
227         }
228         if (parentExpr instanceof PsiPostfixExpression && ((PsiPostfixExpression)parentExpr).getOperand() == referenceExpression && ( ((PsiPostfixExpression)parentExpr).getOperationTokenType() == JavaTokenType.PLUSPLUS || ((PsiPostfixExpression)parentExpr).getOperationTokenType() == JavaTokenType.MINUSMINUS)) {
229           PsiPostfixExpression postfixExpression = (PsiPostfixExpression)parentExpr;
230           return handToProcessor(postfixExpression, processor, parent, parentSubstitutor);
231         }
232         return true;
233       }
234     });
235   }
236
237   public static SliceUsage createSliceUsage(@NotNull PsiElement element, @NotNull SliceUsage parent, @NotNull PsiSubstitutor substitutor) {
238     return new SliceUsage(simplify(element), parent, substitutor);
239   }
240   public static SliceUsage createTooComplexDFAUsage(@NotNull PsiElement element, @NotNull SliceUsage parent, @NotNull PsiSubstitutor substitutor) {
241     return new SliceTooComplexDFAUsage(simplify(element), parent, substitutor);
242   }
243
244   static boolean processParameterUsages(@NotNull final PsiParameter parameter, @NotNull final Processor<SliceUsage> processor, @NotNull final SliceUsage parent,
245                                         @NotNull final PsiSubstitutor parentSubstitutor) {
246     PsiElement declarationScope = parameter.getDeclarationScope();
247     if (!(declarationScope instanceof PsiMethod)) return true;
248     final PsiMethod method = (PsiMethod)declarationScope;
249     final PsiType actualType = parameter.getType();
250
251     final PsiParameter[] actualParameters = method.getParameterList().getParameters();
252     final int paramSeqNo = ArrayUtil.find(actualParameters, parameter);
253     assert paramSeqNo != -1;
254
255     Collection<PsiMethod> superMethods = new THashSet<PsiMethod>(Arrays.asList(method.findDeepestSuperMethods()));
256     superMethods.add(method);
257
258     final Set<PsiReference> processed = new THashSet<PsiReference>(); //usages of super method and overridden method can overlap
259     for (final PsiMethod superMethod : superMethods) {
260       if (!MethodReferencesSearch.search(superMethod, parent.getScope().toSearchScope(), true).forEach(new Processor<PsiReference>() {
261         public boolean process(final PsiReference reference) {
262           SliceManager.getInstance(parameter.getProject()).checkCanceled();
263           synchronized (processed) {
264             if (!processed.add(reference)) return true;
265           }
266           PsiElement refElement = reference.getElement();
267           PsiExpressionList argumentList;
268           JavaResolveResult result;
269           if (refElement instanceof PsiCall) {
270             // the case of enum constant decl
271             PsiCall call = (PsiCall)refElement;
272             argumentList = call.getArgumentList();
273             result = call.resolveMethodGenerics();
274           }
275           else {
276             PsiElement element = refElement.getParent();
277             if (element instanceof PsiCompiledElement) return true;
278             if (element instanceof PsiAnonymousClass) {
279               PsiAnonymousClass anon = (PsiAnonymousClass)element;
280               argumentList = anon.getArgumentList();
281               PsiElement callExp = element.getParent();
282               if (!(callExp instanceof PsiCallExpression)) return true;
283               result = ((PsiCall)callExp).resolveMethodGenerics();
284             }
285             else {
286               if (!(element instanceof PsiCall)) return true;
287               PsiCall call = (PsiCall)element;
288               argumentList = call.getArgumentList();
289               result = call.resolveMethodGenerics();
290             }
291           }
292           PsiSubstitutor substitutor = result.getSubstitutor();
293
294           PsiExpression[] expressions = argumentList.getExpressions();
295           if (paramSeqNo >= expressions.length) {
296             return true;
297           }
298           PsiExpression passExpression = expressions[paramSeqNo];
299
300           Project project = argumentList.getProject();
301           PsiElement element = result.getElement();
302           if (element instanceof PsiCompiledElement) {
303             element = element.getNavigationElement();
304           }
305
306           // for erased method calls for which we cannot determine target substitutor,
307           // rely on call argument types. I.e. new Pair(1,2) -> Pair<Integer, Integer>
308           if (element instanceof PsiTypeParameterListOwner && PsiUtil.isRawSubstitutor((PsiTypeParameterListOwner)element, substitutor)) {
309             PsiTypeParameter[] typeParameters = substitutor.getSubstitutionMap().keySet().toArray(new PsiTypeParameter[0]);
310
311             PsiResolveHelper resolveHelper = JavaPsiFacade.getInstance(project).getResolveHelper();
312             substitutor = resolveHelper.inferTypeArguments(typeParameters, actualParameters, expressions, parentSubstitutor, argumentList, false);
313           }
314
315           substitutor = removeRawMappingsLeftFromResolve(substitutor);
316
317           PsiSubstitutor combined = unify(substitutor, parentSubstitutor, project);
318           if (combined == null) return true;
319           PsiType substitited = combined.substitute(passExpression.getType());
320           if (substitited == null || !TypeConversionUtil.areTypesConvertible(substitited, actualType)) return true;
321
322           return handToProcessor(passExpression, processor, parent, combined);
323         }
324       })) {
325         return false;
326       }
327     }
328
329     return true;
330   }
331
332   @NotNull
333   private static PsiSubstitutor removeRawMappingsLeftFromResolve(@NotNull PsiSubstitutor substitutor) {
334     Map<PsiTypeParameter, PsiType> map = null;
335     for (Map.Entry<PsiTypeParameter, PsiType> entry : substitutor.getSubstitutionMap().entrySet()) {
336       if (entry.getValue() == null) {
337         if (map == null) map = new THashMap<PsiTypeParameter, PsiType>();
338         map.put(entry.getKey(), entry.getValue());
339       }
340     }
341     if (map == null) return substitutor;
342     Map<PsiTypeParameter, PsiType> newmap = new THashMap<PsiTypeParameter, PsiType>(substitutor.getSubstitutionMap());
343     newmap.keySet().removeAll(map.keySet());
344     return PsiSubstitutorImpl.createSubstitutor(newmap);
345   }
346
347   @Nullable
348   private static PsiSubstitutor unify(@NotNull PsiSubstitutor substitutor, @NotNull PsiSubstitutor parentSubstitutor, @NotNull Project project) {
349     Map<PsiTypeParameter,PsiType> newMap = new THashMap<PsiTypeParameter, PsiType>(substitutor.getSubstitutionMap());
350
351     for (Map.Entry<PsiTypeParameter, PsiType> entry : substitutor.getSubstitutionMap().entrySet()) {
352       PsiTypeParameter typeParameter = entry.getKey();
353       PsiType type = entry.getValue();
354       PsiClass resolved = PsiUtil.resolveClassInType(type);
355       if (!parentSubstitutor.getSubstitutionMap().containsKey(typeParameter)) continue;
356       PsiType parentType = parentSubstitutor.substitute(parentSubstitutor.substitute(typeParameter));
357
358       if (resolved instanceof PsiTypeParameter) {
359         PsiTypeParameter res = (PsiTypeParameter)resolved;
360         newMap.put(res, parentType);
361       }
362       else if (!Comparing.equal(type, parentType)) {
363         return null; // cannot unify
364       }
365     }
366     return JavaPsiFacade.getElementFactory(project).createSubstitutor(newMap);
367   }
368 }