LCOV - code coverage report
Current view: | top level - Objects - tupleobject.c (source / functions) |  |  | Hit | Total | Coverage
Test: | CPython 3.12 LCOV report [commit 5e6661bce9] |  | Lines: | 361 | 504 | 71.6 %
Date: | 2023-03-20 08:15:36 |  | Functions: | 38 | 44 | 86.4 %
|  |  | Branches: | 213 | 363 | 58.7 %

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

Generated by: LCOV version 1.14