"""Type inference constraints."""

from __future__ import annotations

from collections.abc import Iterable, Sequence

from typing import TYPE_CHECKING, Final, TypeGuard, cast

import mypy.subtypes

import mypy.typeops

from mypy.argmap import ArgTypeExpander

from mypy.erasetype import erase_typevars

from mypy.expandtype import expand_type_by_instance

from mypy.maptype import map_instance_to_supertype

from mypy.nodes import (

ARG_OPT,

ARG_POS,

ARG_STAR,

ARG_STAR2,

CONTRAVARIANT,

COVARIANT,

ArgKind,

TypeInfo,

)

from mypy.types import (

MAX_PROTOCOL_DEPTH,

TUPLE_LIKE_INSTANCE_NAMES,

AnyType,

CallableType,

DeletedType,

ErasedType,

Instance,

LiteralType,

NoneType,

NormalizedCallableType,

Overloaded,

Parameters,

ParamSpecType,

PartialType,

ProperType,

TupleType,

Type,

TypeAliasType,

TypedDictType,

TypeOfAny,

TypeType,

TypeVarId,

TypeVarLikeType,

TypeVarTupleType,

TypeVarType,

TypeVisitor,

UnboundType,

UninhabitedType,

UnionType,

UnpackType,

find_unpack_in_list,

flatten_nested_tuples,

get_proper_type,

has_recursive_types,

has_type_vars,

is_named_instance,

split_with_prefix_and_suffix,

)

from mypy.types_utils import is_union_with_any

from mypy.typestate import type_state

if TYPE_CHECKING:

from mypy.infer import ArgumentInferContext

SUBTYPE_OF: Final = 0

SUPERTYPE_OF: Final = 1

class Constraint:

"""A representation of a type constraint.

It can be either T <: type or T :> type (T is a type variable).

"""

type_var: TypeVarId

op = 0 # SUBTYPE_OF or SUPERTYPE_OF

target: Type

def __init__(self, type_var: TypeVarLikeType, op: int, target: Type) -> None:

self.type_var = type_var.id

self.op = op

# TODO: should we add "assert not isinstance(target, UnpackType)"?

# UnpackType is a synthetic type, and is never valid as a constraint target.

self.target = target

self.origin_type_var = type_var

# These are additional type variables that should be solved for together with type_var.

# TODO: A cleaner solution may be to modify the return type of infer_constraints()

# to include these instead, but this is a rather big refactoring.

self.extra_tvars: list[TypeVarLikeType] = []

def __repr__(self) -> str:

op_str = "<:"

if self.op == SUPERTYPE_OF:

op_str = ":>"

return f"{self.type_var} {op_str} {self.target}"

def __hash__(self) -> int:

return hash((self.type_var, self.op, self.target))

def __eq__(self, other: object) -> bool:

if not isinstance(other, Constraint):

return False

return (self.type_var, self.op, self.target) == (other.type_var, other.op, other.target)

def infer_constraints_for_callable(

callee: CallableType,

arg_types: Sequence[Type | None],

arg_kinds: list[ArgKind],

arg_names: Sequence[str | None] | None,

formal_to_actual: list[list[int]],

context: ArgumentInferContext,

) -> list[Constraint]:

"""Infer type variable constraints for a callable and actual arguments.

Return a list of constraints.

"""

constraints: list[Constraint] = []

mapper = ArgTypeExpander(context)

param_spec = callee.param_spec()

param_spec_arg_types = []

param_spec_arg_names = []

param_spec_arg_kinds: list[ArgKind] = []

incomplete_star_mapping = False

for i, actuals in enumerate(formal_to_actual): # TODO: isn't this `enumerate(arg_types)`?

for actual in actuals:

if actual is None and callee.arg_kinds[i] in (ARG_STAR, ARG_STAR2): # type: ignore[unreachable]

# We can't use arguments to infer ParamSpec constraint, if only some

# are present in the current inference pass.

incomplete_star_mapping = True # type: ignore[unreachable]

break

for i, actuals in enumerate(formal_to_actual):

if isinstance(callee.arg_types[i], UnpackType):

unpack_type = callee.arg_types[i]

assert isinstance(unpack_type, UnpackType)

# In this case we are binding all the actuals to *args,

# and we want a constraint that the typevar tuple being unpacked

# is equal to a type list of all the actuals.

actual_types = []

unpacked_type = get_proper_type(unpack_type.type)

if isinstance(unpacked_type, TypeVarTupleType):

tuple_instance = unpacked_type.tuple_fallback

elif isinstance(unpacked_type, TupleType):

tuple_instance = unpacked_type.partial_fallback

else:

assert False, "mypy bug: unhandled constraint inference case"

for actual in actuals:

actual_arg_type = arg_types[actual]

if actual_arg_type is None:

continue

expanded_actual = mapper.expand_actual_type(

actual_arg_type,

arg_kinds[actual],

callee.arg_names[i],

callee.arg_kinds[i],

allow_unpack=True,

)

if arg_kinds[actual] != ARG_STAR or isinstance(

get_proper_type(actual_arg_type), TupleType

):

actual_types.append(expanded_actual)

else:

# If we are expanding an iterable inside * actual, append a homogeneous item instead

actual_types.append(

UnpackType(tuple_instance.copy_modified(args=[expanded_actual]))

)

if isinstance(unpacked_type, TypeVarTupleType):

constraints.append(

Constraint(

unpacked_type,

SUPERTYPE_OF,

TupleType(actual_types, unpacked_type.tuple_fallback),

)

)

elif isinstance(unpacked_type, TupleType):

# Prefixes get converted to positional args, so technically the only case we

# should have here is like Tuple[Unpack[Ts], Y1, Y2, Y3]. If this turns out

# not to hold we can always handle the prefixes too.

inner_unpack = unpacked_type.items[0]

assert isinstance(inner_unpack, UnpackType)

inner_unpacked_type = get_proper_type(inner_unpack.type)

suffix_len = len(unpacked_type.items) - 1

if isinstance(inner_unpacked_type, TypeVarTupleType):

# Variadic item can be either *Ts...

constraints.append(

Constraint(

inner_unpacked_type,

SUPERTYPE_OF,

TupleType(

actual_types[:-suffix_len], inner_unpacked_type.tuple_fallback

),

)

)

else:

# ...or it can be a homogeneous tuple.

assert (

isinstance(inner_unpacked_type, Instance)

and inner_unpacked_type.type.fullname == "builtins.tuple"

)

for at in actual_types[:-suffix_len]:

constraints.extend(

infer_constraints(inner_unpacked_type.args[0], at, SUPERTYPE_OF)

)

# Now handle the suffix (if any).

if suffix_len:

for tt, at in zip(unpacked_type.items[1:], actual_types[-suffix_len:]):

constraints.extend(infer_constraints(tt, at, SUPERTYPE_OF))

else:

assert False, "mypy bug: unhandled constraint inference case"

else:

for actual in actuals:

actual_arg_type = arg_types[actual]

if actual_arg_type is None:

continue

if param_spec and callee.arg_kinds[i] in (ARG_STAR, ARG_STAR2):

# If actual arguments are mapped to ParamSpec type, we can't infer individual

# constraints, instead store them and infer single constraint at the end.

# It is impossible to map actual kind to formal kind, so use some heuristic.

# This inference is used as a fallback, so relying on heuristic should be OK.

if not incomplete_star_mapping:

param_spec_arg_types.append(

mapper.expand_actual_type(

actual_arg_type, arg_kinds[actual], None, arg_kinds[actual]

)

)

actual_kind = arg_kinds[actual]

param_spec_arg_kinds.append(

ARG_POS if actual_kind not in (ARG_STAR, ARG_STAR2) else actual_kind

)

param_spec_arg_names.append(arg_names[actual] if arg_names else None)

else:

actual_type = mapper.expand_actual_type(

actual_arg_type,

arg_kinds[actual],

callee.arg_names[i],

callee.arg_kinds[i],

)

c = infer_constraints(callee.arg_types[i], actual_type, SUPERTYPE_OF)

constraints.extend(c)

if (

param_spec

and not any(c.type_var == param_spec.id for c in constraints)

and not incomplete_star_mapping

):

# Use ParamSpec constraint from arguments only if there are no other constraints,

# since as explained above it is quite ad-hoc.

constraints.append(

Constraint(

param_spec,

SUPERTYPE_OF,

Parameters(

arg_types=param_spec_arg_types,

arg_kinds=param_spec_arg_kinds,

arg_names=param_spec_arg_names,

imprecise_arg_kinds=True,

),

)

)

if any(isinstance(v, ParamSpecType) for v in callee.variables):

# As a perf optimization filter imprecise constraints only when we can have them.

constraints = filter_imprecise_kinds(constraints)

return constraints

def infer_constraints(

template: Type,

actual: Type,

direction: int,

skip_neg_op: bool = False,

erase_types: bool = True,

) -> list[Constraint]:

"""Infer type constraints.

Match a template type, which may contain type variable references,

recursively against a type which does not contain (the same) type

variable references. The result is a list of type constrains of

form 'T is a supertype/subtype of x', where T is a type variable

present in the template and x is a type without reference to type

variables present in the template.

Assume T and S are type variables. Now the following results can be

calculated (read as '(template, actual) --> result'):

(T, X) --> T :> X

(X[T], X[Y]) --> T <: Y and T :> Y

((T, T), (X, Y)) --> T :> X and T :> Y

((T, S), (X, Y)) --> T :> X and S :> Y

(X[T], Any) --> T <: Any and T :> Any

The constraints are represented as Constraint objects. If skip_neg_op == True,

then skip adding reverse (polymorphic) constraints (since this is already a call

to infer such constraints).

"""

if any(

get_proper_type(template) == get_proper_type(t)

and get_proper_type(actual) == get_proper_type(a)

for (t, a) in reversed(type_state.inferring)

):

return []

# This guard matches the one we use for subtyping, it is slightly more risky,

# but it is much faster than has_recursive_types().

if (

isinstance(template, TypeAliasType)

and template.is_recursive

or isinstance(get_proper_type(template), Instance)

):

# This case requires special care because it may cause infinite recursion.

# Note that we include Instances because the may be recursive as str(Sequence[str]).

if not has_type_vars(template):

# Return early on an empty branch.

return []

type_state.inferring.append((template, actual))

res = _infer_constraints(template, actual, direction, skip_neg_op, erase_types)

type_state.inferring.pop()

return res

return _infer_constraints(template, actual, direction, skip_neg_op, erase_types)

def _infer_constraints(

template: Type, actual: Type, direction: int, skip_neg_op: bool, erase_types: bool

) -> list[Constraint]:

orig_template = template

template = get_proper_type(template)

actual = get_proper_type(actual)

# Type inference shouldn't be affected by whether union types have been simplified.

# We however keep any ErasedType items, so that the caller will see it when using

# checkexpr.has_erased_component().

if not type_state.keep_unions and isinstance(template, UnionType):

template = mypy.typeops.make_simplified_union(template.items, keep_erased=True)

if not type_state.keep_unions and isinstance(actual, UnionType):

actual = mypy.typeops.make_simplified_union(actual.items, keep_erased=True)

# Ignore Any types from the type suggestion engine to avoid them

# causing us to infer Any in situations where a better job could

# be done otherwise. (This can produce false positives but that

# doesn't really matter because it is all heuristic anyway.)

if isinstance(actual, AnyType) and actual.type_of_any == TypeOfAny.suggestion_engine:

return []

# type[A | B] is always represented as type[A] | type[B] internally.

# This makes our constraint solver choke on type[T] <: type[A] | type[B],

# solving T as generic meet(A, B) which is often `object`. Force unwrap such unions

# if both sides are type[...] or unions thereof. See `testTypeVarType` test

type_type_unwrapped = False

if _is_type_type(template) and _is_type_type(actual):

type_type_unwrapped = True

template = _unwrap_type_type(template)

actual = _unwrap_type_type(actual)

# If the template is simply a type variable, emit a Constraint directly.

# We need to handle this case before handling Unions for two reasons:

# 1. "T <: Union[U1, U2]" is not equivalent to "T <: U1 or T <: U2",

# because T can itself be a union (notably, Union[U1, U2] itself).

# 2. "T :> Union[U1, U2]" is logically equivalent to "T :> U1 and

# T :> U2", but they are not equivalent to the constraint solver,

# which never introduces new Union types (it uses join() instead).

if isinstance(template, TypeVarType):

return [Constraint(template, direction, actual)]

if (

isinstance(actual, TypeVarType)

and not actual.id.is_meta_var()

and direction == SUPERTYPE_OF

):

# Unless template is also a type variable (or a union that contains one), using the upper

# bound for inference will usually give better result for actual that is a type variable.

if not isinstance(template, UnionType) or not any(

isinstance(t, TypeVarType) for t in template.items

):

actual = get_proper_type(actual.upper_bound)

# Now handle the case of either template or actual being a Union.

# For a Union to be a subtype of another type, every item of the Union

# must be a subtype of that type, so concatenate the constraints.

if direction == SUBTYPE_OF and isinstance(template, UnionType):

res = []

for t_item in template.items:

res.extend(infer_constraints(t_item, actual, direction))

return res

if direction == SUPERTYPE_OF and isinstance(actual, UnionType):

# Case when *both* template and actual are unions needs special-casing:

# * First, remove identical items that appear in both unions.

# * Then, restore any unions that where split in the loop below

# (see comment above about plain type variables for why this is important).

# See e.g. testOptionalUnionInferencePrecise for situations where this helps.

nested_type_vars = None

if isinstance(template, UnionType):

