// Copyright 2000-2025 JetBrains s.r.o. and contributors. Use of this source code is governed by the Apache 2.0 license.
package com.intellij.refactoring.util.duplicates;

import com.intellij.codeInsight.AnnotationUtil;
import com.intellij.codeInsight.PsiEquivalenceUtil;
import com.intellij.lang.ASTNode;
import com.intellij.openapi.diagnostic.Logger;
import com.intellij.openapi.progress.ProgressManager;
import com.intellij.openapi.util.Comparing;
import com.intellij.openapi.util.Key;
import com.intellij.openapi.util.TextRange;
import com.intellij.psi.*;
import com.intellij.psi.controlFlow.*;
import com.intellij.psi.impl.source.PsiImmediateClassType;
import com.intellij.psi.tree.IElementType;
import com.intellij.psi.util.*;
import com.intellij.refactoring.extractMethod.InputVariables;
import com.intellij.refactoring.util.RefactoringChangeUtil;
import com.intellij.util.ArrayUtil;
import com.intellij.util.IncorrectOperationException;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import it.unimi.dsi.fastutil.ints.IntList;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;
import org.jetbrains.annotations.Unmodifiable;

import java.util.*;

public final class DuplicatesFinder {
  private static final Logger LOG = Logger.getInstance(DuplicatesFinder.class);
  public static final Key<Parameter> PARAMETER = Key.create("PARAMETER");
  private final PsiElement @NotNull [] myPattern;
  private final InputVariables myParameters;
  private final List<? extends PsiVariable> myOutputParameters;
  private final List<PsiElement> myPatternAsList;
  private boolean myMultipleExitPoints;
  private final @Nullable ReturnValue myReturnValue;
  private final @Unmodifiable @Nullable Set<? extends TextRange> myTextRanges;
  private final MatchType myMatchType;
  private final Set<? extends PsiVariable> myEffectivelyLocal;
  private ComplexityHolder myPatternComplexityHolder;
  private ComplexityHolder myCandidateComplexityHolder;

  public DuplicatesFinder(PsiElement @NotNull [] pattern,
                          InputVariables parameters,
                          @Nullable ReturnValue returnValue,
                          @NotNull List<? extends PsiVariable> outputParameters,
                          @NotNull MatchType matchType,
                          @Nullable Set<? extends PsiVariable> effectivelyLocal,
                          @Nullable @Unmodifiable Set<? extends TextRange> textRanges) {
    myReturnValue = returnValue;
    LOG.assertTrue(pattern.length > 0);
    myPattern = pattern;
    myPatternAsList = Arrays.asList(myPattern);
    myOutputParameters = outputParameters;
    myMatchType = matchType;
    myEffectivelyLocal = effectivelyLocal != null ? effectivelyLocal : Collections.emptySet();
    myTextRanges = textRanges;

    final PsiElement codeFragment = ControlFlowUtil.findCodeFragment(pattern[0]);
    try {
      final ControlFlow controlFlow = ControlFlowFactory.getInstance(codeFragment.getProject()).getControlFlow(codeFragment, new LocalsControlFlowPolicy(codeFragment), false);

      int startOffset;
      int i = 0;
      do {
        startOffset = controlFlow.getStartOffset(pattern[i++]);
      }
      while(startOffset < 0 && i < pattern.length);

      int endOffset;
      int j = pattern.length - 1;
      do {
        endOffset = controlFlow.getEndOffset(pattern[j--]);
      }
      while (endOffset < 0 && j >= 0);

      IntList exitPoints = new IntArrayList();
      final Collection<PsiStatement> exitStatements = ControlFlowUtil
          .findExitPointsAndStatements(controlFlow, startOffset, endOffset, exitPoints, ControlFlowUtil.DEFAULT_EXIT_STATEMENTS_CLASSES);
      myMultipleExitPoints = exitPoints.size() > 1;

      if (myMultipleExitPoints) {
        parameters = parameters.copy();
        parameters.removeParametersUsedInExitsOnly(codeFragment, exitStatements, controlFlow, startOffset, endOffset);
      }
    }
    catch (AnalysisCanceledException ignored) {
    }
    myParameters = parameters;
  }

