// 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;

import com.ibm.icu.text.ListFormatter;
import com.intellij.DynamicBundle;
import com.intellij.codeInsight.Nullability;
import com.intellij.codeInsight.NullabilityAnnotationInfo;
import com.intellij.codeInsight.NullableNotNullManager;
import com.intellij.codeInspection.dataFlow.TrackingDfaMemoryState.FactDefinition;
import com.intellij.codeInspection.dataFlow.TrackingDfaMemoryState.FactExtractor;
import com.intellij.codeInspection.dataFlow.TrackingDfaMemoryState.MemoryStateChange;
import com.intellij.codeInspection.dataFlow.TrackingDfaMemoryState.Relation;
import com.intellij.codeInspection.dataFlow.interpreter.RunnerResult;
import com.intellij.codeInspection.dataFlow.interpreter.StandardDataFlowInterpreter;
import com.intellij.codeInspection.dataFlow.java.JavaDfaListener;
import com.intellij.codeInspection.dataFlow.java.anchor.JavaExpressionAnchor;
import com.intellij.codeInspection.dataFlow.java.inst.AssignInstruction;
import com.intellij.codeInspection.dataFlow.java.inst.CheckNotNullInstruction;
import com.intellij.codeInspection.dataFlow.java.inst.InstanceofInstruction;
import com.intellij.codeInspection.dataFlow.jvm.FieldChecker;
import com.intellij.codeInspection.dataFlow.jvm.JvmPsiRangeSetUtil;
import com.intellij.codeInspection.dataFlow.jvm.SpecialField;
import com.intellij.codeInspection.dataFlow.lang.DfaAnchor;
import com.intellij.codeInspection.dataFlow.lang.DfaListener;
import com.intellij.codeInspection.dataFlow.lang.ir.*;
import com.intellij.codeInspection.dataFlow.memory.DfaMemoryState;
import com.intellij.codeInspection.dataFlow.rangeSet.LongRangeBinOp;
import com.intellij.codeInspection.dataFlow.rangeSet.LongRangeSet;
import com.intellij.codeInspection.dataFlow.rangeSet.LongRangeType;
import com.intellij.codeInspection.dataFlow.types.DfConstantType;
import com.intellij.codeInspection.dataFlow.types.DfTypes;
import com.intellij.codeInspection.dataFlow.value.*;
import com.intellij.java.analysis.JavaAnalysisBundle;
import com.intellij.lang.ASTNode;
import com.intellij.openapi.editor.Document;
import com.intellij.openapi.progress.ProgressManager;
import com.intellij.openapi.util.*;
import com.intellij.openapi.util.text.StringUtil;
import com.intellij.psi.*;
import com.intellij.psi.impl.source.tree.ChildRole;
import com.intellij.psi.impl.source.tree.CompositeElement;
import com.intellij.psi.tree.IElementType;
import com.intellij.psi.util.*;
import com.intellij.util.ArrayUtil;
import com.intellij.util.JavaPsiConstructorUtil;
import com.intellij.util.ObjectUtils;
import com.intellij.util.ThreeState;
import com.intellij.util.containers.ContainerUtil;
import com.siyeh.ig.psiutils.BoolUtils;
import com.siyeh.ig.psiutils.EquivalenceChecker;
import com.siyeh.ig.psiutils.ExpressionUtils;
import com.siyeh.ig.psiutils.MethodCallUtils;
import one.util.streamex.IntStreamEx;
import one.util.streamex.StreamEx;
import org.jetbrains.annotations.Contract;
import org.jetbrains.annotations.Nls;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;

import java.util.*;
import java.util.stream.Collector;
import java.util.stream.Collectors;
import java.util.stream.Stream;

import static com.intellij.codeInspection.dataFlow.DfaUtil.hasImplicitImpureSuperCall;

@SuppressWarnings("SuspiciousNameCombination")
public final class TrackingRunner extends StandardDataFlowRunner {
  private MemoryStateChange myHistoryForContext = null;
  private final PsiExpression myExpression;
  private final List<DfaInstructionState> afterStates = new ArrayList<>();
  private final List<TrackingDfaMemoryState> killedStates = new ArrayList<>();