nested_type_vars = [it for it in template.items if isinstance(it, TypeVarType)]

template, actual = remove_common_items(template, actual)

if not isinstance(actual, UnionType):

if isinstance(actual, UninhabitedType):

# Empty after simplification: do not infer spurious constraints.

return []

# Not a union after simplification, restart from the top.

return infer_constraints(template, actual, direction)

res = []

for a_item in actual.items:

# `orig_template` has to be preserved intact in case it's recursive.

# If we unwrapped ``type[...]`` previously, wrap the item back again,

# as ``type[...]`` can't be removed from `orig_template`.

if type_type_unwrapped:

a_item = TypeType.make_normalized(a_item)

res.extend(infer_constraints(orig_template, a_item, direction))

if nested_type_vars:

res = restore_union(res, actual, nested_type_vars)

return res

# Now the potential subtype is known not to be a Union or a type

# variable that we are solving for. In that case, for a Union to

# be a supertype of the potential subtype, some item of the Union

# must be a supertype of it.

if direction == SUBTYPE_OF and isinstance(actual, UnionType):

# We infer constraints eagerly -- try to find constraints for a type

# variable if possible. This seems to help with some real-world

# use cases.

return any_constraints(

[

infer_constraints_if_possible(template, a_item, direction)

for a_item in actual.items

],

eager=True,

)

if direction == SUPERTYPE_OF and isinstance(template, UnionType):

# When the template is a union, we are okay with leaving some

# type variables indeterminate. This helps with some special

# cases, though this isn't very principled.

result = any_constraints(

[

infer_constraints_if_possible(t_item, actual, direction)

for t_item in template.items

],

eager=isinstance(actual, AnyType),

)

if result:

return result

elif has_recursive_types(template) and not has_recursive_types(actual):

return handle_recursive_union(template, actual, direction)

return []

# Remaining cases are handled by ConstraintBuilderVisitor.

return template.accept(ConstraintBuilderVisitor(actual, direction, skip_neg_op, erase_types))

def _is_type_type(tp: ProperType) -> TypeGuard[TypeType | UnionType]:

"""Is ``tp`` a ``type[...]`` or a union thereof?

``Type[A | B]`` is internally represented as ``type[A] | type[B]``, and this

troubles the solver sometimes.

"""

return (

isinstance(tp, TypeType)

or isinstance(tp, UnionType)

and all(isinstance(get_proper_type(o), TypeType) for o in tp.items)

)

def _unwrap_type_type(tp: TypeType | UnionType) -> ProperType:

"""Extract the inner type from ``type[...]`` expression or a union thereof."""

if isinstance(tp, TypeType):

return tp.item

return UnionType.make_union([cast(TypeType, get_proper_type(o)).item for o in tp.items])

def infer_constraints_if_possible(

template: Type, actual: Type, direction: int

) -> list[Constraint] | None:

"""Like infer_constraints, but return None if the input relation is

known to be unsatisfiable, for example if template=List[T] and actual=int.

(In this case infer_constraints would return [], just like it would for

an automatically satisfied relation like template=List[T] and actual=object.)

"""

if direction == SUBTYPE_OF and not mypy.subtypes.is_subtype(erase_typevars(template), actual):

return None

if direction == SUPERTYPE_OF and not mypy.subtypes.is_subtype(

actual, erase_typevars(template)

):

return None

if (

direction == SUPERTYPE_OF

and isinstance(template, TypeVarType)

and not mypy.subtypes.is_subtype(actual, erase_typevars(template.upper_bound))

):

# This is not caught by the above branch because of the erase_typevars() call,

# that would return 'Any' for a type variable.

return None

return infer_constraints(template, actual, direction)

def select_trivial(options: Sequence[list[Constraint] | None]) -> list[list[Constraint]]:

"""Select only those lists where each item is a constraint against Any."""

res = []

for option in options:

if option is None:

continue

if all(isinstance(get_proper_type(c.target), AnyType) for c in option):

res.append(option)

return res

def merge_with_any(constraint: Constraint) -> Constraint:

"""Transform a constraint target into a union with given Any type."""

target = constraint.target

if is_union_with_any(target):

# Do not produce redundant unions.

return constraint

# TODO: if we will support multiple sources Any, use this here instead.

any_type = AnyType(TypeOfAny.implementation_artifact)

return Constraint(

constraint.origin_type_var,

constraint.op,

UnionType.make_union([target, any_type], target.line, target.column),

)

def handle_recursive_union(template: UnionType, actual: Type, direction: int) -> list[Constraint]:

# This is a hack to special-case things like Union[T, Inst[T]] in recursive types. Although

# it is quite arbitrary, it is a relatively common pattern, so we should handle it well.

