// Copyright 2000-2017 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.codeInsight.typing;

import com.dynatrace.hash4j.hashing.HashValue128;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
import com.intellij.openapi.util.*;
import com.intellij.psi.PsiComment;
import com.intellij.psi.PsiElement;
import com.intellij.psi.PsiFile;
import com.intellij.psi.impl.source.resolve.FileContextUtil;
import com.intellij.psi.util.CachedValueProvider;
import com.intellij.psi.util.CachedValuesManager;
import com.intellij.psi.util.PsiTreeUtil;
import com.intellij.psi.util.QualifiedName;
import com.intellij.util.ArrayUtil;
import com.intellij.util.ObjectUtils;
import com.intellij.util.containers.ContainerUtil;
import com.intellij.util.containers.Stack;
import com.jetbrains.python.PyCustomType;
import com.jetbrains.python.PyNames;
import com.jetbrains.python.PyTokenTypes;
import com.jetbrains.python.ast.PyAstFunction;
import com.jetbrains.python.ast.PyAstTypeParameter;
import com.jetbrains.python.ast.impl.PyUtilCore;
import com.jetbrains.python.codeInsight.controlflow.ControlFlowCache;
import com.jetbrains.python.codeInsight.controlflow.ScopeOwner;
import com.jetbrains.python.codeInsight.dataflow.scope.Scope;
import com.jetbrains.python.codeInsight.dataflow.scope.ScopeUtil;
import com.jetbrains.python.codeInsight.functionTypeComments.psi.PyFunctionTypeAnnotation;
import com.jetbrains.python.codeInsight.functionTypeComments.psi.PyFunctionTypeAnnotationFile;
import com.jetbrains.python.codeInsight.typeHints.PyTypeHintFile;
import com.jetbrains.python.psi.*;
import com.jetbrains.python.psi.impl.PyBuiltinCache;
import com.jetbrains.python.psi.impl.PyEvaluator;
import com.jetbrains.python.psi.impl.PyPsiUtils;
import com.jetbrains.python.psi.impl.stubs.PyClassElementType;
import com.jetbrains.python.psi.impl.stubs.PyTypingAliasStubType;
import com.jetbrains.python.psi.resolve.PyResolveContext;
import com.jetbrains.python.psi.resolve.PyResolveUtil;
import com.jetbrains.python.psi.resolve.RatedResolveResult;
import com.jetbrains.python.psi.types.*;
import com.jetbrains.python.psi.types.PyTypeParameterMapping.Option;
import one.util.streamex.StreamEx;
import org.jetbrains.annotations.ApiStatus;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;

import java.util.*;
import java.util.function.Function;
import java.util.regex.Pattern;
import java.util.stream.Stream;

import static com.dynatrace.hash4j.hashing.Hashing.xxh3_128;
import static com.intellij.openapi.util.RecursionManager.doPreventingRecursion;
import static com.jetbrains.python.psi.PyKnownDecorator.TYPING_FINAL;
import static com.jetbrains.python.psi.PyKnownDecorator.TYPING_FINAL_EXT;
import static com.jetbrains.python.psi.PyUtil.as;

public final class PyTypingTypeProvider extends PyTypeProviderWithCustomContext<PyTypingTypeProvider.Context> {

  public static final @NlsSafe String TYPING = "typing";