  public DuplicatesFinder(PsiElement @NotNull [] pattern,
                          InputVariables parameters,
                          @Nullable ReturnValue returnValue,
                          @NotNull List<? extends PsiVariable> outputParameters) {
    this(pattern, parameters, returnValue, outputParameters, MatchType.EXACT, null, null);
  }

  public DuplicatesFinder(final PsiElement[] pattern,
                          final InputVariables psiParameters,
                          final List<? extends PsiVariable> psiVariables) {
    this(pattern, psiParameters, null, psiVariables);
  }


  public InputVariables getParameters() {
    return myParameters;
  }

  public PsiElement @NotNull [] getPattern() {
    return myPattern;
  }

  public @Nullable ReturnValue getReturnValue() {
    return myReturnValue;
  }

  public List<Match> findDuplicates(PsiElement scope) {
    annotatePattern();
    final ArrayList<Match> result = new ArrayList<>();
    findPatternOccurrences(result, scope);
    deannotatePattern();
    return result;
  }

  public @Nullable Match isDuplicate(@NotNull PsiElement element, boolean ignoreParameterTypesAndPostVariableUsages) {
    annotatePattern();
    Match match = isDuplicateFragment(element, ignoreParameterTypesAndPostVariableUsages);
    deannotatePattern();
    return match;
  }

  private void annotatePattern() {
    JavaRecursiveElementWalkingVisitor visitor = new JavaRecursiveElementWalkingVisitor() {
      @Override
      public void visitReferenceElement(@NotNull PsiJavaCodeReferenceElement reference) {
        final PsiElement element = reference.resolve();
        if (element instanceof PsiVariable variable) {
          PsiType type = variable.getType();
          myParameters.annotateWithParameter(reference);
          if (myOutputParameters.contains(element)) {
            reference.putUserData(PARAMETER, new Parameter(variable, type));
          }
        }
        PsiElement qualifier = reference.getQualifier();
        if (qualifier != null) {
          qualifier.accept(this);
        }
      }
    };
    for (final PsiElement patternComponent : myPattern) {
      patternComponent.accept(visitor);
    }
  }

  private void deannotatePattern() {
    JavaRecursiveElementWalkingVisitor visitor = new JavaRecursiveElementWalkingVisitor() {
      @Override
      public void visitExpression(@NotNull PsiExpression expression) {
        super.visitExpression(expression);
        if (expression.getUserData(PARAMETER) != null) {
          expression.putUserData(PARAMETER, null);
        }
      }

      @Override
      public void visitReferenceElement(@NotNull PsiJavaCodeReferenceElement reference) {
        if (reference.getUserData(PARAMETER) != null) {
          reference.putUserData(PARAMETER, null);
        }
      }
    };
    for (final PsiElement patternComponent : myPattern) {
      patternComponent.accept(visitor);
    }
  }

  private void findPatternOccurrences(List<? super Match> array, PsiElement scope) {
    PsiElement[] children = scope.getChildren();
    for (PsiElement child : children) {
      ProgressManager.checkCanceled();
      final Match match = isDuplicateFragment(child, false);
      if (match != null && (myTextRanges == null || myTextRanges.contains(match.getTextRange()))) {
        array.add(match);
        continue;
      }
      findPatternOccurrences(array, child);
    }
  }


