bpo-38530: Refactor and improve AttributeError suggestions (GH-25776)

- Make case-swaps half the cost of any other edit
- Refactor Levenshtein code to not use memory allocator, and to bail early on no match.
- Add comments to Levenshtein distance code
- Add test cases for Levenshtein distance behind a debug macro
- Set threshold to `(name_size + item_size + 3) * MOVE_COST / 6`.
  - Reasoning: similar to `difflib.SequenceMatcher.ratio()` >= 2/3:
```
"Multiset Jaccard similarity" >= 2/3
matching letters / total letters >= 2/3
(name_size - distance + item_size - distance) / (name_size + item_size) >= 2/3
1 - (2*distance) / (name_size + item_size) >= 2/3
1/3 >= (2*distance) / (name_size + item_size)
(name_size + item_size) / 6 >= distance
With rounding:
(name_size + item_size + 3) // 6 >= distance
```

Co-authored-by: Pablo Galindo <pablogsal@gmail.com>

1 files changed, 2 insertions, 0 deletions

diff --git a/Include/internal/pycore_pyerrors.h b/Include/internal/pycore_pyerrors.h
index d1af8e9..a5e97fe 100644
--- a/Include/internal/pycore_pyerrors.h
+++ b/Include/internal/pycore_pyerrors.h
@@ -87,6 +87,8 @@ PyAPI_FUNC(int) _PyErr_CheckSignalsTstate(PyThreadState *tstate);
 PyAPI_FUNC(void) _Py_DumpExtensionModules(int fd, PyInterpreterState *interp);
 
 extern PyObject* _Py_Offer_Suggestions(PyObject* exception);
+PyAPI_FUNC(Py_ssize_t) _Py_UTF8_Edit_Cost(PyObject *str_a, PyObject *str_b,
+                                          Py_ssize_t max_cost);
 
 #ifdef __cplusplus
 }