  private TrackingRunner(@NotNull PsiElement context,
                         PsiExpression expression,
                         boolean ignoreAssertions) {
    super(context.getProject(), ThreeState.fromBoolean(ignoreAssertions));
    myExpression = expression;
  }

  @Override
  protected @NotNull StandardDataFlowInterpreter createInterpreter(@NotNull DfaListener listener,
                                                                   @NotNull ControlFlow flow) {
    return new StandardDataFlowInterpreter(flow, listener, true) {
      @Override
      protected void beforeInstruction(Instruction instruction) {
        afterStates.clear();
        killedStates.clear();
      }

      @Override
      protected DfaInstructionState @NotNull [] acceptInstruction(@NotNull DfaInstructionState instructionState) {
        Instruction instruction = instructionState.getInstruction();
        TrackingDfaMemoryState memState = (TrackingDfaMemoryState)instructionState.getMemoryState().createCopy();
        DfaInstructionState[] states = super.acceptInstruction(instructionState);
        for (DfaInstructionState state : states) {
          afterStates.add(state);
          ((TrackingDfaMemoryState)state.getMemoryState()).recordChange(instruction, memState);
        }
        if (states.length == 0) {
          killedStates.add(memState);
        }
        if (instruction instanceof ExpressionPushingInstruction pushing && pushing.getDfaAnchor() instanceof JavaExpressionAnchor anchor &&
            anchor.getExpression() == myExpression) {
          for (DfaInstructionState state : states) {
            MemoryStateChange history = ((TrackingDfaMemoryState)state.getMemoryState()).getHistory();
            myHistoryForContext = myHistoryForContext == null ? history : myHistoryForContext.merge(history);
          }
        }
        return states;
      }

      @Override
      protected void afterInstruction(Instruction instruction) {
        if (afterStates.size() <= 1 && killedStates.isEmpty()) return;
        Map<Instruction, List<TrackingDfaMemoryState>> instructionToState =
          StreamEx.of(afterStates).mapToEntry(s -> s.getInstruction(), s -> (TrackingDfaMemoryState)s.getMemoryState()).grouping();
        if (instructionToState.size() <= 1 && killedStates.isEmpty()) return;
        instructionToState.forEach((target, memStates) -> {
          List<TrackingDfaMemoryState> bridgeChanges =
            StreamEx.of(afterStates).filter(s -> s.getInstruction() != target)
              .map(s -> ((TrackingDfaMemoryState)s.getMemoryState()))
              .append(killedStates)
              .toList();
          for (TrackingDfaMemoryState state : memStates) {
            state.addBridge(instruction, bridgeChanges);
          }
        });
      }
    };
  }

  @Override
  protected @NotNull DfaMemoryState createMemoryState() {
    return new TrackingDfaMemoryState(getFactory());
  }

  public static @Nullable CauseItem findProblemCause(boolean ignoreAssertions,
                                                     PsiExpression expression,
                                                     DfaProblemType type) {
    PsiElement body = DfaUtil.getDataflowContext(expression);
    if (body == null) return null;
    TrackingRunner runner = new TrackingRunner(body, expression, ignoreAssertions);
    if (!runner.analyze(expression, body)) return null;
    return runner.findProblemCause(expression, type);
  }

