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

import com.intellij.codeInsight.generation.GenerateMembersUtil;
import com.intellij.codeInsight.generation.GetterSetterPrototypeProvider;
import com.intellij.java.JavaBundle;
import com.intellij.lang.java.JavaLanguage;
import com.intellij.openapi.application.ApplicationManager;
import com.intellij.openapi.diagnostic.Logger;
import com.intellij.openapi.project.Project;
import com.intellij.openapi.util.Comparing;
import com.intellij.openapi.util.NlsContexts;
import com.intellij.openapi.util.Pair;
import com.intellij.openapi.util.TextRange;
import com.intellij.openapi.util.text.StringUtil;
import com.intellij.psi.*;
import com.intellij.psi.impl.source.PsiImmediateClassType;
import com.intellij.psi.javadoc.PsiDocTagValue;
import com.intellij.psi.search.PsiSearchScopeUtil;
import com.intellij.psi.search.SearchScope;
import com.intellij.psi.search.searches.OverridingMethodsSearch;
import com.intellij.psi.search.searches.ReferencesSearch;
import com.intellij.psi.util.PsiTreeUtil;
import com.intellij.psi.util.PsiTypesUtil;
import com.intellij.psi.util.PsiUtil;
import com.intellij.psi.util.TypeConversionUtil;
import com.intellij.refactoring.rename.RenameProcessor;
import com.intellij.refactoring.typeMigration.usageInfo.OverriddenUsageInfo;
import com.intellij.refactoring.typeMigration.usageInfo.OverriderUsageInfo;
import com.intellij.refactoring.typeMigration.usageInfo.TypeMigrationUsageInfo;
import com.intellij.usageView.UsageInfo;
import com.intellij.util.*;
import com.intellij.util.containers.ContainerUtil;
import com.intellij.util.containers.MultiMap;
import com.intellij.util.graph.DFSTBuilder;
import com.intellij.util.graph.GraphGenerator;
import com.intellij.util.graph.InboundSemiGraph;
import com.siyeh.ig.psiutils.ExpectedTypeUtils;
import com.siyeh.ig.psiutils.MethodCallUtils;
import org.jetbrains.annotations.*;

import java.util.*;

public class TypeMigrationLabeler {
  private static final Logger LOG = Logger.getInstance(TypeMigrationLabeler.class);
  private final Project myProject;

  public TypeMigrationRules getRules() {
    return myRules;
  }

  private final TypeMigrationRules myRules;
  private final Function<? super PsiElement, ? extends PsiType> myMigrationRootTypeFunction;
  private final @Nullable Set<PsiElement> myAllowedRoots;
  private TypeEvaluator myTypeEvaluator;
  private final LinkedHashMap<PsiElement, Object> myConversions;
  private final Map<Pair<SmartPsiElementPointer<PsiElement>, PsiType>, TypeMigrationUsageInfo> myFailedConversions;
  private LinkedList<Pair<TypeMigrationUsageInfo, PsiType>> myMigrationRoots;
  private final LinkedHashMap<TypeMigrationUsageInfo, PsiType> myNewExpressionTypeChange;
  private final LinkedHashMap<TypeMigrationUsageInfo, PsiClassType> myClassTypeArgumentsChange;

  private TypeMigrationUsageInfo[] myMigratedUsages;

  private TypeMigrationUsageInfo myCurrentRoot;
  private final Map<TypeMigrationUsageInfo, HashSet<Pair<TypeMigrationUsageInfo, PsiType>>> myRootsTree =
    new HashMap<>();
  private final Map<Pair<TypeMigrationUsageInfo, TypeMigrationUsageInfo>, Set<PsiElement>> myRootUsagesTree = new HashMap<>();
  private final Set<TypeMigrationUsageInfo> myProcessedRoots = new HashSet<>();
  private final Set<PsiTypeParameter> myDisappearedTypeParameters = new HashSet<>();

  public TypeMigrationLabeler(TypeMigrationRules rules, PsiType rootType, Project project) {
    this(rules, Functions.constant(rootType), null, project);
  }