  public static final String GENERATOR = "typing.Generator";
  public static final String ASYNC_GENERATOR = "typing.AsyncGenerator";
  public static final String COROUTINE = "typing.Coroutine";
  public static final String AWAITABLE = "typing.Awaitable";
  public static final String NAMEDTUPLE = "typing.NamedTuple";
  public static final String TYPED_DICT = "typing.TypedDict";
  public static final String TYPED_DICT_EXT = "typing_extensions.TypedDict";
  public static final String TYPE_GUARD = "typing.TypeGuard";
  public static final String TYPE_GUARD_EXT = "typing_extensions.TypeGuard";
  public static final String TYPE_IS = "typing.TypeIs";
  public static final String TYPE_IS_EXT = "typing_extensions.TypeIs";
  public static final String GENERIC = "typing.Generic";
  public static final String PROTOCOL = "typing.Protocol";
  public static final String PROTOCOL_EXT = "typing_extensions.Protocol";
  public static final String TYPE = "typing.Type";
  public static final String ANY = "typing.Any";
  public static final String NEW_TYPE = "typing.NewType";
  public static final String CALLABLE = "typing.Callable";
  public static final String CALLABLE_EXT = "typing_extensions.Callable";
  public static final String MAPPING = "typing.Mapping";
  public static final String MAPPING_GET = "typing.Mapping.get";
  private static final String LIST = "typing.List";
  private static final String DICT = "typing.Dict";
  private static final String DEFAULT_DICT = "typing.DefaultDict";
  private static final String ORDERED_DICT = "typing.OrderedDict";
  private static final String SET = "typing.Set";
  private static final String FROZEN_SET = "typing.FrozenSet";
  private static final String COUNTER = "typing.Counter";
  private static final String DEQUE = "typing.Deque";
  private static final String TUPLE = "typing.Tuple";
  public static final String CLASS_VAR = "typing.ClassVar";
  public static final String TYPE_VAR = "typing.TypeVar";
  public static final String TYPE_VAR_EXT = "typing_extensions.TypeVar";
  public static final String TYPE_VAR_TUPLE = "typing.TypeVarTuple";
  public static final String TYPE_VAR_TUPLE_EXT = "typing_extensions.TypeVarTuple";
  public static final String PARAM_SPEC = "typing.ParamSpec";
  public static final String PARAM_SPEC_EXT = "typing_extensions.ParamSpec";
  private static final String CHAIN_MAP = "typing.ChainMap";
  public static final String UNION = "typing.Union";
  public static final String CONCATENATE = "typing.Concatenate";
  public static final String CONCATENATE_EXT = "typing_extensions.Concatenate";
  public static final String OPTIONAL = "typing.Optional";
  public static final String NO_RETURN = "typing.NoReturn";
  public static final String NEVER = "typing.Never";
  public static final String NO_RETURN_EXT = "typing_extensions.NoReturn";
  public static final String NEVER_EXT = "typing_extensions.Never";
  public static final String FINAL = "typing.Final";
  public static final String FINAL_EXT = "typing_extensions.Final";
  public static final String LITERAL = "typing.Literal";
  public static final String LITERAL_EXT = "typing_extensions.Literal";
  public static final String LITERALSTRING = "typing.LiteralString";
  public static final String LITERALSTRING_EXT = "typing_extensions.LiteralString";
  public static final String ANNOTATED = "typing.Annotated";
  public static final String ANNOTATED_EXT = "typing_extensions.Annotated";
  public static final String TYPE_ALIAS = "typing.TypeAlias";
  public static final String TYPE_ALIAS_EXT = "typing_extensions.TypeAlias";
  public static final String TYPE_ALIAS_TYPE = "typing.TypeAliasType";
  private static final String SPECIAL_FORM = "typing._SpecialForm";
  private static final String SPECIAL_FORM_EXT = "typing_extensions._SpecialForm";
  public static final String REQUIRED = "typing.Required";
  public static final String REQUIRED_EXT = "typing_extensions.Required";
  public static final String NOT_REQUIRED = "typing.NotRequired";
  public static final String NOT_REQUIRED_EXT = "typing_extensions.NotRequired";
  public static final String READONLY = "typing.ReadOnly";
  public static final String READONLY_EXT = "typing_extensions.ReadOnly";

  public static final Set<String> TYPE_PARAMETER_FACTORIES = Set.of(
    TYPE_VAR, TYPE_VAR_EXT,
    PARAM_SPEC, PARAM_SPEC_EXT,
    TYPE_VAR_TUPLE, TYPE_VAR_TUPLE_EXT
  );

  public static final Set<String> TYPE_DICT_QUALIFIERS =
    Set.of(REQUIRED, REQUIRED_EXT, NOT_REQUIRED, NOT_REQUIRED_EXT, READONLY, READONLY_EXT);

  public static final String UNPACK = "typing.Unpack";
  public static final String UNPACK_EXT = "typing_extensions.Unpack";

  public static final String SELF = "typing.Self";
  public static final String SELF_EXT = "typing_extensions.Self";

  public static final Pattern TYPE_IGNORE_PATTERN =
    Pattern.compile("#\\s*type:\\s*ignore\\s*(\\[[^]#]*])?($|(\\s.*))", Pattern.CASE_INSENSITIVE);

