| 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() |