  private boolean analyze(PsiExpression expression, PsiElement body) {
    List<DfaMemoryState> endOfInitializerStates = new ArrayList<>();
    var interceptor = new JavaDfaListener() {
      @Override
      public void beforeInstanceInitializerEnd(@NotNull DfaMemoryState state) {
        endOfInitializerStates.add(state.createCopy());
      }
    };
    RunnerResult result = analyzeMethodRecursively(body, interceptor);
    if (result != RunnerResult.OK) return false;
    if (body instanceof PsiClass) {
      PsiMethod ctor = PsiTreeUtil.getParentOfType(expression, PsiMethod.class, true, PsiClass.class, PsiLambdaExpression.class);
      if (ctor != null && ctor.isConstructor()) {
        List<DfaMemoryState> initialStates;
        PsiCodeBlock ctorBody = ctor.getBody();
        if (ctorBody != null) {
          PsiMethodCallExpression call = JavaPsiConstructorUtil.findThisOrSuperCallInConstructor(ctor);
          if (JavaPsiConstructorUtil.isChainedConstructorCall(call) ||
              (call == null && hasImplicitImpureSuperCall((PsiClass)body, ctor))) {
            initialStates = Collections.singletonList(createMemoryState());
          }
          else {
            initialStates = ContainerUtil.map(endOfInitializerStates, DfaMemoryState::createCopy);
          }
          return analyzeBlockRecursively(ctorBody, initialStates, interceptor) == RunnerResult.OK;
        }
      }
    }
    return true;
  }

  /*
  TODO: 1. Find causes of other warnings:
            Cause for AIOOBE
            Cause for "modifying an immutable collection"
            Cause for "Collection is always empty" (separate inspection now)
  TODO: 2. Describe causes in more cases:
            Warning caused by complex contracts
            Warning caused by CustomMethodHandler
            Warning caused by polyadic math
            Warning caused by unary minus
            Warning caused by string concatenation
            Warning caused by java.lang.Void nullability
            Warning caused by getClass() equality
            Warning caused by inliners
  TODO: 3. Check how it works with:
            Boxed numbers
   */
  private @Nullable CauseItem findProblemCause(PsiExpression expression, DfaProblemType type) {
    if (myHistoryForContext == null) return null;
    CauseItem cause = null;
    do {
      CauseItem item = new CauseItem(type, expression);
      MemoryStateChange history = myHistoryForContext.getNonMerge();
      if (history.getExpression() == expression) {
        item.addChildren(type.findCauses(this, expression, history));
      }
      if (cause == null) {
        cause = item;
      }
      else {
        cause = cause.merge(item);
        if (cause == null) return null;
      }
    }
    while (myHistoryForContext.advance());
    return cause;
  }

  public abstract static class DfaProblemType {
    @Override
    public abstract @Nls String toString();

    CauseItem[] findCauses(TrackingRunner runner, PsiExpression expression, MemoryStateChange history) {
      return new CauseItem[0];
    }

    @Nullable
    DfaProblemType tryMerge(DfaProblemType other) {
      return this.toString().equals(other.toString()) ? this : null;
    }
  }

  public static class CauseItem {
    private static final @NlsSafe String PLACE_POINTER = "___PLACE___";
    final @NotNull List<CauseItem> myChildren;
    final @NotNull DfaProblemType myProblem;
    final @Nullable SmartPsiFileRange myTarget;

    private CauseItem(@NotNull List<CauseItem> children, @NotNull DfaProblemType problem, @Nullable SmartPsiFileRange target) {
      myChildren = children;
      myProblem = problem;
      myTarget = target;
    }

    CauseItem(@NotNull @Nls String problem, @Nullable PsiElement target) {
      this(new CustomDfaProblemType(problem), target);
    }

    CauseItem(@NotNull DfaProblemType problem, @Nullable PsiElement target) {
      myChildren = new ArrayList<>();
      myProblem = problem;
      if (target != null) {
        PsiFile file = target.getContainingFile();
        myTarget = SmartPointerManager.getInstance(file.getProject()).createSmartPsiFileRangePointer(file, target.getTextRange());
      } else {
        myTarget = null;
      }
    }

    CauseItem(@NotNull @Nls String problem, @NotNull MemoryStateChange change) {
      this(new CustomDfaProblemType(problem), change);
    }

    CauseItem(@NotNull DfaProblemType problem, @NotNull MemoryStateChange change) {
      this(problem, change.getExpression());
    }

    void addChildren(CauseItem... causes) {
      ContainerUtil.addAllNotNull(myChildren, causes);
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      CauseItem item = (CauseItem)o;
      return myChildren.equals(item.myChildren) &&
             getProblemName().equals(item.getProblemName()) &&
             Objects.equals(myTarget, item.myTarget);
    }