# This function may be called when inferring against such union resulted in different

# constraints for each item. Normally we give up in such case, but here we instead split

# the union in two parts, and try inferring sequentially.

non_type_var_items = [t for t in template.items if not isinstance(t, TypeVarType)]

type_var_items = [t for t in template.items if isinstance(t, TypeVarType)]

if not type_var_items or not non_type_var_items:

return []

return infer_constraints(

UnionType.make_union(non_type_var_items), actual, direction

) or infer_constraints(UnionType.make_union(type_var_items), actual, direction)

def any_constraints(options: list[list[Constraint] | None], *, eager: bool) -> list[Constraint]:

"""Deduce what we can from a collection of constraint lists.

It's a given that at least one of the lists must be satisfied. A

None element in the list of options represents an unsatisfiable

constraint and is ignored. Ignore empty constraint lists if eager

is true -- they are always trivially satisfiable.

"""

if eager:

valid_options = [option for option in options if option]

else:

valid_options = [option for option in options if option is not None]

if not valid_options:

return []

if len(valid_options) == 1:

return valid_options[0]

if all(is_same_constraints(valid_options[0], c) for c in valid_options[1:]):

# Multiple sets of constraints that are all the same. Just pick any one of them.

return valid_options[0]

# This special-casing is not safe for ParamSpecs and TypeVarTuples, since unions are

# not valid constraints for them. This is however only needed in niche edge cases.

if all(is_similar_constraints(valid_options[0], c) for c in valid_options[1:]) and all(

isinstance(c.origin_type_var, TypeVarType) for c in valid_options[0]

):

# All options have same structure. In this case we can merge-in trivial

# options (i.e. those that only have Any) and try again.

trivial_options = select_trivial(valid_options)

if trivial_options and len(trivial_options) < len(valid_options):

merged_options = []

for option in valid_options:

if option in trivial_options:

continue

merged_options.append([merge_with_any(c) for c in option])

return any_constraints(list(merged_options), eager=eager)

# If normal logic didn't work, try excluding trivially unsatisfiable constraint (due to

# upper bounds) from each option, and comparing them again.

filtered_options = [filter_satisfiable(o) for o in options]

if filtered_options != options:

return any_constraints(filtered_options, eager=eager)

# Try harder: if that didn't work, try to strip typevars that aren't meta vars.

# Note this is what we would always do, but unfortunately some callers may not

# set the meta var status correctly (for historical reasons), so we use this as

# a fallback only.

filtered_options = [exclude_non_meta_vars(o) for o in options]

if filtered_options != options:

return any_constraints(filtered_options, eager=eager)

# Otherwise, there are either no valid options or multiple, inconsistent valid

# options. Give up and deduce nothing.

return []

def filter_satisfiable(option: list[Constraint] | None) -> list[Constraint] | None:

"""Keep only constraints that can possibly be satisfied.

Currently, we filter out constraints where target is not a subtype of the upper bound.

Since those can be never satisfied. We may add more cases in future if it improves type

inference.

"""

if not option:

return option

satisfiable = []

for c in option:

if isinstance(c.origin_type_var, TypeVarType) and c.origin_type_var.values:

if any(

mypy.subtypes.is_subtype(c.target, value) for value in c.origin_type_var.values

):

satisfiable.append(c)

elif mypy.subtypes.is_subtype(c.target, c.origin_type_var.upper_bound):

satisfiable.append(c)

if not satisfiable:

return None

return satisfiable

def exclude_non_meta_vars(option: list[Constraint] | None) -> list[Constraint] | None:

# If we had an empty list, keep it intact

if not option:

return option

# However, if none of the options actually references meta vars, better remove

# this constraint entirely.

return [c for c in option if c.type_var.is_meta_var()] or None

def is_same_constraints(x: list[Constraint], y: list[Constraint]) -> bool:

for c1 in x:

if not any(is_same_constraint(c1, c2) for c2 in y):

return False

for c1 in y:

if not any(is_same_constraint(c1, c2) for c2 in x):

return False

return True

def is_same_constraint(c1: Constraint, c2: Constraint) -> bool:

# Ignore direction when comparing constraints against Any.

skip_op_check = isinstance(get_proper_type(c1.target), AnyType) and isinstance(

get_proper_type(c2.target), AnyType

)

return (

c1.type_var == c2.type_var

and (c1.op == c2.op or skip_op_check)

and mypy.subtypes.is_same_type(c1.target, c2.target)

)

def is_similar_constraints(x: list[Constraint], y: list[Constraint]) -> bool:

