Cleanup: NotNull/Nullable
[idea/community.git] / java / java-psi-impl / src / com / intellij / psi / controlFlow / ControlFlowUtil.java
1 // Copyright 2000-2018 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license that can be found in the LICENSE file.
2 package com.intellij.psi.controlFlow;
3
4 import com.intellij.codeInsight.ExceptionUtil;
5 import com.intellij.codeInsight.ExpressionUtil;
6 import com.intellij.openapi.diagnostic.Logger;
7 import com.intellij.psi.*;
8 import com.intellij.psi.impl.source.DummyHolder;
9 import com.intellij.psi.util.PsiTreeUtil;
10 import com.intellij.psi.util.PsiUtil;
11 import com.intellij.util.*;
12 import com.intellij.util.containers.IntArrayList;
13 import com.intellij.util.containers.IntStack;
14 import gnu.trove.THashMap;
15 import gnu.trove.THashSet;
16 import gnu.trove.TIntHashSet;
17 import org.jetbrains.annotations.NotNull;
18 import org.jetbrains.annotations.Nullable;
19
20 import java.util.*;
21
22 public class ControlFlowUtil {
23   private static final Logger LOG = Logger.getInstance("#com.intellij.psi.controlFlow.ControlFlowUtil");
24
25   private static class SSAInstructionState implements Cloneable {
26     private final int myWriteCount;
27     private final int myInstructionIdx;
28
29     SSAInstructionState(int writeCount, int instructionIdx) {
30       myWriteCount = writeCount;
31       myInstructionIdx = instructionIdx;
32     }
33
34     public boolean equals(Object o) {
35       if (this == o) return true;
36       if (!(o instanceof SSAInstructionState)) return false;
37
38       final SSAInstructionState ssaInstructionState = (SSAInstructionState)o;
39
40       if (myInstructionIdx != ssaInstructionState.myInstructionIdx) return false;
41       return Math.min(2, myWriteCount) == Math.min(2, ssaInstructionState.myWriteCount);
42     }
43
44     public int hashCode() {
45       int result = Math.min(2, myWriteCount);
46       result = 29 * result + myInstructionIdx;
47       return result;
48     }
49
50     int getWriteCount() {
51       return myWriteCount;
52     }
53
54     int getInstructionIdx() {
55       return myInstructionIdx;
56     }
57   }
58
59   @NotNull
60   public static List<PsiVariable> getSSAVariables(@NotNull ControlFlow flow) {
61     return getSSAVariables(flow, 0, flow.getSize(), false);
62   }
63
64   @NotNull
65   public static List<PsiVariable> getSSAVariables(@NotNull ControlFlow flow, int from, int to,
66                                                   boolean reportVarsIfNonInitializingPathExists) {
67     List<Instruction> instructions = flow.getInstructions();
68     Collection<PsiVariable> writtenVariables = getWrittenVariables(flow, from, to, false);
69     List<PsiVariable> result = new ArrayList<>(1);
70
71     variables:
72     for (PsiVariable psiVariable : writtenVariables) {
73
74       final List<SSAInstructionState> queue = new ArrayList<>();
75       queue.add(new SSAInstructionState(0, from));
76       Set<SSAInstructionState> processedStates = new THashSet<>();
77
78       while (!queue.isEmpty()) {
79         final SSAInstructionState state = queue.remove(0);
80         if (state.getWriteCount() > 1) continue variables;
81         if (!processedStates.contains(state)) {
82           processedStates.add(state);
83           int i = state.getInstructionIdx();
84           if (i < to) {
85             Instruction instruction = instructions.get(i);
86
87             if (instruction instanceof ReturnInstruction) {
88               int[] offsets = ((ReturnInstruction)instruction).getPossibleReturnOffsets();
89               for (int offset : offsets) {
90                 queue.add(new SSAInstructionState(state.getWriteCount(), Math.min(offset, to)));
91               }
92             }
93             else if (instruction instanceof GoToInstruction) {
94               int nextOffset = ((GoToInstruction)instruction).offset;
95               nextOffset = Math.min(nextOffset, to);
96               queue.add(new SSAInstructionState(state.getWriteCount(), nextOffset));
97             }
98             else if (instruction instanceof ThrowToInstruction) {
99               int nextOffset = ((ThrowToInstruction)instruction).offset;
100               nextOffset = Math.min(nextOffset, to);
101               queue.add(new SSAInstructionState(state.getWriteCount(), nextOffset));
102             }
103             else if (instruction instanceof ConditionalGoToInstruction) {
104               int nextOffset = ((ConditionalGoToInstruction)instruction).offset;
105               nextOffset = Math.min(nextOffset, to);
106               queue.add(new SSAInstructionState(state.getWriteCount(), nextOffset));
107               queue.add(new SSAInstructionState(state.getWriteCount(), i + 1));
108             }
109             else if (instruction instanceof ConditionalThrowToInstruction) {
110               int nextOffset = ((ConditionalThrowToInstruction)instruction).offset;
111               nextOffset = Math.min(nextOffset, to);
112               queue.add(new SSAInstructionState(state.getWriteCount(), nextOffset));
113               queue.add(new SSAInstructionState(state.getWriteCount(), i + 1));
114             }
115             else if (instruction instanceof WriteVariableInstruction) {
116               WriteVariableInstruction write = (WriteVariableInstruction)instruction;
117               queue.add(new SSAInstructionState(state.getWriteCount() + (write.variable == psiVariable ? 1 : 0), i + 1));
118             }
119             else if (instruction instanceof ReadVariableInstruction) {
120               ReadVariableInstruction read = (ReadVariableInstruction)instruction;
121               if (read.variable == psiVariable && state.getWriteCount() == 0) continue variables;
122               queue.add(new SSAInstructionState(state.getWriteCount(), i + 1));
123             }
124             else {
125               queue.add(new SSAInstructionState(state.getWriteCount(), i + 1));
126             }
127           }
128           else if (!reportVarsIfNonInitializingPathExists && state.getWriteCount() == 0) continue variables;
129         }
130       }
131
132       result.add(psiVariable);
133     }
134
135     return result;
136   }
137
138   public static boolean needVariableValueAt(@NotNull PsiVariable variable, @NotNull ControlFlow flow, final int offset) {
139     InstructionClientVisitor<Boolean> visitor = new InstructionClientVisitor<Boolean>() {
140       final boolean[] neededBelow = new boolean[flow.getSize() + 1];
141
142       @Override
143       public void procedureEntered(int startOffset, int endOffset) {
144         for (int i = startOffset; i < endOffset; i++) neededBelow[i] = false;
145       }
146
147       @Override
148       public void visitReadVariableInstruction(ReadVariableInstruction instruction, int offset, int nextOffset) {
149         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
150         boolean needed = neededBelow[nextOffset];
151         if (instruction.variable.equals(variable)) {
152           needed = true;
153         }
154         neededBelow[offset] |= needed;
155       }
156
157       @Override
158       public void visitWriteVariableInstruction(WriteVariableInstruction instruction, int offset, int nextOffset) {
159         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
160         boolean needed = neededBelow[nextOffset];
161         if (instruction.variable.equals(variable)) {
162           needed = false;
163         }
164         neededBelow[offset] = needed;
165       }
166
167       @Override
168       public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
169         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
170         boolean needed = neededBelow[nextOffset];
171         neededBelow[offset] |= needed;
172       }
173
174       @Override
175       public Boolean getResult() {
176         return neededBelow[offset];
177       }
178     };
179     depthFirstSearch(flow, visitor, offset, flow.getSize());
180     return visitor.getResult().booleanValue();
181   }
182
183   @NotNull
184   public static Collection<PsiVariable> getWrittenVariables(@NotNull ControlFlow flow, int start, int end, final boolean ignoreNotReachingWrites) {
185     Set<PsiVariable> set = new HashSet<>();
186     getWrittenVariables(flow, start, end, ignoreNotReachingWrites, set);
187     return set;
188   }
189
190   public static void getWrittenVariables(@NotNull ControlFlow flow,
191                                          int start,
192                                          int end,
193                                          final boolean ignoreNotReachingWrites,
194                                          @NotNull Collection<? super PsiVariable> set) {
195     List<Instruction> instructions = flow.getInstructions();
196     for (int i = start; i < end; i++) {
197       Instruction instruction = instructions.get(i);
198       if (instruction instanceof WriteVariableInstruction && (!ignoreNotReachingWrites || isInstructionReachable(flow, end, i))) {
199         set.add(((WriteVariableInstruction)instruction).variable);
200       }
201     }
202   }
203
204   @NotNull
205   public static List<PsiVariable> getUsedVariables(@NotNull ControlFlow flow, int start, int end) {
206     List<PsiVariable> array = new ArrayList<>();
207     if (start < 0) return array;
208     List<Instruction> instructions = flow.getInstructions();
209     for (int i = start; i < end; i++) {
210       Instruction instruction = instructions.get(i);
211       if (instruction instanceof ReadVariableInstruction) {
212         PsiVariable variable = ((ReadVariableInstruction)instruction).variable;
213         if (!array.contains(variable)) {
214           array.add(variable);
215         }
216       }
217       else if (instruction instanceof WriteVariableInstruction) {
218         PsiVariable variable = ((WriteVariableInstruction)instruction).variable;
219         if (!array.contains(variable)) {
220           array.add(variable);
221         }
222       }
223     }
224     return array;
225   }
226                                  
227   public static boolean isVariableUsed(@NotNull ControlFlow flow, int start, int end, @NotNull PsiVariable variable) {
228     List<Instruction> instructions = flow.getInstructions();
229     LOG.assertTrue(start >= 0, "flow start");
230     LOG.assertTrue(end <= instructions.size(), "flow end");
231     for (int i = start; i < end; i++) {
232       Instruction instruction = instructions.get(i);
233       if (instruction instanceof ReadVariableInstruction) {
234         if (((ReadVariableInstruction)instruction).variable == variable) {
235           return true;
236         }
237       }
238       else if (instruction instanceof WriteVariableInstruction) {
239         if (((WriteVariableInstruction)instruction).variable == variable) {
240           return true;
241         }
242       }
243     }
244     return false;
245   }
246
247   private static int findSingleReadOffset(@NotNull ControlFlow flow, int startOffset, int endOffset, @NotNull PsiVariable variable) {
248     List<Instruction> instructions = flow.getInstructions();
249     if (startOffset < 0 || endOffset < 0 || endOffset > instructions.size()) return -1;
250
251     int readOffset = -1;
252     for (int i = startOffset; i < endOffset; i++) {
253       Instruction instruction = instructions.get(i);
254       if (instruction instanceof ReadVariableInstruction) {
255         if (((ReadVariableInstruction)instruction).variable == variable) {
256           if (readOffset < 0) {
257             readOffset = i;
258           }
259           else {
260             return -1;
261           }
262         }
263       }
264       else if (instruction instanceof WriteVariableInstruction) {
265         if (((WriteVariableInstruction)instruction).variable == variable) {
266           return -1;
267         }
268       }
269     }
270     return readOffset;
271   }
272
273   /**
274    * If the variable occurs only once in the element and it's read access return that occurrence
275    */
276   public static PsiReferenceExpression findSingleReadOccurrence(@NotNull ControlFlow flow,
277                                                                 @NotNull PsiElement element,
278                                                                 @NotNull PsiVariable variable) {
279     int readOffset = findSingleReadOffset(flow, flow.getStartOffset(element), flow.getEndOffset(element), variable);
280     if (readOffset >= 0) {
281       PsiElement readElement = flow.getElement(readOffset);
282       readElement = PsiTreeUtil.findFirstParent(readElement, false, e -> e == element || e instanceof PsiReferenceExpression);
283       if (readElement instanceof PsiReferenceExpression) {
284         return (PsiReferenceExpression)readElement;
285       }
286     }
287     return null;
288   }
289
290   public static boolean isVariableReadInFinally(@NotNull ControlFlow flow,
291                                                 @Nullable PsiElement startElement,
292                                                 @NotNull PsiElement enclosingCodeFragment,
293                                                 @NotNull PsiVariable variable) {
294     for (PsiElement element = startElement; element != null && element != enclosingCodeFragment; element = element.getParent()) {
295       if (element instanceof PsiCodeBlock) {
296         final PsiElement parent = element.getParent();
297         if (parent instanceof PsiTryStatement) {
298           final PsiTryStatement tryStatement = (PsiTryStatement)parent;
299           if (tryStatement.getTryBlock() == element) {
300             final PsiCodeBlock finallyBlock = tryStatement.getFinallyBlock();
301             if (finallyBlock != null) {
302               final List<Instruction> instructions = flow.getInstructions();
303               final int startOffset = flow.getStartOffset(finallyBlock);
304               final int endOffset = flow.getEndOffset(finallyBlock);
305               LOG.assertTrue(startOffset >= 0, "flow start");
306               LOG.assertTrue(endOffset <= instructions.size(), "flow end");
307               for (int i = startOffset; i < endOffset; i++) {
308                 final Instruction instruction = instructions.get(i);
309                 if (instruction instanceof ReadVariableInstruction && ((ReadVariableInstruction)instruction).variable == variable) {
310                   return true;
311                 }
312               }
313             }
314           }
315         }
316       }
317     }
318     return false;
319   }
320
321   @NotNull
322   public static List<PsiVariable> getInputVariables(@NotNull ControlFlow flow, int start, int end) {
323     List<PsiVariable> usedVariables = getUsedVariables(flow, start, end);
324     List<PsiVariable> array = new ArrayList<>(usedVariables.size());
325     for (PsiVariable variable : usedVariables) {
326       if (needVariableValueAt(variable, flow, start)) {
327         array.add(variable);
328       }
329     }
330     return array;
331   }
332
333   @NotNull
334   public static PsiVariable[] getOutputVariables(@NotNull ControlFlow flow, int start, int end, @NotNull int[] exitPoints) {
335     Collection<PsiVariable> writtenVariables = getWrittenVariables(flow, start, end, false);
336     List<PsiVariable> array = new ArrayList<>();
337     for (PsiVariable variable : writtenVariables) {
338       for (int exitPoint : exitPoints) {
339         if (needVariableValueAt(variable, flow, exitPoint)) {
340           array.add(variable);
341         }
342       }
343     }
344     PsiVariable[] outputVariables = array.toArray(new PsiVariable[0]);
345     if (LOG.isDebugEnabled()) {
346       LOG.debug("output variables:");
347       for (PsiVariable variable : outputVariables) {
348         LOG.debug("  " + variable);
349       }
350     }
351     return outputVariables;
352   }
353
354   @NotNull
355   public static Collection<PsiStatement> findExitPointsAndStatements(@NotNull ControlFlow flow, final int start, final int end,
356                                                                      @NotNull IntArrayList exitPoints,
357                                                                      @NotNull Class<? extends PsiStatement>... classesFilter) {
358     if (end == start) {
359       exitPoints.add(end);
360       return Collections.emptyList();
361     }
362     final Collection<PsiStatement> exitStatements = new THashSet<>();
363     InstructionClientVisitor visitor = new InstructionClientVisitor() {
364       @Override
365       public void visitThrowToInstruction(ThrowToInstruction instruction, int offset, int nextOffset) {
366         //[ven]This is a hack since Extract Method doesn't want to see throw's exit points
367         processGotoStatement(exitStatements, findStatement(flow, offset), classesFilter);
368       }
369
370       @Override
371       public void visitBranchingInstruction(BranchingInstruction instruction, int offset, int nextOffset) {
372         processGoto(flow, start, end, exitPoints, exitStatements, instruction, findStatement(flow, offset), classesFilter);
373       }
374
375       // call/return do not incur exit points
376       @Override
377       public void visitReturnInstruction(ReturnInstruction instruction, int offset, int nextOffset) {
378       }
379
380       @Override
381       public void visitCallInstruction(CallInstruction instruction, int offset, int nextOffset) {
382       }
383
384       @Override
385       public void visitConditionalThrowToInstruction(ConditionalThrowToInstruction instruction, int offset, int nextOffset) {
386         visitInstruction(instruction, offset, nextOffset);
387       }
388
389       @Override
390       public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
391         if (offset >= end - 1) {
392           int exitOffset = end;
393           exitOffset = promoteThroughGotoChain(flow, exitOffset);
394           if (!exitPoints.contains(exitOffset)) {
395             exitPoints.add(exitOffset);
396           }
397         }
398       }
399
400       @Override
401       public Object getResult() {
402         return null;
403       }
404     };
405     depthFirstSearch(flow, visitor, start, end);
406     return exitStatements;
407   }
408
409   private static void processGoto(@NotNull ControlFlow flow, int start, int end,
410                                   @NotNull IntArrayList exitPoints,
411                                   @NotNull Collection<? super PsiStatement> exitStatements,
412                                   @NotNull BranchingInstruction instruction,
413                                   final PsiStatement statement, @NotNull Class... classesFilter) {
414     if (statement == null) return;
415     int gotoOffset = instruction.offset;
416     if (start > gotoOffset || gotoOffset >= end || isElementOfClass(statement, classesFilter)) {
417       // process chain of goto's
418       gotoOffset = promoteThroughGotoChain(flow, gotoOffset);
419
420       if (gotoOffset > 0 && (gotoOffset >= end || gotoOffset < start) && !exitPoints.contains(gotoOffset)) {
421         exitPoints.add(gotoOffset);
422       }
423       if (gotoOffset >= end || gotoOffset < start) {
424         processGotoStatement(exitStatements, statement, classesFilter);
425       }
426       else {
427         boolean isReturn = instruction instanceof GoToInstruction && ((GoToInstruction)instruction).isReturn;
428         final Instruction gotoInstruction = flow.getInstructions().get(gotoOffset);
429         isReturn |= gotoInstruction instanceof GoToInstruction && ((GoToInstruction)gotoInstruction).isReturn;
430         if (isReturn) {
431           processGotoStatement(exitStatements, statement, classesFilter);
432         }
433       }
434     }
435   }
436
437   private static void processGotoStatement(@NotNull Collection<? super PsiStatement> exitStatements,
438                                            PsiStatement statement, @NotNull Class... classesFilter) {
439     if (statement != null && isElementOfClass(statement, classesFilter)) {
440       exitStatements.add(statement);
441     }
442   }
443
444   private static boolean isElementOfClass(@NotNull PsiElement element, @NotNull Class... classesFilter) {
445     for (Class aClassesFilter : classesFilter) {
446       if (ReflectionUtil.isAssignable(aClassesFilter, element.getClass())) {
447         return true;
448       }
449     }
450     return false;
451   }
452
453   private static int promoteThroughGotoChain(@NotNull ControlFlow flow, int offset) {
454     List<Instruction> instructions = flow.getInstructions();
455     while (true) {
456       if (offset >= instructions.size()) break;
457       Instruction instruction = instructions.get(offset);
458       if (!(instruction instanceof GoToInstruction) || ((GoToInstruction)instruction).isReturn) break;
459       offset = ((BranchingInstruction)instruction).offset;
460     }
461     return offset;
462   }
463
464   @SuppressWarnings("unchecked")
465   public static final Class<? extends PsiStatement>[] DEFAULT_EXIT_STATEMENTS_CLASSES =
466     new Class[]{PsiReturnStatement.class, PsiBreakStatement.class, PsiContinueStatement.class};
467
468   private static PsiStatement findStatement(@NotNull ControlFlow flow, int offset) {
469     PsiElement element = flow.getElement(offset);
470     return PsiTreeUtil.getParentOfType(element, PsiStatement.class, false);
471   }
472
473   /**
474    * Detect throw instructions which might affect observable control flow via side effects with local variables.
475    *
476    * The side effect of exception thrown occurs when a local variable is written in the try block, and then accessed
477    * in the finally section or in/after a catch section.
478    *
479    * Example:
480    * <pre>
481    * { // --- start of theOuterBlock ---
482    *   Status status = STARTED;
483    *   try { // --- start of theTryBlock ---
484    *     status = PREPARING;
485    *     doPrepare(); // may throw exception
486    *     status = WORKING;
487    *     doWork(); // may throw exception
488    *     status = FINISHED;
489    *   } // --- end of theTryBlock ---
490    *   catch (Exception e) {
491    *      LOG.error("Failed when " + status, e); // can get PREPARING or WORKING here
492    *   }
493    *   if (status == FINISHED) LOG.info("Finished"); // can get PREPARING or WORKING here in the case of exception
494    * } // --- end of theOuterBlock ---
495    * </pre>
496    * In the example above {@code hasObservableThrowExitPoints(theTryBlock) == true},
497    * because the resulting value of the "status" variable depends on the exceptions being thrown.
498    * In the same example {@code hasObservableThrowExitPoints(theOuterBlock) == false},
499    * because no outgoing variables here depend on the exceptions being thrown.
500    */
501   public static boolean hasObservableThrowExitPoints(@NotNull final ControlFlow flow,
502                                                      final int flowStart,
503                                                      final int flowEnd,
504                                                      @NotNull PsiElement[] elements,
505                                                      @NotNull PsiElement enclosingCodeFragment) {
506     final List<Instruction> instructions = flow.getInstructions();
507     class Worker {
508       @NotNull
509       private Map<PsiVariable, IntArrayList> getWritesOffsets() {
510         final Map<PsiVariable, IntArrayList> writeOffsets = new THashMap<>();
511         for (int i = flowStart; i < flowEnd; i++) {
512           Instruction instruction = instructions.get(i);
513           if (instruction instanceof WriteVariableInstruction) {
514             final PsiVariable variable = ((WriteVariableInstruction)instruction).variable;
515             if (variable instanceof PsiLocalVariable || variable instanceof PsiParameter) {
516               IntArrayList offsets = writeOffsets.get(variable);
517               if (offsets == null) writeOffsets.put(variable, offsets = new IntArrayList());
518               offsets.add(i);
519             }
520           }
521         }
522         LOG.debug("writeOffsets:", writeOffsets);
523         return writeOffsets;
524       }
525
526       @NotNull
527       private Map<PsiVariable, IntArrayList> getVisibleReadsOffsets(@NotNull Map<PsiVariable, IntArrayList> writeOffsets, @NotNull PsiCodeBlock tryBlock) {
528         final Map<PsiVariable, IntArrayList> visibleReadOffsets = new THashMap<>();
529         for (PsiVariable variable : writeOffsets.keySet()) {
530           if (!PsiTreeUtil.isAncestor(tryBlock, variable, true)) {
531             visibleReadOffsets.put(variable, new IntArrayList());
532           }
533         }
534         if (visibleReadOffsets.isEmpty()) return visibleReadOffsets;
535
536         for (int i = 0; i < instructions.size(); i++) {
537           final Instruction instruction = instructions.get(i);
538           if (instruction instanceof ReadVariableInstruction) {
539             final PsiVariable variable = ((ReadVariableInstruction)instruction).variable;
540             final IntArrayList readOffsets = visibleReadOffsets.get(variable);
541             if (readOffsets != null) {
542               readOffsets.add(i);
543             }
544           }
545         }
546         LOG.debug("visibleReadOffsets:", visibleReadOffsets);
547         return visibleReadOffsets;
548       }
549
550       @NotNull
551       private Map<PsiVariable, Set<PsiElement>> getReachableAfterWrite(@NotNull Map<PsiVariable, IntArrayList> writeOffsets,
552                                                                        @NotNull Map<PsiVariable, IntArrayList> visibleReadOffsets) {
553         final Map<PsiVariable, Set<PsiElement>> afterWrite = new THashMap<>();
554         for (PsiVariable variable : visibleReadOffsets.keySet()) {
555           final Function<Integer, BitSet> calculator = getReachableInstructionsCalculator();
556           final BitSet collectedOffsets = new BitSet(flowEnd);
557           for (final int writeOffset : writeOffsets.get(variable).toArray()) {
558             LOG.assertTrue(writeOffset >= flowStart, "writeOffset");
559             final BitSet reachableOffsets = calculator.fun(writeOffset);
560             collectedOffsets.or(reachableOffsets);
561           }
562           Set<PsiElement> throwSources = afterWrite.get(variable);
563           if (throwSources == null) afterWrite.put(variable, throwSources = new THashSet<>());
564           for (int i = flowStart; i < flowEnd; i++) {
565             if (collectedOffsets.get(i)) {
566               throwSources.add(flow.getElement(i));
567             }
568           }
569           final List<PsiElement> subordinates = new ArrayList<>();
570           for (PsiElement element : throwSources) {
571             if (throwSources.contains(element.getParent())) {
572               subordinates.add(element);
573             }
574           }
575           throwSources.removeAll(subordinates);
576         }
577         LOG.debug("afterWrite:", afterWrite);
578         return afterWrite;
579       }
580
581       @NotNull
582       private IntArrayList getCatchOrFinallyOffsets(@NotNull List<? extends PsiTryStatement> tryStatements, @NotNull List<? extends PsiClassType> thrownExceptions) {
583         final IntArrayList catchOrFinallyOffsets = new IntArrayList();
584         for (PsiTryStatement tryStatement : tryStatements) {
585           final PsiCodeBlock finallyBlock = tryStatement.getFinallyBlock();
586           if (finallyBlock != null) {
587             int offset = flow.getStartOffset(finallyBlock);
588             if (offset >= 0) {
589               catchOrFinallyOffsets.add(offset - 2); // -2 is an adjustment for rethrow-after-finally
590             }
591           }
592           for (PsiCatchSection catchSection : tryStatement.getCatchSections()) {
593             final PsiCodeBlock catchBlock = catchSection.getCatchBlock();
594             final PsiParameter parameter = catchSection.getParameter();
595             if (catchBlock != null && parameter != null) {
596               for (PsiClassType throwType : thrownExceptions) {
597                 if (isCaughtExceptionType(throwType, parameter.getType())) {
598                   int offset = flow.getStartOffset(catchBlock);
599                   if (offset >= 0) {
600                     catchOrFinallyOffsets.add(offset - 1); // -1 is an adjustment for catch block initialization
601                   }
602                 }
603               }
604             }
605           }
606         }
607         return catchOrFinallyOffsets;
608       }
609
610       private boolean isAnyReadOffsetReachableFrom(@Nullable IntArrayList readOffsets, @NotNull IntArrayList fromOffsets) {
611         if (readOffsets != null && !readOffsets.isEmpty()) {
612           final int[] readOffsetsArray = readOffsets.toArray();
613           for (int j = 0; j < fromOffsets.size(); j++) {
614             int fromOffset = fromOffsets.get(j);
615             if (areInstructionsReachable(flow, readOffsetsArray, fromOffset)) {
616               LOG.debug("reachableFromOffset:", fromOffset);
617               return true;
618             }
619           }
620         }
621         return false;
622       }
623
624       @NotNull
625       private Function<Integer, BitSet> getReachableInstructionsCalculator() {
626         final ControlFlowGraph graph = new ControlFlowGraph(flow.getSize()) {
627           @Override
628           void addArc(int offset, int nextOffset) {
629             nextOffset = promoteThroughGotoChain(flow, nextOffset);
630             if (nextOffset >= flowStart && nextOffset < flowEnd) {
631               super.addArc(offset, nextOffset);
632             }
633           }
634         };
635         graph.buildFrom(flow);
636
637         return startOffset -> {
638           BitSet visitedOffsets = new BitSet(flowEnd);
639           graph.depthFirstSearch(startOffset, visitedOffsets);
640           return visitedOffsets;
641         };
642       }
643     }
644
645     final Worker worker = new Worker();
646     final Map<PsiVariable, IntArrayList> writeOffsets = worker.getWritesOffsets();
647     if (writeOffsets.isEmpty()) return false;
648
649     final PsiElement commonParent = elements.length != 1 ? PsiTreeUtil.findCommonParent(elements) : elements[0].getParent();
650     final List<PsiTryStatement> tryStatements = collectTryStatementStack(commonParent, enclosingCodeFragment);
651     if (tryStatements.isEmpty()) return false;
652     final PsiCodeBlock tryBlock = tryStatements.get(0).getTryBlock();
653     if (tryBlock == null) return false;
654
655     final Map<PsiVariable, IntArrayList> visibleReadOffsets = worker.getVisibleReadsOffsets(writeOffsets, tryBlock);
656     if (visibleReadOffsets.isEmpty()) return false;
657
658     final Map<PsiVariable, Set<PsiElement>> afterWrite = worker.getReachableAfterWrite(writeOffsets, visibleReadOffsets);
659     if (afterWrite.isEmpty()) return false;
660
661     for (Map.Entry<PsiVariable, Set<PsiElement>> entry : afterWrite.entrySet()) {
662       final PsiVariable variable = entry.getKey();
663       final PsiElement[] psiElements = entry.getValue().toArray(PsiElement.EMPTY_ARRAY);
664       final List<PsiClassType> thrownExceptions = ExceptionUtil.getThrownExceptions(psiElements);
665
666       if (!thrownExceptions.isEmpty()) {
667         final IntArrayList catchOrFinallyOffsets = worker.getCatchOrFinallyOffsets(tryStatements, thrownExceptions);
668         if (worker.isAnyReadOffsetReachableFrom(visibleReadOffsets.get(variable), catchOrFinallyOffsets)) {
669           return true;
670         }
671       }
672     }
673     return false;
674   }
675
676   @Nullable
677   private static PsiTryStatement getEnclosingTryStatementHavingCatchOrFinally(@Nullable PsiElement startElement,
678                                                                               @NotNull PsiElement enclosingCodeFragment) {
679     for (PsiElement element = startElement; element != null && element != enclosingCodeFragment; element = element.getParent()) {
680       if (element instanceof PsiCodeBlock) {
681         final PsiElement parent = element.getParent();
682         if (parent instanceof PsiTryStatement) {
683           final PsiTryStatement tryStatement = (PsiTryStatement)parent;
684           if (tryStatement.getTryBlock() == element &&
685               (tryStatement.getFinallyBlock() != null || tryStatement.getCatchBlocks().length != 0)) {
686             return tryStatement;
687           }
688         }
689       }
690     }
691     return null;
692   }
693
694   @NotNull
695   private static List<PsiTryStatement> collectTryStatementStack(@Nullable PsiElement startElement,
696                                                                 @NotNull PsiElement enclosingCodeFragment) {
697     final List<PsiTryStatement> stack = new ArrayList<>();
698     for (PsiTryStatement tryStatement = getEnclosingTryStatementHavingCatchOrFinally(startElement, enclosingCodeFragment);
699          tryStatement != null;
700          tryStatement = getEnclosingTryStatementHavingCatchOrFinally(tryStatement, enclosingCodeFragment)) {
701       stack.add(tryStatement);
702     }
703     return stack;
704   }
705
706   @NotNull
707   public static PsiElement findCodeFragment(@NotNull PsiElement element) {
708     PsiElement codeFragment = element;
709     PsiElement parent = codeFragment.getParent();
710     while (parent != null) {
711       if (parent instanceof PsiDirectory
712           || parent instanceof PsiMethod
713           || parent instanceof PsiField || parent instanceof PsiClassInitializer
714           || parent instanceof DummyHolder
715           || parent instanceof PsiLambdaExpression) {
716         break;
717       }
718       codeFragment = parent;
719       parent = parent.getParent();
720     }
721     return codeFragment;
722   }
723
724   private static boolean checkReferenceExpressionScope(@NotNull PsiReferenceExpression ref, @NotNull PsiElement targetClassMember) {
725     final JavaResolveResult resolveResult = ref.advancedResolve(false);
726     final PsiElement def = resolveResult.getElement();
727     if (def != null) {
728       PsiElement parent = def.getParent();
729       PsiElement commonParent = parent == null ? null : PsiTreeUtil.findCommonParent(parent, targetClassMember);
730       if (commonParent == null) {
731         parent = resolveResult.getCurrentFileResolveScope();
732       }
733       if (parent instanceof PsiClass) {
734         final PsiClass clss = (PsiClass)parent;
735         if (PsiTreeUtil.isAncestor(targetClassMember, clss, false)) return false;
736         PsiClass containingClass = PsiTreeUtil.getParentOfType(ref, PsiClass.class);
737         while (containingClass != null) {
738           if (containingClass.isInheritor(clss, true) &&
739               PsiTreeUtil.isAncestor(targetClassMember, containingClass, false)) {
740             return false;
741           }
742           containingClass = containingClass.getContainingClass();
743         }
744       }
745     }
746
747     return true;
748   }
749
750   /**
751    * Checks possibility of extracting code fragment outside containing anonymous (local) class.
752    * Also collects variables to be passed as additional parameters.
753    *
754    * @param array             Vector to collect variables to be passed as additional parameters
755    * @param scope             scope to be scanned (part of code fragment to be extracted)
756    * @param member            member containing the code to be extracted
757    * @param targetClassMember member in target class containing code fragment
758    * @return true if code fragment can be extracted outside
759    */
760   public static boolean collectOuterLocals(@NotNull List<? super PsiVariable> array, @NotNull PsiElement scope, @NotNull PsiElement member,
761                                            @NotNull PsiElement targetClassMember) {
762     if (scope instanceof PsiMethodCallExpression) {
763       final PsiMethodCallExpression call = (PsiMethodCallExpression)scope;
764       if (!checkReferenceExpressionScope(call.getMethodExpression(), targetClassMember)) {
765         return false;
766       }
767     }
768     else if (scope instanceof PsiReferenceExpression) {
769       if (!checkReferenceExpressionScope((PsiReferenceExpression)scope, targetClassMember)) {
770         return false;
771       }
772     }
773
774     if (scope instanceof PsiJavaCodeReferenceElement) {
775
776       final PsiJavaCodeReferenceElement ref = (PsiJavaCodeReferenceElement)scope;
777       final JavaResolveResult result = ref.advancedResolve(false);
778       final PsiElement refElement = result.getElement();
779
780       if (refElement != null) {
781
782         PsiElement parent = refElement.getParent();
783         parent = parent != null ? PsiTreeUtil.findCommonParent(parent, member) : null;
784         if (parent == null) {
785           parent = result.getCurrentFileResolveScope();
786         }
787
788         if (parent != null && !member.equals(parent)) { // not local in member
789           parent = PsiTreeUtil.findCommonParent(parent, targetClassMember);
790           if (targetClassMember.equals(parent)) { //something in anonymous class
791             if (refElement instanceof PsiVariable) {
792               if (scope instanceof PsiReferenceExpression &&
793                   PsiUtil.isAccessedForWriting((PsiReferenceExpression)scope)) {
794                 return false;
795               }
796               PsiVariable variable = (PsiVariable)refElement;
797               if (!array.contains(variable)) {
798                 array.add(variable);
799               }
800             }
801             else {
802               return false;
803             }
804           }
805         }
806       }
807     }
808     else if (scope instanceof PsiThisExpression) {
809       PsiJavaCodeReferenceElement qualifier = ((PsiThisExpression)scope).getQualifier();
810       if (qualifier == null) {
811         return false;
812       }
813     }
814     else if (scope instanceof PsiSuperExpression) {
815       if (((PsiSuperExpression)scope).getQualifier() == null) {
816         return false;
817       }
818     }
819
820     for (PsiElement child = scope.getFirstChild(); child != null; child = child.getNextSibling()) {
821       if (!collectOuterLocals(array, child, member, targetClassMember)) return false;
822     }
823     return true;
824   }
825
826
827   /**
828    * @return true if each control flow path results in return statement or exception thrown
829    */
830   public static boolean returnPresent(@NotNull ControlFlow flow) {
831     InstructionClientVisitor<Boolean> visitor = new ReturnPresentClientVisitor(flow);
832
833     depthFirstSearch(flow, visitor);
834     return visitor.getResult().booleanValue();
835   }
836
837   public static boolean processReturns(@NotNull ControlFlow flow, @NotNull ReturnStatementsVisitor afterVisitor) throws IncorrectOperationException {
838     final ConvertReturnClientVisitor instructionsVisitor = new ConvertReturnClientVisitor(flow, afterVisitor);
839
840     depthFirstSearch(flow, instructionsVisitor);
841
842     instructionsVisitor.afterProcessing();
843     return instructionsVisitor.getResult().booleanValue();
844   }
845
846   private static class ConvertReturnClientVisitor extends ReturnPresentClientVisitor {
847     private final List<PsiReturnStatement> myAffectedReturns;
848     private final ReturnStatementsVisitor myVisitor;
849
850     ConvertReturnClientVisitor(@NotNull ControlFlow flow, @NotNull ReturnStatementsVisitor visitor) {
851       super(flow);
852       myAffectedReturns = new ArrayList<>();
853       myVisitor = visitor;
854     }
855
856     @Override
857     public void visitGoToInstruction(final GoToInstruction instruction, final int offset, final int nextOffset) {
858       super.visitGoToInstruction(instruction, offset, nextOffset);
859
860       if (instruction.isReturn) {
861         final PsiElement element = myFlow.getElement(offset);
862         if (element instanceof PsiReturnStatement) {
863           final PsiReturnStatement returnStatement = (PsiReturnStatement)element;
864           myAffectedReturns.add(returnStatement);
865         }
866       }
867     }
868
869     void afterProcessing() throws IncorrectOperationException {
870       myVisitor.visit(myAffectedReturns);
871     }
872   }
873
874   private static class ReturnPresentClientVisitor extends InstructionClientVisitor<Boolean> {
875     // false if control flow at this offset terminates either by return called or exception thrown
876     private final boolean[] isNormalCompletion;
877     protected final ControlFlow myFlow;
878
879     ReturnPresentClientVisitor(@NotNull ControlFlow flow) {
880       myFlow = flow;
881       isNormalCompletion = new boolean[myFlow.getSize() + 1];
882       isNormalCompletion[myFlow.getSize()] = true;
883     }
884
885     @Override
886     public void visitConditionalThrowToInstruction(ConditionalThrowToInstruction instruction, int offset, int nextOffset) {
887       if (nextOffset > myFlow.getSize()) nextOffset = myFlow.getSize();
888       boolean isNormal = instruction.offset == nextOffset && nextOffset != offset + 1 ?
889                          !isLeaf(nextOffset) && isNormalCompletion[nextOffset] :
890                          isLeaf(nextOffset) || isNormalCompletion[nextOffset];
891
892       isNormalCompletion[offset] |= isNormal;
893     }
894
895     @Override
896     public void visitThrowToInstruction(ThrowToInstruction instruction, int offset, int nextOffset) {
897       if (nextOffset > myFlow.getSize()) nextOffset = myFlow.getSize();
898       isNormalCompletion[offset] |= !isLeaf(nextOffset) && isNormalCompletion[nextOffset];
899     }
900
901     @Override
902     public void visitGoToInstruction(GoToInstruction instruction, int offset, int nextOffset) {
903       if (nextOffset > myFlow.getSize()) nextOffset = myFlow.getSize();
904       isNormalCompletion[offset] |= !instruction.isReturn && isNormalCompletion[nextOffset];
905     }
906
907     @Override
908     public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
909       if (nextOffset > myFlow.getSize()) nextOffset = myFlow.getSize();
910
911       boolean isNormal = isLeaf(nextOffset) || isNormalCompletion[nextOffset];
912       isNormalCompletion[offset] |= isNormal;
913     }
914
915     @Override
916     @NotNull
917     public Boolean getResult() {
918       return !isNormalCompletion[0];
919     }
920   }
921
922   public static boolean returnPresentBetween(@NotNull ControlFlow flow, final int startOffset, final int endOffset) {
923     class MyVisitor extends InstructionClientVisitor<Boolean> {
924       // false if control flow at this offset terminates either by return called or exception thrown
925       private final boolean[] isNormalCompletion = new boolean[flow.getSize() + 1];
926
927       MyVisitor() {
928         int i;
929         final int length = flow.getSize();
930         for (i = 0; i < startOffset; i++) {
931           isNormalCompletion[i] = true;
932         }
933         for (i = endOffset; i <= length; i++) {
934           isNormalCompletion[i] = true;
935         }
936       }
937
938       @Override
939       public void visitConditionalThrowToInstruction(ConditionalThrowToInstruction instruction, int offset, int nextOffset) {
940         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
941         if (offset > endOffset) return;
942         int throwToOffset = instruction.offset;
943         boolean isNormal;
944         if (throwToOffset == nextOffset) {
945           if (throwToOffset <= endOffset) {
946             isNormal = !isLeaf(nextOffset) && isNormalCompletion[nextOffset];
947           }
948           else {
949             return;
950           }
951         }
952         else {
953           isNormal = isLeaf(nextOffset) || isNormalCompletion[nextOffset];
954         }
955         isNormalCompletion[offset] |= isNormal;
956       }
957
958       @Override
959       public void visitThrowToInstruction(ThrowToInstruction instruction, int offset, int nextOffset) {
960         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
961         if (offset > endOffset) return;
962         if (nextOffset <= endOffset) {
963           boolean isNormal = !isLeaf(nextOffset) && isNormalCompletion[nextOffset];
964           isNormalCompletion[offset] |= isNormal;
965         }
966       }
967
968       @Override
969       public void visitCallInstruction(CallInstruction instruction, int offset, int nextOffset) {
970         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
971         if (offset > endOffset) return;
972         if (nextOffset > endOffset && nextOffset != offset + 1) {
973           return;
974         }
975         boolean isNormal = isNormalCompletion[nextOffset];
976         isNormalCompletion[offset] |= isNormal;
977       }
978
979       @Override
980       public void visitGoToInstruction(GoToInstruction instruction, int offset, int nextOffset) {
981         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
982         if (offset > endOffset) return;
983         boolean isRethrowFromFinally = instruction instanceof ReturnInstruction && ((ReturnInstruction)instruction).isRethrowFromFinally();
984         boolean isNormal = !instruction.isReturn && isNormalCompletion[nextOffset] && !isRethrowFromFinally;
985         isNormalCompletion[offset] |= isNormal;
986       }
987
988       @Override
989       public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
990         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
991         if (offset > endOffset) return;
992         final boolean isNormal = isLeaf(nextOffset) || isNormalCompletion[nextOffset];
993         isNormalCompletion[offset] |= isNormal;
994       }
995
996       @Override
997       @NotNull
998       public Boolean getResult() {
999         return !isNormalCompletion[startOffset];
1000       }
1001     }
1002     final MyVisitor visitor = new MyVisitor();
1003     depthFirstSearch(flow, visitor, startOffset, endOffset);
1004     return visitor.getResult().booleanValue();
1005   }
1006
1007   /**
1008    * returns true iff exists controlflow path completing normally, i.e. not resulting in return,break,continue or exception thrown.
1009    * In other words, if we add instruction after controlflow specified, it should be reachable
1010    */
1011   public static boolean canCompleteNormally(@NotNull ControlFlow flow, final int startOffset, final int endOffset) {
1012     class MyVisitor extends InstructionClientVisitor<Boolean> {
1013       // false if control flow at this offset terminates abruptly
1014       private final boolean[] canCompleteNormally = new boolean[flow.getSize() + 1];
1015
1016       @Override
1017       public void visitConditionalGoToInstruction(ConditionalGoToInstruction instruction, int offset, int nextOffset) {
1018         checkInstruction(offset, nextOffset, false);
1019       }
1020
1021       @Override
1022       public void visitGoToInstruction(GoToInstruction instruction, int offset, int nextOffset) {
1023         checkInstruction(offset, nextOffset, instruction.isReturn);
1024       }
1025
1026       private void checkInstruction(int offset, int nextOffset, boolean isReturn) {
1027         if (offset > endOffset) return;
1028         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
1029         boolean isNormal = nextOffset <= endOffset && !isReturn && (nextOffset == endOffset || canCompleteNormally[nextOffset]);
1030         if (isNormal && nextOffset == endOffset) {
1031           PsiElement element = flow.getElement(offset);
1032           if (element instanceof PsiBreakStatement) {
1033             PsiStatement exitedStatement = ((PsiBreakStatement)element).findExitedStatement();
1034             if (exitedStatement == null || flow.getStartOffset(exitedStatement) < startOffset) {
1035               isNormal = false;
1036             }
1037           }
1038           else if (element instanceof PsiContinueStatement) {
1039             PsiStatement continuedStatement = ((PsiContinueStatement)element).findContinuedStatement();
1040             if (continuedStatement == null || flow.getStartOffset(continuedStatement) < startOffset) {
1041               isNormal = false;
1042             }
1043           }
1044         }
1045         canCompleteNormally[offset] |= isNormal;
1046       }
1047
1048       @Override
1049       public void visitConditionalThrowToInstruction(ConditionalThrowToInstruction instruction, int offset, int nextOffset) {
1050         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
1051         if (offset > endOffset) return;
1052         int throwToOffset = instruction.offset;
1053         boolean isNormal;
1054         if (throwToOffset == nextOffset) {
1055           isNormal = throwToOffset <= endOffset && !isLeaf(nextOffset) && canCompleteNormally[nextOffset];
1056         }
1057         else {
1058           isNormal = canCompleteNormally[nextOffset];
1059         }
1060         canCompleteNormally[offset] |= isNormal;
1061       }
1062
1063       @Override
1064       public void visitThrowToInstruction(ThrowToInstruction instruction, int offset, int nextOffset) {
1065         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
1066         if (offset > endOffset) return;
1067         if (nextOffset <= endOffset) {
1068           boolean isNormal = !isLeaf(nextOffset) && canCompleteNormally[nextOffset];
1069           canCompleteNormally[offset] |= isNormal;
1070         }
1071       }
1072
1073       @Override
1074       public void visitCallInstruction(CallInstruction instruction, int offset, int nextOffset) {
1075         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
1076         if (offset > endOffset) return;
1077         if (nextOffset > endOffset && nextOffset != offset + 1) {
1078           return;
1079         }
1080         boolean isNormal = canCompleteNormally[nextOffset];
1081         canCompleteNormally[offset] |= isNormal;
1082       }
1083
1084       @Override
1085       public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
1086         checkInstruction(offset, nextOffset, false);
1087       }
1088
1089       @Override
1090       @NotNull
1091       public Boolean getResult() {
1092         return canCompleteNormally[startOffset];
1093       }
1094     }
1095     final MyVisitor visitor = new MyVisitor();
1096     depthFirstSearch(flow, visitor, startOffset, endOffset);
1097     return visitor.getResult().booleanValue();
1098   }
1099
1100   /**
1101    * @return any unreachable statement or null
1102    */
1103   public static PsiElement getUnreachableStatement(@NotNull ControlFlow flow) {
1104     final InstructionClientVisitor<PsiElement> visitor = new UnreachableStatementClientVisitor(flow);
1105     depthFirstSearch(flow, visitor);
1106     return visitor.getResult();
1107   }
1108
1109   private static class UnreachableStatementClientVisitor extends InstructionClientVisitor<PsiElement> {
1110     private final ControlFlow myFlow;
1111
1112     UnreachableStatementClientVisitor(@NotNull ControlFlow flow) {
1113       myFlow = flow;
1114     }
1115
1116     @Override
1117     public PsiElement getResult() {
1118       for (int i = 0; i < processedInstructions.length; i++) {
1119         if (!processedInstructions[i]) {
1120           PsiElement element = myFlow.getElement(i);
1121
1122           final PsiElement unreachableParent = getUnreachableExpressionParent(element);
1123           if (unreachableParent != null) return unreachableParent;
1124
1125           if (element == null || !PsiUtil.isStatement(element)) continue;
1126           if (element.getParent() instanceof PsiExpression) continue;
1127
1128           // ignore for(;;) statement unreachable update
1129           while (element instanceof PsiExpression) {
1130             element = element.getParent();
1131           }
1132           if (element instanceof PsiStatement
1133               && element.getParent() instanceof PsiForStatement
1134               && element == ((PsiForStatement)element.getParent()).getUpdate()) {
1135             continue;
1136           }
1137           //filter out generated statements
1138           final int endOffset = myFlow.getEndOffset(element);
1139           if (endOffset != i + 1) continue;
1140           final int startOffset = myFlow.getStartOffset(element);
1141           // this offset actually is a part of reachable statement
1142           if (0 <= startOffset && startOffset < processedInstructions.length && processedInstructions[startOffset]) continue;
1143           final PsiElement enclosingStatement = getEnclosingUnreachableStatement(element);
1144           return enclosingStatement != null ? enclosingStatement : element;
1145         }
1146       }
1147       return null;
1148     }
1149
1150     @Nullable
1151     private static PsiElement getUnreachableExpressionParent(@Nullable PsiElement element) {
1152       if (element instanceof PsiExpression) {
1153         final PsiElement expression = PsiTreeUtil.findFirstParent(element, e -> !(e.getParent() instanceof PsiParenthesizedExpression));
1154         if (expression != null) {
1155           final PsiElement parent = expression.getParent();
1156           if (parent instanceof PsiExpressionStatement) {
1157             return getUnreachableStatementParent(parent);
1158           }
1159           if (parent instanceof PsiIfStatement && ((PsiIfStatement)parent).getCondition() == expression ||
1160               parent instanceof PsiSwitchBlock && ((PsiSwitchBlock)parent).getExpression() == expression ||
1161               parent instanceof PsiWhileStatement && ((PsiWhileStatement)parent).getCondition() == expression ||
1162               parent instanceof PsiForeachStatement && ((PsiForeachStatement)parent).getIteratedValue() == expression) {
1163             return parent;
1164           }
1165         }
1166       }
1167       return null;
1168     }
1169
1170     @Nullable
1171     private static PsiElement getEnclosingUnreachableStatement(@NotNull PsiElement statement) {
1172       final PsiElement parent = statement.getParent();
1173       if (parent instanceof PsiDoWhileStatement && ((PsiDoWhileStatement)parent).getBody() == statement) {
1174         return parent;
1175       }
1176       if (parent instanceof PsiCodeBlock && PsiTreeUtil.getNextSiblingOfType(parent.getFirstChild(), PsiStatement.class) == statement) {
1177         final PsiBlockStatement blockStatement = ObjectUtils.tryCast(parent.getParent(), PsiBlockStatement.class);
1178         if (blockStatement != null) {
1179           final PsiElement blockParent = blockStatement.getParent();
1180           if (blockParent instanceof PsiDoWhileStatement && ((PsiDoWhileStatement)blockParent).getBody() == blockStatement) {
1181             return blockParent;
1182           }
1183         }
1184       }
1185       return getUnreachableStatementParent(statement);
1186     }
1187
1188     @Nullable
1189     private static PsiElement getUnreachableStatementParent(@NotNull PsiElement statement) {
1190       final PsiElement parent = statement.getParent();
1191       if (parent instanceof PsiForStatement && ((PsiForStatement)parent).getInitialization() == statement) {
1192         return parent;
1193       }
1194       return null;
1195     }
1196   }
1197
1198   private static PsiReferenceExpression getEnclosingReferenceExpression(@NotNull PsiElement element, @NotNull PsiVariable variable) {
1199     final PsiReferenceExpression reference = findReferenceTo(element, variable);
1200     if (reference != null) return reference;
1201     while (element != null) {
1202       if (element instanceof PsiReferenceExpression) {
1203         return (PsiReferenceExpression)element;
1204       }
1205       if (element instanceof PsiMethod || element instanceof PsiClass) {
1206         return null;
1207       }
1208       element = element.getParent();
1209     }
1210     return null;
1211   }
1212
1213   private static PsiReferenceExpression findReferenceTo(@NotNull PsiElement element, @NotNull PsiVariable variable) {
1214     if (element instanceof PsiReferenceExpression
1215         && ExpressionUtil.isEffectivelyUnqualified((PsiReferenceExpression)element)
1216         && ((PsiReferenceExpression)element).resolve() == variable) {
1217       return (PsiReferenceExpression)element;
1218     }
1219     final PsiElement[] children = element.getChildren();
1220     for (PsiElement child : children) {
1221       final PsiReferenceExpression reference = findReferenceTo(child, variable);
1222       if (reference != null) return reference;
1223     }
1224     return null;
1225   }
1226
1227   /**
1228    * Returns true of instruction at given offset is a dominator for target instruction (that is: execution from flow start to
1229    * the target always goes through given offset).
1230    * @param flow control flow to analyze
1231    * @param maybeDominator a dominator candidate offset
1232    * @param target a target instruction offset
1233    * @return true if instruction at maybeDominator offset is actually a dominator.
1234    */
1235   public static boolean isDominator(ControlFlow flow, int maybeDominator, int target) {
1236     class MyVisitor extends InstructionClientVisitor<Boolean> {
1237       final BitSet myReachedWithoutDominator = new BitSet();
1238       
1239       @Override
1240       public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
1241         super.visitInstruction(instruction, offset, nextOffset);
1242         if (nextOffset != maybeDominator && (target == nextOffset || myReachedWithoutDominator.get(nextOffset))) {
1243           myReachedWithoutDominator.set(offset);
1244         }
1245       }
1246
1247       @Override
1248       public Boolean getResult() {
1249         return myReachedWithoutDominator.get(0);
1250       }
1251     }
1252     MyVisitor visitor = new MyVisitor();
1253     depthFirstSearch(flow, visitor, 0, target);
1254     return !visitor.getResult();
1255   }
1256
1257   public static boolean isVariableDefinitelyAssigned(@NotNull final PsiVariable variable, @NotNull final ControlFlow flow) {
1258     final int variableDeclarationOffset = flow.getStartOffset(variable.getParent());
1259     int offset = variableDeclarationOffset > -1 ? variableDeclarationOffset : 0;
1260     boolean[] unassignedOffsets = getVariablePossiblyUnassignedOffsets(variable, flow);
1261     return !unassignedOffsets[offset];
1262   }
1263
1264   /**
1265    * Returns offsets starting from which the variable could be unassigned 
1266    * 
1267    * @param variable variable to check
1268    * @param flow control flow
1269    * @return a boolean array which values correspond to control flow offset. 
1270    * True value means that variable could be unassigned when execution starts from given offset.
1271    */
1272   public static boolean[] getVariablePossiblyUnassignedOffsets(@NotNull PsiVariable variable, @NotNull ControlFlow flow) {
1273     class MyVisitor extends InstructionClientVisitor<boolean[]> {
1274       // true if from this point below there may be branch with no variable assignment
1275       private final boolean[] maybeUnassigned = new boolean[flow.getSize() + 1];
1276
1277       {
1278         maybeUnassigned[maybeUnassigned.length - 1] = true;
1279       }
1280
1281       @Override
1282       public void visitWriteVariableInstruction(WriteVariableInstruction instruction, int offset, int nextOffset) {
1283         if (instruction.variable == variable) {
1284           maybeUnassigned[offset] = false;
1285         }
1286         else {
1287           visitInstruction(instruction, offset, nextOffset);
1288         }
1289       }
1290
1291       @Override
1292       public void visitConditionalThrowToInstruction(ConditionalThrowToInstruction instruction, int offset, int nextOffset) {
1293         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
1294         boolean unassigned = offset == flow.getSize() - 1
1295                              || !isLeaf(nextOffset) && maybeUnassigned[nextOffset];
1296
1297         maybeUnassigned[offset] |= unassigned;
1298       }
1299
1300       @Override
1301       public void visitCallInstruction(CallInstruction instruction, int offset, int nextOffset) {
1302         visitInstruction(instruction, offset, nextOffset);
1303         // clear return statements after procedure as well
1304         for (int i = instruction.procBegin; i < instruction.procEnd + 3; i++) {
1305           maybeUnassigned[i] = false;
1306         }
1307       }
1308
1309       @Override
1310       public void visitGoToInstruction(GoToInstruction instruction, int offset, int nextOffset) {
1311         if (instruction.isReturn && variable instanceof PsiLocalVariable) {
1312           if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
1313           boolean unassigned = !isLeaf(nextOffset) && maybeUnassigned[nextOffset];
1314           maybeUnassigned[offset] |= unassigned;
1315         }
1316         else {
1317           super.visitGoToInstruction(instruction, offset, nextOffset);
1318         }
1319       }
1320
1321       @Override
1322       public void visitThrowToInstruction(ThrowToInstruction instruction, int offset, int nextOffset) {
1323         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
1324         boolean unassigned = !isLeaf(nextOffset) && maybeUnassigned[nextOffset];
1325         maybeUnassigned[offset] |= unassigned;
1326       }
1327
1328       @Override
1329       public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
1330         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
1331
1332         boolean unassigned = isLeaf(nextOffset) || maybeUnassigned[nextOffset];
1333         maybeUnassigned[offset] |= unassigned;
1334       }
1335
1336       @Override
1337       @NotNull
1338       public boolean[] getResult() {
1339         return maybeUnassigned;
1340       }
1341     }
1342     if (flow.getSize() == 0) return new boolean[] {true};
1343     MyVisitor visitor = new MyVisitor();
1344     depthFirstSearch(flow, visitor);
1345     return visitor.getResult();
1346   }
1347
1348   public static boolean isVariableDefinitelyNotAssigned(@NotNull PsiVariable variable, @NotNull ControlFlow flow) {
1349     class MyVisitor extends InstructionClientVisitor<Boolean> {
1350       // true if from this point below there may be branch with variable assignment
1351       private final boolean[] maybeAssigned = new boolean[flow.getSize() + 1];
1352
1353       @Override
1354       public void visitWriteVariableInstruction(WriteVariableInstruction instruction, int offset, int nextOffset) {
1355         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
1356         boolean assigned = instruction.variable == variable || maybeAssigned[nextOffset];
1357         maybeAssigned[offset] |= assigned;
1358       }
1359
1360       @Override
1361       public void visitThrowToInstruction(ThrowToInstruction instruction, int offset, int nextOffset) {
1362         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
1363         boolean assigned = !isLeaf(nextOffset) && maybeAssigned[nextOffset];
1364         maybeAssigned[offset] |= assigned;
1365       }
1366
1367       @Override
1368       public void visitConditionalThrowToInstruction(ConditionalThrowToInstruction instruction, int offset, int nextOffset) {
1369         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
1370         int throwToOffset = instruction.offset;
1371         boolean assigned = throwToOffset == nextOffset ? !isLeaf(nextOffset) && maybeAssigned[nextOffset] :
1372                            maybeAssigned[nextOffset];
1373         maybeAssigned[offset] |= assigned;
1374       }
1375
1376       @Override
1377       public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
1378         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
1379
1380         boolean assigned = maybeAssigned[nextOffset];
1381
1382         maybeAssigned[offset] |= assigned;
1383       }
1384
1385       @Override
1386       @NotNull
1387       public Boolean getResult() {
1388         return !maybeAssigned[0];
1389       }
1390     }
1391     MyVisitor visitor = new MyVisitor();
1392     depthFirstSearch(flow, visitor);
1393     return visitor.getResult().booleanValue();
1394   }
1395
1396   /**
1397    * Returns true if the value the variable has at start is later referenced without going through stop instruction
1398    *
1399    * @param flow ControlFlow to analyze
1400    * @param start the point at which variable value is created
1401    * @param stop the stop-point
1402    * @param variable the variable to examine
1403    * @return true if the value the variable has at start is later referenced without going through stop instruction
1404    */
1405   public static boolean isValueUsedWithoutVisitingStop(@NotNull ControlFlow flow, final int start, final int stop, @NotNull PsiVariable variable) {
1406     if(start == stop) return false;
1407
1408     class MyVisitor extends InstructionClientVisitor<Boolean> {
1409       // true if value the variable has at given offset maybe referenced without going through stop instruction
1410       private final boolean[] maybeReferenced = new boolean[flow.getSize() + 1];
1411
1412       @Override
1413       public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
1414         if (offset == stop) {
1415           maybeReferenced[offset] = false;
1416           return;
1417         }
1418         if(instruction instanceof WriteVariableInstruction && ((WriteVariableInstruction)instruction).variable == variable) {
1419           maybeReferenced[offset] = false;
1420           return;
1421         }
1422         if (maybeReferenced[offset]) return;
1423         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
1424
1425         boolean nextState = maybeReferenced[nextOffset];
1426         maybeReferenced[offset] =
1427           nextState || instruction instanceof ReadVariableInstruction && ((ReadVariableInstruction)instruction).variable == variable;
1428       }
1429
1430       @Override
1431       @NotNull
1432       public Boolean getResult() {
1433         return maybeReferenced[start];
1434       }
1435     }
1436     MyVisitor visitor = new MyVisitor();
1437     depthFirstSearch(flow, visitor, start, flow.getSize());
1438     return visitor.getResult().booleanValue();
1439   }
1440
1441   /**
1442    * Checks if the control flow instruction at given offset accesses (reads or writes) given variable
1443    *
1444    * @param flow control flow
1445    * @param offset offset inside given control flow
1446    * @param variable a variable the access to which is to be checked
1447    * @return true if the given instruction is actually a variable access
1448    */
1449   public static boolean isVariableAccess(@NotNull ControlFlow flow, int offset, @NotNull PsiVariable variable) {
1450     Instruction instruction = flow.getInstructions().get(offset);
1451     return instruction instanceof ReadVariableInstruction && ((ReadVariableInstruction)instruction).variable == variable ||
1452            instruction instanceof WriteVariableInstruction && ((WriteVariableInstruction)instruction).variable == variable;
1453   }
1454
1455   public static class ControlFlowEdge {
1456     public final int myFrom;
1457     public final int myTo;
1458
1459     ControlFlowEdge(int from, int to) {
1460       myFrom = from;
1461       myTo = to;
1462     }
1463
1464     @Override
1465     public String toString() {
1466       return myFrom+"->"+myTo;
1467     }
1468   }
1469
1470   /**
1471    * Returns control flow edges which are potentially reachable from start instruction
1472    *
1473    * @param flow control flow to analyze
1474    * @param start starting instruction offset
1475    * @return a list of edges
1476    */
1477   @NotNull
1478   public static List<ControlFlowEdge> getEdges(@NotNull ControlFlow flow, int start) {
1479     final List<ControlFlowEdge> list = new ArrayList<>();
1480     depthFirstSearch(flow, new InstructionClientVisitor<Void>() {
1481       @Override
1482       public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
1483         list.add(new ControlFlowEdge(offset, nextOffset));
1484       }
1485
1486       @Override
1487       public Void getResult() {
1488         return null;
1489       }
1490     }, start, flow.getSize());
1491     return list;
1492   }
1493
1494   /**
1495    * @return min offset after sourceOffset which is definitely reachable from all references
1496    */
1497   public static int getMinDefinitelyReachedOffset(@NotNull ControlFlow flow, final int sourceOffset,
1498                                                   @NotNull List<? extends PsiElement> references) {
1499     class MyVisitor extends InstructionClientVisitor<Integer> {
1500       // set of exit points reached from this offset
1501       private final TIntHashSet[] exitPoints = new TIntHashSet[flow.getSize()];
1502
1503       @Override
1504       public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
1505         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
1506
1507         if (exitPoints[offset] == null) {
1508           exitPoints[offset] = new TIntHashSet();
1509         }
1510         if (isLeaf(nextOffset)) {
1511           exitPoints[offset].add(offset);
1512         }
1513         else if (exitPoints[nextOffset] != null) {
1514           exitPoints[offset].addAll(exitPoints[nextOffset].toArray());
1515         }
1516       }
1517
1518       @Override
1519       @NotNull
1520       public Integer getResult() {
1521         int minOffset = flow.getSize();
1522         int maxExitPoints = 0;
1523         nextOffset:
1524         for (int i = sourceOffset; i < exitPoints.length; i++) {
1525           TIntHashSet exitPointSet = exitPoints[i];
1526           final int size = exitPointSet == null ? 0 : exitPointSet.size();
1527           if (size > maxExitPoints) {
1528             // this offset should be reachable from all other references
1529             for (PsiElement element : references) {
1530               final PsiElement statement = PsiUtil.getEnclosingStatement(element);
1531               if (statement == null) continue;
1532               final int endOffset = flow.getEndOffset(statement);
1533               if (endOffset == -1) continue;
1534               if (i != endOffset && !isInstructionReachable(flow, i, endOffset)) continue nextOffset;
1535             }
1536             minOffset = i;
1537             maxExitPoints = size;
1538           }
1539         }
1540         return minOffset;
1541       }
1542     }
1543     MyVisitor visitor = new MyVisitor();
1544     depthFirstSearch(flow, visitor);
1545     return visitor.getResult().intValue();
1546   }
1547
1548   private static int findUnprocessed(int startOffset, int endOffset, @NotNull InstructionClientVisitor<?> visitor) {
1549     for (int i = startOffset; i < endOffset; i++) {
1550       if (!visitor.processedInstructions[i]) {
1551         return i;
1552       }
1553     }
1554     return endOffset;
1555   }
1556
1557   private static void depthFirstSearch(@NotNull ControlFlow flow, @NotNull InstructionClientVisitor visitor) {
1558     depthFirstSearch(flow, visitor, 0, flow.getSize());
1559   }
1560
1561   private static void depthFirstSearch(@NotNull ControlFlow flow, @NotNull InstructionClientVisitor visitor, int startOffset, int endOffset) {
1562     visitor.processedInstructions = new boolean[endOffset];
1563     internalDepthFirstSearch(flow.getInstructions(), visitor, startOffset, endOffset);
1564   }
1565
1566   private static void internalDepthFirstSearch(@NotNull List<? extends Instruction> instructions,
1567                                                @NotNull InstructionClientVisitor clientVisitor,
1568                                                int startOffset,
1569                                                int endOffset) {
1570
1571     final WalkThroughStack walkThroughStack = new WalkThroughStack(instructions.size() / 2);
1572     walkThroughStack.push(startOffset);
1573
1574     // we can change instruction internal state here (e.g. CallInstruction.stack)
1575     synchronized (instructions) {
1576       final IntArrayList currentProcedureReturnOffsets = new IntArrayList();
1577       ControlFlowInstructionVisitor getNextOffsetVisitor = new ControlFlowInstructionVisitor() {
1578         @Override
1579         public void visitCallInstruction(CallInstruction instruction, int offset, int nextOffset) {
1580           instruction.execute(offset + 1);
1581           int newOffset = instruction.offset;
1582           // 'procedure' pointed by call instruction should be processed regardless of whether it was already visited or not
1583           // clear procedure text and return instructions afterwards
1584           int i;
1585           for (i = instruction.procBegin;
1586                i < clientVisitor.processedInstructions.length &&
1587                (i < instruction.procEnd || i < instructions.size() && instructions.get(i) instanceof ReturnInstruction); i++) {
1588             clientVisitor.processedInstructions[i] = false;
1589           }
1590           clientVisitor.procedureEntered(instruction.procBegin, i);
1591           walkThroughStack.push(offset, newOffset);
1592           walkThroughStack.push(newOffset);
1593
1594           currentProcedureReturnOffsets.add(offset + 1);
1595         }
1596
1597         @Override
1598         public void visitReturnInstruction(ReturnInstruction instruction, int offset, int nextOffset) {
1599           int newOffset = instruction.execute(false);
1600           if (newOffset != -1) {
1601             walkThroughStack.push(offset, newOffset);
1602             walkThroughStack.push(newOffset);
1603           }
1604         }
1605
1606         @Override
1607         public void visitBranchingInstruction(BranchingInstruction instruction, int offset, int nextOffset) {
1608           int newOffset = instruction.offset;
1609           walkThroughStack.push(offset, newOffset);
1610           walkThroughStack.push(newOffset);
1611         }
1612
1613         @Override
1614         public void visitConditionalBranchingInstruction(ConditionalBranchingInstruction instruction, int offset, int nextOffset) {
1615           int newOffset = instruction.offset;
1616
1617           walkThroughStack.push(offset, newOffset);
1618           walkThroughStack.push(offset, offset + 1);
1619           walkThroughStack.push(newOffset);
1620           walkThroughStack.push(offset + 1);
1621         }
1622
1623         @Override
1624         public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
1625           int newOffset = offset + 1;
1626           walkThroughStack.push(offset, newOffset);
1627           walkThroughStack.push(newOffset);
1628         }
1629       };
1630       while (!walkThroughStack.isEmpty()) {
1631         final int offset = walkThroughStack.peekOldOffset();
1632         final int newOffset = walkThroughStack.popNewOffset();
1633
1634         if (offset >= endOffset) {
1635           continue;
1636         }
1637         Instruction instruction = instructions.get(offset);
1638
1639         if (clientVisitor.processedInstructions[offset]) {
1640           if (newOffset != -1) {
1641             instruction.accept(clientVisitor, offset, newOffset);
1642           }
1643           // when traversing call instruction, we have traversed all procedure control flows, so pop return address
1644           if (!currentProcedureReturnOffsets.isEmpty() && currentProcedureReturnOffsets.get(currentProcedureReturnOffsets.size() - 1) - 1 == offset) {
1645             currentProcedureReturnOffsets.remove(currentProcedureReturnOffsets.size() - 1);
1646           }
1647           continue;
1648         }
1649         if (!currentProcedureReturnOffsets.isEmpty()) {
1650           int returnOffset = currentProcedureReturnOffsets.get(currentProcedureReturnOffsets.size() - 1);
1651           CallInstruction callInstruction = (CallInstruction)instructions.get(returnOffset - 1);
1652           // check if we inside procedure but 'return offset' stack is empty, so
1653           // we should push back to 'return offset' stack
1654           synchronized (callInstruction.stack) {
1655             if (callInstruction.procBegin <= offset && offset < callInstruction.procEnd + 2
1656                 && (callInstruction.stack.size() == 0 || callInstruction.stack.peekReturnOffset() != returnOffset)) {
1657               callInstruction.stack.push(returnOffset, callInstruction);
1658             }
1659           }
1660         }
1661
1662         clientVisitor.processedInstructions[offset] = true;
1663         instruction.accept(getNextOffsetVisitor, offset, newOffset);
1664       }
1665     }
1666   }
1667
1668   private static class WalkThroughStack {
1669     private int[] oldOffsets;
1670     private int[] newOffsets;
1671     private int size;
1672
1673     WalkThroughStack(int initialSize) {
1674       if (initialSize < 2) initialSize = 2;
1675       oldOffsets = new int[initialSize];
1676       newOffsets = new int[initialSize];
1677     }
1678
1679     /**
1680      * Push an arc of the graph (oldOffset -> newOffset)
1681      */
1682     void push(int oldOffset, int newOffset) {
1683       LOG.assertTrue(oldOffset >= 0, "negative offset is pushed to walk-through stack");
1684       if (size >= newOffsets.length) {
1685         oldOffsets = ArrayUtil.realloc(oldOffsets, size * 3 / 2);
1686         newOffsets = ArrayUtil.realloc(newOffsets, size * 3 / 2);
1687       }
1688       oldOffsets[size] = oldOffset;
1689       newOffsets[size] = newOffset;
1690       size++;
1691     }
1692
1693     /**
1694      * Push a node of the graph. The node is represented as an arc with newOffset==-1
1695      */
1696     void push(int offset) {
1697       push(offset, -1);
1698     }
1699
1700     /**
1701      * Should be used in pair with {@link #popNewOffset()}
1702      */
1703     int peekOldOffset() {
1704       return oldOffsets[size - 1];
1705     }
1706
1707     /**
1708      * Should be used in pair with {@link #peekOldOffset()}
1709      */
1710     int popNewOffset() {
1711       return newOffsets[--size];
1712     }
1713
1714     boolean isEmpty() {
1715       return size == 0;
1716     }
1717
1718     @Override
1719     public String toString() {
1720       StringBuilder s = new StringBuilder();
1721       for (int i = 0; i < size; i++) {
1722         if (s.length() != 0) s.append(' ');
1723         if (newOffsets[i] != -1) {
1724           s.append('(').append(oldOffsets[i]).append("->").append(newOffsets[i]).append(')');
1725         }
1726         else {
1727           s.append('[').append(oldOffsets[i]).append(']');
1728         }
1729       }
1730       return s.toString();
1731     }
1732   }
1733
1734   private static boolean isInsideReturnStatement(PsiElement element) {
1735     while (element instanceof PsiExpression) element = element.getParent();
1736     return element instanceof PsiReturnStatement;
1737   }
1738
1739   private static class CopyOnWriteList {
1740     private final List<VariableInfo> list;
1741
1742     @NotNull
1743     public CopyOnWriteList add(@NotNull VariableInfo value) {
1744       CopyOnWriteList newList = new CopyOnWriteList();
1745       List<VariableInfo> list = getList();
1746       for (final VariableInfo variableInfo : list) {
1747         if (!value.equals(variableInfo)) {
1748           newList.list.add(variableInfo);
1749         }
1750       }
1751       newList.list.add(value);
1752       return newList;
1753     }
1754
1755     @NotNull
1756     public CopyOnWriteList remove(@NotNull VariableInfo value) {
1757       CopyOnWriteList newList = new CopyOnWriteList();
1758       List<VariableInfo> list = getList();
1759       for (final VariableInfo variableInfo : list) {
1760         if (!value.equals(variableInfo)) {
1761           newList.list.add(variableInfo);
1762         }
1763       }
1764       return newList;
1765     }
1766
1767     @NotNull
1768     public List<VariableInfo> getList() {
1769       return list;
1770     }
1771
1772     CopyOnWriteList() {
1773       this(Collections.emptyList());
1774     }
1775
1776     CopyOnWriteList(@NotNull VariableInfo... infos) {
1777       this(Arrays.asList(infos));
1778     }
1779
1780     CopyOnWriteList(@NotNull Collection<? extends VariableInfo> infos) {
1781       list = new SmartList<>(infos);
1782     }
1783
1784     @NotNull
1785     public CopyOnWriteList addAll(@NotNull CopyOnWriteList addList) {
1786       CopyOnWriteList newList = new CopyOnWriteList();
1787       List<VariableInfo> list = getList();
1788       newList.list.addAll(list);
1789       List<VariableInfo> toAdd = addList.getList();
1790       for (final VariableInfo variableInfo : toAdd) {
1791         if (!newList.list.contains(variableInfo)) {
1792           // no copy
1793           newList.list.add(variableInfo);
1794         }
1795       }
1796       return newList;
1797     }
1798
1799     @NotNull
1800     public static CopyOnWriteList add(@Nullable CopyOnWriteList list, @NotNull VariableInfo value) {
1801       return list == null ? new CopyOnWriteList(value) : list.add(value);
1802     }
1803   }
1804
1805   public static class VariableInfo {
1806     private final PsiVariable variable;
1807     public final PsiElement expression;
1808
1809     public VariableInfo(@NotNull PsiVariable variable, @Nullable PsiElement expression) {
1810       this.variable = variable;
1811       this.expression = expression;
1812     }
1813
1814     public boolean equals(Object o) {
1815       return this == o || o instanceof VariableInfo && variable.equals(((VariableInfo)o).variable);
1816     }
1817
1818     public int hashCode() {
1819       return variable.hashCode();
1820     }
1821   }
1822
1823   private static void merge(int offset, CopyOnWriteList source, @NotNull CopyOnWriteList[] target) {
1824     if (source != null) {
1825       CopyOnWriteList existing = target[offset];
1826       target[offset] = existing == null ? source : existing.addAll(source);
1827     }
1828   }
1829
1830   /**
1831    * @return list of PsiReferenceExpression of usages of non-initialized local variables
1832    */
1833   @NotNull
1834   public static List<PsiReferenceExpression> getReadBeforeWriteLocals(@NotNull ControlFlow flow) {
1835     final InstructionClientVisitor<List<PsiReferenceExpression>> visitor = new ReadBeforeWriteClientVisitor(flow, true);
1836     depthFirstSearch(flow, visitor);
1837     return visitor.getResult();
1838   }
1839
1840   @NotNull
1841   public static List<PsiReferenceExpression> getReadBeforeWrite(@NotNull ControlFlow flow) {
1842     return getReadBeforeWrite(flow, 0);
1843   }
1844
1845   @NotNull
1846   private static List<PsiReferenceExpression> getReadBeforeWrite(@NotNull ControlFlow flow, int startOffset) {
1847     if (startOffset < 0 || startOffset >= flow.getSize()) {
1848       return Collections.emptyList();
1849     }
1850     final ReadBeforeWriteClientVisitor visitor = new ReadBeforeWriteClientVisitor(flow, false);
1851     depthFirstSearch(flow, visitor);
1852     return visitor.getResult(startOffset);
1853   }
1854
1855   private static class ReadBeforeWriteClientVisitor extends InstructionClientVisitor<List<PsiReferenceExpression>> {
1856     // map of variable->PsiReferenceExpressions for all read before written variables for this point and below in control flow
1857     private final CopyOnWriteList[] readVariables;
1858     private final ControlFlow myFlow;
1859     private final boolean localVariablesOnly;
1860
1861     ReadBeforeWriteClientVisitor(@NotNull ControlFlow flow, boolean localVariablesOnly) {
1862       myFlow = flow;
1863       this.localVariablesOnly = localVariablesOnly;
1864       readVariables = new CopyOnWriteList[myFlow.getSize() + 1];
1865     }
1866
1867     @Override
1868     public void visitReadVariableInstruction(ReadVariableInstruction instruction, int offset, int nextOffset) {
1869       CopyOnWriteList readVars = readVariables[Math.min(nextOffset, myFlow.getSize())];
1870       final PsiVariable variable = instruction.variable;
1871       if (!localVariablesOnly || !isMethodParameter(variable)) {
1872         final PsiReferenceExpression expression = getEnclosingReferenceExpression(myFlow.getElement(offset), variable);
1873         if (expression != null) {
1874           readVars = CopyOnWriteList.add(readVars, new VariableInfo(variable, expression));
1875         }
1876       }
1877       merge(offset, readVars, readVariables);
1878     }
1879
1880     @Override
1881     public void visitWriteVariableInstruction(WriteVariableInstruction instruction, int offset, int nextOffset) {
1882       CopyOnWriteList readVars = readVariables[Math.min(nextOffset, myFlow.getSize())];
1883       if (readVars == null) return;
1884
1885       final PsiVariable variable = instruction.variable;
1886       if (!localVariablesOnly || !isMethodParameter(variable)) {
1887         readVars = readVars.remove(new VariableInfo(variable, null));
1888       }
1889       merge(offset, readVars, readVariables);
1890     }
1891
1892     private static boolean isMethodParameter(@NotNull PsiVariable variable) {
1893       if (variable instanceof PsiParameter) {
1894         final PsiParameter parameter = (PsiParameter)variable;
1895         return !(parameter.getDeclarationScope() instanceof PsiForeachStatement);
1896       }
1897       return false;
1898     }
1899
1900     @Override
1901     public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
1902       merge(offset, readVariables[Math.min(nextOffset, myFlow.getSize())], readVariables);
1903     }
1904
1905     @Override
1906     public void visitCallInstruction(CallInstruction instruction, int offset, int nextOffset) {
1907       visitInstruction(instruction, offset, nextOffset);
1908       for (int i = instruction.procBegin; i <= instruction.procEnd; i++) {
1909         readVariables[i] = null;
1910       }
1911     }
1912
1913     @Override
1914     @NotNull
1915     public List<PsiReferenceExpression> getResult() {
1916       return getResult(0);
1917     }
1918
1919     @NotNull
1920     public List<PsiReferenceExpression> getResult(int startOffset) {
1921       final CopyOnWriteList topReadVariables = readVariables[startOffset];
1922       if (topReadVariables == null) return Collections.emptyList();
1923
1924       final List<PsiReferenceExpression> result = new ArrayList<>();
1925       List<VariableInfo> list = topReadVariables.getList();
1926       for (final VariableInfo variableInfo : list) {
1927         result.add((PsiReferenceExpression)variableInfo.expression);
1928       }
1929       return result;
1930     }
1931   }
1932
1933   public static final int NORMAL_COMPLETION_REASON = 1;
1934   private static final int RETURN_COMPLETION_REASON = 2;
1935
1936   /**
1937    * return reasons.normalCompletion when  block can complete normally
1938    * reasons.returnCalled when  block can complete abruptly because of return statement executed
1939    */
1940   public static int getCompletionReasons(@NotNull ControlFlow flow, final int offset, final int endOffset) {
1941     class MyVisitor extends InstructionClientVisitor<Integer> {
1942       private final boolean[] normalCompletion = new boolean[endOffset];
1943       private final boolean[] returnCalled = new boolean[endOffset];
1944
1945       @Override
1946       public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
1947         boolean ret = nextOffset < endOffset && returnCalled[nextOffset];
1948         boolean normal = nextOffset < endOffset && normalCompletion[nextOffset];
1949         final PsiElement element = flow.getElement(offset);
1950         boolean goToReturn = instruction instanceof GoToInstruction && ((GoToInstruction)instruction).isReturn;
1951         if (goToReturn || isInsideReturnStatement(element)) {
1952           ret = true;
1953         }
1954         else if (instruction instanceof ConditionalThrowToInstruction) {
1955           final int throwOffset = ((ConditionalThrowToInstruction)instruction).offset;
1956           boolean normalWhenThrow = throwOffset < endOffset && normalCompletion[throwOffset];
1957           boolean normalWhenNotThrow = offset == endOffset - 1 || normalCompletion[offset + 1];
1958           normal = normalWhenThrow || normalWhenNotThrow;
1959         }
1960         else if (!(instruction instanceof ThrowToInstruction) && nextOffset >= endOffset) {
1961           normal = true;
1962         }
1963         returnCalled[offset] |= ret;
1964         normalCompletion[offset] |= normal;
1965       }
1966
1967       @Override
1968       @NotNull
1969       public Integer getResult() {
1970         return (returnCalled[offset] ? RETURN_COMPLETION_REASON : 0) | (normalCompletion[offset] ? NORMAL_COMPLETION_REASON : 0);
1971       }
1972     }
1973     MyVisitor visitor = new MyVisitor();
1974     depthFirstSearch(flow, visitor, offset, endOffset);
1975
1976     return visitor.getResult().intValue();
1977   }
1978
1979   @NotNull
1980   public static Collection<VariableInfo> getInitializedTwice(@NotNull ControlFlow flow) {
1981     return getInitializedTwice(flow, 0, flow.getSize());
1982   }
1983
1984   @NotNull
1985   public static Collection<VariableInfo> getInitializedTwice(@NotNull ControlFlow flow, int startOffset, int endOffset) {
1986     while (startOffset < endOffset) {
1987       InitializedTwiceClientVisitor visitor = new InitializedTwiceClientVisitor(flow, startOffset);
1988       depthFirstSearch(flow, visitor, startOffset, endOffset);
1989       Collection<VariableInfo> result = visitor.getResult();
1990       if(!result.isEmpty()) {
1991         return result;
1992       }
1993       startOffset = findUnprocessed(startOffset, endOffset, visitor);
1994     }
1995     return Collections.emptyList();
1996   }
1997
1998   private static class InitializedTwiceClientVisitor extends InstructionClientVisitor<Collection<VariableInfo>> {
1999     // map of variable->PsiReferenceExpressions for all read and not written variables for this point and below in control flow
2000     private final CopyOnWriteList[] writtenVariables;
2001     private final CopyOnWriteList[] writtenTwiceVariables;
2002     private final ControlFlow myFlow;
2003     private final int myStartOffset;
2004
2005     InitializedTwiceClientVisitor(@NotNull ControlFlow flow, final int startOffset) {
2006       myFlow = flow;
2007       myStartOffset = startOffset;
2008       writtenVariables = new CopyOnWriteList[myFlow.getSize() + 1];
2009       writtenTwiceVariables = new CopyOnWriteList[myFlow.getSize() + 1];
2010     }
2011
2012     @Override
2013     public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
2014       final int safeNextOffset = Math.min(nextOffset, myFlow.getSize());
2015
2016       CopyOnWriteList writeVars = writtenVariables[safeNextOffset];
2017       CopyOnWriteList writeTwiceVars = writtenTwiceVariables[safeNextOffset];
2018       if (instruction instanceof WriteVariableInstruction) {
2019         final PsiVariable variable = ((WriteVariableInstruction)instruction).variable;
2020
2021         final PsiElement latestWriteVarExpression = getLatestWriteVarExpression(writeVars, variable);
2022
2023         if (latestWriteVarExpression == null) {
2024           final PsiElement expression = getExpression(myFlow.getElement(offset));
2025           writeVars = CopyOnWriteList.add(writeVars, new VariableInfo(variable, expression));
2026         }
2027         else {
2028           writeTwiceVars = CopyOnWriteList.add(writeTwiceVars, new VariableInfo(variable, latestWriteVarExpression));
2029         }
2030       }
2031       merge(offset, writeVars, writtenVariables);
2032       merge(offset, writeTwiceVars, writtenTwiceVariables);
2033     }
2034
2035     @Nullable
2036     private static PsiElement getExpression(@NotNull PsiElement element) {
2037       if (element instanceof PsiAssignmentExpression) {
2038         PsiExpression target = PsiUtil.skipParenthesizedExprDown(((PsiAssignmentExpression)element).getLExpression());
2039         return ObjectUtils.tryCast(target, PsiReferenceExpression.class);
2040       }
2041       if (element instanceof PsiUnaryExpression) {
2042         PsiExpression target = PsiUtil.skipParenthesizedExprDown(((PsiUnaryExpression)element).getOperand());
2043         return ObjectUtils.tryCast(target, PsiReferenceExpression.class);
2044       }
2045       if (element instanceof PsiDeclarationStatement) {
2046         //should not happen
2047         return element;
2048       }
2049       return null;
2050     }
2051
2052     @Nullable
2053     private static PsiElement getLatestWriteVarExpression(@Nullable CopyOnWriteList writeVars, @NotNull PsiVariable variable) {
2054       if (writeVars == null) return null;
2055
2056       for (final VariableInfo variableInfo : writeVars.getList()) {
2057         if (variableInfo.variable == variable) {
2058           return variableInfo.expression;
2059         }
2060       }
2061       return null;
2062     }
2063
2064     @Override
2065     @NotNull
2066     public Collection<VariableInfo> getResult() {
2067       final CopyOnWriteList writtenTwiceVariable = writtenTwiceVariables[myStartOffset];
2068       if (writtenTwiceVariable == null) return Collections.emptyList();
2069       return writtenTwiceVariable.getList();
2070     }
2071   }
2072
2073   /**
2074    * Find locations of writes of variables from writeVars that happened before one of reads of variables from readVars.
2075    *
2076    * @param stopPoint point until which reads are considered
2077    * @return locations of writes
2078    */
2079   @NotNull
2080   public static Map<PsiElement, PsiVariable> getWritesBeforeReads(@NotNull ControlFlow flow,
2081                                                                   @NotNull Set<PsiVariable> writeVars,
2082                                                                   @NotNull Set<PsiVariable> readVars,
2083                                                                   final int stopPoint) {
2084     Map<PsiElement, PsiVariable> writes = new HashMap<>();
2085     List<Instruction> instructions = flow.getInstructions();
2086
2087     for (int i = 0; i < instructions.size(); i++) {
2088       Instruction instruction = instructions.get(i);
2089       if (!(instruction instanceof WriteVariableInstruction)) continue;
2090
2091       PsiVariable writtenVar = ((WriteVariableInstruction)instruction).variable;
2092       if (!writeVars.contains(writtenVar)) continue;
2093
2094       if (readBeforeStopPoint(flow, readVars, i, stopPoint)) writes.put(flow.getElement(i), writtenVar);
2095     }
2096
2097     return writes;
2098   }
2099
2100   /**
2101    * Check if any of given variables was read after start point and before stop point or before next write to this variable.
2102    *
2103    * @return true if it was read
2104    */
2105   private static boolean readBeforeStopPoint(@NotNull final ControlFlow flow,
2106                                              @NotNull Set<PsiVariable> readVars,
2107                                              final int startOffset,
2108                                              final int stopPoint) {
2109     class MyVisitor extends InstructionClientVisitor<Boolean> {
2110
2111       private boolean reachable = false;
2112
2113       @Override
2114       public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
2115
2116         if (offset == stopPoint || isWriteToReadVar(instruction)) {
2117           // since it's dfs if we even already found some reads, they happened after stop point or after reassignment
2118           reachable = false;
2119           return;
2120         }
2121
2122         boolean foundRead = instruction instanceof ReadVariableInstruction &&
2123                             readVars.contains(((ReadVariableInstruction)instruction).variable);
2124
2125         reachable |= foundRead;
2126       }
2127
2128       private boolean isWriteToReadVar(Instruction instruction) {
2129         return instruction instanceof WriteVariableInstruction &&
2130                readVars.contains(((WriteVariableInstruction)instruction).variable);
2131       }
2132
2133       @Override
2134       public Boolean getResult() {
2135         return reachable;
2136       }
2137     }
2138
2139     MyVisitor visitor = new MyVisitor();
2140     depthFirstSearch(flow, visitor, startOffset, flow.getSize());
2141
2142     return visitor.getResult();
2143   }
2144
2145   /**
2146    * @return true if instruction at 'instructionOffset' is reachable from offset 'startOffset'
2147    */
2148   public static boolean isInstructionReachable(@NotNull final ControlFlow flow, final int instructionOffset, final int startOffset) {
2149     return areInstructionsReachable(flow, new int[]{instructionOffset}, startOffset);
2150   }
2151
2152   private static boolean areInstructionsReachable(@NotNull final ControlFlow flow,
2153                                                   @NotNull final int[] instructionOffsets,
2154                                                   final int startOffset) {
2155     class MyVisitor extends InstructionClientVisitor<Boolean> {
2156       private boolean reachable;
2157
2158       @Override
2159       public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
2160         reachable |= ArrayUtil.indexOf(instructionOffsets, nextOffset) >= 0;
2161       }
2162
2163       @Override
2164       @NotNull
2165       public Boolean getResult() {
2166         return reachable;
2167       }
2168     }
2169
2170     if (startOffset != 0 && hasCalls(flow)) {
2171       // Additional computations are required to take into account CALL and RETURN instructions in the case where
2172       // the start offset isn't the beginning of the control flow, because we couldn't know the correct state
2173       // of the call stack if we started traversal of the control flow from an offset in the middle.
2174       return areInstructionsReachableWithCalls(flow, instructionOffsets, startOffset);
2175     }
2176     MyVisitor visitor = new MyVisitor();
2177     depthFirstSearch(flow, visitor, startOffset, flow.getSize());
2178
2179     return visitor.getResult().booleanValue();
2180   }
2181
2182   private static boolean hasCalls(@NotNull ControlFlow flow) {
2183     for (Instruction instruction : flow.getInstructions()) {
2184       if (instruction instanceof CallInstruction) {
2185         return true;
2186       }
2187     }
2188     return false;
2189   }
2190
2191   private abstract static class ControlFlowGraph extends InstructionClientVisitor<Void> {
2192     // The graph is sparse: simple instructions have 1 next offset, branching - 2 next offsets, RETURN may have many (one per call)
2193     final int[][] nextOffsets;
2194
2195     ControlFlowGraph(int size) {
2196       nextOffsets = new int[size][];
2197     }
2198
2199     @Override
2200     public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
2201       if (nextOffset > size()) nextOffset = size();
2202       addArc(offset, nextOffset);
2203     }
2204
2205     void addArc(int offset, int nextOffset) {
2206       if (nextOffsets[offset] == null) {
2207         nextOffsets[offset] = new int[]{nextOffset, -1};
2208       }
2209       else {
2210         int[] targets = nextOffsets[offset];
2211         if (ArrayUtil.indexOf(targets, nextOffset) < 0) {
2212           int freeIndex = ArrayUtil.indexOf(targets, -1);
2213           if (freeIndex >= 0) {
2214             targets[freeIndex] = nextOffset;
2215           }
2216           else {
2217             int oldLength = targets.length;
2218             nextOffsets[offset] = targets = ArrayUtil.realloc(targets, oldLength * 3 / 2);
2219             Arrays.fill(targets, oldLength, targets.length, -1);
2220             targets[oldLength] = nextOffset;
2221           }
2222         }
2223       }
2224     }
2225
2226     @NotNull
2227     int[] getNextOffsets(int offset) {
2228       return nextOffsets[offset] != null ? nextOffsets[offset] : ArrayUtil.EMPTY_INT_ARRAY;
2229     }
2230
2231     int size() {
2232       return nextOffsets.length;
2233     }
2234
2235     @Override
2236     public String toString() {
2237       StringBuilder s = new StringBuilder();
2238       for (int i = 0; i < nextOffsets.length; i++) {
2239         int[] targets = nextOffsets[i];
2240         if (targets != null && targets.length != 0 && targets[0] != -1) {
2241           if (s.length() != 0) s.append(' ');
2242           s.append('(').append(i).append("->");
2243           for (int j = 0; j < targets.length && targets[j] != -1; j++) {
2244             if (j != 0) s.append(",");
2245             s.append(targets[j]);
2246           }
2247           s.append(')');
2248         }
2249       }
2250       return s.toString();
2251     }
2252
2253     boolean depthFirstSearch(final int startOffset) {
2254       return depthFirstSearch(startOffset, new BitSet(size()));
2255     }
2256
2257     boolean depthFirstSearch(final int startOffset, @NotNull BitSet visitedOffsets) {
2258       // traverse the graph starting with the startOffset
2259       IntStack walkThroughStack = new IntStack(Math.max(size() / 2, 2));
2260       visitedOffsets.clear();
2261       walkThroughStack.push(startOffset);
2262       while (!walkThroughStack.empty()) {
2263         int currentOffset = walkThroughStack.pop();
2264         if (currentOffset < size() && !visitedOffsets.get(currentOffset)) {
2265           visitedOffsets.set(currentOffset);
2266           int[] nextOffsets = getNextOffsets(currentOffset);
2267           for (int nextOffset : nextOffsets) {
2268             if (nextOffset == -1) break;
2269             if (isComplete(currentOffset, nextOffset)) {
2270               return true;
2271             }
2272             walkThroughStack.push(nextOffset);
2273           }
2274         }
2275       }
2276       return false;
2277     }
2278
2279     @Override
2280     public Void getResult() {
2281       return null;
2282     }
2283
2284     boolean isComplete(int offset, int nextOffset) {
2285       return false;
2286     }
2287
2288     void buildFrom(@NotNull ControlFlow flow) {
2289       // traverse the whole flow in order to collect the graph edges
2290       ControlFlowUtil.depthFirstSearch(flow, this, 0, flow.getSize());
2291     }
2292   }
2293
2294   private static boolean areInstructionsReachableWithCalls(@NotNull final ControlFlow flow,
2295                                                            @NotNull final int[] instructionOffsets,
2296                                                            final int startOffset) {
2297     ControlFlowGraph graph = new ControlFlowGraph(flow.getSize()) {
2298       @Override
2299       boolean isComplete(int offset, int nextOffset) {
2300         return ArrayUtil.indexOf(instructionOffsets, nextOffset) >= 0;
2301       }
2302     };
2303     graph.buildFrom(flow);
2304     return graph.depthFirstSearch(startOffset);
2305   }
2306
2307   public static boolean isVariableAssignedInLoop(@NotNull PsiReferenceExpression expression, @NotNull PsiElement resolved) {
2308     if (!(expression.getParent() instanceof PsiAssignmentExpression)
2309         || ((PsiAssignmentExpression)expression.getParent()).getLExpression() != expression) {
2310       return false;
2311     }
2312     PsiExpression qualifier = expression.getQualifierExpression();
2313     if (qualifier != null && !(qualifier instanceof PsiThisExpression)) return false;
2314
2315     if (!(resolved instanceof PsiVariable)) return false;
2316     PsiVariable variable = (PsiVariable)resolved;
2317
2318     final PsiElement codeBlock = PsiUtil.getVariableCodeBlock(variable, expression);
2319     if (codeBlock == null) return false;
2320     final ControlFlow flow;
2321     try {
2322       flow = ControlFlowFactory.getInstance(codeBlock.getProject()).getControlFlow(codeBlock, LocalsOrMyInstanceFieldsControlFlowPolicy.getInstance(), true);
2323     }
2324     catch (AnalysisCanceledException e) {
2325       return false;
2326     }
2327     final PsiAssignmentExpression assignmentExpression = (PsiAssignmentExpression)expression.getParent();
2328     int startOffset = flow.getStartOffset(assignmentExpression);
2329     return startOffset != -1 && isInstructionReachable(flow, startOffset, startOffset);
2330   }
2331
2332   static boolean isCaughtExceptionType(@NotNull PsiClassType throwType, @NotNull PsiType catchType) {
2333     return catchType.isAssignableFrom(throwType) || mightBeAssignableFromSubclass(throwType, catchType);
2334   }
2335
2336   private static boolean mightBeAssignableFromSubclass(@NotNull final PsiClassType throwType, @NotNull PsiType catchType) {
2337     if (catchType instanceof PsiDisjunctionType) {
2338       for (PsiType catchDisjunction : ((PsiDisjunctionType)catchType).getDisjunctions()) {
2339         if (throwType.isAssignableFrom(catchDisjunction)) {
2340           return true;
2341         }
2342       }
2343       return false;
2344     }
2345     return throwType.isAssignableFrom(catchType);
2346   }
2347
2348   /**
2349    * Check that in the <code>flow</code> between <code>startOffset</code> and <code>endOffset</code> there are no writes
2350    * to the <code>variables</code> or these writes aren't observable at the <code>locations</code>.
2351    */
2352   public static boolean areVariablesUnmodifiedAtLocations(@NotNull ControlFlow flow,
2353                                                           int startOffset,
2354                                                           int endOffset,
2355                                                           @NotNull Set<? extends PsiVariable> variables,
2356                                                           @NotNull Iterable<? extends PsiElement> locations) {
2357     List<Instruction> instructions = flow.getInstructions();
2358     startOffset = Math.max(startOffset, 0);
2359     endOffset = Math.min(endOffset, instructions.size());
2360
2361     IntArrayList locationOffsetList = new IntArrayList();
2362     for (PsiElement location : locations) {
2363       int offset = flow.getStartOffset(location);
2364       if (offset >= startOffset && offset < endOffset) {
2365         locationOffsetList.add(offset);
2366       }
2367     }
2368     int[] locationOffsets = locationOffsetList.toArray();
2369
2370     for (int offset = startOffset; offset < endOffset; offset++) {
2371       Instruction instruction = instructions.get(offset);
2372       if (instruction instanceof WriteVariableInstruction && variables.contains(((WriteVariableInstruction)instruction).variable)) {
2373         if (areInstructionsReachable(flow, locationOffsets, offset)) {
2374           return false;
2375         }
2376       }
2377     }
2378     return true;
2379   }
2380 }