// Copyright 200myPsiClassBrains s.r.o. and contributors. Use of this source code is governed by the Apache 2.0 license.
package com.intellij.java.codeserver.core;

import com.intellij.openapi.diagnostic.Logger;
import com.intellij.psi.*;
import com.intellij.psi.util.*;
import com.intellij.util.containers.ConcurrentFactoryMap;
import com.intellij.util.containers.ContainerUtil;
import com.intellij.util.containers.MultiMap;
import com.intellij.util.containers.SmartHashSet;
import one.util.streamex.StreamEx;
import org.jetbrains.annotations.*;

import java.util.*;
import java.util.function.BiPredicate;
import java.util.stream.Collectors;

import static java.util.Objects.hash;

/**
 * Utilities related to the computation of pattern exhaustiveness
 */
public final class JavaPatternExhaustivenessUtil {
  private JavaPatternExhaustivenessUtil() { }

  private static final Logger LOG = Logger.getInstance(JavaPatternExhaustivenessUtil.class);
  //it is approximately equals max method size * 10
  private static final int MAX_ITERATION_COVERAGE = 5_000;
  private static final int MAX_GENERATED_PATTERN_NUMBER = 10;

  /**
   * JEP 440-441
   * Check record pattern exhaustiveness.
   * This method tries to rewrite the existing set of patterns to equivalent
   */
  private static @NotNull RecordExhaustivenessResult checkRecordPatternExhaustivenessForDescriptors(@NotNull List<? extends PatternDescriptor> elements,
                                                                                                    @NotNull PsiType targetType,
                                                                                                    @NotNull PsiElement context) {
    List<PatternDeconstructionDescriptor> descriptions =
      StreamEx.of(elements).select(PatternDeconstructionDescriptor.class)
        .filter(element -> TypeConversionUtil.areTypesConvertible(element.type(), targetType))
        .toList();

    if (descriptions.isEmpty()) {
      return RecordExhaustivenessResult.createNotBeAdded();
    }
    return CachedValuesManager.getCachedValue(context, () -> {
      Map<ReduceResultCacheContext, RecordExhaustivenessResult> cacheResult = ConcurrentFactoryMap.createMap(cacheContext -> {
        Set<? extends PatternDescriptor> patterns = cacheContext.currentPatterns;
        PsiType selectorType = cacheContext.mySelectorType;
        ReduceCache cache = ReduceCache.init();
        LoopReduceResult result = reduceInLoop(selectorType, context, new HashSet<>(patterns),
                                               (descriptionPatterns, type) -> coverSelectorType(context, descriptionPatterns, selectorType),
                                               cache, true);
        if (result.stopped()) {
          return RecordExhaustivenessResult.createExhaustiveResult();
        }
        List<? extends PatternDescriptor> missedRecordPatterns = findMissedRecordPatterns(selectorType, result.patterns, context, cache);
        if (missedRecordPatterns == null) {
          return RecordExhaustivenessResult.createNotBeAdded();
        }
        RecordExhaustivenessResult exhaustiveResult = RecordExhaustivenessResult.createNotExhaustiveResult();
        exhaustiveResult.addBranches(missedRecordPatterns);
        return exhaustiveResult;
      });
      return CachedValueProvider.Result.create(cacheResult, PsiModificationTracker.MODIFICATION_COUNT);
    }).get(new ReduceResultCacheContext(targetType, new HashSet<>(descriptions)));
  }

  @ApiStatus.Experimental
  public static @NotNull RecordExhaustivenessResult checkRecordExhaustiveness(@NotNull List<? extends PsiCaseLabelElement> elements,
                                                                              @NotNull PsiType selectorType,
                                                                              @NotNull PsiElement context) {
    return checkRecordPatternExhaustivenessForDescriptors(preparePatternDescriptors(elements), selectorType, context);
  }

