// Copyright 2000-2018 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license that can be found in the LICENSE file.
package com.jetbrains.python.psi.types;

import com.intellij.openapi.util.*;
import com.intellij.psi.PsiElement;
import com.intellij.psi.PsiFile;
import com.intellij.psi.PsiNamedElement;
import com.intellij.util.ArrayUtil;
import com.intellij.util.containers.ContainerUtil;
import com.jetbrains.python.PyNames;
import com.jetbrains.python.PyNamesKt;
import com.jetbrains.python.PythonRuntimeService;
import com.jetbrains.python.ast.PyAstFunction;
import com.jetbrains.python.codeInsight.dataflow.scope.ScopeUtil;
import com.jetbrains.python.codeInsight.typing.PyProtocolsKt;
import com.jetbrains.python.codeInsight.typing.PyTypingTypeProvider;
import com.jetbrains.python.psi.*;
import com.jetbrains.python.psi.impl.ParamHelper;
import com.jetbrains.python.psi.impl.PyBuiltinCache;
import com.jetbrains.python.psi.impl.PyPsiUtils;
import com.jetbrains.python.psi.impl.PyTypeProvider;
import com.jetbrains.python.psi.resolve.PyResolveContext;
import com.jetbrains.python.psi.resolve.RatedResolveResult;
import com.jetbrains.python.psi.types.PyRecursiveTypeVisitor.PyTypeTraverser;
import com.jetbrains.python.psi.types.PyRecursiveTypeVisitor.Traversal;
import com.jetbrains.python.psi.types.PyTypeParameterMapping.Option;
import com.jetbrains.python.pyi.PyiFile;
import com.jetbrains.python.sdk.legacy.PythonSdkUtil;
import one.util.streamex.EntryStream;
import one.util.streamex.IntStreamEx;
import one.util.streamex.StreamEx;
import org.jetbrains.annotations.ApiStatus;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;

import java.util.*;

import static com.jetbrains.python.PyNames.FUNCTION;
import static com.jetbrains.python.psi.PyUtil.*;
import static com.jetbrains.python.psi.impl.PyCallExpressionHelper.*;

public final class PyTypeChecker {
  private PyTypeChecker() {
  }

  /**
   * See {@link PyTypeChecker#match(PyType, PyType, TypeEvalContext, Map)} for description.
   */
  public static boolean match(@Nullable PyType expected, @Nullable PyType actual, @NotNull TypeEvalContext context) {
    @NotNull GenericSubstitutions substitutions = new GenericSubstitutions();
    return match(expected, actual, new MatchContext(context, substitutions, false)).orElse(true);
  }

  /**
   * Checks whether a type {@code actual} can be placed where {@code expected} is expected.
   * <p>
   * For example {@code int} matches {@code object}, while {@code str} doesn't match {@code int}.
   * Work for builtin types, classes, tuples etc.
   * <p>
   * Whether it's unknown if {@code actual} match {@code expected} the method returns {@code true}.
   *
   * @param expected      expected type
   * @param actual        type to be matched against expected
   * @param context       type evaluation context
   * @param substitutions map of substitutions for {@code expected} type
   * @return {@code false} if {@code expected} and {@code actual} don't match, true otherwise
   * @implNote This behavior may be changed in future by replacing {@code boolean} with {@code Optional<Boolean>} and updating the clients.
   */
  public static boolean match(@Nullable PyType expected,
                              @Nullable PyType actual,
                              @NotNull TypeEvalContext context,
                              @NotNull Map<? extends PyTypeParameterType, PyType> typeVars) {
    var substitutions = new GenericSubstitutions(typeVars);
    return match(expected, actual, new MatchContext(context, substitutions, false)).orElse(true);
  }

  public static boolean match(@Nullable PyType expected,
                              @Nullable PyType actual,
                              @NotNull TypeEvalContext context,
                              @NotNull GenericSubstitutions substitutions) {
    return match(expected, actual, new MatchContext(context, substitutions, false))
      .orElse(true);
  }