  private @Nullable Match isDuplicateFragment(@NotNull PsiElement candidate, boolean ignoreParameterTypesAndPostVariableUsages) {
    if (isSelf(candidate)) return null;
    PsiElement sibling = candidate;
    ArrayList<PsiElement> candidates = new ArrayList<>();
    for (final PsiElement element : myPattern) {
      if (sibling == null) return null;
      if (!canBeEquivalent(element, sibling) || isSelf(sibling)) return null;
      candidates.add(sibling);
      sibling = PsiTreeUtil.skipSiblingsForward(sibling, PsiWhiteSpace.class, PsiComment.class, PsiEmptyStatement.class);
    }
    LOG.assertTrue(myPattern.length == candidates.size());
    if (myPattern.length == 1 && myPattern[0] instanceof PsiExpression) {
      if (candidates.get(0) instanceof PsiExpression candidateExpression) {
        if (PsiUtil.isAccessedForWriting(candidateExpression)) return null;
        final PsiType patternType = ((PsiExpression)myPattern[0]).getType();
        final PsiType candidateType = candidateExpression.getType();
        PsiSubstitutor substitutor = PsiSubstitutor.EMPTY;
        final PsiMethod method = PsiTreeUtil.getContextOfType(myPattern[0], PsiMethod.class);
        if (method != null) {
          final PsiResolveHelper resolveHelper = JavaPsiFacade.getInstance(candidate.getProject()).getResolveHelper();
          substitutor = resolveHelper.inferTypeArguments(method.getTypeParameters(), new PsiType[]{patternType},
                                                         new PsiType[]{candidateType}, PsiUtil.getLanguageLevel(method));
        }
        if (!canTypesBeEquivalent(substitutor.substitute(patternType), candidateType)) return null;
      }
      else {
        return null;
      }

    }
    final Match match = new Match(candidates.getFirst(), candidates.getLast(), ignoreParameterTypesAndPostVariableUsages);
    for (int i = 0; i < myPattern.length; i++) {
      if (!matchPattern(myPattern[i], candidates.get(i), candidates, match)) return null;
    }

    if (!ignoreParameterTypesAndPostVariableUsages && checkPostVariableUsages(candidates, match)) return null;

    return match;
  }

  private boolean isSelf(@NotNull PsiElement candidate) {
    for (PsiElement pattern : myPattern) {
      ProgressManager.checkCanceled();
      if (PsiTreeUtil.isAncestor(pattern, candidate, false)) {
        return true;
      }
    }
    return false;
  }

  private boolean checkPostVariableUsages(final ArrayList<? extends PsiElement> candidates, final Match match) {
    final PsiElement codeFragment = ControlFlowUtil.findCodeFragment(candidates.get(0));
    try {
      final ControlFlow controlFlow = ControlFlowFactory.getInstance(codeFragment.getProject()).getControlFlow(codeFragment, new LocalsControlFlowPolicy(codeFragment), false);

      int startOffset;
      int i = 0;
      do {
        startOffset = controlFlow.getStartOffset(candidates.get(i++));
      } while(startOffset < 0 && i < candidates.size());

      int endOffset;
      int j = candidates.size() - 1;
      do {
        endOffset = controlFlow.getEndOffset(candidates.get(j--));
      } while(endOffset < 0 && j >= 0);

      final IntList exitPoints = new IntArrayList();
      ControlFlowUtil.findExitPointsAndStatements(controlFlow, startOffset, endOffset, exitPoints, ControlFlowUtil.DEFAULT_EXIT_STATEMENTS_CLASSES);
      final PsiVariable[] outVariables = ControlFlowUtil.getOutputVariables(controlFlow, startOffset, endOffset, exitPoints.toIntArray());

      if (outVariables.length > 0) {
        if (outVariables.length == 1) {
          ReturnValue returnValue = match.getReturnValue();
          if (returnValue == null) {
            returnValue = myReturnValue;
          }
          if (returnValue instanceof GotoReturnValue ||
              returnValue instanceof ConditionalReturnStatementValue &&
              ((ConditionalReturnStatementValue)returnValue).isEmptyOrConstantExpression()) {
            return false;
          }
          if (returnValue instanceof VariableReturnValue) {
            final ReturnValue value = match.getOutputVariableValue(((VariableReturnValue)returnValue).getVariable());
            if (value != null) {
              if (value.isEquivalent(new VariableReturnValue(outVariables[0]))) return false;
              if (value instanceof ExpressionReturnValue) {
                final PsiExpression expression = ((ExpressionReturnValue)value).getExpression();
                if (expression instanceof PsiReferenceExpression) {
                  final PsiElement variable = ((PsiReferenceExpression)expression).resolve();
                  return variable == null || !PsiEquivalenceUtil.areElementsEquivalent(variable, outVariables[0]);
                }
              }
            }
          }
        }
        return true;
      }
    }
    catch (AnalysisCanceledException ignored) {
    }
    return false;
  }