  /**
   * Try to find the missed record patterns for the given selector type and patterns.
   * This method works only with relatively simple cases: components must not have generic types,
   * nested record patterns are ignored.
   * How it works:
   * Record(q0...qi...qn).
   * The method finds a set of records for i components, such that (q0...qr...qn), where r!=i equivalent,
   * and tries to find missing classes for i components. After each iteration, reducing is applied.
   * Used patterns will be deleted if something was reduced.
   * After all steps, coverage is checked.
   *
   * @param selectorType The selector type to find missed record patterns for.
   * @param patterns     The set of patterns to analyze.
   * @param context      The context element.
   * @param cache        The cache of previously calculated reduce results.
   * @return The list of missed record patterns, or null if none are found.
   */
  private static @Nullable List<? extends PatternDescriptor> findMissedRecordPatterns(@NotNull PsiType selectorType,
                                                                                      @NotNull Set<? extends PatternDescriptor> patterns,
                                                                                      @NotNull PsiElement context,
                                                                                      @NotNull ReduceCache cache) {
    PsiClass selectorClass = PsiUtil.resolveClassInClassTypeOnly(selectorType);
    if (selectorClass == null) {
      return null;
    }
    if (patterns.size() > 100) {
      return null;
    }
    List<PsiType> componentTypes = getComponentTypes(context, selectorType);
    if (componentTypes == null) {
      return null;
    }
    for (PsiType componentType : componentTypes) {
      PsiClass componentClass = PsiUtil.resolveClassInClassTypeOnly(componentType);
      if ((componentClass == null || componentClass.hasTypeParameters()) && !TypeConversionUtil.isPrimitiveAndNotNull(componentType)) {
        return null;
      }
    }
    for (PatternDescriptor pattern : patterns) {
      if (pattern instanceof PatternTypeTestDescriptor) {
        return null;
      }
    }

    Map<PsiType, Set<PatternDeconstructionDescriptor>> groupedByType =
      StreamEx.of(patterns)
        .select(PatternDeconstructionDescriptor.class)
        .groupingBy(t -> t.type(), Collectors.toSet());
    if (groupedByType.size() != 1) {
      return null;
    }

    Set<PatternDeconstructionDescriptor> descriptions = groupedByType.values().iterator().next();
    if (descriptions.isEmpty()) {
      return null;
    }
    PatternDeconstructionDescriptor sample = descriptions.iterator().next();
    if (!(sample.type().equals(selectorType))) {
      return null;
    }
    LinkedHashSet<PatternDeconstructionDescriptor> missingRecordPatterns = new LinkedHashSet<>();
    Set<PatternDeconstructionDescriptor> filtered = getDeconstructionPatternOnlyWithTestPatterns(descriptions);
    if (filtered.isEmpty()) {
      return List.of(
        new PatternDeconstructionDescriptor(selectorType, ContainerUtil.map(componentTypes, t -> new PatternTypeTestDescriptor(t))));
    }
    Set<PatternDescriptor> combinedPatterns = new HashSet<>(filtered);

    for (int i = 0; i < sample.list().size(); i++) {
      List<PatternDeconstructionDescriptor> missingRecordPatternsForThisIteration = new ArrayList<>();

      //limit the depth
      if (missingRecordPatterns.size() > MAX_GENERATED_PATTERN_NUMBER) {
        return null;
      }
      MultiMap<List<PatternDescriptor>, PatternDeconstructionDescriptor> groupWithoutOneComponent =
        getGroupWithoutOneComponent(combinedPatterns, i);
      for (Map.Entry<List<PatternDescriptor>, Collection<PatternDeconstructionDescriptor>> value :
        groupWithoutOneComponent.entrySet()) {
        Collection<PatternDeconstructionDescriptor> setWithOneDifferentElement = value.getValue();
        if (setWithOneDifferentElement.isEmpty()) {
          return null;
        }
        List<PatternTypeTestDescriptor> nestedTypeDescriptions = getNestedTypeTestDescriptions(setWithOneDifferentElement, i);
        Set<PatternTypeTestDescriptor> missedComponentTypeDescription = new HashSet<>();
        if (componentTypes.size() <= i) {
          return null;
        }
        PsiType componentType = componentTypes.get(i);
        if (nestedTypeDescriptions.isEmpty()) {
          missedComponentTypeDescription.add(new PatternTypeTestDescriptor(componentType));
        }
        else {
          Set<PsiType> existedTypes = nestedTypeDescriptions.stream().map(t -> t.type()).collect(Collectors.toSet());
          Set<PsiClass> sealedResult = findMissedClasses(componentType, nestedTypeDescriptions, new ArrayList<>(), context);
          if (!sealedResult.isEmpty()) {
            addNewClasses(context, componentType, sealedResult, existedTypes, missedComponentTypeDescription);
          }
          else {
            combinedPatterns.removeAll(setWithOneDifferentElement);
            Collection<PatternDeconstructionDescriptor> topLevelPattern =
              createPatternsFrom(i, Set.of(new PatternTypeTestDescriptor(componentType)), setWithOneDifferentElement.iterator().next());
            combinedPatterns.addAll(topLevelPattern);
          }
        }
        Collection<PatternDeconstructionDescriptor> newPatterns =
          createPatternsFrom(i, missedComponentTypeDescription, setWithOneDifferentElement.iterator().next());
        for (PatternDeconstructionDescriptor pattern : newPatterns) {
          if (ContainerUtil.exists(filtered, existedPattern -> oneOfUnconditional(context, existedPattern, pattern))) {
            continue;
          }
          missingRecordPatternsForThisIteration.add(pattern);
        }
        missingRecordPatterns.addAll(missingRecordPatternsForThisIteration);
      }
      combinedPatterns.addAll(missingRecordPatternsForThisIteration);
      LoopReduceResult reduceResult = reduceInLoop(selectorType, context, combinedPatterns, (set, type) -> false, cache, false);
      //work only with reduced patterns to speed up
      Set<? extends PatternDescriptor> newPatterns = new HashSet<>(reduceResult.patterns());
      if (reduceResult.changed()) {
        newPatterns.removeAll(combinedPatterns);
        combinedPatterns.clear();
        combinedPatterns.addAll(newPatterns);
      }
    }
    LoopReduceResult reduceResult = reduceInLoop(selectorType, context, combinedPatterns, (set, type) -> false, cache, false);
    return coverSelectorType(context, reduceResult.patterns(), selectorType) ? new ArrayList<>(missingRecordPatterns) : null;
  }

