"""Classes for representing mypy types."""

import sys
from abc import abstractmethod
from collections import OrderedDict
from typing import (
    Any, TypeVar, Dict, List, Tuple, cast, Generic, Set, Optional, Union, Iterable, NamedTuple,
    Callable, Sequence, Iterator,
)

MYPY = False
if MYPY:
    from typing import ClassVar

import mypy.nodes
from mypy import experiments
from mypy.nodes import (
    INVARIANT, SymbolNode, ARG_POS, ARG_OPT, ARG_STAR, ARG_STAR2, ARG_NAMED, ARG_NAMED_OPT,
    FuncBase, FuncDef,
)
from mypy.sharedparse import argument_elide_name
from mypy.util import IdMapper, replace_object_state
from mypy.bogus_type import Bogus

from mypy.mypyc_hacks import TypeOfAny

T = TypeVar('T')

JsonDict = Dict[str, Any]

# If we import type_visitor in the middle of the file, mypy breaks, and if we do it
# at the top, it breaks at runtime because of import cycle issues, so we do it at different
# times in different places.
if MYPY:
    from mypy.type_visitor import TypeVisitor, SyntheticTypeVisitor, TypeTranslator, TypeQuery


def deserialize_type(data: Union[JsonDict, str]) -> 'Type':
    if isinstance(data, str):
        return Instance.deserialize(data)
    classname = data['.class']
    method = deserialize_map.get(classname)
    if method is not None:
        return method(data)
    raise NotImplementedError('unexpected .class {}'.format(classname))


class Type(mypy.nodes.Context):
    """Abstract base class for all types."""

    __slots__ = ('can_be_true', 'can_be_false')

    def __init__(self, line: int = -1, column: int = -1) -> None:
        super().__init__(line, column)
        self.can_be_true = self.can_be_true_default()
        self.can_be_false = self.can_be_false_default()

    def can_be_true_default(self) -> bool:
        return True

    def can_be_false_default(self) -> bool:
        return True

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        raise RuntimeError('Not implemented')

    def __repr__(self) -> str:
        return self.accept(TypeStrVisitor())

    def serialize(self) -> Union[JsonDict, str]:
        raise NotImplementedError('Cannot serialize {} instance'.format(self.__class__.__name__))

    @classmethod
    def deserialize(cls, data: JsonDict) -> 'Type':
        raise NotImplementedError('Cannot deserialize {} instance'.format(cls.__name__))


class TypeVarId:
    # A type variable is uniquely identified by its raw id and meta level.

    # For plain variables (type parameters of generic classes and
    # functions) raw ids are allocated by semantic analysis, using
    # positive ids 1, 2, ... for generic class parameters and negative
    # ids -1, ... for generic function type arguments. This convention
    # is only used to keep type variable ids distinct when allocating
    # them; the type checker makes no distinction between class and
    # function type variables.

    # Metavariables are allocated unique ids starting from 1.
    raw_id = 0  # type: int

    # Level of the variable in type inference. Currently either 0 for
    # declared types, or 1 for type inference metavariables.
    meta_level = 0  # type: int

    # Class variable used for allocating fresh ids for metavariables.
    next_raw_id = 1  # type: ClassVar[int]

    def __init__(self, raw_id: int, meta_level: int = 0) -> None:
        self.raw_id = raw_id
        self.meta_level = meta_level

    @staticmethod
    def new(meta_level: int) -> 'TypeVarId':
        raw_id = TypeVarId.next_raw_id
        TypeVarId.next_raw_id += 1
        return TypeVarId(raw_id, meta_level)

    def __repr__(self) -> str:
        return self.raw_id.__repr__()

    def __eq__(self, other: object) -> bool:
        if isinstance(other, TypeVarId):
            return (self.raw_id == other.raw_id and
                    self.meta_level == other.meta_level)
        else:
            return False

    def __ne__(self, other: object) -> bool:
        return not (self == other)

    def __hash__(self) -> int:
        return hash((self.raw_id, self.meta_level))

    def is_meta_var(self) -> bool:
        return self.meta_level > 0


class TypeVarDef(mypy.nodes.Context):
    """Definition of a single type variable."""

    name = ''  # Name (may be qualified)
    fullname = ''  # Fully qualified name
    id = None  # type: TypeVarId
    values = None  # type: List[Type]  # Value restriction, empty list if no restriction
    upper_bound = None  # type: Type
    variance = INVARIANT  # type: int

    def __init__(self, name: str, fullname: str, id: Union[TypeVarId, int], values: List[Type],
                 upper_bound: Type, variance: int = INVARIANT, line: int = -1,
                 column: int = -1) -> None:
        super().__init__(line, column)
        assert values is not None, "No restrictions must be represented by empty list"
        self.name = name
        self.fullname = fullname
        if isinstance(id, int):
            id = TypeVarId(id)
        self.id = id
        self.values = values
        self.upper_bound = upper_bound
        self.variance = variance

    @staticmethod
    def new_unification_variable(old: 'TypeVarDef') -> 'TypeVarDef':
        new_id = TypeVarId.new(meta_level=1)
        return TypeVarDef(old.name, old.fullname, new_id, old.values,
                          old.upper_bound, old.variance, old.line, old.column)

    def erase_to_union_or_bound(self) -> Type:
        if self.values:
            return UnionType.make_simplified_union(self.values)
        else:
            return self.upper_bound

    def __repr__(self) -> str:
        if self.values:
            return '{} in {}'.format(self.name, tuple(self.values))
        elif not is_named_instance(self.upper_bound, 'builtins.object'):
            return '{} <: {}'.format(self.name, self.upper_bound)
        else:
            return self.name

    def serialize(self) -> JsonDict:
        assert not self.id.is_meta_var()
        return {'.class': 'TypeVarDef',
                'name': self.name,
                'fullname': self.fullname,
                'id': self.id.raw_id,
                'values': [v.serialize() for v in self.values],
                'upper_bound': self.upper_bound.serialize(),
                'variance': self.variance,
                }

    @classmethod
    def deserialize(cls, data: JsonDict) -> 'TypeVarDef':
        assert data['.class'] == 'TypeVarDef'
        return TypeVarDef(data['name'],
                          data['fullname'],
                          data['id'],
                          [deserialize_type(v) for v in data['values']],
                          deserialize_type(data['upper_bound']),
                          data['variance'],
                          )


class UnboundType(Type):
    """Instance type that has not been bound during semantic analysis."""

    __slots__ = ('name', 'args', 'optional', 'empty_tuple_index')

    def __init__(self,
                 name: str,
                 args: Optional[List[Type]] = None,
                 line: int = -1,
                 column: int = -1,
                 optional: bool = False,
                 empty_tuple_index: bool = False) -> None:
        super().__init__(line, column)
        if not args:
            args = []
        self.name = name
        self.args = args
        # Should this type be wrapped in an Optional?
        self.optional = optional
        # Special case for X[()]
        self.empty_tuple_index = empty_tuple_index

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        return visitor.visit_unbound_type(self)

    def __hash__(self) -> int:
        return hash((self.name, self.optional, tuple(self.args)))

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, UnboundType):
            return NotImplemented
        return (self.name == other.name and self.optional == other.optional and
                self.args == other.args)

    def serialize(self) -> JsonDict:
        return {'.class': 'UnboundType',
                'name': self.name,
                'args': [a.serialize() for a in self.args],
                }

    @classmethod
    def deserialize(cls, data: JsonDict) -> 'UnboundType':
        assert data['.class'] == 'UnboundType'
        return UnboundType(data['name'],
                           [deserialize_type(a) for a in data['args']])


class CallableArgument(Type):
    """Represents a Arg(type, 'name') inside a Callable's type list.

    Note that this is a synthetic type for helping parse ASTs, not a real type.
    """
    typ = None          # type: Type
    name = None         # type: Optional[str]
    constructor = None  # type: Optional[str]

    def __init__(self, typ: Type, name: Optional[str], constructor: Optional[str],
                 line: int = -1, column: int = -1) -> None:
        super().__init__(line, column)
        self.typ = typ
        self.name = name
        self.constructor = constructor

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        assert isinstance(visitor, SyntheticTypeVisitor)
        return visitor.visit_callable_argument(self)

    def serialize(self) -> JsonDict:
        assert False, "Synthetic types don't serialize"