  private static @NotNull Optional<Boolean> match(@Nullable PyType expected, @Nullable PyType actual, @NotNull MatchContext context) {
    final Optional<Boolean> result = RecursionManager.doPreventingRecursion(
      Pair.create(expected, actual),
      false,
      () -> matchImpl(expected, actual, context)
    );

    return result == null ? Optional.of(true) : result;
  }

  /**
   * Perform type matching.
   * <p>
   * Implementation details:
   * <ul>
   *  <li>The method mutates {@code context.substitutions} map adding new entries into it
   *  <li>The order of match subroutine calls is important
   *  <li>The method may recursively call itself
   * </ul>
   */
  private static @NotNull Optional<Boolean> matchImpl(@Nullable PyType expected, @Nullable PyType actual, @NotNull MatchContext context) {
    if (Objects.equals(expected, actual)) {
      return Optional.of(true);
    }

    for (PyTypeCheckerExtension extension : PyTypeCheckerExtension.EP_NAME.getExtensionList()) {
      final Optional<Boolean> result = extension.match(expected, actual, context.context, context.mySubstitutions);
      if (result.isPresent()) {
        return result;
      }
    }

    if (expected instanceof PyClassType) {
      Optional<Boolean> match = matchObject((PyClassType)expected, actual);
      if (match.isPresent()) {
        return match;
      }
    }

    if (actual instanceof PyNarrowedType actualNarrowedType && expected instanceof PyNarrowedType expectedNarrowedType) {
      return match(expectedNarrowedType, actualNarrowedType, context);
    }

    if (actual instanceof PyTypeVarTupleType typeVarTupleType && context.reversedSubstitutions) {
      return Optional.of(match(typeVarTupleType, expected, context));
    }

    if (expected instanceof PyPositionalVariadicType variadic) {
      return Optional.of(match(variadic, actual, context));
    }

    if (actual instanceof PyTypeVarType typeVarType && context.reversedSubstitutions) {
      return Optional.of(match(typeVarType, expected, context));
    }

    if (expected instanceof PyTypeVarType typeVarType) {
      return Optional.of(match(typeVarType, actual, context));
    }

    if (expected instanceof PySelfType selfType) {
      return Optional.of(match(selfType, actual, context));
    }

    if (actual instanceof PySelfType selfType && context.reversedSubstitutions) {
      return Optional.of(match(selfType, expected, context));
    }

    if (expected instanceof PyParamSpecType paramSpecType) {
      return Optional.of(match(paramSpecType, actual, context));
    }

    if (expected instanceof PyConcatenateType concatenateType) {
      return Optional.of(match(concatenateType, actual, context));
    }

    if (expected == null || actual == null || isUnknown(actual, context.context)) {
      return Optional.of(true);
    }

    if (expected instanceof PyCallableParameterListType callableParameterListType) {
      return Optional.of(match(callableParameterListType, actual, context));
    }

    if (actual instanceof PyNeverType) {
      return Optional.of(true);
    }

    if (expected instanceof PyNeverType) {
      return Optional.of(false);
    }

    if (actual instanceof PyUnionType) {
      return Optional.of(match(expected, (PyUnionType)actual, context));
    }

    if (expected instanceof PyUnionType) {
      return Optional.of(match((PyUnionType)expected, actual, context));
    }

    if (actual instanceof PyUnsafeUnionType weakUnionType) {
      return Optional.of(match(expected, weakUnionType, context));
    }

    if (expected instanceof PyUnsafeUnionType weakUnionType) {
      return Optional.of(match(weakUnionType, actual, context));
    }

    if (expected instanceof PyClassType && actual instanceof PyClassType) {
      Optional<Boolean> match = match((PyClassType)expected, (PyClassType)actual, context);
      if (match.isPresent()) {
        return match;
      }
    }

    if (actual instanceof PyStructuralType && ((PyStructuralType)actual).isInferredFromUsages()) {
      return Optional.of(true);
    }

    if (expected instanceof PyStructuralType) {
      return Optional.of(match((PyStructuralType)expected, actual, context.context));
    }

    if (actual instanceof PyStructuralType && expected instanceof PyClassType) {
      final Set<String> expectedAttributes = ((PyClassType)expected).getMemberNames(true, context.context);
      return Optional.of(expectedAttributes.containsAll(((PyStructuralType)actual).getAttributeNames()));
    }

    if (actual instanceof PyCallableType actualCallable && expected instanceof PyCallableType expectedCallable) {
      final Optional<Boolean> match = match(expectedCallable, actualCallable, context);
      if (match.isPresent()) {
        return match;
      }
    }

    if (expected instanceof PyModuleType) {
      return Optional.of(actual instanceof PyModuleType && ((PyModuleType)expected).getModule() == ((PyModuleType)actual).getModule());
    }

    if (expected instanceof PyClassType classType && actual instanceof PyModuleType moduleType) {
      if (PyProtocolsKt.isProtocol(classType, context.context)) {
        return Optional.of(match(classType, moduleType, context));
      }
      return match(expected, moduleType.getModuleClassType(), context);
    }

    return Optional.of(matchNumericTypes(expected, actual));
  }