  private static @NotNull List<PatternTypeTestDescriptor> getNestedTypeTestDescriptions(@NotNull Collection<PatternDeconstructionDescriptor> setWithOneDifferentElement,
                                                                                        int i) {
    return StreamEx.of(setWithOneDifferentElement)
      .map(t -> t.list().get(i))
      .select(PatternTypeTestDescriptor.class)
      .toList();
  }

  private static @NotNull MultiMap<List<PatternDescriptor>, PatternDeconstructionDescriptor> getGroupWithoutOneComponent(
    @NotNull Set<? extends PatternDescriptor> combinedPatterns, int i) {
    MultiMap<List<PatternDescriptor>, PatternDeconstructionDescriptor> groupWithoutOneComponent = new MultiMap<>();
    for (PatternDescriptor description : combinedPatterns) {
      if (!(description instanceof PatternDeconstructionDescriptor deconstructionDescription)) {
        continue;
      }
      if (deconstructionDescription.list().size() <= i) {
        continue;
      }
      groupWithoutOneComponent.putValue(getWithoutComponent(deconstructionDescription, i), deconstructionDescription);
    }
    return groupWithoutOneComponent;
  }

  private static List<PatternDescriptor> getWithoutComponent(@NotNull PatternDeconstructionDescriptor description,
                                                             int toRemove) {
    ArrayList<PatternDescriptor> shortKey = new ArrayList<>();
    for (int i = 0; i < description.list().size(); i++) {
      if (toRemove == i) {
        continue;
      }
      shortKey.add(description.list().get(i));
    }
    return shortKey;
  }