class TypeList(Type):
    """Information about argument types and names [...].

    This is used for the arguments of a Callable type, i.e. for
    [arg, ...] in Callable[[arg, ...], ret]. This is not a real type
    but a syntactic AST construct. UnboundTypes can also have TypeList
    types before they are processed into Callable types.
    """

    items = None  # type: List[Type]

    def __init__(self, items: List[Type], line: int = -1, column: int = -1) -> None:
        super().__init__(line, column)
        self.items = items

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        assert isinstance(visitor, SyntheticTypeVisitor)
        return visitor.visit_type_list(self)

    def serialize(self) -> JsonDict:
        assert False, "Synthetic types don't serialize"


_dummy = object()  # type: Any


class AnyType(Type):
    """The type 'Any'."""

    __slots__ = ('type_of_any', 'source_any', 'missing_import_name')

    def __init__(self,
                 type_of_any: TypeOfAny,
                 source_any: Optional['AnyType'] = None,
                 missing_import_name: Optional[str] = None,
                 line: int = -1,
                 column: int = -1) -> None:
        super().__init__(line, column)
        self.type_of_any = type_of_any
        # If this Any was created as a result of interacting with another 'Any', record the source
        # and use it in reports.
        self.source_any = source_any
        if source_any and source_any.source_any:
            self.source_any = source_any.source_any

        if source_any is None:
            self.missing_import_name = missing_import_name
        else:
            self.missing_import_name = source_any.missing_import_name

        # Only unimported type anys and anys from other anys should have an import name
        assert (missing_import_name is None or
                type_of_any in (TypeOfAny.from_unimported_type, TypeOfAny.from_another_any))
        # Only Anys that come from another Any can have source_any.
        assert type_of_any != TypeOfAny.from_another_any or source_any is not None
        # We should not have chains of Anys.
        assert not self.source_any or self.source_any.type_of_any != TypeOfAny.from_another_any

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        return visitor.visit_any(self)

    def copy_modified(self,
                      # Mark with Bogus because _dummy is just an object (with type Any)
                      type_of_any: Bogus[TypeOfAny] = _dummy,
                      original_any: Bogus[Optional['AnyType']] = _dummy,
                      ) -> 'AnyType':
        if type_of_any is _dummy:
            type_of_any = self.type_of_any
        if original_any is _dummy:
            original_any = self.source_any
        return AnyType(type_of_any=type_of_any, source_any=original_any,
                       missing_import_name=self.missing_import_name,
                       line=self.line, column=self.column)

    def __hash__(self) -> int:
        return hash(AnyType)

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

    def serialize(self) -> JsonDict:
        return {'.class': 'AnyType', 'type_of_any': self.type_of_any.name,
                'source_any': self.source_any.serialize() if self.source_any is not None else None,
                'missing_import_name': self.missing_import_name}

    @classmethod
    def deserialize(cls, data: JsonDict) -> 'AnyType':
        assert data['.class'] == 'AnyType'
        source = data['source_any']
        return AnyType(TypeOfAny[data['type_of_any']],
                       AnyType.deserialize(source) if source is not None else None,
                       data['missing_import_name'])


class UninhabitedType(Type):
    """This type has no members.

    This type is the bottom type.
    With strict Optional checking, it is the only common subtype between all
    other types, which allows `meet` to be well defined.  Without strict
    Optional checking, NoneTyp fills this role.

    In general, for any type T:
        join(UninhabitedType, T) = T
        meet(UninhabitedType, T) = UninhabitedType
        is_subtype(UninhabitedType, T) = True
    """

    is_noreturn = False  # Does this come from a NoReturn?  Purely for error messages.
    # It is important to track whether this is an actual NoReturn type, or just a result
    # of ambiguous type inference, in the latter case we don't want to mark a branch as
    # unreachable in binder.
    ambiguous = False  # Is this a result of inference for a variable without constraints?

    def __init__(self, is_noreturn: bool = False, line: int = -1, column: int = -1) -> None:
        super().__init__(line, column)
        self.is_noreturn = is_noreturn

    def can_be_true_default(self) -> bool:
        return False

    def can_be_false_default(self) -> bool:
        return False

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        return visitor.visit_uninhabited_type(self)

    def __hash__(self) -> int:
        return hash(UninhabitedType)

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

    def serialize(self) -> JsonDict:
        return {'.class': 'UninhabitedType',
                'is_noreturn': self.is_noreturn}

    @classmethod
    def deserialize(cls, data: JsonDict) -> 'UninhabitedType':
        assert data['.class'] == 'UninhabitedType'
        return UninhabitedType(is_noreturn=data['is_noreturn'])


class NoneTyp(Type):
    """The type of 'None'.

    This type can be written by users as 'None'.
    """

    __slots__ = ()

    def __init__(self, line: int = -1, column: int = -1) -> None:
        super().__init__(line, column)

    def can_be_true_default(self) -> bool:
        return False

    def __hash__(self) -> int:
        return hash(NoneTyp)

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

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        return visitor.visit_none_type(self)

    def serialize(self) -> JsonDict:
        return {'.class': 'NoneTyp'}

    @classmethod
    def deserialize(cls, data: JsonDict) -> 'NoneTyp':
        assert data['.class'] == 'NoneTyp'
        return NoneTyp()


class ErasedType(Type):
    """Placeholder for an erased type.

    This is used during type inference. This has the special property that
    it is ignored during type inference.
    """

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        return visitor.visit_erased_type(self)


class DeletedType(Type):
    """Type of deleted variables.

    These can be used as lvalues but not rvalues.
    """

    source = ''  # type: Optional[str]  # May be None; name that generated this value

    def __init__(self, source: Optional[str] = None, line: int = -1, column: int = -1) -> None:
        super().__init__(line, column)
        self.source = source

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        return visitor.visit_deleted_type(self)

    def serialize(self) -> JsonDict:
        return {'.class': 'DeletedType',
                'source': self.source}

    @classmethod
    def deserialize(cls, data: JsonDict) -> 'DeletedType':
        assert data['.class'] == 'DeletedType'
        return DeletedType(data['source'])


# Fake TypeInfo to be used as a placeholder during Instance de-serialization.
NOT_READY = mypy.nodes.FakeInfo('De-serialization failure: TypeInfo not fixed')


class Instance(Type):
    """An instance type of form C[T1, ..., Tn].

    The list of type variables may be empty.
    """

    __slots__ = ('type', 'args', 'erased', 'invalid', 'type_ref')

    def __init__(self, typ: mypy.nodes.TypeInfo, args: List[Type],
                 line: int = -1, column: int = -1, erased: bool = False) -> None:
        super().__init__(line, column)
        assert not typ or typ.fullname() not in ["builtins.Any", "typing.Any"]
        self.type = typ
        self.args = args
        self.erased = erased  # True if result of type variable substitution
        self.invalid = False  # True if recovered after incorrect number of type arguments error
        self.type_ref = None  # type: Optional[str]

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        return visitor.visit_instance(self)

    def __hash__(self) -> int:
        return hash((self.type, tuple(self.args)))

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Instance):
            return NotImplemented
        return self.type == other.type and self.args == other.args

    def serialize(self) -> Union[JsonDict, str]:
        assert self.type is not None
        type_ref = self.type.fullname()
        if not self.args:
            return type_ref
        data = {'.class': 'Instance',
                }  # type: JsonDict
        data['type_ref'] = type_ref
        data['args'] = [arg.serialize() for arg in self.args]
        return data

    @classmethod
    def deserialize(cls, data: Union[JsonDict, str]) -> 'Instance':
        if isinstance(data, str):
            inst = Instance(NOT_READY, [])
            inst.type_ref = data
            return inst
        assert data['.class'] == 'Instance'
        args = []  # type: List[Type]
        if 'args' in data:
            args_list = data['args']
            assert isinstance(args_list, list)
            args = [deserialize_type(arg) for arg in args_list]
        inst = Instance(NOT_READY, args)
        inst.type_ref = data['type_ref']  # Will be fixed up by fixup.py later.
        return inst

    def copy_modified(self, *, args: List[Type]) -> 'Instance':
        return Instance(self.type, args, self.line, self.column, self.erased)

    def has_readable_member(self, name: str) -> bool:
        return self.type.has_readable_member(name)