  private static boolean canTypesBeEquivalent(PsiType type1, PsiType type2) {
    if (type1 == null || type2 == null) return false;
    if (!type2.isAssignableFrom(type1)) {
      if (type1 instanceof PsiImmediateClassType && type2 instanceof PsiImmediateClassType) {
        final PsiClass psiClass1 = ((PsiImmediateClassType)type1).resolve();
        final PsiClass psiClass2 = ((PsiImmediateClassType)type2).resolve();
        if (!(psiClass1 instanceof PsiAnonymousClass anonymousClass1) ||
            !(psiClass2 instanceof PsiAnonymousClass anonymousClass2) ||
            !anonymousClass1.getBaseClassType().equals(anonymousClass2.getBaseClassType())) {
          return false;
        }
      }
      else {
        return false;
      }
    }
    return true;
  }

  private static boolean canBeEquivalent(final PsiElement pattern, PsiElement candidate) {
    if (pattern instanceof PsiReturnStatement && candidate instanceof PsiExpressionStatement) return true;
    if (pattern instanceof PsiReturnStatement && candidate instanceof PsiDeclarationStatement) return true;
    if (pattern instanceof PsiThisExpression && candidate instanceof PsiReferenceExpression) return true;
    final ASTNode node1 = pattern.getNode();
    final ASTNode node2 = candidate.getNode();
    if (node1 == null || node2 == null) return false;
    if (node1.getElementType() != node2.getElementType()) return false;
    if (pattern instanceof PsiUnaryExpression) {
      return ((PsiUnaryExpression)pattern).getOperationTokenType() == ((PsiUnaryExpression)candidate).getOperationTokenType();
    }
    if (pattern instanceof PsiPolyadicExpression) {
      return ((PsiPolyadicExpression)pattern).getOperationTokenType() == ((PsiPolyadicExpression)candidate).getOperationTokenType();
    }
    return true;
  }

  private boolean matchPattern(@Nullable PsiElement pattern,
                               @Nullable PsiElement candidate,
                               @NotNull List<PsiElement> candidates,
                               @NotNull Match match) {
    if (pattern == null || candidate == null) return pattern == candidate;
    final Boolean parameterMatches = matchParameter(pattern, candidate, match);
    if (parameterMatches != null) {
      return parameterMatches;
    }

    if (!canBeEquivalent(pattern, candidate)) {
      return false; // Q : is it correct to check implementation classes?
    }

    if (pattern instanceof PsiExpressionList && candidate instanceof PsiExpressionList) {
      Boolean matches = matchVarargs((PsiExpressionList)pattern, (PsiExpressionList)candidate, candidates, match);
      if (matches != null) {
        return matches;
      }
    }

    if (isParameterModification(pattern, candidate)) {
      return false;
    }

    if (pattern instanceof PsiJavaCodeReferenceElement && candidate instanceof PsiJavaCodeReferenceElement) {
      Boolean matches =
        matchReferenceElement((PsiJavaCodeReferenceElement)pattern, (PsiJavaCodeReferenceElement)candidate, candidates, match);
      if (matches != null) {
        return matches;
      }
    }

    if (pattern instanceof PsiTypeCastExpression && candidate instanceof PsiTypeCastExpression) {
      if (!isEquivalentTypeCast((PsiTypeCastExpression)pattern, (PsiTypeCastExpression)candidate)) {
        return false;
      }
    }
    else if (pattern instanceof PsiNewExpression && candidate instanceof PsiNewExpression) {
      if (!isEquivalentNewExpression((PsiNewExpression)pattern, (PsiNewExpression)candidate)) {
        return false;
      }
    }
    else if (pattern instanceof PsiClassObjectAccessExpression && candidate instanceof PsiClassObjectAccessExpression) {
      return matchObjectAccess((PsiClassObjectAccessExpression)pattern, (PsiClassObjectAccessExpression)candidate);
    }
    else if (pattern instanceof PsiInstanceOfExpression && candidate instanceof PsiInstanceOfExpression) {
      if (!isEquivalentInstanceOf((PsiInstanceOfExpression)pattern, (PsiInstanceOfExpression)candidate)) {
        return false;
      }
    } else if (pattern instanceof PsiReturnStatement) {
      return matchReturnStatement((PsiReturnStatement)pattern, candidate, candidates, match);
    } else if (pattern instanceof PsiContinueStatement) {
      match.registerReturnValue(new ContinueReturnValue());
    } else if (pattern instanceof PsiBreakStatement) {
      match.registerReturnValue(new BreakReturnValue());
    }
    else if (pattern instanceof PsiMethodCallExpression && candidate instanceof PsiMethodCallExpression) {
      if (!isEquivalentMethodCall((PsiMethodCallExpression)pattern, (PsiMethodCallExpression)candidate)) {
        return false;
      }
    }
    else if (pattern instanceof PsiReferenceExpression && candidate instanceof PsiReferenceExpression) {
      final Boolean matches = matchReferenceExpression((PsiReferenceExpression)pattern, (PsiReferenceExpression)candidate, match);
      if (matches != null) {
        return matches;
      }
    } else if (pattern instanceof PsiThisExpression) {
      return matchThisExpression((PsiThisExpression)pattern, candidate, match);
    }
    else if (pattern instanceof PsiSuperExpression && candidate instanceof PsiSuperExpression) {
      return matchSuperExpression((PsiSuperExpression)pattern, (PsiSuperExpression)candidate);
    }
    else if (pattern instanceof PsiModifierList && candidate instanceof PsiModifierList) {
      return matchModifierList((PsiModifierList)pattern, (PsiModifierList)candidate);
    }

    PsiElement[] children1 = getFilteredChildren(pattern);
    PsiElement[] children2 = getFilteredChildren(candidate);
    if (!matchChildren(children1, children2, candidates, match)) {
      return false;
    }

    if (children1.length == 0) {
      return matchLeaf(pattern, candidate, match);
    }

    return true;
  }

