Branch data Line data Source code
1 : :
2 : : /* Tuple object implementation */
3 : :
4 : : #include "Python.h"
5 : : #include "pycore_abstract.h" // _PyIndex_Check()
6 : : #include "pycore_gc.h" // _PyObject_GC_IS_TRACKED()
7 : : #include "pycore_initconfig.h" // _PyStatus_OK()
8 : : #include "pycore_object.h" // _PyObject_GC_TRACK(), _Py_FatalRefcountError()
9 : :
10 : : /*[clinic input]
11 : : class tuple "PyTupleObject *" "&PyTuple_Type"
12 : : [clinic start generated code]*/
13 : : /*[clinic end generated code: output=da39a3ee5e6b4b0d input=f051ba3cfdf9a189]*/
14 : :
15 : : #include "clinic/tupleobject.c.h"
16 : :
17 : :
18 : : static inline PyTupleObject * maybe_freelist_pop(Py_ssize_t);
19 : : static inline int maybe_freelist_push(PyTupleObject *);
20 : :
21 : :
22 : : /* Allocate an uninitialized tuple object. Before making it public, following
23 : : steps must be done:
24 : :
25 : : - Initialize its items.
26 : : - Call _PyObject_GC_TRACK() on it.
27 : :
28 : : Because the empty tuple is always reused and it's already tracked by GC,
29 : : this function must not be called with size == 0 (unless from PyTuple_New()
30 : : which wraps this function).
31 : : */
32 : : static PyTupleObject *
33 : 281710119 : tuple_alloc(Py_ssize_t size)
34 : : {
35 [ + + ]: 281710119 : if (size < 0) {
36 : 1 : PyErr_BadInternalCall();
37 : 1 : return NULL;
38 : : }
39 : : #ifdef Py_DEBUG
40 : : assert(size != 0); // The empty tuple is statically allocated.
41 : : #endif
42 : :
43 : 281710118 : PyTupleObject *op = maybe_freelist_pop(size);
44 [ + + ]: 281710118 : if (op == NULL) {
45 : : /* Check for overflow */
46 [ - + ]: 35705705 : if ((size_t)size > ((size_t)PY_SSIZE_T_MAX - (sizeof(PyTupleObject) -
47 : : sizeof(PyObject *))) / sizeof(PyObject *)) {
48 : : return (PyTupleObject *)PyErr_NoMemory();
49 : : }
50 : 35705705 : op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
51 [ - + ]: 35705705 : if (op == NULL)
52 : 0 : return NULL;
53 : : }
54 : 281710118 : return op;
55 : : }
56 : :
57 : : // The empty tuple singleton is not tracked by the GC.
58 : : // It does not contain any Python object.
59 : : // Note that tuple subclasses have their own empty instances.
60 : :
61 : : static inline PyObject *
62 : 24803272 : tuple_get_empty(void)
63 : : {
64 : 24803272 : Py_INCREF(&_Py_SINGLETON(tuple_empty));
65 : 24803272 : return (PyObject *)&_Py_SINGLETON(tuple_empty);
66 : : }
67 : :
68 : : PyObject *
69 : 141328005 : PyTuple_New(Py_ssize_t size)
70 : : {
71 : : PyTupleObject *op;
72 [ + + ]: 141328005 : if (size == 0) {
73 : 6578385 : return tuple_get_empty();
74 : : }
75 : 134749620 : op = tuple_alloc(size);
76 [ + + ]: 134749620 : if (op == NULL) {
77 : 1 : return NULL;
78 : : }
79 [ + + ]: 535223175 : for (Py_ssize_t i = 0; i < size; i++) {
80 : 400473556 : op->ob_item[i] = NULL;
81 : : }
82 : 134749619 : _PyObject_GC_TRACK(op);
83 : 134749619 : return (PyObject *) op;
84 : : }
85 : :
86 : : Py_ssize_t
87 : 18539792 : PyTuple_Size(PyObject *op)
88 : : {
89 [ - + ]: 18539792 : if (!PyTuple_Check(op)) {
90 : 0 : PyErr_BadInternalCall();
91 : 0 : return -1;
92 : : }
93 : : else
94 : 18539792 : return Py_SIZE(op);
95 : : }
96 : :
97 : : PyObject *
98 : 12126249 : PyTuple_GetItem(PyObject *op, Py_ssize_t i)
99 : : {
100 [ - + ]: 12126249 : if (!PyTuple_Check(op)) {
101 : 0 : PyErr_BadInternalCall();
102 : 0 : return NULL;
103 : : }
104 [ + + + + ]: 12126249 : if (i < 0 || i >= Py_SIZE(op)) {
105 : 2 : PyErr_SetString(PyExc_IndexError, "tuple index out of range");
106 : 2 : return NULL;
107 : : }
108 : 12126247 : return ((PyTupleObject *)op) -> ob_item[i];
109 : : }
110 : :
111 : : int
112 : 86 : PyTuple_SetItem(PyObject *op, Py_ssize_t i, PyObject *newitem)
113 : : {
114 : : PyObject **p;
115 [ + - - + ]: 86 : if (!PyTuple_Check(op) || Py_REFCNT(op) != 1) {
116 : 0 : Py_XDECREF(newitem);
117 : 0 : PyErr_BadInternalCall();
118 : 0 : return -1;
119 : : }
120 [ + - - + ]: 86 : if (i < 0 || i >= Py_SIZE(op)) {
121 : 0 : Py_XDECREF(newitem);
122 : 0 : PyErr_SetString(PyExc_IndexError,
123 : : "tuple assignment index out of range");
124 : 0 : return -1;
125 : : }
126 : 86 : p = ((PyTupleObject *)op) -> ob_item + i;
127 : 86 : Py_XSETREF(*p, newitem);
128 : 86 : return 0;
129 : : }
130 : :
131 : : void
132 : 78012971 : _PyTuple_MaybeUntrack(PyObject *op)
133 : : {
134 : : PyTupleObject *t;
135 : : Py_ssize_t i, n;
136 : :
137 [ + - - + ]: 78012971 : if (!PyTuple_CheckExact(op) || !_PyObject_GC_IS_TRACKED(op))
138 : 0 : return;
139 : 78012971 : t = (PyTupleObject *) op;
140 : 78012971 : n = Py_SIZE(t);
141 [ + + ]: 212976993 : for (i = 0; i < n; i++) {
142 : 179177874 : PyObject *elt = PyTuple_GET_ITEM(t, i);
143 : : /* Tuple with NULL elements aren't
144 : : fully constructed, don't untrack
145 : : them yet. */
146 [ + + + + ]: 358343377 : if (!elt ||
147 : 179165503 : _PyObject_GC_MAY_BE_TRACKED(elt))
148 : 44213852 : return;
149 : : }
150 : 33799119 : _PyObject_GC_UNTRACK(op);
151 : : }
152 : :
153 : : PyObject *
154 : 10652461 : PyTuple_Pack(Py_ssize_t n, ...)
155 : : {
156 : : Py_ssize_t i;
157 : : PyObject *o;
158 : : PyObject **items;
159 : : va_list vargs;
160 : :
161 [ - + ]: 10652461 : if (n == 0) {
162 : 0 : return tuple_get_empty();
163 : : }
164 : :
165 : 10652461 : va_start(vargs, n);
166 : 10652461 : PyTupleObject *result = tuple_alloc(n);
167 [ - + ]: 10652461 : if (result == NULL) {
168 : 0 : va_end(vargs);
169 : 0 : return NULL;
170 : : }
171 : 10652461 : items = result->ob_item;
172 [ + + ]: 27778650 : for (i = 0; i < n; i++) {
173 : 17126189 : o = va_arg(vargs, PyObject *);
174 : 17126189 : Py_INCREF(o);
175 : 17126189 : items[i] = o;
176 : : }
177 : 10652461 : va_end(vargs);
178 : 10652461 : _PyObject_GC_TRACK(result);
179 : 10652461 : return (PyObject *)result;
180 : : }
181 : :
182 : :
183 : : /* Methods */
184 : :
185 : : static void
186 : 289186963 : tupledealloc(PyTupleObject *op)
187 : : {
188 [ + + ]: 289186963 : if (Py_SIZE(op) == 0) {
189 : : /* The empty tuple is statically allocated. */
190 [ - + ]: 43 : if (op == &_Py_SINGLETON(tuple_empty)) {
191 : : #ifdef Py_DEBUG
192 : : _Py_FatalRefcountError("deallocating the empty tuple singleton");
193 : : #else
194 : 0 : return;
195 : : #endif
196 : : }
197 : : #ifdef Py_DEBUG
198 : : /* tuple subclasses have their own empty instances. */
199 : : assert(!PyTuple_CheckExact(op));
200 : : #endif
201 : : }
202 : :
203 : 289186963 : PyObject_GC_UnTrack(op);
204 [ + + + + ]: 289186963 : Py_TRASHCAN_BEGIN(op, tupledealloc)
205 : :
206 : 289185472 : Py_ssize_t i = Py_SIZE(op);
207 [ + + ]: 992162335 : while (--i >= 0) {
208 : 702976863 : Py_XDECREF(op->ob_item[i]);
209 : : }
210 : : // This will abort on the empty singleton (if there is one).
211 [ + + ]: 289185472 : if (!maybe_freelist_push(op)) {
212 : 23204122 : Py_TYPE(op)->tp_free((PyObject *)op);
213 : : }
214 : :
215 [ + + ]: 289185472 : Py_TRASHCAN_END
216 : : }
217 : :
218 : : static PyObject *
219 : 24888 : tuplerepr(PyTupleObject *v)
220 : : {
221 : : Py_ssize_t i, n;
222 : : _PyUnicodeWriter writer;
223 : :
224 : 24888 : n = Py_SIZE(v);
225 [ + + ]: 24888 : if (n == 0)
226 : 1613 : return PyUnicode_FromString("()");
227 : :
228 : : /* While not mutable, it is still possible to end up with a cycle in a
229 : : tuple through an object that stores itself within a tuple (and thus
230 : : infinitely asks for the repr of itself). This should only be
231 : : possible within a type. */
232 : 23275 : i = Py_ReprEnter((PyObject *)v);
233 [ - + ]: 23275 : if (i != 0) {
234 [ # # ]: 0 : return i > 0 ? PyUnicode_FromString("(...)") : NULL;
235 : : }
236 : :
237 : 23275 : _PyUnicodeWriter_Init(&writer);
238 : 23275 : writer.overallocate = 1;
239 [ + + ]: 23275 : if (Py_SIZE(v) > 1) {
240 : : /* "(" + "1" + ", 2" * (len - 1) + ")" */
241 : 19423 : writer.min_length = 1 + 1 + (2 + 1) * (Py_SIZE(v) - 1) + 1;
242 : : }
243 : : else {
244 : : /* "(1,)" */
245 : 3852 : writer.min_length = 4;
246 : : }
247 : :
248 [ - + ]: 23275 : if (_PyUnicodeWriter_WriteChar(&writer, '(') < 0)
249 : 0 : goto error;
250 : :
251 : : /* Do repr() on each element. */
252 [ + + ]: 1151861 : for (i = 0; i < n; ++i) {
253 : : PyObject *s;
254 : :
255 [ + + ]: 1128586 : if (i > 0) {
256 [ - + ]: 1105311 : if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)
257 : 0 : goto error;
258 : : }
259 : :
260 : 1128586 : s = PyObject_Repr(v->ob_item[i]);
261 [ - + ]: 1128586 : if (s == NULL)
262 : 0 : goto error;
263 : :
264 [ - + ]: 1128586 : if (_PyUnicodeWriter_WriteStr(&writer, s) < 0) {
265 : 0 : Py_DECREF(s);
266 : 0 : goto error;
267 : : }
268 : 1128586 : Py_DECREF(s);
269 : : }
270 : :
271 : 23275 : writer.overallocate = 0;
272 [ + + ]: 23275 : if (n > 1) {
273 [ - + ]: 19423 : if (_PyUnicodeWriter_WriteChar(&writer, ')') < 0)
274 : 0 : goto error;
275 : : }
276 : : else {
277 [ - + ]: 3852 : if (_PyUnicodeWriter_WriteASCIIString(&writer, ",)", 2) < 0)
278 : 0 : goto error;
279 : : }
280 : :
281 : 23275 : Py_ReprLeave((PyObject *)v);
282 : 23275 : return _PyUnicodeWriter_Finish(&writer);
283 : :
284 : 0 : error:
285 : 0 : _PyUnicodeWriter_Dealloc(&writer);
286 : 0 : Py_ReprLeave((PyObject *)v);
287 : 0 : return NULL;
288 : : }
289 : :
290 : :
291 : : /* Hash for tuples. This is a slightly simplified version of the xxHash
292 : : non-cryptographic hash:
293 : : - we do not use any parallellism, there is only 1 accumulator.
294 : : - we drop the final mixing since this is just a permutation of the
295 : : output space: it does not help against collisions.
296 : : - at the end, we mangle the length with a single constant.
297 : : For the xxHash specification, see
298 : : https://github.com/Cyan4973/xxHash/blob/master/doc/xxhash_spec.md
299 : :
300 : : Below are the official constants from the xxHash specification. Optimizing
301 : : compilers should emit a single "rotate" instruction for the
302 : : _PyHASH_XXROTATE() expansion. If that doesn't happen for some important
303 : : platform, the macro could be changed to expand to a platform-specific rotate
304 : : spelling instead.
305 : : */
306 : : #if SIZEOF_PY_UHASH_T > 4
307 : : #define _PyHASH_XXPRIME_1 ((Py_uhash_t)11400714785074694791ULL)
308 : : #define _PyHASH_XXPRIME_2 ((Py_uhash_t)14029467366897019727ULL)
309 : : #define _PyHASH_XXPRIME_5 ((Py_uhash_t)2870177450012600261ULL)
310 : : #define _PyHASH_XXROTATE(x) ((x << 31) | (x >> 33)) /* Rotate left 31 bits */
311 : : #else
312 : : #define _PyHASH_XXPRIME_1 ((Py_uhash_t)2654435761UL)
313 : : #define _PyHASH_XXPRIME_2 ((Py_uhash_t)2246822519UL)
314 : : #define _PyHASH_XXPRIME_5 ((Py_uhash_t)374761393UL)
315 : : #define _PyHASH_XXROTATE(x) ((x << 13) | (x >> 19)) /* Rotate left 13 bits */
316 : : #endif
317 : :
318 : : /* Tests have shown that it's not worth to cache the hash value, see
319 : : https://bugs.python.org/issue9685 */
320 : : static Py_hash_t
321 : 24791699 : tuplehash(PyTupleObject *v)
322 : : {
323 : 24791699 : Py_ssize_t i, len = Py_SIZE(v);
324 : 24791699 : PyObject **item = v->ob_item;
325 : :
326 : 24791699 : Py_uhash_t acc = _PyHASH_XXPRIME_5;
327 [ + + ]: 107562648 : for (i = 0; i < len; i++) {
328 : 82771009 : Py_uhash_t lane = PyObject_Hash(item[i]);
329 [ + + ]: 82771009 : if (lane == (Py_uhash_t)-1) {
330 : 60 : return -1;
331 : : }
332 : 82770949 : acc += lane * _PyHASH_XXPRIME_2;
333 : 82770949 : acc = _PyHASH_XXROTATE(acc);
334 : 82770949 : acc *= _PyHASH_XXPRIME_1;
335 : : }
336 : :
337 : : /* Add input length, mangled to keep the historical value of hash(()). */
338 : 24791639 : acc += len ^ (_PyHASH_XXPRIME_5 ^ 3527539UL);
339 : :
340 [ - + ]: 24791639 : if (acc == (Py_uhash_t)-1) {
341 : 0 : return 1546275796;
342 : : }
343 : 24791639 : return acc;
344 : : }
345 : :
346 : : static Py_ssize_t
347 : 13397381 : tuplelength(PyTupleObject *a)
348 : : {
349 : 13397381 : return Py_SIZE(a);
350 : : }
351 : :
352 : : static int
353 : 13144131 : tuplecontains(PyTupleObject *a, PyObject *el)
354 : : {
355 : : Py_ssize_t i;
356 : : int cmp;
357 : :
358 [ + + + + ]: 43110117 : for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
359 : 29965986 : cmp = PyObject_RichCompareBool(PyTuple_GET_ITEM(a, i), el, Py_EQ);
360 : 13144131 : return cmp;
361 : : }
362 : :
363 : : static PyObject *
364 : 3845205 : tupleitem(PyTupleObject *a, Py_ssize_t i)
365 : : {
366 [ + + + + ]: 3845205 : if (i < 0 || i >= Py_SIZE(a)) {
367 : 6828 : PyErr_SetString(PyExc_IndexError, "tuple index out of range");
368 : 6828 : return NULL;
369 : : }
370 : 3838377 : Py_INCREF(a->ob_item[i]);
371 : 3838377 : return a->ob_item[i];
372 : : }
373 : :
374 : : PyObject *
375 : 122841416 : _PyTuple_FromArray(PyObject *const *src, Py_ssize_t n)
376 : : {
377 [ + + ]: 122841416 : if (n == 0) {
378 : 14286180 : return tuple_get_empty();
379 : : }
380 : :
381 : 108555236 : PyTupleObject *tuple = tuple_alloc(n);
382 [ - + ]: 108555236 : if (tuple == NULL) {
383 : 0 : return NULL;
384 : : }
385 : 108555236 : PyObject **dst = tuple->ob_item;
386 [ + + ]: 308237195 : for (Py_ssize_t i = 0; i < n; i++) {
387 : 199681959 : PyObject *item = src[i];
388 : 199681959 : Py_INCREF(item);
389 : 199681959 : dst[i] = item;
390 : : }
391 : 108555236 : _PyObject_GC_TRACK(tuple);
392 : 108555236 : return (PyObject *)tuple;
393 : : }
394 : :
395 : : PyObject *
396 : 19134829 : _PyTuple_FromArraySteal(PyObject *const *src, Py_ssize_t n)
397 : : {
398 [ + + ]: 19134829 : if (n == 0) {
399 : 1000452 : return tuple_get_empty();
400 : : }
401 : 18134377 : PyTupleObject *tuple = tuple_alloc(n);
402 [ - + ]: 18134377 : if (tuple == NULL) {
403 [ # # ]: 0 : for (Py_ssize_t i = 0; i < n; i++) {
404 : 0 : Py_DECREF(src[i]);
405 : : }
406 : 0 : return NULL;
407 : : }
408 : 18134377 : PyObject **dst = tuple->ob_item;
409 [ + + ]: 44425443 : for (Py_ssize_t i = 0; i < n; i++) {
410 : 26291066 : PyObject *item = src[i];
411 : 26291066 : dst[i] = item;
412 : : }
413 : 18134377 : _PyObject_GC_TRACK(tuple);
414 : 18134377 : return (PyObject *)tuple;
415 : : }
416 : :
417 : : static PyObject *
418 : 16539724 : tupleslice(PyTupleObject *a, Py_ssize_t ilow,
419 : : Py_ssize_t ihigh)
420 : : {
421 [ - + ]: 16539724 : if (ilow < 0)
422 : 0 : ilow = 0;
423 [ + + ]: 16539724 : if (ihigh > Py_SIZE(a))
424 : 76507 : ihigh = Py_SIZE(a);
425 [ - + ]: 16539724 : if (ihigh < ilow)
426 : 0 : ihigh = ilow;
427 [ + + + + : 16539724 : if (ilow == 0 && ihigh == Py_SIZE(a) && PyTuple_CheckExact(a)) {
- + ]
428 : 0 : Py_INCREF(a);
429 : 0 : return (PyObject *)a;
430 : : }
431 : 16539724 : return _PyTuple_FromArray(a->ob_item + ilow, ihigh - ilow);
432 : : }
433 : :
434 : : PyObject *
435 : 16539578 : PyTuple_GetSlice(PyObject *op, Py_ssize_t i, Py_ssize_t j)
436 : : {
437 [ + - - + ]: 16539578 : if (op == NULL || !PyTuple_Check(op)) {
438 : 0 : PyErr_BadInternalCall();
439 : 0 : return NULL;
440 : : }
441 : 16539578 : return tupleslice((PyTupleObject *)op, i, j);
442 : : }
443 : :
444 : : static PyObject *
445 : 192819 : tupleconcat(PyTupleObject *a, PyObject *bb)
446 : : {
447 : : Py_ssize_t size;
448 : : Py_ssize_t i;
449 : : PyObject **src, **dest;
450 : : PyTupleObject *np;
451 [ + + + + ]: 192819 : if (Py_SIZE(a) == 0 && PyTuple_CheckExact(bb)) {
452 : 56179 : Py_INCREF(bb);
453 : 56179 : return bb;
454 : : }
455 [ + + ]: 136640 : if (!PyTuple_Check(bb)) {
456 : 1 : PyErr_Format(PyExc_TypeError,
457 : : "can only concatenate tuple (not \"%.200s\") to tuple",
458 : 1 : Py_TYPE(bb)->tp_name);
459 : 1 : return NULL;
460 : : }
461 : 136639 : PyTupleObject *b = (PyTupleObject *)bb;
462 : :
463 [ + + + + ]: 136639 : if (Py_SIZE(b) == 0 && PyTuple_CheckExact(a)) {
464 : 10210 : Py_INCREF(a);
465 : 10210 : return (PyObject *)a;
466 : : }
467 : : assert((size_t)Py_SIZE(a) + (size_t)Py_SIZE(b) < PY_SSIZE_T_MAX);
468 : 126429 : size = Py_SIZE(a) + Py_SIZE(b);
469 [ + + ]: 126429 : if (size == 0) {
470 : 1 : return tuple_get_empty();
471 : : }
472 : :
473 : 126428 : np = tuple_alloc(size);
474 [ - + ]: 126428 : if (np == NULL) {
475 : 0 : return NULL;
476 : : }
477 : 126428 : src = a->ob_item;
478 : 126428 : dest = np->ob_item;
479 [ + + ]: 769529 : for (i = 0; i < Py_SIZE(a); i++) {
480 : 643101 : PyObject *v = src[i];
481 : 643101 : Py_INCREF(v);
482 : 643101 : dest[i] = v;
483 : : }
484 : 126428 : src = b->ob_item;
485 : 126428 : dest = np->ob_item + Py_SIZE(a);
486 [ + + ]: 346814 : for (i = 0; i < Py_SIZE(b); i++) {
487 : 220386 : PyObject *v = src[i];
488 : 220386 : Py_INCREF(v);
489 : 220386 : dest[i] = v;
490 : : }
491 : 126428 : _PyObject_GC_TRACK(np);
492 : 126428 : return (PyObject *)np;
493 : : }
494 : :
495 : : static PyObject *
496 : 15165 : tuplerepeat(PyTupleObject *a, Py_ssize_t n)
497 : : {
498 : : Py_ssize_t size;
499 : : PyTupleObject *np;
500 [ + + + + ]: 15165 : if (Py_SIZE(a) == 0 || n == 1) {
501 [ + + ]: 9553 : if (PyTuple_CheckExact(a)) {
502 : : /* Since tuples are immutable, we can return a shared
503 : : copy in this case */
504 : 9547 : Py_INCREF(a);
505 : 9547 : return (PyObject *)a;
506 : : }
507 : : }
508 [ + + + + ]: 5618 : if (Py_SIZE(a) == 0 || n <= 0) {
509 : 4175 : return tuple_get_empty();
510 : : }
511 [ - + ]: 1443 : if (n > PY_SSIZE_T_MAX / Py_SIZE(a))
512 : : return PyErr_NoMemory();
513 : 1443 : size = Py_SIZE(a) * n;
514 : 1443 : np = tuple_alloc(size);
515 [ - + ]: 1443 : if (np == NULL)
516 : 0 : return NULL;
517 : 1443 : PyObject **dest = np->ob_item;
518 : 1443 : PyObject **dest_end = dest + size;
519 [ + + ]: 1443 : if (Py_SIZE(a) == 1) {
520 : 1376 : PyObject *elem = a->ob_item[0];
521 : 1376 : Py_SET_REFCNT(elem, Py_REFCNT(elem) + n);
522 : : #ifdef Py_REF_DEBUG
523 : : _Py_RefTotal += n;
524 : : #endif
525 [ + + ]: 1092511 : while (dest < dest_end) {
526 : 1091135 : *dest++ = elem;
527 : : }
528 : : }
529 : : else {
530 : 67 : PyObject **src = a->ob_item;
531 : 67 : PyObject **src_end = src + Py_SIZE(a);
532 [ + + ]: 15731 : while (src < src_end) {
533 : 15664 : Py_SET_REFCNT(*src, Py_REFCNT(*src) + n);
534 : : #ifdef Py_REF_DEBUG
535 : : _Py_RefTotal += n;
536 : : #endif
537 : 15664 : *dest++ = *src++;
538 : : }
539 : : // Now src chases after dest in the same buffer
540 : 67 : src = np->ob_item;
541 [ + + ]: 41700 : while (dest < dest_end) {
542 : 41633 : *dest++ = *src++;
543 : : }
544 : : }
545 : 1443 : _PyObject_GC_TRACK(np);
546 : 1443 : return (PyObject *) np;
547 : : }
548 : :
549 : : /*[clinic input]
550 : : tuple.index
551 : :
552 : : value: object
553 : : start: slice_index(accept={int}) = 0
554 : : stop: slice_index(accept={int}, c_default="PY_SSIZE_T_MAX") = sys.maxsize
555 : : /
556 : :
557 : : Return first index of value.
558 : :
559 : : Raises ValueError if the value is not present.
560 : : [clinic start generated code]*/
561 : :
562 : : static PyObject *
563 : 1704 : tuple_index_impl(PyTupleObject *self, PyObject *value, Py_ssize_t start,
564 : : Py_ssize_t stop)
565 : : /*[clinic end generated code: output=07b6f9f3cb5c33eb input=fb39e9874a21fe3f]*/
566 : : {
567 : : Py_ssize_t i;
568 : :
569 [ + + ]: 1704 : if (start < 0) {
570 : 6 : start += Py_SIZE(self);
571 [ + + ]: 6 : if (start < 0)
572 : 3 : start = 0;
573 : : }
574 [ + + ]: 1704 : if (stop < 0) {
575 : 4 : stop += Py_SIZE(self);
576 : : }
577 [ + + ]: 1700 : else if (stop > Py_SIZE(self)) {
578 : 1698 : stop = Py_SIZE(self);
579 : : }
580 [ + + ]: 2106 : for (i = start; i < stop; i++) {
581 : 2100 : int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ);
582 [ + + ]: 2100 : if (cmp > 0)
583 : 1697 : return PyLong_FromSsize_t(i);
584 [ + + ]: 403 : else if (cmp < 0)
585 : 1 : return NULL;
586 : : }
587 : 6 : PyErr_SetString(PyExc_ValueError, "tuple.index(x): x not in tuple");
588 : 6 : return NULL;
589 : : }
590 : :
591 : : /*[clinic input]
592 : : tuple.count
593 : :
594 : : value: object
595 : : /
596 : :
597 : : Return number of occurrences of value.
598 : : [clinic start generated code]*/
599 : :
600 : : static PyObject *
601 : 183 : tuple_count(PyTupleObject *self, PyObject *value)
602 : : /*[clinic end generated code: output=aa927affc5a97605 input=531721aff65bd772]*/
603 : : {
604 : 183 : Py_ssize_t count = 0;
605 : : Py_ssize_t i;
606 : :
607 [ + + ]: 785 : for (i = 0; i < Py_SIZE(self); i++) {
608 : 603 : int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ);
609 [ + + ]: 603 : if (cmp > 0)
610 : 341 : count++;
611 [ + + ]: 262 : else if (cmp < 0)
612 : 1 : return NULL;
613 : : }
614 : 182 : return PyLong_FromSsize_t(count);
615 : : }
616 : :
617 : : static int
618 : 175771808 : tupletraverse(PyTupleObject *o, visitproc visit, void *arg)
619 : : {
620 : : Py_ssize_t i;
621 : :
622 [ + + ]: 747305343 : for (i = Py_SIZE(o); --i >= 0; )
623 [ + + + + ]: 571533550 : Py_VISIT(o->ob_item[i]);
624 : 175771793 : return 0;
625 : : }
626 : :
627 : : static PyObject *
628 : 15078901 : tuplerichcompare(PyObject *v, PyObject *w, int op)
629 : : {
630 : : PyTupleObject *vt, *wt;
631 : : Py_ssize_t i;
632 : : Py_ssize_t vlen, wlen;
633 : :
634 [ + - + + ]: 15078901 : if (!PyTuple_Check(v) || !PyTuple_Check(w))
635 : 40984 : Py_RETURN_NOTIMPLEMENTED;
636 : :
637 : 15037917 : vt = (PyTupleObject *)v;
638 : 15037917 : wt = (PyTupleObject *)w;
639 : :
640 : 15037917 : vlen = Py_SIZE(vt);
641 : 15037917 : wlen = Py_SIZE(wt);
642 : :
643 : : /* Note: the corresponding code for lists has an "early out" test
644 : : * here when op is EQ or NE and the lengths differ. That pays there,
645 : : * but Tim was unable to find any real code where EQ/NE tuple
646 : : * compares don't have the same length, so testing for it here would
647 : : * have cost without benefit.
648 : : */
649 : :
650 : : /* Search for the first index where items are different.
651 : : * Note that because tuples are immutable, it's safe to reuse
652 : : * vlen and wlen across the comparison calls.
653 : : */
654 [ + + + + ]: 39483682 : for (i = 0; i < vlen && i < wlen; i++) {
655 : 28056211 : int k = PyObject_RichCompareBool(vt->ob_item[i],
656 : : wt->ob_item[i], Py_EQ);
657 [ + + ]: 28056211 : if (k < 0)
658 : 2906 : return NULL;
659 [ + + ]: 28053305 : if (!k)
660 : 3607540 : break;
661 : : }
662 : :
663 [ + + + + ]: 15035011 : if (i >= vlen || i >= wlen) {
664 : : /* No more items to compare -- compare sizes */
665 [ + + + + : 11427471 : Py_RETURN_RICHCOMPARE(vlen, wlen, op);
+ + - + +
+ + + + +
+ + - +
- ]
666 : : }
667 : :
668 : : /* We have an item that differs -- shortcuts for EQ/NE */
669 [ + + ]: 3607540 : if (op == Py_EQ) {
670 : 2756244 : Py_RETURN_FALSE;
671 : : }
672 [ + + ]: 851296 : if (op == Py_NE) {
673 : 153068 : Py_RETURN_TRUE;
674 : : }
675 : :
676 : : /* Compare the final item again using the proper operator */
677 : 698228 : return PyObject_RichCompare(vt->ob_item[i], wt->ob_item[i], op);
678 : : }
679 : :
680 : : static PyObject *
681 : : tuple_subtype_new(PyTypeObject *type, PyObject *iterable);
682 : :
683 : : /*[clinic input]
684 : : @classmethod
685 : : tuple.__new__ as tuple_new
686 : : iterable: object(c_default="NULL") = ()
687 : : /
688 : :
689 : : Built-in immutable sequence.
690 : :
691 : : If no argument is given, the constructor returns an empty tuple.
692 : : If iterable is specified the tuple is initialized from iterable's items.
693 : :
694 : : If the argument is a tuple, the return value is the same object.
695 : : [clinic start generated code]*/
696 : :
697 : : static PyObject *
698 : 15762949 : tuple_new_impl(PyTypeObject *type, PyObject *iterable)
699 : : /*[clinic end generated code: output=4546d9f0d469bce7 input=86963bcde633b5a2]*/
700 : : {
701 [ + + ]: 15762949 : if (type != &PyTuple_Type)
702 : 7829065 : return tuple_subtype_new(type, iterable);
703 : :
704 [ + + ]: 7933884 : if (iterable == NULL) {
705 : 30 : return tuple_get_empty();
706 : : }
707 : : else {
708 : 7933854 : return PySequence_Tuple(iterable);
709 : : }
710 : : }
711 : :
712 : : static PyObject *
713 : 105133 : tuple_vectorcall(PyObject *type, PyObject * const*args,
714 : : size_t nargsf, PyObject *kwnames)
715 : : {
716 [ + + + - ]: 105133 : if (!_PyArg_NoKwnames("tuple", kwnames)) {
717 : 4 : return NULL;
718 : : }
719 : :
720 : 105129 : Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);
721 [ + - - + : 105129 : if (!_PyArg_CheckPositional("tuple", nargs, 0, 1)) {
- - ]
722 : 0 : return NULL;
723 : : }
724 : :
725 [ + + ]: 105129 : if (nargs) {
726 : 104819 : return tuple_new_impl(_PyType_CAST(type), args[0]);
727 : : }
728 : : else {
729 : 310 : return tuple_get_empty();
730 : : }
731 : : }
732 : :
733 : : static PyObject *
734 : 7829065 : tuple_subtype_new(PyTypeObject *type, PyObject *iterable)
735 : : {
736 : : PyObject *tmp, *newobj, *item;
737 : : Py_ssize_t i, n;
738 : :
739 : : assert(PyType_IsSubtype(type, &PyTuple_Type));
740 : : // tuple subclasses must implement the GC protocol
741 : : assert(_PyType_IS_GC(type));
742 : :
743 : 7829065 : tmp = tuple_new_impl(&PyTuple_Type, iterable);
744 [ - + ]: 7829065 : if (tmp == NULL)
745 : 0 : return NULL;
746 : : assert(PyTuple_Check(tmp));
747 : : /* This may allocate an empty tuple that is not the global one. */
748 : 7829065 : newobj = type->tp_alloc(type, n = PyTuple_GET_SIZE(tmp));
749 [ - + ]: 7829065 : if (newobj == NULL) {
750 : 0 : Py_DECREF(tmp);
751 : 0 : return NULL;
752 : : }
753 [ + + ]: 47269811 : for (i = 0; i < n; i++) {
754 : 39440746 : item = PyTuple_GET_ITEM(tmp, i);
755 : 39440746 : Py_INCREF(item);
756 : 39440746 : PyTuple_SET_ITEM(newobj, i, item);
757 : : }
758 : 7829065 : Py_DECREF(tmp);
759 : :
760 : : // Don't track if a subclass tp_alloc is PyType_GenericAlloc()
761 [ - + ]: 7829065 : if (!_PyObject_GC_IS_TRACKED(newobj)) {
762 : 0 : _PyObject_GC_TRACK(newobj);
763 : : }
764 : 7829065 : return newobj;
765 : : }
766 : :
767 : : static PySequenceMethods tuple_as_sequence = {
768 : : (lenfunc)tuplelength, /* sq_length */
769 : : (binaryfunc)tupleconcat, /* sq_concat */
770 : : (ssizeargfunc)tuplerepeat, /* sq_repeat */
771 : : (ssizeargfunc)tupleitem, /* sq_item */
772 : : 0, /* sq_slice */
773 : : 0, /* sq_ass_item */
774 : : 0, /* sq_ass_slice */
775 : : (objobjproc)tuplecontains, /* sq_contains */
776 : : };
777 : :
778 : : static PyObject*
779 : 17480821 : tuplesubscript(PyTupleObject* self, PyObject* item)
780 : : {
781 [ + + ]: 17480821 : if (_PyIndex_Check(item)) {
782 : 2667802 : Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
783 [ + + + + ]: 2667802 : if (i == -1 && PyErr_Occurred())
784 : 2 : return NULL;
785 [ + + ]: 2667800 : if (i < 0)
786 : 1843678 : i += PyTuple_GET_SIZE(self);
787 : 2667800 : return tupleitem(self, i);
788 : : }
789 [ + + ]: 14813019 : else if (PySlice_Check(item)) {
790 : : Py_ssize_t start, stop, step, slicelength, i;
791 : : size_t cur;
792 : : PyObject* it;
793 : : PyObject **src, **dest;
794 : :
795 [ + + ]: 14813017 : if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
796 : 4 : return NULL;
797 : : }
798 : 14813013 : slicelength = PySlice_AdjustIndices(PyTuple_GET_SIZE(self), &start,
799 : : &stop, step);
800 : :
801 [ + + ]: 14813013 : if (slicelength <= 0) {
802 : 2922672 : return tuple_get_empty();
803 : : }
804 [ + + + + : 21490354 : else if (start == 0 && step == 1 &&
+ + ]
805 [ + + ]: 11999830 : slicelength == PyTuple_GET_SIZE(self) &&
806 : 2399817 : PyTuple_CheckExact(self)) {
807 : 2399787 : Py_INCREF(self);
808 : 2399787 : return (PyObject *)self;
809 : : }
810 : : else {
811 : 9490554 : PyTupleObject* result = tuple_alloc(slicelength);
812 [ - + ]: 9490554 : if (!result) return NULL;
813 : :
814 : 9490554 : src = self->ob_item;
815 : 9490554 : dest = result->ob_item;
816 [ + + ]: 28877266 : for (cur = start, i = 0; i < slicelength;
817 : 19386712 : cur += step, i++) {
818 : 19386712 : it = src[cur];
819 : 19386712 : Py_INCREF(it);
820 : 19386712 : dest[i] = it;
821 : : }
822 : :
823 : 9490554 : _PyObject_GC_TRACK(result);
824 : 9490554 : return (PyObject *)result;
825 : : }
826 : : }
827 : : else {
828 : 2 : PyErr_Format(PyExc_TypeError,
829 : : "tuple indices must be integers or slices, not %.200s",
830 : 2 : Py_TYPE(item)->tp_name);
831 : 2 : return NULL;
832 : : }
833 : : }
834 : :
835 : : /*[clinic input]
836 : : tuple.__getnewargs__
837 : : [clinic start generated code]*/
838 : :
839 : : static PyObject *
840 : 146 : tuple___getnewargs___impl(PyTupleObject *self)
841 : : /*[clinic end generated code: output=25e06e3ee56027e2 input=1aeb4b286a21639a]*/
842 : : {
843 : 146 : return Py_BuildValue("(N)", tupleslice(self, 0, Py_SIZE(self)));
844 : : }
845 : :
846 : : static PyMethodDef tuple_methods[] = {
847 : : TUPLE___GETNEWARGS___METHODDEF
848 : : TUPLE_INDEX_METHODDEF
849 : : TUPLE_COUNT_METHODDEF
850 : : {"__class_getitem__", Py_GenericAlias, METH_O|METH_CLASS, PyDoc_STR("See PEP 585")},
851 : : {NULL, NULL} /* sentinel */
852 : : };
853 : :
854 : : static PyMappingMethods tuple_as_mapping = {
855 : : (lenfunc)tuplelength,
856 : : (binaryfunc)tuplesubscript,
857 : : 0
858 : : };
859 : :
860 : : static PyObject *tuple_iter(PyObject *seq);
861 : :
862 : : PyTypeObject PyTuple_Type = {
863 : : PyVarObject_HEAD_INIT(&PyType_Type, 0)
864 : : "tuple",
865 : : sizeof(PyTupleObject) - sizeof(PyObject *),
866 : : sizeof(PyObject *),
867 : : (destructor)tupledealloc, /* tp_dealloc */
868 : : 0, /* tp_vectorcall_offset */
869 : : 0, /* tp_getattr */
870 : : 0, /* tp_setattr */
871 : : 0, /* tp_as_async */
872 : : (reprfunc)tuplerepr, /* tp_repr */
873 : : 0, /* tp_as_number */
874 : : &tuple_as_sequence, /* tp_as_sequence */
875 : : &tuple_as_mapping, /* tp_as_mapping */
876 : : (hashfunc)tuplehash, /* tp_hash */
877 : : 0, /* tp_call */
878 : : 0, /* tp_str */
879 : : PyObject_GenericGetAttr, /* tp_getattro */
880 : : 0, /* tp_setattro */
881 : : 0, /* tp_as_buffer */
882 : : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
883 : : Py_TPFLAGS_BASETYPE | Py_TPFLAGS_TUPLE_SUBCLASS |
884 : : _Py_TPFLAGS_MATCH_SELF | Py_TPFLAGS_SEQUENCE, /* tp_flags */
885 : : tuple_new__doc__, /* tp_doc */
886 : : (traverseproc)tupletraverse, /* tp_traverse */
887 : : 0, /* tp_clear */
888 : : tuplerichcompare, /* tp_richcompare */
889 : : 0, /* tp_weaklistoffset */
890 : : tuple_iter, /* tp_iter */
891 : : 0, /* tp_iternext */
892 : : tuple_methods, /* tp_methods */
893 : : 0, /* tp_members */
894 : : 0, /* tp_getset */
895 : : 0, /* tp_base */
896 : : 0, /* tp_dict */
897 : : 0, /* tp_descr_get */
898 : : 0, /* tp_descr_set */
899 : : 0, /* tp_dictoffset */
900 : : 0, /* tp_init */
901 : : 0, /* tp_alloc */
902 : : tuple_new, /* tp_new */
903 : : PyObject_GC_Del, /* tp_free */
904 : : .tp_vectorcall = tuple_vectorcall,
905 : : };
906 : :
907 : : /* The following function breaks the notion that tuples are immutable:
908 : : it changes the size of a tuple. We get away with this only if there
909 : : is only one module referencing the object. You can also think of it
910 : : as creating a new tuple object and destroying the old one, only more
911 : : efficiently. In any case, don't use this if the tuple may already be
912 : : known to some other part of the code. */
913 : :
914 : : int
915 : 231819 : _PyTuple_Resize(PyObject **pv, Py_ssize_t newsize)
916 : : {
917 : : PyTupleObject *v;
918 : : PyTupleObject *sv;
919 : : Py_ssize_t i;
920 : : Py_ssize_t oldsize;
921 : :
922 : 231819 : v = (PyTupleObject *) *pv;
923 [ + - + - : 463638 : if (v == NULL || !Py_IS_TYPE(v, &PyTuple_Type) ||
+ + ]
924 [ - + ]: 463637 : (Py_SIZE(v) != 0 && Py_REFCNT(v) != 1)) {
925 : 0 : *pv = 0;
926 : 0 : Py_XDECREF(v);
927 : 0 : PyErr_BadInternalCall();
928 : 0 : return -1;
929 : : }
930 : :
931 : 231819 : oldsize = Py_SIZE(v);
932 [ + + ]: 231819 : if (oldsize == newsize) {
933 : 61932 : return 0;
934 : : }
935 [ + + ]: 169887 : if (newsize == 0) {
936 : 11067 : Py_DECREF(v);
937 : 11067 : *pv = tuple_get_empty();
938 : 11067 : return 0;
939 : : }
940 [ - + ]: 158820 : if (oldsize == 0) {
941 : : #ifdef Py_DEBUG
942 : : assert(v == &_Py_SINGLETON(tuple_empty));
943 : : #endif
944 : : /* The empty tuple is statically allocated so we never
945 : : resize it in-place. */
946 : 0 : Py_DECREF(v);
947 : 0 : *pv = PyTuple_New(newsize);
948 [ # # ]: 0 : return *pv == NULL ? -1 : 0;
949 : : }
950 : :
951 : : /* XXX UNREF/NEWREF interface should be more symmetrical */
952 : : #ifdef Py_REF_DEBUG
953 : : _Py_RefTotal--;
954 : : #endif
955 [ + + ]: 158820 : if (_PyObject_GC_IS_TRACKED(v)) {
956 : 158815 : _PyObject_GC_UNTRACK(v);
957 : : }
958 : : #ifdef Py_TRACE_REFS
959 : : _Py_ForgetReference((PyObject *) v);
960 : : #endif
961 : : /* DECREF items deleted by shrinkage */
962 [ + + ]: 1336931 : for (i = newsize; i < oldsize; i++) {
963 [ - + ]: 1178111 : Py_CLEAR(v->ob_item[i]);
964 : : }
965 : 158820 : sv = PyObject_GC_Resize(PyTupleObject, v, newsize);
966 [ - + ]: 158820 : if (sv == NULL) {
967 : 0 : *pv = NULL;
968 : 0 : PyObject_GC_Del(v);
969 : 0 : return -1;
970 : : }
971 : 158820 : _Py_NewReference((PyObject *) sv);
972 : : /* Zero out items added by growing */
973 [ + + ]: 158820 : if (newsize > oldsize)
974 : 7222 : memset(&sv->ob_item[oldsize], 0,
975 : 7222 : sizeof(*sv->ob_item) * (newsize - oldsize));
976 : 158820 : *pv = (PyObject *) sv;
977 : 158820 : _PyObject_GC_TRACK(sv);
978 : 158820 : return 0;
979 : : }
980 : :
981 : :
982 : : PyStatus
983 : 3138 : _PyTuple_InitTypes(PyInterpreterState *interp)
984 : : {
985 [ + + ]: 3138 : if (!_Py_IsMainInterpreter(interp)) {
986 : 171 : return _PyStatus_OK();
987 : : }
988 : :
989 [ - + ]: 2967 : if (PyType_Ready(&PyTuple_Type) < 0) {
990 : 0 : return _PyStatus_ERR("Can't initialize tuple type");
991 : : }
992 : :
993 [ - + ]: 2967 : if (PyType_Ready(&PyTupleIter_Type) < 0) {
994 : 0 : return _PyStatus_ERR("Can't initialize tuple iterator type");
995 : : }
996 : :
997 : 2967 : return _PyStatus_OK();
998 : : }
999 : :
1000 : : static void maybe_freelist_clear(PyInterpreterState *, int);
1001 : :
1002 : : void
1003 : 3125 : _PyTuple_Fini(PyInterpreterState *interp)
1004 : : {
1005 : 3125 : maybe_freelist_clear(interp, 1);
1006 : 3125 : }
1007 : :
1008 : : void
1009 : 26699 : _PyTuple_ClearFreeList(PyInterpreterState *interp)
1010 : : {
1011 : 26699 : maybe_freelist_clear(interp, 0);
1012 : 26699 : }
1013 : :
1014 : : /*********************** Tuple Iterator **************************/
1015 : :
1016 : : typedef struct {
1017 : : PyObject_HEAD
1018 : : Py_ssize_t it_index;
1019 : : PyTupleObject *it_seq; /* Set to NULL when iterator is exhausted */
1020 : : } tupleiterobject;
1021 : :
1022 : : static void
1023 : 28693053 : tupleiter_dealloc(tupleiterobject *it)
1024 : : {
1025 : 28693053 : _PyObject_GC_UNTRACK(it);
1026 : 28693053 : Py_XDECREF(it->it_seq);
1027 : 28693053 : PyObject_GC_Del(it);
1028 : 28693053 : }
1029 : :
1030 : : static int
1031 : 47720 : tupleiter_traverse(tupleiterobject *it, visitproc visit, void *arg)
1032 : : {
1033 [ + + - + ]: 47720 : Py_VISIT(it->it_seq);
1034 : 47720 : return 0;
1035 : : }
1036 : :
1037 : : static PyObject *
1038 : 99159364 : tupleiter_next(tupleiterobject *it)
1039 : : {
1040 : : PyTupleObject *seq;
1041 : : PyObject *item;
1042 : :
1043 : : assert(it != NULL);
1044 : 99159364 : seq = it->it_seq;
1045 [ + + ]: 99159364 : if (seq == NULL)
1046 : 90 : return NULL;
1047 : : assert(PyTuple_Check(seq));
1048 : :
1049 [ + + ]: 99159274 : if (it->it_index < PyTuple_GET_SIZE(seq)) {
1050 : 70994460 : item = PyTuple_GET_ITEM(seq, it->it_index);
1051 : 70994460 : ++it->it_index;
1052 : 70994460 : Py_INCREF(item);
1053 : 70994460 : return item;
1054 : : }
1055 : :
1056 : 28164814 : it->it_seq = NULL;
1057 : 28164814 : Py_DECREF(seq);
1058 : 28164814 : return NULL;
1059 : : }
1060 : :
1061 : : static PyObject *
1062 : 96425 : tupleiter_len(tupleiterobject *it, PyObject *Py_UNUSED(ignored))
1063 : : {
1064 : 96425 : Py_ssize_t len = 0;
1065 [ + + ]: 96425 : if (it->it_seq)
1066 : 96423 : len = PyTuple_GET_SIZE(it->it_seq) - it->it_index;
1067 : 96425 : return PyLong_FromSsize_t(len);
1068 : : }
1069 : :
1070 : : PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
1071 : :
1072 : : static PyObject *
1073 : 168 : tupleiter_reduce(tupleiterobject *it, PyObject *Py_UNUSED(ignored))
1074 : : {
1075 [ + - ]: 168 : if (it->it_seq)
1076 : 168 : return Py_BuildValue("N(O)n", _PyEval_GetBuiltin(&_Py_ID(iter)),
1077 : : it->it_seq, it->it_index);
1078 : : else
1079 : 0 : return Py_BuildValue("N(())", _PyEval_GetBuiltin(&_Py_ID(iter)));
1080 : : }
1081 : :
1082 : : static PyObject *
1083 : 216 : tupleiter_setstate(tupleiterobject *it, PyObject *state)
1084 : : {
1085 : 216 : Py_ssize_t index = PyLong_AsSsize_t(state);
1086 [ - + - - ]: 216 : if (index == -1 && PyErr_Occurred())
1087 : 0 : return NULL;
1088 [ + - ]: 216 : if (it->it_seq != NULL) {
1089 [ - + ]: 216 : if (index < 0)
1090 : 0 : index = 0;
1091 [ - + ]: 216 : else if (index > PyTuple_GET_SIZE(it->it_seq))
1092 : 0 : index = PyTuple_GET_SIZE(it->it_seq); /* exhausted iterator */
1093 : 216 : it->it_index = index;
1094 : : }
1095 : 216 : Py_RETURN_NONE;
1096 : : }
1097 : :
1098 : : PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1099 : : PyDoc_STRVAR(setstate_doc, "Set state information for unpickling.");
1100 : :
1101 : : static PyMethodDef tupleiter_methods[] = {
1102 : : {"__length_hint__", (PyCFunction)tupleiter_len, METH_NOARGS, length_hint_doc},
1103 : : {"__reduce__", (PyCFunction)tupleiter_reduce, METH_NOARGS, reduce_doc},
1104 : : {"__setstate__", (PyCFunction)tupleiter_setstate, METH_O, setstate_doc},
1105 : : {NULL, NULL} /* sentinel */
1106 : : };
1107 : :
1108 : : PyTypeObject PyTupleIter_Type = {
1109 : : PyVarObject_HEAD_INIT(&PyType_Type, 0)
1110 : : "tuple_iterator", /* tp_name */
1111 : : sizeof(tupleiterobject), /* tp_basicsize */
1112 : : 0, /* tp_itemsize */
1113 : : /* methods */
1114 : : (destructor)tupleiter_dealloc, /* tp_dealloc */
1115 : : 0, /* tp_vectorcall_offset */
1116 : : 0, /* tp_getattr */
1117 : : 0, /* tp_setattr */
1118 : : 0, /* tp_as_async */
1119 : : 0, /* tp_repr */
1120 : : 0, /* tp_as_number */
1121 : : 0, /* tp_as_sequence */
1122 : : 0, /* tp_as_mapping */
1123 : : 0, /* tp_hash */
1124 : : 0, /* tp_call */
1125 : : 0, /* tp_str */
1126 : : PyObject_GenericGetAttr, /* tp_getattro */
1127 : : 0, /* tp_setattro */
1128 : : 0, /* tp_as_buffer */
1129 : : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1130 : : 0, /* tp_doc */
1131 : : (traverseproc)tupleiter_traverse, /* tp_traverse */
1132 : : 0, /* tp_clear */
1133 : : 0, /* tp_richcompare */
1134 : : 0, /* tp_weaklistoffset */
1135 : : PyObject_SelfIter, /* tp_iter */
1136 : : (iternextfunc)tupleiter_next, /* tp_iternext */
1137 : : tupleiter_methods, /* tp_methods */
1138 : : 0,
1139 : : };
1140 : :
1141 : : static PyObject *
1142 : 28693053 : tuple_iter(PyObject *seq)
1143 : : {
1144 : : tupleiterobject *it;
1145 : :
1146 [ - + ]: 28693053 : if (!PyTuple_Check(seq)) {
1147 : 0 : PyErr_BadInternalCall();
1148 : 0 : return NULL;
1149 : : }
1150 : 28693053 : it = PyObject_GC_New(tupleiterobject, &PyTupleIter_Type);
1151 [ - + ]: 28693053 : if (it == NULL)
1152 : 0 : return NULL;
1153 : 28693053 : it->it_index = 0;
1154 : 28693053 : Py_INCREF(seq);
1155 : 28693053 : it->it_seq = (PyTupleObject *)seq;
1156 : 28693053 : _PyObject_GC_TRACK(it);
1157 : 28693053 : return (PyObject *)it;
1158 : : }
1159 : :
1160 : :
1161 : : /*************
1162 : : * freelists *
1163 : : *************/
1164 : :
1165 : : #define STATE (interp->tuple)
1166 : : #define FREELIST_FINALIZED (STATE.numfree[0] < 0)
1167 : :
1168 : : static inline PyTupleObject *
1169 : 281710118 : maybe_freelist_pop(Py_ssize_t size)
1170 : : {
1171 : : #if PyTuple_NFREELISTS > 0
1172 : 281710118 : PyInterpreterState *interp = _PyInterpreterState_GET();
1173 : : #ifdef Py_DEBUG
1174 : : /* maybe_freelist_pop() must not be called after maybe_freelist_fini(). */
1175 : : assert(!FREELIST_FINALIZED);
1176 : : #endif
1177 [ - + ]: 281710118 : if (size == 0) {
1178 : 0 : return NULL;
1179 : : }
1180 : : assert(size > 0);
1181 [ + + ]: 281710118 : if (size < PyTuple_MAXSAVESIZE) {
1182 : 280846048 : Py_ssize_t index = size - 1;
1183 : 280846048 : PyTupleObject *op = STATE.free_list[index];
1184 [ + + ]: 280846048 : if (op != NULL) {
1185 : : /* op is the head of a linked list, with the first item
1186 : : pointing to the next node. Here we pop off the old head. */
1187 : 246004413 : STATE.free_list[index] = (PyTupleObject *) op->ob_item[0];
1188 : 246004413 : STATE.numfree[index]--;
1189 : : /* Inlined _PyObject_InitVar() without _PyType_HasFeature() test */
1190 : : #ifdef Py_TRACE_REFS
1191 : : /* maybe_freelist_push() ensures these were already set. */
1192 : : // XXX Can we drop these? See commit 68055ce6fe01 (GvR, Dec 1998).
1193 : : Py_SET_SIZE(op, size);
1194 : : Py_SET_TYPE(op, &PyTuple_Type);
1195 : : #endif
1196 : 246004413 : _Py_NewReference((PyObject *)op);
1197 : : /* END inlined _PyObject_InitVar() */
1198 : : OBJECT_STAT_INC(from_freelist);
1199 : 246004413 : return op;
1200 : : }
1201 : : }
1202 : : #endif
1203 : 35705705 : return NULL;
1204 : : }
1205 : :
1206 : : static inline int
1207 : 289185472 : maybe_freelist_push(PyTupleObject *op)
1208 : : {
1209 : : #if PyTuple_NFREELISTS > 0
1210 : 289185472 : PyInterpreterState *interp = _PyInterpreterState_GET();
1211 : : #ifdef Py_DEBUG
1212 : : /* maybe_freelist_push() must not be called after maybe_freelist_fini(). */
1213 : : assert(!FREELIST_FINALIZED);
1214 : : #endif
1215 [ + + ]: 289185472 : if (Py_SIZE(op) == 0) {
1216 : 43 : return 0;
1217 : : }
1218 : 289185429 : Py_ssize_t index = Py_SIZE(op) - 1;
1219 [ + + ]: 289185429 : if (index < PyTuple_NFREELISTS
1220 [ + + ]: 288372168 : && STATE.numfree[index] < PyTuple_MAXFREELIST
1221 [ + + ]: 273811186 : && Py_IS_TYPE(op, &PyTuple_Type))
1222 : : {
1223 : : /* op is the head of a linked list, with the first item
1224 : : pointing to the next node. Here we set op as the new head. */
1225 : 265981350 : op->ob_item[0] = (PyObject *) STATE.free_list[index];
1226 : 265981350 : STATE.free_list[index] = op;
1227 : 265981350 : STATE.numfree[index]++;
1228 : : OBJECT_STAT_INC(to_freelist);
1229 : 265981350 : return 1;
1230 : : }
1231 : : #endif
1232 : 23204079 : return 0;
1233 : : }
1234 : :
1235 : : static void
1236 : 29824 : maybe_freelist_clear(PyInterpreterState *interp, int fini)
1237 : : {
1238 : : #if PyTuple_NFREELISTS > 0
1239 [ + + ]: 626304 : for (Py_ssize_t i = 0; i < PyTuple_NFREELISTS; i++) {
1240 : 596480 : PyTupleObject *p = STATE.free_list[i];
1241 : 596480 : STATE.free_list[i] = NULL;
1242 [ + + ]: 596480 : STATE.numfree[i] = fini ? -1 : 0;
1243 [ + + ]: 20570229 : while (p) {
1244 : 19973749 : PyTupleObject *q = p;
1245 : 19973749 : p = (PyTupleObject *)(p->ob_item[0]);
1246 : 19973749 : PyObject_GC_Del(q);
1247 : : }
1248 : : }
1249 : : #endif
1250 : 29824 : }
1251 : :
1252 : : /* Print summary info about the state of the optimized allocator */
1253 : : void
1254 : 1 : _PyTuple_DebugMallocStats(FILE *out)
1255 : : {
1256 : : #if PyTuple_NFREELISTS > 0
1257 : 1 : PyInterpreterState *interp = _PyInterpreterState_GET();
1258 [ + + ]: 21 : for (int i = 0; i < PyTuple_NFREELISTS; i++) {
1259 : 20 : int len = i + 1;
1260 : : char buf[128];
1261 : 20 : PyOS_snprintf(buf, sizeof(buf),
1262 : : "free %d-sized PyTupleObject", len);
1263 : 20 : _PyDebugAllocatorStats(out, buf, STATE.numfree[i],
1264 : 20 : _PyObject_VAR_SIZE(&PyTuple_Type, len));
1265 : : }
1266 : : #endif
1267 : 1 : }
1268 : :
1269 : : #undef STATE
1270 : : #undef FREELIST_FINALIZED
|