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 }