From 80a2a4ed7d090fff2584302f07315d567109bca9 Mon Sep 17 00:00:00 2001 From: Dennis Sweeney <36520290+sweeneyde@users.noreply.github.com> Date: Mon, 3 May 2021 11:47:27 -0400 Subject: 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 --- Include/internal/pycore_pyerrors.h | 2 + Lib/test/test_exceptions.py | 102 ++++++++++++++++---- Modules/_testinternalcapi.c | 87 +++++++++++++++++ Python/suggestions.c | 189 +++++++++++++++++++++++++------------ 4 files changed, 303 insertions(+), 77 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 } diff --git a/Lib/test/test_exceptions.py b/Lib/test/test_exceptions.py index 3810108..bc0404e 100644 --- a/Lib/test/test_exceptions.py +++ b/Lib/test/test_exceptions.py @@ -1486,13 +1486,13 @@ class NameErrorTests(unittest.TestCase): def test_name_error_suggestions_from_builtins(self): def func(): - print(AttributeErrop) + print(ZeroDivisionErrrrr) try: func() except NameError as exc: with support.captured_stderr() as err: sys.__excepthook__(*sys.exc_info()) - self.assertIn("'AttributeError'?", err.getvalue()) + self.assertIn("'ZeroDivisionError'?", err.getvalue()) def test_name_error_suggestions_do_not_trigger_for_long_names(self): def f(): @@ -1565,21 +1565,87 @@ class NameErrorTests(unittest.TestCase): def test_name_error_suggestions_do_not_trigger_for_too_many_locals(self): def f(): # Mutating locals() is unreliable, so we need to do it by hand - a1 = a2 = a3 = a4 = a5 = a6 = a7 = a8 = a9 = a10 = a11 = a12 = a13 = \ - a14 = a15 = a16 = a17 = a18 = a19 = a20 = a21 = a22 = a23 = a24 = a25 = \ - a26 = a27 = a28 = a29 = a30 = a31 = a32 = a33 = a34 = a35 = a36 = a37 = \ - a38 = a39 = a40 = a41 = a42 = a43 = a44 = a45 = a46 = a47 = a48 = a49 = \ - a50 = a51 = a52 = a53 = a54 = a55 = a56 = a57 = a58 = a59 = a60 = a61 = \ - a62 = a63 = a64 = a65 = a66 = a67 = a68 = a69 = a70 = a71 = a72 = a73 = \ - a74 = a75 = a76 = a77 = a78 = a79 = a80 = a81 = a82 = a83 = a84 = a85 = \ - a86 = a87 = a88 = a89 = a90 = a91 = a92 = a93 = a94 = a95 = a96 = a97 = \ - a98 = a99 = a100 = a101 = a102 = a103 = a104 = a105 = a106 = a107 = \ - a108 = a109 = a110 = a111 = a112 = a113 = a114 = a115 = a116 = a117 = \ - a118 = a119 = a120 = a121 = a122 = a123 = a124 = a125 = a126 = \ - a127 = a128 = a129 = a130 = a131 = a132 = a133 = a134 = a135 = a136 = \ - a137 = a138 = a139 = a140 = a141 = a142 = a143 = a144 = a145 = \ - a146 = a147 = a148 = a149 = a150 = a151 = a152 = a153 = a154 = a155 = \ - a156 = a157 = a158 = a159 = a160 = a161 = None + a1 = a2 = a3 = a4 = a5 = a6 = a7 = a8 = a9 = a10 = \ + a11 = a12 = a13 = a14 = a15 = a16 = a17 = a18 = a19 = a20 = \ + a21 = a22 = a23 = a24 = a25 = a26 = a27 = a28 = a29 = a30 = \ + a31 = a32 = a33 = a34 = a35 = a36 = a37 = a38 = a39 = a40 = \ + a41 = a42 = a43 = a44 = a45 = a46 = a47 = a48 = a49 = a50 = \ + a51 = a52 = a53 = a54 = a55 = a56 = a57 = a58 = a59 = a60 = \ + a61 = a62 = a63 = a64 = a65 = a66 = a67 = a68 = a69 = a70 = \ + a71 = a72 = a73 = a74 = a75 = a76 = a77 = a78 = a79 = a80 = \ + a81 = a82 = a83 = a84 = a85 = a86 = a87 = a88 = a89 = a90 = \ + a91 = a92 = a93 = a94 = a95 = a96 = a97 = a98 = a99 = a100 = \ + a101 = a102 = a103 = a104 = a105 = a106 = a107 = a108 = a109 = a110 = \ + a111 = a112 = a113 = a114 = a115 = a116 = a117 = a118 = a119 = a120 = \ + a121 = a122 = a123 = a124 = a125 = a126 = a127 = a128 = a129 = a130 = \ + a131 = a132 = a133 = a134 = a135 = a136 = a137 = a138 = a139 = a140 = \ + a141 = a142 = a143 = a144 = a145 = a146 = a147 = a148 = a149 = a150 = \ + a151 = a152 = a153 = a154 = a155 = a156 = a157 = a158 = a159 = a160 = \ + a161 = a162 = a163 = a164 = a165 = a166 = a167 = a168 = a169 = a170 = \ + a171 = a172 = a173 = a174 = a175 = a176 = a177 = a178 = a179 = a180 = \ + a181 = a182 = a183 = a184 = a185 = a186 = a187 = a188 = a189 = a190 = \ + a191 = a192 = a193 = a194 = a195 = a196 = a197 = a198 = a199 = a200 = \ + a201 = a202 = a203 = a204 = a205 = a206 = a207 = a208 = a209 = a210 = \ + a211 = a212 = a213 = a214 = a215 = a216 = a217 = a218 = a219 = a220 = \ + a221 = a222 = a223 = a224 = a225 = a226 = a227 = a228 = a229 = a230 = \ + a231 = a232 = a233 = a234 = a235 = a236 = a237 = a238 = a239 = a240 = \ + a241 = a242 = a243 = a244 = a245 = a246 = a247 = a248 = a249 = a250 = \ + a251 = a252 = a253 = a254 = a255 = a256 = a257 = a258 = a259 = a260 = \ + a261 = a262 = a263 = a264 = a265 = a266 = a267 = a268 = a269 = a270 = \ + a271 = a272 = a273 = a274 = a275 = a276 = a277 = a278 = a279 = a280 = \ + a281 = a282 = a283 = a284 = a285 = a286 = a287 = a288 = a289 = a290 = \ + a291 = a292 = a293 = a294 = a295 = a296 = a297 = a298 = a299 = a300 = \ + a301 = a302 = a303 = a304 = a305 = a306 = a307 = a308 = a309 = a310 = \ + a311 = a312 = a313 = a314 = a315 = a316 = a317 = a318 = a319 = a320 = \ + a321 = a322 = a323 = a324 = a325 = a326 = a327 = a328 = a329 = a330 = \ + a331 = a332 = a333 = a334 = a335 = a336 = a337 = a338 = a339 = a340 = \ + a341 = a342 = a343 = a344 = a345 = a346 = a347 = a348 = a349 = a350 = \ + a351 = a352 = a353 = a354 = a355 = a356 = a357 = a358 = a359 = a360 = \ + a361 = a362 = a363 = a364 = a365 = a366 = a367 = a368 = a369 = a370 = \ + a371 = a372 = a373 = a374 = a375 = a376 = a377 = a378 = a379 = a380 = \ + a381 = a382 = a383 = a384 = a385 = a386 = a387 = a388 = a389 = a390 = \ + a391 = a392 = a393 = a394 = a395 = a396 = a397 = a398 = a399 = a400 = \ + a401 = a402 = a403 = a404 = a405 = a406 = a407 = a408 = a409 = a410 = \ + a411 = a412 = a413 = a414 = a415 = a416 = a417 = a418 = a419 = a420 = \ + a421 = a422 = a423 = a424 = a425 = a426 = a427 = a428 = a429 = a430 = \ + a431 = a432 = a433 = a434 = a435 = a436 = a437 = a438 = a439 = a440 = \ + a441 = a442 = a443 = a444 = a445 = a446 = a447 = a448 = a449 = a450 = \ + a451 = a452 = a453 = a454 = a455 = a456 = a457 = a458 = a459 = a460 = \ + a461 = a462 = a463 = a464 = a465 = a466 = a467 = a468 = a469 = a470 = \ + a471 = a472 = a473 = a474 = a475 = a476 = a477 = a478 = a479 = a480 = \ + a481 = a482 = a483 = a484 = a485 = a486 = a487 = a488 = a489 = a490 = \ + a491 = a492 = a493 = a494 = a495 = a496 = a497 = a498 = a499 = a500 = \ + a501 = a502 = a503 = a504 = a505 = a506 = a507 = a508 = a509 = a510 = \ + a511 = a512 = a513 = a514 = a515 = a516 = a517 = a518 = a519 = a520 = \ + a521 = a522 = a523 = a524 = a525 = a526 = a527 = a528 = a529 = a530 = \ + a531 = a532 = a533 = a534 = a535 = a536 = a537 = a538 = a539 = a540 = \ + a541 = a542 = a543 = a544 = a545 = a546 = a547 = a548 = a549 = a550 = \ + a551 = a552 = a553 = a554 = a555 = a556 = a557 = a558 = a559 = a560 = \ + a561 = a562 = a563 = a564 = a565 = a566 = a567 = a568 = a569 = a570 = \ + a571 = a572 = a573 = a574 = a575 = a576 = a577 = a578 = a579 = a580 = \ + a581 = a582 = a583 = a584 = a585 = a586 = a587 = a588 = a589 = a590 = \ + a591 = a592 = a593 = a594 = a595 = a596 = a597 = a598 = a599 = a600 = \ + a601 = a602 = a603 = a604 = a605 = a606 = a607 = a608 = a609 = a610 = \ + a611 = a612 = a613 = a614 = a615 = a616 = a617 = a618 = a619 = a620 = \ + a621 = a622 = a623 = a624 = a625 = a626 = a627 = a628 = a629 = a630 = \ + a631 = a632 = a633 = a634 = a635 = a636 = a637 = a638 = a639 = a640 = \ + a641 = a642 = a643 = a644 = a645 = a646 = a647 = a648 = a649 = a650 = \ + a651 = a652 = a653 = a654 = a655 = a656 = a657 = a658 = a659 = a660 = \ + a661 = a662 = a663 = a664 = a665 = a666 = a667 = a668 = a669 = a670 = \ + a671 = a672 = a673 = a674 = a675 = a676 = a677 = a678 = a679 = a680 = \ + a681 = a682 = a683 = a684 = a685 = a686 = a687 = a688 = a689 = a690 = \ + a691 = a692 = a693 = a694 = a695 = a696 = a697 = a698 = a699 = a700 = \ + a701 = a702 = a703 = a704 = a705 = a706 = a707 = a708 = a709 = a710 = \ + a711 = a712 = a713 = a714 = a715 = a716 = a717 = a718 = a719 = a720 = \ + a721 = a722 = a723 = a724 = a725 = a726 = a727 = a728 = a729 = a730 = \ + a731 = a732 = a733 = a734 = a735 = a736 = a737 = a738 = a739 = a740 = \ + a741 = a742 = a743 = a744 = a745 = a746 = a747 = a748 = a749 = a750 = \ + a751 = a752 = a753 = a754 = a755 = a756 = a757 = a758 = a759 = a760 = \ + a761 = a762 = a763 = a764 = a765 = a766 = a767 = a768 = a769 = a770 = \ + a771 = a772 = a773 = a774 = a775 = a776 = a777 = a778 = a779 = a780 = \ + a781 = a782 = a783 = a784 = a785 = a786 = a787 = a788 = a789 = a790 = \ + a791 = a792 = a793 = a794 = a795 = a796 = a797 = a798 = a799 = a800 \ + = None print(a0) try: @@ -1778,7 +1844,7 @@ class AttributeErrorTests(unittest.TestCase): blech = None # A class with a very big __dict__ will not be consider # for suggestions. - for index in range(160): + for index in range(2000): setattr(A, f"index_{index}", None) try: diff --git a/Modules/_testinternalcapi.c b/Modules/_testinternalcapi.c index ab6c596..d5616fd 100644 --- a/Modules/_testinternalcapi.c +++ b/Modules/_testinternalcapi.c @@ -18,6 +18,7 @@ #include "pycore_hashtable.h" // _Py_hashtable_new() #include "pycore_initconfig.h" // _Py_GetConfigsAsDict() #include "pycore_interp.h" // _PyInterpreterState_GetConfigCopy() +#include "pycore_pyerrors.h" // _Py_UTF8_Edit_Cost() static PyObject * @@ -279,6 +280,91 @@ test_atomic_funcs(PyObject *self, PyObject *Py_UNUSED(args)) } +static int +check_edit_cost(const char *a, const char *b, Py_ssize_t expected) +{ + int ret = -1; + PyObject *a_obj = NULL; + PyObject *b_obj = NULL; + + a_obj = PyUnicode_FromString(a); + if (a_obj == NULL) { + goto exit; + } + b_obj = PyUnicode_FromString(b); + if (a_obj == NULL) { + goto exit; + } + Py_ssize_t result = _Py_UTF8_Edit_Cost(a_obj, b_obj, -1); + if (result != expected) { + PyErr_Format(PyExc_AssertionError, + "Edit cost from '%s' to '%s' returns %zd, expected %zd", + a, b, result, expected); + goto exit; + } + // Check that smaller max_edits thresholds are exceeded. + Py_ssize_t max_edits = result; + while (max_edits > 0) { + max_edits /= 2; + Py_ssize_t result2 = _Py_UTF8_Edit_Cost(a_obj, b_obj, max_edits); + if (result2 <= max_edits) { + PyErr_Format(PyExc_AssertionError, + "Edit cost from '%s' to '%s' (threshold %zd) " + "returns %zd, expected greater than %zd", + a, b, max_edits, result2, max_edits); + goto exit; + } + } + // Check that bigger max_edits thresholds don't change anything + Py_ssize_t result3 = _Py_UTF8_Edit_Cost(a_obj, b_obj, result * 2 + 1); + if (result3 != result) { + PyErr_Format(PyExc_AssertionError, + "Edit cost from '%s' to '%s' (threshold %zd) " + "returns %zd, expected %zd", + a, b, result * 2, result3, result); + goto exit; + } + ret = 0; +exit: + Py_XDECREF(a_obj); + Py_XDECREF(b_obj); + return ret; +} + +static PyObject * +test_edit_cost(PyObject *self, PyObject *Py_UNUSED(args)) +{ + #define CHECK(a, b, n) do { \ + if (check_edit_cost(a, b, n) < 0) { \ + return NULL; \ + } \ + } while (0) \ + + CHECK("", "", 0); + CHECK("", "a", 2); + CHECK("a", "A", 1); + CHECK("Apple", "Aple", 2); + CHECK("Banana", "B@n@n@", 6); + CHECK("Cherry", "Cherry!", 2); + CHECK("---0---", "------", 2); + CHECK("abc", "y", 6); + CHECK("aa", "bb", 4); + CHECK("aaaaa", "AAAAA", 5); + CHECK("wxyz", "wXyZ", 2); + CHECK("wxyz", "wXyZ123", 8); + CHECK("Python", "Java", 12); + CHECK("Java", "C#", 8); + CHECK("AbstractFoobarManager", "abstract_foobar_manager", 3+2*2); + CHECK("CPython", "PyPy", 10); + CHECK("CPython", "pypy", 11); + CHECK("AttributeError", "AttributeErrop", 2); + CHECK("AttributeError", "AttributeErrorTests", 10); + + #undef CHECK + Py_RETURN_NONE; +} + + static PyMethodDef TestMethods[] = { {"get_configs", get_configs, METH_NOARGS}, {"get_recursion_depth", get_recursion_depth, METH_NOARGS}, @@ -289,6 +375,7 @@ static PyMethodDef TestMethods[] = { {"get_config", test_get_config, METH_NOARGS}, {"set_config", test_set_config, METH_O}, {"test_atomic_funcs", test_atomic_funcs, METH_NOARGS}, + {"test_edit_cost", test_edit_cost, METH_NOARGS}, {NULL, NULL} /* sentinel */ }; diff --git a/Python/suggestions.c b/Python/suggestions.c index 2fd6714..6fb01f1 100644 --- a/Python/suggestions.c +++ b/Python/suggestions.c @@ -3,78 +3,129 @@ #include "pycore_pyerrors.h" -#define MAX_DISTANCE 3 -#define MAX_CANDIDATE_ITEMS 160 -#define MAX_STRING_SIZE 25 +#define MAX_CANDIDATE_ITEMS 750 +#define MAX_STRING_SIZE 40 -/* Calculate the Levenshtein distance between string1 and string2 */ -static Py_ssize_t -levenshtein_distance(const char *a, size_t a_size, - const char *b, size_t b_size) { +#define MOVE_COST 2 +#define CASE_COST 1 - if (a_size > MAX_STRING_SIZE || b_size > MAX_STRING_SIZE) { +#define LEAST_FIVE_BITS(n) ((n) & 31) + +static inline int +substitution_cost(char a, char b) +{ + if (LEAST_FIVE_BITS(a) != LEAST_FIVE_BITS(b)) { + // Not the same, not a case flip. + return MOVE_COST; + } + if (a == b) { return 0; } + if ('A' <= a && a <= 'Z') { + a += ('a' - 'A'); + } + if ('A' <= b && b <= 'Z') { + b += ('a' - 'A'); + } + if (a == b) { + return CASE_COST; + } + return MOVE_COST; +} + +/* Calculate the Levenshtein distance between string1 and string2 */ +static Py_ssize_t +levenshtein_distance(const char *a, size_t a_size, + const char *b, size_t b_size, + size_t max_cost) +{ + static size_t buffer[MAX_STRING_SIZE]; // Both strings are the same (by identity) if (a == b) { return 0; } - // The first string is empty - if (a_size == 0) { - return b_size; + // Trim away common affixes. + while (a_size && b_size && a[0] == b[0]) { + a++; a_size--; + b++; b_size--; + } + while (a_size && b_size && a[a_size-1] == b[b_size-1]) { + a_size--; + b_size--; + } + if (a_size == 0 || b_size == 0) { + return (a_size + b_size) * MOVE_COST; + } + if (a_size > MAX_STRING_SIZE || b_size > MAX_STRING_SIZE) { + return max_cost + 1; } - // The second string is empty - if (b_size == 0) { - return a_size; + // Prefer shorter buffer + if (b_size < a_size) { + const char *t = a; a = b; b = t; + size_t t_size = a_size; a_size = b_size; b_size = t_size; } - size_t *buffer = PyMem_Calloc(a_size, sizeof(size_t)); - if (buffer == NULL) { - return -1; + // quick fail when a match is impossible. + if ((b_size - a_size) * MOVE_COST > max_cost) { + return max_cost + 1; } + // Instead of producing the whole traditional len(a)-by-len(b) + // matrix, we can update just one row in place. // Initialize the buffer row - size_t index = 0; - while (index < a_size) { - buffer[index] = index + 1; - index++; + for (size_t i = 0; i < a_size; i++) { + // cost from b[:0] to a[:i+1] + buffer[i] = (i + 1) * MOVE_COST; } - size_t b_index = 0; size_t result = 0; - while (b_index < b_size) { + for (size_t b_index = 0; b_index < b_size; b_index++) { char code = b[b_index]; - size_t distance = result = b_index++; - index = SIZE_MAX; - while (++index < a_size) { - size_t b_distance = code == a[index] ? distance : distance + 1; + // cost(b[:b_index], a[:0]) == b_index * MOVE_COST + size_t distance = result = b_index * MOVE_COST; + size_t minimum = SIZE_MAX; + for (size_t index = 0; index < a_size; index++) { + + // cost(b[:b_index+1], a[:index+1]) = min( + // // 1) substitute + // cost(b[:b_index], a[:index]) + // + substitution_cost(b[b_index], a[index]), + // // 2) delete from b + // cost(b[:b_index], a[:index+1]) + MOVE_COST, + // // 3) delete from a + // cost(b[:b_index+1], a[index]) + MOVE_COST + // ) + + // 1) Previous distance in this row is cost(b[:b_index], a[:index]) + size_t substitute = distance + substitution_cost(code, a[index]); + // 2) cost(b[:b_index], a[:index+1]) from previous row distance = buffer[index]; - if (distance > result) { - if (b_distance > result) { - result = result + 1; - } else { - result = b_distance; - } - } else { - if (b_distance > distance) { - result = distance + 1; - } else { - result = b_distance; - } - } + // 3) existing result is cost(b[:b_index+1], a[index]) + + size_t insert_delete = Py_MIN(result, distance) + MOVE_COST; + result = Py_MIN(insert_delete, substitute); + + // cost(b[:b_index+1], a[:index+1]) buffer[index] = result; + if (result < minimum) { + minimum = result; + } + } + if (minimum > max_cost) { + // Everything in this row is too big, so bail early. + return max_cost + 1; } } - PyMem_Free(buffer); return result; } static inline PyObject * calculate_suggestions(PyObject *dir, - PyObject *name) { + PyObject *name) +{ assert(!PyErr_Occurred()); assert(PyList_CheckExact(dir)); @@ -83,13 +134,14 @@ calculate_suggestions(PyObject *dir, return NULL; } - Py_ssize_t suggestion_distance = PyUnicode_GetLength(name); + Py_ssize_t suggestion_distance = PY_SSIZE_T_MAX; PyObject *suggestion = NULL; Py_ssize_t name_size; const char *name_str = PyUnicode_AsUTF8AndSize(name, &name_size); if (name_str == NULL) { return NULL; } + for (int i = 0; i < dir_size; ++i) { PyObject *item = PyList_GET_ITEM(dir, i); Py_ssize_t item_size; @@ -97,15 +149,14 @@ calculate_suggestions(PyObject *dir, if (item_str == NULL) { return NULL; } - Py_ssize_t current_distance = levenshtein_distance( - name_str, name_size, item_str, item_size); - if (current_distance == -1) { - return NULL; - } - if (current_distance == 0 || - current_distance > MAX_DISTANCE || - current_distance * 2 > name_size) - { + // No more than 1/3 of the involved characters should need changed. + Py_ssize_t max_distance = (name_size + item_size + 3) * MOVE_COST / 6; + // Don't take matches we've already beaten. + max_distance = Py_MIN(max_distance, suggestion_distance - 1); + Py_ssize_t current_distance = + levenshtein_distance(name_str, name_size, + item_str, item_size, max_distance); + if (current_distance > max_distance) { continue; } if (!suggestion || current_distance < suggestion_distance) { @@ -113,15 +164,13 @@ calculate_suggestions(PyObject *dir, suggestion_distance = current_distance; } } - if (!suggestion) { - return NULL; - } - Py_INCREF(suggestion); + Py_XINCREF(suggestion); return suggestion; } static PyObject * -offer_suggestions_for_attribute_error(PyAttributeErrorObject *exc) { +offer_suggestions_for_attribute_error(PyAttributeErrorObject *exc) +{ PyObject *name = exc->name; // borrowed reference PyObject *obj = exc->obj; // borrowed reference @@ -142,7 +191,8 @@ offer_suggestions_for_attribute_error(PyAttributeErrorObject *exc) { static PyObject * -offer_suggestions_for_name_error(PyNameErrorObject *exc) { +offer_suggestions_for_name_error(PyNameErrorObject *exc) +{ PyObject *name = exc->name; // borrowed reference PyTracebackObject *traceback = (PyTracebackObject *) exc->traceback; // borrowed reference // Abort if we don't have a variable name or we have an invalid one @@ -194,7 +244,9 @@ offer_suggestions_for_name_error(PyNameErrorObject *exc) { // Offer suggestions for a given exception. Returns a python string object containing the // suggestions. This function returns NULL if no suggestion was found or if an exception happened, // users must call PyErr_Occurred() to disambiguate. -PyObject *_Py_Offer_Suggestions(PyObject *exception) { +PyObject * +_Py_Offer_Suggestions(PyObject *exception) +{ PyObject *result = NULL; assert(!PyErr_Occurred()); if (Py_IS_TYPE(exception, (PyTypeObject*)PyExc_AttributeError)) { @@ -205,3 +257,22 @@ PyObject *_Py_Offer_Suggestions(PyObject *exception) { return result; } +Py_ssize_t +_Py_UTF8_Edit_Cost(PyObject *a, PyObject *b, Py_ssize_t max_cost) +{ + assert(PyUnicode_Check(a) && PyUnicode_Check(b)); + Py_ssize_t size_a, size_b; + const char *utf8_a = PyUnicode_AsUTF8AndSize(a, &size_a); + if (utf8_a == NULL) { + return -1; + } + const char *utf8_b = PyUnicode_AsUTF8AndSize(b, &size_b); + if (utf8_b == NULL) { + return -1; + } + if (max_cost == -1) { + max_cost = MOVE_COST * Py_MAX(size_a, size_b); + } + return levenshtein_distance(utf8_a, size_a, utf8_b, size_b, max_cost); +} + -- cgit v0.12