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