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