class TypeVarType(Type):
    """A type variable type.

    This refers to either a class type variable (id > 0) or a function
    type variable (id < 0).
    """

    __slots__ = ('name', 'fullname', 'id', 'values', 'upper_bound', 'variance')

    def __init__(self, binder: TypeVarDef, line: int = -1, column: int = -1) -> None:
        super().__init__(line, column)
        self.name = binder.name  # Name of the type variable (for messages and debugging)
        self.fullname = binder.fullname  # type: str
        self.id = binder.id  # type: TypeVarId
        # Value restriction, empty list if no restriction
        self.values = binder.values  # type: List[Type]
        # Upper bound for values
        self.upper_bound = binder.upper_bound  # type: Type
        # See comments in TypeVarDef for more about variance.
        self.variance = binder.variance  # type: int

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        return visitor.visit_type_var(self)

    def erase_to_union_or_bound(self) -> Type:
        if self.values:
            return UnionType.make_simplified_union(self.values)
        else:
            return self.upper_bound

    def __hash__(self) -> int:
        return hash(self.id)

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, TypeVarType):
            return NotImplemented
        return self.id == other.id

    def serialize(self) -> JsonDict:
        assert not self.id.is_meta_var()
        return {'.class': 'TypeVarType',
                'name': self.name,
                'fullname': self.fullname,
                'id': self.id.raw_id,
                'values': [v.serialize() for v in self.values],
                'upper_bound': self.upper_bound.serialize(),
                'variance': self.variance,
                }

    @classmethod
    def deserialize(cls, data: JsonDict) -> 'TypeVarType':
        assert data['.class'] == 'TypeVarType'
        tvdef = TypeVarDef(data['name'],
                           data['fullname'],
                           data['id'],
                           [deserialize_type(v) for v in data['values']],
                           deserialize_type(data['upper_bound']),
                           data['variance'])
        return TypeVarType(tvdef)


class FunctionLike(Type):
    """Abstract base class for function types."""

    __slots__ = ('fallback',)

    def __init__(self, line: int = -1, column: int = -1) -> None:
        super().__init__(line, column)
        self.can_be_false = False
        if MYPY:  # Use MYPY to declare, we don't want a runtime None value
            # Corresponding instance type (e.g. builtins.type)
            self.fallback = cast(Instance, None)

    @abstractmethod
    def is_type_obj(self) -> bool: pass

    def is_concrete_type_obj(self) -> bool:
        return self.is_type_obj()

    @abstractmethod
    def type_object(self) -> mypy.nodes.TypeInfo: pass

    @abstractmethod
    def items(self) -> List['CallableType']: pass

    @abstractmethod
    def with_name(self, name: str) -> 'FunctionLike': pass

    @abstractmethod
    def get_name(self) -> Optional[str]: pass


FormalArgument = NamedTuple('FormalArgument', [
    ('name', Optional[str]),
    ('pos', Optional[int]),
    ('typ', Type),
    ('required', bool)])