  public static final String ASSERT_TYPE = "typing.assert_type";
  public static final String REVEAL_TYPE = "typing.reveal_type";
  public static final String REVEAL_TYPE_EXT = "typing_extensions.reveal_type";
  public static final String CAST = "typing.cast";
  public static final String CAST_EXT = "typing_extensions.cast";

  public static final ImmutableMap<String, String> BUILTIN_COLLECTION_CLASSES = ImmutableMap.<String, String>builder()
    .put(LIST, "list")
    .put(DICT, "dict")
    .put(SET, PyNames.SET)
    .put(FROZEN_SET, "frozenset")
    .put(TUPLE, PyNames.TUPLE)
    .build();

  private static final ImmutableMap<String, String> COLLECTIONS_CLASSES = ImmutableMap.<String, String>builder()
    .put(DEFAULT_DICT, "collections.defaultdict")
    .put(ORDERED_DICT, "collections.OrderedDict")
    .put(COUNTER, "collections.Counter")
    .put(DEQUE, "collections.deque")
    .put(CHAIN_MAP, "collections.ChainMap")
    .build();

  public static final ImmutableMap<String, @NlsSafe String> TYPING_COLLECTION_CLASSES = ImmutableMap.<String, String>builder()
    .put("list", "List")
    .put("dict", "Dict")
    .put("set", "Set")
    .put("frozenset", "FrozenSet")
    .build();

  public static final ImmutableMap<String, String> TYPING_BUILTINS_GENERIC_ALIASES = ImmutableMap.<String, String>builder()
    .putAll(TYPING_COLLECTION_CLASSES.entrySet())
    .put("type", "Type")
    .put("tuple", "Tuple")
    .build();

  public static final ImmutableSet<String> GENERIC_CLASSES = ImmutableSet.<String>builder()
    // special forms
    .add(TUPLE, GENERIC, PROTOCOL, CALLABLE, CALLABLE_EXT, TYPE, CLASS_VAR, FINAL, LITERAL, ANNOTATED, REQUIRED, NOT_REQUIRED, READONLY)
    // type aliases
    .add(UNION, OPTIONAL, LIST, DICT, DEFAULT_DICT, ORDERED_DICT, SET, FROZEN_SET, COUNTER, DEQUE, CHAIN_MAP)
    .add(PROTOCOL_EXT, FINAL_EXT, LITERAL_EXT, ANNOTATED_EXT, REQUIRED_EXT, NOT_REQUIRED_EXT, READONLY_EXT)
    .build();

  /**
   * For the following names we shouldn't go further to the RHS of assignments,
   * since they are not type aliases already and in typing.pyi are assigned to
   * some synthetic values.
   */
  public static final ImmutableSet<String> OPAQUE_NAMES = ImmutableSet.<String>builder()
    .add(PyKnownDecorator.TYPING_OVERLOAD.getQualifiedName().toString())
    .add(ANY)
    .add(TYPE_VAR)
    .add(TYPE_VAR_EXT)
    .add(TYPE_VAR_TUPLE)
    .add(TYPE_VAR_TUPLE_EXT)
    .add(GENERIC)
    .add(PARAM_SPEC)
    .add(PARAM_SPEC_EXT)
    .add(CONCATENATE)
    .add(CONCATENATE_EXT)
    .add(TUPLE)
    .add(CALLABLE)
    .add(CALLABLE_EXT)
    .add(TYPE)
    .add(PyKnownDecorator.TYPING_NO_TYPE_CHECK.getQualifiedName().toString())
    .add(PyKnownDecorator.TYPING_NO_TYPE_CHECK_EXT.getQualifiedName().toString())
    .add(UNION)
    .add(OPTIONAL)
    .add(LIST)
    .add(DICT)
    .add(DEFAULT_DICT)
    .add(ORDERED_DICT)
    .add(SET)
    .add(FROZEN_SET)
    .add(PROTOCOL, PROTOCOL_EXT)
    .add(CLASS_VAR)
    .add(COUNTER)
    .add(DEQUE)
    .add(CHAIN_MAP)
    .add(NO_RETURN, NO_RETURN_EXT)
    .add(NEVER, NEVER_EXT)
    .add(FINAL, FINAL_EXT)
    .add(LITERAL, LITERAL_EXT)
    .add(TYPED_DICT, TYPED_DICT_EXT)
    .add(ANNOTATED, ANNOTATED_EXT)
    .add(TYPE_ALIAS, TYPE_ALIAS_EXT)
    .add(REQUIRED, REQUIRED_EXT)
    .add(NOT_REQUIRED, NOT_REQUIRED_EXT)
    .add(READONLY, READONLY_EXT)
    .add(SELF, SELF_EXT)
    .add(LITERALSTRING, LITERALSTRING_EXT)
    .build();