    private @Nls String getProblemName() {
      return myProblem.toString();
    }

    @Override
    public int hashCode() {
      return Objects.hash(myChildren, getProblemName(), myTarget);
    }

    public String dump(Document doc) {
      return dump(doc, 0, null);
    }

    private String dump(Document doc, int indent, CauseItem parent) {
      String text = null;
      if (myTarget != null) {
        Segment range = myTarget.getRange();
        if (range != null) {
          text = doc.getText(TextRange.create(range));
          int lineNumber = doc.getLineNumber(range.getStartOffset());
          text += "; line#" + (lineNumber + 1);
        }
      }
      return StringUtil.repeat("  ", indent) + render(doc, parent) + (text == null ? "" : " (" + text + ")") + "\n" +
             StreamEx.of(myChildren).map(child -> child.dump(doc, indent + 1, this)).joining();
    }

    public Stream<CauseItem> children() {
      return StreamEx.of(myChildren);
    }

    public @Nullable PsiFile getFile() {
      return myTarget != null ? myTarget.getContainingFile() : null;
    }

    public Segment getTargetSegment() {
      return myTarget == null ? null : myTarget.getRange();
    }

    public @Nls String render(Document doc, CauseItem parent) {
      String title = null;
      Segment range = getTargetSegment();
      if (range != null) {
        String cause = getProblemName();
        if (cause.contains(PLACE_POINTER)) {
          int offset = range.getStartOffset();
          int number = doc.getLineNumber(offset);
          title = cause.replaceFirst(PLACE_POINTER, JavaAnalysisBundle.message("dfa.find.cause.place.line.number", number + 1));
        }
      }
      if (title == null) {
        title = toString();
      }
      int childIndex = parent == null ? 0 : parent.myChildren.indexOf(this);
      if (childIndex > 0) {
        title = (parent.myProblem instanceof PossibleExecutionDfaProblemType
                 ? JavaAnalysisBundle.message("dfa.find.cause.or.another", title)
                 : JavaAnalysisBundle.message("dfa.find.cause.and.another", title));
      } else {
        title = StringUtil.capitalize(title);
      }
      return title;
    }

    @Override
    public @Nls String toString() {
      return getProblemName().replaceFirst(PLACE_POINTER, JavaAnalysisBundle.message("dfa.find.cause.place.here"));
    }

    public CauseItem merge(CauseItem other) {
      if (this.equals(other)) return this;
      if (Objects.equals(this.myTarget, other.myTarget)) {
        if (myChildren.equals(other.myChildren)) {
          DfaProblemType mergedProblem = myProblem.tryMerge(other.myProblem);
          if (mergedProblem != null) {
            return new CauseItem(myChildren, mergedProblem, myTarget);
          }
        }
        if (getProblemName().equals(other.getProblemName())) {
          if (tryMergeChildren(other.myChildren)) return this;
          if (other.tryMergeChildren(this.myChildren)) return other;
        }
      }
      return null;
    }

    private boolean tryMergeChildren(List<CauseItem> children) {
      if (myChildren.isEmpty()) return false;
      if (myChildren.size() != 1 || !(myChildren.get(0).myProblem instanceof PossibleExecutionDfaProblemType)) {
        if (children.size() == myChildren.size()) {
          List<CauseItem> merged = StreamEx.zip(myChildren, children, CauseItem::merge).toList();
          int nullPos = merged.indexOf(null);
          if (nullPos == -1) {
            myChildren.clear();
            myChildren.addAll(merged);
            return true;
          } else if (merged.lastIndexOf(null) == nullPos) {
            CauseItem merge = new CauseItem(new PossibleExecutionDfaProblemType(), (PsiElement)null);
            merge.addChildren(myChildren.get(nullPos), children.get(nullPos));
            myChildren.clear();
            myChildren.addAll(merged);
            myChildren.set(nullPos, merge);
            return true;
          }
        }
        insertIntoHierarchy(new CauseItem(new PossibleExecutionDfaProblemType(), (PsiElement)null));
      }
      CauseItem mergePoint = myChildren.get(0);
      if (children.isEmpty()) {
        ((PossibleExecutionDfaProblemType)mergePoint.myProblem).myComplete = false;
      }
      List<CauseItem> mergeChildren = mergePoint.myChildren;
      for (CauseItem child : children) {
        if (!mergeChildren.contains(child)) {
          boolean merged = false;
          for (int i = 0; i < mergeChildren.size(); i++) {
            CauseItem mergeChild = mergeChildren.get(i);
            CauseItem result = mergeChild.merge(child);
            if (result != null) {
              mergeChildren.set(i, result);
              merged = true;
              break;
            }
          }
          if (!merged) {
            mergeChildren.add(child);
          }
        }
      }
      return true;
    }