class CallableType(FunctionLike):
    """Type of a non-overloaded callable object (such as function)."""

    __slots__ = ('arg_types',  # Types of function arguments
                 'arg_kinds',  # ARG_ constants
                 'arg_names',  # Argument names; None if not a keyword argument
                 'min_args',  # Minimum number of arguments; derived from arg_kinds
                 'var_arg',  # The formal argument for *args. Derived from arg kinds and types
                 'kw_arg',  # The formal argument for **kwargs. Derived from arg kinds and types
                 'ret_type',  # Return value type
                 'name',  # Name (may be None; for error messages and plugins)
                 'definition',  # For error messages.  May be None.
                 'variables',  # Type variables for a generic function
                 'is_ellipsis_args',  # Is this Callable[..., t] (with literal '...')?
                 'is_classmethod_class',  # Is this callable constructed for the benefit
                                          # of a classmethod's 'cls' argument?
                 'implicit',  # Was this type implicitly generated instead of explicitly
                              # specified by the user?
                 'special_sig',  # Non-None for signatures that require special handling
                                 # (currently only value is 'dict' for a signature similar to
                                 # 'dict')
                 'from_type_type',  # Was this callable generated by analyzing Type[...]
                                    # instantiation?
                 'bound_args',  # Bound type args, mostly unused but may be useful for
                                # tools that consume mypy ASTs
                 'def_extras',  # Information about original definition we want to serialize.
                                # This is used for more detailed error messages.
                 )

    def __init__(self,
                 arg_types: List[Type],
                 arg_kinds: List[int],
                 arg_names: Sequence[Optional[str]],
                 ret_type: Type,
                 fallback: Instance,
                 name: Optional[str] = None,
                 definition: Optional[SymbolNode] = None,
                 variables: Optional[List[TypeVarDef]] = None,
                 line: int = -1,
                 column: int = -1,
                 is_ellipsis_args: bool = False,
                 implicit: bool = False,
                 is_classmethod_class: bool = False,
                 special_sig: Optional[str] = None,
                 from_type_type: bool = False,
                 bound_args: Sequence[Optional[Type]] = (),
                 def_extras: Optional[Dict[str, Any]] = None,
                 ) -> None:
        super().__init__(line, column)
        assert len(arg_types) == len(arg_kinds) == len(arg_names)
        assert not any(tp is None for tp in arg_types), "No annotation must be Any, not None"
        if variables is None:
            variables = []
        self.arg_types = arg_types
        self.arg_kinds = arg_kinds
        self.arg_names = list(arg_names)
        self.min_args = arg_kinds.count(ARG_POS)
        self.var_arg, self.kw_arg = self._lookup_star_args(self.arg_types, self.arg_kinds)
        self.ret_type = ret_type
        self.fallback = fallback
        assert not name or '<bound method' not in name
        self.name = name
        self.definition = definition
        self.variables = variables
        self.is_ellipsis_args = is_ellipsis_args
        self.implicit = implicit
        self.is_classmethod_class = is_classmethod_class
        self.special_sig = special_sig
        self.from_type_type = from_type_type
        if not bound_args:
            bound_args = ()
        self.bound_args = bound_args
        if def_extras:
            self.def_extras = def_extras
        elif isinstance(definition, FuncDef):
            # This information would be lost if we don't have definition
            # after serialization, but it is useful in error messages.
            # TODO: decide how to add more info here (file, line, column)
            # without changing interface hash.
            self.def_extras = {'first_arg': definition.arg_names[0]
                               if definition.arg_names and definition.info and
                               not definition.is_static else None}
        else:
            self.def_extras = {}

    def copy_modified(self,
                      arg_types: Bogus[List[Type]] = _dummy,
                      arg_kinds: Bogus[List[int]] = _dummy,
                      arg_names: Bogus[List[Optional[str]]] = _dummy,
                      ret_type: Bogus[Type] = _dummy,
                      fallback: Bogus[Instance] = _dummy,
                      name: Bogus[Optional[str]] = _dummy,
                      definition: Bogus[SymbolNode] = _dummy,
                      variables: Bogus[List[TypeVarDef]] = _dummy,
                      line: Bogus[int] = _dummy,
                      column: Bogus[int] = _dummy,
                      is_ellipsis_args: Bogus[bool] = _dummy,
                      implicit: Bogus[bool] = _dummy,
                      special_sig: Bogus[Optional[str]] = _dummy,
                      from_type_type: Bogus[bool] = _dummy,
                      bound_args: Bogus[List[Optional[Type]]] = _dummy,
                      def_extras: Bogus[Dict[str, Any]] = _dummy) -> 'CallableType':
        return CallableType(
            arg_types=arg_types if arg_types is not _dummy else self.arg_types,
            arg_kinds=arg_kinds if arg_kinds is not _dummy else self.arg_kinds,
            arg_names=arg_names if arg_names is not _dummy else self.arg_names,
            ret_type=ret_type if ret_type is not _dummy else self.ret_type,
            fallback=fallback if fallback is not _dummy else self.fallback,
            name=name if name is not _dummy else self.name,
            definition=definition if definition is not _dummy else self.definition,
            variables=variables if variables is not _dummy else self.variables,
            line=line if line is not _dummy else self.line,
            column=column if column is not _dummy else self.column,
            is_ellipsis_args=(
                is_ellipsis_args if is_ellipsis_args is not _dummy else self.is_ellipsis_args),
            implicit=implicit if implicit is not _dummy else self.implicit,
            is_classmethod_class=self.is_classmethod_class,
            special_sig=special_sig if special_sig is not _dummy else self.special_sig,
            from_type_type=from_type_type if from_type_type is not _dummy else self.from_type_type,
            bound_args=bound_args if bound_args is not _dummy else self.bound_args,
            def_extras=def_extras if def_extras is not _dummy else dict(self.def_extras),
        )

    def _lookup_star_args(self,
                          arg_types: List[Type],
                          arg_kinds: List[int],
                          ) -> Tuple[Optional[FormalArgument], Optional[FormalArgument]]:
        """Returns the formal arguments for *args and **kwargs, if they exist.

        This helper method is used only in the constructor."""
        star_arg = None
        kwarg_arg = None
        for position, (type, kind) in enumerate(zip(arg_types, arg_kinds)):
            if kind == ARG_STAR:
                star_arg = FormalArgument(None, position, type, False)
            elif kind == ARG_STAR2:
                kwarg_arg = FormalArgument(None, position, type, False)
        return star_arg, kwarg_arg

    @property
    def is_var_arg(self) -> bool:
        """Does this callable have a *args argument?"""
        return self.var_arg is not None

    @property
    def is_kw_arg(self) -> bool:
        """Does this callable have a **kwargs argument?"""
        return self.kw_arg is not None

    def is_type_obj(self) -> bool:
        return self.fallback.type.is_metaclass()

    def is_concrete_type_obj(self) -> bool:
        return self.is_type_obj() and self.is_classmethod_class

    def type_object(self) -> mypy.nodes.TypeInfo:
        assert self.is_type_obj()
        ret = self.ret_type
        if isinstance(ret, TupleType):
            ret = ret.fallback
        if isinstance(ret, TypeVarType):
            ret = ret.upper_bound
        assert isinstance(ret, Instance)
        return ret.type

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        return visitor.visit_callable_type(self)

    def with_name(self, name: str) -> 'CallableType':
        """Return a copy of this type with the specified name."""
        return self.copy_modified(ret_type=self.ret_type, name=name)

    def get_name(self) -> Optional[str]:
        return self.name

    def max_fixed_args(self) -> int:
        n = len(self.arg_types)
        if self.is_var_arg:
            n -= 1
        return n

    def max_possible_positional_args(self) -> int:
        """Returns maximum number of positional arguments this method could possibly accept.

        This takes into account *arg and **kwargs but excludes keyword-only args."""
        if self.is_var_arg or self.is_kw_arg:
            return sys.maxsize
        blacklist = (ARG_NAMED, ARG_NAMED_OPT)
        return len([kind not in blacklist for kind in self.arg_kinds])

    def formal_arguments(self, include_star_args: bool = False) -> Iterator[FormalArgument]:
        """Yields the formal arguments corresponding to this callable, ignoring *arg and **kwargs.

        To handle *args and **kwargs, use the 'callable.var_args' and 'callable.kw_args' fields,
        if they are not None.

        If you really want to include star args in the yielded output, set the
        'include_star_args' parameter to 'True'."""
        done_with_positional = False
        for i in range(len(self.arg_types)):
            kind = self.arg_kinds[i]
            if kind in (ARG_STAR, ARG_STAR2, ARG_NAMED, ARG_NAMED_OPT):
                done_with_positional = True
            if not include_star_args and kind in (ARG_STAR, ARG_STAR2):
                continue

            required = kind in (ARG_POS, ARG_NAMED)
            pos = None if done_with_positional else i
            yield FormalArgument(
                self.arg_names[i],
                pos,
                self.arg_types[i],
                required)

    def corresponding_argument(self, model: FormalArgument) -> Optional[FormalArgument]:
        """Return the argument in this function that corresponds to `model`"""

        by_name = self.argument_by_name(model.name)
        by_pos = self.argument_by_position(model.pos)
        if by_name is None and by_pos is None:
            return None
        if by_name is not None and by_pos is not None:
            if by_name == by_pos:
                return by_name
            # If we're dealing with an optional pos-only and an optional
            # name-only arg, merge them.  This is the case for all functions
            # taking both *args and **args, or a pair of functions like so:

            # def right(a: int = ...) -> None: ...
            # def left(__a: int = ..., *, a: int = ...) -> None: ...
            from mypy.subtypes import is_equivalent
            if (not (by_name.required or by_pos.required)
                    and by_pos.name is None
                    and by_name.pos is None
                    and is_equivalent(by_name.typ, by_pos.typ)):
                return FormalArgument(by_name.name, by_pos.pos, by_name.typ, False)
        return by_name if by_name is not None else by_pos

    def argument_by_name(self, name: Optional[str]) -> Optional[FormalArgument]:
        if name is None:
            return None
        seen_star = False
        for i, (arg_name, kind, typ) in enumerate(
                zip(self.arg_names, self.arg_kinds, self.arg_types)):
            # No more positional arguments after these.
            if kind in (ARG_STAR, ARG_STAR2, ARG_NAMED, ARG_NAMED_OPT):
                seen_star = True
            if kind == ARG_STAR or kind == ARG_STAR2:
                continue
            if arg_name == name:
                position = None if seen_star else i
                return FormalArgument(name, position, typ, kind in (ARG_POS, ARG_NAMED))
        return self.try_synthesizing_arg_from_kwarg(name)

    def argument_by_position(self, position: Optional[int]) -> Optional[FormalArgument]:
        if position is None:
            return None
        if position >= len(self.arg_names):
            return self.try_synthesizing_arg_from_vararg(position)
        name, kind, typ = (
            self.arg_names[position],
            self.arg_kinds[position],
            self.arg_types[position],
        )
        if kind in (ARG_POS, ARG_OPT):
            return FormalArgument(name, position, typ, kind == ARG_POS)
        else:
            return self.try_synthesizing_arg_from_vararg(position)

    def try_synthesizing_arg_from_kwarg(self,
                                        name: Optional[str]) -> Optional[FormalArgument]:
        if self.kw_arg is not None:
            return FormalArgument(name, None, self.kw_arg.typ, False)
        else:
            return None

    def try_synthesizing_arg_from_vararg(self,
                                         position: Optional[int]) -> Optional[FormalArgument]:
        if self.var_arg is not None:
            return FormalArgument(None, position, self.var_arg.typ, False)
        else:
            return None

    def items(self) -> List['CallableType']:
        return [self]

    def is_generic(self) -> bool:
        return bool(self.variables)

    def type_var_ids(self) -> List[TypeVarId]:
        a = []  # type: List[TypeVarId]
        for tv in self.variables:
            a.append(tv.id)
        return a

    def __hash__(self) -> int:
        return hash((self.ret_type, self.is_type_obj(),
                     self.is_ellipsis_args, self.name,
                    tuple(self.arg_types), tuple(self.arg_names), tuple(self.arg_kinds)))

    def __eq__(self, other: object) -> bool:
        if isinstance(other, CallableType):
            return (self.ret_type == other.ret_type and
                    self.arg_types == other.arg_types and
                    self.arg_names == other.arg_names and
                    self.arg_kinds == other.arg_kinds and
                    self.name == other.name and
                    self.is_type_obj() == other.is_type_obj() and
                    self.is_ellipsis_args == other.is_ellipsis_args)
        else:
            return NotImplemented

    def serialize(self) -> JsonDict:
        # TODO: As an optimization, leave out everything related to
        # generic functions for non-generic functions.
        return {'.class': 'CallableType',
                'arg_types': [t.serialize() for t in self.arg_types],
                'arg_kinds': self.arg_kinds,
                'arg_names': self.arg_names,
                'ret_type': self.ret_type.serialize(),
                'fallback': self.fallback.serialize(),
                'name': self.name,
                # We don't serialize the definition (only used for error messages).
                'variables': [v.serialize() for v in self.variables],
                'is_ellipsis_args': self.is_ellipsis_args,
                'implicit': self.implicit,
                'is_classmethod_class': self.is_classmethod_class,
                'bound_args': [(None if t is None else t.serialize())
                               for t in self.bound_args],
                'def_extras': dict(self.def_extras),
                }

    @classmethod
    def deserialize(cls, data: JsonDict) -> 'CallableType':
        assert data['.class'] == 'CallableType'
        # TODO: Set definition to the containing SymbolNode?
        return CallableType([deserialize_type(t) for t in data['arg_types']],
                            data['arg_kinds'],
                            data['arg_names'],
                            deserialize_type(data['ret_type']),
                            Instance.deserialize(data['fallback']),
                            name=data['name'],
                            variables=[TypeVarDef.deserialize(v) for v in data['variables']],
                            is_ellipsis_args=data['is_ellipsis_args'],
                            implicit=data['implicit'],
                            is_classmethod_class=data['is_classmethod_class'],
                            bound_args=[(None if t is None else deserialize_type(t))
                                        for t in data['bound_args']],
                            def_extras=data['def_extras']
                            )


