Skip to content

Commit 5dc2840

Browse files
authored
Prevent quadratic runtime for overlap check at large overload counts (python#15865)
Fixes python#10004
1 parent 55472c0 commit 5dc2840

4 files changed

Lines changed: 28 additions & 0 deletions

File tree

‎docs/source/error_code_list.rst‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1386,6 +1386,17 @@ to the line with the string literal:
13861386
dict_of_typx = {'str_or_none': TypeForm(str | None)}
13871387
list_of_typx: list[TypeForm] = [dict_of_typx['str_or_none']] # type: ignore[maybe-unrecognized-str-typeform]
13881388
1389+
.. _code-performance-limit:
1390+
1391+
Checks skipped for performance reasons [performance-limit]
1392+
----------------------------------------------------------
1393+
1394+
Mypy reports this error when it limits or skip checks to avoid excessive type
1395+
checking time. As a result, some errors may go undetected.
1396+
1397+
For example, when a function has 50 or more ``@overload`` variants, mypy limits
1398+
the number of variants it compares for overlap.
1399+
13891400
.. _code-misc:
13901401

13911402
Miscellaneous checks [misc]

‎mypy/checker.py‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1039,6 +1039,11 @@ def check_overlapping_overloads(self, defn: OverloadedFuncDef) -> None:
10391039
if self.can_skip_diagnostics:
10401040
return
10411041

1042+
max_overload_count = 50
1043+
if len(defn.items) >= max_overload_count:
1044+
# Since the following is quadratic, we limit the size of the inner loop
1045+
self.fail(message_registry.TOO_MANY_OVERLOADS, defn)
1046+
10421047
# Compute some info about the implementation (if it exists) for use below
10431048
impl_type: CallableType | None = None
10441049
if defn.impl:
@@ -1061,6 +1066,10 @@ def check_overlapping_overloads(self, defn: OverloadedFuncDef) -> None:
10611066
continue
10621067

10631068
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
1072+
10641073
assert isinstance(item2, Decorator)
10651074
sig2 = self.extract_callable_type(item2.var.type, item2)
10661075
if sig2 is None:

‎mypy/errorcodes.py‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -284,6 +284,10 @@ def __hash__(self) -> int:
284284
# Syntax errors are often blocking.
285285
SYNTAX: Final = ErrorCode("syntax", "Report syntax errors", "General")
286286

287+
PERFORMANCE_LIMIT: Final = ErrorCode(
288+
"performance-limit", "Warn about checks skipped for performance reasons", "General"
289+
)
290+
287291
# This is a catch-all for remaining uncategorized errors.
288292
MISC: Final = ErrorCode("misc", "Miscellaneous other checks", "General")
289293

‎mypy/message_registry.py‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -107,6 +107,10 @@ def with_additional_msg(self, info: str) -> ErrorMessage:
107107
"Overloaded method has both abstract and non-abstract variants"
108108
)
109109
MULTIPLE_OVERLOADS_REQUIRED: Final = ErrorMessage("Single overload definition, multiple required")
110+
TOO_MANY_OVERLOADS: Final = ErrorMessage(
111+
"Not all overload combinations were checked for overlap because there were too many",
112+
codes.PERFORMANCE_LIMIT,
113+
)
110114
READ_ONLY_PROPERTY_OVERRIDES_READ_WRITE: Final = ErrorMessage(
111115
"Read-only property cannot override read-write property"
112116
)

0 commit comments

Comments
 (0)