  // Type hints in PSI stubs, type comments and "escaped" string annotations are represented as PyExpressionCodeFragments
  // created from the corresponding text fragments. This key points to the closest definition in the original file
  // they belong to.
  // TODO Make this the result of PyExpressionCodeFragment.getContext()
  private static final Key<PsiElement> FRAGMENT_OWNER = Key.create("PY_FRAGMENT_OWNER");
  private static final Key<Context> TYPE_HINT_EVAL_CONTEXT = Key.create("TYPE_HINT_EVAL_CONTEXT");

  @Override
  public @Nullable PyType getReferenceExpressionType(@NotNull PyReferenceExpression referenceExpression, @NotNull Context context) {
    // Check for the exact name in advance for performance reasons
    if ("Generic".equals(referenceExpression.getName())) {
      if (resolvesToQualifiedNames(referenceExpression, context.myContext, GENERIC)) {
        return createTypingGenericType(referenceExpression);
      }
    }
    // Check for the exact name in advance for performance reasons
    if ("Protocol".equals(referenceExpression.getName())) {
      if (resolvesToQualifiedNames(referenceExpression, context.myContext, PROTOCOL, PROTOCOL_EXT)) {
        return createTypingProtocolType(referenceExpression);
      }
    }
    // Check for the exact name in advance for performance reasons
    if ("Callable".equals(referenceExpression.getName())) {
      if (resolvesToQualifiedNames(referenceExpression, context.myContext, CALLABLE, CALLABLE_EXT)) {
        return createTypingCallableType(referenceExpression);
      }
    }

    return null;
  }

  @Override
  public @Nullable Ref<PyType> getParameterType(@NotNull PyNamedParameter param, @NotNull PyFunction func, @NotNull Context context) {
    @Nullable PyExpression typeHint = getAnnotationValue(param, context.myContext);
    if (typeHint == null) {
      String paramTypeCommentHint = param.getTypeCommentAnnotation();
      if (paramTypeCommentHint != null) {
        typeHint = toExpression(paramTypeCommentHint, param);
      }
    }
    if (typeHint == null) {
      PyFunctionTypeAnnotation annotation = getFunctionTypeAnnotation(func);
      if (annotation != null) {
        PyExpression funcTypeCommentParamHint = findParamTypeHintInFunctionTypeComment(annotation, param, func);
        if (funcTypeCommentParamHint == null) {
          return Ref.create();
        }
        typeHint = funcTypeCommentParamHint;
      }
    }
    if (typeHint == null) {
      return null;
    }
    if (param.isKeywordContainer()) {
      Ref<PyType> type = getTypeFromUnpackOperator(typeHint, context.myContext);
      if (type != null) {
        return type.get() instanceof PyTypedDictType ? type : null;
      }
    }
    if (typeHint instanceof PyReferenceExpression ref && ref.isQualified() && (
      param.isPositionalContainer() && "args".equals(ref.getReferencedName()) ||
      param.isKeywordContainer() && "kwargs".equals(ref.getReferencedName())
    )) {
      typeHint = Objects.requireNonNull(ref.getQualifier());
    }
    PyType type = Ref.deref(getType(typeHint, context));
    if (param.isPositionalContainer() && !(type instanceof PyParamSpecType)) {
      return Ref.create(PyTypeUtil.toPositionalContainerType(param, type));
    }
    if (param.isKeywordContainer() && !(type instanceof PyParamSpecType)) {
      return Ref.create(PyTypeUtil.toKeywordContainerType(param, type));
    }
    if (PyNames.NONE.equals(param.getDefaultValueText())) {
      return Ref.create(PyUnionType.union(type, PyBuiltinCache.getInstance(param).getNoneType()));
    }
    return Ref.create(type);
  }