class Overloaded(FunctionLike):
    """Overloaded function type T1, ... Tn, where each Ti is CallableType.

    The variant to call is chosen based on static argument
    types. Overloaded function types can only be defined in stub
    files, and thus there is no explicit runtime dispatch
    implementation.
    """

    _items = None  # type: List[CallableType]  # Must not be empty

    def __init__(self, items: List[CallableType]) -> None:
        super().__init__(items[0].line, items[0].column)
        self._items = items
        self.fallback = items[0].fallback

    def items(self) -> List[CallableType]:
        return self._items

    def name(self) -> Optional[str]:
        return self.get_name()

    def is_type_obj(self) -> bool:
        # All the items must have the same type object status, so it's
        # sufficient to query only (any) one of them.
        return self._items[0].is_type_obj()

    def type_object(self) -> mypy.nodes.TypeInfo:
        # All the items must have the same type object, so it's sufficient to
        # query only (any) one of them.
        return self._items[0].type_object()

    def with_name(self, name: str) -> 'Overloaded':
        ni = []  # type: List[CallableType]
        for it in self._items:
            ni.append(it.with_name(name))
        return Overloaded(ni)

    def get_name(self) -> Optional[str]:
        return self._items[0].name

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        return visitor.visit_overloaded(self)

    def __hash__(self) -> int:
        return hash(tuple(self.items()))

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Overloaded):
            return NotImplemented
        return self.items() == other.items()

    def serialize(self) -> JsonDict:
        return {'.class': 'Overloaded',
                'items': [t.serialize() for t in self.items()],
                }

    @classmethod
    def deserialize(cls, data: JsonDict) -> 'Overloaded':
        assert data['.class'] == 'Overloaded'
        return Overloaded([CallableType.deserialize(t) for t in data['items']])


class TupleType(Type):
    """The tuple type Tuple[T1, ..., Tn] (at least one type argument).

    Instance variables:
        items: tuple item types
        fallback: the underlying instance type that is used for non-tuple methods
            (this is currently always builtins.tuple, but it could be different for named
            tuples, for example)
        implicit: if True, derived from a tuple expression (t,....) instead of Tuple[t, ...]
    """

    items = None  # type: List[Type]
    fallback = None  # type: Instance
    implicit = False

    def __init__(self, items: List[Type], fallback: Instance, line: int = -1,
                 column: int = -1, implicit: bool = False) -> None:
        super().__init__(line, column)
        self.items = items
        self.fallback = fallback
        self.implicit = implicit
        self.can_be_true = len(self.items) > 0
        self.can_be_false = len(self.items) == 0

    def length(self) -> int:
        return len(self.items)

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        return visitor.visit_tuple_type(self)

    def __hash__(self) -> int:
        return hash((tuple(self.items), self.fallback))

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, TupleType):
            return NotImplemented
        return self.items == other.items and self.fallback == other.fallback

    def serialize(self) -> JsonDict:
        return {'.class': 'TupleType',
                'items': [t.serialize() for t in self.items],
                'fallback': self.fallback.serialize(),
                'implicit': self.implicit,
                }

    @classmethod
    def deserialize(cls, data: JsonDict) -> 'TupleType':
        assert data['.class'] == 'TupleType'
        return TupleType([deserialize_type(t) for t in data['items']],
                         Instance.deserialize(data['fallback']),
                         implicit=data['implicit'])

    def copy_modified(self, *, fallback: Optional[Instance] = None,
                      items: Optional[List[Type]] = None) -> 'TupleType':
        if fallback is None:
            fallback = self.fallback
        if items is None:
            items = self.items
        return TupleType(items, fallback, self.line, self.column)

    def slice(self, begin: Optional[int], stride: Optional[int],
              end: Optional[int]) -> 'TupleType':
        return TupleType(self.items[begin:end:stride], self.fallback,
                         self.line, self.column, self.implicit)


class TypedDictType(Type):
    """The type of a TypedDict instance. TypedDict(K1=VT1, ..., Kn=VTn)

    A TypedDictType can be either named or anonymous.
    If it is anonymous then its fallback will be an Instance of Mapping[str, V].
    If it is named then its fallback will be an Instance of the named type (ex: "Point")
    whose TypeInfo has a typeddict_type that is anonymous.
    """

    items = None  # type: OrderedDict[str, Type]  # item_name -> item_type
    required_keys = None  # type: Set[str]
    fallback = None  # type: Instance

    def __init__(self, items: 'OrderedDict[str, Type]', required_keys: Set[str],
                 fallback: Instance, line: int = -1, column: int = -1) -> None:
        super().__init__(line, column)
        self.items = items
        self.required_keys = required_keys
        self.fallback = fallback
        self.can_be_true = len(self.items) > 0
        self.can_be_false = len(self.items) == 0

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        return visitor.visit_typeddict_type(self)

    def __hash__(self) -> int:
        return hash((frozenset(self.items.items()), self.fallback,
                     frozenset(self.required_keys)))

    def __eq__(self, other: object) -> bool:
        if isinstance(other, TypedDictType):
            if frozenset(self.items.keys()) != frozenset(other.items.keys()):
                return False
            for (_, left_item_type, right_item_type) in self.zip(other):
                if not left_item_type == right_item_type:
                    return False
            return self.fallback == other.fallback and self.required_keys == other.required_keys
        else:
            return NotImplemented

    def serialize(self) -> JsonDict:
        return {'.class': 'TypedDictType',
                'items': [[n, t.serialize()] for (n, t) in self.items.items()],
                'required_keys': sorted(self.required_keys),
                'fallback': self.fallback.serialize(),
                }

    @classmethod
    def deserialize(cls, data: JsonDict) -> 'TypedDictType':
        assert data['.class'] == 'TypedDictType'
        return TypedDictType(OrderedDict([(n, deserialize_type(t))
                                          for (n, t) in data['items']]),
                             set(data['required_keys']),
                             Instance.deserialize(data['fallback']))

    def is_anonymous(self) -> bool:
        return self.fallback.type.fullname() == 'typing.Mapping'

    def as_anonymous(self) -> 'TypedDictType':
        if self.is_anonymous():
            return self
        assert self.fallback.type.typeddict_type is not None
        return self.fallback.type.typeddict_type.as_anonymous()

    def copy_modified(self, *, fallback: Optional[Instance] = None,
                      item_types: Optional[List[Type]] = None,
                      required_keys: Optional[Set[str]] = None) -> 'TypedDictType':
        if fallback is None:
            fallback = self.fallback
        if item_types is None:
            items = self.items
        else:
            items = OrderedDict(zip(self.items, item_types))
        if required_keys is None:
            required_keys = self.required_keys
        return TypedDictType(items, required_keys, fallback, self.line, self.column)

    def create_anonymous_fallback(self, *, value_type: Type) -> Instance:
        anonymous = self.as_anonymous()
        return anonymous.fallback.copy_modified(args=[  # i.e. Mapping
            anonymous.fallback.args[0],                 # i.e. str
            value_type
        ])

    def names_are_wider_than(self, other: 'TypedDictType') -> bool:
        return len(other.items.keys() - self.items.keys()) == 0

    def zip(self, right: 'TypedDictType') -> Iterable[Tuple[str, Type, Type]]:
        left = self
        for (item_name, left_item_type) in left.items.items():
            right_item_type = right.items.get(item_name)
            if right_item_type is not None:
                yield (item_name, left_item_type, right_item_type)

    def zipall(self, right: 'TypedDictType') \
            -> Iterable[Tuple[str, Optional[Type], Optional[Type]]]:
        left = self
        for (item_name, left_item_type) in left.items.items():
            right_item_type = right.items.get(item_name)
            yield (item_name, left_item_type, right_item_type)
        for (item_name, right_item_type) in right.items.items():
            if item_name in left.items:
                continue
            yield (item_name, None, right_item_type)