  /**
   * Unwrap sealed types in the given ReduceResult.
   * This method can expand a set of patterns drastically, that's why it is called only once and only for highlighting.
   * Usually, it tries to expand for cases like in {@link ReduceResult#reduceRecordPatterns(PsiElement, ReduceCache)}
   * The idea is to choose sealed types from q0,...,qn deconstruction components, find their inheritances and add patterns with
   * (q0,...,inheritance,...,qn) components
   * Inheritance must be only on a sealed path
   * This behavior was changed in javac.
   * According to jep, it is not clear what is the correct behavior.
   *
   * @return a new ReduceResult with expanded sealed types
   */
  private static @NotNull ReduceResult unwrapSealedTypes(@NotNull Set<? extends PatternDescriptor> existedPatterns,
                                                         @NotNull ReduceCache cache) {
    Set<PatternDescriptor> result = new HashSet<>(existedPatterns);
    if (existedPatterns.isEmpty()) return new ReduceResult(result, false);
    List<PatternDeconstructionDescriptor> deconstructionExistedPatterns =
      ContainerUtil.filterIsInstance(existedPatterns, PatternDeconstructionDescriptor.class);
    if (deconstructionExistedPatterns.isEmpty()) return new ReduceResult(result, false);
    ReduceUnwrapContext cacheContext = new ReduceUnwrapContext(new HashSet<>(deconstructionExistedPatterns));
    ReduceResult cachedResult = cache.unwrapCache().get(cacheContext);
    if (cachedResult != null) {
      return new ReduceResult(cachedResult.patterns(), cachedResult.patterns().size() != existedPatterns.size());
    }

    Map<PsiType, Set<PatternDeconstructionDescriptor>> deconstructionPatternsByType =
      StreamEx.of(deconstructionExistedPatterns)
        .groupingBy(t -> t.type(), Collectors.toSet());

    for (Set<PatternDeconstructionDescriptor> deconstructionExistedPatternWithTheSameType : deconstructionPatternsByType.values()) {
      for (PatternDeconstructionDescriptor basePattern : deconstructionExistedPatternWithTheSameType) {
        List<? extends PatternDescriptor> patternDescriptions = basePattern.list();
        for (int i = 0; i < patternDescriptions.size(); i++) {
          PatternDescriptor baseDescription = patternDescriptions.get(i);
          if (!(baseDescription instanceof PatternTypeTestDescriptor(PsiType baseType, PsiClass baseClass))) continue;
          if (baseClass == null) continue;
          if (!JavaPsiSealedUtil.isAbstractSealed(baseClass)) continue;
          for (PatternDeconstructionDescriptor comparedPattern : deconstructionExistedPatternWithTheSameType) {
            if (comparedPattern == basePattern) continue;
            if (!comparedPattern.type().equals(basePattern.type())) continue;
            if (comparedPattern.list().size() != patternDescriptions.size()) continue;
            PatternDescriptor comparedDescription = comparedPattern.list().get(i);
            if (!(comparedDescription instanceof PatternTypeTestDescriptor(PsiType cmpType, PsiClass cmpClass))) continue;
            if (cmpClass == null) continue;
            if (baseClass.getManager().areElementsEquivalent(baseClass, cmpClass)) continue;
            if (!baseType.isAssignableFrom(cmpType)) continue;
            if (!isDirectSealedPath(cmpClass, baseClass, cache, new HashSet<>())) {
              continue;
            }
            result.addAll(createPatternsFrom(i, Set.of(comparedDescription), basePattern));
          }
        }
      }
    }
    ReduceResult reduceResult = new ReduceResult(result, result.size() != existedPatterns.size());
    cache.unwrapCache().put(cacheContext, reduceResult);
    ReduceUnwrapContext newContext =
      new ReduceUnwrapContext(StreamEx.of(reduceResult.patterns()).select(PatternDeconstructionDescriptor.class).toSet());
    cache.unwrapCache().put(newContext, reduceResult);
    return reduceResult;
  }