  private static @Nullable PyExpression findParamTypeHintInFunctionTypeComment(@NotNull PyFunctionTypeAnnotation annotation,
                                                                               @NotNull PyNamedParameter param,
                                                                               @NotNull PyFunction func) {
    List<PyExpression> paramTypes = annotation.getParameterTypeList().getParameterTypes();
    if (paramTypes.size() == 1 && paramTypes.get(0) instanceof PyEllipsisLiteralExpression) {
      return null;
    }
    int startOffset = omitFirstParamInTypeComment(func, annotation) ? 1 : 0;
    List<PyParameter> funcParams = Arrays.asList(func.getParameterList().getParameters());
    int i = funcParams.indexOf(param) - startOffset;
    if (i >= 0 && i < paramTypes.size()) {
      PyExpression paramTypeHint = paramTypes.get(i);
      if (paramTypeHint instanceof PyStarExpression starExpression) {
        return starExpression.getExpression();
      }
      else if (paramTypeHint instanceof PyDoubleStarExpression doubleStarExpression) {
        return doubleStarExpression.getExpression();
      }
      else {
        return paramTypeHint;
      }
    }
    return null;
  }

  public static boolean isGenerator(@NotNull PyType type) {
    return type instanceof PyCollectionType genericType && GENERATOR.equals(genericType.getClassQName());
  }

  private static @NotNull PyType createTypingGenericType(@NotNull PsiElement anchor) {
    return new PyCustomType(GENERIC, null, false, true, PyBuiltinCache.getInstance(anchor).getObjectType());
  }

  private static @NotNull PyType createTypingProtocolType(@NotNull PsiElement anchor) {
    return new PyCustomType(PROTOCOL, null, false, true, PyBuiltinCache.getInstance(anchor).getObjectType());
  }

  public static @NotNull PyType createTypingCallableType(@NotNull PsiElement anchor) {
    return new PyCustomType(CALLABLE, null, false, true, PyBuiltinCache.getInstance(anchor).getObjectType());
  }

  private static boolean omitFirstParamInTypeComment(@NotNull PyFunction func, @NotNull PyFunctionTypeAnnotation annotation) {
    return func.getContainingClass() != null && func.getModifier() != PyAstFunction.Modifier.STATICMETHOD &&
           annotation.getParameterTypeList().getParameterTypes().size() < func.getParameterList().getParameters().length;
  }

  @Override
  public @Nullable Ref<PyType> getReturnType(@NotNull PyCallable callable, @NotNull Context context) {
    if (callable instanceof PyFunction function) {
      final PyExpression returnTypeAnnotation = getReturnTypeAnnotation(function, context.myContext);
      if (returnTypeAnnotation != null) {
        final Ref<PyType> typeRef = getType(returnTypeAnnotation, context);
        if (typeRef != null) {
          // Do not use toAsyncIfNeeded, as it also converts Generators. Here we do not need it.
          if (function.isAsync() && function.isAsyncAllowed() && !function.isGenerator()) {
            return Ref.create(wrapInCoroutineType(typeRef.get(), function));
          }
          return typeRef;
        }
        // Don't rely on other type providers if a type hint is present, but cannot be resolved.
        return Ref.create();
      }
    }
    return null;
  }

  @ApiStatus.Internal
  public static @Nullable PyExpression getReturnTypeAnnotation(@NotNull PyFunction function, TypeEvalContext context) {
    final PyExpression returnAnnotation = getAnnotationValue(function, context);
    if (returnAnnotation != null) {
      return returnAnnotation;
    }
    final PyFunctionTypeAnnotation functionAnnotation = getFunctionTypeAnnotation(function);
    if (functionAnnotation != null) {
      return functionAnnotation.getReturnType();
    }
    return null;
  }

  public static @Nullable PyFunctionTypeAnnotation getFunctionTypeAnnotation(@NotNull PyFunction function) {
    final String comment = function.getTypeCommentAnnotation();
    if (comment == null) {
      return null;
    }
    final PyFunctionTypeAnnotationFile file = CachedValuesManager.getCachedValue(function, () ->
      CachedValueProvider.Result.create(new PyFunctionTypeAnnotationFile(function.getTypeCommentAnnotation(), function), function));
    return file.getAnnotation();
  }