class StarType(Type):
    """The star type *type_parameter.

    This is not a real type but a syntactic AST construct.
    """

    type = None  # type: Type

    def __init__(self, type: Type, line: int = -1, column: int = -1) -> None:
        super().__init__(line, column)
        self.type = type

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        assert isinstance(visitor, SyntheticTypeVisitor)
        return visitor.visit_star_type(self)

    def serialize(self) -> JsonDict:
        assert False, "Synthetic types don't serialize"


class UnionType(Type):
    """The union type Union[T1, ..., Tn] (at least one type argument)."""

    __slots__ = ('items',)

    def __init__(self, items: List[Type], line: int = -1, column: int = -1) -> None:
        super().__init__(line, column)
        self.items = flatten_nested_unions(items)  # type: List[Type]
        self.can_be_true = any(item.can_be_true for item in items)
        self.can_be_false = any(item.can_be_false for item in items)

    def __hash__(self) -> int:
        return hash(frozenset(self.items))

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, UnionType):
            return NotImplemented
        return frozenset(self.items) == frozenset(other.items)

    @staticmethod
    def make_union(items: List[Type], line: int = -1, column: int = -1) -> Type:
        if len(items) > 1:
            return UnionType(items, line, column)
        elif len(items) == 1:
            return items[0]
        else:
            return UninhabitedType()

    @staticmethod
    def make_simplified_union(items: List[Type], line: int = -1, column: int = -1) -> Type:
        """Build union type with redundant union items removed.

        If only a single item remains, this may return a non-union type.

        Examples:

        * [int, str] -> Union[int, str]
        * [int, object] -> object
        * [int, int] -> int
        * [int, Any] -> Union[int, Any] (Any types are not simplified away!)
        * [Any, Any] -> Any

        Note: This must NOT be used during semantic analysis, since TypeInfos may not
              be fully initialized.
        """
        # TODO: Make this a function living somewhere outside mypy.types. Most other non-trivial
        #       type operations are not static methods, so this is inconsistent.
        while any(isinstance(typ, UnionType) for typ in items):
            all_items = []  # type: List[Type]
            for typ in items:
                if isinstance(typ, UnionType):
                    all_items.extend(typ.items)
                else:
                    all_items.append(typ)
            items = all_items

        from mypy.subtypes import is_proper_subtype

        removed = set()  # type: Set[int]
        for i, ti in enumerate(items):
            if i in removed: continue
            # Keep track of the truishness info for deleted subtypes which can be relevant
            cbt = cbf = False
            for j, tj in enumerate(items):
                if (i != j and is_proper_subtype(tj, ti)):
                    # We found a redundant item in the union.
                    removed.add(j)
                    cbt = cbt or tj.can_be_true
                    cbf = cbf or tj.can_be_false
            # if deleted subtypes had more general truthiness, use that
            if not ti.can_be_true and cbt:
                items[i] = true_or_false(ti)
            elif not ti.can_be_false and cbf:
                items[i] = true_or_false(ti)

        simplified_set = [items[i] for i in range(len(items)) if i not in removed]
        return UnionType.make_union(simplified_set, line, column)

    def length(self) -> int:
        return len(self.items)

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        return visitor.visit_union_type(self)

    def has_readable_member(self, name: str) -> bool:
        """For a tree of unions of instances, check whether all instances have a given member.

        TODO: Deal with attributes of TupleType etc.
        TODO: This should probably be refactored to go elsewhere.
        """
        return all((isinstance(x, UnionType) and x.has_readable_member(name)) or
                   (isinstance(x, Instance) and x.type.has_readable_member(name))
                   for x in self.relevant_items())

    def relevant_items(self) -> List[Type]:
        """Removes NoneTypes from Unions when strict Optional checking is off."""
        if experiments.STRICT_OPTIONAL:
            return self.items
        else:
            return [i for i in self.items if not isinstance(i, NoneTyp)]

    def serialize(self) -> JsonDict:
        return {'.class': 'UnionType',
                'items': [t.serialize() for t in self.items],
                }

    @classmethod
    def deserialize(cls, data: JsonDict) -> 'UnionType':
        assert data['.class'] == 'UnionType'
        return UnionType([deserialize_type(t) for t in data['items']])


class PartialType(Type):
    """Type such as List[?] where type arguments are unknown, or partial None type.

    These are used for inferring types in multiphase initialization such as this:

      x = []       # x gets a partial type List[?], as item type is unknown
      x.append(1)  # partial type gets replaced with normal type List[int]

    Or with None:

      x = None  # x gets a partial type None
      if c:
          x = 1  # Infer actual type int for x
    """

    # None for the 'None' partial type; otherwise a generic class
    type = None  # type: Optional[mypy.nodes.TypeInfo]
    var = None  # type: mypy.nodes.Var
    inner_types = None  # type: List[Type]

    def __init__(self,
                 type: 'Optional[mypy.nodes.TypeInfo]',
                 var: 'mypy.nodes.Var',
                 inner_types: List[Type]) -> None:
        super().__init__()
        self.type = type
        self.var = var
        self.inner_types = inner_types

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        return visitor.visit_partial_type(self)


class EllipsisType(Type):
    """The type ... (ellipsis).

    This is not a real type but a syntactic AST construct, used in Callable[..., T], for example.

    A semantically analyzed type will never have ellipsis types.
    """

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        assert isinstance(visitor, SyntheticTypeVisitor)
        return visitor.visit_ellipsis_type(self)

    def serialize(self) -> JsonDict:
        assert False, "Synthetic types don't serialize"


