// Copyright 2000-2024 JetBrains s.r.o. and contributors. Use of this source code is governed by the Apache 2.0 license.
package com.intellij.codeInspection.dataFlow.java;

import com.intellij.codeInsight.ExceptionUtil;
import com.intellij.codeInsight.Nullability;
import com.intellij.codeInsight.daemon.ImplicitUsageProvider;
import com.intellij.codeInsight.daemon.impl.UnusedSymbolUtil;
import com.intellij.codeInsight.daemon.impl.analysis.JavaGenericsUtil;
import com.intellij.codeInspection.dataFlow.*;
import com.intellij.codeInspection.dataFlow.java.anchor.JavaExpressionAnchor;
import com.intellij.codeInspection.dataFlow.java.anchor.JavaPolyadicPartAnchor;
import com.intellij.codeInspection.dataFlow.java.anchor.JavaSwitchLabelTakenAnchor;
import com.intellij.codeInspection.dataFlow.java.inliner.*;
import com.intellij.codeInspection.dataFlow.java.inst.*;
import com.intellij.codeInspection.dataFlow.jvm.JvmPsiRangeSetUtil;
import com.intellij.codeInspection.dataFlow.jvm.SpecialField;
import com.intellij.codeInspection.dataFlow.jvm.TrapTracker;
import com.intellij.codeInspection.dataFlow.jvm.descriptors.*;
import com.intellij.codeInspection.dataFlow.jvm.problems.ArrayIndexProblem;
import com.intellij.codeInspection.dataFlow.jvm.problems.ConsumedStreamProblem;
import com.intellij.codeInspection.dataFlow.jvm.problems.ContractFailureProblem;
import com.intellij.codeInspection.dataFlow.jvm.problems.NegativeArraySizeProblem;
import com.intellij.codeInspection.dataFlow.jvm.transfer.*;
import com.intellij.codeInspection.dataFlow.jvm.transfer.EnterFinallyTrap.TwrFinally;
import com.intellij.codeInspection.dataFlow.jvm.transfer.TryCatchTrap.CatchClauseDescriptor;
import com.intellij.codeInspection.dataFlow.jvm.transfer.TryCatchTrap.JavaCatchClauseDescriptor;
import com.intellij.codeInspection.dataFlow.lang.DfaAnchor;
import com.intellij.codeInspection.dataFlow.lang.ir.*;
import com.intellij.codeInspection.dataFlow.lang.ir.ControlFlow.ControlFlowOffset;
import com.intellij.codeInspection.dataFlow.lang.ir.ControlFlow.DeferredOffset;
import com.intellij.codeInspection.dataFlow.rangeSet.LongRangeBinOp;
import com.intellij.codeInspection.dataFlow.rangeSet.LongRangeSet;
import com.intellij.codeInspection.dataFlow.types.DfStreamStateType;
import com.intellij.codeInspection.dataFlow.types.DfType;
import com.intellij.codeInspection.dataFlow.types.DfTypes;
import com.intellij.codeInspection.dataFlow.value.*;
import com.intellij.codeInspection.dataFlow.value.DfaControlTransferValue.Trap;
import com.intellij.openapi.diagnostic.Logger;
import com.intellij.pom.java.JavaFeature;
import com.intellij.psi.*;
import com.intellij.psi.augment.PsiAugmentProvider;
import com.intellij.psi.impl.source.tree.java.PsiEmptyExpressionImpl;
import com.intellij.psi.tree.IElementType;
import com.intellij.psi.util.*;
import com.intellij.psi.util.InheritanceUtil;
import com.intellij.util.ArrayUtil;
import com.intellij.util.IncorrectOperationException;
import com.intellij.util.ObjectUtils;
import com.intellij.util.containers.ContainerUtil;
import com.intellij.util.containers.FList;
import com.siyeh.ig.callMatcher.CallMatcher;
import com.siyeh.ig.psiutils.*;
import one.util.streamex.StreamEx;
import org.jetbrains.annotations.Contract;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;

import java.util.*;

import static com.intellij.psi.CommonClassNames.*;