    private void insertIntoHierarchy(CauseItem intermediate) {
      intermediate.myChildren.addAll(myChildren);
      myChildren.clear();
      myChildren.add(intermediate);
    }
  }

  public static class CastDfaProblemType extends DfaProblemType {
    @Override
    public CauseItem[] findCauses(TrackingRunner runner, PsiExpression expression, MemoryStateChange history) {
      if (expression instanceof PsiTypeCastExpression) {
        PsiType expressionType = expression.getType();
        MemoryStateChange operandPush = history.findExpressionPush(((PsiTypeCastExpression)expression).getOperand());
        if (operandPush != null) {
          return new CauseItem[]{findTypeCause(operandPush, expressionType, false)};
        }
      }
      return new CauseItem[0];
    }

    @Override
    public String toString() {
      return JavaAnalysisBundle.message("dfa.find.cause.cast.may.fail");
    }
  }

  public static class NullableDfaProblemType extends DfaProblemType {
    @Override
    public CauseItem[] findCauses(TrackingRunner runner, PsiExpression expression, MemoryStateChange history) {
      FactDefinition<DfaNullability> nullability = history.findFact(history.myTopOfStack, FactExtractor.nullability());
      if (nullability.myFact == DfaNullability.NULLABLE || nullability.myFact == DfaNullability.NULL) {
        return new CauseItem[]{runner.findNullabilityCause(history, nullability.myFact)};
      }
      return new CauseItem[0];
    }

    @Override
    public String toString() {
      return JavaAnalysisBundle.message("dfa.find.cause.may.be.null");
    }
  }

  public static class FailingCallDfaProblemType extends DfaProblemType {
    @Override
    CauseItem[] findCauses(TrackingRunner runner, PsiExpression expression, MemoryStateChange history) {
      if (expression instanceof PsiCallExpression) {
        return new CauseItem[]{runner.fromCallContract(history, (PsiCallExpression)expression, ContractReturnValue.fail())};
      }
      return super.findCauses(runner, expression, history);
    }

    @Override
    public String toString() {
      return JavaAnalysisBundle.message("dfa.find.cause.call.always.fails");
    }
  }


  static class PossibleExecutionDfaProblemType extends DfaProblemType {
    boolean myComplete = true;

    @Override
    public String toString() {
      return myComplete ?
             JavaAnalysisBundle.message("dfa.find.cause.one.of.the.following.happens") :
             JavaAnalysisBundle.message("dfa.find.cause.an.execution.might.exist.where");
    }
  }

  public static class RangeDfaProblemType extends DfaProblemType {
    final @NotNull @Nls String myTemplate;
    final @NotNull LongRangeSet myRangeSet;
    final @Nullable PsiPrimitiveType myType;

    public RangeDfaProblemType(@NotNull LongRangeSet set, @Nullable PsiPrimitiveType type) {
      this(JavaAnalysisBundle.message("dfa.find.cause.numeric.range.generic.template"), set, type);
    }

    RangeDfaProblemType(@NotNull @Nls String template, @NotNull LongRangeSet set, @Nullable PsiPrimitiveType type) {
      myTemplate = template;
      myRangeSet = set;
      myType = type;
    }

