restore DataFlowRunner instruction logging and commented printlns
[idea/community.git] / java / java-analysis-impl / src / com / intellij / codeInspection / dataFlow / DataFlowRunner.java
1 /*
2  * Copyright 2000-2015 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.*;
28 import com.intellij.codeInspection.dataFlow.value.DfaValueFactory;
29 import com.intellij.codeInspection.dataFlow.value.DfaVariableValue;
30 import com.intellij.openapi.application.ApplicationManager;
31 import com.intellij.openapi.diagnostic.Logger;
32 import com.intellij.openapi.progress.ProgressManager;
33 import com.intellij.openapi.util.Key;
34 import com.intellij.openapi.util.Pair;
35 import com.intellij.openapi.util.registry.Registry;
36 import com.intellij.psi.*;
37 import com.intellij.psi.templateLanguages.OuterLanguageElement;
38 import com.intellij.psi.util.PsiTreeUtil;
39 import com.intellij.psi.util.PsiUtil;
40 import com.intellij.util.containers.ContainerUtil;
41 import com.intellij.util.containers.MultiMap;
42 import gnu.trove.THashSet;
43 import org.jetbrains.annotations.NotNull;
44 import org.jetbrains.annotations.Nullable;
45
46 import java.util.*;
47
48 public class DataFlowRunner {
49   private static final Logger LOG = Logger.getInstance("#com.intellij.codeInspection.dataFlow.DataFlowRunner");
50   private static final Key<Integer> TOO_EXPENSIVE_HASH = Key.create("TOO_EXPENSIVE_HASH");
51
52   private Instruction[] myInstructions;
53   private final MultiMap<PsiElement, DfaMemoryState> myNestedClosures = new MultiMap<>();
54   @NotNull
55   private final DfaValueFactory myValueFactory;
56   private final boolean myShouldCheckLimitTime;
57   // Maximum allowed attempts to process instruction. Fail as too complex to process if certain instruction
58   // is executed more than this limit times.
59   static final int MAX_STATES_PER_BRANCH = 300;
60
61   protected DataFlowRunner() {
62     this(false, true, false);
63   }
64
65   protected DataFlowRunner(boolean unknownMembersAreNullable, boolean honorFieldInitializers, boolean shouldCheckLimitTime) {
66     myShouldCheckLimitTime = shouldCheckLimitTime;
67     myValueFactory = new DfaValueFactory(honorFieldInitializers, unknownMembersAreNullable);
68   }
69
70   @NotNull
71   public DfaValueFactory getFactory() {
72     return myValueFactory;
73   }
74
75   @Nullable
76   private Collection<DfaMemoryState> createInitialStates(@NotNull PsiElement psiBlock, @NotNull InstructionVisitor visitor) {
77     PsiElement container = PsiTreeUtil.getParentOfType(psiBlock, PsiClass.class, PsiLambdaExpression.class);
78     if (container != null && (!(container instanceof PsiClass) || PsiUtil.isLocalOrAnonymousClass((PsiClass)container))) {
79       final PsiElement parent = container.getParent();
80       final PsiCodeBlock block = DfaPsiUtil.getTopmostBlockInSameClass(parent);
81       if (block != null) {
82         final RunnerResult result = analyzeMethod(block, visitor);
83         if (result == RunnerResult.OK) {
84           final Collection<DfaMemoryState> closureStates = myNestedClosures.get(DfaPsiUtil.getTopmostBlockInSameClass(psiBlock));
85           if (!closureStates.isEmpty()) {
86             return closureStates;
87           }
88         }
89         return null;
90       }
91     }
92
93     return Collections.singletonList(createMemoryState());
94   }
95
96   @NotNull
97   public final RunnerResult analyzeMethod(@NotNull PsiElement psiBlock, @NotNull InstructionVisitor visitor) {
98     Collection<DfaMemoryState> initialStates = createInitialStates(psiBlock, visitor);
99     return initialStates == null ? RunnerResult.NOT_APPLICABLE : analyzeMethod(psiBlock, visitor, false, initialStates);
100   }
101
102   @NotNull
103   final RunnerResult analyzeMethod(@NotNull PsiElement psiBlock,
104                                    @NotNull InstructionVisitor visitor,
105                                    boolean ignoreAssertions,
106                                    @NotNull Collection<DfaMemoryState> initialStates) {
107     if (PsiTreeUtil.findChildOfType(psiBlock, OuterLanguageElement.class) != null) return RunnerResult.NOT_APPLICABLE;
108
109     try {
110       final ControlFlow flow = new ControlFlowAnalyzer(myValueFactory, psiBlock, ignoreAssertions).buildControlFlow();
111       if (flow == null) return RunnerResult.NOT_APPLICABLE;
112       int[] loopNumber = LoopAnalyzer.calcInLoop(flow);
113
114       int endOffset = flow.getInstructionCount();
115       myInstructions = flow.getInstructions();
116       myNestedClosures.clear();
117       
118       Set<Instruction> joinInstructions = ContainerUtil.newHashSet();
119       for (int index = 0; index < myInstructions.length; index++) {
120         Instruction instruction = myInstructions[index];
121         if (instruction instanceof GotoInstruction) {
122           joinInstructions.add(myInstructions[((GotoInstruction)instruction).getOffset()]);
123         } else if (instruction instanceof ConditionalGotoInstruction) {
124           joinInstructions.add(myInstructions[((ConditionalGotoInstruction)instruction).getOffset()]);
125         } else if (instruction instanceof MethodCallInstruction && !((MethodCallInstruction)instruction).getContracts().isEmpty()) {
126           joinInstructions.add(myInstructions[index + 1]);
127         }
128       }
129
130       if (LOG.isTraceEnabled()) {
131         LOG.debug("Analyzing code block: " + psiBlock.getText());
132         for (int i = 0; i < myInstructions.length; i++) {
133           LOG.trace(i + ": " + myInstructions[i]);
134         }
135       }
136
137       Integer tooExpensiveHash = psiBlock.getUserData(TOO_EXPENSIVE_HASH);
138       if (tooExpensiveHash != null && tooExpensiveHash == psiBlock.getText().hashCode()) {
139         LOG.debug("Too complex because hasn't changed since being too complex already");
140         return RunnerResult.TOO_COMPLEX;
141       }
142
143       final StateQueue queue = new StateQueue();
144       for (final DfaMemoryState initialState : initialStates) {
145         queue.offer(new DfaInstructionState(myInstructions[0], initialState));
146       }
147
148       MultiMap<BranchingInstruction, DfaMemoryState> processedStates = MultiMap.createSet();
149       MultiMap<BranchingInstruction, DfaMemoryState> incomingStates = MultiMap.createSet();
150
151       long msLimit = Registry.intValue(shouldCheckTimeLimit() ? "ide.dfa.time.limit.online" : "ide.dfa.time.limit.offline");
152       WorkingTimeMeasurer measurer = new WorkingTimeMeasurer(msLimit * 1000 * 1000);
153       int count = 0;
154       while (!queue.isEmpty()) {
155         List<DfaInstructionState> states = queue.getNextInstructionStates(joinInstructions);
156         for (DfaInstructionState instructionState : states) {
157           if (count++ % 1024 == 0 && measurer.isTimeOver()) {
158             LOG.debug("Too complex because the analysis took too long");
159             psiBlock.putUserData(TOO_EXPENSIVE_HASH, psiBlock.getText().hashCode());
160             return RunnerResult.TOO_COMPLEX;
161           }
162           ProgressManager.checkCanceled();
163
164           if (LOG.isTraceEnabled()) {
165             LOG.trace(instructionState.toString());
166           }
167           // useful for quick debugging by uncommenting and hot-swapping
168           //System.out.println(instructionState.toString());
169
170           Instruction instruction = instructionState.getInstruction();
171
172           if (instruction instanceof BranchingInstruction) {
173             BranchingInstruction branching = (BranchingInstruction)instruction;
174             Collection<DfaMemoryState> processed = processedStates.get(branching);
175             if (processed.contains(instructionState.getMemoryState())) {
176               continue;
177             }
178             if (processed.size() > MAX_STATES_PER_BRANCH) {
179               LOG.debug("Too complex because too many different possible states");
180               return RunnerResult.TOO_COMPLEX; // Too complex :(
181             }
182             if (loopNumber[branching.getIndex()] != 0) {
183               processedStates.putValue(branching, instructionState.getMemoryState().createCopy());
184             }
185           }
186
187           DfaInstructionState[] after = acceptInstruction(visitor, instructionState);
188           for (DfaInstructionState state : after) {
189             Instruction nextInstruction = state.getInstruction();
190             if (nextInstruction.getIndex() >= endOffset) {
191               continue;
192             }
193             handleStepOutOfLoop(instruction, nextInstruction, loopNumber, processedStates, incomingStates, states, after, queue);
194             if (nextInstruction instanceof BranchingInstruction) {
195               BranchingInstruction branching = (BranchingInstruction)nextInstruction;
196               if (processedStates.get(branching).contains(state.getMemoryState()) ||
197                   incomingStates.get(branching).contains(state.getMemoryState())) {
198                 continue;
199               }
200               if (loopNumber[branching.getIndex()] != 0) {
201                 incomingStates.putValue(branching, state.getMemoryState().createCopy());
202               }
203             }
204             queue.offer(state);
205           }
206         }
207       }
208
209       psiBlock.putUserData(TOO_EXPENSIVE_HASH, null);
210       LOG.trace("Analysis ok");
211       return RunnerResult.OK;
212     }
213     catch (ArrayIndexOutOfBoundsException | EmptyStackException e) {
214       LOG.error(psiBlock.getText(), e);
215       return RunnerResult.ABORTED;
216     }
217   }
218
219   private void handleStepOutOfLoop(@NotNull final Instruction prevInstruction,
220                                    @NotNull Instruction nextInstruction,
221                                    @NotNull final int[] loopNumber,
222                                    @NotNull MultiMap<BranchingInstruction, DfaMemoryState> processedStates,
223                                    @NotNull MultiMap<BranchingInstruction, DfaMemoryState> incomingStates,
224                                    @NotNull List<DfaInstructionState> inFlightStates,
225                                    @NotNull DfaInstructionState[] afterStates,
226                                    @NotNull StateQueue queue) {
227     if (loopNumber[prevInstruction.getIndex()] == 0 || inSameLoop(prevInstruction, nextInstruction, loopNumber)) {
228       return;
229     }
230     // stepped out of loop. destroy all memory states from the loop, we don't need them anymore
231
232     // but do not touch yet states being handled right now
233     for (DfaInstructionState state : inFlightStates) {
234       Instruction instruction = state.getInstruction();
235       if (inSameLoop(prevInstruction, instruction, loopNumber)) {
236         return;
237       }
238     }
239     for (DfaInstructionState state : afterStates) {
240       Instruction instruction = state.getInstruction();
241       if (inSameLoop(prevInstruction, instruction, loopNumber)) {
242         return;
243       }
244     }
245     // and still in queue
246     if (!queue.processAll(state -> {
247       Instruction instruction = state.getInstruction();
248       return !inSameLoop(prevInstruction, instruction, loopNumber);
249     })) return;
250
251     // now remove obsolete memory states
252     final Set<BranchingInstruction> mayRemoveStatesFor = new THashSet<>();
253     for (Instruction instruction : myInstructions) {
254       if (inSameLoop(prevInstruction, instruction, loopNumber) && instruction instanceof BranchingInstruction) {
255         mayRemoveStatesFor.add((BranchingInstruction)instruction);
256       }
257     }
258
259     for (Instruction instruction : mayRemoveStatesFor) {
260       processedStates.remove((BranchingInstruction)instruction);
261       incomingStates.remove((BranchingInstruction)instruction);
262     }
263   }
264
265   private static boolean inSameLoop(@NotNull Instruction prevInstruction, @NotNull Instruction nextInstruction, @NotNull int[] loopNumber) {
266     return loopNumber[nextInstruction.getIndex()] == loopNumber[prevInstruction.getIndex()];
267   }
268
269   protected boolean shouldCheckTimeLimit() {
270     return myShouldCheckLimitTime && !ApplicationManager.getApplication().isUnitTestMode();
271   }
272
273   @NotNull
274   protected DfaInstructionState[] acceptInstruction(@NotNull InstructionVisitor visitor, @NotNull DfaInstructionState instructionState) {
275     Instruction instruction = instructionState.getInstruction();
276     PsiElement closure = DfaUtil.getClosureInside(instruction);
277     if (closure instanceof PsiClass) {
278       registerNestedClosures(instructionState, (PsiClass)closure);
279     } else if (closure instanceof PsiLambdaExpression) {
280       registerNestedClosures(instructionState, (PsiLambdaExpression)closure);
281     }
282
283     return instruction.accept(this, instructionState.getMemoryState(), visitor);
284   }
285
286   private void registerNestedClosures(@NotNull DfaInstructionState instructionState, @NotNull PsiClass nestedClass) {
287     DfaMemoryState state = instructionState.getMemoryState();
288     for (PsiMethod method : nestedClass.getMethods()) {
289       PsiCodeBlock body = method.getBody();
290       if (body != null) {
291         myNestedClosures.putValue(body, createClosureState(state));
292       }
293     }
294     for (PsiClassInitializer initializer : nestedClass.getInitializers()) {
295       myNestedClosures.putValue(initializer.getBody(), createClosureState(state));
296     }
297     for (PsiField field : nestedClass.getFields()) {
298       myNestedClosures.putValue(field, createClosureState(state));
299     }
300   }
301   
302   private void registerNestedClosures(@NotNull DfaInstructionState instructionState, @NotNull PsiLambdaExpression expr) {
303     DfaMemoryState state = instructionState.getMemoryState();
304     PsiElement body = expr.getBody();
305     if (body != null) {
306       myNestedClosures.putValue(body, createClosureState(state));
307     }
308   }
309
310   @NotNull
311   protected DfaMemoryState createMemoryState() {
312     return new DfaMemoryStateImpl(myValueFactory);
313   }
314
315   @NotNull
316   public Instruction[] getInstructions() {
317     return myInstructions;
318   }
319
320   @NotNull
321   public Instruction getInstruction(int index) {
322     return myInstructions[index];
323   }
324
325   @NotNull
326   MultiMap<PsiElement, DfaMemoryState> getNestedClosures() {
327     return new MultiMap<>(myNestedClosures);
328   }
329
330   @NotNull
331   public Pair<Set<Instruction>,Set<Instruction>> getConstConditionalExpressions() {
332     Set<Instruction> trueSet = new HashSet<>();
333     Set<Instruction> falseSet = new HashSet<>();
334
335     for (Instruction instruction : myInstructions) {
336       if (instruction instanceof BranchingInstruction) {
337         BranchingInstruction branchingInstruction = (BranchingInstruction)instruction;
338         if (branchingInstruction.getPsiAnchor() != null && branchingInstruction.isConditionConst()) {
339           if (!branchingInstruction.isTrueReachable()) {
340             falseSet.add(branchingInstruction);
341           }
342
343           if (!branchingInstruction.isFalseReachable()) {
344             trueSet.add(branchingInstruction);
345           }
346         }
347       }
348     }
349
350     for (Instruction instruction : myInstructions) {
351       if (instruction instanceof BranchingInstruction) {
352         BranchingInstruction branchingInstruction = (BranchingInstruction)instruction;
353         if (branchingInstruction.isTrueReachable()) {
354           falseSet.remove(branchingInstruction);
355         }
356         if (branchingInstruction.isFalseReachable()) {
357           trueSet.remove(branchingInstruction);
358         }
359       }
360     }
361
362     return Pair.create(trueSet, falseSet);
363   }
364
365   @NotNull
366   private static DfaMemoryStateImpl createClosureState(@NotNull DfaMemoryState memState) {
367     DfaMemoryStateImpl copy = (DfaMemoryStateImpl)memState.createCopy();
368     copy.flushFields();
369     Set<DfaVariableValue> vars = new HashSet<>(copy.getVariableStates().keySet());
370     for (DfaVariableValue value : vars) {
371       copy.flushDependencies(value);
372     }
373     copy.emptyStack();
374     return copy;
375   }
376 }