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