  private @Nullable Boolean matchParameter(@NotNull PsiElement pattern, @NotNull PsiElement candidate, @NotNull Match match) {
    final Parameter parameter = pattern.getUserData(PARAMETER);
    if (parameter == null || myMatchType == MatchType.EXACT && parameter.isFolded()) {
      return null;
    }
    if (!match.putParameter(parameter, candidate)) {
      return false;
    }
    if (parameter.isFolded() && pattern instanceof PsiExpression && candidate instanceof PsiExpression) {
      match.putFoldedExpressionMapping(parameter, (PsiExpression)pattern, (PsiExpression)candidate);
    }
    return true;
  }

  private @Nullable Boolean matchVarargs(@NotNull PsiExpressionList pattern,
                                         @NotNull PsiExpressionList candidate,
                                         @NotNull List<PsiElement> candidates,
                                         @NotNull Match match) {
    final PsiExpression[] expressions = pattern.getExpressions();
    final PsiExpression[] childExpressions = candidate.getExpressions();
    if (expressions.length > 0 && expressions[expressions.length - 1] instanceof PsiReferenceExpression) {
      final PsiElement resolved = ((PsiReferenceExpression)expressions[expressions.length - 1]).resolve();
      if (resolved instanceof PsiParameter && ((PsiParameter)resolved).getType() instanceof PsiEllipsisType) {
        for (int i = 0; i < expressions.length - 1; i++) {
          final Parameter parameter = expressions[i].getUserData(PARAMETER);
          if (parameter == null) {
            if (!matchPattern(expressions[i], childExpressions[i], candidates, match)) {
              return false;
            }
          }
          else if (!match.putParameter(parameter, childExpressions[i])) return false;
        }
        final Parameter param = expressions[expressions.length - 1].getUserData(PARAMETER);
        if (param == null) return false;
        for (int i = expressions.length - 1; i < childExpressions.length; i++) {
          if (!match.putParameter(param, childExpressions[i])) return false;
        }
        return true;
      }
    }
    return null;
  }