    @Override
    CauseItem[] findCauses(TrackingRunner runner, PsiExpression expression, MemoryStateChange history) {
      CauseItem cause = findRangeCause(history, history.myTopOfStack, myRangeSet, myTemplate);
      return cause == null ? new CauseItem[0] : new CauseItem[]{cause};
    }

    @Nullable
    @Override
    DfaProblemType tryMerge(DfaProblemType other) {
      if (other instanceof RangeDfaProblemType rangeProblem &&
          myTemplate.equals(rangeProblem.myTemplate) &&
          Objects.equals(myType, rangeProblem.myType)) {
        return new RangeDfaProblemType(myTemplate, myRangeSet.join(rangeProblem.myRangeSet), myType);
      }
      return super.tryMerge(other);
    }

    @Override
    public String toString() {
      return String.format(myTemplate, JvmPsiRangeSetUtil.getPresentationText(myRangeSet, myType));
    }
  }


  public static class ValueDfaProblemType extends DfaProblemType {
    final Object myValue;

    public ValueDfaProblemType(Object value) {
      myValue = value;
    }

    @Override
    public CauseItem[] findCauses(TrackingRunner runner, PsiExpression expression, MemoryStateChange history) {
      return runner.findConstantValueCause(expression, history, myValue);
    }

    @Override
    public String toString() {
      return JavaAnalysisBundle.message("dfa.find.cause.value.is.always.the.same", myValue);
    }
  }

  public static class ZeroSizeDfaProblemType extends DfaProblemType {
    final SpecialField myField;

    public ZeroSizeDfaProblemType(@NotNull SpecialField field) {
      myField = field;
    }

    @Override
    public CauseItem[] findCauses(TrackingRunner runner, PsiExpression expression, MemoryStateChange history) {
      DfaValue topOfStack = history.myTopOfStack;
      DfaValue value = myField.createValue(runner.getFactory(), topOfStack);
      MemoryStateChange change = MemoryStateChange.create(history, new PushInstruction(value, null), Map.of(), value);
      return runner.findConstantValueCause(expression, change, 0);
    }

    @Override
    public String toString() {
      return JavaAnalysisBundle.message("dfa.find.cause.size.is.always.zero");
    }
  }

  static class CustomDfaProblemType extends DfaProblemType {
    private final @Nls String myMessage;

    CustomDfaProblemType(@Nls String message) {
      myMessage = message;
    }

    @Override
    public String toString() {
      return myMessage;
    }
  }

  private CauseItem @NotNull [] findConstantValueCause(@Nullable PsiExpression expression, MemoryStateChange history, Object expectedValue) {
    if (expression instanceof PsiLiteralExpression) return new CauseItem[0];
    Object constantExpressionValue = ExpressionUtils.computeConstantExpression(expression);
    DfaValue value = history.myTopOfStack;
    if (constantExpressionValue != null && constantExpressionValue.equals(expectedValue)) {
      return new CauseItem[]{new CauseItem(JavaAnalysisBundle.message("dfa.find.cause.compile.time.constant", value), expression)};
    }
    Boolean boolConst = value.getDfType().getConstantOfType(Boolean.class);
    if (boolConst != null && expression != null && boolConst.equals(expectedValue)) {
      return findBooleanResultCauses(expression, history, boolConst);
    }
    if (value instanceof DfaVariableValue) {
      MemoryStateChange change = history.findRelation(
        (DfaVariableValue)value, rel -> rel.myRelationType == RelationType.EQ &&
                                        rel.myCounterpart.getDfType().isConst(expectedValue), false);
      if (change != null) {
        PsiExpression varSourceExpression = change.getExpression();
        Instruction instruction = change.myInstruction;
        if (instruction instanceof AssignInstruction && change.myTopOfStack == value) {
          PsiExpression rValue = ((AssignInstruction)instruction).getRExpression();
          CauseItem item = createAssignmentCause((AssignInstruction)instruction, value);
          MemoryStateChange push = change.findSubExpressionPush(rValue);
          if (push != null) {
            item.addChildren(findConstantValueCause(rValue, push, expectedValue));
          }
          return new CauseItem[]{item};
        }
        else if (varSourceExpression != null) {
          return new CauseItem[]{new CauseItem(
            JavaAnalysisBundle.message("dfa.find.cause.equality.established.from.condition", value + " == " + expectedValue),
            varSourceExpression)};
        }
      }
    }
    return new CauseItem[0];
  }

