java/java-impl/src/com/intellij/psi/controlFlow/ControlFlowUtil.java

   1 /*
   2  * Copyright 2000-2009 JetBrains s.r.o.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package com.intellij.psi.controlFlow;
  17
  18 import com.intellij.openapi.diagnostic.Logger;
  19 import com.intellij.psi.*;
  20 import com.intellij.psi.impl.source.DummyHolder;
  21 import com.intellij.psi.util.PsiTreeUtil;
  22 import com.intellij.psi.util.PsiUtil;
  23 import com.intellij.util.IncorrectOperationException;
  24 import com.intellij.util.ReflectionCache;
  25 import com.intellij.util.containers.IntArrayList;
  26 import gnu.trove.THashSet;
  27 import gnu.trove.TIntHashSet;
  28 import org.jetbrains.annotations.NotNull;
  29
  30 import java.util.*;
  31
  32 public class ControlFlowUtil {
  33   private static final Logger LOG = Logger.getInstance("#com.intellij.psi.controlFlow.ControlFlowUtil");
  34
  35   private static class SSAInstructionState implements Cloneable {
  36     private final int myWriteCount;
  37     private final int myInstructionIdx;
  38
  39     public SSAInstructionState(int writeCount, int instructionIdx) {
  40       myWriteCount = writeCount;
  41       myInstructionIdx = instructionIdx;
  42     }
  43
  44     public boolean equals(Object o) {
  45       if (this == o) return true;
  46       if (!(o instanceof SSAInstructionState)) return false;
  47
  48       final SSAInstructionState ssaInstructionState = (SSAInstructionState)o;
  49
  50       if (myInstructionIdx != ssaInstructionState.myInstructionIdx) return false;
  51       if (Math.min(2, myWriteCount) != Math.min(2, ssaInstructionState.myWriteCount)) return false;
  52
  53       return true;
  54     }
  55
  56     public int hashCode() {
  57       int result = Math.min(2, myWriteCount);
  58       result = 29 * result + myInstructionIdx;
  59       return result;
  60     }
  61
  62     public int getWriteCount() {
  63       return myWriteCount;
  64     }
  65
  66     public int getInstructionIdx() {
  67       return myInstructionIdx;
  68     }
  69   }
  70
  71   public static List<PsiVariable> getSSAVariables(ControlFlow flow) {
  72     return getSSAVariables(flow, 0, flow.getSize(), false);
  73   }
  74
  75   public static List<PsiVariable> getSSAVariables(ControlFlow flow, int from, int to,
  76                                               boolean reportVarsIfNonInitializingPathExists) {
  77     List<Instruction> instructions = flow.getInstructions();
  78     Collection<PsiVariable> writtenVariables = getWrittenVariables(flow, from, to, false);
  79     ArrayList<PsiVariable> result = new ArrayList<PsiVariable>(1);
  80
  81     variables:
  82     for (PsiVariable psiVariable : writtenVariables) {
  83
  84       final List<SSAInstructionState> queue = new ArrayList<SSAInstructionState>();
  85       queue.add(new SSAInstructionState(0, from));
  86       Set<SSAInstructionState> processedStates = new THashSet<SSAInstructionState>();
  87
  88       while (!queue.isEmpty()) {
  89         final SSAInstructionState state = queue.remove(0);
  90         if (state.getWriteCount() > 1) continue variables;
  91         if (!processedStates.contains(state)) {
  92           processedStates.add(state);
  93           int i = state.getInstructionIdx();
  94           if (i < to) {
  95             Instruction instruction = instructions.get(i);
  96
  97             if (instruction instanceof ReturnInstruction) {
  98               int[] offsets = ((ReturnInstruction)instruction).getPossibleReturnOffsets();
  99               for (int offset : offsets) {
 100                 queue.add(new SSAInstructionState(state.getWriteCount(), Math.min(offset, to)));
 101               }
 102             }
 103             else if (instruction instanceof GoToInstruction) {
 104               int nextOffset = ((GoToInstruction)instruction).offset;
 105               nextOffset = Math.min(nextOffset, to);
 106               queue.add(new SSAInstructionState(state.getWriteCount(), nextOffset));
 107             }
 108             else if (instruction instanceof ThrowToInstruction) {
 109               int nextOffset = ((ThrowToInstruction)instruction).offset;
 110               nextOffset = Math.min(nextOffset, to);
 111               queue.add(new SSAInstructionState(state.getWriteCount(), nextOffset));
 112             }
 113             else if (instruction instanceof ConditionalGoToInstruction) {
 114               int nextOffset = ((ConditionalGoToInstruction)instruction).offset;
 115               nextOffset = Math.min(nextOffset, to);
 116               queue.add(new SSAInstructionState(state.getWriteCount(), nextOffset));
 117               queue.add(new SSAInstructionState(state.getWriteCount(), i + 1));
 118             }
 119             else if (instruction instanceof ConditionalThrowToInstruction) {
 120               int nextOffset = ((ConditionalThrowToInstruction)instruction).offset;
 121               nextOffset = Math.min(nextOffset, to);
 122               queue.add(new SSAInstructionState(state.getWriteCount(), nextOffset));
 123               queue.add(new SSAInstructionState(state.getWriteCount(), i + 1));
 124             }
 125             else if (instruction instanceof WriteVariableInstruction) {
 126               WriteVariableInstruction write = (WriteVariableInstruction)instruction;
 127               queue.add(new SSAInstructionState(state.getWriteCount() + (write.variable == psiVariable ? 1 : 0), i + 1));
 128             }
 129             else if (instruction instanceof ReadVariableInstruction) {
 130               ReadVariableInstruction read = (ReadVariableInstruction)instruction;
 131               if (read.variable == psiVariable && state.getWriteCount() == 0) continue variables;
 132               queue.add(new SSAInstructionState(state.getWriteCount(), i + 1));
 133             }
 134             else {
 135               queue.add(new SSAInstructionState(state.getWriteCount(), i + 1));
 136             }
 137           }
 138           else if (!reportVarsIfNonInitializingPathExists && state.getWriteCount() == 0) continue variables;
 139         }
 140       }
 141
 142       result.add(psiVariable);
 143     }
 144
 145     return result;
 146   }
 147
 148   private static boolean needVariableValueAt(final PsiVariable variable, final ControlFlow flow, final int offset) {
 149     InstructionClientVisitor<Boolean> visitor = new InstructionClientVisitor<Boolean>() {
 150       final boolean[] neededBelow = new boolean[flow.getSize()+1];
 151
 152       @Override
 153       public void procedureEntered(int startOffset, int endOffset) {
 154         for (int i = startOffset; i < endOffset; i++) neededBelow[i] = false;
 155       }
 156
 157       @Override public void visitReadVariableInstruction(ReadVariableInstruction instruction, int offset, int nextOffset) {
 158         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 159         boolean needed = neededBelow[nextOffset];
 160         if (instruction.variable.equals(variable)) {
 161            needed = true;
 162         }
 163         neededBelow[offset] |= needed;
 164       }
 165
 166       @Override public void visitWriteVariableInstruction(WriteVariableInstruction instruction, int offset, int nextOffset) {
 167         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 168         boolean needed = neededBelow[nextOffset];
 169         if (instruction.variable.equals(variable)) {
 170           needed = false;
 171         }
 172         neededBelow[offset] = needed;
 173       }
 174
 175       @Override public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
 176         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 177         boolean needed = neededBelow[nextOffset];
 178         neededBelow[offset] |= needed;
 179       }
 180
 181       public Boolean getResult() {
 182         return neededBelow[offset];
 183       }
 184     };
 185     depthFirstSearch(flow, visitor, offset, flow.getSize());
 186     return visitor.getResult().booleanValue();
 187   }
 188
 189   public static Collection<PsiVariable> getWrittenVariables(ControlFlow flow, int start, int end, final boolean ignoreNotReachingWrites) {
 190     Set<PsiVariable> set = new HashSet<PsiVariable>();
 191     List<Instruction> instructions = flow.getInstructions();
 192     for (int i = start; i < end; i++) {
 193       Instruction instruction = instructions.get(i);
 194       if (instruction instanceof WriteVariableInstruction && (!ignoreNotReachingWrites || isInstructionReachable(flow, end, i))) {
 195         set.add(((WriteVariableInstruction)instruction).variable);
 196       }
 197     }
 198     return set;
 199   }
 200
 201   public static List<PsiVariable> getUsedVariables(ControlFlow flow, int start, int end) {
 202     ArrayList<PsiVariable> array = new ArrayList<PsiVariable>();
 203     List<Instruction> instructions = flow.getInstructions();
 204     for (int i = start; i < end; i++) {
 205       Instruction instruction = instructions.get(i);
 206       if (instruction instanceof ReadVariableInstruction) {
 207         PsiVariable variable = ((ReadVariableInstruction)instruction).variable;
 208         if (!array.contains(variable)) {
 209           array.add(variable);
 210         }
 211       }
 212       else if (instruction instanceof WriteVariableInstruction) {
 213         PsiVariable variable = ((WriteVariableInstruction)instruction).variable;
 214         if (!array.contains(variable)) {
 215           array.add(variable);
 216         }
 217       }
 218     }
 219     return array;
 220   }
 221
 222   public static List<PsiVariable> getInputVariables(ControlFlow flow, int start, int end) {
 223     List<PsiVariable> usedVariables = getUsedVariables(flow, start, end);
 224     ArrayList<PsiVariable> array = new ArrayList<PsiVariable>(usedVariables.size());
 225     for (PsiVariable variable : usedVariables) {
 226       if (needVariableValueAt(variable, flow, start)) {
 227         array.add(variable);
 228       }
 229     }
 230     return array;
 231   }
 232
 233   public static PsiVariable[] getOutputVariables(ControlFlow flow, int start, int end, int[] exitPoints) {
 234     Collection<PsiVariable> writtenVariables = getWrittenVariables(flow, start, end, false);
 235     ArrayList<PsiVariable> array = new ArrayList<PsiVariable>();
 236     for (PsiVariable variable : writtenVariables) {
 237       for (int exitPoint : exitPoints) {
 238         if (needVariableValueAt(variable, flow, exitPoint)) {
 239           array.add(variable);
 240         }
 241       }
 242     }
 243     PsiVariable[] outputVariables = array.toArray(new PsiVariable[array.size()]);
 244     if (LOG.isDebugEnabled()) {
 245       LOG.debug("output variables:");
 246       for (PsiVariable variable : outputVariables) {
 247         LOG.debug("  " + variable.toString());
 248       }
 249     }
 250     return outputVariables;
 251   }
 252
 253   public static Collection<PsiStatement> findExitPointsAndStatements(final ControlFlow flow, final int start, final int end, final IntArrayList exitPoints,
 254                                                                      final Class... classesFilter) {
 255     if (end == start) {
 256       exitPoints.add(end);
 257       return Collections.emptyList();
 258     }
 259     final Collection<PsiStatement> exitStatements = new THashSet<PsiStatement>();
 260     InstructionClientVisitor visitor = new InstructionClientVisitor() {
 261       @Override public void visitThrowToInstruction(ThrowToInstruction instruction, int offset, int nextOffset) {
 262         //[ven]This is a hack since Extract Method doesn't want to see throw's exit points
 263         processGotoStatement(classesFilter, exitStatements, findStatement(flow, offset));
 264       }
 265
 266       @Override public void visitBranchingInstruction(BranchingInstruction instruction, int offset, int nextOffset) {
 267         processGoto(flow, start, end, exitPoints, exitStatements, instruction.offset, classesFilter, findStatement(flow, offset));
 268       }
 269
 270       // call/return do not incur exit points
 271       @Override public void visitReturnInstruction(ReturnInstruction instruction, int offset, int nextOffset) {
 272       }
 273       @Override public void visitCallInstruction(CallInstruction instruction, int offset, int nextOffset) {
 274       }
 275
 276       @Override public void visitConditionalThrowToInstruction(ConditionalThrowToInstruction instruction, int offset, int nextOffset) {
 277         visitInstruction(instruction, offset, nextOffset);
 278       }
 279
 280       @Override public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
 281         if (offset >= end - 1) {
 282           int exitOffset = end;
 283           exitOffset = promoteThroughGotoChain(flow, exitOffset);
 284           if (!exitPoints.contains(exitOffset)) {
 285             exitPoints.add(exitOffset);
 286           }
 287         }
 288       }
 289
 290       public Object getResult() {
 291         return null;
 292       }
 293     };
 294     depthFirstSearch(flow, visitor, start, end);
 295     return exitStatements;
 296   }
 297
 298   private static void processGoto(ControlFlow flow, int start, int end,
 299                                   IntArrayList exitPoints,
 300                                   Collection<PsiStatement> exitStatements, int gotoOffset, Class[] classesFilter, final PsiStatement statement) {
 301     if (statement == null) return;
 302     if (start > gotoOffset || gotoOffset >= end || isElementOfClass(statement, classesFilter)) {
 303       // process chain of goto's
 304       gotoOffset = promoteThroughGotoChain(flow, gotoOffset);
 305
 306       if (!exitPoints.contains(gotoOffset) && (gotoOffset >= end || gotoOffset < start)) {
 307         exitPoints.add(gotoOffset);
 308       }
 309       processGotoStatement(classesFilter, exitStatements, statement);
 310     }
 311   }
 312
 313   private static void processGotoStatement(Class[] classesFilter, Collection<PsiStatement> exitStatements, PsiStatement statement) {
 314     if (statement != null && isElementOfClass(statement, classesFilter)) {
 315       exitStatements.add(statement);
 316     }
 317   }
 318
 319   private static boolean isElementOfClass(PsiElement element, Class[] classesFilter) {
 320     if (classesFilter == null) return true;
 321     for (Class aClassesFilter : classesFilter) {
 322       if (ReflectionCache.isAssignable(aClassesFilter, element.getClass())) {
 323         return true;
 324       }
 325     }
 326     return false;
 327   }
 328
 329   private static int promoteThroughGotoChain(ControlFlow flow, int offset) {
 330     List<Instruction> instructions = flow.getInstructions();
 331     while (true) {
 332       if (offset >= instructions.size()) break;
 333       Instruction instruction = instructions.get(offset);
 334       if (!(instruction instanceof GoToInstruction) || ((GoToInstruction)instruction).isReturn) break;
 335       offset = ((BranchingInstruction)instruction).offset;
 336     }
 337     return offset;
 338   }
 339
 340   public static final Class[] DEFAULT_EXIT_STATEMENTS_CLASSES = new Class[] {PsiReturnStatement.class, PsiBreakStatement.class, PsiContinueStatement.class};
 341
 342   private static PsiStatement findStatement(ControlFlow flow, int offset) {
 343     PsiElement element = flow.getElement(offset);
 344     return PsiTreeUtil.getParentOfType(element, PsiStatement.class, false);
 345   }
 346
 347   public static PsiElement findCodeFragment(PsiElement element) {
 348     PsiElement codeFragment = element;
 349     PsiElement parent = codeFragment.getParent();
 350     while (parent != null) {
 351       if (parent instanceof PsiDirectory
 352           || parent instanceof PsiMethod
 353           || parent instanceof PsiField || parent instanceof PsiClassInitializer
 354           || parent instanceof DummyHolder) {
 355         break;
 356       }
 357       codeFragment = parent;
 358       parent = parent.getParent();
 359     }
 360     return codeFragment;
 361   }
 362
 363   private static boolean checkReferenceExpressionScope(final PsiReferenceExpression ref, @NotNull PsiElement targetClassMember) {
 364     final JavaResolveResult resolveResult = ref.advancedResolve(false);
 365     final PsiElement def = resolveResult.getElement();
 366     if (def != null) {
 367       PsiElement parent = def.getParent();
 368       PsiElement commonParent = parent == null ? null : PsiTreeUtil.findCommonParent(parent, targetClassMember);
 369       if (commonParent == null) {
 370         parent = resolveResult.getCurrentFileResolveScope();
 371       }
 372       if (parent instanceof PsiClass) {
 373         final PsiClass clss = (PsiClass)parent;
 374         if (PsiTreeUtil.isAncestor(targetClassMember, clss, false)) return false;
 375       }
 376     }
 377
 378     return true;
 379   }
 380
 381   /**
 382    * Checks possibility of extracting code fragment outside containing anonymous (local) class.
 383    * Also collects variables to be passed as additional parameters.
 384    * @return true if code fragement can be extracted outside
 385    * @param array Vector to collect variables to be passed as additional parameters
 386    * @param scope scope to be scanned (part of code fragement to be extracted)
 387    * @param member member containing the code to be extracted
 388    * @param targetClassMember member in target class containing code fragement
 389    */
 390   public static boolean collectOuterLocals(List<PsiVariable> array, PsiElement scope, PsiElement member,
 391                                            PsiElement targetClassMember) {
 392     if (scope instanceof PsiMethodCallExpression) {
 393       final PsiMethodCallExpression call = (PsiMethodCallExpression)scope;
 394       if (!checkReferenceExpressionScope (call.getMethodExpression(), targetClassMember)) {
 395         return false;
 396       }
 397     }
 398     else if (scope instanceof PsiReferenceExpression) {
 399       if (!checkReferenceExpressionScope ((PsiReferenceExpression)scope, targetClassMember)) {
 400         return false;
 401       }
 402     }
 403
 404     if (scope instanceof PsiJavaCodeReferenceElement) {
 405
 406       final PsiJavaCodeReferenceElement ref = (PsiJavaCodeReferenceElement)scope;
 407       final JavaResolveResult result = ref.advancedResolve(false);
 408       final PsiElement refElement = result.getElement();
 409
 410       if (refElement != null) {
 411
 412         PsiElement parent = PsiTreeUtil.findCommonParent(refElement.getParent(), member);
 413         if (parent == null) {
 414           parent = result.getCurrentFileResolveScope();
 415         }
 416
 417         if (parent != null && !member.equals(parent)) { // not local in member
 418           parent = PsiTreeUtil.findCommonParent(parent, targetClassMember);
 419           if (targetClassMember.equals(parent)) { //something in anonymous class
 420             if (refElement instanceof PsiVariable) {
 421               if (scope instanceof PsiReferenceExpression &&
 422                   PsiUtil.isAccessedForWriting((PsiReferenceExpression)scope)) {
 423                 return false;
 424               }
 425               PsiVariable variable = (PsiVariable)refElement;
 426               if (!array.contains(variable)) {
 427                 array.add(variable);
 428               }
 429             }
 430             else {
 431               return false;
 432             }
 433           }
 434         }
 435       }
 436     }
 437     else if (scope instanceof PsiThisExpression) {
 438       PsiJavaCodeReferenceElement qualifier = ((PsiThisExpression)scope).getQualifier();
 439       if (qualifier == null) {
 440         return false;
 441       }
 442     }
 443     else if (scope instanceof PsiSuperExpression) {
 444       if (((PsiSuperExpression)scope).getQualifier() == null) {
 445         return false;
 446       }
 447     }
 448
 449     for (PsiElement child = scope.getFirstChild(); child != null; child = child.getNextSibling()) {
 450       if (!collectOuterLocals(array, child, member, targetClassMember)) return false;
 451     }
 452     return true;
 453   }
 454
 455
 456   /**
 457    * @return true if each control flow path results in return statement or exception thrown
 458    */
 459   public static boolean returnPresent(final ControlFlow flow) {
 460     InstructionClientVisitor<Boolean> visitor = new ReturnPresentClientVisitor(flow);
 461
 462     depthFirstSearch(flow, visitor);
 463     return visitor.getResult().booleanValue();
 464   }
 465
 466   public static boolean checkReturns(final ControlFlow flow, final ReturnStatementsVisitor afterVisitor) throws IncorrectOperationException {
 467     final ConvertReturnClientVisitor instructionsVisitor = new ConvertReturnClientVisitor(flow, afterVisitor);
 468
 469     depthFirstSearch(flow, instructionsVisitor);
 470
 471     instructionsVisitor.afterProcessing();
 472     return instructionsVisitor.getResult().booleanValue();
 473   }
 474
 475   private static class ConvertReturnClientVisitor extends ReturnPresentClientVisitor {
 476     private final List<PsiReturnStatement> myAffectedReturns;
 477     private final ReturnStatementsVisitor myVisitor;
 478
 479     ConvertReturnClientVisitor(final ControlFlow flow, final ReturnStatementsVisitor visitor) {
 480       super(flow);
 481       myAffectedReturns = new ArrayList<PsiReturnStatement>();
 482       myVisitor = visitor;
 483     }
 484
 485     public void visitGoToInstruction(final GoToInstruction instruction, final int offset, final int nextOffset) {
 486       super.visitGoToInstruction(instruction, offset, nextOffset);
 487
 488       if (instruction.isReturn) {
 489         final PsiElement element = myFlow.getElement(offset);
 490         if (element instanceof PsiReturnStatement) {
 491           final PsiReturnStatement returnStatement = (PsiReturnStatement) element;
 492           myAffectedReturns.add(returnStatement);
 493         }
 494       }
 495     }
 496
 497     public void afterProcessing() throws IncorrectOperationException {
 498       myVisitor.visit(myAffectedReturns);
 499     }
 500   }
 501
 502   private static class ReturnPresentClientVisitor extends InstructionClientVisitor<Boolean> {
 503     // false if control flow at this offset terminates either by return called or exception thrown
 504     private final boolean[] isNormalCompletion;
 505     protected final ControlFlow myFlow;
 506
 507     public ReturnPresentClientVisitor(ControlFlow flow) {
 508       myFlow = flow;
 509       isNormalCompletion = new boolean[myFlow.getSize() + 1];
 510       isNormalCompletion[myFlow.getSize()] = true;
 511     }
 512
 513     @Override public void visitConditionalThrowToInstruction(ConditionalThrowToInstruction instruction, int offset, int nextOffset) {
 514       if (nextOffset > myFlow.getSize()) nextOffset = myFlow.getSize();
 515       boolean isNormal = instruction.offset == nextOffset && nextOffset != offset + 1 ?
 516                   !isLeaf(nextOffset) && isNormalCompletion[nextOffset] :
 517                   isLeaf(nextOffset) || isNormalCompletion[nextOffset];
 518
 519       isNormalCompletion[offset] |= isNormal;
 520     }
 521
 522     @Override public void visitThrowToInstruction(ThrowToInstruction instruction, int offset, int nextOffset) {
 523       if (nextOffset > myFlow.getSize()) nextOffset = myFlow.getSize();
 524       isNormalCompletion[offset] |= !isLeaf(nextOffset) && isNormalCompletion[nextOffset];
 525     }
 526
 527     @Override public void visitGoToInstruction(GoToInstruction instruction, int offset, int nextOffset) {
 528       if (nextOffset > myFlow.getSize()) nextOffset = myFlow.getSize();
 529       isNormalCompletion[offset] |= !instruction.isReturn && isNormalCompletion[nextOffset];
 530     }
 531
 532     @Override public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
 533       if (nextOffset > myFlow.getSize()) nextOffset = myFlow.getSize();
 534
 535       boolean isNormal = isLeaf(nextOffset) || isNormalCompletion[nextOffset];
 536       isNormalCompletion[offset] |= isNormal;
 537     }
 538
 539     public Boolean getResult() {
 540       return !isNormalCompletion[0];
 541     }
 542   }
 543
 544   public static boolean returnPresentBetween(final ControlFlow flow, final int startOffset, final int endOffset) {
 545     class MyVisitor extends InstructionClientVisitor<Boolean> {
 546       // false if control flow at this offset terminates either by return called or exception thrown
 547       final boolean[] isNormalCompletion = new boolean[flow.getSize() + 1];
 548
 549       public MyVisitor() {
 550         int i;
 551         final int length = flow.getSize();
 552         for (i = 0; i < startOffset; i++) {
 553           isNormalCompletion[i] = true;
 554         }
 555         for (i = endOffset; i <= length; i++) {
 556           isNormalCompletion[i] = true;
 557         }
 558       }
 559
 560       @Override public void visitConditionalThrowToInstruction(ConditionalThrowToInstruction instruction, int offset, int nextOffset) {
 561         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 562         if (offset > endOffset) return;
 563         int throwToOffset = instruction.offset;
 564         boolean isNormal;
 565         if (throwToOffset == nextOffset) {
 566           if (throwToOffset <= endOffset) {
 567             isNormal = !isLeaf(nextOffset) && isNormalCompletion[nextOffset];
 568           }
 569           else {
 570             return;
 571           }
 572         }
 573         else {
 574           isNormal = isLeaf(nextOffset) || isNormalCompletion[nextOffset];
 575         }
 576         isNormalCompletion[offset] |= isNormal;
 577       }
 578
 579       @Override public void visitThrowToInstruction(ThrowToInstruction instruction, int offset, int nextOffset) {
 580         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 581         if (offset > endOffset) return;
 582         if (nextOffset <= endOffset) {
 583           boolean isNormal = !isLeaf(nextOffset) && isNormalCompletion[nextOffset];
 584           isNormalCompletion[offset] |= isNormal;
 585         }
 586       }
 587
 588       @Override public void visitCallInstruction(CallInstruction instruction, int offset, int nextOffset) {
 589         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 590         if (offset > endOffset) return;
 591         if (nextOffset > endOffset && nextOffset != offset + 1) {
 592           return;
 593         }
 594         boolean isNormal = isNormalCompletion[nextOffset];
 595         isNormalCompletion[offset] |= isNormal;
 596       }
 597
 598       @Override public void visitGoToInstruction(GoToInstruction instruction, int offset, int nextOffset) {
 599         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 600         if (offset > endOffset) return;
 601         boolean isRethrowFromFinally = instruction instanceof ReturnInstruction && ((ReturnInstruction) instruction).isRethrowFromFinally();
 602         boolean isNormal = !instruction.isReturn && isNormalCompletion[nextOffset] && !isRethrowFromFinally;
 603         isNormalCompletion[offset] |= isNormal;
 604       }
 605
 606       @Override public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
 607         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 608         if (offset > endOffset) return;
 609         final boolean isNormal = isLeaf(nextOffset) || isNormalCompletion[nextOffset];
 610         isNormalCompletion[offset] |= isNormal;
 611       }
 612
 613       public Boolean getResult() {
 614         return !isNormalCompletion[startOffset];
 615       }
 616     }
 617     final MyVisitor visitor = new MyVisitor();
 618     depthFirstSearch(flow, visitor, startOffset, endOffset);
 619     return visitor.getResult().booleanValue();
 620   }
 621
 622   public static Object[] getAllWorldProblemsAtOnce(final ControlFlow flow) {
 623     InstructionClientVisitor[] visitors = new InstructionClientVisitor[]{
 624       new ReturnPresentClientVisitor(flow),
 625       new UnreachableStatementClientVisitor(flow),
 626       new ReadBeforeWriteClientVisitor(flow),
 627       new InitializedTwiceClientVisitor(flow, 0),
 628     };
 629     CompositeInstructionClientVisitor visitor = new CompositeInstructionClientVisitor(visitors);
 630     depthFirstSearch(flow, visitor);
 631     return visitor.getResult();
 632   }
 633
 634   /**
 635    * returns true iff exists controlflow path completing normally, i.e. not resulting in return,break,continue or exception thrown.
 636    * In other words, if we add instruction after controlflow specified, it should be reachable
 637    */
 638   public static boolean canCompleteNormally(final ControlFlow flow, final int startOffset, final int endOffset) {
 639     class MyVisitor extends InstructionClientVisitor<Boolean> {
 640       // false if control flow at this offset terminates abruptly
 641       final boolean[] canCompleteNormally = new boolean[flow.getSize() + 1];
 642
 643       @Override public void visitConditionalGoToInstruction(ConditionalGoToInstruction instruction, int offset, int nextOffset) {
 644         checkInstruction(offset, nextOffset, false);
 645       }
 646       @Override public void visitGoToInstruction(GoToInstruction instruction, int offset, int nextOffset) {
 647         checkInstruction(offset, nextOffset, instruction.isReturn);
 648       }
 649
 650       private void checkInstruction(int offset, int nextOffset, boolean isReturn) {
 651         if (offset > endOffset) return;
 652         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 653         boolean isNormal = nextOffset <= endOffset && !isReturn && (nextOffset == endOffset || canCompleteNormally[nextOffset]);
 654         if (isNormal && nextOffset == endOffset) {
 655           PsiElement element = flow.getElement(offset);
 656           if (element instanceof PsiBreakStatement || element instanceof PsiContinueStatement) {
 657             isNormal = false;
 658           }
 659         }
 660         canCompleteNormally[offset] |= isNormal;
 661       }
 662
 663       @Override public void visitConditionalThrowToInstruction(ConditionalThrowToInstruction instruction, int offset, int nextOffset) {
 664         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 665         if (offset > endOffset) return;
 666         int throwToOffset = instruction.offset;
 667         boolean isNormal;
 668         if (throwToOffset == nextOffset) {
 669           isNormal = throwToOffset <= endOffset && !isLeaf(nextOffset) && canCompleteNormally[nextOffset];
 670         }
 671         else {
 672           isNormal = canCompleteNormally[nextOffset];
 673         }
 674         canCompleteNormally[offset] |= isNormal;
 675       }
 676
 677       @Override public void visitThrowToInstruction(ThrowToInstruction instruction, int offset, int nextOffset) {
 678         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 679         if (offset > endOffset) return;
 680         if (nextOffset <= endOffset) {
 681           boolean isNormal = !isLeaf(nextOffset) && canCompleteNormally[nextOffset];
 682           canCompleteNormally[offset] |= isNormal;
 683         }
 684       }
 685
 686       @Override public void visitCallInstruction(CallInstruction instruction, int offset, int nextOffset) {
 687         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 688         if (offset > endOffset) return;
 689         if (nextOffset > endOffset && nextOffset != offset + 1) {
 690           return;
 691         }
 692         boolean isNormal = canCompleteNormally[nextOffset];
 693         canCompleteNormally[offset] |= isNormal;
 694       }
 695
 696       @Override public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
 697         checkInstruction(offset, nextOffset, false);
 698       }
 699
 700       public Boolean getResult() {
 701         return canCompleteNormally[startOffset];
 702       }
 703     }
 704     final MyVisitor visitor = new MyVisitor();
 705     depthFirstSearch(flow, visitor, startOffset, endOffset);
 706     return visitor.getResult().booleanValue();
 707   }
 708
 709   /**
 710    * @return any unreachable statement or null
 711    */
 712   public static PsiElement getUnreachableStatement(final ControlFlow flow) {
 713     final InstructionClientVisitor<PsiElement> visitor = new UnreachableStatementClientVisitor(flow);
 714     depthFirstSearch(flow, visitor);
 715     return visitor.getResult();
 716   }
 717   private static class UnreachableStatementClientVisitor extends InstructionClientVisitor<PsiElement> {
 718     private final ControlFlow myFlow;
 719
 720     public UnreachableStatementClientVisitor(ControlFlow flow) {
 721       myFlow = flow;
 722     }
 723
 724     public PsiElement getResult() {
 725       for (int i = 0; i < processedInstructions.length; i++) {
 726         if (!processedInstructions[i]) {
 727           PsiElement element = myFlow.getElement(i);
 728           if (element == null || !PsiUtil.isStatement(element)) continue;
 729           if (element.getParent() instanceof PsiExpression) continue;
 730
 731           // ignore for(;;) statement unreachable update
 732           while (element instanceof PsiExpression) {
 733             element = element.getParent();
 734           }
 735           if (element instanceof PsiStatement
 736               && element.getParent() instanceof PsiForStatement
 737               && element == ((PsiForStatement) element.getParent()).getUpdate()) {
 738             continue;
 739           }
 740           //filter out generated stmts
 741           final int endOffset = myFlow.getEndOffset(element);
 742           if (endOffset != i + 1) continue;
 743           final int startOffset = myFlow.getStartOffset(element);
 744           // this offset actually is a part of reachable statement
 745           if (0 <= startOffset && startOffset < processedInstructions.length && processedInstructions[startOffset]) continue;
 746           return element;
 747         }
 748       }
 749       return null;
 750     }
 751   }
 752
 753   private static PsiReferenceExpression getEnclosingReferenceExpression(PsiElement element, PsiVariable variable) {
 754     final PsiReferenceExpression reference = findReferenceTo(element, variable);
 755     if (reference != null) return reference;
 756     while (element != null) {
 757       if (element instanceof PsiReferenceExpression) {
 758         return (PsiReferenceExpression)element;
 759       }
 760       else if (element instanceof PsiMethod || element instanceof PsiClass) {
 761         return null;
 762       }
 763       element = element.getParent();
 764     }
 765     return null;
 766   }
 767
 768   private static PsiReferenceExpression findReferenceTo(PsiElement element, PsiVariable variable) {
 769     if (element instanceof PsiReferenceExpression
 770         && ((PsiReferenceExpression)element).resolve() == variable) {
 771       return (PsiReferenceExpression)element;
 772     }
 773     final PsiElement[] children = element.getChildren();
 774     for (PsiElement child : children) {
 775       final PsiReferenceExpression reference = findReferenceTo(child, variable);
 776       if (reference != null) return reference;
 777     }
 778     return null;
 779   }
 780
 781
 782   public static boolean isVariableDefinitelyAssigned(final PsiVariable variable, final ControlFlow flow) {
 783     class MyVisitor extends InstructionClientVisitor<Boolean> {
 784       // true if from this point below there may be branch with no variable assignment
 785       final boolean[] maybeUnassigned = new boolean[flow.getSize() + 1];
 786       {
 787         maybeUnassigned[maybeUnassigned.length-1] = true;
 788       }
 789
 790       @Override public void visitWriteVariableInstruction(WriteVariableInstruction instruction, int offset, int nextOffset) {
 791         if (instruction.variable == variable) {
 792           maybeUnassigned[offset] = false;
 793         }
 794         else {
 795           visitInstruction(instruction, offset, nextOffset);
 796         }
 797       }
 798
 799       @Override public void visitConditionalThrowToInstruction(ConditionalThrowToInstruction instruction, int offset, int nextOffset) {
 800         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 801         boolean unassigned = offset == flow.getSize() - 1
 802                              || !isLeaf(nextOffset) && maybeUnassigned[nextOffset];
 803
 804         maybeUnassigned[offset] |= unassigned;
 805       }
 806
 807       @Override public void visitCallInstruction(CallInstruction instruction, int offset, int nextOffset) {
 808         visitInstruction(instruction, offset, nextOffset);
 809         // clear return statements after procedure as well
 810         for (int i = instruction.procBegin; i<instruction.procEnd+3;i++) {
 811           maybeUnassigned[i] = false;
 812         }
 813       }
 814
 815       @Override public void visitThrowToInstruction(ThrowToInstruction instruction, int offset, int nextOffset) {
 816         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 817         boolean unassigned = !isLeaf(nextOffset) && maybeUnassigned[nextOffset];
 818         maybeUnassigned[offset] |= unassigned;
 819       }
 820
 821       @Override public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
 822         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 823
 824         boolean unassigned = isLeaf(nextOffset) || maybeUnassigned[nextOffset];
 825         maybeUnassigned[offset] |= unassigned;
 826       }
 827
 828       public Boolean getResult() {
 829         return !maybeUnassigned[0];
 830       }
 831     }
 832     if (flow.getSize() == 0) return false;
 833     MyVisitor visitor = new MyVisitor();
 834     depthFirstSearch(flow, visitor);
 835     return visitor.getResult().booleanValue();
 836   }
 837
 838   public static boolean isVariableDefinitelyNotAssigned(final PsiVariable variable, final ControlFlow flow) {
 839     class MyVisitor extends InstructionClientVisitor<Boolean> {
 840       // true if from this point below there may be branch with variable assignment
 841       final boolean[] maybeAssigned = new boolean[flow.getSize() + 1];
 842
 843       @Override public void visitWriteVariableInstruction(WriteVariableInstruction instruction, int offset, int nextOffset) {
 844         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 845         boolean assigned = instruction.variable == variable || maybeAssigned[nextOffset];
 846         maybeAssigned[offset] |= assigned;
 847       }
 848
 849       @Override public void visitThrowToInstruction(ThrowToInstruction instruction, int offset, int nextOffset) {
 850         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 851         boolean assigned = !isLeaf(nextOffset) && maybeAssigned[nextOffset];
 852         maybeAssigned[offset] |= assigned;
 853       }
 854
 855       @Override public void visitConditionalThrowToInstruction(ConditionalThrowToInstruction instruction, int offset, int nextOffset) {
 856         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 857         int throwToOffset = instruction.offset;
 858         boolean assigned = throwToOffset == nextOffset ? !isLeaf(nextOffset) && maybeAssigned[nextOffset] :
 859                     maybeAssigned[nextOffset];
 860         maybeAssigned[offset] |= assigned;
 861       }
 862
 863       @Override public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
 864         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 865
 866         boolean assigned = maybeAssigned[nextOffset];
 867
 868         maybeAssigned[offset] |= assigned;
 869       }
 870
 871       public Boolean getResult() {
 872         return !maybeAssigned[0];
 873       }
 874     }
 875     MyVisitor visitor = new MyVisitor();
 876     depthFirstSearch(flow, visitor);
 877     return visitor.getResult().booleanValue();
 878   }
 879
 880   /**
 881    * @return min offset after sourceOffset which is definitely reachable from all references
 882    */
 883   public static int getMinDefinitelyReachedOffset(final ControlFlow flow, final int sourceOffset,
 884                                                   final List references) {
 885     class MyVisitor extends InstructionClientVisitor<Integer> {
 886       // set of exit posint reached from this offset
 887       final TIntHashSet[] exitPoints = new TIntHashSet[flow.getSize()];
 888
 889       @Override public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
 890         if (nextOffset > flow.getSize()) nextOffset = flow.getSize();
 891
 892         if (exitPoints[offset] == null) {
 893           exitPoints[offset] = new TIntHashSet();
 894         }
 895         if (isLeaf(nextOffset)) {
 896           exitPoints[offset].add(offset);
 897         }
 898         else {
 899           exitPoints[offset].addAll(exitPoints[nextOffset].toArray());
 900         }
 901       }
 902
 903       public Integer getResult() {
 904         int minOffset = flow.getSize();
 905         int maxExitPoints = 0;
 906         nextOffset:
 907         for (int i = sourceOffset; i < exitPoints.length; i++) {
 908           TIntHashSet exitPointSet = exitPoints[i];
 909           final int size = exitPointSet == null ? 0 : exitPointSet.size();
 910           if (size > maxExitPoints) {
 911             // this offset should be reachable from all other references
 912             for (Object reference : references) {
 913               PsiElement element = (PsiElement)reference;
 914               final PsiElement statement = PsiUtil.getEnclosingStatement(element);
 915               if (statement == null) continue;
 916               final int endOffset = flow.getEndOffset(statement);
 917               if (endOffset == -1) continue;
 918               if (i != endOffset && !isInstructionReachable(flow, i, endOffset)) continue nextOffset;
 919             }
 920             minOffset = i;
 921             maxExitPoints = size;
 922           }
 923         }
 924         return minOffset;
 925       }
 926     }
 927     MyVisitor visitor = new MyVisitor();
 928     depthFirstSearch(flow, visitor);
 929     return visitor.getResult().intValue();
 930   }
 931
 932   private static void depthFirstSearch(ControlFlow flow, InstructionClientVisitor visitor) {
 933     depthFirstSearch(flow, visitor, 0, flow.getSize());
 934   }
 935
 936   private static void depthFirstSearch(ControlFlow flow, InstructionClientVisitor visitor, int startOffset, int endOffset) {
 937     visitor.processedInstructions = new boolean[endOffset];
 938     internalDepthFirstSearch(flow.getInstructions(), visitor, startOffset, endOffset);
 939   }
 940
 941   private static void internalDepthFirstSearch(final List<Instruction> instructions, final InstructionClientVisitor clientVisitor, int offset, int endOffset) {
 942     final IntArrayList oldOffsets = new IntArrayList(instructions.size() / 2);
 943     final IntArrayList newOffsets = new IntArrayList(instructions.size() / 2);
 944
 945     oldOffsets.add(offset);
 946     newOffsets.add(-1);
 947
 948     // we can change instruction internal state here (e.g. CallInstruction.stack)
 949     synchronized (instructions) {
 950       final IntArrayList currentProcedureReturnOffsets = new IntArrayList();
 951       ControlFlowInstructionVisitor getNextOffsetVisitor = new ControlFlowInstructionVisitor() {
 952         @Override public void visitCallInstruction(CallInstruction instruction, int offset, int nextOffset) {
 953           instruction.execute(offset + 1);
 954           int newOffset = instruction.offset;
 955           // 'procedure' pointed by call instruction should be processed regardless of whether it was already visited or not
 956           // clear procedure text and return instructions aftewards
 957           int i;
 958           for (i = instruction.procBegin; i < instruction.procEnd || instructions.get(i) instanceof ReturnInstruction; i++) {
 959             clientVisitor.processedInstructions[i] = false;
 960           }
 961           clientVisitor.procedureEntered(instruction.procBegin, i);
 962           oldOffsets.add(offset);
 963           newOffsets.add(newOffset);
 964
 965           oldOffsets.add(newOffset);
 966           newOffsets.add(-1);
 967
 968           currentProcedureReturnOffsets.add(offset + 1);
 969         }
 970
 971         @Override public void visitReturnInstruction(ReturnInstruction instruction, int offset, int nextOffset) {
 972           int newOffset = instruction.execute(false);
 973           if (newOffset != -1) {
 974             oldOffsets.add(offset);
 975             newOffsets.add(newOffset);
 976
 977             oldOffsets.add(newOffset);
 978             newOffsets.add(-1);
 979           }
 980         }
 981
 982         @Override public void visitBranchingInstruction(BranchingInstruction instruction, int offset, int nextOffset) {
 983           int newOffset = instruction.offset;
 984           oldOffsets.add(offset);
 985           newOffsets.add(newOffset);
 986
 987           oldOffsets.add(newOffset);
 988           newOffsets.add(-1);
 989         }
 990
 991         @Override public void visitConditionalBranchingInstruction(ConditionalBranchingInstruction instruction, int offset, int nextOffset) {
 992           int newOffset = instruction.offset;
 993
 994           oldOffsets.add(offset);
 995           newOffsets.add(newOffset);
 996
 997           oldOffsets.add(offset);
 998           newOffsets.add(offset + 1);
 999
1000           oldOffsets.add(newOffset);
1001           newOffsets.add(-1);
1002
1003           oldOffsets.add(offset + 1);
1004           newOffsets.add(-1);
1005         }
1006
1007         @Override public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
1008           int newOffset = offset + 1;
1009           oldOffsets.add(offset);
1010           newOffsets.add(newOffset);
1011
1012           oldOffsets.add(newOffset);
1013           newOffsets.add(-1);
1014         }
1015       };
1016       while (!oldOffsets.isEmpty()) {
1017         offset = oldOffsets.remove(oldOffsets.size() - 1);
1018         int newOffset = newOffsets.remove(newOffsets.size() - 1);
1019
1020         if (offset >= endOffset) {
1021           continue;
1022         }
1023         Instruction instruction = instructions.get(offset);
1024
1025         if (clientVisitor.processedInstructions[offset]) {
1026           if (newOffset != -1) {
1027             instruction.accept(clientVisitor, offset, newOffset);
1028           }
1029           // when traversing call instruction, we have traversed all procedure control flows, so pop return address
1030           if (!currentProcedureReturnOffsets.isEmpty() && currentProcedureReturnOffsets.get(currentProcedureReturnOffsets.size() - 1) - 1 == offset) {
1031             currentProcedureReturnOffsets.remove(currentProcedureReturnOffsets.size() - 1);
1032           }
1033           continue;
1034         }
1035         if (!currentProcedureReturnOffsets.isEmpty()) {
1036           int returnOffset = currentProcedureReturnOffsets.get(currentProcedureReturnOffsets.size() - 1);
1037           CallInstruction callInstruction = (CallInstruction) instructions.get(returnOffset - 1);
1038           // check if we inside procedure but 'return offset' stack is empty, so
1039           // we should push back to 'return offset' stack
1040           synchronized (callInstruction.stack) {
1041             if (callInstruction.procBegin <= offset && offset < callInstruction.procEnd + 2
1042                 && (callInstruction.stack.size() == 0 || callInstruction.stack.peekReturnOffset() != returnOffset)) {
1043               callInstruction.stack.push(returnOffset, callInstruction);
1044             }
1045           }
1046         }
1047
1048         clientVisitor.processedInstructions[offset] = true;
1049         instruction.accept(getNextOffsetVisitor, offset, newOffset);
1050       }
1051     }
1052   }
1053
1054   private static boolean isInsideReturnStatement(PsiElement element) {
1055     while (element instanceof PsiExpression) element = element.getParent();
1056     return element instanceof PsiReturnStatement;
1057   }
1058
1059   private static class CopyOnWriteList {
1060     private final List<VariableInfo> list;
1061
1062     public CopyOnWriteList add(VariableInfo value) {
1063       CopyOnWriteList newList = new CopyOnWriteList();
1064       List<VariableInfo> list = getList();
1065       for (final VariableInfo variableInfo : list) {
1066         if (!value.equals(variableInfo)) {
1067           newList.list.add(variableInfo);
1068         }
1069       }
1070       newList.list.add(value);
1071       return newList;
1072     }
1073     public CopyOnWriteList remove(VariableInfo value) {
1074       CopyOnWriteList newList = new CopyOnWriteList();
1075       List<VariableInfo> list = getList();
1076       for (final VariableInfo variableInfo : list) {
1077         if (!value.equals(variableInfo)) {
1078           newList.list.add(variableInfo);
1079         }
1080       }
1081       return newList;
1082     }
1083
1084     public List<VariableInfo> getList() {
1085       return list;
1086     }
1087
1088     public CopyOnWriteList() {
1089       list = new LinkedList<VariableInfo>();
1090     }
1091     public CopyOnWriteList addAll(CopyOnWriteList addList) {
1092       CopyOnWriteList newList = new CopyOnWriteList();
1093       List<VariableInfo> list = getList();
1094       for (final VariableInfo variableInfo : list) {
1095         newList.list.add(variableInfo);
1096       }
1097       List<VariableInfo> toAdd = addList.getList();
1098       for (final VariableInfo variableInfo : toAdd) {
1099         if (!newList.list.contains(variableInfo)) {
1100           // no copy
1101           newList.list.add(variableInfo);
1102         }
1103       }
1104       return newList;
1105     }
1106   }
1107   public static class VariableInfo {
1108     private final PsiVariable variable;
1109     public final PsiElement expression;
1110
1111     public VariableInfo(PsiVariable variable, PsiElement expression) {
1112       this.variable = variable;
1113       this.expression = expression;
1114     }
1115
1116     public boolean equals(Object o) {
1117       return this == o || o instanceof VariableInfo && variable.equals(((VariableInfo)o).variable);
1118     }
1119
1120     public int hashCode() {
1121       return variable.hashCode();
1122     }
1123   }
1124   private static void merge(int offset, CopyOnWriteList readVars, CopyOnWriteList[] readVariables) {
1125     if (readVars != null) {
1126       CopyOnWriteList existing = readVariables[offset];
1127       readVariables[offset] = existing == null ? readVars : existing.addAll(readVars);
1128     }
1129   }
1130   /**
1131    * @return list of PsiReferenceExpression of usages of non-initialized variables
1132    */
1133   public static List<PsiReferenceExpression> getReadBeforeWrite(final ControlFlow flow) {
1134     InstructionClientVisitor<List<PsiReferenceExpression>> visitor = new ReadBeforeWriteClientVisitor(flow);
1135     depthFirstSearch(flow, visitor);
1136     return visitor.getResult();
1137   }
1138   private static class ReadBeforeWriteClientVisitor extends InstructionClientVisitor<List<PsiReferenceExpression>> {
1139     // map of variable->PsiReferenceExpressions for all read before written variables for this point and below in control flow
1140     private final CopyOnWriteList[] readVariables;
1141     private final ControlFlow myFlow;
1142
1143     public ReadBeforeWriteClientVisitor(ControlFlow flow) {
1144       myFlow = flow;
1145       readVariables = new CopyOnWriteList[myFlow.getSize()+1];
1146     }
1147
1148     @Override public void visitReadVariableInstruction(ReadVariableInstruction instruction, int offset, int nextOffset) {
1149       if (nextOffset > myFlow.getSize()) nextOffset = myFlow.getSize();
1150       CopyOnWriteList readVars = readVariables[nextOffset];
1151       PsiElement element = myFlow.getElement(offset);
1152       final PsiVariable variable = instruction.variable;
1153       if (!(variable instanceof PsiParameter) || ((PsiParameter)variable).getDeclarationScope() instanceof PsiForeachStatement) {
1154         PsiReferenceExpression expression = getEnclosingReferenceExpression(element, variable);
1155         if (expression != null) {
1156           VariableInfo variableInfo = new VariableInfo(variable, expression);
1157           if (readVars == null) {
1158             readVars = new CopyOnWriteList();
1159             readVars.list.add(variableInfo);
1160           }
1161           else {
1162             readVars = readVars.add(variableInfo);
1163           }
1164         }
1165       }
1166       merge(offset, readVars, readVariables);
1167     }
1168
1169     @Override public void visitWriteVariableInstruction(WriteVariableInstruction instruction, int offset, int nextOffset) {
1170       if (nextOffset > myFlow.getSize()) nextOffset = myFlow.getSize();
1171       CopyOnWriteList readVars = readVariables[nextOffset];
1172       final PsiVariable variable = instruction.variable;
1173       if (readVars != null && (!(variable instanceof PsiParameter) || ((PsiParameter)variable).getDeclarationScope() instanceof PsiForeachStatement)) {
1174         readVars = readVars.remove(new VariableInfo(variable, null));
1175       }
1176       merge(offset, readVars, readVariables);
1177     }
1178
1179     @Override public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
1180       if (nextOffset > myFlow.getSize()) nextOffset = myFlow.getSize();
1181       CopyOnWriteList readVars = readVariables[nextOffset];
1182       merge(offset, readVars, readVariables);
1183     }
1184
1185     @Override public void visitCallInstruction(CallInstruction instruction, int offset, int nextOffset) {
1186       visitInstruction(instruction, offset, nextOffset);
1187       for (int i = instruction.procBegin; i <= instruction.procEnd; i++) {
1188         readVariables[i] = null;
1189       }
1190     }
1191
1192     public List<PsiReferenceExpression> getResult() {
1193       List<PsiReferenceExpression> problemsFound = new ArrayList<PsiReferenceExpression>();
1194       CopyOnWriteList topReadVariables = readVariables[0];
1195       if (topReadVariables != null) {
1196         List<VariableInfo> list = topReadVariables.getList();
1197         for (final VariableInfo variableInfo : list) {
1198           problemsFound.add((PsiReferenceExpression)variableInfo.expression);
1199         }
1200       }
1201       return problemsFound;
1202     }
1203   }
1204
1205   public static final int NORMAL_COMPLETION_REASON = 1;
1206   public static final int RETURN_COMPLETION_REASON = 2;
1207   /**
1208    * return reasons.normalCompletion when  block can complete normally
1209    *        reasons.returnCalled when  block can complete abruptly because of return statement executed
1210    */
1211   public static int getCompletionReasons(final ControlFlow flow, final int offset, final int endOffset) {
1212     class MyVisitor extends InstructionClientVisitor<Integer> {
1213       final boolean[] normalCompletion = new boolean[endOffset];
1214       final boolean[] returnCalled = new boolean[endOffset];
1215
1216       @Override public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
1217         boolean ret = nextOffset < endOffset && returnCalled[nextOffset];
1218         boolean normal = nextOffset < endOffset && normalCompletion[nextOffset];
1219         final PsiElement element = flow.getElement(offset);
1220         boolean goToReturn = instruction instanceof GoToInstruction && ((GoToInstruction)instruction).isReturn;
1221         if (goToReturn || isInsideReturnStatement(element)) {
1222           ret = true;
1223         }
1224         else if (instruction instanceof ConditionalThrowToInstruction) {
1225           final int throwOffset = ((ConditionalThrowToInstruction)instruction).offset;
1226           boolean normalWhenThrow = throwOffset < endOffset && normalCompletion[throwOffset];
1227           boolean normalWhenNotThrow = offset == endOffset - 1 || normalCompletion[offset + 1];
1228           normal = normalWhenThrow || normalWhenNotThrow;
1229         }
1230         else if (!(instruction instanceof ThrowToInstruction) && nextOffset >= endOffset) {
1231           normal = true;
1232         }
1233         returnCalled[offset] |= ret;
1234         normalCompletion[offset] |= normal;
1235       }
1236
1237       public Integer getResult() {
1238         return (returnCalled[offset] ? RETURN_COMPLETION_REASON : 0) | (normalCompletion[offset] ? NORMAL_COMPLETION_REASON : 0);
1239       }
1240     }
1241     MyVisitor visitor = new MyVisitor();
1242     depthFirstSearch(flow, visitor, offset, endOffset);
1243
1244     return visitor.getResult().intValue();
1245   }
1246
1247   public static Collection<VariableInfo> getInitializedTwice(final ControlFlow flow) {
1248     InitializedTwiceClientVisitor visitor = new InitializedTwiceClientVisitor(flow, 0);
1249     depthFirstSearch(flow, visitor);
1250     return visitor.getResult();
1251   }
1252
1253   public static Collection<VariableInfo> getInitializedTwice(final ControlFlow flow, int startOffset, int endOffset) {
1254     InitializedTwiceClientVisitor visitor = new InitializedTwiceClientVisitor(flow, startOffset);
1255     depthFirstSearch(flow, visitor, startOffset, endOffset);
1256     return visitor.getResult();
1257   }
1258
1259   private static class InitializedTwiceClientVisitor extends InstructionClientVisitor<Collection<VariableInfo>> {
1260     // map of variable->PsiReferenceExpressions for all read and not written variables for this point and below in control flow
1261     private final CopyOnWriteList[] writtenVariables;
1262     private final CopyOnWriteList[] writtenTwiceVariables;
1263     private final ControlFlow myFlow;
1264     private final int myStartOffset;
1265
1266     public InitializedTwiceClientVisitor(ControlFlow flow, final int startOffset) {
1267       myFlow = flow;
1268       myStartOffset = startOffset;
1269       writtenVariables = new CopyOnWriteList[myFlow.getSize() + 1];
1270       writtenTwiceVariables = new CopyOnWriteList[myFlow.getSize() + 1];
1271     }
1272
1273     @Override public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
1274       if (nextOffset > myFlow.getSize()) nextOffset = myFlow.getSize();
1275
1276       CopyOnWriteList writeVars = writtenVariables[nextOffset];
1277       CopyOnWriteList writeTwiceVars = writtenTwiceVariables[nextOffset];
1278       if (instruction instanceof WriteVariableInstruction) {
1279         final WriteVariableInstruction writeVariableInstruction = (WriteVariableInstruction)instruction;
1280         final PsiVariable variable = writeVariableInstruction.variable;
1281         final PsiElement element = myFlow.getElement(offset);
1282
1283         PsiElement latestWriteVarExpression = null;
1284         if (writeVars != null) {
1285           List<VariableInfo> list = writeVars.getList();
1286           for (final VariableInfo variableInfo : list) {
1287             if (variableInfo.variable == variable) {
1288               latestWriteVarExpression = variableInfo.expression;
1289               break;
1290             }
1291           }
1292         }
1293         if (latestWriteVarExpression == null) {
1294           PsiElement expression = null;
1295           if (element instanceof PsiAssignmentExpression
1296               && ((PsiAssignmentExpression)element).getLExpression() instanceof PsiReferenceExpression) {
1297             expression = ((PsiAssignmentExpression)element).getLExpression();
1298           }
1299           else if (element instanceof PsiPostfixExpression) {
1300             expression = ((PsiPostfixExpression)element).getOperand();
1301           }
1302           else if (element instanceof PsiPrefixExpression) {
1303             expression = ((PsiPrefixExpression)element).getOperand();
1304           }
1305           else if (element instanceof PsiDeclarationStatement) {
1306             //should not happen
1307             expression = element;
1308           }
1309           if (writeVars == null) {
1310             writeVars = new CopyOnWriteList();
1311           }
1312           writeVars = writeVars.add(new VariableInfo(variable, expression));
1313         }
1314         else {
1315           if (writeTwiceVars == null) {
1316             writeTwiceVars = new CopyOnWriteList();
1317           }
1318           writeTwiceVars = writeTwiceVars.add(new VariableInfo(variable, latestWriteVarExpression));
1319         }
1320       }
1321       merge(offset, writeVars, writtenVariables);
1322       merge(offset, writeTwiceVars, writtenTwiceVariables);
1323     }
1324
1325     public Collection<VariableInfo> getResult() {
1326       CopyOnWriteList writtenTwiceVariable = writtenTwiceVariables[myStartOffset];
1327       if (writtenTwiceVariable == null) return Collections.emptyList();
1328       return writtenTwiceVariable.getList();
1329     }
1330   }
1331
1332   /**
1333    * @return true if instruction at 'instructionOffset' is reachable from offset 'startOffset'
1334    */
1335   public static boolean isInstructionReachable(final ControlFlow flow, final int instructionOffset, final int startOffset) {
1336     class MyVisitor extends InstructionClientVisitor<Boolean> {
1337       boolean reachable;
1338
1339       @Override public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
1340         if (nextOffset == instructionOffset) reachable = true;
1341       }
1342
1343       public Boolean getResult() {
1344         return reachable;
1345       }
1346     }
1347
1348     MyVisitor visitor = new MyVisitor();
1349     depthFirstSearch(flow, visitor, startOffset, flow.getSize());
1350
1351     return visitor.getResult().booleanValue();
1352   }
1353
1354   public static boolean isVariableAssignedInLoop(PsiReferenceExpression expression, PsiElement resolved) {
1355     if (!(expression.getParent() instanceof PsiAssignmentExpression)
1356         || ((PsiAssignmentExpression)expression.getParent()).getLExpression() != expression) {
1357       return false;
1358     }
1359     PsiExpression qualifier = expression.getQualifierExpression();
1360     if (qualifier != null && !(qualifier instanceof PsiThisExpression)) return false;
1361
1362     if (!(resolved instanceof PsiVariable)) return false;
1363     PsiVariable variable = (PsiVariable)resolved;
1364
1365     final PsiElement codeBlock = PsiUtil.getVariableCodeBlock(variable, expression);
1366     if (codeBlock == null) return false;
1367     final ControlFlow flow;
1368     try {
1369       flow = ControlFlowFactory.getInstance(codeBlock.getProject()).getControlFlow(codeBlock, LocalsOrMyInstanceFieldsControlFlowPolicy.getInstance(), false);
1370     }
1371     catch (AnalysisCanceledException e) {
1372       return false;
1373     }
1374     final PsiAssignmentExpression assignmentExpression = (PsiAssignmentExpression)expression.getParent();
1375     int startOffset = flow.getStartOffset(assignmentExpression);
1376     return startOffset != -1 && isInstructionReachable(flow, startOffset, startOffset);
1377   }
1378 }
1379