Description
Feature
The time complexity of dealing with function overloads in mypy appears to be polynomial. Naively, it seems this is not a fundamental limit (I have no experience in static analysis to base this on), below is a log-log graph of number of overloads vs execution time:
The data for the graph was generated with the following code:
import json
import pathlib
import tempfile
import textwrap
import time
from mypy import api
def generate_n_overloads(n: int, types=('str', 'int', 'float')) -> str:
result = ['import typing']
for name_count in range(n):
type_name = types[name_count % len(types)]
name = f'overload_{name_count}_{type_name}'
annotation = (
textwrap.dedent(f'''
@typing.overload
def get_param(param: typing.Literal['{name}']) -> {type_name}: ...
''')
)
result.append(annotation)
return '\n'.join(result)
def build_test_case(dest_dir: pathlib.Path, n_overloads: int) -> pathlib.Path:
pkg_dir = dest_dir / 'example_overloads_pkg'
pkg_dir.mkdir(exist_ok=True)
stubfile = pkg_dir / '__init__.pyi'
stubfile.write_text(generate_n_overloads(n_overloads))
pkg_file = pkg_dir / '__init__.py'
pkg_file.write_text('def get_param(param): ...')
test_script = dest_dir / 'script.py'
test_script.write_text(textwrap.dedent('''
from example_overloads_pkg import get_param
get_param('overload_3_str').upper() # Good
get_param('overload_2_float').upper() # Bad
'''))
return test_script
if __name__ == '__main__':
tmpdir = tempfile.TemporaryDirectory()
scale_times = {}
numbers_to_check = [16, 32, 64, 128, 256, 512, 1024]
# numbers_to_check = [16, 32, 64, 128, 256, 300, 400, 500, 600, 700, 800, 900, 1000, 1500, 2000, 2500, 3000, 4000, 5000, 6000, 8000, 10000]
for number_of_overloads in numbers_to_check:
print(f'Overload size: {number_of_overloads}')
test_script = build_test_case(pathlib.Path(tmpdir.name), number_of_overloads)
start = time.perf_counter()
result = api.run([str(test_script)])
end = time.perf_counter()
elapsed = end - start
print(' Time:', end - start)
if scale_times:
last_n = next(reversed(scale_times))
print(f" Slowdown: x{elapsed / scale_times[last_n]:.2f}")
scale_times[number_of_overloads] = elapsed
# Save the times to json for plotting/analysis.
with open('times.json', 'wt') as fh:
json.dump(scale_times, fh)
And the plot:
import json
import matplotlib.pyplot as plt
import numpy as np
with open('times.json', 'rt') as fh:
times = json.load(fh)
n_points, times = zip(*times.items())
n_points = np.array(n_points, dtype=int)
times = np.array(times)
fit = np.polyfit(n_points, times, 2)
p = np.poly1d(fit)
plt.title('Number of overloads vs execution time of mypy')
plt.xscale('log')
plt.yscale('log')
plt.scatter(n_points, times)
plt.xlabel('Number of overloads')
plt.ylabel('Time to run mypy / seconds')
plt.show()
The full dataset (times.json):
{"16": 0.11653269396629184, "32": 0.13803347101202235, "64": 0.1889677940052934, "128": 0.42529276601271704, "256": 1.4768535409821197, "300": 2.165687720000278, "400": 3.581374307977967, "500": 5.615040614036843, "600": 8.182245634961873, "700": 10.219899011019152, "800": 14.204097100009676, "900": 19.01026200200431, "1000": 21.914704270020593, "1500": 50.26287814299576, "2000": 88.03798637498403, "2500": 140.229756515997, "3000": 206.8722462329897, "4000": 373.4201490940177, "5000": 596.6820141010103, "6000": 831.5039637690061, "8000": 1579.1185438489774, "10000": 2624.7711193099967}
I have inherited a library which has a very simple DSL to query data from a database and which returns a dictionary of different types depending on the input. Indeed, the language is so simple that I could map these to a collection of literal overloads, with a generic fallback for new/unmapped data. In practice this looks something like:
import typing
@typing.overload
def get_param(param: typing.Literal['some_float']) -> float: ...
@typing.overload
def get_param(param: typing.Literal['some_other_int']) -> int: ...
@typing.overload
def get_param(param: typing.Literal['further_str']) -> str: ...
Being able to do static analysis (and completion) on such an interface would be hugely beneficial to its users for correctness and ease of use. Unfortunately the total number of overloads would need to be in the order of 100,000... clearly from the graph, this number is prohibitive with the current implementation of mypy's overload functionality.
Pitch
I'm therefore reaching out to find out if there is a known good reason for this time-complexity, and potentially seeking help/pointers to address the issue in the implementation.
Other places this could be useful
Truth be told, this is a highly specialised requirement which would apply to a fairly limited set of use cases (some of which are likely anti-patterns in the first place).
Given the high number of overloads involved for this time-complexity to become an issue (at around 100 overloads), it is clear that you'd almost always want to generate the stubs rather than hand-craft them. Examples of where it could come in handy are other string based lookups - I can imagine for example wanting to generate stubs for all of the JClasses that exist in JPype (which can be any Java classes available in the JVM), or perhaps for some interface that allows you to get hold of a CSS property by name and which returns a slightly different type for each of the ~520 valid tags. I could also imagine this being something that could be used for generating the permutations of a multiple-dispatch system.