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