java/java-impl/src/com/intellij/codeInspection/dataFlow/DataFlowRunner.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
  17 /*
  18  * Created by IntelliJ IDEA.
  19  * User: max
  20  * Date: Jan 28, 2002
  21  * Time: 10:16:39 PM
  22  * To change template for new class use
  23  * Code Style | Class Templates options (Tools | IDE Options).
  24  */
  25 package com.intellij.codeInspection.dataFlow;
  26
  27 import com.intellij.codeInspection.dataFlow.instructions.BranchingInstruction;
  28 import com.intellij.codeInspection.dataFlow.instructions.Instruction;
  29 import com.intellij.codeInspection.dataFlow.instructions.MethodCallInstruction;
  30 import com.intellij.codeInspection.dataFlow.value.DfaValueFactory;
  31 import com.intellij.codeInspection.dataFlow.value.DfaVariableValue;
  32 import com.intellij.openapi.application.ApplicationManager;
  33 import com.intellij.openapi.diagnostic.Logger;
  34 import com.intellij.openapi.progress.ProgressManager;
  35 import com.intellij.openapi.util.Pair;
  36 import com.intellij.psi.*;
  37 import gnu.trove.THashSet;
  38 import org.jetbrains.annotations.NotNull;
  39 import org.jetbrains.annotations.Nullable;
  40
  41 import java.util.*;
  42
  43 public class DataFlowRunner {
  44   private static final Logger LOG = Logger.getInstance("#com.intellij.codeInspection.dataFlow.DataFlowRunner");
  45   private static final long ourTimeLimit = 10000;
  46
  47   private Instruction[] myInstructions;
  48   private DfaVariableValue[] myFields;
  49   private final DfaValueFactory myValueFactory = new DfaValueFactory();
  50
  51   // Maximum allowed attempts to process instruction. Fail as too complex to process if certain instruction
  52   // is executed more than this limit times.
  53   public static final int MAX_STATES_PER_BRANCH = 300;
  54
  55   public Instruction getInstruction(int index) {
  56     return myInstructions[index];
  57   }
  58
  59   protected DataFlowRunner() {
  60   }
  61
  62   public DfaValueFactory getFactory() {
  63     return myValueFactory;
  64   }
  65
  66   @Nullable
  67   protected Collection<DfaMemoryState> createInitialStates(@NotNull PsiElement psiBlock, InstructionVisitor visitor) {
  68     if (psiBlock.getParent() instanceof PsiMethod) {
  69       final PsiClass containingClass = ((PsiMethod)psiBlock.getParent()).getContainingClass();
  70       if (containingClass instanceof PsiAnonymousClass) {
  71         final PsiElement newExpression = containingClass.getParent();
  72         final PsiCodeBlock block = DfaUtil.getTopmostBlockInSameClass(newExpression);
  73         if (newExpression instanceof PsiNewExpression && block != null) {
  74           final EnvironmentalInstructionVisitor envVisitor = new EnvironmentalInstructionVisitor(visitor, (PsiNewExpression)newExpression);
  75           final RunnerResult result = analyzeMethod(block, envVisitor);
  76           if (result == RunnerResult.OK) {
  77             final Collection<DfaMemoryState> closureStates = envVisitor.getClosureStates();
  78             if (!closureStates.isEmpty()) {
  79               return closureStates;
  80             }
  81           }
  82           return null;
  83         }
  84       }
  85     }
  86
  87
  88     return Arrays.asList(createMemoryState());
  89   }
  90
  91   public final RunnerResult analyzeMethod(@NotNull PsiElement psiBlock, InstructionVisitor visitor) {
  92     try {
  93       final Collection<DfaMemoryState> initialStates = createInitialStates(psiBlock, visitor);
  94       if (initialStates == null) return RunnerResult.NOT_APPLICABLE;
  95
  96       final ControlFlow flow = createControlFlowAnalyzer().buildControlFlow(psiBlock);
  97       if (flow == null) return RunnerResult.NOT_APPLICABLE;
  98
  99       int endOffset = flow.getInstructionCount();
 100       myInstructions = flow.getInstructions();
 101       myFields = flow.getFields();
 102
 103       if (LOG.isDebugEnabled()) {
 104         for (int i = 0; i < myInstructions.length; i++) {
 105           Instruction instruction = myInstructions[i];
 106           LOG.debug(i + ": " + instruction.toString());
 107         }
 108       }
 109
 110       int branchCount = 0;
 111       for (Instruction instruction : myInstructions) {
 112         if (instruction instanceof BranchingInstruction) branchCount++;
 113       }
 114
 115       if (branchCount > 80) return RunnerResult.TOO_COMPLEX; // Do not even try. Definitely will out of time.
 116
 117       final ArrayList<DfaInstructionState> queue = new ArrayList<DfaInstructionState>();
 118       for (final DfaMemoryState initialState : initialStates) {
 119         queue.add(new DfaInstructionState(myInstructions[0], initialState));
 120       }
 121
 122       long timeLimit = ourTimeLimit;
 123       final boolean unitTestMode = ApplicationManager.getApplication().isUnitTestMode();
 124       final long before = System.currentTimeMillis();
 125       while (!queue.isEmpty()) {
 126         if (!unitTestMode && System.currentTimeMillis() - before > timeLimit) return RunnerResult.TOO_COMPLEX;
 127         ProgressManager.checkCanceled();
 128
 129         DfaInstructionState instructionState = queue.remove(0);
 130         if (LOG.isDebugEnabled()) {
 131           LOG.debug(instructionState.toString());
 132         }
 133
 134         Instruction instruction = instructionState.getInstruction();
 135         long distance = instructionState.getDistanceFromStart();
 136
 137         if (instruction instanceof BranchingInstruction) {
 138           if (!instruction.setMemoryStateProcessed(instructionState.getMemoryState().createCopy())) {
 139             return RunnerResult.TOO_COMPLEX; // Too complex :(
 140           }
 141         }
 142
 143         DfaInstructionState[] after = instruction.accept(this, instructionState.getMemoryState(), visitor);
 144         if (after != null) {
 145           for (DfaInstructionState state : after) {
 146             Instruction nextInstruction = state.getInstruction();
 147             if ((!(nextInstruction instanceof BranchingInstruction) || !nextInstruction.isMemoryStateProcessed(state.getMemoryState())) && instruction.getIndex() < endOffset) {
 148               state.setDistanceFromStart(distance + 1);
 149               queue.add(state);
 150             }
 151           }
 152         }
 153       }
 154
 155       return RunnerResult.OK;
 156     }
 157     catch (ArrayIndexOutOfBoundsException e) {
 158       LOG.error(psiBlock.getText(), e); /* TODO[max] !!! hack (of 18186). Please fix in better times. */
 159       return RunnerResult.ABORTED;
 160     }
 161     catch (EmptyStackException e) /* TODO[max] !!! hack (of 18186). Please fix in better times. */ {
 162       return RunnerResult.ABORTED;
 163     }
 164   }
 165
 166   protected ControlFlowAnalyzer createControlFlowAnalyzer() {
 167     return new ControlFlowAnalyzer(myValueFactory);
 168   }
 169
 170   protected DfaMemoryState createMemoryState() {
 171     return new DfaMemoryStateImpl(myValueFactory);
 172   }
 173
 174   public Instruction[] getInstructions() {
 175     return myInstructions;
 176   }
 177
 178   public DfaVariableValue[] getFields() {
 179     return myFields;
 180   }
 181
 182   public Pair<Set<Instruction>,Set<Instruction>> getConstConditionalExpressions() {
 183     Set<Instruction> trueSet = new HashSet<Instruction>();
 184     Set<Instruction> falseSet = new HashSet<Instruction>();
 185
 186     for (Instruction instruction : myInstructions) {
 187       if (instruction instanceof BranchingInstruction) {
 188         BranchingInstruction branchingInstruction = (BranchingInstruction)instruction;
 189         if (branchingInstruction.getPsiAnchor() != null && branchingInstruction.isConditionConst()) {
 190           if (!branchingInstruction.isTrueReachable()) {
 191             falseSet.add(branchingInstruction);
 192           }
 193
 194           if (!branchingInstruction.isFalseReachable()) {
 195             trueSet.add(branchingInstruction);
 196           }
 197         }
 198       }
 199     }
 200
 201     for (Instruction instruction : myInstructions) {
 202       if (instruction instanceof BranchingInstruction) {
 203         BranchingInstruction branchingInstruction = (BranchingInstruction)instruction;
 204         if (branchingInstruction.isTrueReachable()) {
 205           falseSet.remove(branchingInstruction);
 206         }
 207         if (branchingInstruction.isFalseReachable()) {
 208           trueSet.remove(branchingInstruction);
 209         }
 210       }
 211     }
 212
 213     return Pair.create(trueSet, falseSet);
 214   }
 215
 216   private static class EnvironmentalInstructionVisitor extends DelegatingInstructionVisitor {
 217     private final PsiNewExpression myNewExpression;
 218     private final Set<DfaMemoryState> myClosureStates = new THashSet<DfaMemoryState>();
 219
 220     public EnvironmentalInstructionVisitor(@NotNull InstructionVisitor delegate, @NotNull PsiNewExpression newExpression) {
 221       super(delegate);
 222       myNewExpression = newExpression;
 223     }
 224
 225     @Override
 226     public DfaInstructionState[] visitMethodCall(MethodCallInstruction instruction, DataFlowRunner runner, DfaMemoryState memState) {
 227       if (myNewExpression == instruction.getCallExpression()) {
 228         myClosureStates.add(memState.createCopy());
 229       }
 230       return super.visitMethodCall(instruction, runner, memState);
 231     }
 232
 233     @NotNull
 234     public Collection<DfaMemoryState> getClosureStates() {
 235       return myClosureStates;
 236     }
 237   }
 238 }