  private static @NotNull Optional<Boolean> match(PyNarrowedType expectedNarrowedType,
                                                  PyNarrowedType actualNarrowedType,
                                                  @NotNull MatchContext context) {
    if (expectedNarrowedType.getTypeIs() != actualNarrowedType.getTypeIs()) {
      return Optional.of(false);
    }
    if (expectedNarrowedType.getTypeIs()) {
      return Optional.of(Objects.equals(expectedNarrowedType.getNarrowedType(), actualNarrowedType.getNarrowedType()));
    }
    return match(expectedNarrowedType.getNarrowedType(), actualNarrowedType.getNarrowedType(), context);
  }

  /**
   * Check whether {@code expected} is Python *object* or *type*.
   * <p>
   * {@see PyTypeChecker#match(PyType, PyType, TypeEvalContext, Map)}
   */
  private static @NotNull Optional<Boolean> matchObject(@NotNull PyClassType expected, @Nullable PyType actual) {
    if (ArrayUtil.contains(expected.getName(), PyNames.OBJECT, PyNames.TYPE)) {
      final PyBuiltinCache builtinCache = PyBuiltinCache.getInstance(expected.getPyClass());
      if (expected.equals(builtinCache.getObjectType())) {
        return Optional.of(true);
      }
      if (expected.equals(builtinCache.getTypeType()) &&
          actual instanceof PyInstantiableType && ((PyInstantiableType<?>)actual).isDefinition()) {
        return Optional.of(true);
      }
    }
    return Optional.empty();
  }