  @Contract("_, _ -> new")
  private static @NotNull CauseItem createAssignmentCause(AssignInstruction instruction, DfaValue target) {
    PsiExpression rExpression = instruction.getRExpression();
    PsiElement anchor = null;
    String targetName = target.toString();
    if (rExpression != null) {
      PsiElement parent = PsiUtil.skipParenthesizedExprUp(rExpression.getParent());
      if (parent instanceof PsiAssignmentExpression) {
        anchor = ((PsiAssignmentExpression)parent).getOperationSign();
        targetName = ((PsiAssignmentExpression)parent).getLExpression().getText();
      }
      else if (parent instanceof PsiVariable) {
        ASTNode node = parent.getNode();
        if (node instanceof CompositeElement) {
          anchor = ((CompositeElement)node).findChildByRoleAsPsiElement(ChildRole.INITIALIZER_EQ);
        }
        targetName = ((PsiVariable)parent).getName();
      }
      if (anchor == null) {
        anchor = rExpression;
      }
    }
    PsiExpression stripped = PsiUtil.skipParenthesizedExprDown(rExpression);
    String message;
    if (stripped instanceof PsiLiteralExpression) {
      message = JavaAnalysisBundle
        .message("dfa.find.cause.was.assigned.to", targetName, StringUtil.shortenTextWithEllipsis(stripped.getText(), 40, 5));
    }
    else {
      message = JavaAnalysisBundle.message("dfa.find.cause.was.assigned", targetName);
    }
    return new CauseItem(message, anchor);
  }