  public TypeMigrationLabeler(TypeMigrationRules rules,
                              Function<? super PsiElement, ? extends PsiType> migrationRootTypeFunction,
                              PsiElement @Nullable("any root accepted if null") [] allowedRoots,
                              Project project) {
    myRules = rules;
    myMigrationRootTypeFunction = migrationRootTypeFunction;
    myAllowedRoots = allowedRoots == null ? null : Collections.unmodifiableSet(new HashSet<>(Arrays.asList(allowedRoots)));

    myConversions = new LinkedHashMap<>();
    myFailedConversions = new LinkedHashMap<>();
    myNewExpressionTypeChange = new LinkedHashMap<>();
    myClassTypeArgumentsChange = new LinkedHashMap<>();
    myProject = project;
    myMigrationRoots = new LinkedList<>();
    myTypeEvaluator = new TypeEvaluator(myMigrationRoots, this, myProject);
  }

  public boolean hasFailedConversions() {
    return !myFailedConversions.isEmpty();
  }

  public Function<? super PsiElement, ? extends PsiType> getMigrationRootTypeFunction() {
    return myMigrationRootTypeFunction;
  }

  public @NlsContexts.DialogMessage String[] getFailedConversionsReport() {
    final @Nls String[] report = new String[myFailedConversions.size()];
    int j = 0;

    for (Pair<SmartPsiElementPointer<PsiElement>, PsiType> p : myFailedConversions.keySet()) {
      final PsiElement element = p.getFirst().getElement();
      LOG.assertTrue(element != null);
      if (element instanceof PsiExpression expression) {
        final PsiType type = expression.getType();
        report[j++] = JavaBundle.message("type.migration.cannot.convert.message",
                                         StringUtil.escapeXmlEntities(element.getText()),
                                         type != null ? StringUtil.escapeXmlEntities(type.getCanonicalText()) : "",
                                         StringUtil.escapeXmlEntities(p.getSecond().getCanonicalText()),
                                         type == null ? 0 : 1);
      }
      else {
        LOG.assertTrue(element instanceof PsiExpressionList);
        report[j++] = JavaBundle.message("type.migration.cannot.convert.vararg.message",
                                         StringUtil.escapeXmlEntities(element.getParent().getText()));
      }
    }

    return report;
  }

  public UsageInfo[] getFailedUsages(TypeMigrationUsageInfo root) {
    return map2Usages(ContainerUtil.mapNotNull(myFailedConversions.entrySet(),
                                               entry -> entry.getValue().equals(root) ? entry.getKey() : null));
  }

  public UsageInfo[] getFailedUsages() {
    return map2Usages(myFailedConversions.keySet());
  }

  private static UsageInfo @NotNull [] map2Usages(Collection<? extends Pair<SmartPsiElementPointer<PsiElement>, PsiType>> usages) {
    return ContainerUtil.map2Array(usages, new UsageInfo[usages.size()], pair -> {
      final PsiElement element = pair.getFirst().getElement();
      LOG.assertTrue(element != null);
      return new UsageInfo(element) {
        @Override
        public @Nullable String getTooltipText() {
          if (element instanceof PsiExpression expression) {
            final PsiType type = expression.isValid() ? expression.getType() : null;
            if (type == null) return null;
            return JavaBundle.message("type.migration.cannot.convert.tooltip", type.getCanonicalText(), pair.getSecond().getCanonicalText());
          }
          else {
            return JavaBundle.message("type.migration.cannot.convert.vararg.tooltip");
          }
        }
      };
    });
  }

