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