@Nullable
  public static PyType substitute(@Nullable PyType type,
                                  @NotNull GenericSubstitutions substitutions,
                                  @NotNull TypeEvalContext context,
                                  @NotNull Set<PyType> substituting) {
    boolean alreadySubstituting = !substituting.add(type);
    if (alreadySubstituting) {
      return null;
    }
    try {
      if (hasGenerics(type, context)) {
        if (type instanceof PyUnpackedTupleType unpackedTupleType) {
          return new PyUnpackedTupleTypeImpl(ContainerUtil.flatMap(unpackedTupleType.getElementTypes(),
                                                                   t -> substituteExpand(t, substitutions, context, substituting)),
                                             unpackedTupleType.isUnbound());
        }
        if (type instanceof PyTypeVarTupleType typeVarTupleType) {
          if (!substitutions.typeVarTuples.containsKey(typeVarTupleType)) {
            return type;
          }
          PyVariadicType substitution = substitutions.typeVarTuples.get(typeVarTupleType);
          if (!typeVarTupleType.equals(substitution) && hasGenerics(substitution, context)) {
            return substitute(substitution, substitutions, context, substituting);
          }
          // TODO This should happen in getSubstitutionsWithUnresolvedReturnGenerics, but it won't work for inherited constructors
          //   as in testVariadicGenericCheckTypeAliasesRedundantParameter, investigate why
          // Replace unknown TypeVarTuples by *tuple[Any, ...] instead of plain Any
          return substitution == null ? PyUnpackedTupleTypeImpl.UNSPECIFIED : substitution;
        }
        if (type instanceof PyTypeVarType typeVar) {
          // Both mappings of kind {T: T2} (and no mapping for T2) and {T: T} mean the substitution process should stop for T.
          // The first one occurs in the situations like
          //
          // def f(x: T1) -> T1: ...
          // def g(y: T2): f(y)
          //
          // when we're inferring the return type of "g".
          // The second is a plug for type hints like
          //
          // def g() -> Callable[[T], T]
          //
          // where we want to prevent replacing T with Any, even though it cannot be inferred at a call site.
          if (!substitutions.typeVars.containsKey(typeVar) && !substitutions.typeVars.containsKey(invert(typeVar))) {
            return typeVar;
          }
          PyType substitution = substitutions.typeVars.get(typeVar);
          if (substitution == null) {
            final PyInstantiableType<?> invertedTypeVar = invert(typeVar);
            final PyInstantiableType<?> invertedSubstitution = as(substitutions.typeVars.get(invertedTypeVar), PyInstantiableType.class);
            if (invertedSubstitution != null) {
              substitution = invert(invertedSubstitution);
            }
          }
          // TODO remove !typeVar.equals(substitution) part, it's necessary due to the logic in unifyReceiverWithParamSpecs
          if (!typeVar.equals(substitution) && hasGenerics(substitution, context)) {
            return substitute(substitution, substitutions, context, substituting);
          }
          return substitution;
        }
        else if (type instanceof PyParamSpecType paramSpecType && paramSpecType.getParameters() == null) {
          if (!substitutions.paramSpecs.containsKey(paramSpecType)) {
            return paramSpecType;
          }
          PyParamSpecType substitution = substitutions.paramSpecs.get(paramSpecType);
          if (substitution != null && !substitution.equals(paramSpecType) && hasGenerics(substitution, context)) {
            return substitute(substitution, substitutions, context);
          }
          // TODO For ParamSpecs, replace Any with (*args: Any, **kwargs: Any) as it's a logical "wildcard" for this kind of type parameter
          return substitution;
        }
        else if (type instanceof PySelfType) {
          var qualifierType = substitutions.qualifierType;
          var selfScopeClassType = ((PySelfType)type).getScopeClassType();
          return PyTypeUtil.toStream(qualifierType)
            .filter(memberType -> match(selfScopeClassType, memberType, context))
            .collect(PyTypeUtil.toUnion());
        }
        else if (type instanceof PyUnionType) {
          return ((PyUnionType)type).map(member -> substitute(member, substitutions, context, substituting));
        }
        else if (type instanceof PyTypedDictType typedDictType) {
          final Map<String, kotlin.Pair<PyExpression, PyType>> tdFields = typedDictType.getKeysToValuesWithTypes();
          final var substitutedTDFields = ContainerUtil.map2Map(
            tdFields.entrySet(),
            field -> Pair.create(
              field.getKey(),
              new kotlin.Pair<>(
                field.getValue().getFirst(),
                substitute(field.getValue().getSecond(), substitutions, context, substituting)
              )
            )
          );
          return PyTypedDictType.Companion.createFromKeysToValueTypes(typedDictType.myClass, substitutedTDFields, false);
        }
        else if (type instanceof final PyCollectionTypeImpl collection) {
          return new PyCollectionTypeImpl(collection.getPyClass(), collection.isDefinition(),
                                          ContainerUtil.flatMap(collection.getElementTypes(),
                                                                t -> substituteExpand(t, substitutions, context, substituting)));
        }
        else if (type instanceof PyTupleType tupleType) {
          final PyClass tupleClass = tupleType.getPyClass();

          final List<PyType> oldElementTypes = tupleType.isHomogeneous()
                                               ? Collections.singletonList(tupleType.getIteratedItemType())
                                               : tupleType.getElementTypes();

          // newElementTypes need to be modifiable list
          final List<PyType> newElementTypes =
            new ArrayList<>(ContainerUtil.flatMap(oldElementTypes, elementType ->
              substituteExpand(elementType, substitutions, context, substituting)));

          return new PyTupleType(tupleClass, newElementTypes, tupleType.isHomogeneous());
        }
        else if (type instanceof PyCallableType callable && !(type instanceof PyClassLikeType)) {
          List<PyCallableParameter> substParams;
          List<PyCallableParameter> parameters = callable.getParameters(context);
          if (parameters != null) {
            PyCallableParameter onlyParam = ContainerUtil.getOnlyItem(parameters);
            if (onlyParam != null && onlyParam.getType(context) instanceof PyParamSpecType paramSpecType) {
              final var substitution = substitute(paramSpecType, substitutions, context);
              if (substitution instanceof PyParamSpecType paramSpecSubst && paramSpecSubst.getParameters() != null) {
                substParams = paramSpecSubst.getParameters();
              }
              else {
                substParams = List.of(PyCallableParameterImpl.nonPsi(substitution));
              }
            }
            else if (onlyParam != null && onlyParam.getType(context) instanceof PyConcatenateType concatenateType) {
              final var paramSpecSubst = as(substitute(concatenateType.getParamSpec(), substitutions, context), PyParamSpecType.class);
              List<PyCallableParameter> paramSpecParams = paramSpecSubst != null ? paramSpecSubst.getParameters() : null;
              substParams = StreamEx.of(concatenateType.getFirstTypes())
                .flatCollection(paramType -> substituteExpand(paramType, substitutions, context, substituting))
                .map(PyCallableParameterImpl::nonPsi)
                .append(paramSpecParams != null ? paramSpecParams :
                        Collections.singletonList(PyCallableParameterImpl.nonPsi(paramSpecSubst)))
                .toList();
            }
            else {
              substParams = StreamEx.of(parameters)
                .mapToEntry(param -> param.getType(context))
                .flatMapKeyValue((param, paramType) -> {
                  PyParameter paramPsi = param.getParameter();
                  return StreamEx.of(substituteExpand(param.getType(context), substitutions, context, substituting))
                    .map(paramSubType -> paramPsi != null ?
                                         PyCallableParameterImpl.psi(paramPsi, paramSubType) :
                                         PyCallableParameterImpl.nonPsi(param.getName(), paramSubType, param.getDefaultValue()));
                })
                .toList();
            }
          }
          else {
            substParams = null;
          }
          final PyType substResult = substitute(callable.getReturnType(context), substitutions, context, substituting);
          return new PyCallableTypeImpl(substParams, substResult);
        }
      }
    }
    finally {
      substituting.remove(type);
    }
    return type;
  }
@Nullable
  public static PyType substitute(@Nullable PyType type,
                                  @NotNull GenericSubstitutions substitutions,
                                  @NotNull TypeEvalContext context,
                                  @NotNull Set<PyType> substituting)