java/java-impl/src/com/intellij/codeInspection/dataFlow/DfaUtil.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.codeInspection.dataFlow;
  17
  18 import com.intellij.openapi.util.Key;
  19 import com.intellij.openapi.util.MultiValuesMap;
  20 import com.intellij.openapi.util.Ref;
  21 import com.intellij.psi.*;
  22 import com.intellij.psi.search.LocalSearchScope;
  23 import com.intellij.psi.search.searches.ReferencesSearch;
  24 import com.intellij.psi.tree.IElementType;
  25 import com.intellij.psi.util.CachedValue;
  26 import com.intellij.psi.util.CachedValueProvider;
  27 import com.intellij.psi.util.CachedValuesManager;
  28 import com.intellij.psi.util.PsiTreeUtil;
  29 import com.intellij.util.NullableFunction;
  30 import com.intellij.util.containers.ContainerUtil;
  31 import com.intellij.codeInspection.dataFlow.instructions.PushInstruction;
  32 import com.intellij.codeInspection.dataFlow.instructions.AssignInstruction;
  33 import com.intellij.codeInspection.dataFlow.instructions.Instruction;
  34 import com.intellij.codeInspection.dataFlow.value.DfaVariableValue;
  35 import com.intellij.codeInspection.dataFlow.value.DfaValue;
  36 import gnu.trove.THashSet;
  37 import org.jetbrains.annotations.Nullable;
  38 import org.jetbrains.annotations.NotNull;
  39
  40 import java.util.*;
  41
  42 /**
  43  * @author Gregory.Shrago
  44  */
  45 public class DfaUtil {
  46   private static final Key<CachedValue<MultiValuesMap<PsiVariable, PsiExpression>>> DFA_VARIABLE_INFO_KEY = Key.create("DFA_VARIABLE_INFO_KEY");
  47
  48   private DfaUtil() {
  49   }
  50
  51   private static final MultiValuesMap<PsiVariable, PsiExpression> TOO_COMPLEX = new MultiValuesMap<PsiVariable, PsiExpression>();
  52   @Nullable("null means DFA analysis has failed (too complex to analyze)")
  53   public static Collection<PsiExpression> getCachedVariableValues(@Nullable final PsiVariable variable, @Nullable final PsiElement context) {
  54     if (variable == null || context == null) return Collections.emptyList();
  55
  56     CachedValue<MultiValuesMap<PsiVariable, PsiExpression>> cachedValue = context.getUserData(DFA_VARIABLE_INFO_KEY);
  57     if (cachedValue == null) {
  58       final PsiElement codeBlock = getEnclosingCodeBlock(variable, context);
  59       cachedValue = CachedValuesManager.getManager(context.getProject()).createCachedValue(new CachedValueProvider<MultiValuesMap<PsiVariable, PsiExpression>>() {
  60         public Result<MultiValuesMap<PsiVariable, PsiExpression>> compute() {
  61           final MultiValuesMap<PsiVariable, PsiExpression> result;
  62           if (codeBlock == null) {
  63             result = null;
  64           }
  65           else {
  66             final ValuableInstructionVisitor visitor = new ValuableInstructionVisitor(context);
  67             if (new ValuableDataFlowRunner().analyzeMethod(codeBlock, visitor) == RunnerResult.OK) {
  68               result = visitor.myValues;
  69             }
  70             else {
  71               result = TOO_COMPLEX;
  72             }
  73           }
  74           return new Result<MultiValuesMap<PsiVariable, PsiExpression>>(result, codeBlock);
  75         }
  76       }, false);
  77       context.putUserData(DFA_VARIABLE_INFO_KEY, cachedValue);
  78     }
  79     final MultiValuesMap<PsiVariable, PsiExpression> value = cachedValue.getValue();
  80     if (value == TOO_COMPLEX) return null;
  81     final Collection<PsiExpression> expressions = value == null ? null : value.get(variable);
  82     return expressions == null ? Collections.<PsiExpression>emptyList() : expressions;
  83   }
  84
  85   public static enum Nullness {
  86     NOT_NULL,NULL,UNKNOWN
  87   }
  88
  89   @NotNull
  90   public static Nullness checkNullness(@Nullable final PsiVariable variable, @Nullable final PsiElement context) {
  91     if (variable == null || context == null) return Nullness.UNKNOWN;
  92
  93     final PsiElement codeBlock = getEnclosingCodeBlock(variable, context);
  94     if (codeBlock == null) {
  95       return Nullness.UNKNOWN;
  96     }
  97     final ValuableInstructionVisitor visitor = new ValuableInstructionVisitor(context);
  98     RunnerResult result = new ValuableDataFlowRunner().analyzeMethod(codeBlock, visitor);
  99     if (result != RunnerResult.OK) {
 100       return Nullness.UNKNOWN;
 101     }
 102     if (visitor.myNulls.contains(variable) && !visitor.myNotNulls.contains(variable)) return Nullness.NULL;
 103     if (visitor.myNotNulls.contains(variable) && !visitor.myNulls.contains(variable)) return Nullness.NOT_NULL;
 104     return Nullness.UNKNOWN;
 105   }
 106
 107   @Nullable
 108   public static PsiCodeBlock getTopmostBlockInSameClass(@NotNull PsiElement position) {
 109     PsiCodeBlock block = PsiTreeUtil.getParentOfType(position, PsiCodeBlock.class, false, PsiMember.class, PsiFile.class);
 110     if (block == null) {
 111       return null;
 112     }
 113
 114     PsiCodeBlock lastBlock = block;
 115     while (true) {
 116       block = PsiTreeUtil.getParentOfType(block, PsiCodeBlock.class, true, PsiMember.class, PsiFile.class);
 117       if (block == null) {
 118         return lastBlock;
 119       }
 120       lastBlock = block;
 121     }
 122   }
 123
 124   private static PsiElement getEnclosingCodeBlock(final PsiVariable variable, final PsiElement context) {
 125     PsiElement codeBlock;
 126     if (variable instanceof PsiParameter) {
 127       codeBlock = ((PsiParameter)variable).getDeclarationScope();
 128       if (codeBlock instanceof PsiMethod) {
 129         codeBlock = ((PsiMethod)codeBlock).getBody();
 130       }
 131     }
 132     else if (variable instanceof PsiLocalVariable) {
 133       codeBlock = PsiTreeUtil.getParentOfType(variable, PsiCodeBlock.class);
 134     }
 135     else {
 136       codeBlock = PsiTreeUtil.getParentOfType(context, PsiCodeBlock.class);
 137     }
 138     while (codeBlock != null) {
 139       PsiAnonymousClass anon = PsiTreeUtil.getParentOfType(codeBlock, PsiAnonymousClass.class);
 140       if (anon == null) break;
 141       codeBlock = PsiTreeUtil.getParentOfType(anon, PsiCodeBlock.class);
 142     }
 143     return codeBlock;
 144   }
 145
 146   @Nullable("null means DFA analysis has failed (too complex to analyze)")
 147   public static Collection<? extends PsiElement> getPossibleInitializationElements(final PsiElement qualifierExpression) {
 148     if (qualifierExpression instanceof PsiMethodCallExpression) {
 149       return Collections.singletonList(qualifierExpression);
 150     }
 151     else if (qualifierExpression instanceof PsiReferenceExpression) {
 152       final PsiElement targetElement = ((PsiReferenceExpression)qualifierExpression).resolve();
 153       if (targetElement instanceof PsiVariable) {
 154         final Collection<? extends PsiElement> variableValues = getCachedVariableValues((PsiVariable)targetElement, qualifierExpression);
 155         if (variableValues == null) return null;
 156         if (variableValues.isEmpty() && targetElement instanceof PsiField) {
 157           return getVariableAssignmentsInFile((PsiVariable)targetElement, false);
 158         }
 159         return variableValues;
 160       }
 161     }
 162     else if (qualifierExpression instanceof PsiLiteralExpression) {
 163       return Collections.singletonList(qualifierExpression);
 164     }
 165     return Collections.emptyList();
 166   }
 167
 168   @NotNull
 169   public static Collection<PsiExpression> getVariableAssignmentsInFile(final PsiVariable psiVariable, final boolean literalsOnly) {
 170     final Ref<Boolean> modificationRef = Ref.create(Boolean.FALSE);
 171     final List<PsiExpression> list = ContainerUtil.mapNotNull(
 172       ReferencesSearch.search(psiVariable, new LocalSearchScope(new PsiElement[] {psiVariable.getContainingFile()}, null, true)).findAll(),
 173       new NullableFunction<PsiReference, PsiExpression>() {
 174         public PsiExpression fun(final PsiReference psiReference) {
 175           if (modificationRef.get()) return null;
 176           final PsiElement parent = psiReference.getElement().getParent();
 177           if (parent instanceof PsiAssignmentExpression) {
 178             final PsiAssignmentExpression assignmentExpression = (PsiAssignmentExpression)parent;
 179             final IElementType operation = assignmentExpression.getOperationTokenType();
 180             if (assignmentExpression.getLExpression() == psiReference) {
 181               if (JavaTokenType.EQ.equals(operation)) {
 182                 if (!literalsOnly || allOperandsAreLiterals(assignmentExpression.getRExpression())) {
 183                   return assignmentExpression.getRExpression();
 184                 }
 185                 else {
 186                   modificationRef.set(Boolean.TRUE);
 187                 }
 188               }
 189               else if (JavaTokenType.PLUSEQ.equals(operation)) {
 190                 modificationRef.set(Boolean.TRUE);
 191               }
 192             }
 193           }
 194           return null;
 195         }
 196       });
 197     if (modificationRef.get()) return Collections.emptyList();
 198     if (!literalsOnly || allOperandsAreLiterals(psiVariable.getInitializer())) {
 199       ContainerUtil.addIfNotNull(psiVariable.getInitializer(), list);
 200     }
 201     return list;
 202   }
 203
 204   public static boolean allOperandsAreLiterals(@Nullable final PsiExpression expression) {
 205     if (expression == null) return false;
 206     if (expression instanceof PsiLiteralExpression) return true;
 207     if (expression instanceof PsiBinaryExpression) {
 208       final LinkedList<PsiExpression> stack = new LinkedList<PsiExpression>();
 209       stack.add(expression);
 210       while (!stack.isEmpty()) {
 211         final PsiExpression psiExpression = stack.removeFirst();
 212         if (psiExpression instanceof PsiBinaryExpression) {
 213           final PsiBinaryExpression binaryExpression = (PsiBinaryExpression)psiExpression;
 214           stack.addLast(binaryExpression.getLOperand());
 215           final PsiExpression right = binaryExpression.getROperand();
 216           if (right != null) {
 217             stack.addLast(right);
 218           }
 219         }
 220         else if (!(psiExpression instanceof PsiLiteralExpression)) {
 221           return false;
 222         }
 223       }
 224       return true;
 225     }
 226     return false;
 227   }
 228
 229   private static class ValuableInstructionVisitor extends StandardInstructionVisitor {
 230     final MultiValuesMap<PsiVariable, PsiExpression> myValues = new MultiValuesMap<PsiVariable, PsiExpression>(true);
 231     final Set<PsiVariable> myNulls = new THashSet<PsiVariable>();
 232     final Set<PsiVariable> myNotNulls = new THashSet<PsiVariable>();
 233     private final PsiElement myContext;
 234
 235     public ValuableInstructionVisitor(PsiElement context) {
 236       myContext = context;
 237     }
 238
 239     @Override
 240     public DfaInstructionState[] visitPush(PushInstruction instruction, DataFlowRunner runner, DfaMemoryState memState) {
 241       if (myContext == instruction.getPlace()) {
 242         final Map<DfaVariableValue,DfaVariableState> map = ((ValuableDataFlowRunner.MyDfaMemoryState)memState).getVariableStates();
 243         for (Map.Entry<DfaVariableValue, DfaVariableState> entry : map.entrySet()) {
 244           ValuableDataFlowRunner.ValuableDfaVariableState state = (ValuableDataFlowRunner.ValuableDfaVariableState)entry.getValue();
 245           DfaVariableValue variableValue = entry.getKey();
 246           final PsiExpression psiExpression = state.myExpression;
 247           if (psiExpression != null) {
 248             myValues.put(variableValue.getPsiVariable(), psiExpression);
 249           }
 250         }
 251         DfaValue value = instruction.getValue();
 252         if (value instanceof DfaVariableValue) {
 253           if (memState.isNotNull((DfaVariableValue)value)) {
 254             myNotNulls.add(((DfaVariableValue)value).getPsiVariable());
 255           }
 256           if (memState.isNull(value)) {
 257             myNulls.add(((DfaVariableValue)value).getPsiVariable());
 258           }
 259         }
 260       }
 261       return super.visitPush(instruction, runner, memState);
 262     }
 263
 264     @Override
 265     public DfaInstructionState[] visitAssign(AssignInstruction instruction, DataFlowRunner runner, DfaMemoryState memState) {
 266       final Instruction nextInstruction = runner.getInstruction(instruction.getIndex() + 1);
 267
 268       final DfaValue dfaSource = memState.pop();
 269       final DfaValue dfaDest = memState.pop();
 270
 271       if (dfaDest instanceof DfaVariableValue) {
 272         DfaVariableValue var = (DfaVariableValue)dfaDest;
 273         final PsiExpression rightValue = instruction.getRExpression();
 274         final PsiElement parent = rightValue == null ? null : rightValue.getParent();
 275         final IElementType type = parent instanceof PsiAssignmentExpression
 276                                   ? ((PsiAssignmentExpression)parent).getOperationTokenType() : JavaTokenType.EQ;
 277         // store current value - to use in case of '+='
 278         final PsiExpression prevValue = ((ValuableDataFlowRunner.ValuableDfaVariableState)((ValuableDataFlowRunner.MyDfaMemoryState)memState).getVariableState(var)).myExpression;
 279         memState.setVarValue(var, dfaSource);
 280         // state may have been changed so re-retrieve it
 281         final ValuableDataFlowRunner.ValuableDfaVariableState curState = (ValuableDataFlowRunner.ValuableDfaVariableState)((ValuableDataFlowRunner.MyDfaMemoryState)memState).getVariableState(var);
 282         final PsiExpression curValue = curState.myExpression;
 283         final PsiExpression nextValue;
 284         if (type == JavaTokenType.PLUSEQ && prevValue != null) {
 285           PsiExpression tmpExpression;
 286           try {
 287             tmpExpression = JavaPsiFacade.getElementFactory(myContext.getProject())
 288               .createExpressionFromText(prevValue.getText() + "+" + rightValue.getText(), rightValue);
 289           }
 290           catch (Exception e) {
 291             tmpExpression = curValue == null ? rightValue : curValue;
 292           }
 293           nextValue = tmpExpression;
 294         }
 295         else {
 296           nextValue = curValue == null ? rightValue : curValue;
 297         }
 298         curState.myExpression = nextValue;
 299       }
 300       memState.push(dfaDest);
 301       return new DfaInstructionState[]{new DfaInstructionState(nextInstruction, memState)};
 302     }
 303   }
 304 }