  /**
   * Match {@code actual} versus {@link PyTypeVarType} expected.
   * <p>
   * The method mutates {@code context.substitutions} map adding new entries into it
   */
  private static boolean match(@NotNull PyTypeVarType expected, @Nullable PyType actual, @NotNull MatchContext context) {
    if (expected.isDefinition() && actual instanceof PyInstantiableType && !((PyInstantiableType<?>)actual).isDefinition()) {
      return false;
    }

    Ref<PyType> substitutedRef = context.mySubstitutions.typeVars.get(expected);
    Ref<? extends PyType> defaultTypeRef = expected.getDefaultType();
    if (defaultTypeRef != null) {
      PyType defaultType = defaultTypeRef.get();
      // Skip default substitution
      if (defaultType != null && defaultType.equals(Ref.deref(substitutedRef))) {
        substitutedRef = null;
      }
    }
    PyType bound = expected.getBound();
    List<@Nullable PyType> constraints = expected.getConstraints();
    // Promote int in Type[TypeVar('T', int)] to Type[int] before checking that bounds match
    if (expected.isDefinition()) {
      bound = toClass(bound);
      constraints = ContainerUtil.map(constraints, PyTypeChecker::toClass);
    }

    // Remove value-specific components from the actual type to make it safe to propagate
    PyType safeActual = constraints.isEmpty() && bound instanceof PyLiteralStringType ? actual : replaceLiteralStringWithStr(actual);

    if (substitutedRef != null) {
      final PyType substitution = substitutedRef.get();
      if (expected.equals(safeActual) || expected.equals(substitution)) {
        return true;
      }

      MyMatchHelper matchHelper = new MyMatchHelper(expected, context);
      if (matchHelper.match(substitution, safeActual)) {
        return true;
      }
      if (context.mySubstitutions.frozenTypeVars.contains(expected)) {
        return false;
      }
      if (!matchHelper.match(safeActual, substitution)) {
        safeActual = PyUnionType.union(safeActual, substitution);
      }
    }

    int matchedConstraintIndex = -1;
    if (constraints.isEmpty()) {
      Optional<Boolean> match = match(bound, safeActual, context);
      if (match.isPresent() && !match.get()) {
        return false;
      }
    }
    else {
      final PyType finalSafeActual = safeActual;
      matchedConstraintIndex = ContainerUtil.indexOf(constraints, constraint -> match(constraint, finalSafeActual, context).orElse(true));
      if (matchedConstraintIndex == -1) {
        return false;
      }
    }

    if (safeActual != null) {
      PyType type = constraints.isEmpty() ? safeActual : constraints.get(matchedConstraintIndex);
      context.mySubstitutions.typeVars.put(expected, Ref.create(type));
    }
    else {
      PyType effectiveBound = PyTypeUtil.getEffectiveBound(expected);
      if (effectiveBound != null) {
        context.mySubstitutions.typeVars.put(expected, Ref.create(PyUnionType.createWeakType(effectiveBound)));
      }
    }

    return true;
  }

  private static final class MyMatchHelper {
    private final @NotNull Object myKey;
    private final @NotNull MatchContext myContext;

    MyMatchHelper(@NotNull Object key, @NotNull MatchContext context) {
      myKey = key;
      myContext = context;
    }

    boolean match(@Nullable PyType expected, @Nullable PyType actual) {
      Optional<Boolean> result = RecursionManager.doPreventingRecursion(
        myKey, false, myContext.reversedSubstitutions
                      ? () -> PyTypeChecker.match(actual, expected, myContext)
                      : () -> PyTypeChecker.match(expected, actual, myContext)
      );
      return result != null && result.orElse(false);
    }
  }

  private static boolean match(@NotNull PySelfType expected, @Nullable PyType actual, @NotNull MatchContext context) {
    if (actual == null) return true;
    PyType substitution = context.mySubstitutions.getQualifierType();
    if (substitution != null && !(substitution instanceof PySelfType)) {
      return match(substitution, actual, context).orElse(false);
    }
    if (!(actual instanceof PySelfType actualSelf)) return false;
    return expected.isDefinition() == actualSelf.isDefinition() &&
           match(expected.getScopeClassType(), actualSelf.getScopeClassType(), context).orElse(false);
  }

  private static @Nullable PyType toClass(@Nullable PyType type) {
    return PyTypeUtil.toStream(type)
      .map(t -> t instanceof PyInstantiableType<?> instantiableType ? instantiableType.toClass() : t)
      .collect(PyTypeUtil.toUnion(type));
  }