public class ControlFlowAnalyzer extends JavaElementVisitor {
  private static final Logger LOG = Logger.getInstance(ControlFlowAnalyzer.class);
  private static final CallMatcher LIST_INITIALIZER = CallMatcher.anyOf(
    CallMatcher.staticCall(JAVA_UTIL_ARRAYS, "asList"),
    CallMatcher.staticCall(JAVA_UTIL_LIST, "of"));
  static final int MAX_UNROLL_SIZE = 3;
  private static final int MAX_ARRAY_INDEX_FOR_INITIALIZER = 32;
  private final PsiElement myCodeFragment;
  private final boolean myInlining;
  private final DfaValueFactory myFactory;
  private final TrapTracker myTrapTracker;
  private ControlFlow myCurrentFlow;
  private final Map<PsiExpression, NullabilityProblemKind<? super PsiExpression>> myCustomNullabilityProblems = new HashMap<>();
  private ExpressionBlockContext myExpressionBlockContext;

  /**
   * @param valueFactory factory to create values
   * @param codeFragment code fragment to analyze:
   *                     normally a PsiCodeBlock or PsiExpression.
   *                     If PsiWhileStatement or PsiDoWhileStatement then only one loop iteration will be analyzed
   *                     (similar to analyzing the loop body, but condition is analyzed as well).
   *                     If PsiClass then class initializers + field initializers will be analyzed
   * @param inlining if true inlining is performed for known method calls
   */
  ControlFlowAnalyzer(@NotNull DfaValueFactory valueFactory, @NotNull PsiElement codeFragment, boolean inlining) {
    myInlining = inlining;
    myFactory = valueFactory;
    myCodeFragment = codeFragment;
    myTrapTracker = new TrapTracker(valueFactory, JavaClassDef.typeConstraintFactory(codeFragment));
  }

  private void buildClassInitializerFlow(PsiClass psiClass, boolean isStatic) {
    for (PsiElement element = psiClass.getFirstChild(); element != null; element = element.getNextSibling()) {
      if (element instanceof PsiField field &&
          !field.hasInitializer() && field.hasModifierProperty(PsiModifier.STATIC) == isStatic) {
        visitField(field);
      }
    }
    if (!isStatic &&
        ContainerUtil.exists(ImplicitUsageProvider.EP_NAME.getExtensionList(), p -> p.isClassWithCustomizedInitialization(psiClass))) {
      addInstruction(new EscapeInstruction(List.of(new ThisDescriptor(psiClass))));
      addInstruction(new FlushFieldsInstruction());
    }
    for (PsiElement element = psiClass.getFirstChild(); element != null; element = element.getNextSibling()) {
      if ((element instanceof PsiField field &&
           field.hasInitializer() && PsiAugmentProvider.canTrustFieldInitializer(field) || element instanceof PsiClassInitializer) &&
          ((PsiMember)element).hasModifierProperty(PsiModifier.STATIC) == isStatic) {
        element.accept(this);
      }
    }
    if (!isStatic) {
      addInstruction(new EndOfInstanceInitializerInstruction());
    }
    addInstruction(new FlushFieldsInstruction());
  }

  @Nullable ControlFlow buildControlFlow() {
    myCurrentFlow = new ControlFlow(myFactory, myCodeFragment);
    addInstruction(new FinishElementInstruction(null)); // to initialize LVA
    try {
      if (myCodeFragment instanceof PsiClass psiClass) {
        // if(unknown) { staticInitializer(); } else { instanceInitializer(); }
        pushUnknown();
        ConditionalGotoInstruction conditionalGoto = new ConditionalGotoInstruction(null, DfType.TOP);
        addInstruction(conditionalGoto);
        buildClassInitializerFlow(psiClass, true);
        GotoInstruction unconditionalGoto = new GotoInstruction(null);
        addInstruction(unconditionalGoto);
        conditionalGoto.setOffset(getInstructionCount());
        buildClassInitializerFlow(psiClass, false);
        unconditionalGoto.setOffset(getInstructionCount());
      } else {
        myCodeFragment.accept(this);
      }
    }
    catch (CannotAnalyzeException e) {
      return null;
    }

    myCurrentFlow.finish();
    return myCurrentFlow;
  }

  DfaValueFactory getFactory() {
    return myFactory;
  }

  private void removeVariable(@Nullable PsiVariable variable) {
    if (variable == null) return;
    myCurrentFlow.addInstruction(new FlushVariableInstruction(PlainDescriptor.createVariableValue(getFactory(), variable)));
  }