  private static boolean isDirectSealedPath(@Nullable PsiClass from,
                                            @Nullable PsiClass to,
                                            @NotNull ReduceCache cache,
                                            @NotNull Set<PsiClass> visited) {
    if (from == null || to == null) return false;
    Map<PsiClass, Boolean> toCache = cache.sealedPath().get(from);
    if (toCache != null) {
      Boolean isSealedPath = toCache.get(to);
      if (isSealedPath != null) return isSealedPath;
    }
    if (!visited.add(from)) return false;
    if (from.getManager().areElementsEquivalent(from, to)) {
      boolean result = JavaPsiSealedUtil.isAbstractSealed(to);
      addToSealedCache(from, to, cache, result);
      return result;
    }
    if (!from.isInheritor(to, true)) {
      boolean result = false;
      addToSealedCache(from, to, cache, result);
      return result;
    }
    boolean result = ContainerUtil.exists(from.getSupers(),
                                          superClass -> JavaPsiSealedUtil.isAbstractSealed(superClass) &&
                                                        isDirectSealedPath(superClass, to, cache, visited));
    addToSealedCache(from, to, cache, result);
    return result;
  }

  private static void addToSealedCache(@Nullable PsiClass from,
                                       @Nullable PsiClass to,
                                       @NotNull ReduceCache cache,
                                       boolean result) {
    cache.sealedPath().computeIfAbsent(from, k -> new HashMap<>()).put(to, result);
  }

  private static @NotNull Set<PatternDeconstructionDescriptor> getDeconstructionPatternOnlyWithTestPatterns(Set<PatternDeconstructionDescriptor> descriptions) {
    Set<PatternDeconstructionDescriptor> filtered = new HashSet<>();
    for (PatternDeconstructionDescriptor description : descriptions) {
      if (ContainerUtil.and(description.list(), t -> t instanceof PatternTypeTestDescriptor)) {
        filtered.add(description);
      }
    }
    return filtered;
  }

  private static @Nullable @Unmodifiable List<PsiType> getComponentTypes(@NotNull PsiElement context, @NotNull PsiType type) {
    return CachedValuesManager.getCachedValue(context, () -> {
      Map<PsiType, List<PsiType>> result = ConcurrentFactoryMap.createMap(descriptionType -> {
        PsiType capturedToplevel = PsiUtil.captureToplevelWildcards(descriptionType, context);
        PsiClassType.ClassResolveResult resolve = PsiUtil.resolveGenericsClassInType(capturedToplevel);
        PsiClass selectorClass = resolve.getElement();
        PsiSubstitutor substitutor = resolve.getSubstitutor();
        if (selectorClass == null) return null;
        return ContainerUtil.map(selectorClass.getRecordComponents(), component -> substitutor.substitute(component.getType()));
      });
      return CachedValueProvider.Result.create(result, PsiModificationTracker.MODIFICATION_COUNT);
    }).get(type);
  }

  private static @NotNull Collection<PatternDeconstructionDescriptor> createPatternsFrom(int differentElement,
                                                                                         @NotNull Set<? extends PatternDescriptor> nestedPatterns,
                                                                                         @NotNull PatternDeconstructionDescriptor sample) {
    HashSet<PatternDeconstructionDescriptor> descriptions = new HashSet<>();
    for (PatternDescriptor nestedPattern : nestedPatterns) {
      descriptions.add(sample.createFor(differentElement, nestedPattern));
    }
    return descriptions;
  }

  private static boolean oneOfUnconditional(@NotNull PsiElement context,
                                            @NotNull PatternDeconstructionDescriptor whoType,
                                            @NotNull PatternDeconstructionDescriptor overWhom) {
    if (!whoType.type().equals(overWhom.type())) {
      return false;
    }
    if (whoType.list().size() != overWhom.list().size()) {
      return false;
    }
    for (int i = 0; i < whoType.list().size(); i++) {
      if (!JavaPsiPatternUtil.covers(context, whoType.list().get(i).type(), overWhom.list().get(i).type())) {
        return false;
      }
    }
    return true;
  }

