Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 1 | |
| 2 | #include "Python.h" |
Eric Snow | 2ebc5ce | 2017-09-07 23:51:28 -0600 | [diff] [blame] | 3 | #include "internal/mem.h" |
| 4 | #include "internal/pystate.h" |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 5 | #include "structmember.h" |
| 6 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 7 | /* _functools module written and maintained |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 8 | by Hye-Shik Chang <perky@FreeBSD.org> |
| 9 | with adaptations by Raymond Hettinger <python@rcn.com> |
Thomas Wouters | 4d70c3d | 2006-06-08 14:42:34 +0000 | [diff] [blame] | 10 | Copyright (c) 2004, 2005, 2006 Python Software Foundation. |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 11 | All rights reserved. |
| 12 | */ |
| 13 | |
| 14 | /* partial object **********************************************************/ |
| 15 | |
| 16 | typedef struct { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 17 | PyObject_HEAD |
| 18 | PyObject *fn; |
| 19 | PyObject *args; |
| 20 | PyObject *kw; |
| 21 | PyObject *dict; |
| 22 | PyObject *weakreflist; /* List of weak references */ |
Victor Stinner | 0f7b0b3 | 2017-03-14 21:37:20 +0100 | [diff] [blame] | 23 | int use_fastcall; |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 24 | } partialobject; |
| 25 | |
| 26 | static PyTypeObject partial_type; |
| 27 | |
| 28 | static PyObject * |
| 29 | partial_new(PyTypeObject *type, PyObject *args, PyObject *kw) |
| 30 | { |
Alexander Belopolsky | e49af34 | 2015-03-01 15:08:17 -0500 | [diff] [blame] | 31 | PyObject *func, *pargs, *nargs, *pkw; |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 32 | partialobject *pto; |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 33 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 34 | if (PyTuple_GET_SIZE(args) < 1) { |
| 35 | PyErr_SetString(PyExc_TypeError, |
| 36 | "type 'partial' takes at least one argument"); |
| 37 | return NULL; |
| 38 | } |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 39 | |
Serhiy Storchaka | 3874128 | 2016-02-02 18:45:17 +0200 | [diff] [blame] | 40 | pargs = pkw = NULL; |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 41 | func = PyTuple_GET_ITEM(args, 0); |
Alexander Belopolsky | e49af34 | 2015-03-01 15:08:17 -0500 | [diff] [blame] | 42 | if (Py_TYPE(func) == &partial_type && type == &partial_type) { |
| 43 | partialobject *part = (partialobject *)func; |
| 44 | if (part->dict == NULL) { |
| 45 | pargs = part->args; |
| 46 | pkw = part->kw; |
| 47 | func = part->fn; |
Serhiy Storchaka | 3874128 | 2016-02-02 18:45:17 +0200 | [diff] [blame] | 48 | assert(PyTuple_Check(pargs)); |
| 49 | assert(PyDict_Check(pkw)); |
Alexander Belopolsky | e49af34 | 2015-03-01 15:08:17 -0500 | [diff] [blame] | 50 | } |
| 51 | } |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 52 | if (!PyCallable_Check(func)) { |
| 53 | PyErr_SetString(PyExc_TypeError, |
| 54 | "the first argument must be callable"); |
| 55 | return NULL; |
| 56 | } |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 57 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 58 | /* create partialobject structure */ |
| 59 | pto = (partialobject *)type->tp_alloc(type, 0); |
| 60 | if (pto == NULL) |
| 61 | return NULL; |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 62 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 63 | pto->fn = func; |
| 64 | Py_INCREF(func); |
Alexander Belopolsky | e49af34 | 2015-03-01 15:08:17 -0500 | [diff] [blame] | 65 | |
| 66 | nargs = PyTuple_GetSlice(args, 1, PY_SSIZE_T_MAX); |
| 67 | if (nargs == NULL) { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 68 | Py_DECREF(pto); |
| 69 | return NULL; |
| 70 | } |
Serhiy Storchaka | 3c749fc | 2017-03-25 12:10:16 +0200 | [diff] [blame] | 71 | if (pargs == NULL) { |
Alexander Belopolsky | e49af34 | 2015-03-01 15:08:17 -0500 | [diff] [blame] | 72 | pto->args = nargs; |
Alexander Belopolsky | e49af34 | 2015-03-01 15:08:17 -0500 | [diff] [blame] | 73 | } |
| 74 | else { |
| 75 | pto->args = PySequence_Concat(pargs, nargs); |
Serhiy Storchaka | 3c749fc | 2017-03-25 12:10:16 +0200 | [diff] [blame] | 76 | Py_DECREF(nargs); |
Alexander Belopolsky | e49af34 | 2015-03-01 15:08:17 -0500 | [diff] [blame] | 77 | if (pto->args == NULL) { |
Alexander Belopolsky | e49af34 | 2015-03-01 15:08:17 -0500 | [diff] [blame] | 78 | Py_DECREF(pto); |
| 79 | return NULL; |
| 80 | } |
Serhiy Storchaka | 3874128 | 2016-02-02 18:45:17 +0200 | [diff] [blame] | 81 | assert(PyTuple_Check(pto->args)); |
Alexander Belopolsky | e49af34 | 2015-03-01 15:08:17 -0500 | [diff] [blame] | 82 | } |
Alexander Belopolsky | e49af34 | 2015-03-01 15:08:17 -0500 | [diff] [blame] | 83 | |
Serhiy Storchaka | 5ab81d7 | 2016-12-16 16:18:57 +0200 | [diff] [blame] | 84 | if (pkw == NULL || PyDict_GET_SIZE(pkw) == 0) { |
Serhiy Storchaka | 3874128 | 2016-02-02 18:45:17 +0200 | [diff] [blame] | 85 | if (kw == NULL) { |
| 86 | pto->kw = PyDict_New(); |
Alexander Belopolsky | e49af34 | 2015-03-01 15:08:17 -0500 | [diff] [blame] | 87 | } |
Serhiy Storchaka | 9639e4a | 2017-02-20 14:04:30 +0200 | [diff] [blame] | 88 | else if (Py_REFCNT(kw) == 1) { |
Serhiy Storchaka | 3874128 | 2016-02-02 18:45:17 +0200 | [diff] [blame] | 89 | Py_INCREF(kw); |
| 90 | pto->kw = kw; |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 91 | } |
Serhiy Storchaka | 9639e4a | 2017-02-20 14:04:30 +0200 | [diff] [blame] | 92 | else { |
| 93 | pto->kw = PyDict_Copy(kw); |
| 94 | } |
Alexander Belopolsky | e49af34 | 2015-03-01 15:08:17 -0500 | [diff] [blame] | 95 | } |
| 96 | else { |
Serhiy Storchaka | 3874128 | 2016-02-02 18:45:17 +0200 | [diff] [blame] | 97 | pto->kw = PyDict_Copy(pkw); |
| 98 | if (kw != NULL && pto->kw != NULL) { |
| 99 | if (PyDict_Merge(pto->kw, kw, 1) != 0) { |
Benjamin Peterson | dae2ef1 | 2015-05-09 00:29:08 -0400 | [diff] [blame] | 100 | Py_DECREF(pto); |
| 101 | return NULL; |
| 102 | } |
| 103 | } |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 104 | } |
Serhiy Storchaka | 3874128 | 2016-02-02 18:45:17 +0200 | [diff] [blame] | 105 | if (pto->kw == NULL) { |
| 106 | Py_DECREF(pto); |
| 107 | return NULL; |
| 108 | } |
Raymond Hettinger | c8b6d1b | 2005-03-08 06:14:50 +0000 | [diff] [blame] | 109 | |
Victor Stinner | 0f7b0b3 | 2017-03-14 21:37:20 +0100 | [diff] [blame] | 110 | pto->use_fastcall = _PyObject_HasFastCall(func); |
| 111 | |
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 | |
| 129 | static PyObject * |
Victor Stinner | 0f7b0b3 | 2017-03-14 21:37:20 +0100 | [diff] [blame] | 130 | partial_fastcall(partialobject *pto, PyObject **args, Py_ssize_t nargs, |
| 131 | PyObject *kwargs) |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 132 | { |
Victor Stinner | 0f7b0b3 | 2017-03-14 21:37:20 +0100 | [diff] [blame] | 133 | PyObject *small_stack[_PY_FASTCALL_SMALL_STACK]; |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 134 | PyObject *ret; |
Victor Stinner | 0f7b0b3 | 2017-03-14 21:37:20 +0100 | [diff] [blame] | 135 | PyObject **stack, **stack_buf = NULL; |
| 136 | Py_ssize_t nargs2, pto_nargs; |
| 137 | |
| 138 | pto_nargs = PyTuple_GET_SIZE(pto->args); |
| 139 | nargs2 = pto_nargs + nargs; |
| 140 | |
| 141 | if (pto_nargs == 0) { |
| 142 | stack = args; |
| 143 | } |
| 144 | else if (nargs == 0) { |
| 145 | stack = &PyTuple_GET_ITEM(pto->args, 0); |
| 146 | } |
| 147 | else { |
| 148 | if (nargs2 <= (Py_ssize_t)Py_ARRAY_LENGTH(small_stack)) { |
| 149 | stack = small_stack; |
| 150 | } |
| 151 | else { |
| 152 | stack_buf = PyMem_Malloc(nargs2 * sizeof(PyObject *)); |
| 153 | if (stack_buf == NULL) { |
| 154 | PyErr_NoMemory(); |
| 155 | return NULL; |
| 156 | } |
| 157 | stack = stack_buf; |
| 158 | } |
| 159 | |
| 160 | /* use borrowed references */ |
| 161 | memcpy(stack, |
| 162 | &PyTuple_GET_ITEM(pto->args, 0), |
| 163 | pto_nargs * sizeof(PyObject*)); |
| 164 | memcpy(&stack[pto_nargs], |
| 165 | args, |
| 166 | nargs * sizeof(PyObject*)); |
| 167 | } |
| 168 | |
| 169 | ret = _PyObject_FastCallDict(pto->fn, stack, nargs2, kwargs); |
| 170 | PyMem_Free(stack_buf); |
| 171 | return ret; |
| 172 | } |
| 173 | |
| 174 | static PyObject * |
| 175 | partial_call_impl(partialobject *pto, PyObject *args, PyObject *kwargs) |
| 176 | { |
| 177 | PyObject *ret, *args2; |
| 178 | |
| 179 | /* Note: tupleconcat() is optimized for empty tuples */ |
| 180 | args2 = PySequence_Concat(pto->args, args); |
| 181 | if (args2 == NULL) { |
| 182 | return NULL; |
| 183 | } |
| 184 | assert(PyTuple_Check(args2)); |
| 185 | |
| 186 | ret = PyObject_Call(pto->fn, args2, kwargs); |
| 187 | Py_DECREF(args2); |
| 188 | return ret; |
| 189 | } |
| 190 | |
| 191 | static PyObject * |
| 192 | partial_call(partialobject *pto, PyObject *args, PyObject *kwargs) |
| 193 | { |
| 194 | PyObject *kwargs2, *res; |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 195 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 196 | assert (PyCallable_Check(pto->fn)); |
| 197 | assert (PyTuple_Check(pto->args)); |
Serhiy Storchaka | 3874128 | 2016-02-02 18:45:17 +0200 | [diff] [blame] | 198 | assert (PyDict_Check(pto->kw)); |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 199 | |
Serhiy Storchaka | 5ab81d7 | 2016-12-16 16:18:57 +0200 | [diff] [blame] | 200 | if (PyDict_GET_SIZE(pto->kw) == 0) { |
Victor Stinner | 0f7b0b3 | 2017-03-14 21:37:20 +0100 | [diff] [blame] | 201 | /* kwargs can be NULL */ |
| 202 | kwargs2 = kwargs; |
| 203 | Py_XINCREF(kwargs2); |
Victor Stinner | f4d28d4 | 2016-08-23 16:22:35 +0200 | [diff] [blame] | 204 | } |
| 205 | else { |
Victor Stinner | 561ca80 | 2017-02-23 18:26:43 +0100 | [diff] [blame] | 206 | /* bpo-27840, bpo-29318: dictionary of keyword parameters must be |
| 207 | copied, because a function using "**kwargs" can modify the |
| 208 | dictionary. */ |
Victor Stinner | 0f7b0b3 | 2017-03-14 21:37:20 +0100 | [diff] [blame] | 209 | kwargs2 = PyDict_Copy(pto->kw); |
| 210 | if (kwargs2 == NULL) { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 211 | return NULL; |
| 212 | } |
Victor Stinner | f4d28d4 | 2016-08-23 16:22:35 +0200 | [diff] [blame] | 213 | |
Victor Stinner | 0f7b0b3 | 2017-03-14 21:37:20 +0100 | [diff] [blame] | 214 | if (kwargs != NULL) { |
| 215 | if (PyDict_Merge(kwargs2, kwargs, 1) != 0) { |
| 216 | Py_DECREF(kwargs2); |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 217 | return NULL; |
| 218 | } |
| 219 | } |
| 220 | } |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 221 | |
Victor Stinner | 0f7b0b3 | 2017-03-14 21:37:20 +0100 | [diff] [blame] | 222 | |
| 223 | if (pto->use_fastcall) { |
| 224 | res = partial_fastcall(pto, |
| 225 | &PyTuple_GET_ITEM(args, 0), |
| 226 | PyTuple_GET_SIZE(args), |
| 227 | kwargs2); |
Victor Stinner | f4d28d4 | 2016-08-23 16:22:35 +0200 | [diff] [blame] | 228 | } |
| 229 | else { |
Victor Stinner | 0f7b0b3 | 2017-03-14 21:37:20 +0100 | [diff] [blame] | 230 | res = partial_call_impl(pto, args, kwargs2); |
Victor Stinner | f4d28d4 | 2016-08-23 16:22:35 +0200 | [diff] [blame] | 231 | } |
Victor Stinner | 0f7b0b3 | 2017-03-14 21:37:20 +0100 | [diff] [blame] | 232 | Py_XDECREF(kwargs2); |
| 233 | return res; |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 234 | } |
| 235 | |
| 236 | static int |
| 237 | partial_traverse(partialobject *pto, visitproc visit, void *arg) |
| 238 | { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 239 | Py_VISIT(pto->fn); |
| 240 | Py_VISIT(pto->args); |
| 241 | Py_VISIT(pto->kw); |
| 242 | Py_VISIT(pto->dict); |
| 243 | return 0; |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 244 | } |
| 245 | |
| 246 | PyDoc_STRVAR(partial_doc, |
| 247 | "partial(func, *args, **keywords) - new function with partial application\n\ |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 248 | of the given arguments and keywords.\n"); |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 249 | |
| 250 | #define OFF(x) offsetof(partialobject, x) |
| 251 | static PyMemberDef partial_memberlist[] = { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 252 | {"func", T_OBJECT, OFF(fn), READONLY, |
| 253 | "function object to use in future partial calls"}, |
| 254 | {"args", T_OBJECT, OFF(args), READONLY, |
| 255 | "tuple of arguments to future partial calls"}, |
| 256 | {"keywords", T_OBJECT, OFF(kw), READONLY, |
| 257 | "dictionary of keyword arguments to future partial calls"}, |
| 258 | {NULL} /* Sentinel */ |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 259 | }; |
| 260 | |
Georg Brandl | c2fb6c7 | 2006-02-21 17:49:57 +0000 | [diff] [blame] | 261 | static PyGetSetDef partial_getsetlist[] = { |
Benjamin Peterson | 23d7f12 | 2012-02-19 20:02:57 -0500 | [diff] [blame] | 262 | {"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict}, |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 263 | {NULL} /* Sentinel */ |
Raymond Hettinger | c8b6d1b | 2005-03-08 06:14:50 +0000 | [diff] [blame] | 264 | }; |
| 265 | |
Alexander Belopolsky | 41e422a | 2010-12-01 20:05:49 +0000 | [diff] [blame] | 266 | static PyObject * |
| 267 | partial_repr(partialobject *pto) |
| 268 | { |
Serhiy Storchaka | 179f960 | 2016-06-12 11:44:06 +0300 | [diff] [blame] | 269 | PyObject *result = NULL; |
Alexander Belopolsky | 41e422a | 2010-12-01 20:05:49 +0000 | [diff] [blame] | 270 | PyObject *arglist; |
Alexander Belopolsky | 41e422a | 2010-12-01 20:05:49 +0000 | [diff] [blame] | 271 | Py_ssize_t i, n; |
Serhiy Storchaka | 3874128 | 2016-02-02 18:45:17 +0200 | [diff] [blame] | 272 | PyObject *key, *value; |
Serhiy Storchaka | 179f960 | 2016-06-12 11:44:06 +0300 | [diff] [blame] | 273 | int status; |
| 274 | |
| 275 | status = Py_ReprEnter((PyObject *)pto); |
| 276 | if (status != 0) { |
| 277 | if (status < 0) |
| 278 | return NULL; |
Nick Coghlan | 457fc9a | 2016-09-10 20:00:02 +1000 | [diff] [blame] | 279 | return PyUnicode_FromString("..."); |
Serhiy Storchaka | 179f960 | 2016-06-12 11:44:06 +0300 | [diff] [blame] | 280 | } |
Alexander Belopolsky | 41e422a | 2010-12-01 20:05:49 +0000 | [diff] [blame] | 281 | |
| 282 | arglist = PyUnicode_FromString(""); |
Serhiy Storchaka | 179f960 | 2016-06-12 11:44:06 +0300 | [diff] [blame] | 283 | if (arglist == NULL) |
| 284 | goto done; |
Alexander Belopolsky | 41e422a | 2010-12-01 20:05:49 +0000 | [diff] [blame] | 285 | /* Pack positional arguments */ |
| 286 | assert (PyTuple_Check(pto->args)); |
| 287 | n = PyTuple_GET_SIZE(pto->args); |
| 288 | for (i = 0; i < n; i++) { |
Serhiy Storchaka | 179f960 | 2016-06-12 11:44:06 +0300 | [diff] [blame] | 289 | Py_SETREF(arglist, PyUnicode_FromFormat("%U, %R", arglist, |
| 290 | PyTuple_GET_ITEM(pto->args, i))); |
| 291 | if (arglist == NULL) |
| 292 | goto done; |
Alexander Belopolsky | 41e422a | 2010-12-01 20:05:49 +0000 | [diff] [blame] | 293 | } |
| 294 | /* Pack keyword arguments */ |
Serhiy Storchaka | 3874128 | 2016-02-02 18:45:17 +0200 | [diff] [blame] | 295 | assert (PyDict_Check(pto->kw)); |
| 296 | for (i = 0; PyDict_Next(pto->kw, &i, &key, &value);) { |
Michael Seifert | 6c3d527 | 2017-03-15 06:26:33 +0100 | [diff] [blame] | 297 | /* Prevent key.__str__ from deleting the value. */ |
| 298 | Py_INCREF(value); |
| 299 | Py_SETREF(arglist, PyUnicode_FromFormat("%U, %S=%R", arglist, |
Serhiy Storchaka | 179f960 | 2016-06-12 11:44:06 +0300 | [diff] [blame] | 300 | key, value)); |
Michael Seifert | 6c3d527 | 2017-03-15 06:26:33 +0100 | [diff] [blame] | 301 | Py_DECREF(value); |
Serhiy Storchaka | 179f960 | 2016-06-12 11:44:06 +0300 | [diff] [blame] | 302 | if (arglist == NULL) |
| 303 | goto done; |
Alexander Belopolsky | 41e422a | 2010-12-01 20:05:49 +0000 | [diff] [blame] | 304 | } |
| 305 | result = PyUnicode_FromFormat("%s(%R%U)", Py_TYPE(pto)->tp_name, |
| 306 | pto->fn, arglist); |
| 307 | Py_DECREF(arglist); |
Serhiy Storchaka | 179f960 | 2016-06-12 11:44:06 +0300 | [diff] [blame] | 308 | |
| 309 | done: |
| 310 | Py_ReprLeave((PyObject *)pto); |
Alexander Belopolsky | 41e422a | 2010-12-01 20:05:49 +0000 | [diff] [blame] | 311 | return result; |
| 312 | } |
| 313 | |
Jack Diederich | e0cbd69 | 2009-04-01 04:27:09 +0000 | [diff] [blame] | 314 | /* Pickle strategy: |
| 315 | __reduce__ by itself doesn't support getting kwargs in the unpickle |
| 316 | operation so we define a __setstate__ that replaces all the information |
| 317 | 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] | 318 | it as a hook to do strange things. |
Jack Diederich | e0cbd69 | 2009-04-01 04:27:09 +0000 | [diff] [blame] | 319 | */ |
| 320 | |
Antoine Pitrou | 69f7114 | 2009-05-24 21:25:49 +0000 | [diff] [blame] | 321 | static PyObject * |
Jack Diederich | e0cbd69 | 2009-04-01 04:27:09 +0000 | [diff] [blame] | 322 | partial_reduce(partialobject *pto, PyObject *unused) |
| 323 | { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 324 | return Py_BuildValue("O(O)(OOOO)", Py_TYPE(pto), pto->fn, pto->fn, |
| 325 | pto->args, pto->kw, |
| 326 | pto->dict ? pto->dict : Py_None); |
Jack Diederich | e0cbd69 | 2009-04-01 04:27:09 +0000 | [diff] [blame] | 327 | } |
| 328 | |
Antoine Pitrou | 69f7114 | 2009-05-24 21:25:49 +0000 | [diff] [blame] | 329 | static PyObject * |
Serhiy Storchaka | 19c4e0d | 2013-02-04 12:47:24 +0200 | [diff] [blame] | 330 | partial_setstate(partialobject *pto, PyObject *state) |
Jack Diederich | e0cbd69 | 2009-04-01 04:27:09 +0000 | [diff] [blame] | 331 | { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 332 | PyObject *fn, *fnargs, *kw, *dict; |
Serhiy Storchaka | 3874128 | 2016-02-02 18:45:17 +0200 | [diff] [blame] | 333 | |
| 334 | if (!PyTuple_Check(state) || |
| 335 | !PyArg_ParseTuple(state, "OOOO", &fn, &fnargs, &kw, &dict) || |
| 336 | !PyCallable_Check(fn) || |
| 337 | !PyTuple_Check(fnargs) || |
| 338 | (kw != Py_None && !PyDict_Check(kw))) |
| 339 | { |
| 340 | PyErr_SetString(PyExc_TypeError, "invalid partial state"); |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 341 | return NULL; |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 342 | } |
Serhiy Storchaka | 3874128 | 2016-02-02 18:45:17 +0200 | [diff] [blame] | 343 | |
| 344 | if(!PyTuple_CheckExact(fnargs)) |
| 345 | fnargs = PySequence_Tuple(fnargs); |
| 346 | else |
| 347 | Py_INCREF(fnargs); |
| 348 | if (fnargs == NULL) |
| 349 | return NULL; |
| 350 | |
| 351 | if (kw == Py_None) |
| 352 | kw = PyDict_New(); |
| 353 | else if(!PyDict_CheckExact(kw)) |
| 354 | kw = PyDict_Copy(kw); |
| 355 | else |
| 356 | Py_INCREF(kw); |
| 357 | if (kw == NULL) { |
| 358 | Py_DECREF(fnargs); |
| 359 | return NULL; |
| 360 | } |
| 361 | |
Serhiy Storchaka | 3874128 | 2016-02-02 18:45:17 +0200 | [diff] [blame] | 362 | if (dict == Py_None) |
| 363 | dict = NULL; |
| 364 | else |
| 365 | Py_INCREF(dict); |
| 366 | |
Victor Stinner | 0f7b0b3 | 2017-03-14 21:37:20 +0100 | [diff] [blame] | 367 | Py_INCREF(fn); |
| 368 | pto->use_fastcall = _PyObject_HasFastCall(fn); |
Serhiy Storchaka | 864b63c | 2016-04-11 09:53:37 +0300 | [diff] [blame] | 369 | Py_SETREF(pto->fn, fn); |
| 370 | Py_SETREF(pto->args, fnargs); |
| 371 | Py_SETREF(pto->kw, kw); |
Serhiy Storchaka | 4884271 | 2016-04-06 09:45:48 +0300 | [diff] [blame] | 372 | Py_XSETREF(pto->dict, dict); |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 373 | Py_RETURN_NONE; |
Jack Diederich | e0cbd69 | 2009-04-01 04:27:09 +0000 | [diff] [blame] | 374 | } |
| 375 | |
| 376 | static PyMethodDef partial_methods[] = { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 377 | {"__reduce__", (PyCFunction)partial_reduce, METH_NOARGS}, |
Serhiy Storchaka | 19c4e0d | 2013-02-04 12:47:24 +0200 | [diff] [blame] | 378 | {"__setstate__", (PyCFunction)partial_setstate, METH_O}, |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 379 | {NULL, NULL} /* sentinel */ |
Jack Diederich | e0cbd69 | 2009-04-01 04:27:09 +0000 | [diff] [blame] | 380 | }; |
| 381 | |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 382 | static PyTypeObject partial_type = { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 383 | PyVarObject_HEAD_INIT(NULL, 0) |
| 384 | "functools.partial", /* tp_name */ |
| 385 | sizeof(partialobject), /* tp_basicsize */ |
| 386 | 0, /* tp_itemsize */ |
| 387 | /* methods */ |
| 388 | (destructor)partial_dealloc, /* tp_dealloc */ |
| 389 | 0, /* tp_print */ |
| 390 | 0, /* tp_getattr */ |
| 391 | 0, /* tp_setattr */ |
| 392 | 0, /* tp_reserved */ |
Alexander Belopolsky | 41e422a | 2010-12-01 20:05:49 +0000 | [diff] [blame] | 393 | (reprfunc)partial_repr, /* tp_repr */ |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 394 | 0, /* tp_as_number */ |
| 395 | 0, /* tp_as_sequence */ |
| 396 | 0, /* tp_as_mapping */ |
| 397 | 0, /* tp_hash */ |
| 398 | (ternaryfunc)partial_call, /* tp_call */ |
| 399 | 0, /* tp_str */ |
| 400 | PyObject_GenericGetAttr, /* tp_getattro */ |
| 401 | PyObject_GenericSetAttr, /* tp_setattro */ |
| 402 | 0, /* tp_as_buffer */ |
| 403 | Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | |
| 404 | Py_TPFLAGS_BASETYPE, /* tp_flags */ |
| 405 | partial_doc, /* tp_doc */ |
| 406 | (traverseproc)partial_traverse, /* tp_traverse */ |
| 407 | 0, /* tp_clear */ |
| 408 | 0, /* tp_richcompare */ |
| 409 | offsetof(partialobject, weakreflist), /* tp_weaklistoffset */ |
| 410 | 0, /* tp_iter */ |
| 411 | 0, /* tp_iternext */ |
| 412 | partial_methods, /* tp_methods */ |
| 413 | partial_memberlist, /* tp_members */ |
| 414 | partial_getsetlist, /* tp_getset */ |
| 415 | 0, /* tp_base */ |
| 416 | 0, /* tp_dict */ |
| 417 | 0, /* tp_descr_get */ |
| 418 | 0, /* tp_descr_set */ |
| 419 | offsetof(partialobject, dict), /* tp_dictoffset */ |
| 420 | 0, /* tp_init */ |
| 421 | 0, /* tp_alloc */ |
| 422 | partial_new, /* tp_new */ |
| 423 | PyObject_GC_Del, /* tp_free */ |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 424 | }; |
| 425 | |
| 426 | |
Raymond Hettinger | 7ab9e22 | 2011-04-05 02:33:54 -0700 | [diff] [blame] | 427 | /* cmp_to_key ***************************************************************/ |
| 428 | |
| 429 | typedef struct { |
Victor Stinner | 446c8d5 | 2011-04-05 12:21:35 +0200 | [diff] [blame] | 430 | PyObject_HEAD |
Raymond Hettinger | 7ab9e22 | 2011-04-05 02:33:54 -0700 | [diff] [blame] | 431 | PyObject *cmp; |
| 432 | PyObject *object; |
| 433 | } keyobject; |
| 434 | |
| 435 | static void |
| 436 | keyobject_dealloc(keyobject *ko) |
| 437 | { |
| 438 | Py_DECREF(ko->cmp); |
| 439 | Py_XDECREF(ko->object); |
| 440 | PyObject_FREE(ko); |
| 441 | } |
| 442 | |
| 443 | static int |
| 444 | keyobject_traverse(keyobject *ko, visitproc visit, void *arg) |
| 445 | { |
| 446 | Py_VISIT(ko->cmp); |
| 447 | if (ko->object) |
| 448 | Py_VISIT(ko->object); |
| 449 | return 0; |
| 450 | } |
| 451 | |
Benjamin Peterson | 3bd9729 | 2011-04-05 17:25:14 -0500 | [diff] [blame] | 452 | static int |
| 453 | keyobject_clear(keyobject *ko) |
| 454 | { |
| 455 | Py_CLEAR(ko->cmp); |
| 456 | if (ko->object) |
| 457 | Py_CLEAR(ko->object); |
| 458 | return 0; |
| 459 | } |
| 460 | |
Raymond Hettinger | 7ab9e22 | 2011-04-05 02:33:54 -0700 | [diff] [blame] | 461 | static PyMemberDef keyobject_members[] = { |
| 462 | {"obj", T_OBJECT, |
| 463 | offsetof(keyobject, object), 0, |
| 464 | PyDoc_STR("Value wrapped by a key function.")}, |
| 465 | {NULL} |
| 466 | }; |
| 467 | |
| 468 | static PyObject * |
Raymond Hettinger | a563286 | 2011-04-09 12:57:00 -0700 | [diff] [blame] | 469 | keyobject_call(keyobject *ko, PyObject *args, PyObject *kwds); |
Raymond Hettinger | 7ab9e22 | 2011-04-05 02:33:54 -0700 | [diff] [blame] | 470 | |
| 471 | static PyObject * |
| 472 | keyobject_richcompare(PyObject *ko, PyObject *other, int op); |
| 473 | |
| 474 | static PyTypeObject keyobject_type = { |
| 475 | PyVarObject_HEAD_INIT(&PyType_Type, 0) |
| 476 | "functools.KeyWrapper", /* tp_name */ |
| 477 | sizeof(keyobject), /* tp_basicsize */ |
| 478 | 0, /* tp_itemsize */ |
| 479 | /* methods */ |
| 480 | (destructor)keyobject_dealloc, /* tp_dealloc */ |
| 481 | 0, /* tp_print */ |
| 482 | 0, /* tp_getattr */ |
| 483 | 0, /* tp_setattr */ |
| 484 | 0, /* tp_reserved */ |
| 485 | 0, /* tp_repr */ |
| 486 | 0, /* tp_as_number */ |
| 487 | 0, /* tp_as_sequence */ |
| 488 | 0, /* tp_as_mapping */ |
| 489 | 0, /* tp_hash */ |
| 490 | (ternaryfunc)keyobject_call, /* tp_call */ |
| 491 | 0, /* tp_str */ |
| 492 | PyObject_GenericGetAttr, /* tp_getattro */ |
| 493 | 0, /* tp_setattro */ |
| 494 | 0, /* tp_as_buffer */ |
| 495 | Py_TPFLAGS_DEFAULT, /* tp_flags */ |
| 496 | 0, /* tp_doc */ |
| 497 | (traverseproc)keyobject_traverse, /* tp_traverse */ |
Benjamin Peterson | 3bd9729 | 2011-04-05 17:25:14 -0500 | [diff] [blame] | 498 | (inquiry)keyobject_clear, /* tp_clear */ |
Raymond Hettinger | 7ab9e22 | 2011-04-05 02:33:54 -0700 | [diff] [blame] | 499 | keyobject_richcompare, /* tp_richcompare */ |
| 500 | 0, /* tp_weaklistoffset */ |
| 501 | 0, /* tp_iter */ |
| 502 | 0, /* tp_iternext */ |
| 503 | 0, /* tp_methods */ |
| 504 | keyobject_members, /* tp_members */ |
| 505 | 0, /* tp_getset */ |
| 506 | }; |
| 507 | |
| 508 | static PyObject * |
| 509 | keyobject_call(keyobject *ko, PyObject *args, PyObject *kwds) |
| 510 | { |
| 511 | PyObject *object; |
| 512 | keyobject *result; |
| 513 | static char *kwargs[] = {"obj", NULL}; |
| 514 | |
| 515 | if (!PyArg_ParseTupleAndKeywords(args, kwds, "O:K", kwargs, &object)) |
| 516 | return NULL; |
| 517 | result = PyObject_New(keyobject, &keyobject_type); |
| 518 | if (!result) |
| 519 | return NULL; |
| 520 | Py_INCREF(ko->cmp); |
| 521 | result->cmp = ko->cmp; |
| 522 | Py_INCREF(object); |
| 523 | result->object = object; |
| 524 | return (PyObject *)result; |
| 525 | } |
| 526 | |
| 527 | static PyObject * |
| 528 | keyobject_richcompare(PyObject *ko, PyObject *other, int op) |
| 529 | { |
| 530 | PyObject *res; |
Raymond Hettinger | 7ab9e22 | 2011-04-05 02:33:54 -0700 | [diff] [blame] | 531 | PyObject *x; |
| 532 | PyObject *y; |
| 533 | PyObject *compare; |
| 534 | PyObject *answer; |
Victor Stinner | f7a4c48 | 2016-08-19 18:52:35 +0200 | [diff] [blame] | 535 | PyObject* stack[2]; |
Raymond Hettinger | 7ab9e22 | 2011-04-05 02:33:54 -0700 | [diff] [blame] | 536 | |
Raymond Hettinger | 7ab9e22 | 2011-04-05 02:33:54 -0700 | [diff] [blame] | 537 | if (Py_TYPE(other) != &keyobject_type){ |
| 538 | PyErr_Format(PyExc_TypeError, "other argument must be K instance"); |
| 539 | return NULL; |
| 540 | } |
| 541 | compare = ((keyobject *) ko)->cmp; |
| 542 | assert(compare != NULL); |
| 543 | x = ((keyobject *) ko)->object; |
| 544 | y = ((keyobject *) other)->object; |
| 545 | if (!x || !y){ |
| 546 | PyErr_Format(PyExc_AttributeError, "object"); |
| 547 | return NULL; |
| 548 | } |
| 549 | |
| 550 | /* Call the user's comparison function and translate the 3-way |
| 551 | * result into true or false (or error). |
| 552 | */ |
Victor Stinner | f7a4c48 | 2016-08-19 18:52:35 +0200 | [diff] [blame] | 553 | stack[0] = x; |
| 554 | stack[1] = y; |
Victor Stinner | 559bb6a | 2016-08-22 22:48:54 +0200 | [diff] [blame] | 555 | res = _PyObject_FastCall(compare, stack, 2); |
Victor Stinner | f7a4c48 | 2016-08-19 18:52:35 +0200 | [diff] [blame] | 556 | if (res == NULL) { |
Raymond Hettinger | 7ab9e22 | 2011-04-05 02:33:54 -0700 | [diff] [blame] | 557 | return NULL; |
Victor Stinner | f7a4c48 | 2016-08-19 18:52:35 +0200 | [diff] [blame] | 558 | } |
| 559 | |
Serhiy Storchaka | ba85d69 | 2017-03-30 09:09:41 +0300 | [diff] [blame] | 560 | answer = PyObject_RichCompare(res, _PyLong_Zero, op); |
Raymond Hettinger | 7ab9e22 | 2011-04-05 02:33:54 -0700 | [diff] [blame] | 561 | Py_DECREF(res); |
| 562 | return answer; |
| 563 | } |
| 564 | |
| 565 | static PyObject * |
Victor Stinner | 446c8d5 | 2011-04-05 12:21:35 +0200 | [diff] [blame] | 566 | functools_cmp_to_key(PyObject *self, PyObject *args, PyObject *kwds) |
| 567 | { |
| 568 | PyObject *cmp; |
Raymond Hettinger | 7ab9e22 | 2011-04-05 02:33:54 -0700 | [diff] [blame] | 569 | static char *kwargs[] = {"mycmp", NULL}; |
Victor Stinner | 446c8d5 | 2011-04-05 12:21:35 +0200 | [diff] [blame] | 570 | keyobject *object; |
Raymond Hettinger | 7ab9e22 | 2011-04-05 02:33:54 -0700 | [diff] [blame] | 571 | |
| 572 | if (!PyArg_ParseTupleAndKeywords(args, kwds, "O:cmp_to_key", kwargs, &cmp)) |
| 573 | return NULL; |
Victor Stinner | 446c8d5 | 2011-04-05 12:21:35 +0200 | [diff] [blame] | 574 | object = PyObject_New(keyobject, &keyobject_type); |
Raymond Hettinger | 7ab9e22 | 2011-04-05 02:33:54 -0700 | [diff] [blame] | 575 | if (!object) |
| 576 | return NULL; |
| 577 | Py_INCREF(cmp); |
| 578 | object->cmp = cmp; |
| 579 | object->object = NULL; |
| 580 | return (PyObject *)object; |
| 581 | } |
| 582 | |
| 583 | PyDoc_STRVAR(functools_cmp_to_key_doc, |
| 584 | "Convert a cmp= function into a key= function."); |
| 585 | |
Guido van Rossum | 0919a1a | 2006-08-26 20:49:04 +0000 | [diff] [blame] | 586 | /* reduce (used to be a builtin) ********************************************/ |
| 587 | |
| 588 | static PyObject * |
| 589 | functools_reduce(PyObject *self, PyObject *args) |
| 590 | { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 591 | PyObject *seq, *func, *result = NULL, *it; |
Guido van Rossum | 0919a1a | 2006-08-26 20:49:04 +0000 | [diff] [blame] | 592 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 593 | if (!PyArg_UnpackTuple(args, "reduce", 2, 3, &func, &seq, &result)) |
| 594 | return NULL; |
| 595 | if (result != NULL) |
| 596 | Py_INCREF(result); |
Guido van Rossum | 0919a1a | 2006-08-26 20:49:04 +0000 | [diff] [blame] | 597 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 598 | it = PyObject_GetIter(seq); |
| 599 | if (it == NULL) { |
Alexander Belopolsky | e29e6bf | 2010-08-16 18:55:46 +0000 | [diff] [blame] | 600 | if (PyErr_ExceptionMatches(PyExc_TypeError)) |
| 601 | PyErr_SetString(PyExc_TypeError, |
| 602 | "reduce() arg 2 must support iteration"); |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 603 | Py_XDECREF(result); |
| 604 | return NULL; |
| 605 | } |
Guido van Rossum | 0919a1a | 2006-08-26 20:49:04 +0000 | [diff] [blame] | 606 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 607 | if ((args = PyTuple_New(2)) == NULL) |
| 608 | goto Fail; |
Guido van Rossum | 0919a1a | 2006-08-26 20:49:04 +0000 | [diff] [blame] | 609 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 610 | for (;;) { |
| 611 | PyObject *op2; |
Guido van Rossum | 0919a1a | 2006-08-26 20:49:04 +0000 | [diff] [blame] | 612 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 613 | if (args->ob_refcnt > 1) { |
| 614 | Py_DECREF(args); |
| 615 | if ((args = PyTuple_New(2)) == NULL) |
| 616 | goto Fail; |
| 617 | } |
Guido van Rossum | 0919a1a | 2006-08-26 20:49:04 +0000 | [diff] [blame] | 618 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 619 | op2 = PyIter_Next(it); |
| 620 | if (op2 == NULL) { |
| 621 | if (PyErr_Occurred()) |
| 622 | goto Fail; |
| 623 | break; |
| 624 | } |
Guido van Rossum | 0919a1a | 2006-08-26 20:49:04 +0000 | [diff] [blame] | 625 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 626 | if (result == NULL) |
| 627 | result = op2; |
| 628 | else { |
| 629 | PyTuple_SetItem(args, 0, result); |
| 630 | PyTuple_SetItem(args, 1, op2); |
| 631 | if ((result = PyEval_CallObject(func, args)) == NULL) |
| 632 | goto Fail; |
| 633 | } |
| 634 | } |
Guido van Rossum | 0919a1a | 2006-08-26 20:49:04 +0000 | [diff] [blame] | 635 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 636 | Py_DECREF(args); |
Guido van Rossum | 0919a1a | 2006-08-26 20:49:04 +0000 | [diff] [blame] | 637 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 638 | if (result == NULL) |
| 639 | PyErr_SetString(PyExc_TypeError, |
| 640 | "reduce() of empty sequence with no initial value"); |
Guido van Rossum | 0919a1a | 2006-08-26 20:49:04 +0000 | [diff] [blame] | 641 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 642 | Py_DECREF(it); |
| 643 | return result; |
Guido van Rossum | 0919a1a | 2006-08-26 20:49:04 +0000 | [diff] [blame] | 644 | |
| 645 | Fail: |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 646 | Py_XDECREF(args); |
| 647 | Py_XDECREF(result); |
| 648 | Py_DECREF(it); |
| 649 | return NULL; |
Guido van Rossum | 0919a1a | 2006-08-26 20:49:04 +0000 | [diff] [blame] | 650 | } |
| 651 | |
| 652 | PyDoc_STRVAR(functools_reduce_doc, |
| 653 | "reduce(function, sequence[, initial]) -> value\n\ |
| 654 | \n\ |
| 655 | Apply a function of two arguments cumulatively to the items of a sequence,\n\ |
| 656 | from left to right, so as to reduce the sequence to a single value.\n\ |
| 657 | For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates\n\ |
| 658 | ((((1+2)+3)+4)+5). If initial is present, it is placed before the items\n\ |
| 659 | of the sequence in the calculation, and serves as a default when the\n\ |
| 660 | sequence is empty."); |
| 661 | |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 662 | /* lru_cache object **********************************************************/ |
| 663 | |
| 664 | /* this object is used delimit args and keywords in the cache keys */ |
| 665 | static PyObject *kwd_mark = NULL; |
| 666 | |
| 667 | struct lru_list_elem; |
| 668 | struct lru_cache_object; |
| 669 | |
| 670 | typedef struct lru_list_elem { |
| 671 | PyObject_HEAD |
| 672 | struct lru_list_elem *prev, *next; /* borrowed links */ |
Serhiy Storchaka | b9d98d5 | 2015-10-02 12:47:11 +0300 | [diff] [blame] | 673 | Py_hash_t hash; |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 674 | PyObject *key, *result; |
| 675 | } lru_list_elem; |
| 676 | |
| 677 | static void |
| 678 | lru_list_elem_dealloc(lru_list_elem *link) |
| 679 | { |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 680 | Py_XDECREF(link->key); |
| 681 | Py_XDECREF(link->result); |
INADA Naoki | 3070b71 | 2017-12-26 02:03:24 +0900 | [diff] [blame] | 682 | PyObject_Del(link); |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 683 | } |
| 684 | |
| 685 | static PyTypeObject lru_list_elem_type = { |
| 686 | PyVarObject_HEAD_INIT(&PyType_Type, 0) |
| 687 | "functools._lru_list_elem", /* tp_name */ |
| 688 | sizeof(lru_list_elem), /* tp_basicsize */ |
| 689 | 0, /* tp_itemsize */ |
| 690 | /* methods */ |
| 691 | (destructor)lru_list_elem_dealloc, /* tp_dealloc */ |
| 692 | 0, /* tp_print */ |
| 693 | 0, /* tp_getattr */ |
| 694 | 0, /* tp_setattr */ |
| 695 | 0, /* tp_reserved */ |
| 696 | 0, /* tp_repr */ |
| 697 | 0, /* tp_as_number */ |
| 698 | 0, /* tp_as_sequence */ |
| 699 | 0, /* tp_as_mapping */ |
| 700 | 0, /* tp_hash */ |
| 701 | 0, /* tp_call */ |
| 702 | 0, /* tp_str */ |
| 703 | 0, /* tp_getattro */ |
| 704 | 0, /* tp_setattro */ |
| 705 | 0, /* tp_as_buffer */ |
INADA Naoki | 3070b71 | 2017-12-26 02:03:24 +0900 | [diff] [blame] | 706 | Py_TPFLAGS_DEFAULT, /* tp_flags */ |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 707 | }; |
| 708 | |
| 709 | |
| 710 | typedef PyObject *(*lru_cache_ternaryfunc)(struct lru_cache_object *, PyObject *, PyObject *); |
| 711 | |
| 712 | typedef struct lru_cache_object { |
| 713 | lru_list_elem root; /* includes PyObject_HEAD */ |
| 714 | Py_ssize_t maxsize; |
| 715 | PyObject *maxsize_O; |
| 716 | PyObject *func; |
| 717 | lru_cache_ternaryfunc wrapper; |
| 718 | PyObject *cache; |
| 719 | PyObject *cache_info_type; |
| 720 | Py_ssize_t misses, hits; |
| 721 | int typed; |
| 722 | PyObject *dict; |
| 723 | int full; |
| 724 | } lru_cache_object; |
| 725 | |
| 726 | static PyTypeObject lru_cache_type; |
| 727 | |
| 728 | static PyObject * |
| 729 | lru_cache_make_key(PyObject *args, PyObject *kwds, int typed) |
| 730 | { |
Raymond Hettinger | dda4468 | 2017-01-08 18:04:30 -0800 | [diff] [blame] | 731 | PyObject *key, *keyword, *value; |
| 732 | Py_ssize_t key_size, pos, key_pos, kwds_size; |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 733 | |
| 734 | /* short path, key will match args anyway, which is a tuple */ |
| 735 | if (!typed && !kwds) { |
| 736 | Py_INCREF(args); |
| 737 | return args; |
| 738 | } |
| 739 | |
Raymond Hettinger | dda4468 | 2017-01-08 18:04:30 -0800 | [diff] [blame] | 740 | kwds_size = kwds ? PyDict_GET_SIZE(kwds) : 0; |
| 741 | assert(kwds_size >= 0); |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 742 | |
| 743 | key_size = PyTuple_GET_SIZE(args); |
Raymond Hettinger | dda4468 | 2017-01-08 18:04:30 -0800 | [diff] [blame] | 744 | if (kwds_size) |
| 745 | key_size += kwds_size * 2 + 1; |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 746 | if (typed) |
Raymond Hettinger | dda4468 | 2017-01-08 18:04:30 -0800 | [diff] [blame] | 747 | key_size += PyTuple_GET_SIZE(args) + kwds_size; |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 748 | |
| 749 | key = PyTuple_New(key_size); |
| 750 | if (key == NULL) |
Raymond Hettinger | dda4468 | 2017-01-08 18:04:30 -0800 | [diff] [blame] | 751 | return NULL; |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 752 | |
| 753 | key_pos = 0; |
| 754 | for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) { |
| 755 | PyObject *item = PyTuple_GET_ITEM(args, pos); |
| 756 | Py_INCREF(item); |
| 757 | PyTuple_SET_ITEM(key, key_pos++, item); |
| 758 | } |
Raymond Hettinger | dda4468 | 2017-01-08 18:04:30 -0800 | [diff] [blame] | 759 | if (kwds_size) { |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 760 | Py_INCREF(kwd_mark); |
| 761 | PyTuple_SET_ITEM(key, key_pos++, kwd_mark); |
Raymond Hettinger | dda4468 | 2017-01-08 18:04:30 -0800 | [diff] [blame] | 762 | for (pos = 0; PyDict_Next(kwds, &pos, &keyword, &value);) { |
| 763 | Py_INCREF(keyword); |
| 764 | PyTuple_SET_ITEM(key, key_pos++, keyword); |
| 765 | Py_INCREF(value); |
| 766 | PyTuple_SET_ITEM(key, key_pos++, value); |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 767 | } |
Raymond Hettinger | dda4468 | 2017-01-08 18:04:30 -0800 | [diff] [blame] | 768 | assert(key_pos == PyTuple_GET_SIZE(args) + kwds_size * 2 + 1); |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 769 | } |
| 770 | if (typed) { |
| 771 | for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) { |
| 772 | PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(args, pos)); |
| 773 | Py_INCREF(item); |
| 774 | PyTuple_SET_ITEM(key, key_pos++, item); |
| 775 | } |
Raymond Hettinger | dda4468 | 2017-01-08 18:04:30 -0800 | [diff] [blame] | 776 | if (kwds_size) { |
| 777 | for (pos = 0; PyDict_Next(kwds, &pos, &keyword, &value);) { |
| 778 | PyObject *item = (PyObject *)Py_TYPE(value); |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 779 | Py_INCREF(item); |
| 780 | PyTuple_SET_ITEM(key, key_pos++, item); |
| 781 | } |
| 782 | } |
| 783 | } |
| 784 | assert(key_pos == key_size); |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 785 | return key; |
| 786 | } |
| 787 | |
| 788 | static PyObject * |
| 789 | uncached_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds) |
| 790 | { |
| 791 | PyObject *result = PyObject_Call(self->func, args, kwds); |
| 792 | if (!result) |
| 793 | return NULL; |
| 794 | self->misses++; |
| 795 | return result; |
| 796 | } |
| 797 | |
| 798 | static PyObject * |
| 799 | infinite_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds) |
| 800 | { |
| 801 | PyObject *result; |
Serhiy Storchaka | b9d98d5 | 2015-10-02 12:47:11 +0300 | [diff] [blame] | 802 | Py_hash_t hash; |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 803 | PyObject *key = lru_cache_make_key(args, kwds, self->typed); |
| 804 | if (!key) |
| 805 | return NULL; |
Serhiy Storchaka | b9d98d5 | 2015-10-02 12:47:11 +0300 | [diff] [blame] | 806 | hash = PyObject_Hash(key); |
Yury Selivanov | 46a02db | 2016-11-09 18:55:45 -0500 | [diff] [blame] | 807 | if (hash == -1) { |
| 808 | Py_DECREF(key); |
Serhiy Storchaka | b9d98d5 | 2015-10-02 12:47:11 +0300 | [diff] [blame] | 809 | return NULL; |
Yury Selivanov | 46a02db | 2016-11-09 18:55:45 -0500 | [diff] [blame] | 810 | } |
Serhiy Storchaka | b9d98d5 | 2015-10-02 12:47:11 +0300 | [diff] [blame] | 811 | result = _PyDict_GetItem_KnownHash(self->cache, key, hash); |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 812 | if (result) { |
| 813 | Py_INCREF(result); |
| 814 | self->hits++; |
| 815 | Py_DECREF(key); |
| 816 | return result; |
| 817 | } |
| 818 | if (PyErr_Occurred()) { |
| 819 | Py_DECREF(key); |
| 820 | return NULL; |
| 821 | } |
| 822 | result = PyObject_Call(self->func, args, kwds); |
| 823 | if (!result) { |
| 824 | Py_DECREF(key); |
| 825 | return NULL; |
| 826 | } |
Serhiy Storchaka | b9d98d5 | 2015-10-02 12:47:11 +0300 | [diff] [blame] | 827 | if (_PyDict_SetItem_KnownHash(self->cache, key, result, hash) < 0) { |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 828 | Py_DECREF(result); |
| 829 | Py_DECREF(key); |
| 830 | return NULL; |
| 831 | } |
| 832 | Py_DECREF(key); |
| 833 | self->misses++; |
| 834 | return result; |
| 835 | } |
| 836 | |
| 837 | static void |
| 838 | lru_cache_extricate_link(lru_list_elem *link) |
| 839 | { |
| 840 | link->prev->next = link->next; |
| 841 | link->next->prev = link->prev; |
| 842 | } |
| 843 | |
| 844 | static void |
| 845 | lru_cache_append_link(lru_cache_object *self, lru_list_elem *link) |
| 846 | { |
| 847 | lru_list_elem *root = &self->root; |
| 848 | lru_list_elem *last = root->prev; |
| 849 | last->next = root->prev = link; |
| 850 | link->prev = last; |
| 851 | link->next = root; |
| 852 | } |
| 853 | |
| 854 | static PyObject * |
| 855 | bounded_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds) |
| 856 | { |
| 857 | lru_list_elem *link; |
| 858 | PyObject *key, *result; |
Serhiy Storchaka | b9d98d5 | 2015-10-02 12:47:11 +0300 | [diff] [blame] | 859 | Py_hash_t hash; |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 860 | |
| 861 | key = lru_cache_make_key(args, kwds, self->typed); |
| 862 | if (!key) |
| 863 | return NULL; |
Serhiy Storchaka | b9d98d5 | 2015-10-02 12:47:11 +0300 | [diff] [blame] | 864 | hash = PyObject_Hash(key); |
Yury Selivanov | 46a02db | 2016-11-09 18:55:45 -0500 | [diff] [blame] | 865 | if (hash == -1) { |
| 866 | Py_DECREF(key); |
Serhiy Storchaka | b9d98d5 | 2015-10-02 12:47:11 +0300 | [diff] [blame] | 867 | return NULL; |
Yury Selivanov | 46a02db | 2016-11-09 18:55:45 -0500 | [diff] [blame] | 868 | } |
Serhiy Storchaka | b9d98d5 | 2015-10-02 12:47:11 +0300 | [diff] [blame] | 869 | link = (lru_list_elem *)_PyDict_GetItem_KnownHash(self->cache, key, hash); |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 870 | if (link) { |
| 871 | lru_cache_extricate_link(link); |
| 872 | lru_cache_append_link(self, link); |
| 873 | self->hits++; |
| 874 | result = link->result; |
| 875 | Py_INCREF(result); |
| 876 | Py_DECREF(key); |
| 877 | return result; |
| 878 | } |
| 879 | if (PyErr_Occurred()) { |
| 880 | Py_DECREF(key); |
| 881 | return NULL; |
| 882 | } |
| 883 | result = PyObject_Call(self->func, args, kwds); |
| 884 | if (!result) { |
| 885 | Py_DECREF(key); |
| 886 | return NULL; |
| 887 | } |
| 888 | if (self->full && self->root.next != &self->root) { |
| 889 | /* Use the oldest item to store the new key and result. */ |
Serhiy Storchaka | 6779652 | 2017-01-12 18:34:33 +0200 | [diff] [blame] | 890 | PyObject *oldkey, *oldresult, *popresult; |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 891 | /* Extricate the oldest item. */ |
| 892 | link = self->root.next; |
| 893 | lru_cache_extricate_link(link); |
| 894 | /* Remove it from the cache. |
| 895 | The cache dict holds one reference to the link, |
| 896 | and the linked list holds yet one reference to it. */ |
Serhiy Storchaka | 42e1ea9 | 2017-01-12 19:12:21 +0200 | [diff] [blame] | 897 | popresult = _PyDict_Pop_KnownHash(self->cache, |
Serhiy Storchaka | 6779652 | 2017-01-12 18:34:33 +0200 | [diff] [blame] | 898 | link->key, link->hash, |
| 899 | Py_None); |
| 900 | if (popresult == Py_None) { |
| 901 | /* Getting here means that this same key was added to the |
| 902 | cache while the lock was released. Since the link |
| 903 | update is already done, we need only return the |
| 904 | computed result and update the count of misses. */ |
| 905 | Py_DECREF(popresult); |
| 906 | Py_DECREF(link); |
| 907 | Py_DECREF(key); |
| 908 | } |
| 909 | else if (popresult == NULL) { |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 910 | lru_cache_append_link(self, link); |
| 911 | Py_DECREF(key); |
| 912 | Py_DECREF(result); |
| 913 | return NULL; |
| 914 | } |
Serhiy Storchaka | 6779652 | 2017-01-12 18:34:33 +0200 | [diff] [blame] | 915 | else { |
| 916 | Py_DECREF(popresult); |
| 917 | /* Keep a reference to the old key and old result to |
| 918 | prevent their ref counts from going to zero during the |
| 919 | update. That will prevent potentially arbitrary object |
| 920 | clean-up code (i.e. __del__) from running while we're |
| 921 | still adjusting the links. */ |
| 922 | oldkey = link->key; |
| 923 | oldresult = link->result; |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 924 | |
Serhiy Storchaka | 6779652 | 2017-01-12 18:34:33 +0200 | [diff] [blame] | 925 | link->hash = hash; |
| 926 | link->key = key; |
| 927 | link->result = result; |
| 928 | if (_PyDict_SetItem_KnownHash(self->cache, key, (PyObject *)link, |
| 929 | hash) < 0) { |
| 930 | Py_DECREF(link); |
| 931 | Py_DECREF(oldkey); |
| 932 | Py_DECREF(oldresult); |
| 933 | return NULL; |
| 934 | } |
| 935 | lru_cache_append_link(self, link); |
| 936 | Py_INCREF(result); /* for return */ |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 937 | Py_DECREF(oldkey); |
| 938 | Py_DECREF(oldresult); |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 939 | } |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 940 | } else { |
| 941 | /* Put result in a new link at the front of the queue. */ |
INADA Naoki | 3070b71 | 2017-12-26 02:03:24 +0900 | [diff] [blame] | 942 | link = (lru_list_elem *)PyObject_New(lru_list_elem, |
| 943 | &lru_list_elem_type); |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 944 | if (link == NULL) { |
| 945 | Py_DECREF(key); |
| 946 | Py_DECREF(result); |
| 947 | return NULL; |
| 948 | } |
| 949 | |
Serhiy Storchaka | b9d98d5 | 2015-10-02 12:47:11 +0300 | [diff] [blame] | 950 | link->hash = hash; |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 951 | link->key = key; |
| 952 | link->result = result; |
Serhiy Storchaka | b9d98d5 | 2015-10-02 12:47:11 +0300 | [diff] [blame] | 953 | if (_PyDict_SetItem_KnownHash(self->cache, key, (PyObject *)link, |
| 954 | hash) < 0) { |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 955 | Py_DECREF(link); |
| 956 | return NULL; |
| 957 | } |
| 958 | lru_cache_append_link(self, link); |
| 959 | Py_INCREF(result); /* for return */ |
Serhiy Storchaka | 5ab81d7 | 2016-12-16 16:18:57 +0200 | [diff] [blame] | 960 | self->full = (PyDict_GET_SIZE(self->cache) >= self->maxsize); |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 961 | } |
| 962 | self->misses++; |
| 963 | return result; |
| 964 | } |
| 965 | |
| 966 | static PyObject * |
| 967 | lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw) |
| 968 | { |
Serhiy Storchaka | 374164c | 2015-07-25 12:10:21 +0300 | [diff] [blame] | 969 | PyObject *func, *maxsize_O, *cache_info_type, *cachedict; |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 970 | int typed; |
| 971 | lru_cache_object *obj; |
| 972 | Py_ssize_t maxsize; |
| 973 | PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *); |
| 974 | static char *keywords[] = {"user_function", "maxsize", "typed", |
| 975 | "cache_info_type", NULL}; |
| 976 | |
| 977 | if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords, |
| 978 | &func, &maxsize_O, &typed, |
| 979 | &cache_info_type)) { |
| 980 | return NULL; |
| 981 | } |
| 982 | |
| 983 | if (!PyCallable_Check(func)) { |
| 984 | PyErr_SetString(PyExc_TypeError, |
| 985 | "the first argument must be callable"); |
| 986 | return NULL; |
| 987 | } |
| 988 | |
| 989 | /* select the caching function, and make/inc maxsize_O */ |
| 990 | if (maxsize_O == Py_None) { |
| 991 | wrapper = infinite_lru_cache_wrapper; |
| 992 | /* use this only to initialize lru_cache_object attribute maxsize */ |
| 993 | maxsize = -1; |
| 994 | } else if (PyIndex_Check(maxsize_O)) { |
| 995 | maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError); |
| 996 | if (maxsize == -1 && PyErr_Occurred()) |
| 997 | return NULL; |
| 998 | if (maxsize == 0) |
| 999 | wrapper = uncached_lru_cache_wrapper; |
| 1000 | else |
| 1001 | wrapper = bounded_lru_cache_wrapper; |
| 1002 | } else { |
| 1003 | PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None"); |
| 1004 | return NULL; |
| 1005 | } |
| 1006 | |
Serhiy Storchaka | 374164c | 2015-07-25 12:10:21 +0300 | [diff] [blame] | 1007 | if (!(cachedict = PyDict_New())) |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 1008 | return NULL; |
| 1009 | |
Serhiy Storchaka | 374164c | 2015-07-25 12:10:21 +0300 | [diff] [blame] | 1010 | obj = (lru_cache_object *)type->tp_alloc(type, 0); |
| 1011 | if (obj == NULL) { |
| 1012 | Py_DECREF(cachedict); |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 1013 | return NULL; |
| 1014 | } |
| 1015 | |
Serhiy Storchaka | 374164c | 2015-07-25 12:10:21 +0300 | [diff] [blame] | 1016 | obj->cache = cachedict; |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 1017 | obj->root.prev = &obj->root; |
| 1018 | obj->root.next = &obj->root; |
| 1019 | obj->maxsize = maxsize; |
| 1020 | Py_INCREF(maxsize_O); |
| 1021 | obj->maxsize_O = maxsize_O; |
| 1022 | Py_INCREF(func); |
| 1023 | obj->func = func; |
| 1024 | obj->wrapper = wrapper; |
| 1025 | obj->misses = obj->hits = 0; |
| 1026 | obj->typed = typed; |
| 1027 | Py_INCREF(cache_info_type); |
| 1028 | obj->cache_info_type = cache_info_type; |
| 1029 | |
| 1030 | return (PyObject *)obj; |
| 1031 | } |
| 1032 | |
| 1033 | static lru_list_elem * |
| 1034 | lru_cache_unlink_list(lru_cache_object *self) |
| 1035 | { |
| 1036 | lru_list_elem *root = &self->root; |
| 1037 | lru_list_elem *link = root->next; |
| 1038 | if (link == root) |
| 1039 | return NULL; |
| 1040 | root->prev->next = NULL; |
| 1041 | root->next = root->prev = root; |
| 1042 | return link; |
| 1043 | } |
| 1044 | |
| 1045 | static void |
| 1046 | lru_cache_clear_list(lru_list_elem *link) |
| 1047 | { |
| 1048 | while (link != NULL) { |
| 1049 | lru_list_elem *next = link->next; |
| 1050 | Py_DECREF(link); |
| 1051 | link = next; |
| 1052 | } |
| 1053 | } |
| 1054 | |
| 1055 | static void |
| 1056 | lru_cache_dealloc(lru_cache_object *obj) |
| 1057 | { |
INADA Naoki | a6296d3 | 2017-08-24 14:55:17 +0900 | [diff] [blame] | 1058 | lru_list_elem *list; |
| 1059 | /* bpo-31095: UnTrack is needed before calling any callbacks */ |
| 1060 | PyObject_GC_UnTrack(obj); |
| 1061 | |
| 1062 | list = lru_cache_unlink_list(obj); |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 1063 | Py_XDECREF(obj->maxsize_O); |
| 1064 | Py_XDECREF(obj->func); |
| 1065 | Py_XDECREF(obj->cache); |
| 1066 | Py_XDECREF(obj->dict); |
| 1067 | Py_XDECREF(obj->cache_info_type); |
| 1068 | lru_cache_clear_list(list); |
| 1069 | Py_TYPE(obj)->tp_free(obj); |
| 1070 | } |
| 1071 | |
| 1072 | static PyObject * |
| 1073 | lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds) |
| 1074 | { |
| 1075 | return self->wrapper(self, args, kwds); |
| 1076 | } |
| 1077 | |
| 1078 | static PyObject * |
Serhiy Storchaka | e7070f0 | 2015-06-08 11:19:24 +0300 | [diff] [blame] | 1079 | lru_cache_descr_get(PyObject *self, PyObject *obj, PyObject *type) |
| 1080 | { |
| 1081 | if (obj == Py_None || obj == NULL) { |
| 1082 | Py_INCREF(self); |
| 1083 | return self; |
| 1084 | } |
| 1085 | return PyMethod_New(self, obj); |
| 1086 | } |
| 1087 | |
| 1088 | static PyObject * |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 1089 | lru_cache_cache_info(lru_cache_object *self, PyObject *unused) |
| 1090 | { |
| 1091 | return PyObject_CallFunction(self->cache_info_type, "nnOn", |
| 1092 | self->hits, self->misses, self->maxsize_O, |
Serhiy Storchaka | 5ab81d7 | 2016-12-16 16:18:57 +0200 | [diff] [blame] | 1093 | PyDict_GET_SIZE(self->cache)); |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 1094 | } |
| 1095 | |
| 1096 | static PyObject * |
| 1097 | lru_cache_cache_clear(lru_cache_object *self, PyObject *unused) |
| 1098 | { |
| 1099 | lru_list_elem *list = lru_cache_unlink_list(self); |
| 1100 | self->hits = self->misses = 0; |
| 1101 | self->full = 0; |
| 1102 | PyDict_Clear(self->cache); |
| 1103 | lru_cache_clear_list(list); |
| 1104 | Py_RETURN_NONE; |
| 1105 | } |
| 1106 | |
Serhiy Storchaka | 45120f2 | 2015-10-24 09:49:56 +0300 | [diff] [blame] | 1107 | static PyObject * |
| 1108 | lru_cache_reduce(PyObject *self, PyObject *unused) |
| 1109 | { |
| 1110 | return PyObject_GetAttrString(self, "__qualname__"); |
| 1111 | } |
| 1112 | |
Serhiy Storchaka | e4d65e3 | 2015-12-28 23:58:07 +0200 | [diff] [blame] | 1113 | static PyObject * |
| 1114 | lru_cache_copy(PyObject *self, PyObject *unused) |
| 1115 | { |
| 1116 | Py_INCREF(self); |
| 1117 | return self; |
| 1118 | } |
| 1119 | |
| 1120 | static PyObject * |
| 1121 | lru_cache_deepcopy(PyObject *self, PyObject *unused) |
| 1122 | { |
| 1123 | Py_INCREF(self); |
| 1124 | return self; |
| 1125 | } |
| 1126 | |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 1127 | static int |
| 1128 | lru_cache_tp_traverse(lru_cache_object *self, visitproc visit, void *arg) |
| 1129 | { |
| 1130 | lru_list_elem *link = self->root.next; |
| 1131 | while (link != &self->root) { |
| 1132 | lru_list_elem *next = link->next; |
INADA Naoki | 3070b71 | 2017-12-26 02:03:24 +0900 | [diff] [blame] | 1133 | Py_VISIT(link->key); |
| 1134 | Py_VISIT(link->result); |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 1135 | link = next; |
| 1136 | } |
| 1137 | Py_VISIT(self->maxsize_O); |
| 1138 | Py_VISIT(self->func); |
| 1139 | Py_VISIT(self->cache); |
| 1140 | Py_VISIT(self->cache_info_type); |
| 1141 | Py_VISIT(self->dict); |
| 1142 | return 0; |
| 1143 | } |
| 1144 | |
| 1145 | static int |
| 1146 | lru_cache_tp_clear(lru_cache_object *self) |
| 1147 | { |
| 1148 | lru_list_elem *list = lru_cache_unlink_list(self); |
| 1149 | Py_CLEAR(self->maxsize_O); |
| 1150 | Py_CLEAR(self->func); |
| 1151 | Py_CLEAR(self->cache); |
| 1152 | Py_CLEAR(self->cache_info_type); |
| 1153 | Py_CLEAR(self->dict); |
| 1154 | lru_cache_clear_list(list); |
| 1155 | return 0; |
| 1156 | } |
| 1157 | |
| 1158 | |
| 1159 | PyDoc_STRVAR(lru_cache_doc, |
| 1160 | "Create a cached callable that wraps another function.\n\ |
| 1161 | \n\ |
| 1162 | user_function: the function being cached\n\ |
| 1163 | \n\ |
| 1164 | maxsize: 0 for no caching\n\ |
| 1165 | None for unlimited cache size\n\ |
| 1166 | n for a bounded cache\n\ |
| 1167 | \n\ |
| 1168 | typed: False cache f(3) and f(3.0) as identical calls\n\ |
| 1169 | True cache f(3) and f(3.0) as distinct calls\n\ |
| 1170 | \n\ |
| 1171 | cache_info_type: namedtuple class with the fields:\n\ |
| 1172 | hits misses currsize maxsize\n" |
| 1173 | ); |
| 1174 | |
| 1175 | static PyMethodDef lru_cache_methods[] = { |
| 1176 | {"cache_info", (PyCFunction)lru_cache_cache_info, METH_NOARGS}, |
| 1177 | {"cache_clear", (PyCFunction)lru_cache_cache_clear, METH_NOARGS}, |
Serhiy Storchaka | 45120f2 | 2015-10-24 09:49:56 +0300 | [diff] [blame] | 1178 | {"__reduce__", (PyCFunction)lru_cache_reduce, METH_NOARGS}, |
Serhiy Storchaka | e4d65e3 | 2015-12-28 23:58:07 +0200 | [diff] [blame] | 1179 | {"__copy__", (PyCFunction)lru_cache_copy, METH_VARARGS}, |
| 1180 | {"__deepcopy__", (PyCFunction)lru_cache_deepcopy, METH_VARARGS}, |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 1181 | {NULL} |
| 1182 | }; |
| 1183 | |
| 1184 | static PyGetSetDef lru_cache_getsetlist[] = { |
| 1185 | {"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict}, |
| 1186 | {NULL} |
| 1187 | }; |
| 1188 | |
| 1189 | static PyTypeObject lru_cache_type = { |
| 1190 | PyVarObject_HEAD_INIT(NULL, 0) |
| 1191 | "functools._lru_cache_wrapper", /* tp_name */ |
| 1192 | sizeof(lru_cache_object), /* tp_basicsize */ |
| 1193 | 0, /* tp_itemsize */ |
| 1194 | /* methods */ |
| 1195 | (destructor)lru_cache_dealloc, /* tp_dealloc */ |
| 1196 | 0, /* tp_print */ |
| 1197 | 0, /* tp_getattr */ |
| 1198 | 0, /* tp_setattr */ |
| 1199 | 0, /* tp_reserved */ |
| 1200 | 0, /* tp_repr */ |
| 1201 | 0, /* tp_as_number */ |
| 1202 | 0, /* tp_as_sequence */ |
| 1203 | 0, /* tp_as_mapping */ |
| 1204 | 0, /* tp_hash */ |
| 1205 | (ternaryfunc)lru_cache_call, /* tp_call */ |
| 1206 | 0, /* tp_str */ |
| 1207 | 0, /* tp_getattro */ |
| 1208 | 0, /* tp_setattro */ |
| 1209 | 0, /* tp_as_buffer */ |
| 1210 | Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE|Py_TPFLAGS_HAVE_GC, |
| 1211 | /* tp_flags */ |
| 1212 | lru_cache_doc, /* tp_doc */ |
| 1213 | (traverseproc)lru_cache_tp_traverse,/* tp_traverse */ |
| 1214 | (inquiry)lru_cache_tp_clear, /* tp_clear */ |
| 1215 | 0, /* tp_richcompare */ |
| 1216 | 0, /* tp_weaklistoffset */ |
| 1217 | 0, /* tp_iter */ |
| 1218 | 0, /* tp_iternext */ |
| 1219 | lru_cache_methods, /* tp_methods */ |
| 1220 | 0, /* tp_members */ |
| 1221 | lru_cache_getsetlist, /* tp_getset */ |
| 1222 | 0, /* tp_base */ |
| 1223 | 0, /* tp_dict */ |
Serhiy Storchaka | e7070f0 | 2015-06-08 11:19:24 +0300 | [diff] [blame] | 1224 | lru_cache_descr_get, /* tp_descr_get */ |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 1225 | 0, /* tp_descr_set */ |
| 1226 | offsetof(lru_cache_object, dict), /* tp_dictoffset */ |
| 1227 | 0, /* tp_init */ |
| 1228 | 0, /* tp_alloc */ |
| 1229 | lru_cache_new, /* tp_new */ |
| 1230 | }; |
| 1231 | |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 1232 | /* module level code ********************************************************/ |
| 1233 | |
| 1234 | PyDoc_STRVAR(module_doc, |
Thomas Wouters | 4d70c3d | 2006-06-08 14:42:34 +0000 | [diff] [blame] | 1235 | "Tools that operate on functions."); |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 1236 | |
| 1237 | static PyMethodDef module_methods[] = { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 1238 | {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc}, |
Victor Stinner | 446c8d5 | 2011-04-05 12:21:35 +0200 | [diff] [blame] | 1239 | {"cmp_to_key", (PyCFunction)functools_cmp_to_key, |
| 1240 | METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc}, |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 1241 | {NULL, NULL} /* sentinel */ |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 1242 | }; |
| 1243 | |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 1244 | static void |
| 1245 | module_free(void *m) |
| 1246 | { |
| 1247 | Py_CLEAR(kwd_mark); |
| 1248 | } |
Martin v. Löwis | 1a21451 | 2008-06-11 05:26:20 +0000 | [diff] [blame] | 1249 | |
| 1250 | static struct PyModuleDef _functoolsmodule = { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 1251 | PyModuleDef_HEAD_INIT, |
| 1252 | "_functools", |
| 1253 | module_doc, |
| 1254 | -1, |
| 1255 | module_methods, |
| 1256 | NULL, |
| 1257 | NULL, |
| 1258 | NULL, |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 1259 | module_free, |
Martin v. Löwis | 1a21451 | 2008-06-11 05:26:20 +0000 | [diff] [blame] | 1260 | }; |
| 1261 | |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 1262 | PyMODINIT_FUNC |
Martin v. Löwis | 1a21451 | 2008-06-11 05:26:20 +0000 | [diff] [blame] | 1263 | PyInit__functools(void) |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 1264 | { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 1265 | int i; |
| 1266 | PyObject *m; |
Serhiy Storchaka | 4ab46d7 | 2017-09-17 21:11:04 +0300 | [diff] [blame] | 1267 | const char *name; |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 1268 | PyTypeObject *typelist[] = { |
| 1269 | &partial_type, |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 1270 | &lru_cache_type, |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 1271 | NULL |
| 1272 | }; |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 1273 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 1274 | m = PyModule_Create(&_functoolsmodule); |
| 1275 | if (m == NULL) |
| 1276 | return NULL; |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 1277 | |
Victor Stinner | a5ed5f0 | 2016-12-06 18:45:50 +0100 | [diff] [blame] | 1278 | kwd_mark = _PyObject_CallNoArg((PyObject *)&PyBaseObject_Type); |
Serhiy Storchaka | 46c5611 | 2015-05-24 21:53:49 +0300 | [diff] [blame] | 1279 | if (!kwd_mark) { |
| 1280 | Py_DECREF(m); |
| 1281 | return NULL; |
| 1282 | } |
| 1283 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 1284 | for (i=0 ; typelist[i] != NULL ; i++) { |
| 1285 | if (PyType_Ready(typelist[i]) < 0) { |
| 1286 | Py_DECREF(m); |
| 1287 | return NULL; |
| 1288 | } |
Serhiy Storchaka | 4ab46d7 | 2017-09-17 21:11:04 +0300 | [diff] [blame] | 1289 | name = _PyType_Name(typelist[i]); |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 1290 | Py_INCREF(typelist[i]); |
Serhiy Storchaka | 4ab46d7 | 2017-09-17 21:11:04 +0300 | [diff] [blame] | 1291 | PyModule_AddObject(m, name, (PyObject *)typelist[i]); |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 1292 | } |
| 1293 | return m; |
Raymond Hettinger | 9c323f8 | 2005-02-28 19:39:44 +0000 | [diff] [blame] | 1294 | } |