  @Override
  public @Nullable Ref<PyType> getCallType(@NotNull PyFunction function, @NotNull PyCallSiteExpression callSite, @NotNull Context context) {
    final String functionQName = function.getQualifiedName();

    if (CAST.equals(functionQName) || CAST_EXT.equals(functionQName)) {
      return Optional
        .ofNullable(as(callSite, PyCallExpression.class))
        .map(PyCallExpression::getArguments)
        .filter(args -> args.length > 0)
        .map(args -> getType(args[0], context))
        .orElse(null);
    }

    if (functionReturningCallSiteAsAType(function)) {
      return getAsClassObjectType(callSite, context);
    }

    return null;
  }

  private static boolean functionReturningCallSiteAsAType(@NotNull PyFunction function) {
    final String name = function.getName();

    if (PyNames.CLASS_GETITEM.equals(name)) return true;
    if (PyNames.GETITEM.equals(name)) {
      final PyClass cls = function.getContainingClass();
      if (cls != null) {
        final String qualifiedName = cls.getQualifiedName();
        return SPECIAL_FORM.equals(qualifiedName) || SPECIAL_FORM_EXT.equals(qualifiedName);
      }
    }

    return false;
  }

  private static @Nullable PyType getTypedDictTypeForTarget(@NotNull PyTargetExpression referenceTarget, @NotNull TypeEvalContext context) {
    if (PyTypedDictTypeProvider.Companion.isTypedDict(referenceTarget, context)) {
      return new PyCustomType(TYPED_DICT, null, false, true,
                              PyBuiltinCache.getInstance(referenceTarget).getDictType());
    }

    return null;
  }