  private static boolean coverSelectorType(@NotNull PsiElement context,
                                           @NotNull Set<? extends PatternDescriptor> patterns,
                                           @NotNull PsiType selectorType) {
    for (PatternDescriptor pattern : patterns) {
      if (pattern instanceof PatternTypeTestDescriptor &&
          JavaPsiPatternUtil.covers(context, pattern.type(), selectorType)) {
        return true;
      }
    }
    return false;
  }

  /**
   * Tries all types of reductions
   */
  private static @NotNull ReduceResult reduce(@NotNull PsiType selectorType,
                                              @NotNull PsiElement context,
                                              @NotNull Set<? extends PatternDescriptor> currentPatterns,
                                              @NotNull ReduceCache cache) {
    currentPatterns = new HashSet<>(currentPatterns);
    ReduceResultCacheContext cacheContext = new ReduceResultCacheContext(selectorType, currentPatterns);
    ReduceResult result = cache.loopReduceCache().get(cacheContext);
    if (result == null) {
      result = new ReduceResult(currentPatterns, false)
        .reduceRecordPatterns(context, cache)
        .reduceDeconstructionRecordToTypePattern(context)
        .reduceClasses(selectorType, context);
      cache.loopReduceCache().put(cacheContext, result);
    }
    return result;
  }

  /**
   * Reduces a set of patterns in a loop until a stopping condition is met.
   *
   * @param selectorType the type of the selector
   * @param context      the context element
   * @param patterns     the initial set of patterns
   * @param stopAt       a condition that determines if the reduction should stop
   * @param cache        the cache of reduction results
   * @param tryToExpand  a flag indicating whether to try to expand sealed types
   * @return the result of the reduction loop
   */
  private static @NotNull LoopReduceResult reduceInLoop(@NotNull PsiType selectorType,
                                                        @NotNull PsiElement context,
                                                        @NotNull Set<? extends PatternDescriptor> patterns,
                                                        @NotNull BiPredicate<Set<? extends PatternDescriptor>, PsiType> stopAt,
                                                        @NotNull ReduceCache cache, boolean tryToExpand) {
    boolean changed = false;
    int currentIteration = 0;
    Set<? extends PatternDescriptor> currentPatterns = new HashSet<>(patterns);
    boolean tryToExpandNext = tryToExpand;
    while (currentIteration < MAX_ITERATION_COVERAGE) {
      currentIteration++;
      if (stopAt.test(currentPatterns, selectorType)) {
        return new LoopReduceResult(currentPatterns, true, true);
      }
      ReduceResult reduceResult = reduce(selectorType, context, currentPatterns, cache);
      if (tryToExpandNext && !reduceResult.changed() && reduceResult.patterns().size() > 1) {
        reduceResult = unwrapSealedTypes(reduceResult.patterns(), cache);
        tryToExpandNext = false;
      }
      changed |= reduceResult.changed();
      currentPatterns = reduceResult.patterns();
      if (!reduceResult.changed()) {
        return new LoopReduceResult(currentPatterns, changed, false);
      }
    }
    LOG.error("The number of iteration is exceeded, length of set patterns: " + patterns.size() +
              "max length deconstruction: " + patterns.stream()
                .filter(t -> t instanceof PatternDeconstructionDescriptor)
                .map(t -> ((PatternDeconstructionDescriptor)t).list.size())
                .max(Comparator.naturalOrder())
    );
    return new LoopReduceResult(currentPatterns, changed, false);
  }