  void addInstruction(Instruction i) {
    myCurrentFlow.addInstruction(i);
  }

  int getInstructionCount() {
    return myCurrentFlow.getInstructionCount();
  }

  private ControlFlowOffset getEndOffset(PsiElement element) {
    assert !(element instanceof PsiExpression) || element instanceof PsiSwitchExpression;
    return myCurrentFlow.getEndOffset(element);
  }

  private ControlFlowOffset getStartOffset(PsiElement element) {
    assert !(element instanceof PsiExpression) || element instanceof PsiSwitchExpression;
    return myCurrentFlow.getStartOffset(element);
  }

  private void startElement(@NotNull PsiElement element) {
    myCurrentFlow.startElement(element);
  }

  private void finishElement(@NotNull PsiElement element) {
    myCurrentFlow.finishElement(element);
    if (element instanceof PsiField || (element instanceof PsiStatement && !(element instanceof PsiReturnStatement) &&
        !(element instanceof PsiSwitchLabeledRuleStatement))) {
      int startOffset = myCurrentFlow.getStartOffset(element).getInstructionOffset();
      List<VariableDescriptor> synthetics = myFactory.getTempVariableDescriptorsFrom(startOffset);
      FinishElementInstruction instruction = new FinishElementInstruction(element);
      instruction.flushVars(synthetics);
      addInstruction(instruction);
    }
  }

  @Override
  public void visitErrorElement(@NotNull PsiErrorElement element) {
    throw new CannotAnalyzeException();
  }

  @Override public void visitAssignmentExpression(@NotNull PsiAssignmentExpression expression) {
    PsiExpression rExpr = expression.getRExpression();

    startElement(expression);
    if (rExpr == null) {
      pushUnknown();
      finishElement(expression);
      return;
    }

    IElementType op = expression.getOperationTokenType();
    PsiType type = expression.getType();
    PsiExpression lExpr = expression.getLExpression();
    PsiArrayAccessExpression arrayStore = ObjectUtils.tryCast(lExpr, PsiArrayAccessExpression.class);
    if (arrayStore != null) {
      pushArrayAndIndex(arrayStore);
    } else {
      lExpr.accept(this);
    }
    if (op == JavaTokenType.EQ) {
      rExpr.accept(this);
      generateBoxingUnboxingInstructionFor(rExpr, type);
    }
    else {
      if (arrayStore != null) {
        // duplicate array and index on the stack
        addInstruction(new SpliceInstruction(2, 1, 0, 1, 0));
        readArrayElement(arrayStore);
      } else {
        addInstruction(new DupInstruction());
      }
      IElementType sign = TypeConversionUtil.convertEQtoOperation(op);
      PsiType resType = TypeConversionUtil.calcTypeForBinaryExpression(lExpr.getType(), rExpr.getType(), sign, true);
      generateBoxingUnboxingInstructionFor(lExpr, resType);
      rExpr.accept(this);
      generateBoxingUnboxingInstructionFor(rExpr, resType);
      generateBinOp(new JavaExpressionAnchor(expression), sign, rExpr, resType);
      generateBoxingUnboxingInstructionFor(rExpr, resType, type, false);
    }

    if (arrayStore != null) {
      DfaControlTransferValue transfer = createTransfer("java.lang.ArrayIndexOutOfBoundsException");
      VariableDescriptor staticDescriptor = ArrayElementDescriptor.fromArrayAccess(arrayStore);
      addInstruction(new JavaArrayStoreInstruction(arrayStore, rExpr, transfer, staticDescriptor));
    } else {
      addInstruction(new AssignInstruction(rExpr, JavaDfaValueFactory.getExpressionDfaValue(myFactory, lExpr)));
    }
    addNullCheck(expression);

    finishElement(expression);
  }

