Debian Codegraph @

Tools/build/generate_levenshtein_examples.py

raw
1 """Generate 10,000 unique examples for the Levenshtein short-circuit tests."""
2
3 import argparse
4 import json
5 import os.path
6 from functools import lru_cache
7 from random import choices, randrange
8
9 # This should be in sync with Lib/traceback.py. It's not importing those values
10 # because this script is being executed by PYTHON_FOR_REGEN and not by the in-tree
11 # build of Python.
12 _MOVE_COST = 2
13 _CASE_COST = 1
14
15
16 def _substitution_cost(ch_a: str, ch_b: str) -> int:
17 if ch_a == ch_b:
18 return 0
19 if ch_a.lower() == ch_b.lower():
20 return _CASE_COST
21 return _MOVE_COST
22
23
24 @lru_cache(None)
25 def levenshtein(a: str, b: str) -> int:
26 if not a or not b:
27 return (len(a) + len(b)) * _MOVE_COST
28 option1 = levenshtein(a[:-1], b[:-1]) + _substitution_cost(a[-1], b[-1])
29 option2 = levenshtein(a[:-1], b) + _MOVE_COST
30 option3 = levenshtein(a, b[:-1]) + _MOVE_COST
31 return min(option1, option2, option3)
32
33
34 def main() -> None:
35 parser = argparse.ArgumentParser(description=__doc__)
36 parser.add_argument('output_path', metavar='FILE', type=str)
37 parser.add_argument('--overwrite', dest='overwrite', action='store_const',
38 const=True, default=False,
39 help='overwrite an existing test file')
40
41 args = parser.parse_args()
42 output_path = os.path.realpath(args.output_path)
43 if not args.overwrite and os.path.isfile(output_path):
44 print(f"{output_path} already exists, skipping regeneration.")
45 print(
46 "To force, add --overwrite to the invocation of this tool or"
47 " delete the existing file."
48 )
49 return
50
51 examples: set[tuple[str, str, int]] = set()
52 # Create a lot of non-empty examples, which should end up with a Gauss-like
53 # distribution for even costs (moves) and odd costs (case substitutions).
54 while len(examples) < 9990:
55 a = ''.join(choices("abcABC", k=randrange(1, 10)))
56 b = ''.join(choices("abcABC", k=randrange(1, 10)))
57 expected = levenshtein(a, b)
58 examples.add((a, b, expected))
59 # Create one empty case each for strings between 0 and 9 in length.
60 for i in range(10):
61 b = ''.join(choices("abcABC", k=i))
62 expected = levenshtein("", b)
63 examples.add(("", b, expected))
64 with open(output_path, "w") as f:
65 json.dump(sorted(examples), f, indent=2)
66
67
68 if __name__ == "__main__":
69 main()