"""Check that two lists of constraints have similar structure.

This means that each list has same type variable plus direction pairs (i.e we

ignore the target). Except for constraints where target is Any type, there

we ignore direction as well.

"""

return _is_similar_constraints(x, y) and _is_similar_constraints(y, x)

def _is_similar_constraints(x: list[Constraint], y: list[Constraint]) -> bool:

"""Check that every constraint in the first list has a similar one in the second.

See docstring above for definition of similarity.

"""

for c1 in x:

has_similar = False

for c2 in y:

# Ignore direction when either constraint is against Any.

skip_op_check = isinstance(get_proper_type(c1.target), AnyType) or isinstance(

get_proper_type(c2.target), AnyType

)

if c1.type_var == c2.type_var and (c1.op == c2.op or skip_op_check):

has_similar = True

break

if not has_similar:

return False

return True

class ConstraintBuilderVisitor(TypeVisitor[list[Constraint]]):

"""Visitor class for inferring type constraints."""

# The type that is compared against a template

# TODO: The value may be None. Is that actually correct?

actual: ProperType

def __init__(

self, actual: ProperType, direction: int, skip_neg_op: bool, erase_types: bool

) -> None:

# Direction must be SUBTYPE_OF or SUPERTYPE_OF.

self.actual = actual

self.direction = direction

# Whether to skip polymorphic inference (involves inference in opposite direction)

# this is used to prevent infinite recursion when both template and actual are

# generic callables.

self.skip_neg_op = skip_neg_op

# Normally we should erase generic actual type when inferring against type[T]

# to avoid leaking type variables, see testGenericClassAsArgumentToType.

# The only exception is self-types in generic classes, where we set this to False.

self.erase_types = erase_types

# Trivial leaf types

def visit_unbound_type(self, template: UnboundType) -> list[Constraint]:

return []

def visit_any(self, template: AnyType) -> list[Constraint]:

return []

def visit_none_type(self, template: NoneType) -> list[Constraint]:

return []

def visit_uninhabited_type(self, template: UninhabitedType) -> list[Constraint]:

return []

def visit_erased_type(self, template: ErasedType) -> list[Constraint]:

return []

def visit_deleted_type(self, template: DeletedType) -> list[Constraint]:

return []

def visit_literal_type(self, template: LiteralType) -> list[Constraint]:

return []

# Errors

def visit_partial_type(self, template: PartialType) -> list[Constraint]:

# We can't do anything useful with a partial type here.

assert False, "Internal error"

# Non-trivial leaf type

def visit_type_var(self, template: TypeVarType) -> list[Constraint]:

assert False, (

"Unexpected TypeVarType in ConstraintBuilderVisitor"

" (should have been handled in infer_constraints)"

)

def visit_param_spec(self, template: ParamSpecType) -> list[Constraint]:

# Can't infer ParamSpecs from component values (only via Callable[P, T]).

return []

def visit_type_var_tuple(self, template: TypeVarTupleType) -> list[Constraint]:

raise NotImplementedError

def visit_unpack_type(self, template: UnpackType) -> list[Constraint]:

raise RuntimeError("Mypy bug: unpack should be handled at a higher level.")

def visit_parameters(self, template: Parameters) -> list[Constraint]:

# Constraining Any against C[P] turns into infer_against_any([P], Any)

if isinstance(self.actual, AnyType):

return self.infer_against_any(template.arg_types, self.actual)

if type_state.infer_polymorphic and isinstance(self.actual, Parameters):

# For polymorphic inference we need to be able to infer secondary constraints

# in situations like [x: T] <: P <: [x: int].

return infer_callable_arguments_constraints(template, self.actual, self.direction)

if type_state.infer_polymorphic and isinstance(self.actual, ParamSpecType):

# Similar for [x: T] <: Q <: Concatenate[int, P].

return infer_callable_arguments_constraints(

template, self.actual.prefix, self.direction

)

# There also may be unpatched types after a user error, simply ignore them.

return []

# Non-leaf types

def visit_instance(self, template: Instance) -> list[Constraint]:

original_actual = actual = self.actual

res: list[Constraint] = []

if isinstance(actual, (CallableType, Overloaded)) and template.type.is_protocol:

if "__call__" in template.type.protocol_members:

# Special case: a generic callback protocol

if len(template.type.inferring) < MAX_PROTOCOL_DEPTH and not any(

template == t for t in template.type.inferring

):

template.type.inferring.append(template)

call = mypy.subtypes.find_member(

"__call__", template, actual, is_operator=True

)

assert call is not None

if (

self.direction == SUPERTYPE_OF

and mypy.subtypes.is_subtype(actual, erase_typevars(call))

or self.direction == SUBTYPE_OF

and mypy.subtypes.is_subtype(erase_typevars(call), actual)

):