  private static boolean isParameterModification(@NotNull PsiElement pattern, @NotNull PsiElement candidate) {
    if (pattern instanceof PsiAssignmentExpression) {
      final PsiExpression lExpression = PsiUtil.skipParenthesizedExprDown(((PsiAssignmentExpression)pattern).getLExpression());
      if (lExpression instanceof PsiReferenceExpression &&
          lExpression.getType() instanceof PsiPrimitiveType &&
          ((PsiReferenceExpression)lExpression).resolve() instanceof PsiParameter) {
        return true;
      }
    }
    else if (pattern instanceof PsiUnaryExpression && candidate instanceof PsiUnaryExpression) {
      if (checkParameterModification(((PsiUnaryExpression)pattern).getOperand(), ((PsiUnaryExpression)pattern).getOperationTokenType(),
                                     ((PsiUnaryExpression)candidate).getOperand())) {
        return true;
      }
    }
    return false;
  }

  private @Nullable Boolean matchReferenceElement(@NotNull PsiJavaCodeReferenceElement pattern,
                                                  @NotNull PsiJavaCodeReferenceElement candidate,
                                                  @NotNull List<? extends PsiElement> candidates,
                                                  @NotNull Match match) {
    final PsiElement resolveResult1 = pattern.resolve();
    final PsiElement resolveResult2 = candidate.resolve();
    if (resolveResult1 instanceof PsiClass && resolveResult2 instanceof PsiClass) return true;
    if (isUnder(resolveResult1, myPatternAsList) && isUnder(resolveResult2, candidates)) {
      traverseParameter(resolveResult1, resolveResult2, match);
      return match.putDeclarationCorrespondence(resolveResult1, resolveResult2);
    }
    if (resolveResult1 instanceof PsiVariable && myEffectivelyLocal.contains((PsiVariable)resolveResult1)) {
      return PsiUtil.isJvmLocalVariable(resolveResult2) &&
             match.putDeclarationCorrespondence(resolveResult1, resolveResult2);
    }
    PsiElement qualifier2 = candidate.getQualifier();
    while (qualifier2 instanceof PsiParenthesizedExpression) {
      qualifier2 = ((PsiParenthesizedExpression)qualifier2).getExpression();
    }
    if (!equivalentResolve(resolveResult1, resolveResult2, qualifier2)) {
      return matchExtractableVariable(pattern, candidate, match);
    }
    PsiElement qualifier1 = pattern.getQualifier();
    while (qualifier1 instanceof PsiParenthesizedExpression) {
      qualifier1 = ((PsiParenthesizedExpression)qualifier1).getExpression();
    }
    if (qualifier1 instanceof PsiReferenceExpression && qualifier2 instanceof PsiReferenceExpression &&
        !match.areCorrespond(((PsiReferenceExpression)qualifier1).resolve(), ((PsiReferenceExpression)qualifier2).resolve())) {
      return false;
    }

    if (qualifier1 == null && qualifier2 == null) {
      final PsiClass patternClass = RefactoringChangeUtil.getThisClass(pattern);
      final PsiClass candidateClass = RefactoringChangeUtil.getThisClass(candidate);
      if (resolveResult1 == resolveResult2 &&
          resolveResult1 instanceof PsiMember) {
        final PsiClass containingClass = ((PsiMember)resolveResult1).getContainingClass();
        if (!InheritanceUtil.isInheritorOrSelf(candidateClass, patternClass, true) &&
            InheritanceUtil.isInheritorOrSelf(candidateClass, containingClass, true) &&
            InheritanceUtil.isInheritorOrSelf(patternClass, containingClass, true)) {
          return false;
        }
      }
    }
    return null;
  }

  private static boolean isEquivalentTypeCast(@NotNull PsiTypeCastExpression pattern, @NotNull PsiTypeCastExpression candidate) {
    final PsiTypeElement castTypeElement1 = pattern.getCastType();
    final PsiTypeElement castTypeElement2 = candidate.getCastType();
    if (castTypeElement1 != null && castTypeElement2 != null) {
      final PsiType type1 = TypeConversionUtil.erasure(castTypeElement1.getType());
      final PsiType type2 = TypeConversionUtil.erasure(castTypeElement2.getType());
      if (!type1.equals(type2)) return false;
    }
    return true;
  }