  public TypeMigrationUsageInfo[] getMigratedUsages() {
    final LinkedList<Pair<TypeMigrationUsageInfo, PsiType>> declarations = getTypeEvaluator().getMigratedDeclarations();
    final TypeMigrationUsageInfo[] usages =
      new TypeMigrationUsageInfo[declarations.size() + myConversions.size() + myNewExpressionTypeChange.size() +
                                 myClassTypeArgumentsChange.size()];

    int j = 0;

    for (PsiElement element : myConversions.keySet()) {
      final Object conv = myConversions.get(element);
      usages[j++] = new TypeMigrationUsageInfo(element) {
        @Override
        public String getTooltipText() {
          if (conv instanceof String conversion) {   //todo
            return JavaBundle.message("type.migration.replaced.notification", conversion.replaceAll("\\$", element.getText()));
          }
          else {
            return JavaBundle.message("type.migration.replaced.notification", conv.toString());
          }
        }

        @Override
        public boolean isExcluded() {
          if (conv instanceof TypeConversionDescriptorBase) return ((TypeConversionDescriptorBase)conv).getRoot().isExcluded();
          return super.isExcluded();
        }

        @Override
        public TypeMigrationUsageInfo getOwnerRoot() {
          return conv instanceof TypeConversionDescriptorBase ? ((TypeConversionDescriptorBase)conv).getRoot() : null;
        }
      };
    }

    for (Pair<TypeMigrationUsageInfo, PsiType> p : declarations) {
      final TypeMigrationUsageInfo element = p.getFirst();
      usages[j++] = element;
    }

    for (TypeMigrationUsageInfo info : myClassTypeArgumentsChange.keySet()) {
      usages[j++] = info;
    }

    for (TypeMigrationUsageInfo expr : myNewExpressionTypeChange.keySet()) {
      usages[j++] = expr;
    }
    return sortMigratedUsages(usages);
  }

  private TypeMigrationUsageInfo[] sortMigratedUsages(TypeMigrationUsageInfo[] infos) {
    final DFSTBuilder<TypeMigrationUsageInfo> builder = new DFSTBuilder<>(GraphGenerator.generate(
      new InboundSemiGraph<>() {
        @Override
        public @NotNull Collection<TypeMigrationUsageInfo> getNodes() {
          final Set<TypeMigrationUsageInfo> infos = new HashSet<>();
          for (Map.Entry<TypeMigrationUsageInfo, HashSet<Pair<TypeMigrationUsageInfo, PsiType>>> entry : myRootsTree.entrySet()) {
            infos.add(entry.getKey());
            infos.addAll(ContainerUtil.map(entry.getValue(), pair -> pair.getFirst()));
          }
          return infos;
        }

        @Override
        public @NotNull Iterator<TypeMigrationUsageInfo> getIn(TypeMigrationUsageInfo n) {
          final HashSet<Pair<TypeMigrationUsageInfo, PsiType>> rawNodes = myRootsTree.get(n);
          if (rawNodes == null) {
            return Collections.emptyIterator();
          }
          final List<TypeMigrationUsageInfo> in =
            ContainerUtil.map(rawNodes, pair -> pair.getFirst());
          return in.iterator();
        }
      }));
    final Comparator<TypeMigrationUsageInfo> cmp = builder.comparator();

    Arrays.sort(infos, (info1, info2) -> {
      final TypeMigrationUsageInfo i1 = info1.getOwnerRoot();
      final TypeMigrationUsageInfo i2 = info2.getOwnerRoot();
      if (i1 == null && i2 == null) {
        return 0;
      }
      if (i1 == null) {
        return 1;
      }
      if (i2 == null) {
        return -1;
      }
      final PsiElement element1 = info1.getElement();
      final PsiElement element2 = info2.getElement();
      LOG.assertTrue(element1 != null && element2 != null);
      if (element1.equals(element2)) {
        return 0;
      }
      final TextRange range1 = element1.getTextRange();
      final TextRange range2 = element2.getTextRange();
      if (range1.contains(range2)) {
        return 1;
      }
      if (range2.contains(range1)) {
        return -1;
      }

      final int res = cmp.compare(i1, i2);
      if (res != 0) {
        return res;
      }
      return Integer.compare(range2.getStartOffset(), range1.getStartOffset());
    });

    return infos;
  }

  MigrationProducer createMigratorFor(UsageInfo[] usages) {
    final Map<UsageInfo, Object> conversions = new HashMap<>();
    for (UsageInfo usage : usages) {
      final Object conversion = getConversion(usage.getElement());
      if (conversion != null) {
        conversions.put(usage, conversion);
      }
    }
    return new MigrationProducer(conversions);
  }