res.extend(infer_constraints(call, actual, self.direction))

template.type.inferring.pop()

if isinstance(actual, CallableType) and actual.fallback is not None:

if (

actual.is_type_obj()

and template.type.is_protocol

and self.direction == SUPERTYPE_OF

):

instance_type = actual.get_instance_type(force_fallback=True)

if isinstance(instance_type, Instance):

res.extend(

self.infer_constraints_from_protocol_members(

instance_type, template, instance_type, template, class_obj=True

)

)

actual = actual.fallback

if isinstance(actual, TypeType) and template.type.is_protocol:

if self.direction == SUPERTYPE_OF:

a_item = actual.item

if isinstance(a_item, Instance):

res.extend(

self.infer_constraints_from_protocol_members(

a_item, template, a_item, template, class_obj=True

)

)

# Infer constraints for Type[T] via metaclass of T when it makes sense.

if isinstance(a_item, TypeVarType):

a_item = get_proper_type(a_item.upper_bound)

if isinstance(a_item, Instance) and a_item.type.metaclass_type:

res.extend(

self.infer_constraints_from_protocol_members(

a_item.type.metaclass_type, template, actual, template

)

)

if isinstance(actual, Overloaded) and actual.fallback is not None:

actual = actual.fallback

if isinstance(actual, TypedDictType):

actual = actual.create_anonymous_fallback()

if isinstance(actual, LiteralType):

actual = actual.fallback

if isinstance(actual, Instance):

instance = actual

erased = erase_typevars(template)

assert isinstance(erased, ProperType) and isinstance(erased, Instance)

# We always try nominal inference if possible,

# it is much faster than the structural one.

if self.direction == SUBTYPE_OF and template.type.has_base(instance.type.fullname):

mapped = map_instance_to_supertype(template, instance.type)

tvars = mapped.type.defn.type_vars

if instance.type.has_type_var_tuple_type:

# Variadic types need special handling to map each type argument to

# the correct corresponding type variable.

assert instance.type.type_var_tuple_prefix is not None

assert instance.type.type_var_tuple_suffix is not None

prefix_len = instance.type.type_var_tuple_prefix

suffix_len = instance.type.type_var_tuple_suffix

tvt = instance.type.defn.type_vars[prefix_len]

assert isinstance(tvt, TypeVarTupleType)

fallback = tvt.tuple_fallback

i_prefix, i_middle, i_suffix = split_with_prefix_and_suffix(

instance.args, prefix_len, suffix_len

)

m_prefix, m_middle, m_suffix = split_with_prefix_and_suffix(

mapped.args, prefix_len, suffix_len

)

instance_args = i_prefix + (TupleType(list(i_middle), fallback),) + i_suffix

mapped_args = m_prefix + (TupleType(list(m_middle), fallback),) + m_suffix

else:

mapped_args = mapped.args

instance_args = instance.args

# N.B: We use zip instead of indexing because the lengths might have

# mismatches during daemon reprocessing.

for tvar, mapped_arg, instance_arg in zip(tvars, mapped_args, instance_args):

if isinstance(tvar, TypeVarType):

# The constraints for generic type parameters depend on variance.

# Include constraints from both directions if invariant.

if tvar.variance != CONTRAVARIANT:

res.extend(infer_constraints(mapped_arg, instance_arg, self.direction))

if tvar.variance != COVARIANT:

res.extend(

infer_constraints(mapped_arg, instance_arg, neg_op(self.direction))

)

elif isinstance(tvar, ParamSpecType) and isinstance(mapped_arg, ParamSpecType):

prefix = mapped_arg.prefix

if isinstance(instance_arg, Parameters):

# No such thing as variance for ParamSpecs, consider them invariant

# TODO: constraints between prefixes using

# infer_callable_arguments_constraints()

suffix: Type = instance_arg.copy_modified(

instance_arg.arg_types[len(prefix.arg_types) :],

instance_arg.arg_kinds[len(prefix.arg_kinds) :],

instance_arg.arg_names[len(prefix.arg_names) :],

)

res.append(Constraint(mapped_arg, SUBTYPE_OF, suffix))

res.append(Constraint(mapped_arg, SUPERTYPE_OF, suffix))

elif isinstance(instance_arg, ParamSpecType):

suffix = instance_arg.copy_modified(

prefix=Parameters(

instance_arg.prefix.arg_types[len(prefix.arg_types) :],

instance_arg.prefix.arg_kinds[len(prefix.arg_kinds) :],

instance_arg.prefix.arg_names[len(prefix.arg_names) :],

)

)