  @Override public void visitAssertStatement(@NotNull PsiAssertStatement statement) {
    startElement(statement);
    addInstruction(new PushInstruction(AssertionDisabledDescriptor.createAssertionsDisabledVar(myFactory), null));
    ConditionalGotoInstruction jump = new ConditionalGotoInstruction(null, DfTypes.TRUE);
    addInstruction(jump);
    final PsiExpression condition = statement.getAssertCondition();
    if (condition != null) {
      condition.accept(this);
      generateBoxingUnboxingInstructionFor(condition, PsiTypes.booleanType());
      addInstruction(new ConditionalGotoInstruction(getEndOffset(statement), DfTypes.TRUE, condition));
      final PsiExpression description = statement.getAssertDescription();
      if (description != null) {
        description.accept(this);
      }

      addInstruction(new ThrowInstruction(myTrapTracker.transferValue(JAVA_LANG_ASSERTION_ERROR), statement));
    }
    jump.setOffset(getInstructionCount());
    finishElement(statement);
  }

  @Override public void visitDeclarationStatement(@NotNull PsiDeclarationStatement statement) {
    startElement(statement);
    int startSize = getInstructionCount();

    PsiElement[] elements = statement.getDeclaredElements();
    for (PsiElement element : elements) {
      if (element instanceof PsiClass) {
        handleClosure(element);
      }
      else if (element instanceof PsiVariable variable) {
        PsiExpression initializer = variable.getInitializer();
        if (initializer != null) {
          initializeVariable(variable, initializer);
        }
      }
    }
    if (getInstructionCount() == startSize) {
      // Add no-op instruction if the statement has no instructions at all,
      // so it could be anchored in debugger.
      addInstruction(new SpliceInstruction(0));
    }

    finishElement(statement);
  }

  @Override
  public void visitField(@NotNull PsiField field) {
    PsiExpression initializer = field.getInitializer();
    if (initializer != null) {
      startElement(field);
      initializeVariable(field, initializer);
      finishElement(field);
    }
    else if (!field.hasModifierProperty(PsiModifier.FINAL) && !UnusedSymbolUtil.isImplicitWrite(field)) {
      // initialize with default value
      DfaVariableValue dfaVariable = PlainDescriptor.createVariableValue(myFactory, field);
      new CFGBuilder(this).assignAndPop(dfaVariable, DfTypes.defaultValue(field.getType()));
    }
  }

  @Override
  public void visitClassInitializer(@NotNull PsiClassInitializer initializer) {
    visitCodeBlock(initializer.getBody());
  }

  private void initializeVariable(PsiVariable variable, PsiExpression initializer) {
    if (JavaDfaValueFactory.ignoreInitializer(variable)) return;
    DfaVariableValue dfaVariable = PlainDescriptor.createVariableValue(myFactory, variable);
    addInstruction(new JvmPushForWriteInstruction(dfaVariable));
    initializer.accept(this);
    generateBoxingUnboxingInstructionFor(initializer, variable.getType());
    addInstruction(new AssignInstruction(initializer, dfaVariable));
    addInstruction(new PopInstruction());
  }

  @Override
  public void visitCodeFragment(@NotNull JavaCodeFragment codeFragment) {
    startElement(codeFragment);
    if (codeFragment instanceof PsiExpressionCodeFragment expressionCodeFragment) {
      PsiExpression expression = expressionCodeFragment.getExpression();
      if (expression != null) {
        expression.accept(this);
      }
    }
    finishElement(codeFragment);
  }

  @Override public void visitCodeBlock(@NotNull PsiCodeBlock block) {
    startElement(block);

    PsiStatement[] blockStatements = block.getStatements();
    for (PsiStatement statement : blockStatements) {
      statement.accept(this);
    }

    flushCodeBlockVariables(blockStatements, block.getParent());

    finishElement(block);
  }

  private void flushCodeBlockVariables(PsiStatement @NotNull [] statements, @Nullable PsiElement parent) {
    for (PsiStatement statement : statements) {
      if (statement instanceof PsiDeclarationStatement declarationStatement) {
        for (PsiElement declaration : declarationStatement.getDeclaredElements()) {
          if (declaration instanceof PsiVariable variable) {
            removeVariable(variable);
          }
        }
      }
    }
    if (parent instanceof PsiCatchSection catchSection) {
      removeVariable(catchSection.getParameter());
    }
    else if (parent instanceof PsiForeachStatement forEach) {
      removeVariable(forEach.getIterationParameter());
    }
    else if (parent instanceof PsiForStatement forStatement) {
      PsiStatement statement = forStatement.getInitialization();
      if (statement instanceof PsiDeclarationStatement declarationStatement) {
        for (PsiElement declaration : declarationStatement.getDeclaredElements()) {
          if (declaration instanceof PsiVariable variable) {
            removeVariable(variable);
          }
        }
      }
    }
    else if (parent instanceof PsiTryStatement tryStatement) {
      PsiResourceList list = tryStatement.getResourceList();
      if (list != null) {
        for (PsiResourceListElement resource : list) {
          if (resource instanceof PsiResourceVariable variable) {
            removeVariable(variable);
          }
        }
      }
    }
  }