class TypeType(Type):
    """For types like Type[User].

    This annotates variables that are class objects, constrained by
    the type argument.  See PEP 484 for more details.

    We may encounter expressions whose values are specific classes;
    those are represented as callables (possibly overloaded)
    corresponding to the class's constructor's signature and returning
    an instance of that class.  The difference with Type[C] is that
    those callables always represent the exact class given as the
    return type; Type[C] represents any class that's a subclass of C,
    and C may also be a type variable or a union (or Any).

    Many questions around subtype relationships between Type[C1] and
    def(...) -> C2 are answered by looking at the subtype
    relationships between C1 and C2, since Type[] is considered
    covariant.

    There's an unsolved problem with constructor signatures (also
    unsolved in PEP 484): calling a variable whose type is Type[C]
    assumes the constructor signature for C, even though a subclass of
    C might completely change the constructor signature.  For now we
    just assume that users of Type[C] are careful not to do that (in
    the future we might detect when they are violating that
    assumption).
    """

    # This can't be everything, but it can be a class reference,
    # a generic class instance, a union, Any, a type variable...
    item = None  # type: Type

    def __init__(self, item: Bogus[Union[Instance, AnyType, TypeVarType, TupleType, NoneTyp,
                                         CallableType]], *,
                 line: int = -1, column: int = -1) -> None:
        """To ensure Type[Union[A, B]] is always represented as Union[Type[A], Type[B]], item of
        type UnionType must be handled through make_normalized static method.
        """
        super().__init__(line, column)
        self.item = item

    @staticmethod
    def make_normalized(item: Type, *, line: int = -1, column: int = -1) -> Type:
        if isinstance(item, UnionType):
            return UnionType.make_union(
                [TypeType.make_normalized(union_item) for union_item in item.items],
                line=line, column=column
            )
        return TypeType(item, line=line, column=column)  # type: ignore

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        return visitor.visit_type_type(self)

    def __hash__(self) -> int:
        return hash(self.item)

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, TypeType):
            return NotImplemented
        return self.item == other.item

    def serialize(self) -> JsonDict:
        return {'.class': 'TypeType', 'item': self.item.serialize()}

    @classmethod
    def deserialize(cls, data: JsonDict) -> Type:
        assert data['.class'] == 'TypeType'
        return TypeType.make_normalized(deserialize_type(data['item']))


class ForwardRef(Type):
    """Class to wrap forward references to other types.

    This is used when a forward reference to an (unanalyzed) synthetic type is found,
    for example:

        x: A
        A = TypedDict('A', {'x': int})

    To avoid false positives and crashes in such situations, we first wrap the first
    occurrence of 'A' in ForwardRef. Then, the wrapped UnboundType is updated in the third
    pass of semantic analysis and ultimately fixed in the patches after the third pass.
    So that ForwardRefs are temporary and will be completely replaced with the linked types
    or Any (to avoid cyclic references) before the type checking stage.
    """
    _unbound = None  # type: UnboundType  # The original wrapped type
    _resolved = None  # type: Optional[Type]  # The resolved forward reference (initially None)

    def __init__(self, unbound: UnboundType) -> None:
        super().__init__()
        self._unbound = unbound
        self._resolved = None

    @property
    def unbound(self) -> UnboundType:
        # This is read-only to make it clear that resolution happens through resolve().
        return self._unbound

    @property
    def resolved(self) -> Optional[Type]:
        # Similar to above.
        return self._resolved

    def resolve(self, resolved: Type) -> None:
        """Resolve an unbound forward reference to point to a type."""
        assert self._resolved is None
        self._resolved = resolved

    def accept(self, visitor: 'TypeVisitor[T]') -> T:
        return visitor.visit_forwardref_type(self)

    def serialize(self) -> str:
        name = self.unbound.name
        # We should never get here since all forward references should be resolved
        # and removed during semantic analysis.
        assert False, "Internal error: Unresolved forward reference to {}".format(name)


# We split off the type visitor base classes to another module
# to make it easier to gradually get modules working with mypyc.
# Import them here, after the types are defined.
# This is intended as a re-export also.
if not MYPY:
    from mypy.type_visitor import (  # noqa
        TypeVisitor, SyntheticTypeVisitor, TypeTranslator, TypeQuery
    )


class TypeStrVisitor(SyntheticTypeVisitor[str]):
    """Visitor for pretty-printing types into strings.

    This is mostly for debugging/testing.

    Do not preserve original formatting.

    Notes:
     - Represent unbound types as Foo? or Foo?[...].
     - Represent the NoneTyp type as None.
    """

    def __init__(self, id_mapper: Optional[IdMapper] = None) -> None:
        self.id_mapper = id_mapper

    def visit_unbound_type(self, t: UnboundType)-> str:
        s = t.name + '?'
        if t.args != []:
            s += '[{}]'.format(self.list_str(t.args))
        return s

    def visit_type_list(self, t: TypeList) -> str:
        return '<TypeList {}>'.format(self.list_str(t.items))

    def visit_callable_argument(self, t: CallableArgument) -> str:
        typ = t.typ.accept(self)
        if t.name is None:
            return "{}({})".format(t.constructor, typ)
        else:
            return "{}({}, {})".format(t.constructor, typ, t.name)

    def visit_any(self, t: AnyType) -> str:
        return 'Any'

    def visit_none_type(self, t: NoneTyp) -> str:
        return "None"

    def visit_uninhabited_type(self, t: UninhabitedType) -> str:
        return "<nothing>"

    def visit_erased_type(self, t: ErasedType) -> str:
        return "<Erased>"

    def visit_deleted_type(self, t: DeletedType) -> str:
        if t.source is None:
            return "<Deleted>"
        else:
            return "<Deleted '{}'>".format(t.source)

    def visit_instance(self, t: Instance) -> str:
        if t.type is not None:
            s = t.type.fullname() or t.type.name() or '<???>'
        else:
            s = '<?>'
        if t.erased:
            s += '*'
        if t.args != []:
            s += '[{}]'.format(self.list_str(t.args))
        if self.id_mapper:
            s += '<{}>'.format(self.id_mapper.id(t.type))
        return s

    def visit_type_var(self, t: TypeVarType) -> str:
        if t.name is None:
            # Anonymous type variable type (only numeric id).
            s = '`{}'.format(t.id)
        else:
            # Named type variable type.
            s = '{}`{}'.format(t.name, t.id)
        if self.id_mapper and t.upper_bound:
            s += '(upper_bound={})'.format(t.upper_bound.accept(self))
        return s

    def visit_callable_type(self, t: CallableType) -> str:
        s = ''
        bare_asterisk = False
        for i in range(len(t.arg_types)):
            if s != '':
                s += ', '
            if t.arg_kinds[i] in (ARG_NAMED, ARG_NAMED_OPT) and not bare_asterisk:
                s += '*, '
                bare_asterisk = True
            if t.arg_kinds[i] == ARG_STAR:
                s += '*'
            if t.arg_kinds[i] == ARG_STAR2:
                s += '**'
            name = t.arg_names[i]
            if name:
                s += name + ': '
            s += t.arg_types[i].accept(self)
            if t.arg_kinds[i] in (ARG_OPT, ARG_NAMED_OPT):
                s += ' ='

        s = '({})'.format(s)

        if not isinstance(t.ret_type, NoneTyp):
            s += ' -> {}'.format(t.ret_type.accept(self))

        if t.variables:
            vs = []
            # We reimplement TypeVarDef.__repr__ here in order to support id_mapper.
            for var in t.variables:
                if var.values:
                    vals = '({})'.format(', '.join(val.accept(self) for val in var.values))
                    vs.append('{} in {}'.format(var.name, vals))
                elif not is_named_instance(var.upper_bound, 'builtins.object'):
                    vs.append('{} <: {}'.format(var.name, var.upper_bound.accept(self)))
                else:
                    vs.append(var.name)
            s = '{} {}'.format('[{}]'.format(', '.join(vs)), s)

        return 'def {}'.format(s)

    def visit_overloaded(self, t: Overloaded) -> str:
        a = []
        for i in t.items():
            a.append(i.accept(self))
        return 'Overload({})'.format(', '.join(a))

    def visit_tuple_type(self, t: TupleType) -> str:
        s = self.list_str(t.items)
        if t.fallback and t.fallback.type:
            fallback_name = t.fallback.type.fullname()
            if fallback_name != 'builtins.tuple':
                return 'Tuple[{}, fallback={}]'.format(s, t.fallback.accept(self))
        return 'Tuple[{}]'.format(s)

    def visit_typeddict_type(self, t: TypedDictType) -> str:
        def item_str(name: str, typ: str) -> str:
            if name in t.required_keys:
                return '{!r}: {}'.format(name, typ)
            else:
                return '{!r}?: {}'.format(name, typ)

        s = '{' + ', '.join(item_str(name, typ.accept(self))
                            for name, typ in t.items.items()) + '}'
        prefix = ''
        suffix = ''
        if t.fallback and t.fallback.type:
            if t.fallback.type.fullname() != 'typing.Mapping':
                prefix = repr(t.fallback.type.fullname()) + ', '
            else:
                suffix = ', fallback={}'.format(t.fallback.accept(self))
        return 'TypedDict({}{}{})'.format(prefix, s, suffix)

    def visit_star_type(self, t: StarType) -> str:
        s = t.type.accept(self)
        return '*{}'.format(s)

    def visit_union_type(self, t: UnionType) -> str:
        s = self.list_str(t.items)
        return 'Union[{}]'.format(s)

    def visit_partial_type(self, t: PartialType) -> str:
        if t.type is None:
            return '<partial None>'
        else:
            return '<partial {}[{}]>'.format(t.type.name(),
                                             ', '.join(['?'] * len(t.type.type_vars)))

    def visit_ellipsis_type(self, t: EllipsisType) -> str:
        return '...'

    def visit_type_type(self, t: TypeType) -> str:
        return 'Type[{}]'.format(t.item.accept(self))

    def visit_forwardref_type(self, t: ForwardRef) -> str:
        if t.resolved:
            return '~{}'.format(t.resolved.accept(self))
        else:
            return '~{}'.format(t.unbound.accept(self))

    def list_str(self, a: List[Type]) -> str:
        """Convert items of an array to strings (pretty-print types)
        and join the results with commas.
        """
        res = []
        for t in a:
            if isinstance(t, Type):
                res.append(t.accept(self))
            else:
                res.append(str(t))
        return ', '.join(res)