  public @Nullable <T> T getSettings(Class<T> aClass) {
    return myRules.getConversionSettings(aClass);
  }

  final class MigrationProducer {
    private final Map<UsageInfo, Object> myRemainConversions;
    private final MultiMap<PsiTypeElement, TypeMigrationUsageInfo> myVariableMigration = new MultiMap<>();

    private MigrationProducer(Map<UsageInfo, Object> conversions) {
      myRemainConversions = conversions;
    }

    public void change(@NotNull TypeMigrationUsageInfo usageInfo, @NotNull Consumer<? super PsiNewExpression> consumer) {
      final PsiElement element = usageInfo.getElement();
      if (element == null) return;
      final Project project = element.getProject();
      if (element instanceof PsiExpression expression) {
        if (element instanceof PsiNewExpression) {
          for (Map.Entry<TypeMigrationUsageInfo, PsiType> info : myNewExpressionTypeChange.entrySet()) {
            final PsiElement expressionToReplace = info.getKey().getElement();
            if (expression.equals(expressionToReplace)) {
              final PsiNewExpression newExpression =
                TypeMigrationReplacementUtil.replaceNewExpressionType(project, (PsiNewExpression)expressionToReplace, info.getValue());
              if (newExpression != null) {
                consumer.consume(newExpression);
              }
            }
          }
        }
        final Object conversion = myRemainConversions.get(usageInfo);
        if (conversion != null) {
          myRemainConversions.remove(usageInfo);
          TypeMigrationReplacementUtil.replaceExpression(expression, project, conversion, myTypeEvaluator);
        }
      } else if (element instanceof PsiReferenceParameterList) {
        for (Map.Entry<TypeMigrationUsageInfo, PsiClassType> entry : myClassTypeArgumentsChange.entrySet()) {
          if (element.equals(entry.getKey().getElement())) { //todo check null
            final PsiElementFactory factory = JavaPsiFacade.getElementFactory(project);
            try {
              element.getParent().replace(factory.createReferenceElementByType(entry.getValue()));
            }
            catch (IncorrectOperationException e) {
              LOG.error(e);
            }
          }
        }
      }
      else if ((element instanceof PsiField || element instanceof PsiLocalVariable) &&
               isMultiVariableDeclaration((PsiVariable)element)) {
        final PsiTypeElement typeElement = ((PsiVariable)element).getTypeElement();
        if (typeElement != null) myVariableMigration.putValue(typeElement, usageInfo);
      }
      else {
        TypeMigrationReplacementUtil.migrateMemberOrVariableType(element, project, getTypeEvaluator().getType(usageInfo));
        if (usageInfo instanceof OverriddenUsageInfo) {
          final String migrationName = ((OverriddenUsageInfo)usageInfo).getMigrateMethodName();
          if (migrationName != null) {
            ApplicationManager.getApplication().invokeLater(() -> {
              if (element.isValid()) {
                new RenameProcessor(project, element, migrationName, false, false).run();
              }
            });
          }
        }
      }
    }

    public void flush() {
      for (Map.Entry<PsiTypeElement, Collection<TypeMigrationUsageInfo>> entry : myVariableMigration.entrySet()) {
        final PsiTypeElement typeElement = entry.getKey();
        if (!typeElement.isValid()) continue;
        final Collection<TypeMigrationUsageInfo> migrations = entry.getValue();
        if (migrations.size() != 1) {
          MultiMap<PsiType, PsiVariable> variablesByMigrationType = new MultiMap<>();
          for (TypeMigrationUsageInfo migration : migrations) {
            final PsiElement var = migration.getElement();
            if (!(var instanceof PsiLocalVariable || var instanceof PsiField)) {
              continue;
            }
            final PsiType type = getTypeEvaluator().getType(migration);
            variablesByMigrationType.putValue(type, (PsiVariable)var);
          }
          if (variablesByMigrationType.size() == 1) {
            final Map.Entry<PsiType, Collection<PsiVariable>> migrationTypeAndVariables =
              ContainerUtil.getFirstItem(variablesByMigrationType.entrySet());
            LOG.assertTrue(migrationTypeAndVariables != null);
            final PsiVariable[] variables = PsiTreeUtil.getChildrenOfType(typeElement.getParent().getParent(), PsiVariable.class);
            if (variables != null && variables.length == migrationTypeAndVariables.getValue().size()) {
              try {
                PsiType migrationType = migrationTypeAndVariables.getKey();
                final Project project = variables[0].getProject();
                migrationType = TypeMigrationReplacementUtil.revalidateType(migrationType, project);
                typeElement.replace(JavaPsiFacade.getElementFactory(project).createTypeElement(migrationType));
              }
              catch (IncorrectOperationException e) {
                LOG.error(e);
              }
              continue;
            }
          }
        }
        for (TypeMigrationUsageInfo info : entry.getValue()) migrateMultiDeclarationVariable(info);
      }
    }