  @Override public void visitBlockStatement(@NotNull PsiBlockStatement statement) {
    startElement(statement);
    statement.getCodeBlock().accept(this);
    finishElement(statement);
  }

  @Override public void visitBreakStatement(@NotNull PsiBreakStatement statement) {
    startElement(statement);
    jumpOut(statement.findExitedStatement());
    finishElement(statement);
  }

  @Override
  public void visitYieldStatement(@NotNull PsiYieldStatement statement) {
    startElement(statement);
    PsiSwitchExpression enclosing = statement.findEnclosingExpression();
    PsiExpression expression = statement.getExpression();
    if (enclosing != null && myExpressionBlockContext != null && myExpressionBlockContext.myCodeBlock == enclosing.getBody()) {
      myExpressionBlockContext.generateReturn(expression, this);
    } else {
      // yield in incorrect location or only part of switch is analyzed
      if (expression != null) {
        expression.accept(this);
        addInstruction(new PopInstruction());
      }
      jumpOut(enclosing);
    }
    finishElement(statement);
  }

  void addNullCheck(@NotNull PsiExpression expression) {
    addNullCheck(NullabilityProblemKind.fromContext(expression, myCustomNullabilityProblems));
  }

  void addNullCheck(@Nullable NullabilityProblemKind.NullabilityProblem<?> problem) {
    if (problem != null) {
      DfaControlTransferValue transfer =
        problem.thrownException() != null ? myTrapTracker.maybeTransferValue(problem.thrownException()) : null;
      addInstruction(new CheckNotNullInstruction(problem, transfer));
    }
  }

  private void jumpOut(PsiElement exitedStatement) {
    if (exitedStatement != null && PsiTreeUtil.isAncestor(myCodeFragment, exitedStatement, false)) {
      controlTransfer(createTransfer(exitedStatement, exitedStatement),
                      myTrapTracker.getTrapsInsideElement(exitedStatement));
    } else {
      // Jumping out of analyzed code fragment
      controlTransfer(DfaControlTransferValue.RETURN_TRANSFER, myTrapTracker.getTrapsInsideElement(myCodeFragment));
    }
  }

  private void controlTransfer(@NotNull DfaControlTransferValue.TransferTarget target, FList<Trap> traps) {
    addInstruction(new ControlTransferInstruction(myFactory.controlTransfer(target, traps)));
  }

  @Override public void visitContinueStatement(@NotNull PsiContinueStatement statement) {
    startElement(statement);
    PsiStatement continuedStatement = statement.findContinuedStatement();
    if (continuedStatement instanceof PsiLoopStatement loopStatement && PsiTreeUtil.isAncestor(myCodeFragment, continuedStatement, true)) {
      PsiStatement body = loopStatement.getBody();
      controlTransfer(createTransfer(body, body), myTrapTracker.getTrapsInsideElement(body));
    }
    else {
      // Jumping out of analyzed code fragment
      controlTransfer(DfaControlTransferValue.RETURN_TRANSFER, myTrapTracker.getTrapsInsideElement(myCodeFragment));
    }
    finishElement(statement);
  }

  @Override public void visitDoWhileStatement(@NotNull PsiDoWhileStatement statement) {
    startElement(statement);

    PsiStatement body = statement.getBody();
    if (body != null) {
      body.accept(this);
      PsiExpression condition = statement.getCondition();
      if (condition != null) {
        condition.accept(this);
        generateBoxingUnboxingInstructionFor(condition, PsiTypes.booleanType());
        if (statement == myCodeFragment) {
          addInstruction(new PopInstruction());
        } else {
          addInstruction(new ConditionalGotoInstruction(getStartOffset(statement), DfTypes.TRUE, condition));
        }
      }
    }

    finishElement(statement);
  }