  private static boolean match(@NotNull PyPositionalVariadicType expected, @Nullable PyType actual, @NotNull MatchContext context) {
    if (actual == null) {
      return true;
    }
    if (!(actual instanceof PyPositionalVariadicType actualVariadic)) {
      return false;
    }
    if (expected instanceof PyUnpackedTupleType expectedUnpackedTupleType) {
      // The actual type is just a TypeVarTuple
      if (!(actualVariadic instanceof PyUnpackedTupleType actualUnpackedTupleType)) {
        return false;
      }
      if (expectedUnpackedTupleType.isUnbound()) {
        PyType repeatedExpectedType = expectedUnpackedTupleType.getElementTypes().get(0);
        if (actualUnpackedTupleType.isUnbound()) {
          return match(repeatedExpectedType, actualUnpackedTupleType.getElementTypes().get(0), context).orElse(false);
        }
        else {
          return ContainerUtil.all(actualUnpackedTupleType.getElementTypes(),
                                   singleActualType -> match(repeatedExpectedType, singleActualType, context).orElse(false));
        }
      }
      else {
        if (actualUnpackedTupleType.isUnbound()) {
          PyType repeatedActualType = actualUnpackedTupleType.getElementTypes().get(0);
          return ContainerUtil.all(expectedUnpackedTupleType.getElementTypes(),
                                   singleExpectedType -> match(singleExpectedType, repeatedActualType, context).orElse(false));
        }
        else {
          return matchTypeParameters(expectedUnpackedTupleType.getElementTypes(), actualUnpackedTupleType.getElementTypes(), context);
        }
      }
    }
    // The expected type is just a TypeVarTuple
    else {
      PyPositionalVariadicType substitution = context.mySubstitutions.typeVarTuples.get(expected);
      if (substitution != null && !substitution.equals(PyUnpackedTupleTypeImpl.UNSPECIFIED)) {
        if (expected.equals(actual) || substitution.equals(expected)) {
          return true;
        }
        return context.reversedSubstitutions ? match(actualVariadic, substitution, context) : match(substitution, actualVariadic, context);
      }
      context.mySubstitutions.typeVarTuples.put((PyTypeVarTupleType)expected, actualVariadic);
    }
    return true;
  }

  private static @Nullable PyType replaceLiteralStringWithStr(@Nullable PyType actual) {
    // TODO replace with PyTypeVisitor API once it's ready
    if (actual instanceof PyLiteralStringType literalStringType) {
      return new PyClassTypeImpl(literalStringType.getPyClass(), false);
    }
    if (actual instanceof PyUnionType unionType) {
      return unionType.map(PyTypeChecker::replaceLiteralStringWithStr);
    }
    if (actual instanceof PyNamedTupleType) {
      return actual;
    }
    if (actual instanceof PyTupleType tupleType) {
      return new PyTupleType(tupleType.getPyClass(),
                             ContainerUtil.map(tupleType.getElementTypes(), PyTypeChecker::replaceLiteralStringWithStr),
                             tupleType.isHomogeneous(), tupleType.isDefinition());
    }
    if (actual instanceof PyCollectionType generic) {
      return new PyCollectionTypeImpl(generic.getPyClass(), generic.isDefinition(),
                                      ContainerUtil.map(generic.getElementTypes(), PyTypeChecker::replaceLiteralStringWithStr));
    }
    return actual;
  }

  private static boolean match(@NotNull PyParamSpecType expected, @Nullable PyType actual, @NotNull MatchContext context) {
    if (actual == null) return true;
    if (!(actual instanceof PyCallableParameterVariadicType actualParameters)) return false;
    context.mySubstitutions.paramSpecs.put(expected, actualParameters);
    return true;
  }

  private static boolean match(@NotNull PyConcatenateType expected, @Nullable PyType actual, @NotNull MatchContext context) {
    if (actual == null) return true;
    List<PyType> expectedFirstTypes = expected.getFirstTypes();
    int expectedPrefixSize = expectedFirstTypes.size();
    PyParamSpecType expectedParamSpec = expected.getParamSpec();
    if (actual instanceof PyConcatenateType actualConcatenateType) {
      if (expectedPrefixSize > actualConcatenateType.getFirstTypes().size()) {
        return false;
      }
      List<PyType> actualFirstTypes = actualConcatenateType.getFirstTypes().subList(0, expectedPrefixSize);
      if (!match(expectedFirstTypes, actualFirstTypes, context)) {
        return false;
      }
      if (expectedParamSpec == null) {
        return true;
      }
      if (actualFirstTypes.size() > expectedPrefixSize) {
        return match(expectedParamSpec,
                     new PyConcatenateType(ContainerUtil.subList(expectedFirstTypes, actualFirstTypes.size()),
                                           actualConcatenateType.getParamSpec()), context);
      }
      else {
        return match(expectedParamSpec, actualConcatenateType.getParamSpec(), context);
      }
    }
    else if (actual instanceof PyCallableParameterListType actualParameters) {
      if (expectedPrefixSize > actualParameters.getParameters().size()) {
        return false;
      }
      List<PyType> actualFirstParamTypes = ContainerUtil.map(actualParameters.getParameters().subList(0, expectedPrefixSize),
                                                             it -> it.getType(context.context));
      if (!match(expectedFirstTypes, actualFirstParamTypes, context)) {
        return false;
      }
      if (expectedParamSpec == null) {
        return true;
      }
      return match(expectedParamSpec,
                   new PyCallableParameterListTypeImpl(ContainerUtil.subList(actualParameters.getParameters(), expectedPrefixSize)),
                   context);
    }
    return false;
  }