  private static boolean addNewClasses(@NotNull PsiElement context,
                                       @NotNull PsiType selectorType,
                                       @NotNull Set<PsiClass> visitedCovered,
                                       @NotNull Set<PsiType> existedTypes,
                                       @NotNull Collection<PatternTypeTestDescriptor> toAdd) {
    boolean changed = false;
    for (PsiClass covered : visitedCovered) {
      PsiClassType classType = JavaPsiFacade.getElementFactory(covered.getProject()).createType(covered);
      if (!existedTypes.contains(classType)) {
        if (JavaPsiPatternUtil.covers(context, selectorType, classType)) {
          toAdd.add(new PatternTypeTestDescriptor(classType));
          changed = true;
        }
        //find something upper. let's change to selectorType
        if (JavaPsiPatternUtil.covers(context, classType, selectorType)) {
          toAdd.add(new PatternTypeTestDescriptor(selectorType));
          changed = true;
          break;
        }
      }
    }
    return changed;
  }

  private static @NotNull Set<PatternDescriptor> combineResult(@NotNull Set<? extends PatternDescriptor> patterns,
                                                               Set<? extends PatternDescriptor> toRemove,
                                                               Set<? extends PatternDescriptor> toAdd) {
    Set<PatternDescriptor> result = new HashSet<>();
    for (PatternDescriptor pattern : patterns) {
      if (!toRemove.contains(pattern)) {
        result.add(pattern);
      }
    }
    result.addAll(toAdd);
    return result;
  }

  private static @NotNull MultiMap<PsiClass, PsiType> findPermittedClasses(@NotNull List<PatternTypeTestDescriptor> elements) {
    MultiMap<PsiClass, PsiType> patternClasses = new MultiMap<>();
    for (PatternDescriptor element : elements) {
      PsiType patternType = element.type();
      PsiClass patternClass = PsiUtil.resolveClassInClassTypeOnly(patternType);
      if (patternClass != null) {
        patternClasses.putValue(patternClass, element.type());
        Set<PsiClass> classes = JavaPsiSealedUtil.getAllPermittedClasses(patternClass);
        for (PsiClass aClass : classes) {
          patternClasses.putValue(aClass, element.type());
        }
      }
    }
    return patternClasses;
  }

  private static @NotNull List<PatternTypeTestDescriptor> reduceToTypeTest(@NotNull List<? extends PatternDescriptor> elements,
                                                                            @NotNull PsiElement context) {
    List<PatternTypeTestDescriptor> reducedToTypeTest = new ArrayList<>();
    List<PatternDeconstructionDescriptor> deconstructionDescriptions = new ArrayList<>();
    for (PatternDescriptor element : elements) {
      if (element instanceof PatternTypeTestDescriptor typeTestDescription) {
        reducedToTypeTest.add(typeTestDescription);
      }
      if (element instanceof PatternDeconstructionDescriptor deconstructionDescription) {
        deconstructionDescriptions.add(deconstructionDescription);
      }
    }
    Map<PsiType, List<PatternDeconstructionDescriptor>> groupedByType =
      deconstructionDescriptions.stream().collect(Collectors.groupingBy(t -> t.type()));
    for (Map.Entry<PsiType, List<PatternDeconstructionDescriptor>> entry : groupedByType.entrySet()) {
      if (checkRecordPatternExhaustivenessForDescriptors(entry.getValue(), entry.getKey(), context).isExhaustive()) {
        reducedToTypeTest.add(new PatternTypeTestDescriptor(entry.getKey()));
      }
    }
    return reducedToTypeTest;
  }

  private static @NotNull List<PatternTypeTestDescriptor> reduceEnumConstantsToTypeTest(@NotNull List<PsiEnumConstant> constants) {
    List<PatternTypeTestDescriptor> reducedToTypeTest = new ArrayList<>();
    Map<PsiType, Set<PsiEnumConstant>> enumsByTypes = constants.stream().collect(
      Collectors.groupingBy(t -> t.getType(), Collectors.toUnmodifiableSet()));
    enumsByTypes.forEach((enumType, enumConstants) -> {
      PsiClass enumClass = PsiUtil.resolveClassInClassTypeOnly(enumType);
      if (enumClass != null && !hasMissingEnumConstant(enumClass, enumConstants)) {
        reducedToTypeTest.add(new PatternTypeTestDescriptor(enumType));
      }
    });
    return reducedToTypeTest;
  }