  @Override public void visitEmptyStatement(@NotNull PsiEmptyStatement statement) {
    startElement(statement);
    finishElement(statement);
  }

  @Override public void visitExpressionStatement(@NotNull PsiExpressionStatement statement) {
    startElement(statement);
    final PsiExpression expr = statement.getExpression();
    expr.accept(this);
    addInstruction(new PopInstruction());
    finishElement(statement);
  }

  @Override public void visitExpressionListStatement(@NotNull PsiExpressionListStatement statement) {
    startElement(statement);
    PsiExpression[] expressions = statement.getExpressionList().getExpressions();
    for (PsiExpression expr : expressions) {
      expr.accept(this);
      addInstruction(new PopInstruction());
    }
    finishElement(statement);
  }

  private DfaValue getIteratedElement(PsiType type, PsiExpression iteratedValue) {
    PsiExpression[] expressions = null;
    if (iteratedValue instanceof PsiNewExpression newExpression) {
      PsiArrayInitializerExpression initializer = newExpression.getArrayInitializer();
      if (initializer != null) {
        expressions = initializer.getInitializers();
      }
    }
    else if (iteratedValue instanceof PsiReferenceExpression ref && ref.resolve() instanceof PsiVariable arrayVar) {
      expressions = ExpressionUtils.getConstantArrayElements(arrayVar);
    }
    if (iteratedValue instanceof PsiMethodCallExpression call && LIST_INITIALIZER.test(call)) {
      expressions = call.getArgumentList().getExpressions();
    }
    return expressions == null ? getFactory().getUnknown() : JavaDfaValueFactory.createCommonValue(getFactory(), expressions, type);
  }

  @Override
  public void visitForeachPatternStatement(@NotNull PsiForeachPatternStatement statement) {
    processForeach(statement);
  }

  @Override 
  public void visitForeachStatement(@NotNull PsiForeachStatement statement) {
    processForeach(statement);
  }
  
  private void processForeach(@NotNull PsiForeachStatementBase statement) {
    startElement(statement);
    final PsiExpression iteratedValue = PsiUtil.skipParenthesizedExprDown(statement.getIteratedValue());

    ControlFlowOffset loopEndOffset = getEndOffset(statement);
    boolean hasSizeCheck = false;

    if (iteratedValue != null) {
      iteratedValue.accept(this);

      PsiType type = iteratedValue.getType();
      SpecialField length = null;
      if (type instanceof PsiArrayType) {
        length = SpecialField.ARRAY_LENGTH;
      }
      else if (InheritanceUtil.isInheritor(type, JAVA_UTIL_COLLECTION)) {
        length = SpecialField.COLLECTION_SIZE;
      }
      if (length != null) {
        addInstruction(new GetQualifiedValueInstruction(length));
        addInstruction(new ConditionalGotoInstruction(loopEndOffset, DfTypes.intValue(0)));
        hasSizeCheck = true;
      } else {
        addInstruction(new PopInstruction());
      }
    }

    ControlFlowOffset offset = myCurrentFlow.getNextOffset();
    if (statement instanceof PsiForeachStatement normalForeach) {
      PsiParameter parameter = normalForeach.getIterationParameter();
      DfaVariableValue dfaVariable = PlainDescriptor.createVariableValue(myFactory, parameter);
      DfaValue commonValue = getIteratedElement(parameter.getType(), iteratedValue);
      if (DfaTypeValue.isUnknown(commonValue)) {
        addInstruction(new FlushVariableInstruction(dfaVariable));
      } else {
        new CFGBuilder(this).pushForWrite(dfaVariable).push(commonValue).assign().pop();
      }
    }
    else if (statement instanceof PsiForeachPatternStatement patternForeach &&
             patternForeach.getIterationPattern() instanceof PsiDeconstructionPattern pattern) {
      PsiType contextType = JavaPsiPatternUtil.getContextType(pattern);
      if (contextType == null) {
        contextType = TypeUtils.getObjectType(statement);
      }
      DfaValue commonValue = getIteratedElement(contextType, iteratedValue);
      addInstruction(new PushInstruction(commonValue, null));
      DeferredOffset endPattern = new DeferredOffset();
      processPattern(pattern, pattern, contextType,null, endPattern);
      endPattern.setOffset(getInstructionCount());
      addInstruction(new EnsureInstruction(null, RelationType.EQ, DfTypes.TRUE, null));
      addInstruction(new PopInstruction());
    }

    if (!hasSizeCheck) {
      pushUnknown();
      addInstruction(new ConditionalGotoInstruction(loopEndOffset, DfType.TOP));
    }

    final PsiStatement body = statement.getBody();
    if (body != null) {
      body.accept(this);
    }

    if (hasSizeCheck) {
      pushUnknown();
      addInstruction(new ConditionalGotoInstruction(loopEndOffset, DfType.TOP));
    }

    addInstruction(new GotoInstruction(offset));

    finishElement(statement);
  }