  private static boolean match(@NotNull PyCallableParameterListType expectedParameters,
                               @Nullable PyType actual,
                               @NotNull MatchContext context) {
    if (actual == null) return true;
    if (!(actual instanceof PyCallableParameterListType actualParameters)) return false;
    return matchCallableParameters(expectedParameters.getParameters(), actualParameters.getParameters(), context);
  }

  private static boolean match(@NotNull PyType expected, @NotNull PyUnionType actual, @NotNull MatchContext context) {
    if (expected instanceof PyTupleType expectedTupleType) {
      // XXX A type-widening hack for cases like PyTypeTest.testDictFromTuple
      Optional<Boolean> match = match(expectedTupleType, actual, context);
      if (match.isPresent()) {
        return match.get();
      }
    }

    if (!PyUnionType.isStrictSemanticsEnabled()) {// checking strictly separately until PY-24834 gets implemented
      if (ContainerUtil.exists(actual.getMembers(), x -> x instanceof PyLiteralStringType || x instanceof PyLiteralType)) {
        return ContainerUtil.and(actual.getMembers(), type -> match(expected, type, context).orElse(false));
      }
      return ContainerUtil.or(actual.getMembers(), type -> match(expected, type, context).orElse(false));
    }
    return ContainerUtil.and(actual.getMembers(), type -> match(expected, type, context).orElse(false));
  }

  private static boolean match(@NotNull PyType expected, @NotNull PyUnsafeUnionType actual, @NotNull MatchContext context) {
    return ContainerUtil.or(actual.getMembers(), type -> match(expected, type, context).orElse(false));
  }

  private static @NotNull Optional<Boolean> match(@NotNull PyTupleType expected,
                                                  @NotNull PyUnionType actual,
                                                  @NotNull MatchContext context) {
    final int elementCount = expected.getElementCount();

    if (!expected.isHomogeneous()) {
      PyTupleType widenedActual = widenUnionOfTuplesToTupleOfUnions(actual, elementCount);
      if (widenedActual != null) {
        return match(expected, widenedActual, context);
      }
    }

    return Optional.empty();
  }

  private static boolean match(@NotNull PyUnionType expected, @NotNull PyType actual, @NotNull MatchContext context) {
    if (expected.getMembers().contains(actual)) {
      return true;
    }
    return ContainerUtil.or(expected.getMembers(), type -> match(type, actual, context).orElse(true));
  }

  private static boolean match(@NotNull PyUnsafeUnionType expected, @NotNull PyType actual, @NotNull MatchContext context) {
    if (expected.getMembers().contains(actual)) {
      return true;
    }
    return ContainerUtil.or(expected.getMembers(), type -> match(type, actual, context).orElse(true));
  }