  private static boolean isEquivalentNewExpression(@NotNull PsiNewExpression pattern, @NotNull PsiNewExpression candidate) {
    final PsiType type1 = pattern.getType();
    final PsiType type2 = candidate.getType();
    if (type1 == null || type2 == null) return false;
    final PsiMethod constructor1 = pattern.resolveConstructor();
    final PsiMethod constructor2 = candidate.resolveConstructor();
    if (constructor1 != null && constructor2 != null) {
      if (!pattern.getManager().areElementsEquivalent(constructor1, constructor2)) return false;
      if (pattern.getAnonymousClass() == null && candidate.getAnonymousClass() == null) return true;
    }
    return canTypesBeEquivalent(type1, type2);
  }

  private static boolean matchObjectAccess(@NotNull PsiClassObjectAccessExpression pattern,
                                           @NotNull PsiClassObjectAccessExpression candidate) {
    final PsiTypeElement operand1 = pattern.getOperand();
    final PsiTypeElement operand2 = candidate.getOperand();
    return operand1.getType().equals(operand2.getType());
  }

  private static boolean isEquivalentInstanceOf(@NotNull PsiInstanceOfExpression pattern, @NotNull PsiInstanceOfExpression candidate) {
    final PsiTypeElement operand1 = pattern.getCheckType();
    final PsiTypeElement operand2 = candidate.getCheckType();
    if (operand1 == null || operand2 == null) return false;
    if (!operand1.getType().equals(operand2.getType())) return false;
    return true;
  }

  private static boolean isEquivalentMethodCall(@NotNull PsiMethodCallExpression pattern, @NotNull PsiMethodCallExpression candidate) {
    final PsiMethod patternMethod = pattern.resolveMethod();
    final PsiMethod candidateMethod = candidate.resolveMethod();
    if (patternMethod != null && candidateMethod != null) {
      if (!MethodSignatureUtil.areSignaturesEqual(patternMethod, candidateMethod)) return false;
    }
    return true;
  }

  private static @Nullable Boolean matchReferenceExpression(@NotNull PsiReferenceExpression pattern,
                                                            @NotNull PsiReferenceExpression candidate,
                                                            @NotNull Match match) {
    final PsiExpression patternQualifier = pattern.getQualifierExpression();
    final PsiExpression candidateQualifier = candidate.getQualifierExpression();
    if (patternQualifier == null) {
      return matchUnqualifiedPatternReference(pattern, candidateQualifier, match);
    }
    if (candidateQualifier == null) {
      return matchUnqualifiedCandidateReference(patternQualifier, candidate, match);
    }
    if (patternQualifier instanceof PsiThisExpression && candidateQualifier instanceof PsiThisExpression) {
      return matchThisQualifierReference((PsiThisExpression)patternQualifier, (PsiThisExpression)candidateQualifier);
    }
    return null;
  }

  private static boolean matchUnqualifiedPatternReference(@NotNull PsiReferenceExpression pattern,
                                                          @Nullable PsiExpression candidateQualifier,
                                                          @NotNull Match match) {
    PsiClass contextClass = RefactoringChangeUtil.getThisClass(pattern);
    if (candidateQualifier instanceof PsiReferenceExpression) {
      final PsiElement resolved = ((PsiReferenceExpression)candidateQualifier).resolve();
      if (resolved instanceof PsiClass &&
          contextClass != null &&
          InheritanceUtil.isInheritorOrSelf(contextClass, (PsiClass)resolved, true)) {
        return true;
      }
    }
    return contextClass != null && match.registerInstanceExpression(candidateQualifier, contextClass);
  }