  @Override public void visitForStatement(@NotNull PsiForStatement statement) {
    startElement(statement);
    final ArrayList<PsiElement> declaredVariables = new ArrayList<>();

    PsiStatement initialization = statement.getInitialization();
    if (initialization != null) {
      initialization.accept(this);
      initialization.accept(new JavaRecursiveElementWalkingVisitor() {
        @Override
        public void visitReferenceExpression(@NotNull PsiReferenceExpression expression) {
          visitElement(expression);
        }

        @Override
        public void visitDeclarationStatement(@NotNull PsiDeclarationStatement statement) {
          PsiElement[] declaredElements = statement.getDeclaredElements();
          for (PsiElement element : declaredElements) {
            if (element instanceof PsiVariable) {
              declaredVariables.add(element);
            }
          }
        }
      });
    }

    PsiExpression condition = statement.getCondition();
    if (condition != null) {
      condition.accept(this);
      generateBoxingUnboxingInstructionFor(condition, PsiTypes.booleanType());
    }
    else {
      addInstruction(new PushValueInstruction(statement.getRParenth() == null ? DfTypes.BOOLEAN : DfTypes.TRUE));
    }
    addInstruction(new ConditionalGotoInstruction(getEndOffset(statement), DfTypes.FALSE, condition));

    PsiStatement body = statement.getBody();
    if (body != null) {
      body.accept(this);
    }

    ControlFlowOffset offset = initialization != null ? getEndOffset(initialization) : getStartOffset(statement);

    if (!addCountingLoopBound(statement, offset)) {
      PsiStatement update = statement.getUpdate();
      if (update != null) {
        update.accept(this);
      }
      addInstruction(new GotoInstruction(offset));
    }

    finishElement(statement);

    for (PsiElement declaredVariable : declaredVariables) {
      PsiVariable psiVariable = (PsiVariable)declaredVariable;
      removeVariable(psiVariable);
    }
  }

  private static @Nullable Long asLong(PsiExpression expression) {
    Object value = ExpressionUtils.computeConstantExpression(expression);
    if(value instanceof Integer || value instanceof Long) {
      return ((Number)value).longValue();
    }
    return null;
  }