  private static @NotNull Optional<Boolean> match(@NotNull PyClassType expected,
                                                  @NotNull PyClassType actual,
                                                  @NotNull MatchContext matchContext) {
    if (expected.equals(actual)) {
      return Optional.of(true);
    }

    final TypeEvalContext context = matchContext.context;

    if (expected.isDefinition() ^ actual.isDefinition() && !PyProtocolsKt.isProtocol(expected, context)) {
      if (!expected.isDefinition() && actual.isDefinition()) {
        final PyClassLikeType metaClass = actual.getMetaClassType(context, true);
        return Optional.of(metaClass != null && match((PyType)expected, metaClass.toInstance(), matchContext).orElse(true));
      }
      return Optional.of(false);
    }

    if (expected instanceof PyTupleType && actual instanceof PyTupleType) {
      return match((PyTupleType)expected, (PyTupleType)actual, matchContext);
    }

    if (expected instanceof PyLiteralType) {
      return Optional.of(actual instanceof PyLiteralType && PyLiteralType.Companion.match((PyLiteralType)expected, (PyLiteralType)actual));
    }

    if (expected instanceof PyTypedDictType && !(actual instanceof PyTypedDictType)) {
      return Optional.of(false);
    }

    if (actual instanceof PyTypedDictType typedDictType) {
      final Boolean matchResult = PyTypedDictType.match(expected, typedDictType, context);
      if (matchResult != null) return Optional.of(matchResult);
    }

    if (expected instanceof PyLiteralStringType) {
      return Optional.of(PyLiteralStringType.Companion.match((PyLiteralStringType)expected, actual));
    }

    final PyClass superClass = expected.getPyClass();
    final PyClass subClass = actual.getPyClass();

    if (!subClass.isSubclass(superClass, context) && PyProtocolsKt.isProtocol(expected, context)) {
      return Optional.of(matchProtocols(expected, actual, matchContext));
    }

    if (expected instanceof PyCollectionType) {
      return Optional.of(match((PyCollectionType)expected, actual, matchContext));
    }

    if (matchClasses(superClass, subClass, context)) {
      if (expected instanceof PyTypingNewType && !expected.equals(actual) && superClass.equals(subClass)) {
        return Optional.of(actual.getAncestorTypes(context).contains(expected));
      }
      return Optional.of(true);
    }
    return Optional.empty();
  }

  private static boolean matchProtocols(@NotNull PyClassType expected, @NotNull PyClassType actual, @NotNull MatchContext matchContext) {
    GenericSubstitutions expectedSubstitutions = collectTypeSubstitutions(expected, matchContext.context);
    GenericSubstitutions actualSubstitutions = collectTypeSubstitutions(actual, matchContext.context);


    // See https://typing.python.org/en/latest/spec/generics.html#use-in-protocols
    // > If a protocol uses Self in methods or attribute annotations, then a class Foo is assignable to the protocol
    //   if its corresponding methods and attribute annotations use either Self or Foo or any of Foo’s subclasses.
    //
    // It should be equivalent to replacing Self in the protocol with the Foo class we're matching it with.
    GenericSubstitutions protocolSubstitutions = new GenericSubstitutions();
    protocolSubstitutions.qualifierType = actual.toInstance();
    MatchContext protocolContext =
      new MatchContext(matchContext.context, protocolSubstitutions, matchContext.reversedSubstitutions);
    for (kotlin.Pair<PyTypeMember, List<PyTypeMember>> pair : PyProtocolsKt.inspectProtocolSubclass(expected, actual,
                                                                                                    matchContext.context)) {
      final PyTypeMember protocolMember = pair.getFirst();
      final List<PyTypeMember> subclassElementMembers = pair.getSecond();
      if (ContainerUtil.isEmpty(subclassElementMembers)) {
        return false;
      }

      final PyType rawProtocolElementType =
        dropSelfIfNeeded(expected, protocolMember.getType(), matchContext.context);

      final PyType protocolElementType = substitute(rawProtocolElementType, expectedSubstitutions, matchContext.context);
      final boolean elementResult = ContainerUtil.exists(subclassElementMembers, subclassElementMember -> {
        if (protocolMember.isWritable() && !subclassElementMember.isWritable()) {
          return false;
        }
        if (protocolMember.isDeletable() && !subclassElementMember.isDeletable()) {
          return false;
        }
        boolean isProtocolMemberClassVar = protocolMember.isClassVar();
        boolean isSubclassMemberClassVar = subclassElementMember.isClassVar();
        if (isSubclassMemberClassVar != isProtocolMemberClassVar) {
          return false;
        }

        PyType subclassElementType = dropSelfIfNeeded(actual, subclassElementMember.getType(), matchContext.context);
        subclassElementType = substitute(subclassElementType, actualSubstitutions, matchContext.context);

        return match(protocolElementType, subclassElementType, protocolContext).orElse(true);
      });

      if (!elementResult) {
        return false;
      }
    }


    if (expected instanceof PyCollectionType genericExpected && hasGenerics(expected, matchContext.context)) {
      PyCollectionType concreteExpected =
        (PyCollectionType)substitute(expected, protocolContext.mySubstitutions, protocolContext.context);
      assert concreteExpected != null;
      // This match is supposed to succeed since all protocol members were compatible. 
      // Effectively, we're just copying substitutions for the terminal type parameters e.g.
      // extracting: T@func -> str 
      // from: Iterable[T@func] <- Iterable[str]
      return matchGenericClassesParameterWise(genericExpected, concreteExpected, matchContext);
    }

    return true;
  }