  private static boolean hasMissingEnumConstant(PsiClass enumClass, Set<PsiEnumConstant> covered) {
    for (PsiField field : enumClass.getFields()) {
      if (field instanceof PsiEnumConstant enumConstant && !covered.contains(enumConstant)) {
        return true;
      }
    }
    return false;
  }

  /**
   * Finds the missed and covered classes for a sealed selector type.
   * If a selector type is not sealed classes, it will be checked if it is covered by one of the elements or enumConstants
   *
   * @param block        the switch block
   * @param selectorType the selector type
   * @param elements     case labels from the analyzed switch
   * @return the set of missed classes (may contain classes outside the selector type hierarchy)
   */
  public static @NotNull Set<PsiClass> findMissedClasses(@NotNull PsiSwitchBlock block, 
                                                         @NotNull PsiType selectorType,
                                                         @NotNull List<? extends PsiCaseLabelElement> elements) {
    List<PatternDescriptor> descriptions = preparePatternDescriptors(elements);
    List<PsiEnumConstant> enumConstants = getEnumConstants(elements);
    return findMissedClasses(selectorType, descriptions, enumConstants, block);
  }

  private static @NotNull List<PsiEnumConstant> getEnumConstants(@NotNull List<? extends PsiCaseLabelElement> elements) {
    return StreamEx.of(elements).map(JavaPsiSwitchUtil::getEnumConstant).nonNull().toList();
  }

  /**
   * Finds the missed and covered classes for a sealed selector type.
   * If a selector type is not sealed classes, it will be checked if it is covered by one of the elements or enumConstants
   *
   * @param selectorType  the selector type
   * @param elements      the pattern descriptions, unconditional
   * @param enumConstants the enum constants, which can be used to cover enum classes
   * @param context       the context element (parent of pattern descriptions)
   * @return the set of missed classes (may contain classes outside the selector type hierarchy)
   */
  private static @NotNull Set<PsiClass> findMissedClasses(@NotNull PsiType selectorType,
                                                          @NotNull List<? extends PatternDescriptor> elements,
                                                          @NotNull List<PsiEnumConstant> enumConstants,
                                                          @NotNull PsiElement context) {
    return findMissedClassesData(selectorType, elements, enumConstants, context).missedClasses();
  }

  private static @NotNull SealedResult findMissedClassesData(@NotNull PsiType selectorType,
                                                             @NotNull List<? extends PatternDescriptor> elements,
                                                             @NotNull List<PsiEnumConstant> enumConstants,
                                                             @NotNull PsiElement context) {
    //Used to keep dependencies. The last dependency is one of the selector types.
    record ClassWithDependencies(PsiClass mainClass, List<PsiClass> dependencies) {
    }

    Set<PsiClass> coveredClasses = new HashSet<>();
    Set<PsiClass> visitedNotCovered = new HashSet<>();
    Set<PsiClass> missingClasses = new LinkedHashSet<>();

    //reduce record patterns and enums to TypeTestDescription
    List<PatternTypeTestDescriptor> reducedDescriptions = reduceToTypeTest(elements, context);
    reducedDescriptions.addAll(reduceEnumConstantsToTypeTest(enumConstants));
    MultiMap<PsiClass, PsiType> permittedPatternClasses = findPermittedClasses(reducedDescriptions);
    //according to JEP 440-441, only direct abstract-sealed classes are allowed (14.11.1.1)
    Set<PsiClass> sealedUpperClasses = JavaPsiSealedUtil.findSealedUpperClasses(permittedPatternClasses.keySet());

    List<PatternTypeTestDescriptor> typeTestPatterns = ContainerUtil.filterIsInstance(elements, PatternTypeTestDescriptor.class);

    Set<PsiClass> selectorClasses = ContainerUtil.map2SetNotNull(JavaPsiPatternUtil.deconstructSelectorType(selectorType),
