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