res.append(Constraint(mapped_arg, SUBTYPE_OF, suffix))

res.append(Constraint(mapped_arg, SUPERTYPE_OF, suffix))

elif isinstance(tvar, TypeVarTupleType):

# Handle variadic type variables covariantly for consistency.

res.extend(infer_constraints(mapped_arg, instance_arg, self.direction))

return res

elif self.direction == SUPERTYPE_OF and instance.type.has_base(template.type.fullname):

mapped = map_instance_to_supertype(instance, template.type)

tvars = template.type.defn.type_vars

if template.type.has_type_var_tuple_type:

# Variadic types need special handling to map each type argument to

# the correct corresponding type variable.

assert template.type.type_var_tuple_prefix is not None

assert template.type.type_var_tuple_suffix is not None

prefix_len = template.type.type_var_tuple_prefix

suffix_len = template.type.type_var_tuple_suffix

tvt = template.type.defn.type_vars[prefix_len]

assert isinstance(tvt, TypeVarTupleType)

fallback = tvt.tuple_fallback

t_prefix, t_middle, t_suffix = split_with_prefix_and_suffix(

template.args, prefix_len, suffix_len

)

m_prefix, m_middle, m_suffix = split_with_prefix_and_suffix(

mapped.args, prefix_len, suffix_len

)

template_args = t_prefix + (TupleType(list(t_middle), fallback),) + t_suffix

mapped_args = m_prefix + (TupleType(list(m_middle), fallback),) + m_suffix

else:

mapped_args = mapped.args

template_args = template.args

# N.B: We use zip instead of indexing because the lengths might have

# mismatches during daemon reprocessing.

for tvar, mapped_arg, template_arg in zip(tvars, mapped_args, template_args):

if isinstance(tvar, TypeVarType):

# The constraints for generic type parameters depend on variance.

# Include constraints from both directions if invariant.

if tvar.variance != CONTRAVARIANT:

res.extend(infer_constraints(template_arg, mapped_arg, self.direction))

if tvar.variance != COVARIANT:

res.extend(

infer_constraints(template_arg, mapped_arg, neg_op(self.direction))

)

elif isinstance(tvar, ParamSpecType) and isinstance(

template_arg, ParamSpecType

):

prefix = template_arg.prefix

if isinstance(mapped_arg, Parameters):

# No such thing as variance for ParamSpecs, consider them invariant

# TODO: constraints between prefixes using

# infer_callable_arguments_constraints()

suffix = mapped_arg.copy_modified(

mapped_arg.arg_types[len(prefix.arg_types) :],

mapped_arg.arg_kinds[len(prefix.arg_kinds) :],

mapped_arg.arg_names[len(prefix.arg_names) :],

)

res.append(Constraint(template_arg, SUBTYPE_OF, suffix))

res.append(Constraint(template_arg, SUPERTYPE_OF, suffix))

elif isinstance(mapped_arg, ParamSpecType):

suffix = mapped_arg.copy_modified(

prefix=Parameters(

mapped_arg.prefix.arg_types[len(prefix.arg_types) :],

mapped_arg.prefix.arg_kinds[len(prefix.arg_kinds) :],

mapped_arg.prefix.arg_names[len(prefix.arg_names) :],

)

)

res.append(Constraint(template_arg, SUBTYPE_OF, suffix))

res.append(Constraint(template_arg, SUPERTYPE_OF, suffix))

elif isinstance(tvar, TypeVarTupleType):

# Consider variadic type variables to be invariant.

res.extend(infer_constraints(template_arg, mapped_arg, SUBTYPE_OF))

res.extend(infer_constraints(template_arg, mapped_arg, SUPERTYPE_OF))

return res

if (

template.type.is_protocol

and self.direction == SUPERTYPE_OF

and len(template.type.inferring) < MAX_PROTOCOL_DEPTH

and

# We avoid infinite recursion for structural subtypes by checking

# whether this type already appeared in the inference chain.

# This is a conservative way to break the inference cycles.

# It never produces any "false" constraints but gives up soon

# on purely structural inference cycles, see #3829.

# Note that we use is_protocol_implementation instead of is_subtype

# because some type may be considered a subtype of a protocol

# due to _promote, but still not implement the protocol.

not any(template == t for t in reversed(template.type.inferring))

and mypy.subtypes.is_protocol_implementation(instance, erased, skip=["__call__"])

):

template.type.inferring.append(template)

res.extend(

self.infer_constraints_from_protocol_members(

instance, template, original_actual, template

)

)

template.type.inferring.pop()

return res

elif (

instance.type.is_protocol

and self.direction == SUBTYPE_OF