    private void migrateMultiDeclarationVariable(TypeMigrationUsageInfo varUsageInfo) {
      final PsiElement var = varUsageInfo.getElement();
      if (!(var instanceof PsiLocalVariable || var instanceof PsiField)) return;
      ((PsiVariable) var).normalizeDeclaration();
      TypeMigrationReplacementUtil.migrateMemberOrVariableType(var, var.getProject(), getTypeEvaluator().getType(varUsageInfo));
    }

    Object getConversion(UsageInfo info) {
      return myRemainConversions.remove(info);
    }

    private static boolean isMultiVariableDeclaration(PsiVariable variable) {
      final PsiElement parent = variable.getParent();
      LOG.assertTrue(parent != null);
      final PsiVariable[] variables = PsiTreeUtil.getChildrenOfType(parent, PsiVariable.class);
      LOG.assertTrue(variables != null);
      return variables.length != 1;
    }
  }

  @Nullable
  Object getConversion(PsiElement element) {
    return myConversions.get(element);
  }

  public TypeMigrationUsageInfo[] getMigratedUsages(boolean autoMigrate, PsiElement... roots) {
    if (myMigratedUsages == null) {
      migrate(autoMigrate, roots);
      myMigratedUsages = getMigratedUsages();
    }
    return myMigratedUsages;
  }

  public @Nullable Set<PsiElement> getTypeUsages(TypeMigrationUsageInfo element, TypeMigrationUsageInfo currentRoot) {
    return myRootUsagesTree.get(Pair.create(element, currentRoot));
  }

  void convertExpression(PsiExpression expr, PsiType toType, PsiType fromType, boolean isCovariantPosition) {
    final PsiMember member = expr instanceof PsiMethodCallExpression ? ((PsiMethodCallExpression)expr).resolveMethod() : null;
    convertExpression(expr, toType, fromType, isCovariantPosition, member);
  }

  private void convertExpression(PsiExpression expr, PsiType toType, PsiType fromType, boolean isCovariantPosition, PsiMember member) {
    final TypeConversionDescriptorBase conversion = myRules.findConversion(fromType, toType, member, expr, isCovariantPosition, this);

    if (conversion == null) {
      markFailedConversion(toType, expr);
    }
    else {
      setConversionMapping(expr, conversion);
    }
  }