  @Override
  public Ref<PyType> getReferenceType(@NotNull PsiElement referenceTarget, @NotNull Context context, @Nullable PsiElement anchor) {
    if (referenceTarget instanceof PyTargetExpression target) {
      final String targetQName = target.getQualifiedName();

      // Depends on typing.Generic defined as a target expression
      if (GENERIC.equals(targetQName)) {
        return Ref.create(createTypingGenericType(target));
      }
      // Depends on typing.Protocol defined as a target expression
      if (PROTOCOL.equals(targetQName) || PROTOCOL_EXT.equals(targetQName)) {
        return Ref.create(createTypingProtocolType(target));
      }
      // Depends on typing.Callable defined as a target expression
      if (CALLABLE.equals(targetQName) || CALLABLE_EXT.equals(targetQName)) {
        return Ref.create(createTypingCallableType(referenceTarget));
      }

      final PyType collection = getCollection(target, context.myContext);
      if (collection instanceof PyInstantiableType) {
        return Ref.create(((PyInstantiableType<?>)collection).toClass());
      }

      final PyType typedDictType = getTypedDictTypeForTarget(target, context.myContext);
      if (typedDictType != null) {
        return Ref.create(typedDictType);
      }

      PyExpression assignedValue = PyTypingAliasStubType.getAssignedValueStubLike(target);
      if (assignedValue instanceof PyCallExpression callExpression && callExpression.isCalleeText("TypeVar", "TypeVarTuple", "ParamSpec")) {
        for (PsiElement element : tryResolving(Objects.requireNonNull(callExpression.getCallee()), context.myContext)) {
          if (element instanceof PyClass pyClass &&
              TYPE_PARAMETER_FACTORIES.contains(ObjectUtils.notNull(pyClass.getQualifiedName(), "")) &&
              context.myContext.getType(pyClass) instanceof PyClassType pyClassType) {
            return Ref.create(pyClassType.toInstance());
          }
        }
      }

      // Return a type from an immediate type hint, e.g. from a syntactic annotation for
      // 
      // x: int = ...
      //
      // or find the "root" declaration and get a type from a type hint there, e.g.
      // 
      // x: int
      // x = ...
      //
      // or
      //
      // class C:
      //     attr: int
      //     def __init__(self, x):
      //         self.attr = x
      //
      // self.attr = ...

      // assignments "inst.attr = ..." are not preserved in stubs anyway. See PyTargetExpressionElementType.shouldCreateStub.
      if (target.isQualified() && context.myContext.maySwitchToAST(target)) {
        PsiElement resolved = target.getReference(PyResolveContext.defaultContext(context.myContext)).resolve();
        if (resolved instanceof PyTargetExpression resolvedTarget && PyUtil.isAttribute(resolvedTarget)) {
          target = resolvedTarget;
        }
      }

      final Ref<PyType> annotatedType = getTypeFromTargetExpressionAnnotation(target, context);
      if (annotatedType != null) {
        return annotatedType;
      }

      final String name = target.getReferencedName();
      final ScopeOwner scopeOwner = ScopeUtil.getScopeOwner(target);
      if (name == null || scopeOwner == null) {
        return null;
      }

      final PyClass pyClass = target.getContainingClass();

      if (target.isQualified()) {
        if (pyClass != null && scopeOwner instanceof PyFunction) {
          final PyResolveContext resolveContext = PyResolveContext.defaultContext(context.myContext);

          boolean isInstanceAttribute;
          if (context.myContext.maySwitchToAST(target)) {
            isInstanceAttribute = StreamEx.of(PyUtil.multiResolveTopPriority(target.getQualifier(), resolveContext))
              .select(PyParameter.class)
              .filter(PyParameter::isSelf)
              .anyMatch(p -> PsiTreeUtil.getParentOfType(p, PyFunction.class) == scopeOwner);
          }
          else {
            isInstanceAttribute = PyUtil.isInstanceAttribute(target);
          }
          if (!isInstanceAttribute) {
            return null;
          }
          // Set isDefinition=true to start searching right from the class level.
          Ref<PyType> memberType =
            getMemberTypeForClassType(context, target, name, resolveContext, false, new PyClassTypeImpl(pyClass, true));
          if (memberType != null) {
            return memberType;
          }

          for (PyClass ancestor : pyClass.getAncestorClasses(resolveContext.getTypeEvalContext())) {
            Ref<PyType> ancestorMemberType =
              getMemberTypeForClassType(context, target, name, resolveContext, true, new PyClassTypeImpl(ancestor, false));
            if (ancestorMemberType != null) {
              return ancestorMemberType;
            }
          }

          return null;
        }
      }
      else {
        StreamEx<PyTargetExpression> candidates = null;
        if (context.myContext.maySwitchToAST(target)) {
          final Scope scope = ControlFlowCache.getScope(scopeOwner);
          candidates = StreamEx.of(scope.getNamedElements(name, false)).select(PyTargetExpression.class);
        }
        // Unqualified target expression in either class or module
        else if (scopeOwner instanceof PyFile) {
          candidates = StreamEx.of(((PyFile)scopeOwner).getTopLevelAttributes()).filter(t -> name.equals(t.getName()));
        }
        else if (scopeOwner instanceof PyClass) {
          candidates = StreamEx.of(((PyClass)scopeOwner).getClassAttributes()).filter(t -> name.equals(t.getName()));
        }
        if (candidates != null) {
          return candidates
            .map(x -> getTypeFromTargetExpressionAnnotation(x, context))
            .nonNull()
            .findFirst()
            .orElse(null);
        }
      }
    }
    if (anchor instanceof PyExpression && referenceTarget instanceof PyClass pyClass && isGeneric(pyClass, context.myContext)) {
      PyCollectionType parameterizedType = parameterizeClassDefaultAware(pyClass, List.of(), context);
      if (parameterizedType != null) {
        return Ref.create(parameterizedType.toClass());
      }
    }
    return null;
  }

  private static @Nullable Ref<PyType> getMemberTypeForClassType(@NotNull Context context,
                                                                 PyTargetExpression target,
                                                                 String name,
                                                                 PyResolveContext resolveContext,
                                                                 boolean isInherited,
                                                                 PyClassTypeImpl classType) {
    final List<? extends RatedResolveResult> classAttrs =
      classType.resolveMember(name, target, AccessDirection.READ, resolveContext, isInherited);
    if (classAttrs == null) {
      return null;
    }
    return StreamEx.of(classAttrs)
      .map(RatedResolveResult::getElement)
      .select(PyTargetExpression.class)
      .filter(x -> {
        ScopeOwner owner = ScopeUtil.getScopeOwner(x);
        return owner instanceof PyClass || owner instanceof PyFunction;
      })
      .map(x -> getTypeFromTargetExpressionAnnotation(x, context))
      .collect(PyTypeUtil.toUnionFromRef());
  }

  private static @Nullable Ref<PyType> getTypeFromTargetExpressionAnnotation(@NotNull PyTargetExpression target, @NotNull Context context) {
    final PyExpression annotation = getAnnotationValue(target, context.myContext);
    if (annotation != null) {
      return getType(annotation, context);
    }
    final String comment = target.getTypeCommentAnnotation();
    if (comment != null) {
      return getVariableTypeCommentType(comment, target, context);
    }
    return null;
  }

