-
-
Notifications
You must be signed in to change notification settings - Fork 2.7k
/
expandtype.py
595 lines (509 loc) · 23.5 KB
/
expandtype.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
from __future__ import annotations
from typing import Final, Iterable, Mapping, Sequence, TypeVar, cast, overload
from mypy.nodes import ARG_POS, ARG_STAR, ArgKind, Var
from mypy.state import state
from mypy.types import (
ANY_STRATEGY,
AnyType,
BoolTypeQuery,
CallableType,
DeletedType,
ErasedType,
FunctionLike,
Instance,
LiteralType,
NoneType,
Overloaded,
Parameters,
ParamSpecFlavor,
ParamSpecType,
PartialType,
ProperType,
TrivialSyntheticTypeTranslator,
TupleType,
Type,
TypeAliasType,
TypedDictType,
TypeType,
TypeVarId,
TypeVarLikeType,
TypeVarTupleType,
TypeVarType,
UnboundType,
UninhabitedType,
UnionType,
UnpackType,
flatten_nested_tuples,
flatten_nested_unions,
get_proper_type,
split_with_prefix_and_suffix,
)
from mypy.typevartuples import find_unpack_in_list, split_with_instance
# Solving the import cycle:
import mypy.type_visitor # ruff: isort: skip
# WARNING: these functions should never (directly or indirectly) depend on
# is_subtype(), meet_types(), join_types() etc.
# TODO: add a static dependency test for this.
@overload
def expand_type(typ: CallableType, env: Mapping[TypeVarId, Type]) -> CallableType:
...
@overload
def expand_type(typ: ProperType, env: Mapping[TypeVarId, Type]) -> ProperType:
...
@overload
def expand_type(typ: Type, env: Mapping[TypeVarId, Type]) -> Type:
...
def expand_type(typ: Type, env: Mapping[TypeVarId, Type]) -> Type:
"""Substitute any type variable references in a type given by a type
environment.
"""
return typ.accept(ExpandTypeVisitor(env))
@overload
def expand_type_by_instance(typ: CallableType, instance: Instance) -> CallableType:
...
@overload
def expand_type_by_instance(typ: ProperType, instance: Instance) -> ProperType:
...
@overload
def expand_type_by_instance(typ: Type, instance: Instance) -> Type:
...
def expand_type_by_instance(typ: Type, instance: Instance) -> Type:
"""Substitute type variables in type using values from an Instance.
Type variables are considered to be bound by the class declaration."""
if not instance.args:
return typ
else:
variables: dict[TypeVarId, Type] = {}
if instance.type.has_type_var_tuple_type:
assert instance.type.type_var_tuple_prefix is not None
assert instance.type.type_var_tuple_suffix is not None
args_prefix, args_middle, args_suffix = split_with_instance(instance)
tvars_prefix, tvars_middle, tvars_suffix = split_with_prefix_and_suffix(
tuple(instance.type.defn.type_vars),
instance.type.type_var_tuple_prefix,
instance.type.type_var_tuple_suffix,
)
tvar = tvars_middle[0]
assert isinstance(tvar, TypeVarTupleType)
variables = {tvar.id: TupleType(list(args_middle), tvar.tuple_fallback)}
instance_args = args_prefix + args_suffix
tvars = tvars_prefix + tvars_suffix
else:
tvars = tuple(instance.type.defn.type_vars)
instance_args = instance.args
for binder, arg in zip(tvars, instance_args):
assert isinstance(binder, TypeVarLikeType)
variables[binder.id] = arg
return expand_type(typ, variables)
F = TypeVar("F", bound=FunctionLike)
def freshen_function_type_vars(callee: F) -> F:
"""Substitute fresh type variables for generic function type variables."""
if isinstance(callee, CallableType):
if not callee.is_generic():
return cast(F, callee)
tvs = []
tvmap: dict[TypeVarId, Type] = {}
for v in callee.variables:
tv = v.new_unification_variable(v)
tvs.append(tv)
tvmap[v.id] = tv
fresh = expand_type(callee, tvmap).copy_modified(variables=tvs)
return cast(F, fresh)
else:
assert isinstance(callee, Overloaded)
fresh_overload = Overloaded([freshen_function_type_vars(item) for item in callee.items])
return cast(F, fresh_overload)
class HasGenericCallable(BoolTypeQuery):
def __init__(self) -> None:
super().__init__(ANY_STRATEGY)
def visit_callable_type(self, t: CallableType) -> bool:
return t.is_generic() or super().visit_callable_type(t)
# Share a singleton since this is performance sensitive
has_generic_callable: Final = HasGenericCallable()
T = TypeVar("T", bound=Type)
def freshen_all_functions_type_vars(t: T) -> T:
result: Type
has_generic_callable.reset()
if not t.accept(has_generic_callable):
return t # Fast path to avoid expensive freshening
else:
result = t.accept(FreshenCallableVisitor())
assert isinstance(result, type(t))
return result
class FreshenCallableVisitor(mypy.type_visitor.TypeTranslator):
def visit_callable_type(self, t: CallableType) -> Type:
result = super().visit_callable_type(t)
assert isinstance(result, ProperType) and isinstance(result, CallableType)
return freshen_function_type_vars(result)
def visit_type_alias_type(self, t: TypeAliasType) -> Type:
# Same as for ExpandTypeVisitor
return t.copy_modified(args=[arg.accept(self) for arg in t.args])
class ExpandTypeVisitor(TrivialSyntheticTypeTranslator):
"""Visitor that substitutes type variables with values."""
variables: Mapping[TypeVarId, Type] # TypeVar id -> TypeVar value
def __init__(self, variables: Mapping[TypeVarId, Type]) -> None:
self.variables = variables
def visit_unbound_type(self, t: UnboundType) -> Type:
return t
def visit_any(self, t: AnyType) -> Type:
return t
def visit_none_type(self, t: NoneType) -> Type:
return t
def visit_uninhabited_type(self, t: UninhabitedType) -> Type:
return t
def visit_deleted_type(self, t: DeletedType) -> Type:
return t
def visit_erased_type(self, t: ErasedType) -> Type:
# This may happen during type inference if some function argument
# type is a generic callable, and its erased form will appear in inferred
# constraints, then solver may check subtyping between them, which will trigger
# unify_generic_callables(), this is why we can get here. Another example is
# when inferring type of lambda in generic context, the lambda body contains
# a generic method in generic class.
return t
def visit_instance(self, t: Instance) -> Type:
args = self.expand_types_with_unpack(list(t.args))
if isinstance(args, list):
return t.copy_modified(args=args)
else:
return args
def visit_type_var(self, t: TypeVarType) -> Type:
# Normally upper bounds can't contain other type variables, the only exception is
# special type variable Self`0 <: C[T, S], where C is the class where Self is used.
if t.id.raw_id == 0:
t = t.copy_modified(upper_bound=t.upper_bound.accept(self))
repl = self.variables.get(t.id, t)
if isinstance(repl, ProperType) and isinstance(repl, Instance):
# TODO: do we really need to do this?
# If I try to remove this special-casing ~40 tests fail on reveal_type().
return repl.copy_modified(last_known_value=None)
return repl
def visit_param_spec(self, t: ParamSpecType) -> Type:
# Set prefix to something empty, so we don't duplicate it below.
repl = self.variables.get(t.id, t.copy_modified(prefix=Parameters([], [], [])))
if isinstance(repl, ParamSpecType):
return repl.copy_modified(
flavor=t.flavor,
prefix=t.prefix.copy_modified(
arg_types=self.expand_types(t.prefix.arg_types + repl.prefix.arg_types),
arg_kinds=t.prefix.arg_kinds + repl.prefix.arg_kinds,
arg_names=t.prefix.arg_names + repl.prefix.arg_names,
),
)
elif isinstance(repl, Parameters):
assert t.flavor == ParamSpecFlavor.BARE
return Parameters(
self.expand_types(t.prefix.arg_types + repl.arg_types),
t.prefix.arg_kinds + repl.arg_kinds,
t.prefix.arg_names + repl.arg_names,
variables=[*t.prefix.variables, *repl.variables],
)
else:
# TODO: replace this with "assert False"
return repl
def visit_type_var_tuple(self, t: TypeVarTupleType) -> Type:
# Sometimes solver may need to expand a type variable with (a copy of) itself
# (usually together with other TypeVars, but it is hard to filter out TypeVarTuples).
repl = self.variables[t.id]
if isinstance(repl, TypeVarTupleType):
return repl
raise NotImplementedError
def visit_unpack_type(self, t: UnpackType) -> Type:
# It is impossible to reasonably implement visit_unpack_type, because
# unpacking inherently expands to something more like a list of types.
#
# Relevant sections that can call unpack should call expand_unpack()
# instead.
# However, if the item is a variadic tuple, we can simply carry it over.
# it is hard to assert this without getting proper type.
return UnpackType(t.type.accept(self))
def expand_unpack(self, t: UnpackType) -> list[Type] | Instance | AnyType | None:
return expand_unpack_with_variables(t, self.variables)
def visit_parameters(self, t: Parameters) -> Type:
return t.copy_modified(arg_types=self.expand_types(t.arg_types))
def interpolate_args_for_unpack(
self, t: CallableType, var_arg: UnpackType
) -> tuple[list[str | None], list[ArgKind], list[Type]]:
star_index = t.arg_kinds.index(ARG_STAR)
# We have something like Unpack[Tuple[X1, X2, Unpack[Ts], Y1, Y2]]
var_arg_type = get_proper_type(var_arg.type)
if isinstance(var_arg_type, TupleType):
expanded_tuple = var_arg_type.accept(self)
# TODO: handle the case that expanded_tuple is a variable length tuple.
assert isinstance(expanded_tuple, ProperType) and isinstance(expanded_tuple, TupleType)
expanded_items = expanded_tuple.items
else:
expanded_items_res = self.expand_unpack(var_arg)
if isinstance(expanded_items_res, list):
expanded_items = expanded_items_res
elif (
isinstance(expanded_items_res, Instance)
and expanded_items_res.type.fullname == "builtins.tuple"
):
# TODO: We shouldnt't simply treat this as a *arg because of suffix handling
# (there cannot be positional args after a *arg)
arg_types = (
t.arg_types[:star_index]
+ [expanded_items_res.args[0]]
+ t.arg_types[star_index + 1 :]
)
return (t.arg_names, t.arg_kinds, arg_types)
else:
return (t.arg_names, t.arg_kinds, t.arg_types)
expanded_unpack_index = find_unpack_in_list(expanded_items)
# This is the case where we just have Unpack[Tuple[X1, X2, X3]]
# (for example if either the tuple had no unpacks, or the unpack in the
# tuple got fully expanded to something with fixed length)
if expanded_unpack_index is None:
arg_names = (
t.arg_names[:star_index]
+ [None] * len(expanded_items)
+ t.arg_names[star_index + 1 :]
)
arg_kinds = (
t.arg_kinds[:star_index]
+ [ARG_POS] * len(expanded_items)
+ t.arg_kinds[star_index + 1 :]
)
arg_types = (
self.expand_types(t.arg_types[:star_index])
+ expanded_items
+ self.expand_types(t.arg_types[star_index + 1 :])
)
else:
# If Unpack[Ts] simplest form still has an unpack or is a
# homogenous tuple, then only the prefix can be represented as
# positional arguments, and we pass Tuple[Unpack[Ts-1], Y1, Y2]
# as the star arg, for example.
expanded_unpack = expanded_items[expanded_unpack_index]
assert isinstance(expanded_unpack, UnpackType)
# Extract the typevartuple so we can get a tuple fallback from it.
expanded_unpacked_tvt = expanded_unpack.type
if isinstance(expanded_unpacked_tvt, TypeVarTupleType):
fallback = expanded_unpacked_tvt.tuple_fallback
else:
# This can happen when tuple[Any, ...] is used to "patch" a variadic
# generic type without type arguments provided.
assert isinstance(expanded_unpacked_tvt, ProperType)
assert isinstance(expanded_unpacked_tvt, Instance)
assert expanded_unpacked_tvt.type.fullname == "builtins.tuple"
fallback = expanded_unpacked_tvt
prefix_len = expanded_unpack_index
arg_names = t.arg_names[:star_index] + [None] * prefix_len + t.arg_names[star_index:]
arg_kinds = (
t.arg_kinds[:star_index] + [ARG_POS] * prefix_len + t.arg_kinds[star_index:]
)
arg_types = (
self.expand_types(t.arg_types[:star_index])
+ expanded_items[:prefix_len]
# Constructing the Unpack containing the tuple without the prefix.
+ [
UnpackType(TupleType(expanded_items[prefix_len:], fallback))
if len(expanded_items) - prefix_len > 1
else expanded_items[0]
]
+ self.expand_types(t.arg_types[star_index + 1 :])
)
return (arg_names, arg_kinds, arg_types)
def visit_callable_type(self, t: CallableType) -> CallableType:
param_spec = t.param_spec()
if param_spec is not None:
repl = self.variables.get(param_spec.id)
# If a ParamSpec in a callable type is substituted with a
# callable type, we can't use normal substitution logic,
# since ParamSpec is actually split into two components
# *P.args and **P.kwargs in the original type. Instead, we
# must expand both of them with all the argument types,
# kinds and names in the replacement. The return type in
# the replacement is ignored.
if isinstance(repl, Parameters):
# We need to expand both the types in the prefix and the ParamSpec itself
t = t.expand_param_spec(repl)
return t.copy_modified(
arg_types=self.expand_types(t.arg_types),
ret_type=t.ret_type.accept(self),
type_guard=(t.type_guard.accept(self) if t.type_guard is not None else None),
)
elif isinstance(repl, ParamSpecType):
# We're substituting one ParamSpec for another; this can mean that the prefix
# changes, e.g. substitute Concatenate[int, P] in place of Q.
prefix = repl.prefix
clean_repl = repl.copy_modified(prefix=Parameters([], [], []))
return t.copy_modified(
arg_types=self.expand_types(t.arg_types[:-2] + prefix.arg_types)
+ [
clean_repl.with_flavor(ParamSpecFlavor.ARGS),
clean_repl.with_flavor(ParamSpecFlavor.KWARGS),
],
arg_kinds=t.arg_kinds[:-2] + prefix.arg_kinds + t.arg_kinds[-2:],
arg_names=t.arg_names[:-2] + prefix.arg_names + t.arg_names[-2:],
ret_type=t.ret_type.accept(self),
from_concatenate=t.from_concatenate or bool(repl.prefix.arg_types),
)
var_arg = t.var_arg()
if var_arg is not None and isinstance(var_arg.typ, UnpackType):
arg_names, arg_kinds, arg_types = self.interpolate_args_for_unpack(t, var_arg.typ)
else:
arg_names = t.arg_names
arg_kinds = t.arg_kinds
arg_types = self.expand_types(t.arg_types)
return t.copy_modified(
arg_types=arg_types,
arg_names=arg_names,
arg_kinds=arg_kinds,
ret_type=t.ret_type.accept(self),
type_guard=(t.type_guard.accept(self) if t.type_guard is not None else None),
)
def visit_overloaded(self, t: Overloaded) -> Type:
items: list[CallableType] = []
for item in t.items:
new_item = item.accept(self)
assert isinstance(new_item, ProperType)
assert isinstance(new_item, CallableType)
items.append(new_item)
return Overloaded(items)
def expand_types_with_unpack(
self, typs: Sequence[Type]
) -> list[Type] | AnyType | UninhabitedType | Instance:
"""Expands a list of types that has an unpack.
In corner cases, this can return a type rather than a list, in which case this
indicates use of Any or some error occurred earlier. In this case callers should
simply propagate the resulting type.
"""
# TODO: this will cause a crash on aliases like A = Tuple[int, Unpack[A]].
# Although it is unlikely anyone will write this, we should fail gracefully.
typs = flatten_nested_tuples(typs)
items: list[Type] = []
for item in typs:
if isinstance(item, UnpackType) and isinstance(item.type, TypeVarTupleType):
unpacked_items = self.expand_unpack(item)
if unpacked_items is None:
# TODO: better error, something like tuple of unknown?
return UninhabitedType()
elif isinstance(unpacked_items, Instance):
if len(typs) == 1:
return unpacked_items
else:
assert False, "Invalid unpack of variable length tuple"
elif isinstance(unpacked_items, AnyType):
return unpacked_items
else:
items.extend(unpacked_items)
else:
# Must preserve original aliases when possible.
items.append(item.accept(self))
return items
def visit_tuple_type(self, t: TupleType) -> Type:
items = self.expand_types_with_unpack(t.items)
if isinstance(items, list):
fallback = t.partial_fallback.accept(self)
assert isinstance(fallback, ProperType) and isinstance(fallback, Instance)
return t.copy_modified(items=items, fallback=fallback)
else:
return items
def visit_typeddict_type(self, t: TypedDictType) -> Type:
fallback = t.fallback.accept(self)
assert isinstance(fallback, ProperType) and isinstance(fallback, Instance)
return t.copy_modified(item_types=self.expand_types(t.items.values()), fallback=fallback)
def visit_literal_type(self, t: LiteralType) -> Type:
# TODO: Verify this implementation is correct
return t
def visit_union_type(self, t: UnionType) -> Type:
expanded = self.expand_types(t.items)
# After substituting for type variables in t.items, some resulting types
# might be subtypes of others, however calling make_simplified_union()
# can cause recursion, so we just remove strict duplicates.
simplified = UnionType.make_union(
remove_trivial(flatten_nested_unions(expanded)), t.line, t.column
)
# This call to get_proper_type() is unfortunate but is required to preserve
# the invariant that ProperType will stay ProperType after applying expand_type(),
# otherwise a single item union of a type alias will break it. Note this should not
# cause infinite recursion since pathological aliases like A = Union[A, B] are
# banned at the semantic analysis level.
return get_proper_type(simplified)
def visit_partial_type(self, t: PartialType) -> Type:
return t
def visit_type_type(self, t: TypeType) -> Type:
# TODO: Verify that the new item type is valid (instance or
# union of instances or Any). Sadly we can't report errors
# here yet.
item = t.item.accept(self)
return TypeType.make_normalized(item)
def visit_type_alias_type(self, t: TypeAliasType) -> Type:
# Target of the type alias cannot contain type variables (not bound by the type
# alias itself), so we just expand the arguments.
args = self.expand_types_with_unpack(t.args)
if isinstance(args, list):
return t.copy_modified(args=args)
else:
return args
def expand_types(self, types: Iterable[Type]) -> list[Type]:
a: list[Type] = []
for t in types:
a.append(t.accept(self))
return a
def expand_unpack_with_variables(
t: UnpackType, variables: Mapping[TypeVarId, Type]
) -> list[Type] | Instance | AnyType | None:
"""May return either a list of types to unpack to, any, or a single
variable length tuple. The latter may not be valid in all contexts.
"""
if isinstance(t.type, TypeVarTupleType):
repl = get_proper_type(variables.get(t.type.id, t))
if isinstance(repl, TupleType):
return repl.items
elif isinstance(repl, Instance) and repl.type.fullname == "builtins.tuple":
return repl
elif isinstance(repl, AnyType):
# tuple[Any, ...] would be better, but we don't have
# the type info to construct that type here.
return repl
elif isinstance(repl, TypeVarTupleType):
return [UnpackType(typ=repl)]
elif isinstance(repl, UnpackType):
return [repl]
elif isinstance(repl, UninhabitedType):
return None
else:
raise NotImplementedError(f"Invalid type replacement to expand: {repl}")
else:
raise NotImplementedError(f"Invalid type to expand: {t.type}")
@overload
def expand_self_type(var: Var, typ: ProperType, replacement: ProperType) -> ProperType:
...
@overload
def expand_self_type(var: Var, typ: Type, replacement: Type) -> Type:
...
def expand_self_type(var: Var, typ: Type, replacement: Type) -> Type:
"""Expand appearances of Self type in a variable type."""
if var.info.self_type is not None and not var.is_property:
return expand_type(typ, {var.info.self_type.id: replacement})
return typ
def remove_trivial(types: Iterable[Type]) -> list[Type]:
"""Make trivial simplifications on a list of types without calling is_subtype().
This makes following simplifications:
* Remove bottom types (taking into account strict optional setting)
* Remove everything else if there is an `object`
* Remove strict duplicate types
"""
removed_none = False
new_types = []
all_types = set()
for t in types:
p_t = get_proper_type(t)
if isinstance(p_t, UninhabitedType):
continue
if isinstance(p_t, NoneType) and not state.strict_optional:
removed_none = True
continue
if isinstance(p_t, Instance) and p_t.type.fullname == "builtins.object":
return [p_t]
if p_t not in all_types:
new_types.append(t)
all_types.add(p_t)
if new_types:
return new_types
if removed_none:
return [NoneType()]
return [UninhabitedType()]