LCOV - code coverage report
Current view: | top level - Python - suggestions.c (source / functions) |  |  | Hit | Total | Coverage
Test: | CPython 3.12 LCOV report [commit 5e6661bce9] |  | Lines: | 0 | 214 | 0.0 %
Date: | 2023-03-20 08:15:36 |  | Functions: | 0 | 11 | 0.0 %
|  |  | Branches: | 0 | 152 | 0.0 %

               Branch data     Line data    Source code
           1                 :            : #include "Python.h"
           2                 :            : #include "pycore_frame.h"
           3                 :            : #include "pycore_runtime.h"         // _PyRuntime
           4                 :            : #include "pycore_global_objects.h"  // _Py_ID()
           5                 :            :
           6                 :            : #include "pycore_pyerrors.h"
           7                 :            : #include "pycore_code.h"        // _PyCode_GetVarnames()
           8                 :            : #include "stdlib_module_names.h"  // _Py_stdlib_module_names
           9                 :            :
          10                 :            : #define MAX_CANDIDATE_ITEMS 750
          11                 :            : #define MAX_STRING_SIZE 40
          12                 :            :
          13                 :            : #define MOVE_COST 2
          14                 :            : #define CASE_COST 1
          15                 :            :
          16                 :            : #define LEAST_FIVE_BITS(n) ((n) & 31)
          17                 :            :
          18                 :            : static inline int
          19                 :          0 : substitution_cost(char a, char b)
          20                 :            : {
          21         [ #  # ]:          0 :     if (LEAST_FIVE_BITS(a) != LEAST_FIVE_BITS(b)) {
          22                 :            :         // Not the same, not a case flip.
          23                 :          0 :         return MOVE_COST;
          24                 :            :     }
          25         [ #  # ]:          0 :     if (a == b) {
          26                 :          0 :         return 0;
          27                 :            :     }
          28   [ #  #  #  # ]:          0 :     if ('A' <= a && a <= 'Z') {
          29                 :          0 :         a += ('a' - 'A');
          30                 :            :     }
          31   [ #  #  #  # ]:          0 :     if ('A' <= b && b <= 'Z') {
          32                 :          0 :         b += ('a' - 'A');
          33                 :            :     }
          34         [ #  # ]:          0 :     if (a == b) {
          35                 :          0 :         return CASE_COST;
          36                 :            :     }
          37                 :          0 :     return MOVE_COST;
          38                 :            : }
          39                 :            :
          40                 :            : /* Calculate the Levenshtein distance between string1 and string2 */
          41                 :            : static Py_ssize_t
          42                 :          0 : levenshtein_distance(const char *a, size_t a_size,
          43                 :            :                      const char *b, size_t b_size,
          44                 :            :                      size_t max_cost, size_t *buffer)
          45                 :            : {
          46                 :            :     // Both strings are the same (by identity)
          47         [ #  # ]:          0 :     if (a == b) {
          48                 :          0 :         return 0;
          49                 :            :     }
          50                 :            :
          51                 :            :     // Trim away common affixes.
          52   [ #  #  #  #  :          0 :     while (a_size && b_size && a[0] == b[0]) {
                       #  # ]
          53                 :          0 :         a++; a_size--;
          54                 :          0 :         b++; b_size--;
          55                 :            :     }
          56   [ #  #  #  #  :          0 :     while (a_size && b_size && a[a_size-1] == b[b_size-1]) {
                       #  # ]
          57                 :          0 :         a_size--;
          58                 :          0 :         b_size--;
          59                 :            :     }
          60   [ #  #  #  # ]:          0 :     if (a_size == 0 || b_size == 0) {
          61                 :          0 :         return (a_size + b_size) * MOVE_COST;
          62                 :            :     }
          63   [ #  #  #  # ]:          0 :     if (a_size > MAX_STRING_SIZE || b_size > MAX_STRING_SIZE) {
          64                 :          0 :         return max_cost + 1;
          65                 :            :     }
          66                 :            :
          67                 :            :     // Prefer shorter buffer
          68         [ #  # ]:          0 :     if (b_size < a_size) {
          69                 :          0 :         const char *t = a; a = b; b = t;
          70                 :          0 :         size_t t_size = a_size; a_size = b_size; b_size = t_size;
          71                 :            :     }
          72                 :            :
          73                 :            :     // quick fail when a match is impossible.
          74         [ #  # ]:          0 :     if ((b_size - a_size) * MOVE_COST > max_cost) {
          75                 :          0 :         return max_cost + 1;
          76                 :            :     }
          77                 :            :
          78                 :            :     // Instead of producing the whole traditional len(a)-by-len(b)
          79                 :            :     // matrix, we can update just one row in place.
          80                 :            :     // Initialize the buffer row
          81                 :          0 :     size_t tmp = MOVE_COST;
          82         [ #  # ]:          0 :     for (size_t i = 0; i < a_size; i++) {
          83                 :            :         // cost from b[:0] to a[:i+1]
          84                 :          0 :         buffer[i] = tmp;
          85                 :          0 :         tmp += MOVE_COST;
          86                 :            :     }
          87                 :            :
          88                 :          0 :     size_t result = 0;
          89         [ #  # ]:          0 :     for (size_t b_index = 0; b_index < b_size; b_index++) {
          90                 :          0 :         char code = b[b_index];
          91                 :            :         // cost(b[:b_index], a[:0]) == b_index * MOVE_COST
          92                 :          0 :         size_t distance = result = b_index * MOVE_COST;
          93                 :          0 :         size_t minimum = SIZE_MAX;
          94         [ #  # ]:          0 :         for (size_t index = 0; index < a_size; index++) {
          95                 :            :
          96                 :            :             // cost(b[:b_index+1], a[:index+1]) = min(
          97                 :            :             //     // 1) substitute
          98                 :            :             //     cost(b[:b_index], a[:index])
          99                 :            :             //         + substitution_cost(b[b_index], a[index]),
         100                 :            :             //     // 2) delete from b
         101                 :            :             //     cost(b[:b_index], a[:index+1]) + MOVE_COST,
         102                 :            :             //     // 3) delete from a
         103                 :            :             //     cost(b[:b_index+1], a[index]) + MOVE_COST
         104                 :            :             // )
         105                 :            :
         106                 :            :             // 1) Previous distance in this row is cost(b[:b_index], a[:index])
         107                 :          0 :             size_t substitute = distance + substitution_cost(code, a[index]);
         108                 :            :             // 2) cost(b[:b_index], a[:index+1]) from previous row
         109                 :          0 :             distance = buffer[index];
         110                 :            :             // 3) existing result is cost(b[:b_index+1], a[index])
         111                 :            :
         112                 :          0 :             size_t insert_delete = Py_MIN(result, distance) + MOVE_COST;
         113                 :          0 :             result = Py_MIN(insert_delete, substitute);
         114                 :            :
         115                 :            :             // cost(b[:b_index+1], a[:index+1])
         116                 :          0 :             buffer[index] = result;
         117         [ #  # ]:          0 :             if (result < minimum) {
         118                 :          0 :                 minimum = result;
         119                 :            :             }
         120                 :            :         }
         121         [ #  # ]:          0 :         if (minimum > max_cost) {
         122                 :            :             // Everything in this row is too big, so bail early.
         123                 :          0 :             return max_cost + 1;
         124                 :            :         }
         125                 :            :     }
         126                 :          0 :     return result;
         127                 :            : }
         128                 :            :
         129                 :            : static inline PyObject *
         130                 :          0 : calculate_suggestions(PyObject *dir,
         131                 :            :                       PyObject *name)
         132                 :            : {
         133                 :            :     assert(!PyErr_Occurred());
         134                 :            :     assert(PyList_CheckExact(dir));
         135                 :            :
         136                 :          0 :     Py_ssize_t dir_size = PyList_GET_SIZE(dir);
         137         [ #  # ]:          0 :     if (dir_size >= MAX_CANDIDATE_ITEMS) {
         138                 :          0 :         return NULL;
         139                 :            :     }
         140                 :            :
         141                 :          0 :     Py_ssize_t suggestion_distance = PY_SSIZE_T_MAX;
         142                 :          0 :     PyObject *suggestion = NULL;
         143                 :            :     Py_ssize_t name_size;
         144                 :          0 :     const char *name_str = PyUnicode_AsUTF8AndSize(name, &name_size);
         145         [ #  # ]:          0 :     if (name_str == NULL) {
         146                 :          0 :         return NULL;
         147                 :            :     }
         148                 :          0 :     size_t *buffer = PyMem_New(size_t, MAX_STRING_SIZE);
         149         [ #  # ]:          0 :     if (buffer == NULL) {
         150                 :          0 :         return PyErr_NoMemory();
         151                 :            :     }
         152         [ #  # ]:          0 :     for (int i = 0; i < dir_size; ++i) {
         153                 :          0 :         PyObject *item = PyList_GET_ITEM(dir, i);
         154                 :            :         Py_ssize_t item_size;
         155                 :          0 :         const char *item_str = PyUnicode_AsUTF8AndSize(item, &item_size);
         156         [ #  # ]:          0 :         if (item_str == NULL) {
         157                 :          0 :             PyMem_Free(buffer);
         158                 :          0 :             return NULL;
         159                 :            :         }
         160         [ #  # ]:          0 :         if (PyUnicode_CompareWithASCIIString(name, item_str) == 0) {
         161                 :          0 :             continue;
         162                 :            :         }
         163                 :            :         // No more than 1/3 of the involved characters should need changed.
         164                 :          0 :         Py_ssize_t max_distance = (name_size + item_size + 3) * MOVE_COST / 6;
         165                 :            :         // Don't take matches we've already beaten.
         166                 :          0 :         max_distance = Py_MIN(max_distance, suggestion_distance - 1);
         167                 :            :         Py_ssize_t current_distance =
         168                 :          0 :             levenshtein_distance(name_str, name_size, item_str,
         169                 :            :                                  item_size, max_distance, buffer);
         170         [ #  # ]:          0 :         if (current_distance > max_distance) {
         171                 :          0 :             continue;
         172                 :            :         }
         173   [ #  #  #  # ]:          0 :         if (!suggestion || current_distance < suggestion_distance) {
         174                 :          0 :             suggestion = item;
         175                 :          0 :             suggestion_distance = current_distance;
         176                 :            :         }
         177                 :            :     }
         178                 :          0 :     PyMem_Free(buffer);
         179                 :          0 :     return Py_XNewRef(suggestion);
         180                 :            : }
         181                 :            :
         182                 :            : static PyObject *
         183                 :          0 : get_suggestions_for_attribute_error(PyAttributeErrorObject *exc)
         184                 :            : {
         185                 :          0 :     PyObject *name = exc->name; // borrowed reference
         186                 :          0 :     PyObject *obj = exc->obj; // borrowed reference
         187                 :            :
         188                 :            :     // Abort if we don't have an attribute name or we have an invalid one
         189   [ #  #  #  #  :          0 :     if (name == NULL || obj == NULL || !PyUnicode_CheckExact(name)) {
                       #  # ]
         190                 :          0 :         return NULL;
         191                 :            :     }
         192                 :            :
         193                 :          0 :     PyObject *dir = PyObject_Dir(obj);
         194         [ #  # ]:          0 :     if (dir == NULL) {
         195                 :          0 :         return NULL;
         196                 :            :     }
         197                 :            :
         198                 :          0 :     PyObject *suggestions = calculate_suggestions(dir, name);
         199                 :          0 :     Py_DECREF(dir);
         200                 :          0 :     return suggestions;
         201                 :            : }
         202                 :            :
         203                 :            : static PyObject *
         204                 :          0 : offer_suggestions_for_attribute_error(PyAttributeErrorObject *exc)
         205                 :            : {
         206                 :          0 :     PyObject* suggestion = get_suggestions_for_attribute_error(exc);
         207         [ #  # ]:          0 :     if (suggestion == NULL) {
         208                 :          0 :         return NULL;
         209                 :            :     }
         210                 :            :     // Add a trailer ". Did you mean: (...)?"
         211                 :          0 :     PyObject* result = PyUnicode_FromFormat(". Did you mean: %R?", suggestion);
         212                 :          0 :     Py_DECREF(suggestion);
         213                 :          0 :     return result;
         214                 :            : }
         215                 :            :
         216                 :            : static PyObject *
         217                 :          0 : get_suggestions_for_name_error(PyObject* name, PyFrameObject* frame)
         218                 :            : {
         219                 :          0 :     PyCodeObject *code = PyFrame_GetCode(frame);
         220                 :            :     assert(code != NULL && code->co_localsplusnames != NULL);
         221                 :            :
         222                 :          0 :     PyObject *varnames = _PyCode_GetVarnames(code);
         223         [ #  # ]:          0 :     if (varnames == NULL) {
         224                 :          0 :         return NULL;
         225                 :            :     }
         226                 :          0 :     PyObject *dir = PySequence_List(varnames);
         227                 :          0 :     Py_DECREF(varnames);
         228                 :          0 :     Py_DECREF(code);
         229         [ #  # ]:          0 :     if (dir == NULL) {
         230                 :          0 :         return NULL;
         231                 :            :     }
         232                 :            :
         233                 :            :     // Are we inside a method and the instance has an attribute called 'name'?
         234         [ #  # ]:          0 :     if (PySequence_Contains(dir, &_Py_ID(self)) > 0) {
         235                 :          0 :         PyObject* locals = PyFrame_GetLocals(frame);
         236         [ #  # ]:          0 :         if (!locals) {
         237                 :          0 :             goto error;
         238                 :            :         }
         239                 :          0 :         PyObject* self = PyDict_GetItem(locals, &_Py_ID(self)); /* borrowed */
         240                 :          0 :         Py_DECREF(locals);
         241         [ #  # ]:          0 :         if (!self) {
         242                 :          0 :             goto error;
         243                 :            :         }
         244                 :            :
         245         [ #  # ]:          0 :         if (PyObject_HasAttr(self, name)) {
         246                 :          0 :             Py_DECREF(dir);
         247                 :          0 :             return PyUnicode_FromFormat("self.%S", name);
         248                 :            :         }
         249                 :            :     }
         250                 :            :
         251                 :          0 :     PyObject *suggestions = calculate_suggestions(dir, name);
         252                 :          0 :     Py_DECREF(dir);
         253         [ #  # ]:          0 :     if (suggestions != NULL) {
         254                 :          0 :         return suggestions;
         255                 :            :     }
         256                 :            :
         257                 :          0 :     dir = PySequence_List(frame->f_frame->f_globals);
         258         [ #  # ]:          0 :     if (dir == NULL) {
         259                 :          0 :         return NULL;
         260                 :            :     }
         261                 :          0 :     suggestions = calculate_suggestions(dir, name);
         262                 :          0 :     Py_DECREF(dir);
         263         [ #  # ]:          0 :     if (suggestions != NULL) {
         264                 :          0 :         return suggestions;
         265                 :            :     }
         266                 :            :
         267                 :          0 :     dir = PySequence_List(frame->f_frame->f_builtins);
         268         [ #  # ]:          0 :     if (dir == NULL) {
         269                 :          0 :         return NULL;
         270                 :            :     }
         271                 :          0 :     suggestions = calculate_suggestions(dir, name);
         272                 :          0 :     Py_DECREF(dir);
         273                 :            :
         274                 :          0 :     return suggestions;
         275                 :            :
         276                 :          0 : error:
         277                 :          0 :     Py_DECREF(dir);
         278                 :          0 :     return NULL;
         279                 :            : }
         280                 :            :
         281                 :            : static bool
         282                 :          0 : is_name_stdlib_module(PyObject* name)
         283                 :            : {
         284                 :          0 :     const char* the_name = PyUnicode_AsUTF8(name);
         285                 :          0 :     Py_ssize_t len = Py_ARRAY_LENGTH(_Py_stdlib_module_names);
         286         [ #  # ]:          0 :     for (Py_ssize_t i = 0; i < len; i++) {
         287         [ #  # ]:          0 :         if (strcmp(the_name, _Py_stdlib_module_names[i]) == 0) {
         288                 :          0 :             return 1;
         289                 :            :         }
         290                 :            :     }
         291                 :          0 :     return 0;
         292                 :            : }
         293                 :            :
         294                 :            : static PyObject *
         295                 :          0 : offer_suggestions_for_name_error(PyNameErrorObject *exc)
         296                 :            : {
         297                 :          0 :     PyObject *name = exc->name; // borrowed reference
         298                 :          0 :     PyTracebackObject *traceback = (PyTracebackObject *) exc->traceback; // borrowed reference
         299                 :            :     // Abort if we don't have a variable name or we have an invalid one
         300                 :            :     // or if we don't have a traceback to work with
         301   [ #  #  #  #  :          0 :     if (name == NULL || !PyUnicode_CheckExact(name) ||
                       #  # ]
         302         [ #  # ]:          0 :         traceback == NULL || !Py_IS_TYPE(traceback, &PyTraceBack_Type)
         303                 :            :     ) {
         304                 :          0 :         return NULL;
         305                 :            :     }
         306                 :            :
         307                 :            :     // Move to the traceback of the exception
         308                 :          0 :     while (1) {
         309                 :          0 :         PyTracebackObject *next = traceback->tb_next;
         310   [ #  #  #  # ]:          0 :         if (next == NULL || !Py_IS_TYPE(next, &PyTraceBack_Type)) {
         311                 :            :             break;
         312                 :            :         }
         313                 :            :         else {
         314                 :          0 :             traceback = next;
         315                 :            :         }
         316                 :            :     }
         317                 :            :
         318                 :          0 :     PyFrameObject *frame = traceback->tb_frame;
         319                 :            :     assert(frame != NULL);
         320                 :            :
         321                 :          0 :     PyObject* suggestion = get_suggestions_for_name_error(name, frame);
         322                 :          0 :     bool is_stdlib_module = is_name_stdlib_module(name);
         323                 :            :
         324   [ #  #  #  # ]:          0 :     if (suggestion == NULL && !is_stdlib_module) {
         325                 :          0 :         return NULL;
         326                 :            :     }
         327                 :            :
         328                 :            :     // Add a trailer ". Did you mean: (...)?"
         329                 :          0 :     PyObject* result = NULL;
         330         [ #  # ]:          0 :     if (!is_stdlib_module) {
         331                 :          0 :         result = PyUnicode_FromFormat(". Did you mean: %R?", suggestion);
         332         [ #  # ]:          0 :     } else if (suggestion == NULL) {
         333                 :          0 :         result = PyUnicode_FromFormat(". Did you forget to import %R?", name);
         334                 :            :     } else {
         335                 :          0 :         result = PyUnicode_FromFormat(". Did you mean: %R? Or did you forget to import %R?", suggestion, name);
         336                 :            :     }
         337                 :          0 :     Py_XDECREF(suggestion);
         338                 :          0 :     return result;
         339                 :            : }
         340                 :            :
         341                 :            : static PyObject *
         342                 :          0 : offer_suggestions_for_import_error(PyImportErrorObject *exc)
         343                 :            : {
         344                 :          0 :     PyObject *mod_name = exc->name; // borrowed reference
         345                 :          0 :     PyObject *name = exc->name_from; // borrowed reference
         346   [ #  #  #  #  :          0 :     if (name == NULL || mod_name == NULL || name == Py_None ||
                 #  #  #  # ]
         347         [ #  # ]:          0 :         !PyUnicode_CheckExact(name) || !PyUnicode_CheckExact(mod_name)) {
         348                 :          0 :         return NULL;
         349                 :            :     }
         350                 :            :
         351                 :          0 :     PyObject* mod = PyImport_GetModule(mod_name);
         352         [ #  # ]:          0 :     if (mod == NULL) {
         353                 :          0 :         return NULL;
         354                 :            :     }
         355                 :            :
         356                 :          0 :     PyObject *dir = PyObject_Dir(mod);
         357                 :          0 :     Py_DECREF(mod);
         358         [ #  # ]:          0 :     if (dir == NULL) {
         359                 :          0 :         return NULL;
         360                 :            :     }
         361                 :            :
         362                 :          0 :     PyObject *suggestion = calculate_suggestions(dir, name);
         363                 :          0 :     Py_DECREF(dir);
         364         [ #  # ]:          0 :     if (!suggestion) {
         365                 :          0 :         return NULL;
         366                 :            :     }
         367                 :            :
         368                 :          0 :     PyObject* result = PyUnicode_FromFormat(". Did you mean: %R?", suggestion);
         369                 :          0 :     Py_DECREF(suggestion);
         370                 :          0 :     return result;
         371                 :            : }
         372                 :            :
         373                 :            : // Offer suggestions for a given exception. Returns a python string object containing the
         374                 :            : // suggestions. This function returns NULL if no suggestion was found or if an exception happened,
         375                 :            : // users must call PyErr_Occurred() to disambiguate.
         376                 :            : PyObject *
         377                 :          0 : _Py_Offer_Suggestions(PyObject *exception)
         378                 :            : {
         379                 :          0 :     PyObject *result = NULL;
         380                 :            :     assert(!PyErr_Occurred());
         381         [ #  # ]:          0 :     if (Py_IS_TYPE(exception, (PyTypeObject*)PyExc_AttributeError)) {
         382                 :          0 :         result = offer_suggestions_for_attribute_error((PyAttributeErrorObject *) exception);
         383         [ #  # ]:          0 :     } else if (Py_IS_TYPE(exception, (PyTypeObject*)PyExc_NameError)) {
         384                 :          0 :         result = offer_suggestions_for_name_error((PyNameErrorObject *) exception);
         385         [ #  # ]:          0 :     } else if (Py_IS_TYPE(exception, (PyTypeObject*)PyExc_ImportError)) {
         386                 :          0 :         result = offer_suggestions_for_import_error((PyImportErrorObject *) exception);
         387                 :            :     }
         388                 :          0 :     return result;
         389                 :            : }
         390                 :            :
         391                 :            : Py_ssize_t
         392                 :          0 : _Py_UTF8_Edit_Cost(PyObject *a, PyObject *b, Py_ssize_t max_cost)
         393                 :            : {
         394                 :            :     assert(PyUnicode_Check(a) && PyUnicode_Check(b));
         395                 :            :     Py_ssize_t size_a, size_b;
         396                 :          0 :     const char *utf8_a = PyUnicode_AsUTF8AndSize(a, &size_a);
         397         [ #  # ]:          0 :     if (utf8_a == NULL) {
         398                 :          0 :         return -1;
         399                 :            :     }
         400                 :          0 :     const char *utf8_b = PyUnicode_AsUTF8AndSize(b, &size_b);
         401         [ #  # ]:          0 :     if (utf8_b == NULL) {
         402                 :          0 :         return -1;
         403                 :            :     }
         404         [ #  # ]:          0 :     if (max_cost == -1) {
         405                 :          0 :         max_cost = MOVE_COST * Py_MAX(size_a, size_b);
         406                 :            :     }
         407                 :          0 :     size_t *buffer = PyMem_New(size_t, MAX_STRING_SIZE);
         408         [ #  # ]:          0 :     if (buffer == NULL) {
         409                 :          0 :         PyErr_NoMemory();
         410                 :          0 :         return -1;
         411                 :            :     }
         412                 :          0 :     Py_ssize_t res = levenshtein_distance(utf8_a, size_a,
         413                 :            :                                     utf8_b, size_b, max_cost, buffer);
         414                 :          0 :     PyMem_Free(buffer);
         415                 :          0 :     return res;
         416                 :            : }
         417                 :            :

Generated by: LCOV version 1.14