def strip_type(typ: Type) -> Type:
    """Make a copy of type without 'debugging info' (function name)."""

    if isinstance(typ, CallableType):
        return typ.copy_modified(name=None)
    elif isinstance(typ, Overloaded):
        return Overloaded([cast(CallableType, strip_type(item))
                           for item in typ.items()])
    else:
        return typ


def is_named_instance(t: Type, fullname: str) -> bool:
    return (isinstance(t, Instance) and
            t.type is not None and
            t.type.fullname() == fullname)


def copy_type(t: Type) -> Type:
    """
    Build a copy of the type; used to mutate the copy with truthiness information
    """
    # We'd like to just do a copy.copy(), but mypyc types aren't
    # pickleable so we hack around it by manually creating a new type
    # and copying everything in with replace_object_state.
    typ = type(t)
    nt = typ.__new__(typ)
    replace_object_state(nt, t, copy_dict=True)
    return nt


def true_only(t: Type) -> Type:
    """
    Restricted version of t with only True-ish values
    """
    if not t.can_be_true:
        # All values of t are False-ish, so there are no true values in it
        return UninhabitedType(line=t.line, column=t.column)
    elif not t.can_be_false:
        # All values of t are already True-ish, so true_only is idempotent in this case
        return t
    elif isinstance(t, UnionType):
        # The true version of a union type is the union of the true versions of its components
        new_items = [true_only(item) for item in t.items]
        return UnionType.make_simplified_union(new_items, line=t.line, column=t.column)
    else:
        new_t = copy_type(t)
        new_t.can_be_false = False
        return new_t


def false_only(t: Type) -> Type:
    """
    Restricted version of t with only False-ish values
    """
    if not t.can_be_false:
        # All values of t are True-ish, so there are no false values in it
        return UninhabitedType(line=t.line)
    elif not t.can_be_true:
        # All values of t are already False-ish, so false_only is idempotent in this case
        return t
    elif isinstance(t, UnionType):
        # The false version of a union type is the union of the false versions of its components
        new_items = [false_only(item) for item in t.items]
        return UnionType.make_simplified_union(new_items, line=t.line, column=t.column)
    else:
        new_t = copy_type(t)
        new_t.can_be_true = False
        return new_t


def true_or_false(t: Type) -> Type:
    """
    Unrestricted version of t with both True-ish and False-ish values
    """
    if isinstance(t, UnionType):
        new_items = [true_or_false(item) for item in t.items]
        return UnionType.make_simplified_union(new_items, line=t.line, column=t.column)

    new_t = copy_type(t)
    new_t.can_be_true = new_t.can_be_true_default()
    new_t.can_be_false = new_t.can_be_false_default()
    return new_t


def function_type(func: mypy.nodes.FuncBase, fallback: Instance) -> FunctionLike:
    if func.type:
        assert isinstance(func.type, FunctionLike)
        return func.type
    else:
        # Implicit type signature with dynamic types.
        # Overloaded functions always have a signature, so func must be an ordinary function.
        assert isinstance(func, mypy.nodes.FuncItem), str(func)
        return callable_type(func, fallback)


def callable_type(fdef: mypy.nodes.FuncItem, fallback: Instance,
                  ret_type: Optional[Type] = None) -> CallableType:
    return CallableType(
        [AnyType(TypeOfAny.unannotated)] * len(fdef.arg_names),
        fdef.arg_kinds,
        [None if argument_elide_name(n) else n for n in fdef.arg_names],
        ret_type or AnyType(TypeOfAny.unannotated),
        fallback,
        name=fdef.name(),
        line=fdef.line,
        column=fdef.column,
        implicit=True,
    )


def get_typ_args(tp: Type) -> List[Type]:
    """Get all type arguments from a parametrizable Type."""
    if not isinstance(tp, (Instance, UnionType, TupleType, CallableType)):
        return []
    typ_args = (tp.args if isinstance(tp, Instance) else
                tp.items if not isinstance(tp, CallableType) else
                tp.arg_types + [tp.ret_type])
    return typ_args


def set_typ_args(tp: Type, new_args: List[Type], line: int = -1, column: int = -1) -> Type:
    """Return a copy of a parametrizable Type with arguments set to new_args."""
    if isinstance(tp, Instance):
        return Instance(tp.type, new_args, line, column)
    if isinstance(tp, TupleType):
        return tp.copy_modified(items=new_args)
    if isinstance(tp, UnionType):
        return UnionType(new_args, line, column)
    if isinstance(tp, CallableType):
        return tp.copy_modified(arg_types=new_args[:-1], ret_type=new_args[-1],
                                line=line, column=column)
    return tp


def get_type_vars(typ: Type) -> List[TypeVarType]:
    """Get all type variables that are present in an already analyzed type,
    without duplicates, in order of textual appearance.
    Similar to TypeAnalyser.get_type_var_names.
    """
    all_vars = []  # type: List[TypeVarType]
    for t in get_typ_args(typ):
        if isinstance(t, TypeVarType):
            all_vars.append(t)
        else:
            all_vars.extend(get_type_vars(t))
    # Remove duplicates while preserving order
    included = set()  # type: Set[TypeVarId]
    tvars = []
    for var in all_vars:
        if var.id not in included:
            tvars.append(var)
            included.add(var.id)
    return tvars


def flatten_nested_unions(types: Iterable[Type]) -> List[Type]:
    """Flatten nested unions in a type list."""
    flat_items = []  # type: List[Type]
    for tp in types:
        if isinstance(tp, UnionType):
            flat_items.extend(flatten_nested_unions(tp.items))
        else:
            flat_items.append(tp)
    return flat_items


def union_items(typ: Type) -> List[Type]:
    """Return the flattened items of a union type.

    For non-union types, return a list containing just the argument.
    """
    if isinstance(typ, UnionType):
        items = []
        for item in typ.items:
            items.extend(union_items(item))
        return items
    else:
        return [typ]


names = globals().copy()
names.pop('NOT_READY', None)
deserialize_map = {
    key: obj.deserialize  # type: ignore
    for key, obj in names.items()
    if isinstance(obj, type) and issubclass(obj, Type) and obj is not Type
}