1"""
2A shared state for all TypeInfos that holds global cache and dependency information,
3and potentially other mutable TypeInfo state. This module contains mutable global state.
4"""
5
6from typing import Dict, Set, Tuple, Optional, List
7from typing_extensions import ClassVar, Final
8
9from mypy.nodes import TypeInfo
10from mypy.types import Instance, TypeAliasType, get_proper_type, Type
11from mypy.server.trigger import make_trigger
12from mypy import state
13
14# Represents that the 'left' instance is a subtype of the 'right' instance
15SubtypeRelationship = Tuple[Instance, Instance]
16
17# A tuple encoding the specific conditions under which we performed the subtype check.
18# (e.g. did we want a proper subtype? A regular subtype while ignoring variance?)
19SubtypeKind = Tuple[bool, ...]
20
21# A cache that keeps track of whether the given TypeInfo is a part of a particular
22# subtype relationship
23SubtypeCache = Dict[TypeInfo, Dict[SubtypeKind, Set[SubtypeRelationship]]]
24
25
26class TypeState:
27    """This class provides subtype caching to improve performance of subtype checks.
28    It also holds protocol fine grained dependencies.
29
30    Note: to avoid leaking global state, 'reset_all_subtype_caches()' should be called
31    after a build has finished and after a daemon shutdown. This subtype cache only exists for
32    performance reasons, resetting subtype caches for a class has no semantic effect.
33    The protocol dependencies however are only stored here, and shouldn't be deleted unless
34    not needed any more (e.g. during daemon shutdown).
35    """
36    # '_subtype_caches' keeps track of (subtype, supertype) pairs where supertypes are
37    # instances of the given TypeInfo. The cache also keeps track of whether the check
38    # was done in strict optional mode and of the specific *kind* of subtyping relationship,
39    # which we represent as an arbitrary hashable tuple.
40    # We need the caches, since subtype checks for structural types are very slow.
41    _subtype_caches = {}  # type: Final[SubtypeCache]
42
43    # This contains protocol dependencies generated after running a full build,
44    # or after an update. These dependencies are special because:
45    #   * They are a global property of the program; i.e. some dependencies for imported
46    #     classes can be generated in the importing modules.
47    #   * Because of the above, they are serialized separately, after a full run,
48    #     or a full update.
49    # `proto_deps` can be None if after deserialization it turns out that they are
50    # inconsistent with the other cache files (or an error occurred during deserialization).
51    # A blocking error will be generated in this case, since we can't proceed safely.
52    # For the description of kinds of protocol dependencies and corresponding examples,
53    # see _snapshot_protocol_deps.
54    proto_deps = {}  # type: ClassVar[Optional[Dict[str, Set[str]]]]
55
56    # Protocols (full names) a given class attempted to implement.
57    # Used to calculate fine grained protocol dependencies and optimize protocol
58    # subtype cache invalidation in fine grained mode. For example, if we pass a value
59    # of type a.A to a function expecting something compatible with protocol p.P,
60    # we'd have 'a.A' -> {'p.P', ...} in the map. This map is flushed after every incremental
61    # update.
62    _attempted_protocols = {}  # type: Final[Dict[str, Set[str]]]
63    # We also snapshot protocol members of the above protocols. For example, if we pass
64    # a value of type a.A to a function expecting something compatible with Iterable, we'd have
65    # 'a.A' -> {'__iter__', ...} in the map. This map is also flushed after every incremental
66    # update. This map is needed to only generate dependencies like <a.A.__iter__> -> <a.A>
67    # instead of a wildcard to avoid unnecessarily invalidating classes.
68    _checked_against_members = {}  # type: Final[Dict[str, Set[str]]]
69    # TypeInfos that appeared as a left type (subtype) in a subtype check since latest
70    # dependency snapshot update. This is an optimisation for fine grained mode; during a full
71    # run we only take a dependency snapshot at the very end, so this set will contain all
72    # subtype-checked TypeInfos. After a fine grained update however, we can gather only new
73    # dependencies generated from (typically) few TypeInfos that were subtype-checked
74    # (i.e. appeared as r.h.s. in an assignment or an argument in a function call in
75    # a re-checked target) during the update.
76    _rechecked_types = set()  # type: Final[Set[TypeInfo]]
77
78    # The two attributes below are assumption stacks for subtyping relationships between
79    # recursive type aliases. Normally, one would pass type assumptions as an additional
80    # arguments to is_subtype(), but this would mean updating dozens of related functions
81    # threading this through all callsites (see also comment for TypeInfo.assuming).
82    _assuming = []  # type: Final[List[Tuple[TypeAliasType, TypeAliasType]]]
83    _assuming_proper = []  # type: Final[List[Tuple[TypeAliasType, TypeAliasType]]]
84    # Ditto for inference of generic constraints against recursive type aliases.
85    _inferring = []  # type: Final[List[TypeAliasType]]
86
87    # N.B: We do all of the accesses to these properties through
88    # TypeState, instead of making these classmethods and accessing
89    # via the cls parameter, since mypyc can optimize accesses to
90    # Final attributes of a directly referenced type.
91
92    @staticmethod
93    def is_assumed_subtype(left: Type, right: Type) -> bool:
94        for (l, r) in reversed(TypeState._assuming):
95            if (get_proper_type(l) == get_proper_type(left)
96                    and get_proper_type(r) == get_proper_type(right)):
97                return True
98        return False
99
100    @staticmethod
101    def is_assumed_proper_subtype(left: Type, right: Type) -> bool:
102        for (l, r) in reversed(TypeState._assuming_proper):
103            if (get_proper_type(l) == get_proper_type(left)
104                    and get_proper_type(r) == get_proper_type(right)):
105                return True
106        return False
107
108    @staticmethod
109    def reset_all_subtype_caches() -> None:
110        """Completely reset all known subtype caches."""
111        TypeState._subtype_caches.clear()
112
113    @staticmethod
114    def reset_subtype_caches_for(info: TypeInfo) -> None:
115        """Reset subtype caches (if any) for a given supertype TypeInfo."""
116        if info in TypeState._subtype_caches:
117            TypeState._subtype_caches[info].clear()
118
119    @staticmethod
120    def reset_all_subtype_caches_for(info: TypeInfo) -> None:
121        """Reset subtype caches (if any) for a given supertype TypeInfo and its MRO."""
122        for item in info.mro:
123            TypeState.reset_subtype_caches_for(item)
124
125    @staticmethod
126    def is_cached_subtype_check(kind: SubtypeKind, left: Instance, right: Instance) -> bool:
127        info = right.type
128        if info not in TypeState._subtype_caches:
129            return False
130        cache = TypeState._subtype_caches[info]
131        key = (state.strict_optional,) + kind
132        if key not in cache:
133            return False
134        return (left, right) in cache[key]
135
136    @staticmethod
137    def record_subtype_cache_entry(kind: SubtypeKind,
138                                   left: Instance, right: Instance) -> None:
139        cache = TypeState._subtype_caches.setdefault(right.type, dict())
140        cache.setdefault((state.strict_optional,) + kind, set()).add((left, right))
141
142    @staticmethod
143    def reset_protocol_deps() -> None:
144        """Reset dependencies after a full run or before a daemon shutdown."""
145        TypeState.proto_deps = {}
146        TypeState._attempted_protocols.clear()
147        TypeState._checked_against_members.clear()
148        TypeState._rechecked_types.clear()
149
150    @staticmethod
151    def record_protocol_subtype_check(left_type: TypeInfo, right_type: TypeInfo) -> None:
152        assert right_type.is_protocol
153        TypeState._rechecked_types.add(left_type)
154        TypeState._attempted_protocols.setdefault(
155            left_type.fullname, set()).add(right_type.fullname)
156        TypeState._checked_against_members.setdefault(
157            left_type.fullname,
158            set()).update(right_type.protocol_members)
159
160    @staticmethod
161    def _snapshot_protocol_deps() -> Dict[str, Set[str]]:
162        """Collect protocol attribute dependencies found so far from registered subtype checks.
163
164        There are three kinds of protocol dependencies. For example, after a subtype check:
165
166            x: Proto = C()
167
168        the following dependencies will be generated:
169            1. ..., <SuperProto[wildcard]>, <Proto[wildcard]> -> <Proto>
170            2. ..., <B.attr>, <C.attr> -> <C> [for every attr in Proto members]
171            3. <C> -> Proto  # this one to invalidate the subtype cache
172
173        The first kind is generated immediately per-module in deps.py (see also an example there
174        for motivation why it is needed). While two other kinds are generated here after all
175        modules are type checked and we have recorded all the subtype checks. To understand these
176        two kinds, consider a simple example:
177
178            class A:
179                def __iter__(self) -> Iterator[int]:
180                    ...
181
182            it: Iterable[int] = A()
183
184        We add <a.A.__iter__> -> <a.A> to invalidate the assignment (module target in this case),
185        whenever the signature of a.A.__iter__ changes. We also add <a.A> -> typing.Iterable,
186        to invalidate the subtype caches of the latter. (Note that the same logic applies to
187        proper subtype checks, and calculating meets and joins, if this involves calling
188        'subtypes.is_protocol_implementation').
189        """
190        deps = {}  # type: Dict[str, Set[str]]
191        for info in TypeState._rechecked_types:
192            for attr in TypeState._checked_against_members[info.fullname]:
193                # The need for full MRO here is subtle, during an update, base classes of
194                # a concrete class may not be reprocessed, so not all <B.x> -> <C.x> deps
195                # are added.
196                for base_info in info.mro[:-1]:
197                    trigger = make_trigger('%s.%s' % (base_info.fullname, attr))
198                    if 'typing' in trigger or 'builtins' in trigger:
199                        # TODO: avoid everything from typeshed
200                        continue
201                    deps.setdefault(trigger, set()).add(make_trigger(info.fullname))
202            for proto in TypeState._attempted_protocols[info.fullname]:
203                trigger = make_trigger(info.fullname)
204                if 'typing' in trigger or 'builtins' in trigger:
205                    continue
206                # If any class that was checked against a protocol changes,
207                # we need to reset the subtype cache for the protocol.
208                #
209                # Note: strictly speaking, the protocol doesn't need to be
210                # re-checked, we only need to reset the cache, and its uses
211                # elsewhere are still valid (unless invalidated by other deps).
212                deps.setdefault(trigger, set()).add(proto)
213        return deps
214
215    @staticmethod
216    def update_protocol_deps(second_map: Optional[Dict[str, Set[str]]] = None) -> None:
217        """Update global protocol dependency map.
218
219        We update the global map incrementally, using a snapshot only from recently
220        type checked types. If second_map is given, update it as well. This is currently used
221        by FineGrainedBuildManager that maintains normal (non-protocol) dependencies.
222        """
223        assert TypeState.proto_deps is not None, (
224            "This should not be called after failed cache load")
225        new_deps = TypeState._snapshot_protocol_deps()
226        for trigger, targets in new_deps.items():
227            TypeState.proto_deps.setdefault(trigger, set()).update(targets)
228        if second_map is not None:
229            for trigger, targets in new_deps.items():
230                second_map.setdefault(trigger, set()).update(targets)
231        TypeState._rechecked_types.clear()
232        TypeState._attempted_protocols.clear()
233        TypeState._checked_against_members.clear()
234
235    @staticmethod
236    def add_all_protocol_deps(deps: Dict[str, Set[str]]) -> None:
237        """Add all known protocol dependencies to deps.
238
239        This is used by tests and debug output, and also when collecting
240        all collected or loaded dependencies as part of build.
241        """
242        TypeState.update_protocol_deps()  # just in case
243        if TypeState.proto_deps is not None:
244            for trigger, targets in TypeState.proto_deps.items():
245                deps.setdefault(trigger, set()).update(targets)
246
247
248def reset_global_state() -> None:
249    """Reset most existing global state.
250
251    Currently most of it is in this module. Few exceptions are strict optional status and
252    and functools.lru_cache.
253    """
254    TypeState.reset_all_subtype_caches()
255    TypeState.reset_protocol_deps()
256