  /**
   * Add known-to-be-true condition inside counting loop, effectively converting
   * {@code for(int i=origin; i<bound; i++)} to
   * {@code int i = origin; while(i < bound) {... i++; if(i <= origin) break;}}.
   * This adds a range knowledge to data flow analysis.
   * <p>
   * Does nothing if the statement is not a counting loop.
   *
   * @param statement counting loop candidate.
   * @param startOffset loop start offset (jump target for back-branch)
   */
  private boolean addCountingLoopBound(PsiForStatement statement, ControlFlowOffset startOffset) {
    CountingLoop loop = CountingLoop.from(statement);
    if (loop == null || loop.isDescending()) return false;
    PsiLocalVariable counter = loop.getCounter();
    PsiType counterType = counter.getType();
    Long end = asLong(loop.getBound());
    if (loop.isIncluding() && !(PsiTypes.longType().equals(counterType) && PsiTypes.intType().equals(loop.getBound().getType()))) {
      // could be for(int i=0; i<=Integer.MAX_VALUE; i++) which will overflow: conservatively skip this
      if (end == null || end == Long.MAX_VALUE || end == Integer.MAX_VALUE) return false;
    }
    PsiExpression initializer = loop.getInitializer();
    if (!PsiTypes.intType().equals(counterType) && !PsiTypes.longType().equals(counterType)) return false;
    DfaValue origin = null;
    Object initialValue = ExpressionUtils.computeConstantExpression(initializer);
    if (initialValue instanceof Number) {
      origin = myFactory.fromDfType(DfTypes.constant(initialValue, counterType));
    }
    else if (initializer instanceof PsiReferenceExpression ref) {
      PsiVariable initialVariable = ObjectUtils.tryCast(ref.resolve(), PsiVariable.class);
      if (PsiUtil.isJvmLocalVariable(initialVariable)
          && !VariableAccessUtils.variableIsAssigned(initialVariable, statement.getBody())) {
        origin = PlainDescriptor.createVariableValue(myFactory, initialVariable);
      }
    }
    if (origin == null) return false;
    Long start = asLong(initializer);
    long diff = start == null || end == null ? -1 : end - start;
    DfaVariableValue loopVar = PlainDescriptor.createVariableValue(myFactory, counter);
    if(diff >= 0 && diff <= MAX_UNROLL_SIZE) {
      // Unroll small loops
      Objects.requireNonNull(statement.getUpdate()).accept(this);
      // It's possible that a nested loop may cause widening, dismissing our efforts to track the loop variable
      // In this case, we should at least ensure that it's not lower than the start. 
      addInstruction(new PushInstruction(loopVar, null));
      DfType startBound = PsiTypes.intType().equals(counterType) ? DfTypes.intValue(Math.toIntExact(start)) : DfTypes.longValue(start);
      addInstruction(new EnsureInstruction(null, RelationType.GE, startBound, null));
      addInstruction(new PopInstruction());
      addInstruction(new GotoInstruction(startOffset, false));
      return true;
    }
    else if (start != null) {
      long maxValue = end == null ? Long.MAX_VALUE : loop.isIncluding() ? end + 1 : end;
      if (start >= maxValue && !loop.mayOverflow()) {
        addInstruction(new GotoInstruction(getEndOffset(statement)));
      }
      else {
        LongRangeSet rangeSet = start >= maxValue
                                ? LongRangeSet.all().subtract(LongRangeSet.range(maxValue + 1, start))
                                : LongRangeSet.range(start + 1L, maxValue);
        DfType range = DfTypes.rangeClamped(rangeSet, JvmPsiRangeSetUtil.getLongRangeType(counterType));
        new CFGBuilder(this).assignAndPop(loopVar, range);
      }
    } else {
      // loop like for(int i = start; i != end; i++)
      if (loop.mayOverflow()) return false;
      new CFGBuilder(this).assign(loopVar, DfType.TOP)
                          .push(origin)
                          .compare(RelationType.LE);
      addInstruction(new ConditionalGotoInstruction(getEndOffset(statement), DfTypes.TRUE, null));
    }
    addInstruction(new GotoInstruction(startOffset));
    return true;
  }

  @Override public void visitIfStatement(@NotNull PsiIfStatement statement) {
    startElement(statement);

    PsiExpression condition = statement.getCondition();

    PsiStatement thenStatement = statement.getThenBranch();
    PsiStatement elseStatement = statement.getElseBranch();

    DeferredOffset skipThenOffset = new DeferredOffset();

    if (condition != null) {
      condition.accept(this);
      generateBoxingUnboxingInstructionFor(condition, PsiTypes.booleanType());
      addInstruction(new ConditionalGotoInstruction(skipThenOffset, DfTypes.FALSE, condition));
    }

    if (thenStatement != null) {
      addInstruction(new FinishElementInstruction(null));
      thenStatement.accept(this);
    }

    if (elseStatement != null) {
      DeferredOffset skipElseOffset = new DeferredOffset();
      Instruction instruction = new GotoInstruction(skipElseOffset);
      addInstruction(instruction);
      skipThenOffset.setOffset(getInstructionCount());
      addInstruction(new FinishElementInstruction(null));
      elseStatement.accept(this);
      skipElseOffset.setOffset(getInstructionCount());
    } else {
      skipThenOffset.setOffset(getInstructionCount());
    }

    finishElement(statement);
  }

  // in case of JspTemplateStatement
  @Override public void visitStatement(@NotNull PsiStatement statement) {
    startElement(statement);
    finishElement(statement);
  }

  @Override public void visitLabeledStatement(@NotNull PsiLabeledStatement statement) {