  private CauseItem[] findBooleanResultCauses(@NotNull PsiExpression expression,
                                              @NotNull MemoryStateChange history,
                                              boolean value) {
    if (BoolUtils.isNegation(expression)) {
      PsiExpression negated = BoolUtils.getNegated(expression);
      if (negated != null) {
        MemoryStateChange negatedPush = history.findExpressionPush(negated);
        if (negatedPush != null) {
          CauseItem cause = new CauseItem(
            JavaAnalysisBundle.message("dfa.find.cause.value.x.is.always.the.same", negated.getText(), !value), negated);
          cause.addChildren(findConstantValueCause(negated, negatedPush, !value));
          return new CauseItem[]{cause};
        }
      }
    }
    if (expression instanceof PsiPolyadicExpression) {
      IElementType tokenType = ((PsiPolyadicExpression)expression).getOperationTokenType();
      boolean and = tokenType.equals(JavaTokenType.ANDAND);
      if (and || tokenType.equals(JavaTokenType.OROR)) {
        if (value != and) {
          MemoryStateChange push = history;
          if (history.myInstruction instanceof ResultOfInstruction) {
            MemoryStateChange previous = history.getPrevious();
            if (previous != null) {
              previous = previous.getNonMerge();
            }
            if (previous != null && previous.myInstruction instanceof GotoInstruction) {
              previous = previous.getPrevious();
            }
            if (previous != null) {
              push = previous;
            }
          }
          if (push.myInstruction instanceof PushValueInstruction pushValueInstruction && pushValueInstruction.getValue().isConst(value) &&
              pushValueInstruction.getDfaAnchor() instanceof JavaExpressionAnchor anchor &&
              anchor.getExpression() == expression) {
            push = push.getPrevious();
          }
          if (push != null) {
            push = push.getNonMerge();
          }
          if (push != null && push.myInstruction instanceof ConditionalGotoInstruction) {
            push = push.getPrevious();
          }
          if (push != null &&
              push.myInstruction instanceof ExpressionPushingInstruction instruction &&
              instruction.getDfaAnchor() instanceof JavaExpressionAnchor anchor) {
            PsiExpression operand = anchor.getExpression();
            if (expression.equals(PsiUtil.skipParenthesizedExprUp(operand.getParent()))) {
              int i =
                IntStreamEx.ofIndices(((PsiPolyadicExpression)expression).getOperands(), e -> PsiTreeUtil.isAncestor(e, operand, false))
                  .findFirst().orElse(-1);
              if (i >= 0) {
                CauseItem cause = new CauseItem(
                  JavaAnalysisBundle.message("dfa.find.cause.operand.of.boolean.expression.is.the.same", i + 1, and ? 0 : 1, value),
                  operand);
                cause.addChildren(findConstantValueCause(operand, push, value));
                return new CauseItem[]{cause};
              }
            }
          }
          return new CauseItem[0];
        }
        PsiExpression[] operands = ((PsiPolyadicExpression)expression).getOperands();
        List<CauseItem> operandCauses = new ArrayList<>();
        for (int i = 0; i < operands.length; i++) {
          PsiExpression operand = operands[i];
          operand = PsiUtil.skipParenthesizedExprDown(operand);
          MemoryStateChange push = history.findExpressionPush(operand);
          if (push != null &&
              ((push.myInstruction instanceof ConditionalGotoInstruction gotoInstruction &&
                gotoInstruction.isTarget(DfTypes.booleanValue(value), history.myInstruction)) ||
               push.myTopOfStack.getDfType().isConst(value))) {
            int andVal = and ? 1 : 0;
            CauseItem cause = new CauseItem(
              JavaAnalysisBundle.message("dfa.find.cause.operand.of.boolean.expression.is.the.same", i + 1, andVal == 1 ? 0 : 1, value),
              operand);
            cause.addChildren(findBooleanResultCauses(operand, push, value));
            operandCauses.add(cause);
          }
        }
        if (operandCauses.size() == operands.length) {
          return operandCauses.toArray(new CauseItem[0]);
        }
      }
    }
    if (expression instanceof PsiBinaryExpression binOp) {
      RelationType relationType =
        DfaPsiUtil.getRelationByToken(binOp.getOperationTokenType());
      if (relationType != null) {
        if (!value) {
          relationType = relationType.getNegated();
        }
        PsiExpression leftOperand = PsiUtil.skipParenthesizedExprDown(binOp.getLOperand());
        PsiExpression rightOperand = PsiUtil.skipParenthesizedExprDown(binOp.getROperand());
        MemoryStateChange leftChange = history.findExpressionPush(leftOperand);
        MemoryStateChange rightChange = history.findExpressionPush(rightOperand);
        if (leftChange != null && rightChange != null) {
          DfaValue leftValue = leftChange.myTopOfStack;
          DfaValue rightValue = rightChange.myTopOfStack;
          CauseItem[] causes = findRelationCause(relationType, leftChange, rightChange);
          if (causes.length > 0) {
            return causes;
          }
          if (leftValue == rightValue &&
              (leftValue instanceof DfaVariableValue || leftValue.getDfType() instanceof DfConstantType)) {
            List<CauseItem> constCauses = new ArrayList<>();
            CauseItem leftCause = constantInitializerCause(leftValue, leftChange.getExpression());
            CauseItem rightCause = constantInitializerCause(rightValue, rightChange.getExpression());
            ContainerUtil.addAllNotNull(constCauses, leftCause, rightCause);
            if (constCauses.isEmpty()) {
              return new CauseItem[]{
                new CauseItem(JavaAnalysisBundle.message("dfa.find.cause.comparison.arguments.are.the.same"), binOp.getOperationSign())};
            }
            return constCauses.toArray(new CauseItem[0]);
          }
          if (leftValue != rightValue && relationType.isInequality() &&
              leftValue.getDfType() instanceof DfConstantType && rightValue.getDfType() instanceof DfConstantType) {
            CauseItem causeItem = new CauseItem(JavaAnalysisBundle.message("dfa.find.cause.comparison.arguments.are.different.constants"),
                                                binOp.getOperationSign());
            causeItem.addChildren(constantInitializerCause(leftValue, leftChange.getExpression()),
