LCOV - code coverage report
Current view: top level - Objects - tupleobject.c (source / functions) Hit Total Coverage
Test: CPython 3.12 LCOV report [commit acb105a7c1f] Lines: 451 517 87.2 %
Date: 2022-07-20 13:12:14 Functions: 44 44 100.0 %
Branches: 296 365 81.1 %

           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

Generated by: LCOV version 1.14