  /**
   * Checks that text of a comment starts with "# type:" prefix and returns trimmed type hint after it.
   * The trailing part is supposed to contain type annotation in PEP 484 compatible format and an optional
   * plain text comment separated from it with another "#".
   * <p>
   * For instance, for {@code # type: List[int]  # comment} it returns {@code List[int]}.
   * <p>
   * This method cannot return an empty string.
   *
   * @see #getTypeCommentValueRange(String)
   */
  public static @Nullable String getTypeCommentValue(@NotNull String text) {
    return PyUtilCore.getTypeCommentValue(text);
  }

  /**
   * Returns the corresponding text range for a type hint as returned by {@link #getTypeCommentValue(String)}.
   *
   * @see #getTypeCommentValue(String)
   */
  public static @Nullable TextRange getTypeCommentValueRange(@NotNull String text) {
    return PyUtilCore.getTypeCommentValueRange(text);
  }

  @Override
  public @Nullable PyType getGenericType(@NotNull PyClass cls, @NotNull Context context) {
    List<PyTypeParameterType> typeParameters = collectTypeParameters(cls, context);
    return typeParameters.isEmpty() ? null : new PyCollectionTypeImpl(cls, false, typeParameters);
  }

  @Override
  public @NotNull Map<PyType, PyType> getGenericSubstitutions(@NotNull PyClass cls, @NotNull Context context) {
    return PyUtil.getParameterizedCachedValue(cls, context, c -> calculateGenericSubstitutions(cls, c));
  }

  private @NotNull Map<PyType, PyType> calculateGenericSubstitutions(@NotNull PyClass cls, @NotNull Context context) {
    if (!isGeneric(cls, context.myContext)) {
      return Collections.emptyMap();
    }
    Map<PyType, PyType> results = new HashMap<>();
    for (PyClassType superClassType : evaluateSuperClassesAsTypeHints(cls, context.myContext)) {
      Map<PyType, PyType> superSubstitutions =
        doPreventingRecursion(superClassType.getPyClass(), false, () -> getGenericSubstitutions(superClassType.getPyClass(), context));
      if (superSubstitutions != null) {
        results.putAll(superSubstitutions);
      }
      // TODO Share this logic with PyTypeChecker.collectTypeSubstitutions
      List<PyTypeParameterType> superTypeParameters = collectTypeParameters(superClassType.getPyClass(), context);
      List<PyType> superTypeArguments = superClassType instanceof PyCollectionType parameterized ?
                                        parameterized.getElementTypes() : Collections.emptyList();
      PyTypeParameterMapping mapping =
        PyTypeParameterMapping.mapByShape(superTypeParameters, superTypeArguments, Option.MAP_UNMATCHED_EXPECTED_TYPES_TO_ANY,
                                          Option.USE_DEFAULTS);
      if (mapping != null) {
        for (Couple<PyType> pair : mapping.getMappedTypes()) {
          PyType expectedType = pair.getFirst();
          PyType actualType = pair.getSecond();
          if (!expectedType.equals(actualType)) {
            results.put(expectedType, actualType);
          }
        }
      }
    }
    return results;
  }

  private static @NotNull List<PyClassType> evaluateSuperClassesAsTypeHints(@NotNull PyClass pyClass, @NotNull TypeEvalContext context) {
    List<PyClassType> results = new ArrayList<>();
    for (PyExpression superClassExpression : PyClassElementType.getSuperClassExpressions(pyClass)) {
      PsiFile containingFile = superClassExpression.getContainingFile();
      if (containingFile instanceof PyExpressionCodeFragment) {
        containingFile.putUserData(FRAGMENT_OWNER, pyClass);
      }
      PyType type = Ref.deref(getType(superClassExpression, context));
      if (type instanceof PyClassType classType) {
        results.add(classType);
      }
    }
    return results;
  }

  private static @NotNull List<PyTypeParameterType> collectTypeParameters(@NotNull PyClass cls, @NotNull Context context) {
    if (!isGeneric(cls, context.getTypeContext())) {
      return Collections.emptyList();
    }
    if (cls.getTypeParameterList() != null) {
      List<PyTypeParameter> typeParameters = cls.getTypeParameterList().getTypeParameters();
