Skip to content

Commit a54ffb7

Browse files
committed
Prevent quadratic runtime with generic overloads
Fixes python#20439
1 parent 5dc2840 commit a54ffb7

1 file changed

Lines changed: 85 additions & 53 deletions

File tree

‎mypy/checker.py‎

Lines changed: 85 additions & 53 deletions
Original file line numberDiff line numberDiff line change
@@ -1058,56 +1058,81 @@ def check_overlapping_overloads(self, defn: OverloadedFuncDef) -> None:
10581058
# decorator or if the implementation is untyped -- we gave up on the types.
10591059
impl_type = self.extract_callable_type(inner_type, defn.impl)
10601060

1061+
current_class = self.scope.active_class()
1062+
type_vars = current_class.defn.type_vars if current_class else []
1063+
signatures: list[CallableType | None] = []
1064+
expanded_signatures: list[list[CallableType] | None] = []
1065+
expanded_count = 0
1066+
with state.strict_optional_set(True):
1067+
for item in defn.items:
1068+
assert isinstance(item, Decorator)
1069+
sig = self.extract_callable_type(item.var.type, item)
1070+
signatures.append(sig)
1071+
if sig is None:
1072+
expanded_signatures.append(None)
1073+
continue
1074+
sig_expanded = expand_callable_variants(detach_callable(sig, type_vars))
1075+
expanded_signatures.append(sig_expanded)
1076+
expanded_count += len(sig_expanded)
1077+
del item
1078+
1079+
if expanded_count >= 200:
1080+
self.fail(message_registry.TOO_MANY_OVERLOADS, defn)
1081+
10611082
is_descriptor_get = defn.info and defn.name == "__get__"
1062-
for i, item in enumerate(defn.items):
1063-
assert isinstance(item, Decorator)
1064-
sig1 = self.extract_callable_type(item.var.type, item)
1083+
for i, sig1 in enumerate(signatures):
10651084
if sig1 is None:
10661085
continue
10671086

1068-
for j, item2 in enumerate(defn.items[i + 1 :]):
1069-
if j >= max_overload_count:
1070-
# Avoid quadratic blowup for large numbers of overloads.
1071-
break
1087+
if expanded_count < 200:
1088+
for j, sig2 in enumerate(signatures[i + 1 :]):
1089+
if j >= max_overload_count:
1090+
# Avoid quadratic blowup for large numbers of overloads.
1091+
break
10721092

1073-
assert isinstance(item2, Decorator)
1074-
sig2 = self.extract_callable_type(item2.var.type, item2)
1075-
if sig2 is None:
1076-
continue
1093+
if sig2 is None:
1094+
continue
10771095

1078-
if not are_argument_counts_overlapping(sig1, sig2):
1079-
continue
1096+
if not are_argument_counts_overlapping(sig1, sig2):
1097+
continue
10801098