  private static boolean matchUnqualifiedCandidateReference(@NotNull PsiExpression patternQualifier,
                                                            @NotNull PsiReferenceExpression candidate,
                                                            @NotNull Match match) {
    if (patternQualifier instanceof PsiThisExpression) {
      final PsiJavaCodeReferenceElement qualifier = ((PsiThisExpression)patternQualifier).getQualifier();
      PsiElement contextClass = qualifier == null ? RefactoringChangeUtil.getThisClass(patternQualifier) : qualifier.resolve();
      return contextClass instanceof PsiClass && match.registerInstanceExpression(null, (PsiClass)contextClass);
    }
    final PsiType type = patternQualifier.getType();
    PsiClass contextClass = type instanceof PsiClassType ? ((PsiClassType)type).resolve() : null;
    try {
      final Parameter parameter = patternQualifier.getUserData(PARAMETER);

      if (parameter != null) {
        final PsiClass thisClass = RefactoringChangeUtil.getThisClass(parameter.getVariable());

        if (contextClass != null && InheritanceUtil.isInheritorOrSelf(thisClass, contextClass, true)) {
          contextClass = thisClass;
        }
        final PsiClass thisCandidate = RefactoringChangeUtil.getThisClass(candidate);
        if (thisCandidate != null && InheritanceUtil.isInheritorOrSelf(thisCandidate, contextClass, true)) {
          contextClass = thisCandidate;
        }
        return contextClass != null &&
               !(contextClass instanceof PsiAnonymousClass) &&
               match.putParameter(parameter, RefactoringChangeUtil.createThisExpression(patternQualifier.getManager(), contextClass));
      }

      if (patternQualifier instanceof PsiReferenceExpression) {
        final PsiElement resolved = ((PsiReferenceExpression)patternQualifier).resolve();
        if (resolved instanceof PsiClass) {
          final PsiClass classContext = RefactoringChangeUtil.getThisClass(candidate);
          if (classContext != null && InheritanceUtil.isInheritorOrSelf(classContext, (PsiClass)resolved, true)) {
            return true;
          }
        }
      }

      return false;
    }
    catch (IncorrectOperationException e) {
      LOG.error(e);
    }
    return false;
  }

  private static boolean matchThisQualifierReference(PsiThisExpression patternQualifier, PsiThisExpression candidateQualifier) {
    final PsiJavaCodeReferenceElement thisPatternQualifier = patternQualifier.getQualifier();
    final PsiElement patternContextClass = thisPatternQualifier == null
                                           ? RefactoringChangeUtil.getThisClass(patternQualifier) : thisPatternQualifier.resolve();
    final PsiJavaCodeReferenceElement thisCandidateQualifier = candidateQualifier.getQualifier();
    final PsiElement candidateContextClass = thisCandidateQualifier == null
                                             ? RefactoringChangeUtil.getThisClass(candidateQualifier) : thisCandidateQualifier.resolve();
    return patternContextClass == candidateContextClass;
  }

  private static boolean matchThisExpression(@NotNull PsiThisExpression pattern, @NotNull PsiElement candidate, @NotNull Match match) {
    final PsiJavaCodeReferenceElement qualifier = pattern.getQualifier();
    final PsiElement contextClass = qualifier == null ? RefactoringChangeUtil.getThisClass(pattern) : qualifier.resolve();
    if (candidate instanceof PsiReferenceExpression) {
      final PsiElement parent = candidate.getParent();
      return parent instanceof PsiReferenceExpression &&
             contextClass instanceof PsiClass &&
             match.registerInstanceExpression(((PsiReferenceExpression)parent).getQualifierExpression(), (PsiClass)contextClass);
    }
    if (candidate instanceof PsiThisExpression) {
      final PsiJavaCodeReferenceElement candidateQualifier = ((PsiThisExpression)candidate).getQualifier();
      final PsiElement candidateContextClass = candidateQualifier == null
                                               ? RefactoringChangeUtil.getThisClass(candidate) : candidateQualifier.resolve();
      return contextClass == candidateContextClass;
    }
    return false;
  }

  private static boolean matchSuperExpression(@NotNull PsiSuperExpression pattern, @NotNull PsiSuperExpression candidate) {
    final PsiJavaCodeReferenceElement qualifier = pattern.getQualifier();
    final PsiElement contextClass = qualifier == null ? RefactoringChangeUtil.getThisClass(pattern) : qualifier.resolve();
    final PsiJavaCodeReferenceElement candidateQualifier = candidate.getQualifier();
