java/java-impl/src/com/intellij/psi/controlFlow/ControlFlowAnalyzer.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.codeInsight.ExceptionUtil;
  19 import com.intellij.codeInsight.daemon.JavaErrorMessages;
  20 import com.intellij.openapi.diagnostic.Logger;
  21 import com.intellij.openapi.progress.ProgressManager;
  22 import com.intellij.openapi.project.Project;
  23 import com.intellij.openapi.util.Comparing;
  24 import com.intellij.psi.*;
  25 import com.intellij.psi.jsp.JspFile;
  26 import com.intellij.psi.jsp.JavaJspElementVisitor;
  27 import com.intellij.psi.tree.IElementType;
  28 import com.intellij.psi.util.PsiTreeUtil;
  29 import com.intellij.psi.util.PsiUtil;
  30 import com.intellij.util.containers.Stack;
  31 import gnu.trove.THashMap;
  32 import gnu.trove.TIntArrayList;
  33 import org.jetbrains.annotations.NotNull;
  34
  35 import java.util.*;
  36
  37 class ControlFlowAnalyzer extends JavaJspElementVisitor {
  38   private static final Logger LOG = Logger.getInstance("#com.intellij.psi.controlFlow.ControlFlowAnalyzer");
  39
  40   private final PsiElement myCodeFragment;
  41   private final ControlFlowPolicy myPolicy;
  42
  43   private ControlFlowImpl myCurrentFlow;
  44   private final ControlFlowStack myStack = new ControlFlowStack();
  45   private final Stack<PsiParameter> myCatchParameters = new Stack<PsiParameter>();// stack of PsiParameter for catch
  46   private final Stack<PsiElement> myCatchBlocks = new Stack<PsiElement>();
  47
  48   private final Stack<PsiElement> myFinallyBlocks = new Stack<PsiElement>();
  49   private final Stack<PsiElement> myUnhandledExceptionCatchBlocks = new Stack<PsiElement>();
  50
  51   // element to jump to from inner (sub)expression in "jump to begin" situation.
  52   // E.g. we should jump to "then" branch if condition expression evaluated to true inside if statement
  53   private final StatementStack myStartStatementStack = new StatementStack();
  54   // element to jump to from inner (sub)expression in "jump to end" situation.
  55   // E.g. we should jump to "else" branch if condition expression evaluated to false inside if statement
  56   private final StatementStack myEndStatementStack = new StatementStack();
  57
  58   private final Stack<BranchingInstruction.Role> myStartJumpRoles = new Stack<BranchingInstruction.Role>();
  59   private final Stack<BranchingInstruction.Role> myEndJumpRoles = new Stack<BranchingInstruction.Role>();
  60
  61   // true if generate direct jumps for short-circuited operations,
  62   // e.g. jump to else branch of if statement after each calculation of '&&' operand in condition
  63   private final boolean myEnabledShortCircuit;
  64   // true if evaluate constant expression inside 'if' statement condition and alter control flow accordingly
  65   // in case of unreachable statement analysis must be false
  66   private final boolean myEvaluateConstantIfConfition;
  67   private final boolean myAssignmentTargetsAreElements;
  68
  69   private final Stack<TIntArrayList> intArrayPool = new Stack<TIntArrayList>();
  70   // map: PsiElement element -> TIntArrayList instructionOffsetsToPatch with getStartoffset(element)
  71   private final Map<PsiElement,TIntArrayList> offsetsAddElementStart = new THashMap<PsiElement, TIntArrayList>();
  72   // map: PsiElement element -> TIntArrayList instructionOffsetsToPatch with getEndOffset(element)
  73   private final Map<PsiElement,TIntArrayList> offsetsAddElementEnd = new THashMap<PsiElement, TIntArrayList>();
  74   private final ControlFlowFactory myControlFlowFactory;
  75   private final Map<PsiElement, ControlFlowSubRange> mySubRanges = new THashMap<PsiElement, ControlFlowSubRange>();
  76   private final PsiConstantEvaluationHelper myConstantEvaluationHelper;
  77
  78   ControlFlowAnalyzer(@NotNull PsiElement codeFragment,
  79                       @NotNull ControlFlowPolicy policy,
  80                       boolean enabledShortCircuit,
  81                       boolean evaluateConstantIfConfition) {
  82     this(codeFragment, policy, enabledShortCircuit, evaluateConstantIfConfition, false);
  83   }
  84
  85   private ControlFlowAnalyzer(@NotNull PsiElement codeFragment,
  86                               @NotNull ControlFlowPolicy policy,
  87                               boolean enabledShortCircuit,
  88                               boolean evaluateConstantIfConfition,
  89                               boolean assignmentTargetsAreElements) {
  90     myCodeFragment = codeFragment;
  91     myPolicy = policy;
  92     myEnabledShortCircuit = enabledShortCircuit;
  93     myEvaluateConstantIfConfition = evaluateConstantIfConfition;
  94     myAssignmentTargetsAreElements = assignmentTargetsAreElements;
  95     Project project = codeFragment.getProject();
  96     myControlFlowFactory = ControlFlowFactory.getInstance(project);
  97     myConstantEvaluationHelper = JavaPsiFacade.getInstance(project).getConstantEvaluationHelper();
  98   }
  99
 100   @NotNull
 101   ControlFlow buildControlFlow() throws AnalysisCanceledException {
 102     // push guard outer statement offsets in case when nested expression is incorrect
 103     myStartJumpRoles.push(BranchingInstruction.Role.END);
 104     myEndJumpRoles.push(BranchingInstruction.Role.END);
 105
 106     myCurrentFlow = new ControlFlowImpl();
 107
 108     // guard elements
 109     myStartStatementStack.pushStatement(myCodeFragment, false);
 110     myEndStatementStack.pushStatement(myCodeFragment, false);
 111
 112     try {
 113       myCodeFragment.accept(this);
 114       cleanup();
 115     }
 116     catch (AnalysisCanceledSoftException e) {
 117       throw new AnalysisCanceledException(e.getErrorElement());
 118     }
 119
 120     return myCurrentFlow;
 121   }
 122
 123   private static class StatementStack {
 124     private final Stack<PsiElement> myStatements = new Stack<PsiElement>();
 125     private final TIntArrayList myAtStart = new TIntArrayList();
 126
 127     private void popStatement() {
 128       myAtStart.remove(myAtStart.size() - 1);
 129       myStatements.pop();
 130     }
 131
 132     private PsiElement peekElement() {
 133       return myStatements.peek();
 134     }
 135
 136     private boolean peekAtStart() {
 137       return myAtStart.get(myAtStart.size() - 1) == 1;
 138     }
 139
 140     private void pushStatement(PsiElement statement, boolean atStart) {
 141       myStatements.push(statement);
 142       myAtStart.add(atStart ? 1 : 0);
 143     }
 144   }
 145
 146   private TIntArrayList getEmptyIntArray() {
 147     if (intArrayPool.isEmpty()) {
 148       return new TIntArrayList(1);
 149     }
 150     TIntArrayList list = intArrayPool.pop();
 151     list.clear();
 152     return list;
 153   }
 154
 155   private void poolIntArray(TIntArrayList list) {
 156     intArrayPool.add(list);
 157   }
 158
 159   // patch instruction currently added to control flow so that its jump offset corrected on getStartOffset(element) or getEndOffset(element)
 160   //  when corresponding element offset become available
 161   private void addElementOffsetLater(PsiElement element, boolean atStart) {
 162     Map<PsiElement,TIntArrayList> offsetsAddElement = atStart ? offsetsAddElementStart : offsetsAddElementEnd;
 163     TIntArrayList offsets = offsetsAddElement.get(element);
 164     if (offsets == null) {
 165       offsets = getEmptyIntArray();
 166       offsetsAddElement.put(element, offsets);
 167     }
 168     int offset = myCurrentFlow.getSize() - 1;
 169     offsets.add(offset);
 170     if (myCurrentFlow.getEndOffset(element) != -1) {
 171       patchInstructionOffsets(element);
 172     }
 173   }
 174
 175
 176   private void patchInstructionOffsets(PsiElement element) {
 177     patchInstructionOffsets(offsetsAddElementStart.get(element), myCurrentFlow.getStartOffset(element));
 178     offsetsAddElementStart.put(element, null);
 179     patchInstructionOffsets(offsetsAddElementEnd.get(element), myCurrentFlow.getEndOffset(element));
 180     offsetsAddElementEnd.put(element, null);
 181   }
 182
 183   private void patchInstructionOffsets(TIntArrayList offsets, int add) {
 184     if (offsets == null) return;
 185     for (int i = 0; i < offsets.size(); i++) {
 186       int offset = offsets.get(i);
 187       BranchingInstruction instruction = (BranchingInstruction)myCurrentFlow.getInstructions().get(offset);
 188       instruction.offset += add;
 189       LOG.assertTrue(instruction.offset >= 0);
 190     }
 191     poolIntArray(offsets);
 192   }
 193
 194   private void cleanup() {
 195     // make all non patched goto instructions jump to the end of control flow
 196     for (TIntArrayList offsets : offsetsAddElementStart.values()) {
 197       patchInstructionOffsets(offsets, myCurrentFlow.getEndOffset(myCodeFragment));
 198     }
 199     for (TIntArrayList offsets : offsetsAddElementEnd.values()) {
 200       patchInstructionOffsets(offsets, myCurrentFlow.getEndOffset(myCodeFragment));
 201     }
 202
 203     // register all sub ranges
 204     for (Map.Entry<PsiElement, ControlFlowSubRange> entry : mySubRanges.entrySet()) {
 205       ProgressManager.getInstance().checkCanceled();
 206       ControlFlowSubRange subRange = entry.getValue();
 207       PsiElement element = entry.getKey();
 208       myControlFlowFactory.registerSubRange(element, subRange, myEvaluateConstantIfConfition, myPolicy);
 209     }
 210   }
 211
 212   private void startElement(PsiElement element) {
 213     for (PsiElement child = element.getFirstChild(); child != null; child = child.getNextSibling()) {
 214       ProgressManager.getInstance().checkCanceled();
 215       if (child instanceof PsiErrorElement && !Comparing.strEqual(((PsiErrorElement)child).getErrorDescription(), JavaErrorMessages.message("expected.semicolon"))) {
 216         // do not perform control flow analysis for incomplete code
 217         throw new AnalysisCanceledSoftException(element);
 218       }
 219     }
 220     ProgressManager.getInstance().checkCanceled();
 221     myCurrentFlow.startElement(element);
 222
 223     generateUncheckedExceptionJumpsIfNeeded(element, true);
 224   }
 225
 226   private void generateUncheckedExceptionJumpsIfNeeded(PsiElement element, boolean atStart) {
 227     // optimization: reduce number of instructions
 228     boolean isGeneratingStatement = element instanceof PsiStatement && !(element instanceof PsiSwitchLabelStatement);
 229     boolean isGeneratingCodeBlock = element instanceof PsiCodeBlock && !(element.getParent() instanceof PsiSwitchStatement);
 230     if (isGeneratingStatement || isGeneratingCodeBlock) {
 231       generateUncheckedExceptionJumps(element, atStart);
 232     }
 233   }
 234
 235   private void finishElement(PsiElement element) {
 236     generateUncheckedExceptionJumpsIfNeeded(element, false);
 237
 238     myCurrentFlow.finishElement(element);
 239     patchInstructionOffsets(element);
 240   }
 241
 242
 243   private void generateUncheckedExceptionJumps(PsiElement element, boolean atStart) {
 244     // optimization: if we just generated all necessary jumps, do not generate it once again
 245     if (atStart
 246         && element instanceof PsiStatement
 247         && element.getParent() instanceof PsiCodeBlock && element.getPrevSibling() != null) {
 248       return;
 249     }
 250
 251     for (int i = myUnhandledExceptionCatchBlocks.size() - 1; i >= 0; i--) {
 252       ProgressManager.getInstance().checkCanceled();
 253       PsiElement block = myUnhandledExceptionCatchBlocks.get(i);
 254       // cannot jump to outer catch blocks (belonging to outer try stmt) if current try{} has finally block
 255       if (block == null) {
 256         if (!myFinallyBlocks.isEmpty()) {
 257           break;
 258         }
 259         else {
 260           continue;
 261         }
 262       }
 263       ConditionalThrowToInstruction throwToInstruction = new ConditionalThrowToInstruction(-1); // -1 for init parameter
 264       myCurrentFlow.addInstruction(throwToInstruction);
 265       if (!patchUncheckedThrowInstructionIfInsideFinally(throwToInstruction, element, block)) {
 266         addElementOffsetLater(block, true);
 267       }
 268     }
 269
 270
 271     // generate jump to the top finally block
 272     if (!myFinallyBlocks.isEmpty()) {
 273       final PsiElement finallyBlock = myFinallyBlocks.peek();
 274       ConditionalThrowToInstruction throwToInstruction = new ConditionalThrowToInstruction(-2);
 275       myCurrentFlow.addInstruction(throwToInstruction);
 276       if (!patchUncheckedThrowInstructionIfInsideFinally(throwToInstruction, element, finallyBlock)) {
 277         addElementOffsetLater(finallyBlock, true);
 278       }
 279     }
 280
 281   }
 282
 283   private void generateCheckedExceptionJumps(PsiElement element) {
 284     //generate jumps to all handled exception handlers
 285     //if (myCatchBlocks.size() != 0) {
 286     //}
 287     Collection<PsiClassType> unhandledExceptions = ExceptionUtil.collectUnhandledExceptions(element, element.getParent());
 288     for (PsiClassType unhandledException : unhandledExceptions) {
 289       ProgressManager.getInstance().checkCanceled();
 290       generateThrow(unhandledException, element);
 291     }
 292   }
 293
 294   private void generateThrow(PsiClassType unhandledException, PsiElement throwingElement) {
 295     final List<PsiElement> catchBlocks = findThrowToBlocks(unhandledException);
 296     for (PsiElement block : catchBlocks) {
 297       ProgressManager.getInstance().checkCanceled();
 298       ConditionalThrowToInstruction instruction = new ConditionalThrowToInstruction(0);
 299       myCurrentFlow.addInstruction(instruction);
 300       if (!patchCheckedThrowInstructionIfInsideFinally(instruction, throwingElement, block)) {
 301         if (block == null) {
 302           addElementOffsetLater(myCodeFragment, false);
 303         }
 304         else {
 305           instruction.offset--; // -1 for catch block param init
 306           addElementOffsetLater(block, true);
 307         }
 308       }
 309     }
 310   }
 311
 312   private final Map<PsiElement, List<PsiElement>> finallyBlockToUnhandledExceptions = new HashMap<PsiElement, List<PsiElement>>();
 313
 314   private boolean patchCheckedThrowInstructionIfInsideFinally(@NotNull ConditionalThrowToInstruction instruction,
 315                                                               PsiElement throwingElement,
 316                                                               PsiElement elementToJumpTo) {
 317     final PsiElement finallyBlock = findEnclosingFinallyBlockElement(throwingElement, elementToJumpTo);
 318     if (finallyBlock == null) return false;
 319
 320     List<PsiElement> unhandledExceptionCatchBlocks = finallyBlockToUnhandledExceptions.get(finallyBlock);
 321     if (unhandledExceptionCatchBlocks == null) {
 322       unhandledExceptionCatchBlocks = new ArrayList<PsiElement>();
 323       finallyBlockToUnhandledExceptions.put(finallyBlock, unhandledExceptionCatchBlocks);
 324     }
 325     int index = unhandledExceptionCatchBlocks.indexOf(elementToJumpTo);
 326     if (index == -1) {
 327       index = unhandledExceptionCatchBlocks.size();
 328       unhandledExceptionCatchBlocks.add(elementToJumpTo);
 329     }
 330     // first three return instructions are for normal completion, return statement call completion and unchecked exception throwing completion resp.
 331     instruction.offset = 3 + index;
 332     addElementOffsetLater(finallyBlock, false);
 333
 334     return true;
 335   }
 336
 337   private boolean patchUncheckedThrowInstructionIfInsideFinally(@NotNull ConditionalThrowToInstruction instruction,
 338                                                                 PsiElement throwingElement,
 339                                                                 PsiElement elementToJumpTo) {
 340     final PsiElement finallyBlock = findEnclosingFinallyBlockElement(throwingElement, elementToJumpTo);
 341     if (finallyBlock == null) return false;
 342
 343     // first three return instructions are for normal completion, return statement call completion and unchecked exception throwing completion resp.
 344     instruction.offset = 2;
 345     addElementOffsetLater(finallyBlock, false);
 346
 347     return true;
 348   }
 349
 350   @Override public void visitCodeFragment(JavaCodeFragment codeFragment) {
 351     startElement(codeFragment);
 352     int prevOffset = myCurrentFlow.getSize();
 353     PsiElement[] children = codeFragment.getChildren();
 354     for (PsiElement child : children) {
 355       ProgressManager.getInstance().checkCanceled();
 356       child.accept(this);
 357     }
 358
 359     finishElement(codeFragment);
 360     registerSubRange(codeFragment, prevOffset);
 361   }
 362
 363   private void registerSubRange(final PsiElement codeFragment, final int startOffset) {
 364     // cache child code block in hope it will be needed
 365     ControlFlowSubRange flow = new ControlFlowSubRange(myCurrentFlow, startOffset, myCurrentFlow.getSize());
 366     // register it later since offset may not have been patched yet
 367     mySubRanges.put(codeFragment, flow);
 368   }
 369
 370   @Override public void visitCodeBlock(PsiCodeBlock block) {
 371     startElement(block);
 372     int prevOffset = myCurrentFlow.getSize();
 373     PsiStatement[] statements = block.getStatements();
 374     for (PsiStatement statement : statements) {
 375       ProgressManager.getInstance().checkCanceled();
 376       statement.accept(this);
 377     }
 378
 379     //each statement should contain at least one instruction in order to getElement(offset) work
 380     int nextOffset = myCurrentFlow.getSize();
 381     if (!(block.getParent() instanceof PsiSwitchStatement) && prevOffset == nextOffset) {
 382       emitEmptyInstruction();
 383     }
 384
 385     finishElement(block);
 386     if (prevOffset != 0) {
 387       registerSubRange(block, prevOffset);
 388     }
 389   }
 390
 391   private void emitEmptyInstruction() {
 392     myCurrentFlow.addInstruction(EmptyInstruction.INSTANCE);
 393   }
 394
 395   @Override public void visitJspFile(JspFile file) {
 396     visitChildren(file);
 397   }
 398
 399   @Override public void visitBlockStatement(PsiBlockStatement statement) {
 400     startElement(statement);
 401     final PsiCodeBlock codeBlock = statement.getCodeBlock();
 402     codeBlock.accept(this);
 403     finishElement(statement);
 404   }
 405
 406   @Override public void visitBreakStatement(PsiBreakStatement statement) {
 407     startElement(statement);
 408     PsiStatement exitedStatement = statement.findExitedStatement();
 409     if (exitedStatement != null) {
 410       final Instruction instruction;
 411       final PsiElement finallyBlock = findEnclosingFinallyBlockElement(statement, exitedStatement);
 412       final int finallyStartOffset = finallyBlock == null ? -1 : myCurrentFlow.getStartOffset(finallyBlock);
 413       if (finallyBlock != null && finallyStartOffset != -1) {
 414         // go out of finally, use return
 415         CallInstruction callInstruction = (CallInstruction)myCurrentFlow.getInstructions().get(finallyStartOffset - 2);
 416         instruction = new ReturnInstruction(0, myStack, callInstruction);
 417       }
 418       else {
 419         instruction = new GoToInstruction(0);
 420       }
 421       myCurrentFlow.addInstruction(instruction);
 422       // exited statement might be out of control flow analyzed
 423       addElementOffsetLater(exitedStatement, false);
 424     }
 425     finishElement(statement);
 426   }
 427
 428   private PsiElement findEnclosingFinallyBlockElement(PsiElement sourceElement, PsiElement jumpElement) {
 429     PsiElement element = sourceElement;
 430     while (element != null && !(element instanceof PsiFile)) {
 431       if (element instanceof PsiCodeBlock
 432           && element.getParent() instanceof PsiTryStatement
 433           && ((PsiTryStatement)element.getParent()).getFinallyBlock() == element) {
 434         // element maybe out of scope to be analyzed
 435         if (myCurrentFlow.getStartOffset(element.getParent()) == -1) return null;
 436         if (jumpElement == null || !PsiTreeUtil.isAncestor(element, jumpElement, false)) return element;
 437       }
 438       element = element.getParent();
 439     }
 440     return null;
 441   }
 442
 443   @Override public void visitContinueStatement(PsiContinueStatement statement) {
 444     startElement(statement);
 445     PsiStatement continuedStatement = statement.findContinuedStatement();
 446     if (continuedStatement != null) {
 447       PsiElement body = null;
 448       if (continuedStatement instanceof PsiForStatement) {
 449         body = ((PsiForStatement)continuedStatement).getBody();
 450       }
 451       else if (continuedStatement instanceof PsiWhileStatement) {
 452         body = ((PsiWhileStatement)continuedStatement).getBody();
 453       }
 454       else if (continuedStatement instanceof PsiDoWhileStatement) {
 455         body = ((PsiDoWhileStatement)continuedStatement).getBody();
 456       }
 457       else if (continuedStatement instanceof PsiForeachStatement) {
 458         body = ((PsiForeachStatement)continuedStatement).getBody();
 459       }
 460       if (body == null) {
 461         body = myCodeFragment;
 462       }
 463       final Instruction instruction;
 464       final PsiElement finallyBlock = findEnclosingFinallyBlockElement(statement, continuedStatement);
 465       final int finallyStartOffset = finallyBlock == null ? -1 : myCurrentFlow.getStartOffset(finallyBlock);
 466       if (finallyBlock != null && finallyStartOffset != -1) {
 467         // go out of finally, use return
 468         CallInstruction callInstruction = (CallInstruction)myCurrentFlow.getInstructions().get(finallyStartOffset - 2);
 469         instruction = new ReturnInstruction(0, myStack, callInstruction);
 470       }
 471       else {
 472         instruction = new GoToInstruction(0);
 473       }
 474       myCurrentFlow.addInstruction(instruction);
 475       addElementOffsetLater(body, false);
 476     }
 477     finishElement(statement);
 478   }
 479
 480   @Override public void visitDeclarationStatement(PsiDeclarationStatement statement) {
 481     startElement(statement);
 482     int pc = myCurrentFlow.getSize();
 483     PsiElement[] elements = statement.getDeclaredElements();
 484     for (PsiElement element : elements) {
 485       ProgressManager.getInstance().checkCanceled();
 486       if (element instanceof PsiClass) {
 487         element.accept(this);
 488       }
 489       else if (element instanceof PsiVariable) {
 490         PsiExpression initializer = ((PsiVariable)element).getInitializer();
 491         if (initializer != null) {
 492           myStartStatementStack.pushStatement(initializer, false);
 493           myEndStatementStack.pushStatement(initializer, false);
 494           initializer.accept(this);
 495           myStartStatementStack.popStatement();
 496           myEndStatementStack.popStatement();
 497         }
 498         if (element instanceof PsiLocalVariable && initializer != null
 499             || element instanceof PsiField) {
 500           if (element instanceof PsiLocalVariable && !myPolicy.isLocalVariableAccepted((PsiLocalVariable)element)) continue;
 501
 502           if (myAssignmentTargetsAreElements) {
 503             startElement(element);
 504           }
 505
 506           generateWriteInstruction((PsiVariable)element);
 507
 508           if (myAssignmentTargetsAreElements) {
 509             finishElement(element);
 510           }
 511         }
 512       }
 513     }
 514     if (pc == myCurrentFlow.getSize()) {
 515       // generate at least one instruction for declaration
 516       emitEmptyInstruction();
 517     }
 518     finishElement(statement);
 519   }
 520
 521   @Override public void visitDoWhileStatement(PsiDoWhileStatement statement) {
 522     startElement(statement);
 523     myStartStatementStack.pushStatement(statement.getBody() == null ? statement : statement.getBody(), true);
 524     myEndStatementStack.pushStatement(statement, false);
 525
 526     PsiStatement body = statement.getBody();
 527     if (body != null) {
 528       body.accept(this);
 529     }
 530
 531     PsiExpression condition = statement.getCondition();
 532     if (condition != null) {
 533       condition.accept(this);
 534     }
 535
 536     int offset = myCurrentFlow.getStartOffset(statement);
 537
 538     Object loopCondition = myConstantEvaluationHelper.computeConstantExpression(statement.getCondition());
 539     if (loopCondition instanceof Boolean) {
 540       if (((Boolean)loopCondition).booleanValue()) {
 541         myCurrentFlow.addInstruction(new GoToInstruction(offset));
 542       }
 543       else {
 544         emitEmptyInstruction();
 545       }
 546
 547     }
 548     else {
 549       Instruction instruction = new ConditionalGoToInstruction(offset, statement.getCondition());
 550       myCurrentFlow.addInstruction(instruction);
 551     }
 552
 553     myStartStatementStack.popStatement();
 554     myEndStatementStack.popStatement();
 555     finishElement(statement);
 556   }
 557
 558   @Override public void visitEmptyStatement(PsiEmptyStatement statement) {
 559     startElement(statement);
 560     emitEmptyInstruction();
 561
 562     finishElement(statement);
 563   }
 564
 565   @Override public void visitExpressionStatement(PsiExpressionStatement statement) {
 566     startElement(statement);
 567     final PsiExpression expression = statement.getExpression();
 568     expression.accept(this);
 569
 570     for (PsiParameter catchParameter : myCatchParameters) {
 571       ProgressManager.getInstance().checkCanceled();
 572       PsiType type = catchParameter.getType();
 573       if (type instanceof PsiClassType) {
 574         generateThrow((PsiClassType)type, statement);
 575       }
 576     }
 577     finishElement(statement);
 578   }
 579
 580   @Override public void visitExpressionListStatement(PsiExpressionListStatement statement) {
 581     startElement(statement);
 582     PsiExpression[] expressions = statement.getExpressionList().getExpressions();
 583     for (PsiExpression expr : expressions) {
 584       ProgressManager.getInstance().checkCanceled();
 585       expr.accept(this);
 586     }
 587     finishElement(statement);
 588   }
 589
 590   @Override public void visitField(PsiField field) {
 591     final PsiExpression initializer = field.getInitializer();
 592     if (initializer != null) {
 593       startElement(field);
 594       initializer.accept(this);
 595       finishElement(field);
 596     }
 597   }
 598
 599   @Override public void visitForStatement(PsiForStatement statement) {
 600     startElement(statement);
 601     myStartStatementStack.pushStatement(statement.getBody() == null ? statement : statement.getBody(), false);
 602     myEndStatementStack.pushStatement(statement, false);
 603
 604     PsiStatement initialization = statement.getInitialization();
 605     if (initialization != null) {
 606       initialization.accept(this);
 607     }
 608
 609     PsiExpression condition = statement.getCondition();
 610     if (condition != null) {
 611       condition.accept(this);
 612     }
 613
 614
 615     Object loopCondition = myConstantEvaluationHelper.computeConstantExpression(condition);
 616     if (loopCondition instanceof Boolean || condition == null) {
 617       boolean value = condition == null || ((Boolean)loopCondition).booleanValue();
 618       if (value) {
 619         emitEmptyInstruction();
 620       }
 621       else {
 622         myCurrentFlow.addInstruction(new GoToInstruction(0));
 623         addElementOffsetLater(statement, false);
 624       }
 625     }
 626     else {
 627       Instruction instruction = new ConditionalGoToInstruction(0, statement.getCondition());
 628       myCurrentFlow.addInstruction(instruction);
 629       addElementOffsetLater(statement, false);
 630     }
 631
 632     PsiStatement body = statement.getBody();
 633     if (body != null) {
 634       body.accept(this);
 635     }
 636
 637     PsiStatement update = statement.getUpdate();
 638     if (update != null) {
 639       update.accept(this);
 640     }
 641
 642     int offset = initialization != null
 643                  ? myCurrentFlow.getEndOffset(initialization)
 644                  : myCurrentFlow.getStartOffset(statement);
 645     Instruction instruction = new GoToInstruction(offset);
 646     myCurrentFlow.addInstruction(instruction);
 647
 648     myStartStatementStack.popStatement();
 649     myEndStatementStack.popStatement();
 650     finishElement(statement);
 651   }
 652
 653   @Override public void visitForeachStatement(PsiForeachStatement statement) {
 654     startElement(statement);
 655     final PsiStatement body = statement.getBody();
 656     myStartStatementStack.pushStatement(body == null ? statement : body, false);
 657     myEndStatementStack.pushStatement(statement, false);
 658     final PsiExpression iteratedValue = statement.getIteratedValue();
 659     if (iteratedValue != null) {
 660       iteratedValue.accept(this);
 661     }
 662
 663     final int gotoTarget = myCurrentFlow.getSize();
 664     Instruction instruction = new ConditionalGoToInstruction(0, statement.getIteratedValue());
 665     myCurrentFlow.addInstruction(instruction);
 666     addElementOffsetLater(statement, false);
 667
 668     final PsiParameter iterationParameter = statement.getIterationParameter();
 669     if (myPolicy.isParameterAccepted(iterationParameter)) {
 670       generateWriteInstruction(iterationParameter);
 671     }
 672     if (body != null) {
 673       body.accept(this);
 674     }
 675
 676     final GoToInstruction gotoInstruction = new GoToInstruction(gotoTarget);
 677     myCurrentFlow.addInstruction(gotoInstruction);
 678     myStartStatementStack.popStatement();
 679     myEndStatementStack.popStatement();
 680     finishElement(statement);
 681   }
 682
 683   @Override public void visitIfStatement(PsiIfStatement statement) {
 684     startElement(statement);
 685
 686     final PsiStatement elseBranch = statement.getElseBranch();
 687     final PsiStatement thenBranch = statement.getThenBranch();
 688     PsiExpression conditionExpression = statement.getCondition();
 689
 690     generateConditionalStatementInstructions(statement, conditionExpression, thenBranch, elseBranch);
 691
 692     finishElement(statement);
 693   }
 694
 695   private void generateConditionalStatementInstructions(PsiElement statement,
 696                                                         PsiExpression conditionExpression,
 697                                                         final PsiElement thenBranch,
 698                                                         final PsiElement elseBranch) {
 699     if (thenBranch == null) {
 700       myStartStatementStack.pushStatement(statement, false);
 701     }
 702     else {
 703       myStartStatementStack.pushStatement(thenBranch, true);
 704     }
 705     if (elseBranch == null) {
 706       myEndStatementStack.pushStatement(statement, false);
 707     }
 708     else {
 709       myEndStatementStack.pushStatement(elseBranch, true);
 710     }
 711
 712     myEndJumpRoles.push(elseBranch == null ? BranchingInstruction.Role.END : BranchingInstruction.Role.ELSE);
 713     myStartJumpRoles.push(thenBranch == null ? BranchingInstruction.Role.END : BranchingInstruction.Role.THEN);
 714
 715     if (conditionExpression != null) {
 716       conditionExpression.accept(this);
 717     }
 718
 719     boolean generateElseFlow = true;
 720     boolean generateThenFlow = true;
 721     boolean generateConditionalJump = true;
 722     /**
 723      * if() statement generated instructions outline:
 724      *  'if (C) { A } [ else { B } ]' :
 725      *     generate (C)
 726      *     cond_goto else
 727      *     generate (A)
 728      *     [ goto end ]
 729      * :else
 730      *     [ generate (B) ]
 731      * :end
 732      */
 733     if (myEvaluateConstantIfConfition) {
 734       final Object value = myConstantEvaluationHelper.computeConstantExpression(conditionExpression);
 735       if (value instanceof Boolean) {
 736         boolean condition = ((Boolean)value).booleanValue();
 737         generateThenFlow = condition;
 738         generateElseFlow = !condition;
 739         generateConditionalJump = false;
 740         myCurrentFlow.setConstantConditionOccurred(true);
 741       }
 742     }
 743     if (generateConditionalJump) {
 744       BranchingInstruction.Role role = elseBranch == null ? BranchingInstruction.Role.END : BranchingInstruction.Role.ELSE;
 745       Instruction instruction = new ConditionalGoToInstruction(0, role, conditionExpression);
 746       myCurrentFlow.addInstruction(instruction);
 747       if (elseBranch == null) {
 748         addElementOffsetLater(statement, false);
 749       }
 750       else {
 751         addElementOffsetLater(elseBranch, true);
 752       }
 753     }
 754     if (thenBranch != null && generateThenFlow) {
 755       thenBranch.accept(this);
 756     }
 757     if (elseBranch != null && generateElseFlow) {
 758       if (generateThenFlow) {
 759         // make jump to end after then branch (only if it has been generated)
 760         Instruction instruction = new GoToInstruction(0);
 761         myCurrentFlow.addInstruction(instruction);
 762         addElementOffsetLater(statement, false);
 763       }
 764       elseBranch.accept(this);
 765     }
 766
 767     myStartJumpRoles.pop();
 768     myEndJumpRoles.pop();
 769
 770     myStartStatementStack.popStatement();
 771     myEndStatementStack.popStatement();
 772   }
 773
 774   @Override public void visitLabeledStatement(PsiLabeledStatement statement) {
 775     startElement(statement);
 776     final PsiStatement innerStatement = statement.getStatement();
 777     if (innerStatement != null) {
 778       innerStatement.accept(this);
 779     }
 780     finishElement(statement);
 781   }
 782
 783   @Override public void visitReturnStatement(PsiReturnStatement statement) {
 784     startElement(statement);
 785     PsiExpression returnValue = statement.getReturnValue();
 786
 787     myStartStatementStack.pushStatement(returnValue, false);
 788     myEndStatementStack.pushStatement(returnValue, false);
 789
 790     if (returnValue != null) {
 791       returnValue.accept(this);
 792     }
 793     addReturnInstruction(statement);
 794     myStartStatementStack.popStatement();
 795     myEndStatementStack.popStatement();
 796
 797     finishElement(statement);
 798   }
 799
 800   private void addReturnInstruction(PsiElement statement) {
 801     BranchingInstruction instruction;
 802     final PsiElement finallyBlock = findEnclosingFinallyBlockElement(statement, null);
 803     final int finallyStartOffset = finallyBlock == null ? -1 : myCurrentFlow.getStartOffset(finallyBlock);
 804     if (finallyBlock != null && finallyStartOffset != -1) {
 805       // go out of finally, go to 2nd return after finally block
 806       // second return is for return statement called completion
 807       instruction = new GoToInstruction(1, BranchingInstruction.Role.END, true);
 808       myCurrentFlow.addInstruction(instruction);
 809       addElementOffsetLater(finallyBlock, false);
 810     }
 811     else {
 812       instruction = new GoToInstruction(0, BranchingInstruction.Role.END, true);
 813       myCurrentFlow.addInstruction(instruction);
 814       if (myFinallyBlocks.isEmpty()) {
 815         addElementOffsetLater(myCodeFragment, false);
 816       }
 817       else {
 818         instruction.offset = -4; // -4 for return
 819         addElementOffsetLater(myFinallyBlocks.peek(), true);
 820       }
 821     }
 822   }
 823
 824   @Override public void visitSwitchLabelStatement(PsiSwitchLabelStatement statement) {
 825     startElement(statement);
 826     PsiExpression caseValue = statement.getCaseValue();
 827
 828     myStartStatementStack.pushStatement(caseValue, false);
 829     myEndStatementStack.pushStatement(caseValue, false);
 830
 831     if (caseValue != null) caseValue.accept(this);
 832
 833     myStartStatementStack.popStatement();
 834     myEndStatementStack.popStatement();
 835
 836     finishElement(statement);
 837   }
 838
 839   @Override public void visitSwitchStatement(PsiSwitchStatement statement) {
 840     startElement(statement);
 841
 842     PsiExpression expr = statement.getExpression();
 843     if (expr != null) {
 844       expr.accept(this);
 845     }
 846
 847     PsiCodeBlock body = statement.getBody();
 848     if (body != null) {
 849       PsiStatement[] statements = body.getStatements();
 850       PsiSwitchLabelStatement defaultLabel = null;
 851       for (PsiStatement aStatement : statements) {
 852         ProgressManager.getInstance().checkCanceled();
 853         if (aStatement instanceof PsiSwitchLabelStatement) {
 854           if (((PsiSwitchLabelStatement)aStatement).isDefaultCase()) {
 855             defaultLabel = (PsiSwitchLabelStatement)aStatement;
 856           }
 857           Instruction instruction = new ConditionalGoToInstruction(0, statement.getExpression());
 858           myCurrentFlow.addInstruction(instruction);
 859           addElementOffsetLater(aStatement, true);
 860         }
 861       }
 862       if (defaultLabel == null) {
 863         Instruction instruction = new GoToInstruction(0);
 864         myCurrentFlow.addInstruction(instruction);
 865         addElementOffsetLater(body, false);
 866       }
 867
 868       body.accept(this);
 869     }
 870
 871     finishElement(statement);
 872   }
 873
 874   @Override public void visitSynchronizedStatement(PsiSynchronizedStatement statement) {
 875     startElement(statement);
 876
 877     PsiExpression lock = statement.getLockExpression();
 878     if (lock != null) {
 879       lock.accept(this);
 880     }
 881
 882     PsiCodeBlock body = statement.getBody();
 883     if (body != null) {
 884       body.accept(this);
 885     }
 886
 887     finishElement(statement);
 888   }
 889
 890   @Override public void visitThrowStatement(PsiThrowStatement statement) {
 891     startElement(statement);
 892
 893     PsiExpression exception = statement.getException();
 894     if (exception != null) {
 895       exception.accept(this);
 896     }
 897     final List<PsiElement> blocks = findThrowToBlocks(statement);
 898     PsiElement element;
 899     if (blocks.isEmpty() || blocks.get(0) == null) {
 900       ThrowToInstruction instruction = new ThrowToInstruction(0);
 901       myCurrentFlow.addInstruction(instruction);
 902       if (myFinallyBlocks.isEmpty()) {
 903         element = myCodeFragment;
 904         addElementOffsetLater(element, false);
 905       }
 906       else {
 907         instruction.offset = -2; // -2 to rethrow exception
 908         element = myFinallyBlocks.peek();
 909         addElementOffsetLater(element, true);
 910       }
 911     }
 912     else {
 913       for (int i = 0; i < blocks.size(); i++) {
 914         ProgressManager.getInstance().checkCanceled();
 915         element = blocks.get(i);
 916         BranchingInstruction instruction = i == blocks.size() - 1
 917                                            ? new ThrowToInstruction(0)
 918                                            : new ConditionalThrowToInstruction(0);
 919         myCurrentFlow.addInstruction(instruction);
 920         instruction.offset = -1; // -1 to init catch param
 921         addElementOffsetLater(element, true);
 922       }
 923     }
 924
 925
 926     finishElement(statement);
 927   }
 928
 929   /**
 930    * find offsets of catch(es) corresponding to this throw statement
 931    * mycatchParameters and mycatchpoints arrays should be sorted in ascending scope order (from outermost to innermost)
 932    *
 933    * @return offset or -1 if not found
 934    */
 935   private List<PsiElement> findThrowToBlocks(PsiThrowStatement statement) {
 936     final PsiExpression exceptionExpr = statement.getException();
 937     if (exceptionExpr == null) return Collections.emptyList();
 938     final PsiType throwType = exceptionExpr.getType();
 939     if (!(throwType instanceof PsiClassType)) return Collections.emptyList();
 940     return findThrowToBlocks((PsiClassType)throwType);
 941   }
 942
 943   private List<PsiElement> findThrowToBlocks(PsiClassType throwType) {
 944     List<PsiElement> blocks = new ArrayList<PsiElement>();
 945     for (int i = myCatchParameters.size() - 1; i >= 0; i--) {
 946       ProgressManager.getInstance().checkCanceled();
 947       PsiParameter parameter = myCatchParameters.get(i);
 948       final PsiType type = parameter.getType();
 949       PsiClass catchedClass = PsiUtil.resolveClassInType(type);
 950       if (catchedClass == null) continue;
 951       if (type.isAssignableFrom(throwType)) {
 952         blocks.add(myCatchBlocks.get(i));
 953       }
 954       else if (throwType.isAssignableFrom(type)) {
 955         blocks.add(myCatchBlocks.get(i));
 956       }
 957     }
 958     if (blocks.isEmpty()) {
 959       // consider it as throw at the end of the control flow
 960       blocks.add(null);
 961     }
 962     return blocks;
 963   }
 964
 965   @Override public void visitAssertStatement(PsiAssertStatement statement) {
 966     startElement(statement);
 967
 968     // should not try to compute constant expression within assert
 969     // since assertions can be disabled/enabled at any moment via JVM flags
 970
 971     final PsiExpression condition = statement.getAssertCondition();
 972     if (condition != null) {
 973       myStartStatementStack.pushStatement(statement, false);
 974       myEndStatementStack.pushStatement(statement, false);
 975
 976       myEndJumpRoles.push(BranchingInstruction.Role.END);
 977       myStartJumpRoles.push(BranchingInstruction.Role.END);
 978
 979       condition.accept(this);
 980
 981       myStartJumpRoles.pop();
 982       myEndJumpRoles.pop();
 983
 984       myStartStatementStack.popStatement();
 985       myEndStatementStack.popStatement();
 986     }
 987     PsiExpression description = statement.getAssertDescription();
 988     if (description != null) {
 989       description.accept(this);
 990     }
 991
 992     Instruction instruction = new ConditionalThrowToInstruction(0, statement.getAssertCondition());
 993     myCurrentFlow.addInstruction(instruction);
 994     addElementOffsetLater(myCodeFragment, false);
 995
 996     finishElement(statement);
 997   }
 998
 999   @Override public void visitTryStatement(PsiTryStatement statement) {
1000     startElement(statement);
1001
1002     PsiCodeBlock[] catchBlocks = statement.getCatchBlocks();
1003     PsiParameter[] catchBlockParameters = statement.getCatchBlockParameters();
1004     int catchNum = Math.min(catchBlocks.length, catchBlockParameters.length);
1005     myUnhandledExceptionCatchBlocks.push(null);
1006     for (int i = catchNum - 1; i >= 0; i--) {
1007       ProgressManager.getInstance().checkCanceled();
1008       myCatchParameters.push(catchBlockParameters[i]);
1009       myCatchBlocks.push(catchBlocks[i]);
1010
1011       final PsiType type = catchBlockParameters[i].getType();
1012       // todo cast param
1013       if (type instanceof PsiClassType && ExceptionUtil.isUncheckedExceptionOrSuperclass((PsiClassType)type)) {
1014         myUnhandledExceptionCatchBlocks.push(catchBlocks[i]);
1015       }
1016     }
1017
1018     PsiCodeBlock finallyBlock = statement.getFinallyBlock();
1019
1020     if (finallyBlock != null) {
1021       myFinallyBlocks.push(finallyBlock);
1022     }
1023
1024     PsiCodeBlock tryBlock = statement.getTryBlock();
1025     if (tryBlock != null) {
1026       // javac works as if all checked exceptions can occur at the top of the block
1027       generateCheckedExceptionJumps(tryBlock);
1028       tryBlock.accept(this);
1029     }
1030
1031     while (myUnhandledExceptionCatchBlocks.pop() != null) ;
1032
1033     myCurrentFlow.addInstruction(new GoToInstruction(finallyBlock == null ? 0 : -6));
1034     if (finallyBlock == null) {
1035       addElementOffsetLater(statement, false);
1036     }
1037     else {
1038       addElementOffsetLater(finallyBlock, true);
1039     }
1040
1041     for (int i = 0; i < catchNum; i++) {
1042       myCatchParameters.pop();
1043       myCatchBlocks.pop();
1044     }
1045
1046     for (int i = catchNum - 1; i >= 0; i--) {
1047       ProgressManager.getInstance().checkCanceled();
1048       if (myPolicy.isParameterAccepted(catchBlockParameters[i])) {
1049         generateWriteInstruction(catchBlockParameters[i]);
1050       }
1051       PsiCodeBlock catchBlock = catchBlocks[i];
1052       assert catchBlock != null : i+statement.getText();
1053       catchBlock.accept(this);
1054
1055       myCurrentFlow.addInstruction(new GoToInstruction(finallyBlock == null ? 0 : -6));
1056       if (finallyBlock == null) {
1057         addElementOffsetLater(statement, false);
1058       }
1059       else {
1060         addElementOffsetLater(finallyBlock, true);
1061       }
1062     }
1063
1064     if (finallyBlock != null) {
1065       myFinallyBlocks.pop();
1066     }
1067
1068     if (finallyBlock != null) {
1069       // normal completion, call finally block and proceed
1070       myCurrentFlow.addInstruction(new CallInstruction(0, 0, myStack));
1071       addElementOffsetLater(finallyBlock, true);
1072       myCurrentFlow.addInstruction(new GoToInstruction(0));
1073       addElementOffsetLater(statement, false);
1074       // return completion, call finally block and return
1075       myCurrentFlow.addInstruction(new CallInstruction(0, 0, myStack));
1076       addElementOffsetLater(finallyBlock, true);
1077       addReturnInstruction(statement);
1078       // throw exception completion, call finally block and rethrow
1079       myCurrentFlow.addInstruction(new CallInstruction(0, 0, myStack));
1080       addElementOffsetLater(finallyBlock, true);
1081       final GoToInstruction gotoUncheckedRethrow = new GoToInstruction(0);
1082       myCurrentFlow.addInstruction(gotoUncheckedRethrow);
1083       addElementOffsetLater(finallyBlock, false);
1084
1085       finallyBlock.accept(this);
1086       final int procStart = myCurrentFlow.getStartOffset(finallyBlock);
1087       final int procEnd = myCurrentFlow.getEndOffset(finallyBlock);
1088       int offset = procStart - 6;
1089       final List<Instruction> instructions = myCurrentFlow.getInstructions();
1090       CallInstruction callInstruction = (CallInstruction)instructions.get(offset);
1091       callInstruction.procBegin = procStart;
1092       callInstruction.procEnd = procEnd;
1093       offset += 2;
1094       callInstruction = (CallInstruction)instructions.get(offset);
1095       callInstruction.procBegin = procStart;
1096       callInstruction.procEnd = procEnd;
1097       offset += 2;
1098       callInstruction = (CallInstruction)instructions.get(offset);
1099       callInstruction.procBegin = procStart;
1100       callInstruction.procEnd = procEnd;
1101
1102       // generate return instructions
1103       // first three return instructions are for normal completion, return statement call completion and unchecked exception throwing completion resp.
1104
1105       // normal completion
1106       myCurrentFlow.addInstruction(new ReturnInstruction(0, myStack, callInstruction));
1107
1108       // return statement call completion
1109       myCurrentFlow.addInstruction(new ReturnInstruction(procStart - 3, myStack, callInstruction));
1110
1111       // unchecked exception throwing completion
1112       myCurrentFlow.addInstruction(new ReturnInstruction(procStart - 1, myStack, callInstruction));
1113
1114       // checked exception throwing completion. need to dispatch to the correct catch clause
1115       final List<PsiElement> unhandledExceptionCatchBlocks = finallyBlockToUnhandledExceptions.remove(finallyBlock);
1116       for (int i = 0; unhandledExceptionCatchBlocks != null && i < unhandledExceptionCatchBlocks.size(); i++) {
1117         ProgressManager.getInstance().checkCanceled();
1118         PsiElement catchBlock = unhandledExceptionCatchBlocks.get(i);
1119
1120         final ReturnInstruction returnInstruction = new ReturnInstruction(0, myStack, callInstruction);
1121         returnInstruction.setRethrowFromFinally();
1122         myCurrentFlow.addInstruction(returnInstruction);
1123         if (catchBlock == null) {
1124           // dispatch to rethrowing exception code
1125           returnInstruction.offset = procStart - 1;
1126         }
1127         else {
1128           // dispatch to catch clause
1129           returnInstruction.offset--; // -1 for catch block init parameter instruction
1130           addElementOffsetLater(catchBlock, true);
1131         }
1132       }
1133
1134       // here generated rethrowing code for unchecked exceptions
1135       gotoUncheckedRethrow.offset = myCurrentFlow.getSize();
1136       generateUncheckedExceptionJumps(statement, false);
1137       // just in case
1138       myCurrentFlow.addInstruction(new ThrowToInstruction(0));
1139       addElementOffsetLater(myCodeFragment, false);
1140     }
1141
1142     finishElement(statement);
1143   }
1144
1145
1146   @Override public void visitWhileStatement(PsiWhileStatement statement) {
1147     startElement(statement);
1148     if (statement.getBody() == null) {
1149       myStartStatementStack.pushStatement(statement, false);
1150     }
1151     else {
1152       myStartStatementStack.pushStatement(statement.getBody(), true);
1153     }
1154     myEndStatementStack.pushStatement(statement, false);
1155
1156     PsiExpression condition = statement.getCondition();
1157     if (condition != null) {
1158       condition.accept(this);
1159     }
1160
1161
1162     Object loopCondition = myConstantEvaluationHelper.computeConstantExpression(statement.getCondition());
1163     if (loopCondition instanceof Boolean) {
1164       boolean value = ((Boolean)loopCondition).booleanValue();
1165       if (value) {
1166         emitEmptyInstruction();
1167       }
1168       else {
1169         myCurrentFlow.addInstruction(new GoToInstruction(0));
1170         addElementOffsetLater(statement, false);
1171       }
1172     }
1173     else {
1174       Instruction instruction = new ConditionalGoToInstruction(0, statement.getCondition());
1175       myCurrentFlow.addInstruction(instruction);
1176       addElementOffsetLater(statement, false);
1177     }
1178
1179     PsiStatement body = statement.getBody();
1180     if (body != null) {
1181       body.accept(this);
1182     }
1183     int offset = myCurrentFlow.getStartOffset(statement);
1184     Instruction instruction = new GoToInstruction(offset);
1185     myCurrentFlow.addInstruction(instruction);
1186
1187     myStartStatementStack.popStatement();
1188     myEndStatementStack.popStatement();
1189     finishElement(statement);
1190   }
1191
1192   @Override public void visitExpressionList(PsiExpressionList list) {
1193     PsiExpression[] expressions = list.getExpressions();
1194     for (final PsiExpression expression : expressions) {
1195       ProgressManager.getInstance().checkCanceled();
1196       myStartStatementStack.pushStatement(expression, false);
1197       myEndStatementStack.pushStatement(expression, false);
1198
1199       expression.accept(this);
1200       myStartStatementStack.popStatement();
1201       myEndStatementStack.popStatement();
1202     }
1203   }
1204
1205   @Override public void visitArrayAccessExpression(PsiArrayAccessExpression expression) {
1206     startElement(expression);
1207
1208     expression.getArrayExpression().accept(this);
1209     final PsiExpression indexExpression = expression.getIndexExpression();
1210     if (indexExpression != null) {
1211       indexExpression.accept(this);
1212     }
1213
1214     finishElement(expression);
1215   }
1216
1217   @Override public void visitArrayInitializerExpression(PsiArrayInitializerExpression expression) {
1218     startElement(expression);
1219
1220     PsiExpression[] initializers = expression.getInitializers();
1221     for (PsiExpression initializer : initializers) {
1222       ProgressManager.getInstance().checkCanceled();
1223       initializer.accept(this);
1224     }
1225
1226     finishElement(expression);
1227   }
1228
1229   @Override public void visitAssignmentExpression(PsiAssignmentExpression expression) {
1230     startElement(expression);
1231
1232     myStartStatementStack.pushStatement(expression.getRExpression() == null ? expression : expression.getRExpression(), false);
1233     myEndStatementStack.pushStatement(expression.getRExpression() == null ? expression : expression.getRExpression(), false);
1234
1235     PsiExpression rExpr = expression.getRExpression();
1236     if (rExpr != null) {
1237       rExpr.accept(this);
1238     }
1239
1240     PsiExpression lExpr = expression.getLExpression();
1241     if (lExpr instanceof PsiReferenceExpression) {
1242       final PsiReferenceExpression referenceExpression = (PsiReferenceExpression)lExpr;
1243       if (!referenceExpression.isQualified()
1244           || referenceExpression.getQualifierExpression() instanceof PsiThisExpression) {
1245
1246         PsiVariable variable = getUsedVariable(referenceExpression);
1247         if (variable != null) {
1248           if (myAssignmentTargetsAreElements)
1249             startElement(lExpr);
1250
1251           if (expression.getOperationSign().getTokenType() != JavaTokenType.EQ) {
1252             generateReadInstruction(variable);
1253           }
1254           generateWriteInstruction(variable);
1255
1256           if (myAssignmentTargetsAreElements) finishElement(lExpr);
1257         }
1258
1259       }
1260       else {
1261         lExpr.accept(this); //?
1262       }
1263     }
1264     else {
1265       lExpr.accept(this);
1266     }
1267
1268     myStartStatementStack.popStatement();
1269     myEndStatementStack.popStatement();
1270
1271     finishElement(expression);
1272   }
1273
1274   @Override public void visitBinaryExpression(PsiBinaryExpression expression) {
1275     startElement(expression);
1276
1277     final PsiExpression lOperand = expression.getLOperand();
1278     final PsiExpression rOperand = expression.getROperand();
1279     IElementType signTokenType = expression.getOperationSign().getTokenType();
1280
1281     if ((signTokenType == JavaTokenType.ANDAND || signTokenType == JavaTokenType.OROR) && myEnabledShortCircuit) {
1282       Object exprValue = myConstantEvaluationHelper.computeConstantExpression(lOperand);
1283       Boolean lvalue = null;
1284       if (exprValue instanceof Boolean) {
1285         myCurrentFlow.setConstantConditionOccurred(true);
1286         lvalue = shouldCalculateConstantExpression(expression) ? (Boolean)exprValue : null;
1287       }
1288       exprValue = myConstantEvaluationHelper.computeConstantExpression(rOperand);
1289       Boolean rvalue = null;
1290       if (exprValue instanceof Boolean) {
1291         myCurrentFlow.setConstantConditionOccurred(true);
1292         rvalue = shouldCalculateConstantExpression(expression) ? (Boolean)exprValue : null;
1293       }
1294       Boolean doShortcut;
1295       boolean shouldGenLOperand = true;
1296       if (lvalue != null) {
1297         doShortcut = lvalue.booleanValue() != (signTokenType == JavaTokenType.ANDAND);
1298       }
1299       else if (rvalue != null && rvalue.booleanValue() != (signTokenType == JavaTokenType.ANDAND)) {
1300         doShortcut = Boolean.TRUE;
1301         shouldGenLOperand = false; // case of 'if (x && false)...'
1302       }
1303       else {
1304         doShortcut = null;
1305       }
1306
1307       if (shouldGenLOperand) {
1308         generateLOperand(lOperand, rOperand, signTokenType);
1309       }
1310       BranchingInstruction.Role role = signTokenType == JavaTokenType.ANDAND ? myEndJumpRoles.peek() : myStartJumpRoles.peek();
1311       PsiElement gotoElement = signTokenType == JavaTokenType.ANDAND ? myEndStatementStack.peekElement() : myStartStatementStack.peekElement();
1312       boolean gotoIsAtStart = signTokenType == JavaTokenType.ANDAND ? myEndStatementStack.peekAtStart() : myStartStatementStack.peekAtStart();
1313       if (doShortcut == null) {
1314         myCurrentFlow.addInstruction(new ConditionalGoToInstruction(0, role, lOperand));
1315         addElementOffsetLater(gotoElement, gotoIsAtStart);
1316       }
1317       else if (doShortcut.booleanValue()) {
1318         myCurrentFlow.addInstruction(new GoToInstruction(0, role));
1319         addElementOffsetLater(gotoElement, gotoIsAtStart);
1320       }
1321     }
1322     else {
1323       generateLOperand(lOperand, rOperand, signTokenType);
1324     }
1325
1326     if (rOperand != null) {
1327       rOperand.accept(this);
1328     }
1329
1330     finishElement(expression);
1331   }
1332
1333   private void generateLOperand(PsiExpression lOperand, PsiExpression rOperand, IElementType signTokenType) {
1334     if (rOperand != null) {
1335       myStartJumpRoles.push(BranchingInstruction.Role.END);
1336       myEndJumpRoles.push(BranchingInstruction.Role.END);
1337       PsiElement then = signTokenType == JavaTokenType.OROR ? myStartStatementStack.peekElement() : rOperand;
1338       boolean thenAtStart = signTokenType == JavaTokenType.OROR ? myStartStatementStack.peekAtStart() : true;
1339       myStartStatementStack.pushStatement(then, thenAtStart);
1340       PsiElement elseS = signTokenType == JavaTokenType.ANDAND ? myEndStatementStack.peekElement() : rOperand;
1341       boolean elseAtStart = signTokenType == JavaTokenType.ANDAND ? myEndStatementStack.peekAtStart() : true;
1342       myEndStatementStack.pushStatement(elseS, elseAtStart);
1343     }
1344     lOperand.accept(this);
1345     if (rOperand != null) {
1346       myStartStatementStack.popStatement();
1347       myEndStatementStack.popStatement();
1348       myStartJumpRoles.pop();
1349       myEndJumpRoles.pop();
1350     }
1351   }
1352
1353   private static boolean isInsideIfCondition(PsiExpression expression) {
1354     PsiElement element = expression;
1355     while (element instanceof PsiExpression) {
1356       final PsiElement parent = element.getParent();
1357       if (parent instanceof PsiIfStatement && element == ((PsiIfStatement)parent).getCondition()) return true;
1358       element = parent;
1359     }
1360     return false;
1361   }
1362
1363   private boolean shouldCalculateConstantExpression(PsiExpression expression) {
1364     return myEvaluateConstantIfConfition || !isInsideIfCondition(expression);
1365   }
1366
1367   @Override public void visitClassObjectAccessExpression(PsiClassObjectAccessExpression expression) {
1368     visitChildren(expression);
1369
1370   }
1371
1372   private void visitChildren(PsiElement element) {
1373     startElement(element);
1374
1375     PsiElement[] children = element.getChildren();
1376     for (PsiElement child : children) {
1377       ProgressManager.getInstance().checkCanceled();
1378       child.accept(this);
1379     }
1380
1381     finishElement(element);
1382   }
1383
1384   @Override public void visitConditionalExpression(PsiConditionalExpression expression) {
1385     startElement(expression);
1386
1387     final PsiExpression condition = expression.getCondition();
1388     final PsiExpression thenExpression = expression.getThenExpression();
1389     final PsiExpression elseExpression = expression.getElseExpression();
1390     generateConditionalStatementInstructions(expression, condition, thenExpression, elseExpression);
1391
1392     finishElement(expression);
1393   }
1394
1395   @Override public void visitInstanceOfExpression(PsiInstanceOfExpression expression) {
1396     startElement(expression);
1397
1398     final PsiExpression operand = expression.getOperand();
1399     operand.accept(this);
1400
1401     finishElement(expression);
1402   }
1403
1404   @Override public void visitLiteralExpression(PsiLiteralExpression expression) {
1405     startElement(expression);
1406     finishElement(expression);
1407   }
1408
1409   @Override public void visitMethodCallExpression(PsiMethodCallExpression expression) {
1410     startElement(expression);
1411
1412     final PsiReferenceExpression methodExpression = expression.getMethodExpression();
1413     methodExpression.accept(this);
1414     final PsiExpressionList argumentList = expression.getArgumentList();
1415     argumentList.accept(this);
1416     // just to increase counter - there is some executable code here
1417     emitEmptyInstruction();
1418
1419     generateCheckedExceptionJumps(expression);
1420
1421     finishElement(expression);
1422   }
1423
1424   @Override public void visitNewExpression(PsiNewExpression expression) {
1425     startElement(expression);
1426
1427     int pc = myCurrentFlow.getSize();
1428     PsiElement[] children = expression.getChildren();
1429     for (PsiElement child : children) {
1430       ProgressManager.getInstance().checkCanceled();
1431       child.accept(this);
1432     }
1433     generateCheckedExceptionJumps(expression);
1434
1435     if (pc == myCurrentFlow.getSize()) {
1436       // generate at least one instruction for constructor call
1437       emitEmptyInstruction();
1438     }
1439
1440     finishElement(expression);
1441   }
1442
1443   @Override public void visitParenthesizedExpression(PsiParenthesizedExpression expression) {
1444     visitChildren(expression);
1445   }
1446
1447   @Override public void visitPostfixExpression(PsiPostfixExpression expression) {
1448     startElement(expression);
1449
1450     IElementType op = expression.getOperationSign().getTokenType();
1451     PsiExpression operand = expression.getOperand();
1452     operand.accept(this);
1453     if (op == JavaTokenType.PLUSPLUS || op == JavaTokenType.MINUSMINUS) {
1454       if (operand instanceof PsiReferenceExpression) {
1455         PsiVariable variable = getUsedVariable((PsiReferenceExpression)operand);
1456         if (variable != null) {
1457           generateWriteInstruction(variable);
1458         }
1459       }
1460     }
1461
1462     finishElement(expression);
1463   }
1464
1465   @Override public void visitPrefixExpression(PsiPrefixExpression expression) {
1466     startElement(expression);
1467
1468     PsiExpression operand = expression.getOperand();
1469     if (operand != null) {
1470       IElementType operationSign = expression.getOperationSign().getTokenType();
1471       if (operationSign == JavaTokenType.EXCL) {
1472         // negation inverts jump targets
1473         PsiElement topStartStatement = myStartStatementStack.peekElement();
1474         boolean topAtStart = myStartStatementStack.peekAtStart();
1475         myStartStatementStack.pushStatement(myEndStatementStack.peekElement(), myEndStatementStack.peekAtStart());
1476         myEndStatementStack.pushStatement(topStartStatement, topAtStart);
1477       }
1478
1479       operand.accept(this);
1480
1481       if (operationSign == JavaTokenType.EXCL) {
1482         // negation inverts jump targets
1483         myStartStatementStack.popStatement();
1484         myEndStatementStack.popStatement();
1485       }
1486
1487       if (operand instanceof PsiReferenceExpression &&
1488           (operationSign == JavaTokenType.PLUSPLUS || operationSign == JavaTokenType.MINUSMINUS)) {
1489         PsiVariable variable = getUsedVariable((PsiReferenceExpression)operand);
1490         if (variable != null) {
1491           generateWriteInstruction(variable);
1492         }
1493       }
1494     }
1495
1496     finishElement(expression);
1497   }
1498
1499   @Override public void visitReferenceExpression(PsiReferenceExpression expression) {
1500     startElement(expression);
1501
1502     PsiExpression qualifier = expression.getQualifierExpression();
1503     if (qualifier != null) {
1504       qualifier.accept(this);
1505     }
1506
1507     PsiVariable variable = getUsedVariable(expression);
1508     if (variable != null) {
1509       generateReadInstruction(variable);
1510     }
1511
1512     finishElement(expression);
1513   }
1514
1515
1516   @Override public void visitSuperExpression(PsiSuperExpression expression) {
1517     startElement(expression);
1518     finishElement(expression);
1519   }
1520
1521   @Override public void visitThisExpression(PsiThisExpression expression) {
1522     startElement(expression);
1523     finishElement(expression);
1524   }
1525
1526   @Override public void visitTypeCastExpression(PsiTypeCastExpression expression) {
1527     startElement(expression);
1528     PsiExpression operand = expression.getOperand();
1529     if (operand != null) {
1530       operand.accept(this);
1531
1532     }
1533     finishElement(expression);
1534   }
1535
1536   @Override public void visitClass(PsiClass aClass) {
1537     startElement(aClass);
1538     // anonymous or local class
1539     if (aClass instanceof PsiAnonymousClass) {
1540       final PsiElement arguments = PsiTreeUtil.getChildOfType(aClass, PsiExpressionList.class);
1541       if (arguments != null) arguments.accept(this);
1542     }
1543     List<PsiVariable> array = new ArrayList<PsiVariable>();
1544     addUsedVariables(array, aClass);
1545     for (PsiVariable var : array) {
1546       ProgressManager.getInstance().checkCanceled();
1547       generateReadInstruction(var);
1548     }
1549     finishElement(aClass);
1550   }
1551
1552   private void addUsedVariables(List<PsiVariable> array, PsiElement scope) {
1553     if (scope instanceof PsiReferenceExpression) {
1554       PsiVariable variable = getUsedVariable((PsiReferenceExpression)scope);
1555       if (variable != null) {
1556         if (!array.contains(variable)) {
1557           array.add(variable);
1558         }
1559       }
1560     }
1561
1562     PsiElement[] children = scope.getChildren();
1563     for (PsiElement child : children) {
1564       ProgressManager.getInstance().checkCanceled();
1565       addUsedVariables(array, child);
1566     }
1567   }
1568
1569   private void generateReadInstruction(PsiVariable variable) {
1570     Instruction instruction = new ReadVariableInstruction(variable);
1571     myCurrentFlow.addInstruction(instruction);
1572   }
1573
1574   private void generateWriteInstruction(PsiVariable variable) {
1575     Instruction instruction = new WriteVariableInstruction(variable);
1576     myCurrentFlow.addInstruction(instruction);
1577   }
1578
1579   private PsiVariable getUsedVariable(PsiReferenceExpression refExpr) {
1580     if (refExpr.getParent() instanceof PsiMethodCallExpression) return null;
1581     return myPolicy.getUsedVariable(refExpr);
1582   }
1583 }