1081-
if overload_can_never_match(sig1, sig2):
1082-
self.msg.overloaded_signature_will_never_match(i + 1, i + j + 2, item2.func)
1083-
elif not is_descriptor_get:
1084-
# Note: we force mypy to check overload signatures in strict-optional mode
1085-
# so we don't incorrectly report errors when a user tries typing an overload
1086-
# that happens to have a 'if the argument is None' fallback.
1087-
#
1088-
# For example, the following is fine in strict-optional mode but would throw
1089-
# the unsafe overlap error when strict-optional is disabled:
1090-
#
1091-
# @overload
1092-
# def foo(x: None) -> int: ...
1093-
# @overload
1094-
# def foo(x: str) -> str: ...
1095-
#
1096-
# See Python 2's map function for a concrete example of this kind of overload.
1097-
current_class = self.scope.active_class()
1098-
type_vars = current_class.defn.type_vars if current_class else []
1099-
with state.strict_optional_set(True):
1100-
if is_unsafe_overlapping_overload_signatures(sig1, sig2, type_vars):
1101-
flip_note = (
1102-
j == 0
1103-
and not is_unsafe_overlapping_overload_signatures(
1104-
sig2, sig1, type_vars
1099+
if overload_can_never_match(sig1, sig2):
1100+
ctx_item = defn.items[i + j + 1]
1101+
assert isinstance(ctx_item, Decorator)
1102+
self.msg.overloaded_signature_will_never_match(
1103+
i + 1, i + j + 2, ctx_item.func
1104+
)
1105+
elif not is_descriptor_get:
1106+
# Note: we force mypy to check overload signatures in strict-optional mode
1107+
# so we don't incorrectly report errors when a user tries typing an overload
1108+
# that happens to have a 'if the argument is None' fallback.
1109+
#
1110+
# For example, the following is fine in strict-optional mode but would throw
1111+
# the unsafe overlap error when strict-optional is disabled:
1112+
#
1113+
# @overload
1114+
# def foo(x: None) -> int: ...
1115+
# @overload
1116+
# def foo(x: str) -> str: ...
1117+
#
1118+
# See Python 2's map function for a concrete example of this kind of overload.
1119+
with state.strict_optional_set(True):
1120+
esig1 = expanded_signatures[i]
1121+
esig2 = expanded_signatures[i + j + 1]
1122+
assert esig1 is not None and esig2 is not None
1123+
if is_unsafe_overlapping_overload_signatures(esig1, esig2, type_vars):
1124+
flip_note = (
1125+
j == 0
1126+
and not is_unsafe_overlapping_overload_signatures(
1127+
esig2, esig1, type_vars
1128+
)
1129+
and not overload_can_never_match(sig2, sig1)
1130+
)
1131+
ctx_item = defn.items[i]
1132+
assert isinstance(ctx_item, Decorator)
1133+
self.msg.overloaded_signatures_overlap(
1134+
i + 1, i + j + 2, flip_note, ctx_item.func
11051135
)
1106-
and not overload_can_never_match(sig2, sig1)
1107-
)
1108-
self.msg.overloaded_signatures_overlap(
1109-
i + 1, i + j + 2, flip_note, item.func
1110-
)
11111136

11121137
if impl_type is not None:
11131138
assert defn.impl is not None
@@ -9242,6 +9267,10 @@ def are_argument_counts_overlapping(t: CallableType, s: CallableType) -> bool:
92429267

92439268
def expand_callable_variants(c: CallableType) -> list[CallableType]:
92449269
"""Expand a generic callable using all combinations of type variables' values/bounds."""
9270+
if not c.is_generic():
9271+
# Fast path.
9272+
return [c]
9273+
92459274
for tv in c.variables:
92469275
# We need to expand self-type before other variables, because this is the only
92479276
# type variable that can have other type variables in the upper bound.
@@ -9251,10 +9280,6 @@ def expand_callable_variants(c: CallableType) -> list[CallableType]:
92519280
)
92529281
break
92539282

9254-
if not c.is_generic():
9255-
# Fast path.
9256-
return [c]
9257-
92589283
tvar_values = []
92599284
for tvar in c.variables:
92609285
if isinstance(tvar, TypeVarType) and tvar.values:
@@ -9270,8 +9295,8 @@ def expand_callable_variants(c: CallableType) -> list[CallableType]:
92709295

92719296

92729297
def is_unsafe_overlapping_overload_signatures(
9273-
signature: CallableType,
9274-
other: CallableType,
9298+
signature: CallableType | list[CallableType],
9299+
other: CallableType | list[CallableType],
92759300
class_type_vars: list[TypeVarLikeType],
92769301
partial_only: bool = True,
92779302
) -> bool:
@@ -9299,14 +9324,21 @@ def is_unsafe_overlapping_overload_signatures(
92999324
# Try detaching callables from the containing class so that all TypeVars
93009325
# are treated as being free, i.e. the signature is as seen from inside the class,
93019326
# where "self" is not yet bound to anything.
9302-
signature = detach_callable(signature, class_type_vars)
9303-
other = detach_callable(other, class_type_vars)
9327+
if isinstance(signature, list):
9328+
signature_expanded = signature
9329+
else:
9330+
signature = detach_callable(signature, class_type_vars)
9331+
signature_expanded = expand_callable_variants(signature)
9332+
9333+
if isinstance(other, list):
9334+
other_expanded = other
9335+
else:
9336+
other = detach_callable(other, class_type_vars)
9337+
other_expanded = expand_callable_variants(other)
93049338

93059339
# Note: We repeat this check twice in both directions compensate for slight
93069340
# asymmetries in 'is_callable_compatible'.
9307-
9308-
other_expanded = expand_callable_variants(other)
9309-
for sig_variant in expand_callable_variants(signature):
9341+
for sig_variant in signature_expanded:
93109342
for other_variant in other_expanded:
93119343
# Using only expanded callables may cause false negatives, we can add
93129344
# more variants (e.g. using inference between callables) in the future.

0 commit comments

Comments
 (0)