Add subtype visitors

python · ilevkivskyi · Nov 8, 2019 · Aug 25, 2019 · Aug 25, 2019 · Nov 4, 2019
commit c32075bcfe1378eb4a6f9fa995eb28fb74fcfd6c
diff --git a/mypy/constraints.py b/mypy/constraints.py
@@ -7,7 +7,7 @@
     CallableType, Type, TypeVisitor, UnboundType, AnyType, NoneType, TypeVarType, Instance,
     TupleType, TypedDictType, UnionType, Overloaded, ErasedType, PartialType, DeletedType,
     UninhabitedType, TypeType, TypeVarId, TypeQuery, is_named_instance, TypeOfAny, LiteralType,
-    ProperType, get_proper_type
+    ProperType, get_proper_type, TypeAliasType
 )
 from mypy.maptype import map_instance_to_supertype
 import mypy.subtypes
@@ -89,6 +89,22 @@ def infer_constraints(template: Type, actual: Type,
 
     The constraints are represented as Constraint objects.
     """
+    if (isinstance(template, TypeAliasType) and isinstance(actual, TypeAliasType) and
+            template.is_recursive and actual.is_recursive):
+        # This case requires special care because it may cause infinite recursion.
+        assert template.alias is not None
+        if any(mypy.sametypes.is_same_type(template, t) for t in template.alias.inferring):
+            return []
+        template.alias.inferring.append(template)
+        res = _infer_constraints(template, actual, direction)
+        template.alias.inferring.pop()
+        return res
+    return _infer_constraints(template, actual, direction)
+
+
+def _infer_constraints(template: Type, actual: Type,
+                       direction: int) -> List[Constraint]:
+
     template = get_proper_type(template)
     actual = get_proper_type(actual)
 
@@ -485,6 +501,9 @@ def visit_union_type(self, template: UnionType) -> List[Constraint]:
         assert False, ("Unexpected UnionType in ConstraintBuilderVisitor"
                        " (should have been handled in infer_constraints)")
 
+    def visit_type_alias_type(self, template: TypeAliasType) -> List[Constraint]:
+        assert False, "This should be never called, got {}".format(template)
+
     def infer_against_any(self, types: Iterable[Type], any_type: AnyType) -> List[Constraint]:
         res = []  # type: List[Constraint]
         for t in types:

diff --git a/mypy/nodes.py b/mypy/nodes.py
@@ -2632,6 +2632,8 @@ def __getattribute__(self, attr: str) -> None:
 VAR_NO_INFO = FakeInfo('Var is lacking info')  # type: Final[TypeInfo]
 CLASSDEF_NO_INFO = FakeInfo('ClassDef is lacking info')  # type: Final[TypeInfo]
 FUNC_NO_INFO = FakeInfo('FuncBase for non-methods lack info')  # type: Final[TypeInfo]
+if TYPE_CHECKING:
+    TypeAliasType = mypy.types.TypeAliasType
 
 
 class TypeAlias(SymbolNode):
@@ -2735,6 +2737,9 @@ def __init__(self, target: 'mypy.types.Type', fullname: str, line: int, column:
         self.alias_tvars = alias_tvars
         self.no_args = no_args
         self.normalized = normalized
+        self.assuming = []  # type: List[Tuple[TypeAliasType, TypeAliasType]]
+        self.assuming_proper = []  # type: List[Tuple[TypeAliasType, TypeAliasType]]
+        self.inferring = []  # type: List[TypeAliasType]
         super().__init__(line, column)
 
     def name(self) -> str:

diff --git a/mypy/subtypes.py b/mypy/subtypes.py
@@ -1,13 +1,13 @@
 from contextlib import contextmanager
 
-from typing import Any, List, Optional, Callable, Tuple, Iterator, Set, Union, cast
+from typing import Any, List, Optional, Callable, Tuple, Iterator, Set, Union, cast, TypeVar
 from typing_extensions import Final
 
 from mypy.types import (
     Type, AnyType, UnboundType, TypeVisitor, FormalArgument, NoneType,
     Instance, TypeVarType, CallableType, TupleType, TypedDictType, UnionType, Overloaded,
     ErasedType, PartialType, DeletedType, UninhabitedType, TypeType, is_named_instance,
-    FunctionLike, TypeOfAny, LiteralType, ProperType, get_proper_type
+    FunctionLike, TypeOfAny, LiteralType, ProperType, get_proper_type, TypeAliasType
 )
 import mypy.applytype
 import mypy.constraints
@@ -63,6 +63,33 @@ def is_subtype(left: Type, right: Type,
     between the type arguments (e.g., A and B), taking the variance of the
     type var into account.
     """
+    if (isinstance(left, TypeAliasType) and isinstance(right, TypeAliasType) and
+            left.is_recursive and right.is_recursive):
+        # This case requires special care because it may cause infinite recursion.
+        assert right.alias is not None
+        for (l, r) in reversed(right.alias.assuming):
+            if (mypy.sametypes.is_same_type(l, left)
+                    and mypy.sametypes.is_same_type(r, right)):
+                return True
+        with pop_on_exit(right.alias.assuming, left, right):
+            return _is_subtype(left, right,
+                               ignore_type_params=ignore_type_params,
+                               ignore_pos_arg_names=ignore_pos_arg_names,
+                               ignore_declared_variance=ignore_declared_variance,
+                               ignore_promotions=ignore_promotions)
+    return _is_subtype(left, right,
+                       ignore_type_params=ignore_type_params,
+                       ignore_pos_arg_names=ignore_pos_arg_names,
+                       ignore_declared_variance=ignore_declared_variance,
+                       ignore_promotions=ignore_promotions)
+
+
+def _is_subtype(left: Type, right: Type,
+                *,
+                ignore_type_params: bool = False,
+                ignore_pos_arg_names: bool = False,
+                ignore_declared_variance: bool = False,
+                ignore_promotions: bool = False) -> bool:
     left = get_proper_type(left)
     right = get_proper_type(right)
 
@@ -433,10 +460,16 @@ def visit_type_type(self, left: TypeType) -> bool:
                 return metaclass is not None and self._is_subtype(metaclass, right)
         return False
 
+    def visit_type_alias_type(self, left: TypeAliasType) -> bool:
+        assert False, "This should be never called, got {}".format(left)
+
+
+T = TypeVar('T', Instance, TypeAliasType)
+
 
 @contextmanager
-def pop_on_exit(stack: List[Tuple[Instance, Instance]],
-                left: Instance, right: Instance) -> Iterator[None]:
+def pop_on_exit(stack: List[Tuple[T, T]],
+                left: T, right: T) -> Iterator[None]:
     stack.append((left, right))
     yield
     stack.pop()
@@ -1076,6 +1109,25 @@ def is_proper_subtype(left: Type, right: Type, *, ignore_promotions: bool = Fals
     If erase_instances is True, erase left instance *after* mapping it to supertype
     (this is useful for runtime isinstance() checks).
     """
+    if (isinstance(left, TypeAliasType) and isinstance(right, TypeAliasType) and
+            left.is_recursive and right.is_recursive):
+        # This case requires special care because it may cause infinite recursion.
+        assert right.alias is not None
+        for (l, r) in reversed(right.alias.assuming_proper):
+            if (mypy.sametypes.is_same_type(l, left)
+                    and mypy.sametypes.is_same_type(r, right)):
+                return True
+        with pop_on_exit(right.alias.assuming_proper, left, right):
+            return _is_proper_subtype(left, right,
+                                      ignore_promotions=ignore_promotions,
+                                      erase_instances=erase_instances)
+    return _is_proper_subtype(left, right,
+                              ignore_promotions=ignore_promotions,
+                              erase_instances=erase_instances)
+
+
+def _is_proper_subtype(left: Type, right: Type, *, ignore_promotions: bool = False,
+                       erase_instances: bool = False) -> bool:
     left = get_proper_type(left)
     right = get_proper_type(right)
 
@@ -1281,6 +1333,9 @@ def visit_type_type(self, left: TypeType) -> bool:
                 return metaclass is not None and self._is_proper_subtype(metaclass, right)
         return False
 
+    def visit_type_alias_type(self, left: TypeAliasType) -> bool:
+        assert False, "This should be never called, got {}".format(left)
+
 
 def is_more_precise(left: Type, right: Type, *, ignore_promotions: bool = False) -> bool:
     """Check if left is a more precise type than right.