  private static boolean match(PyClassType expectedProtocol, PyModuleType actualModule, MatchContext matchContext) {
    PyFile module = actualModule.getModule();

    Map<String, PyTypedElement> moduleElements =
      StreamEx.of(ContainerUtil.concat(module.getTopLevelAttributes(), module.getTopLevelFunctions()))
        .filter(e -> {
          var name = ((PyQualifiedNameOwner)e).getName();
          return name != null && !PyNamesKt.isPrivate(name) && !PyNamesKt.isProtected(name);
        })
        .toMap(PyTypedElement::getName, v -> v);

    var protocolElements = PyProtocolsKt.inspectProtocolSubclass(expectedProtocol, expectedProtocol, matchContext.context);

    if (protocolElements.size() != moduleElements.size()) return false;

    GenericSubstitutions substitutions = collectTypeSubstitutions(expectedProtocol, matchContext.context);
    for (kotlin.Pair<PyTypeMember, List<PyTypeMember>> pair : protocolElements) {
      PsiElement pm = pair.getFirst().getElement();
      if (!(pm instanceof PsiNamedElement protocolMember)) {
        continue;
      }
      String name = protocolMember.getName();
      PyTypedElement moduleElement = moduleElements.get(name);
      if (moduleElement != null) {
        PyType expectedProtocolMemberType =
          substitute(dropSelfIfNeeded(expectedProtocol, pair.getFirst().getType(), matchContext.context), substitutions,
                     matchContext.context);
        PyType actualModuleElementType = matchContext.context.getType(moduleElement);
        if (!match(expectedProtocolMemberType, actualModuleElementType, matchContext.context)) {
          return false;
        }
        continue;
      }
      return false;
    }
    return true;
  }

  private static @Nullable PyType dropSelfIfNeeded(@NotNull PyClassType classType,
                                                   @Nullable PyType elementType,
                                                   @NotNull TypeEvalContext context) {
    if (elementType instanceof PyCallableType callableType) {
      if (PyUtil.isInitOrNewMethod(callableType.getCallable()) || !classType.isDefinition()) {
        return callableType.dropSelf(context);
      }
    }
    return elementType;
  }

  // https://typing.python.org/en/latest/spec/tuples.html#type-compatibility-rules
  private static @NotNull Optional<Boolean> match(@NotNull PyTupleType expected,
                                                  @NotNull PyTupleType actual,
                                                  @NotNull MatchContext context) {
    if (actual.isHomogeneous()) {
      // The type tuple[Any, ...] is consistent with any tuple
      final PyType elementType = actual.getIteratedItemType();
      if (elementType == null) {
        return Optional.of(true);
      }
    }
    // TODO Delegate to UnpackedTupleType here, once it's introduced
    if (!expected.isHomogeneous() && !actual.isHomogeneous()) {
      Condition<PyType> isUnbound =