  public void migrateExpressionType(PsiExpression expr,
                                    PsiType migrationType,
                                    PsiElement place,
                                    boolean alreadyProcessed,
                                    boolean isCovariant) {
    PsiType originalType = expr.getType();

    if (originalType == null || originalType.equals(migrationType)) return;

    if (originalType.equals(PsiTypes.nullType())) {
      if (migrationType instanceof PsiPrimitiveType) {
        markFailedConversion(migrationType, expr);
        return;
      }
      PsiType expectedType = ExpectedTypeUtils.findExpectedType(expr, false);
      if (expectedType != null &&
          !expectedType.equals(PsiTypes.nullType()) &&
          myRules.shouldConvertNull(expectedType, migrationType, expr)) {
        convertExpression(expr, migrationType, expectedType, isCovariant);
      }
      return;
    }

    if (expr instanceof PsiConditionalExpression condExpr) {
      for (PsiExpression e : new PsiExpression[]{condExpr.getThenExpression(), condExpr.getElseExpression()}) {
        if (e != null) {
          migrateExpressionType(e, migrationType, place, alreadyProcessed, false);
        }
      }
      getTypeEvaluator().setType(new TypeMigrationUsageInfo(expr), migrationType);
      return;
    } else if (expr instanceof PsiClassObjectAccessExpression) {
      if (!TypeConversionUtil.isAssignable(migrationType, expr.getType())) {
        markFailedConversion(migrationType, expr);
        return;
      }
    } else if (expr instanceof PsiArrayInitializerExpression && migrationType instanceof PsiArrayType) {
      final PsiExpression[] initializers = ((PsiArrayInitializerExpression)expr).getInitializers();
      for (PsiExpression initializer : initializers) {
        migrateExpressionType(initializer, ((PsiArrayType)migrationType).getComponentType(), expr, alreadyProcessed, true);
      }
      getTypeEvaluator().setType(new TypeMigrationUsageInfo(expr), migrationType);
      return;
    } else if (expr instanceof PsiArrayAccessExpression) {
      migrateExpressionType(((PsiArrayAccessExpression)expr).getArrayExpression(),
                            migrationType.createArrayType(), place, alreadyProcessed, isCovariant);
      return;
    }
    else if (expr instanceof PsiReferenceExpression) {
      final PsiElement resolved = ((PsiReferenceExpression)expr).resolve();
      if (resolved != null) {
        if (!addMigrationRoot(resolved, migrationType, place, alreadyProcessed, !isCovariant)) {
          convertExpression(expr, migrationType, getTypeEvaluator().evaluateType(expr), isCovariant);
        }
      }
      return;
    }
    else if (expr instanceof PsiMethodCallExpression) {
      final PsiMethod resolved = ((PsiMethodCallExpression)expr).resolveMethod();
      if (resolved != null) {
        if (!addMigrationRoot(resolved, migrationType, place, alreadyProcessed, !isCovariant)) {
          convertExpression(expr, migrationType, getTypeEvaluator().evaluateType(expr), isCovariant);
        }
      }
      return;
    }
    else if (expr instanceof PsiNewExpression) {
      if (originalType.getArrayDimensions() == migrationType.getArrayDimensions()) {
        if (migrationType.getArrayDimensions() > 0) {
          final PsiType elementType = ((PsiArrayType)migrationType).getComponentType();

          final PsiArrayInitializerExpression arrayInitializer = ((PsiNewExpression)expr).getArrayInitializer();

          if (arrayInitializer != null) {
            final PsiExpression[] initializers = arrayInitializer.getInitializers();
            for (int i = initializers.length - 1; i >= 0; i--) {
              migrateExpressionType(initializers[i], elementType, place, alreadyProcessed, true);
            }
          }

          if (isGenericsArrayType(elementType)) {
            markFailedConversion(migrationType, expr);
            return;
          }

          if (!alreadyProcessed) {
            final TypeMigrationUsageInfo usageInfo = new TypeMigrationUsageInfo(expr);
            usageInfo.setOwnerRoot(myCurrentRoot);
            myNewExpressionTypeChange.put(usageInfo, migrationType);
            getTypeEvaluator().setType(new TypeMigrationUsageInfo(expr), migrationType);
          }
          return;
        }
        else if (migrationType instanceof PsiClassType migrationClassType && originalType instanceof PsiClassType originalClassType &&
                 migrationClassType.rawType().isAssignableFrom(originalClassType.rawType())) {
          final PsiClass originalClass = PsiUtil.resolveClassInType(originalType);
          if (originalClass instanceof PsiAnonymousClass anonymousClass) {
            originalClassType = anonymousClass.getBaseClassType();
          }
          final PsiType type = TypeEvaluator.substituteType(migrationClassType, originalClassType, true,
                                                            originalClassType.resolveGenerics().getElement(),
                                                            JavaPsiFacade.getElementFactory(expr.getProject())
                                                              .createType(originalClassType.resolve(), PsiSubstitutor.EMPTY));
          if (type != null) {
            final TypeMigrationUsageInfo usageInfo = new TypeMigrationUsageInfo(expr);
            usageInfo.setOwnerRoot(myCurrentRoot);
            myNewExpressionTypeChange.put(usageInfo, type);
            getTypeEvaluator().setType(new TypeMigrationUsageInfo(expr), type);
            return;
          }
        }
      }

    }
    else if (expr instanceof PsiLambdaExpression) {
      //TODO conversion of lambda expression now works incorrectly [Dmitry Batkovich]
      return;
    }

    convertExpression(expr, migrationType, originalType, isCovariant);
  }

