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