LCOV - code coverage report
Current view: | top level - Modules - _functoolsmodule.c (source / functions) |  |  | Hit | Total | Coverage
Test: | CPython 3.12 LCOV report [commit 5e6661bce9] |  | Lines: | 295 | 622 | 47.4 %
Date: | 2023-03-20 08:15:36 |  | Functions: | 33 | 46 | 71.7 %
|  |  | Branches: | 127 | 388 | 32.7 %

               Branch data     Line data    Source code
           1                 :            : #include "Python.h"
           2                 :            : #include "pycore_call.h"          // _PyObject_CallNoArgs()
           3                 :            : #include "pycore_dict.h"          // _PyDict_Pop_KnownHash()
           4                 :            : #include "pycore_long.h"          // _PyLong_GetZero()
           5                 :            : #include "pycore_moduleobject.h"  // _PyModule_GetState()
           6                 :            : #include "pycore_object.h"        // _PyObject_GC_TRACK
           7                 :            : #include "pycore_pystate.h"       // _PyThreadState_GET()
           8                 :            : #include "pycore_tuple.h"         // _PyTuple_ITEMS()
           9                 :            : #include "structmember.h"         // PyMemberDef
          10                 :            :
          11                 :            : #include "clinic/_functoolsmodule.c.h"
          12                 :            : /*[clinic input]
          13                 :            : module _functools
          14                 :            : class _functools._lru_cache_wrapper "PyObject *" "&lru_cache_type_spec"
          15                 :            : [clinic start generated code]*/
          16                 :            : /*[clinic end generated code: output=da39a3ee5e6b4b0d input=bece4053896b09c0]*/
          17                 :            :
          18                 :            : /* _functools module written and maintained
          19                 :            :    by Hye-Shik Chang <perky@FreeBSD.org>
          20                 :            :    with adaptations by Raymond Hettinger <python@rcn.com>
          21                 :            :    Copyright (c) 2004, 2005, 2006 Python Software Foundation.
          22                 :            :    All rights reserved.
          23                 :            : */
          24                 :            :
          25                 :            : typedef struct _functools_state {
          26                 :            :     /* this object is used delimit args and keywords in the cache keys */
          27                 :            :     PyObject *kwd_mark;
          28                 :            :     PyTypeObject *partial_type;
          29                 :            :     PyTypeObject *keyobject_type;
          30                 :            :     PyTypeObject *lru_list_elem_type;
          31                 :            : } _functools_state;
          32                 :            :
          33                 :            : static inline _functools_state *
          34                 :        142 : get_functools_state(PyObject *module)
          35                 :            : {
          36                 :        142 :     void *state = _PyModule_GetState(module);
          37                 :            :     assert(state != NULL);
          38                 :        142 :     return (_functools_state *)state;
          39                 :            : }
          40                 :            :
          41                 :            :
          42                 :            : /* partial object **********************************************************/
          43                 :            :
          44                 :            : typedef struct {
          45                 :            :     PyObject_HEAD
          46                 :            :     PyObject *fn;
          47                 :            :     PyObject *args;
          48                 :            :     PyObject *kw;
          49                 :            :     PyObject *dict;        /* __dict__ */
          50                 :            :     PyObject *weakreflist; /* List of weak references */
          51                 :            :     vectorcallfunc vectorcall;
          52                 :            : } partialobject;
          53                 :            :
          54                 :            : static void partial_setvectorcall(partialobject *pto);
          55                 :            : static struct PyModuleDef _functools_module;
          56                 :            : static PyObject *
          57                 :            : partial_call(partialobject *pto, PyObject *args, PyObject *kwargs);
          58                 :            :
          59                 :            : static inline _functools_state *
          60                 :         38 : get_functools_state_by_type(PyTypeObject *type)
          61                 :            : {
          62                 :         38 :     PyObject *module = PyType_GetModuleByDef(type, &_functools_module);
          63         [ -  + ]:         38 :     if (module == NULL) {
          64                 :          0 :         return NULL;
          65                 :            :     }
          66                 :         38 :     return get_functools_state(module);
          67                 :            : }
          68                 :            :
          69                 :            : // Not converted to argument clinic, because of `*args, **kwargs` arguments.
          70                 :            : static PyObject *
          71                 :         78 : partial_new(PyTypeObject *type, PyObject *args, PyObject *kw)
          72                 :            : {
          73                 :            :     PyObject *func, *pargs, *nargs, *pkw;
          74                 :            :     partialobject *pto;
          75                 :            :
          76         [ -  + ]:         78 :     if (PyTuple_GET_SIZE(args) < 1) {
          77                 :          0 :         PyErr_SetString(PyExc_TypeError,
          78                 :            :                         "type 'partial' takes at least one argument");
          79                 :          0 :         return NULL;
          80                 :            :     }
          81                 :            :
          82                 :         78 :     pargs = pkw = NULL;
          83                 :         78 :     func = PyTuple_GET_ITEM(args, 0);
          84         [ -  + ]:         78 :     if (Py_TYPE(func)->tp_call == (ternaryfunc)partial_call) {
          85                 :            :         // The type of "func" might not be exactly the same type object
          86                 :            :         // as "type", but if it is called using partial_call, it must have the
          87                 :            :         // same memory layout (fn, args and kw members).
          88                 :            :         // We can use its underlying function directly and merge the arguments.
          89                 :          0 :         partialobject *part = (partialobject *)func;
          90         [ #  # ]:          0 :         if (part->dict == NULL) {
          91                 :          0 :             pargs = part->args;
          92                 :          0 :             pkw = part->kw;
          93                 :          0 :             func = part->fn;
          94                 :            :             assert(PyTuple_Check(pargs));
          95                 :            :             assert(PyDict_Check(pkw));
          96                 :            :         }
          97                 :            :     }
          98         [ -  + ]:         78 :     if (!PyCallable_Check(func)) {
          99                 :          0 :         PyErr_SetString(PyExc_TypeError,
         100                 :            :                         "the first argument must be callable");
         101                 :          0 :         return NULL;
         102                 :            :     }
         103                 :            :
         104                 :            :     /* create partialobject structure */
         105                 :         78 :     pto = (partialobject *)type->tp_alloc(type, 0);
         106         [ -  + ]:         78 :     if (pto == NULL)
         107                 :          0 :         return NULL;
         108                 :            :
         109                 :         78 :     pto->fn = Py_NewRef(func);
         110                 :            :
         111                 :         78 :     nargs = PyTuple_GetSlice(args, 1, PY_SSIZE_T_MAX);
         112         [ -  + ]:         78 :     if (nargs == NULL) {
         113                 :          0 :         Py_DECREF(pto);
         114                 :          0 :         return NULL;
         115                 :            :     }
         116         [ +  - ]:         78 :     if (pargs == NULL) {
         117                 :         78 :         pto->args = nargs;
         118                 :            :     }
         119                 :            :     else {
         120                 :          0 :         pto->args = PySequence_Concat(pargs, nargs);
         121                 :          0 :         Py_DECREF(nargs);
         122         [ #  # ]:          0 :         if (pto->args == NULL) {
         123                 :          0 :             Py_DECREF(pto);
         124                 :          0 :             return NULL;
         125                 :            :         }
         126                 :            :         assert(PyTuple_Check(pto->args));
         127                 :            :     }
         128                 :            :
         129   [ -  +  -  - ]:         78 :     if (pkw == NULL || PyDict_GET_SIZE(pkw) == 0) {
         130         [ +  + ]:         78 :         if (kw == NULL) {
         131                 :          5 :             pto->kw = PyDict_New();
         132                 :            :         }
         133         [ +  - ]:         73 :         else if (Py_REFCNT(kw) == 1) {
         134                 :         73 :             pto->kw = Py_NewRef(kw);
         135                 :            :         }
         136                 :            :         else {
         137                 :          0 :             pto->kw = PyDict_Copy(kw);
         138                 :            :         }
         139                 :            :     }
         140                 :            :     else {
         141                 :          0 :         pto->kw = PyDict_Copy(pkw);
         142   [ #  #  #  # ]:          0 :         if (kw != NULL && pto->kw != NULL) {
         143         [ #  # ]:          0 :             if (PyDict_Merge(pto->kw, kw, 1) != 0) {
         144                 :          0 :                 Py_DECREF(pto);
         145                 :          0 :                 return NULL;
         146                 :            :             }
         147                 :            :         }
         148                 :            :     }
         149         [ -  + ]:         78 :     if (pto->kw == NULL) {
         150                 :          0 :         Py_DECREF(pto);
         151                 :          0 :         return NULL;
         152                 :            :     }
         153                 :            :
         154                 :         78 :     partial_setvectorcall(pto);
         155                 :         78 :     return (PyObject *)pto;
         156                 :            : }
         157                 :            :
         158                 :            : static int
         159                 :         78 : partial_clear(partialobject *pto)
         160                 :            : {
         161         [ +  - ]:         78 :     Py_CLEAR(pto->fn);
         162         [ +  - ]:         78 :     Py_CLEAR(pto->args);
         163         [ +  - ]:         78 :     Py_CLEAR(pto->kw);
         164         [ -  + ]:         78 :     Py_CLEAR(pto->dict);
         165                 :         78 :     return 0;
         166                 :            : }
         167                 :            :
         168                 :            : static int
         169                 :         56 : partial_traverse(partialobject *pto, visitproc visit, void *arg)
         170                 :            : {
         171   [ +  -  -  + ]:         56 :     Py_VISIT(Py_TYPE(pto));
         172   [ +  -  -  + ]:         56 :     Py_VISIT(pto->fn);
         173   [ +  -  -  + ]:         56 :     Py_VISIT(pto->args);
         174   [ +  -  -  + ]:         56 :     Py_VISIT(pto->kw);
         175   [ -  +  -  - ]:         56 :     Py_VISIT(pto->dict);
         176                 :         56 :     return 0;
         177                 :            : }
         178                 :            :
         179                 :            : static void
         180                 :         78 : partial_dealloc(partialobject *pto)
         181                 :            : {
         182                 :         78 :     PyTypeObject *tp = Py_TYPE(pto);
         183                 :            :     /* bpo-31095: UnTrack is needed before calling any callbacks */
         184                 :         78 :     PyObject_GC_UnTrack(pto);
         185         [ -  + ]:         78 :     if (pto->weakreflist != NULL) {
         186                 :          0 :         PyObject_ClearWeakRefs((PyObject *) pto);
         187                 :            :     }
         188                 :         78 :     (void)partial_clear(pto);
         189                 :         78 :     tp->tp_free(pto);
         190                 :         78 :     Py_DECREF(tp);
         191                 :         78 : }
         192                 :            :
         193                 :            :
         194                 :            : /* Merging keyword arguments using the vectorcall convention is messy, so
         195                 :            :  * if we would need to do that, we stop using vectorcall and fall back
         196                 :            :  * to using partial_call() instead. */
         197                 :            : Py_NO_INLINE static PyObject *
         198                 :         72 : partial_vectorcall_fallback(PyThreadState *tstate, partialobject *pto,
         199                 :            :                             PyObject *const *args, size_t nargsf,
         200                 :            :                             PyObject *kwnames)
         201                 :            : {
         202                 :         72 :     pto->vectorcall = NULL;
         203                 :         72 :     Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);
         204                 :         72 :     return _PyObject_MakeTpCall(tstate, (PyObject *)pto,
         205                 :            :                                 args, nargs, kwnames);
         206                 :            : }
         207                 :            :
         208                 :            : static PyObject *
         209                 :         73 : partial_vectorcall(partialobject *pto, PyObject *const *args,
         210                 :            :                    size_t nargsf, PyObject *kwnames)
         211                 :            : {
         212                 :         73 :     PyThreadState *tstate = _PyThreadState_GET();
         213                 :            :
         214                 :            :     /* pto->kw is mutable, so need to check every time */
         215         [ +  + ]:         73 :     if (PyDict_GET_SIZE(pto->kw)) {
         216                 :         72 :         return partial_vectorcall_fallback(tstate, pto, args, nargsf, kwnames);
         217                 :            :     }
         218                 :            :
         219                 :          1 :     Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);
         220                 :          1 :     Py_ssize_t nargs_total = nargs;
         221         [ -  + ]:          1 :     if (kwnames != NULL) {
         222                 :          0 :         nargs_total += PyTuple_GET_SIZE(kwnames);
         223                 :            :     }
         224                 :            :
         225                 :          1 :     PyObject **pto_args = _PyTuple_ITEMS(pto->args);
         226                 :          1 :     Py_ssize_t pto_nargs = PyTuple_GET_SIZE(pto->args);
         227                 :            :
         228                 :            :     /* Fast path if we're called without arguments */
         229         [ +  - ]:          1 :     if (nargs_total == 0) {
         230                 :          1 :         return _PyObject_VectorcallTstate(tstate, pto->fn,
         231                 :            :                                           pto_args, pto_nargs, NULL);
         232                 :            :     }
         233                 :            :
         234                 :            :     /* Fast path using PY_VECTORCALL_ARGUMENTS_OFFSET to prepend a single
         235                 :            :      * positional argument */
         236   [ #  #  #  # ]:          0 :     if (pto_nargs == 1 && (nargsf & PY_VECTORCALL_ARGUMENTS_OFFSET)) {
         237                 :          0 :         PyObject **newargs = (PyObject **)args - 1;
         238                 :          0 :         PyObject *tmp = newargs[0];
         239                 :          0 :         newargs[0] = pto_args[0];
         240                 :          0 :         PyObject *ret = _PyObject_VectorcallTstate(tstate, pto->fn,
         241                 :          0 :                                                    newargs, nargs + 1, kwnames);
         242                 :          0 :         newargs[0] = tmp;
         243                 :          0 :         return ret;
         244                 :            :     }
         245                 :            :
         246                 :          0 :     Py_ssize_t newnargs_total = pto_nargs + nargs_total;
         247                 :            :
         248                 :            :     PyObject *small_stack[_PY_FASTCALL_SMALL_STACK];
         249                 :            :     PyObject *ret;
         250                 :            :     PyObject **stack;
         251                 :            :
         252         [ #  # ]:          0 :     if (newnargs_total <= (Py_ssize_t)Py_ARRAY_LENGTH(small_stack)) {
         253                 :          0 :         stack = small_stack;
         254                 :            :     }
         255                 :            :     else {
         256                 :          0 :         stack = PyMem_Malloc(newnargs_total * sizeof(PyObject *));
         257         [ #  # ]:          0 :         if (stack == NULL) {
         258                 :          0 :             PyErr_NoMemory();
         259                 :          0 :             return NULL;
         260                 :            :         }
         261                 :            :     }
         262                 :            :
         263                 :            :     /* Copy to new stack, using borrowed references */
         264                 :          0 :     memcpy(stack, pto_args, pto_nargs * sizeof(PyObject*));
         265                 :          0 :     memcpy(stack + pto_nargs, args, nargs_total * sizeof(PyObject*));
         266                 :            :
         267                 :          0 :     ret = _PyObject_VectorcallTstate(tstate, pto->fn,
         268                 :          0 :                                      stack, pto_nargs + nargs, kwnames);
         269         [ #  # ]:          0 :     if (stack != small_stack) {
         270                 :          0 :         PyMem_Free(stack);
         271                 :            :     }
         272                 :          0 :     return ret;
         273                 :            : }
         274                 :            :
         275                 :            : /* Set pto->vectorcall depending on the parameters of the partial object */
         276                 :            : static void
         277                 :         78 : partial_setvectorcall(partialobject *pto)
         278                 :            : {
         279         [ +  + ]:         78 :     if (_PyVectorcall_Function(pto->fn) == NULL) {
         280                 :            :         /* Don't use vectorcall if the underlying function doesn't support it */
         281                 :          4 :         pto->vectorcall = NULL;
         282                 :            :     }
         283                 :            :     /* We could have a special case if there are no arguments,
         284                 :            :      * but that is unlikely (why use partial without arguments?),
         285                 :            :      * so we don't optimize that */
         286                 :            :     else {
         287                 :         74 :         pto->vectorcall = (vectorcallfunc)partial_vectorcall;
         288                 :            :     }
         289                 :         78 : }
         290                 :            :
         291                 :            :
         292                 :            : // Not converted to argument clinic, because of `*args, **kwargs` arguments.
         293                 :            : static PyObject *
         294                 :         73 : partial_call(partialobject *pto, PyObject *args, PyObject *kwargs)
         295                 :            : {
         296                 :            :     assert(PyCallable_Check(pto->fn));
         297                 :            :     assert(PyTuple_Check(pto->args));
         298                 :            :     assert(PyDict_Check(pto->kw));
         299                 :            :
         300                 :            :     /* Merge keywords */
         301                 :            :     PyObject *kwargs2;
         302         [ -  + ]:         73 :     if (PyDict_GET_SIZE(pto->kw) == 0) {
         303                 :            :         /* kwargs can be NULL */
         304                 :          0 :         kwargs2 = Py_XNewRef(kwargs);
         305                 :            :     }
         306                 :            :     else {
         307                 :            :         /* bpo-27840, bpo-29318: dictionary of keyword parameters must be
         308                 :            :            copied, because a function using "**kwargs" can modify the
         309                 :            :            dictionary. */
         310                 :         73 :         kwargs2 = PyDict_Copy(pto->kw);
         311         [ -  + ]:         73 :         if (kwargs2 == NULL) {
         312                 :          0 :             return NULL;
         313                 :            :         }
         314                 :            :
         315         [ -  + ]:         73 :         if (kwargs != NULL) {
         316         [ #  # ]:          0 :             if (PyDict_Merge(kwargs2, kwargs, 1) != 0) {
         317                 :          0 :                 Py_DECREF(kwargs2);
         318                 :          0 :                 return NULL;
         319                 :            :             }
         320                 :            :         }
         321                 :            :     }
         322                 :            :
         323                 :            :     /* Merge positional arguments */
         324                 :            :     /* Note: tupleconcat() is optimized for empty tuples */
         325                 :         73 :     PyObject *args2 = PySequence_Concat(pto->args, args);
         326         [ -  + ]:         73 :     if (args2 == NULL) {
         327                 :          0 :         Py_XDECREF(kwargs2);
         328                 :          0 :         return NULL;
         329                 :            :     }
         330                 :            :
         331                 :         73 :     PyObject *res = PyObject_Call(pto->fn, args2, kwargs2);
         332                 :         73 :     Py_DECREF(args2);
         333                 :         73 :     Py_XDECREF(kwargs2);
         334                 :         73 :     return res;
         335                 :            : }
         336                 :            :
         337                 :            : PyDoc_STRVAR(partial_doc,
         338                 :            : "partial(func, *args, **keywords) - new function with partial application\n\
         339                 :            :     of the given arguments and keywords.\n");
         340                 :            :
         341                 :            : #define OFF(x) offsetof(partialobject, x)
         342                 :            : static PyMemberDef partial_memberlist[] = {
         343                 :            :     {"func",            T_OBJECT,       OFF(fn),        READONLY,
         344                 :            :      "function object to use in future partial calls"},
         345                 :            :     {"args",            T_OBJECT,       OFF(args),      READONLY,
         346                 :            :      "tuple of arguments to future partial calls"},
         347                 :            :     {"keywords",        T_OBJECT,       OFF(kw),        READONLY,
         348                 :            :      "dictionary of keyword arguments to future partial calls"},
         349                 :            :     {"__weaklistoffset__", T_PYSSIZET,
         350                 :            :      offsetof(partialobject, weakreflist), READONLY},
         351                 :            :     {"__dictoffset__", T_PYSSIZET,
         352                 :            :      offsetof(partialobject, dict), READONLY},
         353                 :            :     {"__vectorcalloffset__", T_PYSSIZET,
         354                 :            :      offsetof(partialobject, vectorcall), READONLY},
         355                 :            :     {NULL}  /* Sentinel */
         356                 :            : };
         357                 :            :
         358                 :            : static PyGetSetDef partial_getsetlist[] = {
         359                 :            :     {"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict},
         360                 :            :     {NULL} /* Sentinel */
         361                 :            : };
         362                 :            :
         363                 :            : static PyObject *
         364                 :          0 : partial_repr(partialobject *pto)
         365                 :            : {
         366                 :          0 :     PyObject *result = NULL;
         367                 :            :     PyObject *arglist;
         368                 :            :     Py_ssize_t i, n;
         369                 :            :     PyObject *key, *value;
         370                 :            :     int status;
         371                 :            :
         372                 :          0 :     status = Py_ReprEnter((PyObject *)pto);
         373         [ #  # ]:          0 :     if (status != 0) {
         374         [ #  # ]:          0 :         if (status < 0)
         375                 :          0 :             return NULL;
         376                 :          0 :         return PyUnicode_FromString("...");
         377                 :            :     }
         378                 :            :
         379                 :          0 :     arglist = PyUnicode_FromString("");
         380         [ #  # ]:          0 :     if (arglist == NULL)
         381                 :          0 :         goto done;
         382                 :            :     /* Pack positional arguments */
         383                 :            :     assert (PyTuple_Check(pto->args));
         384                 :          0 :     n = PyTuple_GET_SIZE(pto->args);
         385         [ #  # ]:          0 :     for (i = 0; i < n; i++) {
         386                 :          0 :         Py_SETREF(arglist, PyUnicode_FromFormat("%U, %R", arglist,
         387                 :            :                                         PyTuple_GET_ITEM(pto->args, i)));
         388         [ #  # ]:          0 :         if (arglist == NULL)
         389                 :          0 :             goto done;
         390                 :            :     }
         391                 :            :     /* Pack keyword arguments */
         392                 :            :     assert (PyDict_Check(pto->kw));
         393         [ #  # ]:          0 :     for (i = 0; PyDict_Next(pto->kw, &i, &key, &value);) {
         394                 :            :         /* Prevent key.__str__ from deleting the value. */
         395                 :          0 :         Py_INCREF(value);
         396                 :          0 :         Py_SETREF(arglist, PyUnicode_FromFormat("%U, %S=%R", arglist,
         397                 :            :                                                 key, value));
         398                 :          0 :         Py_DECREF(value);
         399         [ #  # ]:          0 :         if (arglist == NULL)
         400                 :          0 :             goto done;
         401                 :            :     }
         402                 :          0 :     result = PyUnicode_FromFormat("%s(%R%U)", Py_TYPE(pto)->tp_name,
         403                 :            :                                   pto->fn, arglist);
         404                 :          0 :     Py_DECREF(arglist);
         405                 :            :
         406                 :          0 :  done:
         407                 :          0 :     Py_ReprLeave((PyObject *)pto);
         408                 :          0 :     return result;
         409                 :            : }
         410                 :            :
         411                 :            : /* Pickle strategy:
         412                 :            :    __reduce__ by itself doesn't support getting kwargs in the unpickle
         413                 :            :    operation so we define a __setstate__ that replaces all the information
         414                 :            :    about the partial.  If we only replaced part of it someone would use
         415                 :            :    it as a hook to do strange things.
         416                 :            :  */
         417                 :            :
         418                 :            : static PyObject *
         419                 :          0 : partial_reduce(partialobject *pto, PyObject *unused)
         420                 :            : {
         421                 :          0 :     return Py_BuildValue("O(O)(OOOO)", Py_TYPE(pto), pto->fn, pto->fn,
         422                 :            :                          pto->args, pto->kw,
         423         [ #  # ]:          0 :                          pto->dict ? pto->dict : Py_None);
         424                 :            : }
         425                 :            :
         426                 :            : static PyObject *
         427                 :          0 : partial_setstate(partialobject *pto, PyObject *state)
         428                 :            : {
         429                 :            :     PyObject *fn, *fnargs, *kw, *dict;
         430                 :            :
         431   [ #  #  #  # ]:          0 :     if (!PyTuple_Check(state) ||
         432         [ #  # ]:          0 :         !PyArg_ParseTuple(state, "OOOO", &fn, &fnargs, &kw, &dict) ||
         433         [ #  # ]:          0 :         !PyCallable_Check(fn) ||
         434                 :          0 :         !PyTuple_Check(fnargs) ||
         435   [ #  #  #  # ]:          0 :         (kw != Py_None && !PyDict_Check(kw)))
         436                 :            :     {
         437                 :          0 :         PyErr_SetString(PyExc_TypeError, "invalid partial state");
         438                 :          0 :         return NULL;
         439                 :            :     }
         440                 :            :
         441         [ #  # ]:          0 :     if(!PyTuple_CheckExact(fnargs))
         442                 :          0 :         fnargs = PySequence_Tuple(fnargs);
         443                 :            :     else
         444                 :          0 :         Py_INCREF(fnargs);
         445         [ #  # ]:          0 :     if (fnargs == NULL)
         446                 :          0 :         return NULL;
         447                 :            :
         448         [ #  # ]:          0 :     if (kw == Py_None)
         449                 :          0 :         kw = PyDict_New();
         450         [ #  # ]:          0 :     else if(!PyDict_CheckExact(kw))
         451                 :          0 :         kw = PyDict_Copy(kw);
         452                 :            :     else
         453                 :          0 :         Py_INCREF(kw);
         454         [ #  # ]:          0 :     if (kw == NULL) {
         455                 :          0 :         Py_DECREF(fnargs);
         456                 :          0 :         return NULL;
         457                 :            :     }
         458                 :            :
         459         [ #  # ]:          0 :     if (dict == Py_None)
         460                 :          0 :         dict = NULL;
         461                 :            :     else
         462                 :          0 :         Py_INCREF(dict);
         463                 :            :
         464                 :          0 :     Py_SETREF(pto->fn, Py_NewRef(fn));
         465                 :          0 :     Py_SETREF(pto->args, fnargs);
         466                 :          0 :     Py_SETREF(pto->kw, kw);
         467                 :          0 :     Py_XSETREF(pto->dict, dict);
         468                 :          0 :     partial_setvectorcall(pto);
         469                 :          0 :     Py_RETURN_NONE;
         470                 :            : }
         471                 :            :
         472                 :            : static PyMethodDef partial_methods[] = {
         473                 :            :     {"__reduce__", (PyCFunction)partial_reduce, METH_NOARGS},
         474                 :            :     {"__setstate__", (PyCFunction)partial_setstate, METH_O},
         475                 :            :     {"__class_getitem__",    Py_GenericAlias,
         476                 :            :     METH_O|METH_CLASS,       PyDoc_STR("See PEP 585")},
         477                 :            :     {NULL,              NULL}           /* sentinel */
         478                 :            : };
         479                 :            :
         480                 :            : static PyType_Slot partial_type_slots[] = {
         481                 :            :     {Py_tp_dealloc, partial_dealloc},
         482                 :            :     {Py_tp_repr, partial_repr},
         483                 :            :     {Py_tp_call, partial_call},
         484                 :            :     {Py_tp_getattro, PyObject_GenericGetAttr},
         485                 :            :     {Py_tp_setattro, PyObject_GenericSetAttr},
         486                 :            :     {Py_tp_doc, (void *)partial_doc},
         487                 :            :     {Py_tp_traverse, partial_traverse},
         488                 :            :     {Py_tp_clear, partial_clear},
         489                 :            :     {Py_tp_methods, partial_methods},
         490                 :            :     {Py_tp_members, partial_memberlist},
         491                 :            :     {Py_tp_getset, partial_getsetlist},
         492                 :            :     {Py_tp_new, partial_new},
         493                 :            :     {Py_tp_free, PyObject_GC_Del},
         494                 :            :     {0, 0}
         495                 :            : };
         496                 :            :
         497                 :            : static PyType_Spec partial_type_spec = {
         498                 :            :     .name = "functools.partial",
         499                 :            :     .basicsize = sizeof(partialobject),
         500                 :            :     .flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
         501                 :            :              Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_VECTORCALL |
         502                 :            :              Py_TPFLAGS_IMMUTABLETYPE,
         503                 :            :     .slots = partial_type_slots
         504                 :            : };
         505                 :            :
         506                 :            :
         507                 :            : /* cmp_to_key ***************************************************************/
         508                 :            :
         509                 :            : typedef struct {
         510                 :            :     PyObject_HEAD
         511                 :            :     PyObject *cmp;
         512                 :            :     PyObject *object;
         513                 :            : } keyobject;
         514                 :            :
         515                 :            : static int
         516                 :         79 : keyobject_clear(keyobject *ko)
         517                 :            : {
         518         [ +  - ]:         79 :     Py_CLEAR(ko->cmp);
         519         [ +  + ]:         79 :     Py_CLEAR(ko->object);
         520                 :         79 :     return 0;
         521                 :            : }
         522                 :            :
         523                 :            : static void
         524                 :         79 : keyobject_dealloc(keyobject *ko)
         525                 :            : {
         526                 :         79 :     PyTypeObject *tp = Py_TYPE(ko);
         527                 :         79 :     PyObject_GC_UnTrack(ko);
         528                 :         79 :     (void)keyobject_clear(ko);
         529                 :         79 :     tp->tp_free(ko);
         530                 :         79 :     Py_DECREF(tp);
         531                 :         79 : }
         532                 :            :
         533                 :            : static int
         534                 :          0 : keyobject_traverse(keyobject *ko, visitproc visit, void *arg)
         535                 :            : {
         536   [ #  #  #  # ]:          0 :     Py_VISIT(Py_TYPE(ko));
         537   [ #  #  #  # ]:          0 :     Py_VISIT(ko->cmp);
         538   [ #  #  #  # ]:          0 :     Py_VISIT(ko->object);
         539                 :          0 :     return 0;
         540                 :            : }
         541                 :            :
         542                 :            : static PyMemberDef keyobject_members[] = {
         543                 :            :     {"obj", T_OBJECT,
         544                 :            :      offsetof(keyobject, object), 0,
         545                 :            :      PyDoc_STR("Value wrapped by a key function.")},
         546                 :            :     {NULL}
         547                 :            : };
         548                 :            :
         549                 :            : static PyObject *
         550                 :            : keyobject_call(keyobject *ko, PyObject *args, PyObject *kwds);
         551                 :            :
         552                 :            : static PyObject *
         553                 :            : keyobject_richcompare(PyObject *ko, PyObject *other, int op);
         554                 :            :
         555                 :            : static PyType_Slot keyobject_type_slots[] = {
         556                 :            :     {Py_tp_dealloc, keyobject_dealloc},
         557                 :            :     {Py_tp_call, keyobject_call},
         558                 :            :     {Py_tp_getattro, PyObject_GenericGetAttr},
         559                 :            :     {Py_tp_traverse, keyobject_traverse},
         560                 :            :     {Py_tp_clear, keyobject_clear},
         561                 :            :     {Py_tp_richcompare, keyobject_richcompare},
         562                 :            :     {Py_tp_members, keyobject_members},
         563                 :            :     {0, 0}
         564                 :            : };
         565                 :            :
         566                 :            : static PyType_Spec keyobject_type_spec = {
         567                 :            :     .name = "functools.KeyWrapper",
         568                 :            :     .basicsize = sizeof(keyobject),
         569                 :            :     .flags = (Py_TPFLAGS_DEFAULT | Py_TPFLAGS_DISALLOW_INSTANTIATION |
         570                 :            :               Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_IMMUTABLETYPE),
         571                 :            :     .slots = keyobject_type_slots
         572                 :            : };
         573                 :            :
         574                 :            : static PyObject *
         575                 :         77 : keyobject_call(keyobject *ko, PyObject *args, PyObject *kwds)
         576                 :            : {
         577                 :            :     PyObject *object;
         578                 :            :     keyobject *result;
         579                 :            :     static char *kwargs[] = {"obj", NULL};
         580                 :            :
         581         [ -  + ]:         77 :     if (!PyArg_ParseTupleAndKeywords(args, kwds, "O:K", kwargs, &object))
         582                 :          0 :         return NULL;
         583                 :            :
         584                 :         77 :     result = PyObject_GC_New(keyobject, Py_TYPE(ko));
         585         [ -  + ]:         77 :     if (result == NULL) {
         586                 :          0 :         return NULL;
         587                 :            :     }
         588                 :         77 :     result->cmp = Py_NewRef(ko->cmp);
         589                 :         77 :     result->object = Py_NewRef(object);
         590                 :         77 :     PyObject_GC_Track(result);
         591                 :         77 :     return (PyObject *)result;
         592                 :            : }
         593                 :            :
         594                 :            : static PyObject *
         595                 :         75 : keyobject_richcompare(PyObject *ko, PyObject *other, int op)
         596                 :            : {
         597                 :            :     PyObject *res;
         598                 :            :     PyObject *x;
         599                 :            :     PyObject *y;
         600                 :            :     PyObject *compare;
         601                 :            :     PyObject *answer;
         602                 :            :     PyObject* stack[2];
         603                 :            :
         604         [ -  + ]:         75 :     if (!Py_IS_TYPE(other, Py_TYPE(ko))) {
         605                 :          0 :         PyErr_Format(PyExc_TypeError, "other argument must be K instance");
         606                 :          0 :         return NULL;
         607                 :            :     }
         608                 :         75 :     compare = ((keyobject *) ko)->cmp;
         609                 :            :     assert(compare != NULL);
         610                 :         75 :     x = ((keyobject *) ko)->object;
         611                 :         75 :     y = ((keyobject *) other)->object;
         612   [ +  -  -  + ]:         75 :     if (!x || !y){
         613                 :          0 :         PyErr_Format(PyExc_AttributeError, "object");
         614                 :          0 :         return NULL;
         615                 :            :     }
         616                 :            :
         617                 :            :     /* Call the user's comparison function and translate the 3-way
         618                 :            :      * result into true or false (or error).
         619                 :            :      */
         620                 :         75 :     stack[0] = x;
         621                 :         75 :     stack[1] = y;
         622                 :         75 :     res = _PyObject_FastCall(compare, stack, 2);
         623         [ -  + ]:         75 :     if (res == NULL) {
         624                 :          0 :         return NULL;
         625                 :            :     }
         626                 :            :
         627                 :         75 :     answer = PyObject_RichCompare(res, _PyLong_GetZero(), op);
         628                 :         75 :     Py_DECREF(res);
         629                 :         75 :     return answer;
         630                 :            : }
         631                 :            :
         632                 :            : /*[clinic input]
         633                 :            : _functools.cmp_to_key
         634                 :            :
         635                 :            :     mycmp: object
         636                 :            :         Function that compares two objects.
         637                 :            :
         638                 :            : Convert a cmp= function into a key= function.
         639                 :            : [clinic start generated code]*/
         640                 :            :
         641                 :            : static PyObject *
         642                 :          2 : _functools_cmp_to_key_impl(PyObject *module, PyObject *mycmp)
         643                 :            : /*[clinic end generated code: output=71eaad0f4fc81f33 input=d1b76f231c0dfeb3]*/
         644                 :            : {
         645                 :            :     keyobject *object;
         646                 :            :     _functools_state *state;
         647                 :            :
         648                 :          2 :     state = get_functools_state(module);
         649                 :          2 :     object = PyObject_GC_New(keyobject, state->keyobject_type);
         650         [ -  + ]:          2 :     if (!object)
         651                 :          0 :         return NULL;
         652                 :          2 :     object->cmp = Py_NewRef(mycmp);
         653                 :          2 :     object->object = NULL;
         654                 :          2 :     PyObject_GC_Track(object);
         655                 :          2 :     return (PyObject *)object;
         656                 :            : }
         657                 :            :
         658                 :            : /* reduce (used to be a builtin) ********************************************/
         659                 :            :
         660                 :            : // Not converted to argument clinic, because of `args` in-place modification.
         661                 :            : // AC will affect performance.
         662                 :            : static PyObject *
         663                 :          0 : functools_reduce(PyObject *self, PyObject *args)
         664                 :            : {
         665                 :          0 :     PyObject *seq, *func, *result = NULL, *it;
         666                 :            :
         667         [ #  # ]:          0 :     if (!PyArg_UnpackTuple(args, "reduce", 2, 3, &func, &seq, &result))
         668                 :          0 :         return NULL;
         669         [ #  # ]:          0 :     if (result != NULL)
         670                 :          0 :         Py_INCREF(result);
         671                 :            :
         672                 :          0 :     it = PyObject_GetIter(seq);
         673         [ #  # ]:          0 :     if (it == NULL) {
         674         [ #  # ]:          0 :         if (PyErr_ExceptionMatches(PyExc_TypeError))
         675                 :          0 :             PyErr_SetString(PyExc_TypeError,
         676                 :            :                             "reduce() arg 2 must support iteration");
         677                 :          0 :         Py_XDECREF(result);
         678                 :          0 :         return NULL;
         679                 :            :     }
         680                 :            :
         681         [ #  # ]:          0 :     if ((args = PyTuple_New(2)) == NULL)
         682                 :          0 :         goto Fail;
         683                 :            :
         684                 :          0 :     for (;;) {
         685                 :            :         PyObject *op2;
         686                 :            :
         687         [ #  # ]:          0 :         if (Py_REFCNT(args) > 1) {
         688                 :          0 :             Py_DECREF(args);
         689         [ #  # ]:          0 :             if ((args = PyTuple_New(2)) == NULL)
         690                 :          0 :                 goto Fail;
         691                 :            :         }
         692                 :            :
         693                 :          0 :         op2 = PyIter_Next(it);
         694         [ #  # ]:          0 :         if (op2 == NULL) {
         695         [ #  # ]:          0 :             if (PyErr_Occurred())
         696                 :          0 :                 goto Fail;
         697                 :          0 :             break;
         698                 :            :         }
         699                 :            :
         700         [ #  # ]:          0 :         if (result == NULL)
         701                 :          0 :             result = op2;
         702                 :            :         else {
         703                 :            :             /* Update the args tuple in-place */
         704                 :            :             assert(Py_REFCNT(args) == 1);
         705                 :          0 :             Py_XSETREF(_PyTuple_ITEMS(args)[0], result);
         706                 :          0 :             Py_XSETREF(_PyTuple_ITEMS(args)[1], op2);
         707         [ #  # ]:          0 :             if ((result = PyObject_Call(func, args, NULL)) == NULL) {
         708                 :          0 :                 goto Fail;
         709                 :            :             }
         710                 :            :             // bpo-42536: The GC may have untracked this args tuple. Since we're
         711                 :            :             // recycling it, make sure it's tracked again:
         712         [ #  # ]:          0 :             if (!_PyObject_GC_IS_TRACKED(args)) {
         713                 :          0 :                 _PyObject_GC_TRACK(args);
         714                 :            :             }
         715                 :            :         }
         716                 :            :     }
         717                 :            :
         718                 :          0 :     Py_DECREF(args);
         719                 :            :
         720         [ #  # ]:          0 :     if (result == NULL)
         721                 :          0 :         PyErr_SetString(PyExc_TypeError,
         722                 :            :                    "reduce() of empty iterable with no initial value");
         723                 :            :
         724                 :          0 :     Py_DECREF(it);
         725                 :          0 :     return result;
         726                 :            :
         727                 :          0 : Fail:
         728                 :          0 :     Py_XDECREF(args);
         729                 :          0 :     Py_XDECREF(result);
         730                 :          0 :     Py_DECREF(it);
         731                 :          0 :     return NULL;
         732                 :            : }
         733                 :            :
         734                 :            : PyDoc_STRVAR(functools_reduce_doc,
         735                 :            : "reduce(function, iterable[, initial]) -> value\n\
         736                 :            : \n\
         737                 :            : Apply a function of two arguments cumulatively to the items of a sequence\n\
         738                 :            : or iterable, from left to right, so as to reduce the iterable to a single\n\
         739                 :            : value.  For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates\n\
         740                 :            : ((((1+2)+3)+4)+5).  If initial is present, it is placed before the items\n\
         741                 :            : of the iterable in the calculation, and serves as a default when the\n\
         742                 :            : iterable is empty.");
         743                 :            :
         744                 :            : /* lru_cache object **********************************************************/
         745                 :            :
         746                 :            : /* There are four principal algorithmic differences from the pure python version:
         747                 :            :
         748                 :            :    1). The C version relies on the GIL instead of having its own reentrant lock.
         749                 :            :
         750                 :            :    2). The prev/next link fields use borrowed references.
         751                 :            :
         752                 :            :    3). For a full cache, the pure python version rotates the location of the
         753                 :            :        root entry so that it never has to move individual links and it can
         754                 :            :        limit updates to just the key and result fields.  However, in the C
         755                 :            :        version, links are temporarily removed while the cache dict updates are
         756                 :            :        occurring. Afterwards, they are appended or prepended back into the
         757                 :            :        doubly-linked lists.
         758                 :            :
         759                 :            :    4)  In the Python version, the _HashSeq class is used to prevent __hash__
         760                 :            :        from being called more than once.  In the C version, the "known hash"
         761                 :            :        variants of dictionary calls as used to the same effect.
         762                 :            :
         763                 :            : */
         764                 :            :
         765                 :            : struct lru_list_elem;
         766                 :            : struct lru_cache_object;
         767                 :            :
         768                 :            : typedef struct lru_list_elem {
         769                 :            :     PyObject_HEAD
         770                 :            :     struct lru_list_elem *prev, *next;  /* borrowed links */
         771                 :            :     Py_hash_t hash;
         772                 :            :     PyObject *key, *result;
         773                 :            : } lru_list_elem;
         774                 :            :
         775                 :            : static void
         776                 :         61 : lru_list_elem_dealloc(lru_list_elem *link)
         777                 :            : {
         778                 :         61 :     PyTypeObject *tp = Py_TYPE(link);
         779                 :         61 :     Py_XDECREF(link->key);
         780                 :         61 :     Py_XDECREF(link->result);
         781                 :         61 :     tp->tp_free(link);
         782                 :         61 :     Py_DECREF(tp);
         783                 :         61 : }
         784                 :            :
         785                 :            : static PyType_Slot lru_list_elem_type_slots[] = {
         786                 :            :     {Py_tp_dealloc, lru_list_elem_dealloc},
         787                 :            :     {0, 0}
         788                 :            : };
         789                 :            :
         790                 :            : static PyType_Spec lru_list_elem_type_spec = {
         791                 :            :     .name = "functools._lru_list_elem",
         792                 :            :     .basicsize = sizeof(lru_list_elem),
         793                 :            :     .flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_DISALLOW_INSTANTIATION |
         794                 :            :              Py_TPFLAGS_IMMUTABLETYPE,
         795                 :            :     .slots = lru_list_elem_type_slots
         796                 :            : };
         797                 :            :
         798                 :            :
         799                 :            : typedef PyObject *(*lru_cache_ternaryfunc)(struct lru_cache_object *, PyObject *, PyObject *);
         800                 :            :
         801                 :            : typedef struct lru_cache_object {
         802                 :            :     lru_list_elem root;  /* includes PyObject_HEAD */
         803                 :            :     lru_cache_ternaryfunc wrapper;
         804                 :            :     int typed;
         805                 :            :     PyObject *cache;
         806                 :            :     Py_ssize_t hits;
         807                 :            :     PyObject *func;
         808                 :            :     Py_ssize_t maxsize;
         809                 :            :     Py_ssize_t misses;
         810                 :            :     /* the kwd_mark is used delimit args and keywords in the cache keys */
         811                 :            :     PyObject *kwd_mark;
         812                 :            :     PyTypeObject *lru_list_elem_type;
         813                 :            :     PyObject *cache_info_type;
         814                 :            :     PyObject *dict;
         815                 :            :     PyObject *weakreflist;
         816                 :            : } lru_cache_object;
         817                 :            :
         818                 :            : static PyObject *
         819                 :         81 : lru_cache_make_key(PyObject *kwd_mark, PyObject *args,
         820                 :            :                    PyObject *kwds, int typed)
         821                 :            : {
         822                 :            :     PyObject *key, *keyword, *value;
         823                 :            :     Py_ssize_t key_size, pos, key_pos, kwds_size;
         824                 :            :
         825         [ +  - ]:         81 :     kwds_size = kwds ? PyDict_GET_SIZE(kwds) : 0;
         826                 :            :
         827                 :            :     /* short path, key will match args anyway, which is a tuple */
         828   [ +  -  +  - ]:         81 :     if (!typed && !kwds_size) {
         829         [ -  + ]:         81 :         if (PyTuple_GET_SIZE(args) == 1) {
         830                 :          0 :             key = PyTuple_GET_ITEM(args, 0);
         831   [ #  #  #  # ]:          0 :             if (PyUnicode_CheckExact(key) || PyLong_CheckExact(key)) {
         832                 :            :                 /* For common scalar keys, save space by
         833                 :            :                    dropping the enclosing args tuple  */
         834                 :          0 :                 return Py_NewRef(key);
         835                 :            :             }
         836                 :            :         }
         837                 :         81 :         return Py_NewRef(args);
         838                 :            :     }
         839                 :            :
         840                 :          0 :     key_size = PyTuple_GET_SIZE(args);
         841         [ #  # ]:          0 :     if (kwds_size)
         842                 :          0 :         key_size += kwds_size * 2 + 1;
         843         [ #  # ]:          0 :     if (typed)
         844                 :          0 :         key_size += PyTuple_GET_SIZE(args) + kwds_size;
         845                 :            :
         846                 :          0 :     key = PyTuple_New(key_size);
         847         [ #  # ]:          0 :     if (key == NULL)
         848                 :          0 :         return NULL;
         849                 :            :
         850                 :          0 :     key_pos = 0;
         851         [ #  # ]:          0 :     for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
         852                 :          0 :         PyObject *item = PyTuple_GET_ITEM(args, pos);
         853                 :          0 :         PyTuple_SET_ITEM(key, key_pos++, Py_NewRef(item));
         854                 :            :     }
         855         [ #  # ]:          0 :     if (kwds_size) {
         856                 :          0 :         PyTuple_SET_ITEM(key, key_pos++, Py_NewRef(kwd_mark));
         857         [ #  # ]:          0 :         for (pos = 0; PyDict_Next(kwds, &pos, &keyword, &value);) {
         858                 :          0 :             PyTuple_SET_ITEM(key, key_pos++, Py_NewRef(keyword));
         859                 :          0 :             PyTuple_SET_ITEM(key, key_pos++, Py_NewRef(value));
         860                 :            :         }
         861                 :            :         assert(key_pos == PyTuple_GET_SIZE(args) + kwds_size * 2 + 1);
         862                 :            :     }
         863         [ #  # ]:          0 :     if (typed) {
         864         [ #  # ]:          0 :         for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
         865                 :          0 :             PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(args, pos));
         866                 :          0 :             PyTuple_SET_ITEM(key, key_pos++, Py_NewRef(item));
         867                 :            :         }
         868         [ #  # ]:          0 :         if (kwds_size) {
         869         [ #  # ]:          0 :             for (pos = 0; PyDict_Next(kwds, &pos, &keyword, &value);) {
         870                 :          0 :                 PyObject *item = (PyObject *)Py_TYPE(value);
         871                 :          0 :                 PyTuple_SET_ITEM(key, key_pos++, Py_NewRef(item));
         872                 :            :             }
         873                 :            :         }
         874                 :            :     }
         875                 :            :     assert(key_pos == key_size);
         876                 :          0 :     return key;
         877                 :            : }
         878                 :            :
         879                 :            : static PyObject *
         880                 :          0 : uncached_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds)
         881                 :            : {
         882                 :            :     PyObject *result;
         883                 :            :
         884                 :          0 :     self->misses++;
         885                 :          0 :     result = PyObject_Call(self->func, args, kwds);
         886         [ #  # ]:          0 :     if (!result)
         887                 :          0 :         return NULL;
         888                 :          0 :     return result;
         889                 :            : }
         890                 :            :
         891                 :            : static PyObject *
         892                 :          0 : infinite_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds)
         893                 :            : {
         894                 :            :     PyObject *result;
         895                 :            :     Py_hash_t hash;
         896                 :          0 :     PyObject *key = lru_cache_make_key(self->kwd_mark, args, kwds, self->typed);
         897         [ #  # ]:          0 :     if (!key)
         898                 :          0 :         return NULL;
         899                 :          0 :     hash = PyObject_Hash(key);
         900         [ #  # ]:          0 :     if (hash == -1) {
         901                 :          0 :         Py_DECREF(key);
         902                 :          0 :         return NULL;
         903                 :            :     }
         904                 :          0 :     result = _PyDict_GetItem_KnownHash(self->cache, key, hash);
         905         [ #  # ]:          0 :     if (result) {
         906                 :          0 :         Py_INCREF(result);
         907                 :          0 :         self->hits++;
         908                 :          0 :         Py_DECREF(key);
         909                 :          0 :         return result;
         910                 :            :     }
         911         [ #  # ]:          0 :     if (PyErr_Occurred()) {
         912                 :          0 :         Py_DECREF(key);
         913                 :          0 :         return NULL;
         914                 :            :     }
         915                 :          0 :     self->misses++;
         916                 :          0 :     result = PyObject_Call(self->func, args, kwds);
         917         [ #  # ]:          0 :     if (!result) {
         918                 :          0 :         Py_DECREF(key);
         919                 :          0 :         return NULL;
         920                 :            :     }
         921         [ #  # ]:          0 :     if (_PyDict_SetItem_KnownHash(self->cache, key, result, hash) < 0) {
         922                 :          0 :         Py_DECREF(result);
         923                 :          0 :         Py_DECREF(key);
         924                 :          0 :         return NULL;
         925                 :            :     }
         926                 :          0 :     Py_DECREF(key);
         927                 :          0 :     return result;
         928                 :            : }
         929                 :            :
         930                 :            : static void
         931                 :         20 : lru_cache_extract_link(lru_list_elem *link)
         932                 :            : {
         933                 :         20 :     lru_list_elem *link_prev = link->prev;
         934                 :         20 :     lru_list_elem *link_next = link->next;
         935                 :         20 :     link_prev->next = link->next;
         936                 :         20 :     link_next->prev = link->prev;
         937                 :         20 : }
         938                 :            :
         939                 :            : static void
         940                 :         81 : lru_cache_append_link(lru_cache_object *self, lru_list_elem *link)
         941                 :            : {
         942                 :         81 :     lru_list_elem *root = &self->root;
         943                 :         81 :     lru_list_elem *last = root->prev;
         944                 :         81 :     last->next = root->prev = link;
         945                 :         81 :     link->prev = last;
         946                 :         81 :     link->next = root;
         947                 :         81 : }
         948                 :            :
         949                 :            : static void
         950                 :          0 : lru_cache_prepend_link(lru_cache_object *self, lru_list_elem *link)
         951                 :            : {
         952                 :          0 :     lru_list_elem *root = &self->root;
         953                 :          0 :     lru_list_elem *first = root->next;
         954                 :          0 :     first->prev = root->next = link;
         955                 :          0 :     link->prev = root;
         956                 :          0 :     link->next = first;
         957                 :          0 : }
         958                 :            :
         959                 :            : /* General note on reentrancy:
         960                 :            :
         961                 :            :    There are four dictionary calls in the bounded_lru_cache_wrapper():
         962                 :            :    1) The initial check for a cache match.  2) The post user-function
         963                 :            :    check for a cache match.  3) The deletion of the oldest entry.
         964                 :            :    4) The addition of the newest entry.
         965                 :            :
         966                 :            :    In all four calls, we have a known hash which lets use avoid a call
         967                 :            :    to __hash__().  That leaves only __eq__ as a possible source of a
         968                 :            :    reentrant call.
         969                 :            :
         970                 :            :    The __eq__ method call is always made for a cache hit (dict access #1).
         971                 :            :    Accordingly, we have make sure not modify the cache state prior to
         972                 :            :    this call.
         973                 :            :
         974                 :            :    The __eq__ method call is never made for the deletion (dict access #3)
         975                 :            :    because it is an identity match.
         976                 :            :
         977                 :            :    For the other two accesses (#2 and #4), calls to __eq__ only occur
         978                 :            :    when some other entry happens to have an exactly matching hash (all
         979                 :            :    64-bits).  Though rare, this can happen, so we have to make sure to
         980                 :            :    either call it at the top of its code path before any cache
         981                 :            :    state modifications (dict access #2) or be prepared to restore
         982                 :            :    invariants at the end of the code path (dict access #4).
         983                 :            :
         984                 :            :    Another possible source of reentrancy is a decref which can trigger
         985                 :            :    arbitrary code execution.  To make the code easier to reason about,
         986                 :            :    the decrefs are deferred to the end of the each possible code path
         987                 :            :    so that we know the cache is a consistent state.
         988                 :            :  */
         989                 :            :
         990                 :            : static PyObject *
         991                 :         81 : bounded_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds)
         992                 :            : {
         993                 :            :     lru_list_elem *link;
         994                 :            :     PyObject *key, *result, *testresult;
         995                 :            :     Py_hash_t hash;
         996                 :            :
         997                 :         81 :     key = lru_cache_make_key(self->kwd_mark, args, kwds, self->typed);
         998         [ -  + ]:         81 :     if (!key)
         999                 :          0 :         return NULL;
        1000                 :         81 :     hash = PyObject_Hash(key);
        1001         [ -  + ]:         81 :     if (hash == -1) {
        1002                 :          0 :         Py_DECREF(key);
        1003                 :          0 :         return NULL;
        1004                 :            :     }
        1005                 :         81 :     link  = (lru_list_elem *)_PyDict_GetItem_KnownHash(self->cache, key, hash);
        1006         [ +  + ]:         81 :     if (link != NULL) {
        1007                 :         20 :         lru_cache_extract_link(link);
        1008                 :         20 :         lru_cache_append_link(self, link);
        1009                 :         20 :         result = link->result;
        1010                 :         20 :         self->hits++;
        1011                 :         20 :         Py_INCREF(result);
        1012                 :         20 :         Py_DECREF(key);
        1013                 :         20 :         return result;
        1014                 :            :     }
        1015         [ -  + ]:         61 :     if (PyErr_Occurred()) {
        1016                 :          0 :         Py_DECREF(key);
        1017                 :          0 :         return NULL;
        1018                 :            :     }
        1019                 :         61 :     self->misses++;
        1020                 :         61 :     result = PyObject_Call(self->func, args, kwds);
        1021         [ -  + ]:         61 :     if (!result) {
        1022                 :          0 :         Py_DECREF(key);
        1023                 :          0 :         return NULL;
        1024                 :            :     }
        1025                 :         61 :     testresult = _PyDict_GetItem_KnownHash(self->cache, key, hash);
        1026         [ -  + ]:         61 :     if (testresult != NULL) {
        1027                 :            :         /* Getting here means that this same key was added to the cache
        1028                 :            :            during the PyObject_Call().  Since the link update is already
        1029                 :            :            done, we need only return the computed result. */
        1030                 :          0 :         Py_DECREF(key);
        1031                 :          0 :         return result;
        1032                 :            :     }
        1033         [ -  + ]:         61 :     if (PyErr_Occurred()) {
        1034                 :            :         /* This is an unusual case since this same lookup
        1035                 :            :            did not previously trigger an error during lookup.
        1036                 :            :            Treat it the same as an error in user function
        1037                 :            :            and return with the error set. */
        1038                 :          0 :         Py_DECREF(key);
        1039                 :          0 :         Py_DECREF(result);
        1040                 :          0 :         return NULL;
        1041                 :            :     }
        1042                 :            :     /* This is the normal case.  The new key wasn't found before
        1043                 :            :        user function call and it is still not there.  So we
        1044                 :            :        proceed normally and update the cache with the new result. */
        1045                 :            :
        1046                 :            :     assert(self->maxsize > 0);
        1047         [ -  + ]:         61 :     if (PyDict_GET_SIZE(self->cache) < self->maxsize ||
        1048         [ #  # ]:          0 :         self->root.next == &self->root)
        1049                 :            :     {
        1050                 :            :         /* Cache is not full, so put the result in a new link */
        1051                 :         61 :         link = (lru_list_elem *)PyObject_New(lru_list_elem,
        1052                 :            :                                              self->lru_list_elem_type);
        1053         [ -  + ]:         61 :         if (link == NULL) {
        1054                 :          0 :             Py_DECREF(key);
        1055                 :          0 :             Py_DECREF(result);
        1056                 :          0 :             return NULL;
        1057                 :            :         }
        1058                 :            :
        1059                 :         61 :         link->hash = hash;
        1060                 :         61 :         link->key = key;
        1061                 :         61 :         link->result = result;
        1062                 :            :         /* What is really needed here is a SetItem variant with a "no clobber"
        1063                 :            :            option.  If the __eq__ call triggers a reentrant call that adds
        1064                 :            :            this same key, then this setitem call will update the cache dict
        1065                 :            :            with this new link, leaving the old link as an orphan (i.e. not
        1066                 :            :            having a cache dict entry that refers to it). */
        1067         [ -  + ]:         61 :         if (_PyDict_SetItem_KnownHash(self->cache, key, (PyObject *)link,
        1068                 :            :                                       hash) < 0) {
        1069                 :          0 :             Py_DECREF(link);
        1070                 :          0 :             return NULL;
        1071                 :            :         }
        1072                 :         61 :         lru_cache_append_link(self, link);
        1073                 :         61 :         return Py_NewRef(result);
        1074                 :            :     }
        1075                 :            :     /* Since the cache is full, we need to evict an old key and add
        1076                 :            :        a new key.  Rather than free the old link and allocate a new
        1077                 :            :        one, we reuse the link for the new key and result and move it
        1078                 :            :        to front of the cache to mark it as recently used.
        1079                 :            :
        1080                 :            :        We try to assure all code paths (including errors) leave all
        1081                 :            :        of the links in place.  Either the link is successfully
        1082                 :            :        updated and moved or it is restored to its old position.
        1083                 :            :        However if an unrecoverable error is found, it doesn't
        1084                 :            :        make sense to reinsert the link, so we leave it out
        1085                 :            :        and the cache will no longer register as full.
        1086                 :            :     */
        1087                 :            :     PyObject *oldkey, *oldresult, *popresult;
        1088                 :            :
        1089                 :            :     /* Extract the oldest item. */
        1090                 :            :     assert(self->root.next != &self->root);
        1091                 :          0 :     link = self->root.next;
        1092                 :          0 :     lru_cache_extract_link(link);
        1093                 :            :     /* Remove it from the cache.
        1094                 :            :        The cache dict holds one reference to the link.
        1095                 :            :        We created one other reference when the link was created.
        1096                 :            :        The linked list only has borrowed references. */
        1097                 :          0 :     popresult = _PyDict_Pop_KnownHash(self->cache, link->key,
        1098                 :            :                                       link->hash, Py_None);
        1099         [ #  # ]:          0 :     if (popresult == Py_None) {
        1100                 :            :         /* Getting here means that the user function call or another
        1101                 :            :            thread has already removed the old key from the dictionary.
        1102                 :            :            This link is now an orphan.  Since we don't want to leave the
        1103                 :            :            cache in an inconsistent state, we don't restore the link. */
        1104                 :          0 :         Py_DECREF(popresult);
        1105                 :          0 :         Py_DECREF(link);
        1106                 :          0 :         Py_DECREF(key);
        1107                 :          0 :         return result;
        1108                 :            :     }
        1109         [ #  # ]:          0 :     if (popresult == NULL) {
        1110                 :            :         /* An error arose while trying to remove the oldest key (the one
        1111                 :            :            being evicted) from the cache.  We restore the link to its
        1112                 :            :            original position as the oldest link.  Then we allow the
        1113                 :            :            error propagate upward; treating it the same as an error
        1114                 :            :            arising in the user function. */
        1115                 :          0 :         lru_cache_prepend_link(self, link);
        1116                 :          0 :         Py_DECREF(key);
        1117                 :          0 :         Py_DECREF(result);
        1118                 :          0 :         return NULL;
        1119                 :            :     }
        1120                 :            :     /* Keep a reference to the old key and old result to prevent their
        1121                 :            :        ref counts from going to zero during the update. That will
        1122                 :            :        prevent potentially arbitrary object clean-up code (i.e. __del__)
        1123                 :            :        from running while we're still adjusting the links. */
        1124                 :          0 :     oldkey = link->key;
        1125                 :          0 :     oldresult = link->result;
        1126                 :            :
        1127                 :          0 :     link->hash = hash;
        1128                 :          0 :     link->key = key;
        1129                 :          0 :     link->result = result;
        1130                 :            :     /* Note:  The link is being added to the cache dict without the
        1131                 :            :        prev and next fields set to valid values.   We have to wait
        1132                 :            :        for successful insertion in the cache dict before adding the
        1133                 :            :        link to the linked list.  Otherwise, the potentially reentrant
        1134                 :            :        __eq__ call could cause the then orphan link to be visited. */
        1135         [ #  # ]:          0 :     if (_PyDict_SetItem_KnownHash(self->cache, key, (PyObject *)link,
        1136                 :            :                                   hash) < 0) {
        1137                 :            :         /* Somehow the cache dict update failed.  We no longer can
        1138                 :            :            restore the old link.  Let the error propagate upward and
        1139                 :            :            leave the cache short one link. */
        1140                 :          0 :         Py_DECREF(popresult);
        1141                 :          0 :         Py_DECREF(link);
        1142                 :          0 :         Py_DECREF(oldkey);
        1143                 :          0 :         Py_DECREF(oldresult);
        1144                 :          0 :         return NULL;
        1145                 :            :     }
        1146                 :          0 :     lru_cache_append_link(self, link);
        1147                 :          0 :     Py_INCREF(result); /* for return */
        1148                 :          0 :     Py_DECREF(popresult);
        1149                 :          0 :     Py_DECREF(oldkey);
        1150                 :          0 :     Py_DECREF(oldresult);
        1151                 :          0 :     return result;
        1152                 :            : }
        1153                 :            :
        1154                 :            : static PyObject *
        1155                 :         38 : lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw)
        1156                 :            : {
        1157                 :            :     PyObject *func, *maxsize_O, *cache_info_type, *cachedict;
        1158                 :            :     int typed;
        1159                 :            :     lru_cache_object *obj;
        1160                 :            :     Py_ssize_t maxsize;
        1161                 :            :     PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *);
        1162                 :            :     _functools_state *state;
        1163                 :            :     static char *keywords[] = {"user_function", "maxsize", "typed",
        1164                 :            :                                "cache_info_type", NULL};
        1165                 :            :
        1166         [ -  + ]:         38 :     if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords,
        1167                 :            :                                      &func, &maxsize_O, &typed,
        1168                 :            :                                      &cache_info_type)) {
        1169                 :          0 :         return NULL;
        1170                 :            :     }
        1171                 :            :
        1172         [ -  + ]:         38 :     if (!PyCallable_Check(func)) {
        1173                 :          0 :         PyErr_SetString(PyExc_TypeError,
        1174                 :            :                         "the first argument must be callable");
        1175                 :          0 :         return NULL;
        1176                 :            :     }
        1177                 :            :
        1178                 :         38 :     state = get_functools_state_by_type(type);
        1179         [ -  + ]:         38 :     if (state == NULL) {
        1180                 :          0 :         return NULL;
        1181                 :            :     }
        1182                 :            :
        1183                 :            :     /* select the caching function, and make/inc maxsize_O */
        1184         [ -  + ]:         38 :     if (maxsize_O == Py_None) {
        1185                 :          0 :         wrapper = infinite_lru_cache_wrapper;
        1186                 :            :         /* use this only to initialize lru_cache_object attribute maxsize */
        1187                 :          0 :         maxsize = -1;
        1188         [ +  - ]:         38 :     } else if (PyIndex_Check(maxsize_O)) {
        1189                 :         38 :         maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError);
        1190   [ -  +  -  - ]:         38 :         if (maxsize == -1 && PyErr_Occurred())
        1191                 :          0 :             return NULL;
        1192         [ -  + ]:         38 :         if (maxsize < 0) {
        1193                 :          0 :             maxsize = 0;
        1194                 :            :         }
        1195         [ -  + ]:         38 :         if (maxsize == 0)
        1196                 :          0 :             wrapper = uncached_lru_cache_wrapper;
        1197                 :            :         else
        1198                 :         38 :             wrapper = bounded_lru_cache_wrapper;
        1199                 :            :     } else {
        1200                 :          0 :         PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None");
        1201                 :          0 :         return NULL;
        1202                 :            :     }
        1203                 :            :
        1204         [ -  + ]:         38 :     if (!(cachedict = PyDict_New()))
        1205                 :          0 :         return NULL;
        1206                 :            :
        1207                 :         38 :     obj = (lru_cache_object *)type->tp_alloc(type, 0);
        1208         [ -  + ]:         38 :     if (obj == NULL) {
        1209                 :          0 :         Py_DECREF(cachedict);
        1210                 :          0 :         return NULL;
        1211                 :            :     }
        1212                 :            :
        1213                 :         38 :     obj->root.prev = &obj->root;
        1214                 :         38 :     obj->root.next = &obj->root;
        1215                 :         38 :     obj->wrapper = wrapper;
        1216                 :         38 :     obj->typed = typed;
        1217                 :         38 :     obj->cache = cachedict;
        1218                 :         38 :     obj->func = Py_NewRef(func);
        1219                 :         38 :     obj->misses = obj->hits = 0;
        1220                 :         38 :     obj->maxsize = maxsize;
        1221                 :         38 :     obj->kwd_mark = Py_NewRef(state->kwd_mark);
        1222                 :         38 :     obj->lru_list_elem_type = (PyTypeObject*)Py_NewRef(state->lru_list_elem_type);
        1223                 :         38 :     obj->cache_info_type = Py_NewRef(cache_info_type);
        1224                 :         38 :     obj->dict = NULL;
        1225                 :         38 :     obj->weakreflist = NULL;
        1226                 :         38 :     return (PyObject *)obj;
        1227                 :            : }
        1228                 :            :
        1229                 :            : static lru_list_elem *
        1230                 :         39 : lru_cache_unlink_list(lru_cache_object *self)
        1231                 :            : {
        1232                 :         39 :     lru_list_elem *root = &self->root;
        1233                 :         39 :     lru_list_elem *link = root->next;
        1234         [ +  + ]:         39 :     if (link == root)
        1235                 :         25 :         return NULL;
        1236                 :         14 :     root->prev->next = NULL;
        1237                 :         14 :     root->next = root->prev = root;
        1238                 :         14 :     return link;
        1239                 :            : }
        1240                 :            :
        1241                 :            : static void
        1242                 :         39 : lru_cache_clear_list(lru_list_elem *link)
        1243                 :            : {
        1244         [ +  + ]:        100 :     while (link != NULL) {
        1245                 :         61 :         lru_list_elem *next = link->next;
        1246                 :         61 :         Py_SETREF(link, next);
        1247                 :            :     }
        1248                 :         39 : }
        1249                 :            :
        1250                 :            : static int
        1251                 :         38 : lru_cache_tp_clear(lru_cache_object *self)
        1252                 :            : {
        1253                 :         38 :     lru_list_elem *list = lru_cache_unlink_list(self);
        1254         [ +  - ]:         38 :     Py_CLEAR(self->cache);
        1255         [ +  - ]:         38 :     Py_CLEAR(self->func);
        1256         [ +  - ]:         38 :     Py_CLEAR(self->kwd_mark);
        1257         [ +  - ]:         38 :     Py_CLEAR(self->lru_list_elem_type);
        1258         [ +  - ]:         38 :     Py_CLEAR(self->cache_info_type);
        1259         [ +  - ]:         38 :     Py_CLEAR(self->dict);
        1260                 :         38 :     lru_cache_clear_list(list);
        1261                 :         38 :     return 0;
        1262                 :            : }
        1263                 :            :
        1264                 :            : static void
        1265                 :         38 : lru_cache_dealloc(lru_cache_object *obj)
        1266                 :            : {
        1267                 :         38 :     PyTypeObject *tp = Py_TYPE(obj);
        1268                 :            :     /* bpo-31095: UnTrack is needed before calling any callbacks */
        1269                 :         38 :     PyObject_GC_UnTrack(obj);
        1270         [ -  + ]:         38 :     if (obj->weakreflist != NULL) {
        1271                 :          0 :         PyObject_ClearWeakRefs((PyObject*)obj);
        1272                 :            :     }
        1273                 :            :
        1274                 :         38 :     (void)lru_cache_tp_clear(obj);
        1275                 :         38 :     tp->tp_free(obj);
        1276                 :         38 :     Py_DECREF(tp);
        1277                 :         38 : }
        1278                 :            :
        1279                 :            : static PyObject *
        1280                 :         81 : lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds)
        1281                 :            : {
        1282                 :         81 :     return self->wrapper(self, args, kwds);
        1283                 :            : }
        1284                 :            :
        1285                 :            : static PyObject *
        1286                 :          0 : lru_cache_descr_get(PyObject *self, PyObject *obj, PyObject *type)
        1287                 :            : {
        1288   [ #  #  #  # ]:          0 :     if (obj == Py_None || obj == NULL) {
        1289                 :          0 :         return Py_NewRef(self);
        1290                 :            :     }
        1291                 :          0 :     return PyMethod_New(self, obj);
        1292                 :            : }
        1293                 :            :
        1294                 :            : /*[clinic input]
        1295                 :            : _functools._lru_cache_wrapper.cache_info
        1296                 :            :
        1297                 :            : Report cache statistics
        1298                 :            : [clinic start generated code]*/
        1299                 :            :
        1300                 :            : static PyObject *
        1301                 :          0 : _functools__lru_cache_wrapper_cache_info_impl(PyObject *self)
        1302                 :            : /*[clinic end generated code: output=cc796a0b06dbd717 input=f05e5b6ebfe38645]*/
        1303                 :            : {
        1304                 :          0 :     lru_cache_object *_self = (lru_cache_object *) self;
        1305         [ #  # ]:          0 :     if (_self->maxsize == -1) {
        1306                 :          0 :         return PyObject_CallFunction(_self->cache_info_type, "nnOn",
        1307                 :            :                                      _self->hits, _self->misses, Py_None,
        1308                 :            :                                      PyDict_GET_SIZE(_self->cache));
        1309                 :            :     }
        1310                 :          0 :     return PyObject_CallFunction(_self->cache_info_type, "nnnn",
        1311                 :            :                                  _self->hits, _self->misses, _self->maxsize,
        1312                 :            :                                  PyDict_GET_SIZE(_self->cache));
        1313                 :            : }
        1314                 :            :
        1315                 :            : /*[clinic input]
        1316                 :            : _functools._lru_cache_wrapper.cache_clear
        1317                 :            :
        1318                 :            : Clear the cache and cache statistics
        1319                 :            : [clinic start generated code]*/
        1320                 :            :
        1321                 :            : static PyObject *
        1322                 :          1 : _functools__lru_cache_wrapper_cache_clear_impl(PyObject *self)
        1323                 :            : /*[clinic end generated code: output=58423b35efc3e381 input=6ca59dba09b12584]*/
        1324                 :            : {
        1325                 :          1 :     lru_cache_object *_self = (lru_cache_object *) self;
        1326                 :          1 :     lru_list_elem *list = lru_cache_unlink_list(_self);
        1327                 :          1 :     _self->hits = _self->misses = 0;
        1328                 :          1 :     PyDict_Clear(_self->cache);
        1329                 :          1 :     lru_cache_clear_list(list);
        1330                 :          1 :     Py_RETURN_NONE;
        1331                 :            : }
        1332                 :            :
        1333                 :            : static PyObject *
        1334                 :          0 : lru_cache_reduce(PyObject *self, PyObject *unused)
        1335                 :            : {
        1336                 :          0 :     return PyObject_GetAttrString(self, "__qualname__");
        1337                 :            : }
        1338                 :            :
        1339                 :            : static PyObject *
        1340                 :          0 : lru_cache_copy(PyObject *self, PyObject *unused)
        1341                 :            : {
        1342                 :          0 :     return Py_NewRef(self);
        1343                 :            : }
        1344                 :            :
        1345                 :            : static PyObject *
        1346                 :          0 : lru_cache_deepcopy(PyObject *self, PyObject *unused)
        1347                 :            : {
        1348                 :          0 :     return Py_NewRef(self);
        1349                 :            : }
        1350                 :            :
        1351                 :            : static int
        1352                 :        518 : lru_cache_tp_traverse(lru_cache_object *self, visitproc visit, void *arg)
        1353                 :            : {
        1354   [ +  -  -  + ]:        518 :     Py_VISIT(Py_TYPE(self));
        1355                 :        518 :     lru_list_elem *link = self->root.next;
        1356         [ +  + ]:       1078 :     while (link != &self->root) {
        1357                 :        560 :         lru_list_elem *next = link->next;
        1358   [ +  -  -  + ]:        560 :         Py_VISIT(link->key);
        1359   [ +  -  -  + ]:        560 :         Py_VISIT(link->result);
        1360   [ +  -  -  + ]:        560 :         Py_VISIT(Py_TYPE(link));
        1361                 :        560 :         link = next;
        1362                 :            :     }
        1363   [ +  -  -  + ]:        518 :     Py_VISIT(self->cache);
        1364   [ +  -  -  + ]:        518 :     Py_VISIT(self->func);
        1365   [ +  -  -  + ]:        518 :     Py_VISIT(self->kwd_mark);
        1366   [ +  -  -  + ]:        518 :     Py_VISIT(self->lru_list_elem_type);
        1367   [ +  -  -  + ]:        518 :     Py_VISIT(self->cache_info_type);
        1368   [ +  -  -  + ]:        518 :     Py_VISIT(self->dict);
        1369                 :        518 :     return 0;
        1370                 :            : }
        1371                 :            :
        1372                 :            :
        1373                 :            : PyDoc_STRVAR(lru_cache_doc,
        1374                 :            : "Create a cached callable that wraps another function.\n\
        1375                 :            : \n\
        1376                 :            : user_function:      the function being cached\n\
        1377                 :            : \n\
        1378                 :            : maxsize:  0         for no caching\n\
        1379                 :            :           None      for unlimited cache size\n\
        1380                 :            :           n         for a bounded cache\n\
        1381                 :            : \n\
        1382                 :            : typed:    False     cache f(3) and f(3.0) as identical calls\n\
        1383                 :            :           True      cache f(3) and f(3.0) as distinct calls\n\
        1384                 :            : \n\
        1385                 :            : cache_info_type:    namedtuple class with the fields:\n\
        1386                 :            :                         hits misses currsize maxsize\n"
        1387                 :            : );
        1388                 :            :
        1389                 :            : static PyMethodDef lru_cache_methods[] = {
        1390                 :            :     _FUNCTOOLS__LRU_CACHE_WRAPPER_CACHE_INFO_METHODDEF
        1391                 :            :     _FUNCTOOLS__LRU_CACHE_WRAPPER_CACHE_CLEAR_METHODDEF
        1392                 :            :     {"__reduce__", (PyCFunction)lru_cache_reduce, METH_NOARGS},
        1393                 :            :     {"__copy__", (PyCFunction)lru_cache_copy, METH_VARARGS},
        1394                 :            :     {"__deepcopy__", (PyCFunction)lru_cache_deepcopy, METH_VARARGS},
        1395                 :            :     {NULL}
        1396                 :            : };
        1397                 :            :
        1398                 :            : static PyGetSetDef lru_cache_getsetlist[] = {
        1399                 :            :     {"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict},
        1400                 :            :     {NULL}
        1401                 :            : };
        1402                 :            :
        1403                 :            : static PyMemberDef lru_cache_memberlist[] = {
        1404                 :            :     {"__dictoffset__", T_PYSSIZET,
        1405                 :            :      offsetof(lru_cache_object, dict), READONLY},
        1406                 :            :     {"__weaklistoffset__", T_PYSSIZET,
        1407                 :            :      offsetof(lru_cache_object, weakreflist), READONLY},
        1408                 :            :     {NULL}  /* Sentinel */
        1409                 :            : };
        1410                 :            :
        1411                 :            : static PyType_Slot lru_cache_type_slots[] = {
        1412                 :            :     {Py_tp_dealloc, lru_cache_dealloc},
        1413                 :            :     {Py_tp_call, lru_cache_call},
        1414                 :            :     {Py_tp_doc, (void *)lru_cache_doc},
        1415                 :            :     {Py_tp_traverse, lru_cache_tp_traverse},
        1416                 :            :     {Py_tp_clear, lru_cache_tp_clear},
        1417                 :            :     {Py_tp_methods, lru_cache_methods},
        1418                 :            :     {Py_tp_members, lru_cache_memberlist},
        1419                 :            :     {Py_tp_getset, lru_cache_getsetlist},
        1420                 :            :     {Py_tp_descr_get, lru_cache_descr_get},
        1421                 :            :     {Py_tp_new, lru_cache_new},
        1422                 :            :     {0, 0}
        1423                 :            : };
        1424                 :            :
        1425                 :            : static PyType_Spec lru_cache_type_spec = {
        1426                 :            :     .name = "functools._lru_cache_wrapper",
        1427                 :            :     .basicsize = sizeof(lru_cache_object),
        1428                 :            :     .flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
        1429                 :            :              Py_TPFLAGS_METHOD_DESCRIPTOR | Py_TPFLAGS_IMMUTABLETYPE,
        1430                 :            :     .slots = lru_cache_type_slots
        1431                 :            : };
        1432                 :            :
        1433                 :            :
        1434                 :            : /* module level code ********************************************************/
        1435                 :            :
        1436                 :            : PyDoc_STRVAR(_functools_doc,
        1437                 :            : "Tools that operate on functions.");
        1438                 :            :
        1439                 :            : static PyMethodDef _functools_methods[] = {
        1440                 :            :     {"reduce",          functools_reduce,     METH_VARARGS, functools_reduce_doc},
        1441                 :            :     _FUNCTOOLS_CMP_TO_KEY_METHODDEF
        1442                 :            :     {NULL,              NULL}           /* sentinel */
        1443                 :            : };
        1444                 :            :
        1445                 :            : static int
        1446                 :          6 : _functools_exec(PyObject *module)
        1447                 :            : {
        1448                 :          6 :     _functools_state *state = get_functools_state(module);
        1449                 :          6 :     state->kwd_mark = _PyObject_CallNoArgs((PyObject *)&PyBaseObject_Type);
        1450         [ -  + ]:          6 :     if (state->kwd_mark == NULL) {
        1451                 :          0 :         return -1;
        1452                 :            :     }
        1453                 :            :
        1454                 :          6 :     state->partial_type = (PyTypeObject *)PyType_FromModuleAndSpec(module,
        1455                 :            :         &partial_type_spec, NULL);
        1456         [ -  + ]:          6 :     if (state->partial_type == NULL) {
        1457                 :          0 :         return -1;
        1458                 :            :     }
        1459         [ -  + ]:          6 :     if (PyModule_AddType(module, state->partial_type) < 0) {
        1460                 :          0 :         return -1;
        1461                 :            :     }
        1462                 :            :
        1463                 :          6 :     PyObject *lru_cache_type = PyType_FromModuleAndSpec(module,
        1464                 :            :         &lru_cache_type_spec, NULL);
        1465         [ -  + ]:          6 :     if (lru_cache_type == NULL) {
        1466                 :          0 :         return -1;
        1467                 :            :     }
        1468         [ -  + ]:          6 :     if (PyModule_AddType(module, (PyTypeObject *)lru_cache_type) < 0) {
        1469                 :          0 :         Py_DECREF(lru_cache_type);
        1470                 :          0 :         return -1;
        1471                 :            :     }
        1472                 :          6 :     Py_DECREF(lru_cache_type);
        1473                 :            :
        1474                 :          6 :     state->keyobject_type = (PyTypeObject *)PyType_FromModuleAndSpec(module,
        1475                 :            :         &keyobject_type_spec, NULL);
        1476         [ -  + ]:          6 :     if (state->keyobject_type == NULL) {
        1477                 :          0 :         return -1;
        1478                 :            :     }
        1479                 :            :     // keyobject_type is used only internally.
        1480                 :            :     // So we don't expose it in module namespace.
        1481                 :            :
        1482                 :          6 :     state->lru_list_elem_type = (PyTypeObject *)PyType_FromModuleAndSpec(
        1483                 :            :         module, &lru_list_elem_type_spec, NULL);
        1484         [ -  + ]:          6 :     if (state->lru_list_elem_type == NULL) {
        1485                 :          0 :         return -1;
        1486                 :            :     }
        1487                 :            :     // lru_list_elem is used only in _lru_cache_wrapper.
        1488                 :            :     // So we don't expose it in module namespace.
        1489                 :            :
        1490                 :          6 :     return 0;
        1491                 :            : }
        1492                 :            :
        1493                 :            : static int
        1494                 :         84 : _functools_traverse(PyObject *module, visitproc visit, void *arg)
        1495                 :            : {
        1496                 :         84 :     _functools_state *state = get_functools_state(module);
        1497   [ +  -  -  + ]:         84 :     Py_VISIT(state->kwd_mark);
        1498   [ +  -  -  + ]:         84 :     Py_VISIT(state->partial_type);
        1499   [ +  -  -  + ]:         84 :     Py_VISIT(state->keyobject_type);
        1500   [ +  -  -  + ]:         84 :     Py_VISIT(state->lru_list_elem_type);
        1501                 :         84 :     return 0;
        1502                 :            : }
        1503                 :            :
        1504                 :            : static int
        1505                 :         12 : _functools_clear(PyObject *module)
        1506                 :            : {
        1507                 :         12 :     _functools_state *state = get_functools_state(module);
        1508         [ +  + ]:         12 :     Py_CLEAR(state->kwd_mark);
        1509         [ +  + ]:         12 :     Py_CLEAR(state->partial_type);
        1510         [ +  + ]:         12 :     Py_CLEAR(state->keyobject_type);
        1511         [ +  + ]:         12 :     Py_CLEAR(state->lru_list_elem_type);
        1512                 :         12 :     return 0;
        1513                 :            : }
        1514                 :            :
        1515                 :            : static void
        1516                 :          6 : _functools_free(void *module)
        1517                 :            : {
        1518                 :          6 :     _functools_clear((PyObject *)module);
        1519                 :          6 : }
        1520                 :            :
        1521                 :            : static struct PyModuleDef_Slot _functools_slots[] = {
        1522                 :            :     {Py_mod_exec, _functools_exec},
        1523                 :            :     {0, NULL}
        1524                 :            : };
        1525                 :            :
        1526                 :            : static struct PyModuleDef _functools_module = {
        1527                 :            :     PyModuleDef_HEAD_INIT,
        1528                 :            :     .m_name = "_functools",
        1529                 :            :     .m_doc = _functools_doc,
        1530                 :            :     .m_size = sizeof(_functools_state),
        1531                 :            :     .m_methods = _functools_methods,
        1532                 :            :     .m_slots = _functools_slots,
        1533                 :            :     .m_traverse = _functools_traverse,
        1534                 :            :     .m_clear = _functools_clear,
        1535                 :            :     .m_free = _functools_free,
        1536                 :            : };
        1537                 :            :
        1538                 :            : PyMODINIT_FUNC
        1539                 :          6 : PyInit__functools(void)
        1540                 :            : {
        1541                 :          6 :     return PyModuleDef_Init(&_functools_module);
        1542                 :            : }

Generated by: LCOV version 1.14