  private static boolean isGenericsArrayType(PsiType elementType) {
    if (elementType instanceof PsiClassType && ((PsiClassType)elementType).hasParameters()) {
      return true;
    } else if (elementType instanceof PsiArrayType) {
      final PsiType componentType = ((PsiArrayType)elementType).getComponentType();
      return isGenericsArrayType(componentType);
    }
    return false;
  }

  boolean addMigrationRoot(PsiElement element, PsiType type, PsiElement place, boolean alreadyProcessed, boolean isContraVariantPosition) {
    return addMigrationRoot(element, type, place, alreadyProcessed, isContraVariantPosition, false);
  }

  boolean addMigrationRoot(PsiElement element,
                           PsiType type,
                           PsiElement place,
                           boolean alreadyProcessed,
                           boolean isContraVariantPosition,
                           boolean userDefinedType) {
    if (myAllowedRoots != null && !myAllowedRoots.contains(element)) {
      return false;
    }
    if (type.equals(PsiTypes.nullType()) ||
        PsiTypes.voidType().equals(type) && myCurrentRoot != null) {
      return false;
    }
    final PsiElement resolved = Util.normalizeElement(element);
    if (!canBeRoot(resolved, myRules.getSearchScope()) || resolved instanceof PsiEnumConstant) {
      return false;
    }
    final PsiType originalType = getElementType(resolved);
    LOG.assertTrue(originalType != null);
    type = userDefinedType ? type : TypeEvaluator.substituteType(type, originalType, isContraVariantPosition);

    if (userDefinedType) {
      Set<PsiTypeParameter> disappearedTypeParameters = getTypeParameters(originalType);
      disappearedTypeParameters.removeAll(getTypeParameters(type));
      myDisappearedTypeParameters.addAll(disappearedTypeParameters);
    }
    else if (typeContainsTypeParameters(originalType, getTypeParameters(type))) return false;

    if (type instanceof PsiCapturedWildcardType) return false;

    if (resolved instanceof PsiMethod method) {
      if (method.getContainingClass() instanceof PsiAnonymousClass anonymousClass) {
        final HierarchicalMethodSignature signature = method.getHierarchicalMethodSignature();
        final List<HierarchicalMethodSignature> superSignatures = signature.getSuperSignatures();
        if (!superSignatures.isEmpty()) {
          final HierarchicalMethodSignature superSignature = superSignatures.get(0);

          final PsiSubstitutor substitutor = superSignature.getSubstitutor();
          if (!substitutor.getSubstitutionMap().isEmpty()) {
            final PsiMethod superMethod = superSignature.getMethod();

            if (superMethod.getReturnType() instanceof PsiClassType superReturnType &&
                superReturnType.resolve() instanceof PsiTypeParameter returnTypeParameter) {
              final PsiType expectedReturnType = substitutor.substitute(returnTypeParameter);
              if (Comparing.equal(expectedReturnType, method.getReturnType())) {
                final PsiClassType baseClassType = anonymousClass.getBaseClassType();
                final PsiClassType.ClassResolveResult result = baseClassType.resolveGenerics();
                final PsiClass anonymousBaseClass = result.getElement();

                if (anonymousBaseClass != null) {
                  final PsiSubstitutor superHierarchySubstitutor = TypeConversionUtil
                    .getClassSubstitutor(superMethod.getContainingClass(), anonymousBaseClass, PsiSubstitutor.EMPTY);
                  final PsiType maybeTypeParameter = superHierarchySubstitutor.substitute(returnTypeParameter);

                  if (maybeTypeParameter instanceof PsiClassType classType &&
                      classType.resolve() instanceof PsiTypeParameter typeParameter) {
                    final PsiSubstitutor newSubstitutor = result.getSubstitutor().put(typeParameter, type);
                    addRoot(new TypeMigrationUsageInfo(anonymousClass.getBaseClassReference().getParameterList()),
                            new PsiImmediateClassType(anonymousBaseClass, newSubstitutor),
                            place,
                            alreadyProcessed);
                  }
                }
              }
            }
          }
        }
      }

      final PsiMethod[] methods = OverridingMethodsSearch.search(method).toArray(PsiMethod.EMPTY_ARRAY);
      final OverriderUsageInfo[] overriders = new OverriderUsageInfo[methods.length];
      for (int i = -1; i < methods.length; i++) {
        final TypeMigrationUsageInfo m;
        if (i < 0) {
          final OverriddenUsageInfo overriddenUsageInfo = new OverriddenUsageInfo(method);
          m = overriddenUsageInfo;
          final String newMethodName = isMethodNameCanBeChanged(method);
          if (newMethodName != null) {
            final MigrateGetterNameSetting migrateGetterNameSetting = myRules.getConversionSettings(MigrateGetterNameSetting.class);
            migrateGetterNameSetting.askUserIfNeeded(overriddenUsageInfo, newMethodName, myTypeEvaluator.getType(myCurrentRoot));
          }
        }
        else {
          overriders[i] = new OverriderUsageInfo(methods[i], method);
          m = overriders[i];
        }

        alreadyProcessed = addRoot(m, type, place, alreadyProcessed);
      }

      return !alreadyProcessed;
    }
    else if (resolved instanceof PsiParameter parameter && parameter.getDeclarationScope() instanceof PsiMethod method) {
      final int index = method.getParameterList().getParameterIndex(parameter);
      final PsiMethod[] methods = OverridingMethodsSearch.search(method).toArray(PsiMethod.EMPTY_ARRAY);

      final OverriderUsageInfo[] overriders = new OverriderUsageInfo[methods.length];
      final OverriddenUsageInfo overriddenUsageInfo = new OverriddenUsageInfo(method.getParameterList().getParameters()[index]);
      for (int i = -1; i < methods.length; i++) {
        final PsiMethod m = i < 0 ? method : methods[i];
        final PsiParameter p = m.getParameterList().getParameters()[index];
        final TypeMigrationUsageInfo paramUsageInfo;
        if (i < 0) {
          paramUsageInfo = overriddenUsageInfo;
        }
        else {
          overriders[i] = new OverriderUsageInfo(p, method);
          paramUsageInfo = overriders[i];
        }
        alreadyProcessed = addRoot(paramUsageInfo, type, place, alreadyProcessed);
      }

      return !alreadyProcessed;
    }
    else {
      return !addRoot(new TypeMigrationUsageInfo(resolved), type, place, alreadyProcessed);
    }
  }

  private static @NotNull Set<PsiTypeParameter> getTypeParameters(@NotNull PsiType type) {
    if (type instanceof PsiClassType) {
      PsiTypesUtil.TypeParameterSearcher searcher = new PsiTypesUtil.TypeParameterSearcher();
      type.accept(searcher);
      return searcher.getTypeParameters();
    }
    return Collections.emptySet();
  }

  private @Nullable String isMethodNameCanBeChanged(PsiMethod method) {
    if (myCurrentRoot == null) {
      return null;
    }
    final PsiElement root = myCurrentRoot.getElement();
    if (!(root instanceof PsiField field)) {
      return null;
    }
    final PsiType migrationType = myTypeEvaluator.getType(root);
    if (migrationType == null) {
      return null;
    }
    final PsiType sourceType = field.getType();
    if (TypeConversionUtil.isAssignable(migrationType, sourceType)) {
      return null;
    }
    if (!(migrationType.equals(PsiTypes.booleanType()) || migrationType.equals(PsiTypes.booleanType().getBoxedType(field))) &&
        !(sourceType.equals(PsiTypes.booleanType()) || sourceType.equals(PsiTypes.booleanType().getBoxedType(field)))) {
      return null;
    }
    final PsiMethod[] getters =
