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