LCOV - code coverage report
Current view: | top level - Objects - listobject.c (source / functions) |  |  | Hit | Total | Coverage
Test: | CPython 3.12 LCOV report [commit 5e6661bce9] |  | Lines: | 1051 | 1485 | 70.8 %
Date: | 2023-03-20 08:15:36 |  | Functions: | 80 | 97 | 82.5 %
|  |  | Branches: | 565 | 937 | 60.3 %

               Branch data     Line data    Source code
           1                 :            : /* List object implementation */
           2                 :            :
           3                 :            : #include "Python.h"
           4                 :            : #include "pycore_abstract.h"      // _PyIndex_Check()
           5                 :            : #include "pycore_interp.h"        // PyInterpreterState.list
           6                 :            : #include "pycore_list.h"          // struct _Py_list_state, _PyListIterObject
           7                 :            : #include "pycore_object.h"        // _PyObject_GC_TRACK()
           8                 :            : #include "pycore_tuple.h"         // _PyTuple_FromArray()
           9                 :            : #include <stddef.h>
          10                 :            :
          11                 :            : /*[clinic input]
          12                 :            : class list "PyListObject *" "&PyList_Type"
          13                 :            : [clinic start generated code]*/
          14                 :            : /*[clinic end generated code: output=da39a3ee5e6b4b0d input=f9b222678f9f71e0]*/
          15                 :            :
          16                 :            : #include "clinic/listobject.c.h"
          17                 :            :
          18                 :            : _Py_DECLARE_STR(list_err, "list index out of range");
          19                 :            :
          20                 :            : #if PyList_MAXFREELIST > 0
          21                 :            : static struct _Py_list_state *
          22                 :     511819 : get_list_state(void)
          23                 :            : {
          24                 :     511819 :     PyInterpreterState *interp = _PyInterpreterState_GET();
          25                 :     511819 :     return &interp->list;
          26                 :            : }
          27                 :            : #endif
          28                 :            :
          29                 :            :
          30                 :            : /* Ensure ob_item has room for at least newsize elements, and set
          31                 :            :  * ob_size to newsize.  If newsize > ob_size on entry, the content
          32                 :            :  * of the new slots at exit is undefined heap trash; it's the caller's
          33                 :            :  * responsibility to overwrite them with sane values.
          34                 :            :  * The number of allocated elements may grow, shrink, or stay the same.
          35                 :            :  * Failure is impossible if newsize <= self.allocated on entry, although
          36                 :            :  * that partly relies on an assumption that the system realloc() never
          37                 :            :  * fails when passed a number of bytes <= the number of bytes last
          38                 :            :  * allocated (the C standard doesn't guarantee this, but it's hard to
          39                 :            :  * imagine a realloc implementation where it wouldn't be true).
          40                 :            :  * Note that self->ob_item may change, and even if newsize is less
          41                 :            :  * than ob_size on entry.
          42                 :            :  */
          43                 :            : static int
          44                 :     269407 : list_resize(PyListObject *self, Py_ssize_t newsize)
          45                 :            : {
          46                 :            :     PyObject **items;
          47                 :            :     size_t new_allocated, num_allocated_bytes;
          48                 :     269407 :     Py_ssize_t allocated = self->allocated;
          49                 :            :
          50                 :            :     /* Bypass realloc() when a previous overallocation is large enough
          51                 :            :        to accommodate the newsize.  If the newsize falls lower than half
          52                 :            :        the allocated size, then proceed with the realloc() to shrink the list.
          53                 :            :     */
          54   [ +  +  +  + ]:     269407 :     if (allocated >= newsize && newsize >= (allocated >> 1)) {
          55                 :            :         assert(self->ob_item != NULL || newsize == 0);
          56                 :      16625 :         Py_SET_SIZE(self, newsize);
          57                 :      16625 :         return 0;
          58                 :            :     }
          59                 :            :
          60                 :            :     /* This over-allocates proportional to the list size, making room
          61                 :            :      * for additional growth.  The over-allocation is mild, but is
          62                 :            :      * enough to give linear-time amortized behavior over a long
          63                 :            :      * sequence of appends() in the presence of a poorly-performing
          64                 :            :      * system realloc().
          65                 :            :      * Add padding to make the allocated size multiple of 4.
          66                 :            :      * The growth pattern is:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
          67                 :            :      * Note: new_allocated won't overflow because the largest possible value
          68                 :            :      *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
          69                 :            :      */
          70                 :     252782 :     new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
          71                 :            :     /* Do not overallocate if the new size is closer to overallocated size
          72                 :            :      * than to the old size.
          73                 :            :      */
          74         [ +  + ]:     252782 :     if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
          75                 :        224 :         new_allocated = ((size_t)newsize + 3) & ~(size_t)3;
          76                 :            :
          77         [ +  + ]:     252782 :     if (newsize == 0)
          78                 :          5 :         new_allocated = 0;
          79         [ +  - ]:     252782 :     if (new_allocated <= (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {
          80                 :     252782 :         num_allocated_bytes = new_allocated * sizeof(PyObject *);
          81                 :     252782 :         items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
          82                 :            :     }
          83                 :            :     else {
          84                 :            :         // integer overflow
          85                 :          0 :         items = NULL;
          86                 :            :     }
          87         [ -  + ]:     252782 :     if (items == NULL) {
          88                 :          0 :         PyErr_NoMemory();
          89                 :          0 :         return -1;
          90                 :            :     }
          91                 :     252782 :     self->ob_item = items;
          92                 :     252782 :     Py_SET_SIZE(self, newsize);
          93                 :     252782 :     self->allocated = new_allocated;
          94                 :     252782 :     return 0;
          95                 :            : }
          96                 :            :
          97                 :            : static int
          98                 :      36864 : list_preallocate_exact(PyListObject *self, Py_ssize_t size)
          99                 :            : {
         100                 :            :     assert(self->ob_item == NULL);
         101                 :            :     assert(size > 0);
         102                 :            :
         103                 :            :     /* Since the Python memory allocator has granularity of 16 bytes on 64-bit
         104                 :            :      * platforms (8 on 32-bit), there is no benefit of allocating space for
         105                 :            :      * the odd number of items, and there is no drawback of rounding the
         106                 :            :      * allocated size up to the nearest even number.
         107                 :            :      */
         108                 :      36864 :     size = (size + 1) & ~(size_t)1;
         109         [ +  - ]:      36864 :     PyObject **items = PyMem_New(PyObject*, size);
         110         [ -  + ]:      36864 :     if (items == NULL) {
         111                 :          0 :         PyErr_NoMemory();
         112                 :          0 :         return -1;
         113                 :            :     }
         114                 :      36864 :     self->ob_item = items;
         115                 :      36864 :     self->allocated = size;
         116                 :      36864 :     return 0;
         117                 :            : }
         118                 :            :
         119                 :            : void
         120                 :        137 : _PyList_ClearFreeList(PyInterpreterState *interp)
         121                 :            : {
         122                 :            : #if PyList_MAXFREELIST > 0
         123                 :        137 :     struct _Py_list_state *state = &interp->list;
         124         [ +  + ]:       3449 :     while (state->numfree) {
         125                 :       3312 :         PyListObject *op = state->free_list[--state->numfree];
         126                 :            :         assert(PyList_CheckExact(op));
         127                 :       3312 :         PyObject_GC_Del(op);
         128                 :            :     }
         129                 :            : #endif
         130                 :        137 : }
         131                 :            :
         132                 :            : void
         133                 :         25 : _PyList_Fini(PyInterpreterState *interp)
         134                 :            : {
         135                 :         25 :     _PyList_ClearFreeList(interp);
         136                 :            : #if defined(Py_DEBUG) && PyList_MAXFREELIST > 0
         137                 :            :     struct _Py_list_state *state = &interp->list;
         138                 :            :     state->numfree = -1;
         139                 :            : #endif
         140                 :         25 : }
         141                 :            :
         142                 :            : /* Print summary info about the state of the optimized allocator */
         143                 :            : void
         144                 :          0 : _PyList_DebugMallocStats(FILE *out)
         145                 :            : {
         146                 :            : #if PyList_MAXFREELIST > 0
         147                 :          0 :     struct _Py_list_state *state = get_list_state();
         148                 :          0 :     _PyDebugAllocatorStats(out,
         149                 :            :                            "free PyListObject",
         150                 :            :                            state->numfree, sizeof(PyListObject));
         151                 :            : #endif
         152                 :          0 : }
         153                 :            :
         154                 :            : PyObject *
         155                 :     248637 : PyList_New(Py_ssize_t size)
         156                 :            : {
         157                 :            :     PyListObject *op;
         158                 :            :
         159         [ -  + ]:     248637 :     if (size < 0) {
         160                 :          0 :         PyErr_BadInternalCall();
         161                 :          0 :         return NULL;
         162                 :            :     }
         163                 :            :
         164                 :            : #if PyList_MAXFREELIST > 0
         165                 :     248637 :     struct _Py_list_state *state = get_list_state();
         166                 :            : #ifdef Py_DEBUG
         167                 :            :     // PyList_New() must not be called after _PyList_Fini()
         168                 :            :     assert(state->numfree != -1);
         169                 :            : #endif
         170         [ +  + ]:     248637 :     if (PyList_MAXFREELIST && state->numfree) {
         171                 :     237084 :         state->numfree--;
         172                 :     237084 :         op = state->free_list[state->numfree];
         173                 :            :         OBJECT_STAT_INC(from_freelist);
         174                 :     237084 :         _Py_NewReference((PyObject *)op);
         175                 :            :     }
         176                 :            :     else
         177                 :            : #endif
         178                 :            :     {
         179                 :      11553 :         op = PyObject_GC_New(PyListObject, &PyList_Type);
         180         [ -  + ]:      11553 :         if (op == NULL) {
         181                 :          0 :             return NULL;
         182                 :            :         }
         183                 :            :     }
         184         [ +  + ]:     248637 :     if (size <= 0) {
         185                 :     207062 :         op->ob_item = NULL;
         186                 :            :     }
         187                 :            :     else {
         188                 :      41575 :         op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
         189         [ -  + ]:      41575 :         if (op->ob_item == NULL) {
         190                 :          0 :             Py_DECREF(op);
         191                 :          0 :             return PyErr_NoMemory();
         192                 :            :         }
         193                 :            :     }
         194                 :     248637 :     Py_SET_SIZE(op, size);
         195                 :     248637 :     op->allocated = size;
         196                 :     248637 :     _PyObject_GC_TRACK(op);
         197                 :     248637 :     return (PyObject *) op;
         198                 :            : }
         199                 :            :
         200                 :            : static PyObject *
         201                 :       2196 : list_new_prealloc(Py_ssize_t size)
         202                 :            : {
         203                 :            :     assert(size > 0);
         204                 :       2196 :     PyListObject *op = (PyListObject *) PyList_New(0);
         205         [ -  + ]:       2196 :     if (op == NULL) {
         206                 :          0 :         return NULL;
         207                 :            :     }
         208                 :            :     assert(op->ob_item == NULL);
         209         [ +  - ]:       2196 :     op->ob_item = PyMem_New(PyObject *, size);
         210         [ -  + ]:       2196 :     if (op->ob_item == NULL) {
         211                 :          0 :         Py_DECREF(op);
         212                 :          0 :         return PyErr_NoMemory();
         213                 :            :     }
         214                 :       2196 :     op->allocated = size;
         215                 :       2196 :     return (PyObject *) op;
         216                 :            : }
         217                 :            :
         218                 :            : Py_ssize_t
         219                 :       8137 : PyList_Size(PyObject *op)
         220                 :            : {
         221         [ -  + ]:       8137 :     if (!PyList_Check(op)) {
         222                 :          0 :         PyErr_BadInternalCall();
         223                 :          0 :         return -1;
         224                 :            :     }
         225                 :            :     else
         226                 :       8137 :         return Py_SIZE(op);
         227                 :            : }
         228                 :            :
         229                 :            : static inline int
         230                 :      31450 : valid_index(Py_ssize_t i, Py_ssize_t limit)
         231                 :            : {
         232                 :            :     /* The cast to size_t lets us use just a single comparison
         233                 :            :        to check whether i is in the range: 0 <= i < limit.
         234                 :            :
         235                 :            :        See:  Section 14.2 "Bounds Checking" in the Agner Fog
         236                 :            :        optimization manual found at:
         237                 :            :        https://www.agner.org/optimize/optimizing_cpp.pdf
         238                 :            :     */
         239                 :      31450 :     return (size_t) i < (size_t) limit;
         240                 :            : }
         241                 :            :
         242                 :            : PyObject *
         243                 :         93 : PyList_GetItem(PyObject *op, Py_ssize_t i)
         244                 :            : {
         245         [ -  + ]:         93 :     if (!PyList_Check(op)) {
         246                 :          0 :         PyErr_BadInternalCall();
         247                 :          0 :         return NULL;
         248                 :            :     }
         249         [ -  + ]:         93 :     if (!valid_index(i, Py_SIZE(op))) {
         250                 :            :         _Py_DECLARE_STR(list_err, "list index out of range");
         251                 :          0 :         PyErr_SetObject(PyExc_IndexError, &_Py_STR(list_err));
         252                 :          0 :         return NULL;
         253                 :            :     }
         254                 :         93 :     return ((PyListObject *)op) -> ob_item[i];
         255                 :            : }
         256                 :            :
         257                 :            : int
         258                 :       5769 : PyList_SetItem(PyObject *op, Py_ssize_t i,
         259                 :            :                PyObject *newitem)
         260                 :            : {
         261                 :            :     PyObject **p;
         262         [ -  + ]:       5769 :     if (!PyList_Check(op)) {
         263                 :          0 :         Py_XDECREF(newitem);
         264                 :          0 :         PyErr_BadInternalCall();
         265                 :          0 :         return -1;
         266                 :            :     }
         267         [ -  + ]:       5769 :     if (!valid_index(i, Py_SIZE(op))) {
         268                 :          0 :         Py_XDECREF(newitem);
         269                 :          0 :         PyErr_SetString(PyExc_IndexError,
         270                 :            :                         "list assignment index out of range");
         271                 :          0 :         return -1;
         272                 :            :     }
         273                 :       5769 :     p = ((PyListObject *)op) -> ob_item + i;
         274                 :       5769 :     Py_XSETREF(*p, newitem);
         275                 :       5769 :     return 0;
         276                 :            : }
         277                 :            :
         278                 :            : static int
         279                 :        177 : ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
         280                 :            : {
         281                 :        177 :     Py_ssize_t i, n = Py_SIZE(self);
         282                 :            :     PyObject **items;
         283         [ -  + ]:        177 :     if (v == NULL) {
         284                 :          0 :         PyErr_BadInternalCall();
         285                 :          0 :         return -1;
         286                 :            :     }
         287                 :            :
         288                 :            :     assert((size_t)n + 1 < PY_SSIZE_T_MAX);
         289         [ -  + ]:        177 :     if (list_resize(self, n+1) < 0)
         290                 :          0 :         return -1;
         291                 :            :
         292         [ -  + ]:        177 :     if (where < 0) {
         293                 :          0 :         where += n;
         294         [ #  # ]:          0 :         if (where < 0)
         295                 :          0 :             where = 0;
         296                 :            :     }
         297         [ -  + ]:        177 :     if (where > n)
         298                 :          0 :         where = n;
         299                 :        177 :     items = self->ob_item;
         300         [ +  + ]:        777 :     for (i = n; --i >= where; )
         301                 :        600 :         items[i+1] = items[i];
         302                 :        177 :     items[where] = Py_NewRef(v);
         303                 :        177 :     return 0;
         304                 :            : }
         305                 :            :
         306                 :            : int
         307                 :         50 : PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
         308                 :            : {
         309         [ -  + ]:         50 :     if (!PyList_Check(op)) {
         310                 :          0 :         PyErr_BadInternalCall();
         311                 :          0 :         return -1;
         312                 :            :     }
         313                 :         50 :     return ins1((PyListObject *)op, where, newitem);
         314                 :            : }
         315                 :            :
         316                 :            : /* internal, used by _PyList_AppendTakeRef */
         317                 :            : int
         318                 :     238252 : _PyList_AppendTakeRefListResize(PyListObject *self, PyObject *newitem)
         319                 :            : {
         320                 :     238252 :     Py_ssize_t len = PyList_GET_SIZE(self);
         321                 :            :     assert(self->allocated == -1 || self->allocated == len);
         322         [ -  + ]:     238252 :     if (list_resize(self, len + 1) < 0) {
         323                 :          0 :         Py_DECREF(newitem);
         324                 :          0 :         return -1;
         325                 :            :     }
         326                 :     238252 :     PyList_SET_ITEM(self, len, newitem);
         327                 :     238252 :     return 0;
         328                 :            : }
         329                 :            :
         330                 :            : int
         331                 :    3479802 : PyList_Append(PyObject *op, PyObject *newitem)
         332                 :            : {
         333   [ +  -  +  - ]:    3479802 :     if (PyList_Check(op) && (newitem != NULL)) {
         334                 :    3479802 :         return _PyList_AppendTakeRef((PyListObject *)op, Py_NewRef(newitem));
         335                 :            :     }
         336                 :          0 :     PyErr_BadInternalCall();
         337                 :          0 :     return -1;
         338                 :            : }
         339                 :            :
         340                 :            : /* Methods */
         341                 :            :
         342                 :            : static void
         343                 :     263182 : list_dealloc(PyListObject *op)
         344                 :            : {
         345                 :            :     Py_ssize_t i;
         346                 :     263182 :     PyObject_GC_UnTrack(op);
         347   [ +  +  -  + ]:     263182 :     Py_TRASHCAN_BEGIN(op, list_dealloc)
         348         [ +  + ]:     263182 :     if (op->ob_item != NULL) {
         349                 :            :         /* Do it backwards, for Christian Tismer.
         350                 :            :            There's a simple test case where somehow this reduces
         351                 :            :            thrashing when a *very* large list is created and
         352                 :            :            immediately deleted. */
         353                 :     222714 :         i = Py_SIZE(op);
         354         [ +  + ]:    5636084 :         while (--i >= 0) {
         355                 :    5413370 :             Py_XDECREF(op->ob_item[i]);
         356                 :            :         }
         357                 :     222714 :         PyMem_Free(op->ob_item);
         358                 :            :     }
         359                 :            : #if PyList_MAXFREELIST > 0
         360                 :     263182 :     struct _Py_list_state *state = get_list_state();
         361                 :            : #ifdef Py_DEBUG
         362                 :            :     // list_dealloc() must not be called after _PyList_Fini()
         363                 :            :     assert(state->numfree != -1);
         364                 :            : #endif
         365   [ +  +  +  + ]:     263182 :     if (state->numfree < PyList_MAXFREELIST && PyList_CheckExact(op)) {
         366                 :     240633 :         state->free_list[state->numfree++] = op;
         367                 :     240633 :         OBJECT_STAT_INC(to_freelist);
         368                 :            :     }
         369                 :            :     else
         370                 :            : #endif
         371                 :            :     {
         372                 :      22549 :         Py_TYPE(op)->tp_free((PyObject *)op);
         373                 :            :     }
         374         [ +  + ]:     263182 :     Py_TRASHCAN_END
         375                 :     263182 : }
         376                 :            :
         377                 :            : static PyObject *
         378                 :         15 : list_repr(PyListObject *v)
         379                 :            : {
         380                 :            :     Py_ssize_t i;
         381                 :            :     PyObject *s;
         382                 :            :     _PyUnicodeWriter writer;
         383                 :            :
         384         [ -  + ]:         15 :     if (Py_SIZE(v) == 0) {
         385                 :          0 :         return PyUnicode_FromString("[]");
         386                 :            :     }
         387                 :            :
         388                 :         15 :     i = Py_ReprEnter((PyObject*)v);
         389         [ -  + ]:         15 :     if (i != 0) {
         390         [ #  # ]:          0 :         return i > 0 ? PyUnicode_FromString("[...]") : NULL;
         391                 :            :     }
         392                 :            :
         393                 :         15 :     _PyUnicodeWriter_Init(&writer);
         394                 :         15 :     writer.overallocate = 1;
         395                 :            :     /* "[" + "1" + ", 2" * (len - 1) + "]" */
         396                 :         15 :     writer.min_length = 1 + 1 + (2 + 1) * (Py_SIZE(v) - 1) + 1;
         397                 :            :
         398         [ -  + ]:         15 :     if (_PyUnicodeWriter_WriteChar(&writer, '[') < 0)
         399                 :          0 :         goto error;
         400                 :            :
         401                 :            :     /* Do repr() on each element.  Note that this may mutate the list,
         402                 :            :        so must refetch the list size on each iteration. */
         403         [ +  + ]:         50 :     for (i = 0; i < Py_SIZE(v); ++i) {
         404         [ +  + ]:         35 :         if (i > 0) {
         405         [ -  + ]:         20 :             if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)
         406                 :          0 :                 goto error;
         407                 :            :         }
         408                 :            :
         409                 :         35 :         s = PyObject_Repr(v->ob_item[i]);
         410         [ -  + ]:         35 :         if (s == NULL)
         411                 :          0 :             goto error;
         412                 :            :
         413         [ -  + ]:         35 :         if (_PyUnicodeWriter_WriteStr(&writer, s) < 0) {
         414                 :          0 :             Py_DECREF(s);
         415                 :          0 :             goto error;
         416                 :            :         }
         417                 :         35 :         Py_DECREF(s);
         418                 :            :     }
         419                 :            :
         420                 :         15 :     writer.overallocate = 0;
         421         [ -  + ]:         15 :     if (_PyUnicodeWriter_WriteChar(&writer, ']') < 0)
         422                 :          0 :         goto error;
         423                 :            :
         424                 :         15 :     Py_ReprLeave((PyObject *)v);
         425                 :         15 :     return _PyUnicodeWriter_Finish(&writer);
         426                 :            :
         427                 :          0 : error:
         428                 :          0 :     _PyUnicodeWriter_Dealloc(&writer);
         429                 :          0 :     Py_ReprLeave((PyObject *)v);
         430                 :          0 :     return NULL;
         431                 :            : }
         432                 :            :
         433                 :            : static Py_ssize_t
         434                 :      31136 : list_length(PyListObject *a)
         435                 :            : {
         436                 :      31136 :     return Py_SIZE(a);
         437                 :            : }
         438                 :            :
         439                 :            : static int
         440                 :       8205 : list_contains(PyListObject *a, PyObject *el)
         441                 :            : {
         442                 :            :     PyObject *item;
         443                 :            :     Py_ssize_t i;
         444                 :            :     int cmp;
         445                 :            :
         446   [ +  +  +  + ]:      26404 :     for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i) {
         447                 :      18199 :         item = PyList_GET_ITEM(a, i);
         448                 :      18199 :         Py_INCREF(item);
         449                 :      18199 :         cmp = PyObject_RichCompareBool(item, el, Py_EQ);
         450                 :      18199 :         Py_DECREF(item);
         451                 :            :     }
         452                 :       8205 :     return cmp;
         453                 :            : }
         454                 :            :
         455                 :            : static PyObject *
         456                 :      15915 : list_item(PyListObject *a, Py_ssize_t i)
         457                 :            : {
         458         [ +  + ]:      15915 :     if (!valid_index(i, Py_SIZE(a))) {
         459                 :        673 :         PyErr_SetObject(PyExc_IndexError, &_Py_STR(list_err));
         460                 :        673 :         return NULL;
         461                 :            :     }
         462                 :      15242 :     return Py_NewRef(a->ob_item[i]);
         463                 :            : }
         464                 :            :
         465                 :            : static PyObject *
         466                 :        649 : list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
         467                 :            : {
         468                 :            :     PyListObject *np;
         469                 :            :     PyObject **src, **dest;
         470                 :            :     Py_ssize_t i, len;
         471                 :        649 :     len = ihigh - ilow;
         472         [ -  + ]:        649 :     if (len <= 0) {
         473                 :          0 :         return PyList_New(0);
         474                 :            :     }
         475                 :        649 :     np = (PyListObject *) list_new_prealloc(len);
         476         [ -  + ]:        649 :     if (np == NULL)
         477                 :          0 :         return NULL;
         478                 :            :
         479                 :        649 :     src = a->ob_item + ilow;
         480                 :        649 :     dest = np->ob_item;
         481         [ +  + ]:       1972 :     for (i = 0; i < len; i++) {
         482                 :       1323 :         PyObject *v = src[i];
         483                 :       1323 :         dest[i] = Py_NewRef(v);
         484                 :            :     }
         485                 :        649 :     Py_SET_SIZE(np, len);
         486                 :        649 :     return (PyObject *)np;
         487                 :            : }
         488                 :            :
         489                 :            : PyObject *
         490                 :          0 : PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
         491                 :            : {
         492         [ #  # ]:          0 :     if (!PyList_Check(a)) {
         493                 :          0 :         PyErr_BadInternalCall();
         494                 :          0 :         return NULL;
         495                 :            :     }
         496         [ #  # ]:          0 :     if (ilow < 0) {
         497                 :          0 :         ilow = 0;
         498                 :            :     }
         499         [ #  # ]:          0 :     else if (ilow > Py_SIZE(a)) {
         500                 :          0 :         ilow = Py_SIZE(a);
         501                 :            :     }
         502         [ #  # ]:          0 :     if (ihigh < ilow) {
         503                 :          0 :         ihigh = ilow;
         504                 :            :     }
         505         [ #  # ]:          0 :     else if (ihigh > Py_SIZE(a)) {
         506                 :          0 :         ihigh = Py_SIZE(a);
         507                 :            :     }
         508                 :          0 :     return list_slice((PyListObject *)a, ilow, ihigh);
         509                 :            : }
         510                 :            :
         511                 :            : static PyObject *
         512                 :        404 : list_concat(PyListObject *a, PyObject *bb)
         513                 :            : {
         514                 :            :     Py_ssize_t size;
         515                 :            :     Py_ssize_t i;
         516                 :            :     PyObject **src, **dest;
         517                 :            :     PyListObject *np;
         518         [ -  + ]:        404 :     if (!PyList_Check(bb)) {
         519                 :          0 :         PyErr_Format(PyExc_TypeError,
         520                 :            :                   "can only concatenate list (not \"%.200s\") to list",
         521                 :          0 :                   Py_TYPE(bb)->tp_name);
         522                 :          0 :         return NULL;
         523                 :            :     }
         524                 :            : #define b ((PyListObject *)bb)
         525                 :            :     assert((size_t)Py_SIZE(a) + (size_t)Py_SIZE(b) < PY_SSIZE_T_MAX);
         526                 :        404 :     size = Py_SIZE(a) + Py_SIZE(b);
         527         [ +  + ]:        404 :     if (size == 0) {
         528                 :          1 :         return PyList_New(0);
         529                 :            :     }
         530                 :        403 :     np = (PyListObject *) list_new_prealloc(size);
         531         [ -  + ]:        403 :     if (np == NULL) {
         532                 :          0 :         return NULL;
         533                 :            :     }
         534                 :        403 :     src = a->ob_item;
         535                 :        403 :     dest = np->ob_item;
         536         [ +  + ]:      21491 :     for (i = 0; i < Py_SIZE(a); i++) {
         537                 :      21088 :         PyObject *v = src[i];
         538                 :      21088 :         dest[i] = Py_NewRef(v);
         539                 :            :     }
         540                 :        403 :     src = b->ob_item;
         541                 :        403 :     dest = np->ob_item + Py_SIZE(a);
         542         [ +  + ]:      14916 :     for (i = 0; i < Py_SIZE(b); i++) {
         543                 :      14513 :         PyObject *v = src[i];
         544                 :      14513 :         dest[i] = Py_NewRef(v);
         545                 :            :     }
         546                 :        403 :     Py_SET_SIZE(np, size);
         547                 :        403 :     return (PyObject *)np;
         548                 :            : #undef b
         549                 :            : }
         550                 :            :
         551                 :            : static PyObject *
         552                 :       1145 : list_repeat(PyListObject *a, Py_ssize_t n)
         553                 :            : {
         554                 :       1145 :     const Py_ssize_t input_size = Py_SIZE(a);
         555   [ +  -  +  + ]:       1145 :     if (input_size == 0 || n <= 0)
         556                 :          1 :         return PyList_New(0);
         557                 :            :     assert(n > 0);
         558                 :            :
         559         [ -  + ]:       1144 :     if (input_size > PY_SSIZE_T_MAX / n)
         560                 :          0 :         return PyErr_NoMemory();
         561                 :       1144 :     Py_ssize_t output_size = input_size * n;
         562                 :            :
         563                 :       1144 :     PyListObject *np = (PyListObject *) list_new_prealloc(output_size);
         564         [ -  + ]:       1144 :     if (np == NULL)
         565                 :          0 :         return NULL;
         566                 :            :
         567                 :       1144 :     PyObject **dest = np->ob_item;
         568         [ +  + ]:       1144 :     if (input_size == 1) {
         569                 :        141 :         PyObject *elem = a->ob_item[0];
         570                 :        141 :         _Py_RefcntAdd(elem, n);
         571                 :        141 :         PyObject **dest_end = dest + output_size;
         572         [ +  + ]:        951 :         while (dest < dest_end) {
         573                 :        810 :             *dest++ = elem;
         574                 :            :         }
         575                 :            :     }
         576                 :            :     else {
         577                 :       1003 :         PyObject **src = a->ob_item;
         578                 :       1003 :         PyObject **src_end = src + input_size;
         579         [ +  + ]:       7011 :         while (src < src_end) {
         580                 :       6008 :             _Py_RefcntAdd(*src, n);
         581                 :       6008 :             *dest++ = *src++;
         582                 :            :         }
         583                 :            :
         584                 :       1003 :         _Py_memory_repeat((char *)np->ob_item, sizeof(PyObject *)*output_size,
         585                 :       1003 :                                         sizeof(PyObject *)*input_size);
         586                 :            :     }
         587                 :            :
         588                 :       1144 :     Py_SET_SIZE(np, output_size);
         589                 :       1144 :     return (PyObject *) np;
         590                 :            : }
         591                 :            :
         592                 :            : static int
         593                 :       8728 : _list_clear(PyListObject *a)
         594                 :            : {
         595                 :            :     Py_ssize_t i;
         596                 :       8728 :     PyObject **item = a->ob_item;
         597         [ +  + ]:       8728 :     if (item != NULL) {
         598                 :            :         /* Because XDECREF can recursively invoke operations on
         599                 :            :            this list, we make it empty first. */
         600                 :       8719 :         i = Py_SIZE(a);
         601                 :       8719 :         Py_SET_SIZE(a, 0);
         602                 :       8719 :         a->ob_item = NULL;
         603                 :       8719 :         a->allocated = 0;
         604         [ +  + ]:      17882 :         while (--i >= 0) {
         605                 :       9163 :             Py_XDECREF(item[i]);
         606                 :            :         }
         607                 :       8719 :         PyMem_Free(item);
         608                 :            :     }
         609                 :            :     /* Never fails; the return value can be ignored.
         610                 :            :        Note that there is no guarantee that the list is actually empty
         611                 :            :        at this point, because XDECREF may have populated it again! */
         612                 :       8728 :     return 0;
         613                 :            : }
         614                 :            :
         615                 :            : /* a[ilow:ihigh] = v if v != NULL.
         616                 :            :  * del a[ilow:ihigh] if v == NULL.
         617                 :            :  *
         618                 :            :  * Special speed gimmick:  when v is NULL and ihigh - ilow <= 8, it's
         619                 :            :  * guaranteed the call cannot fail.
         620                 :            :  */
         621                 :            : static int
         622                 :      34317 : list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
         623                 :            : {
         624                 :            :     /* Because [X]DECREF can recursively invoke list operations on
         625                 :            :        this list, we must postpone all [X]DECREF activity until
         626                 :            :        after the list is back in its canonical shape.  Therefore
         627                 :            :        we must allocate an additional array, 'recycle', into which
         628                 :            :        we temporarily copy the items that are deleted from the
         629                 :            :        list. :-( */
         630                 :            :     PyObject *recycle_on_stack[8];
         631                 :      34317 :     PyObject **recycle = recycle_on_stack; /* will allocate more if needed */
         632                 :            :     PyObject **item;
         633                 :      34317 :     PyObject **vitem = NULL;
         634                 :      34317 :     PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */
         635                 :            :     Py_ssize_t n; /* # of elements in replacement list */
         636                 :            :     Py_ssize_t norig; /* # of elements in list getting replaced */
         637                 :            :     Py_ssize_t d; /* Change in size */
         638                 :            :     Py_ssize_t k;
         639                 :            :     size_t s;
         640                 :      34317 :     int result = -1;            /* guilty until proved innocent */
         641                 :            : #define b ((PyListObject *)v)
         642         [ +  + ]:      34317 :     if (v == NULL)
         643                 :      34256 :         n = 0;
         644                 :            :     else {
         645         [ -  + ]:         61 :         if (a == b) {
         646                 :            :             /* Special case "a[i:j] = a" -- copy b first */
         647                 :          0 :             v = list_slice(b, 0, Py_SIZE(b));
         648         [ #  # ]:          0 :             if (v == NULL)
         649                 :          0 :                 return result;
         650                 :          0 :             result = list_ass_slice(a, ilow, ihigh, v);
         651                 :          0 :             Py_DECREF(v);
         652                 :          0 :             return result;
         653                 :            :         }
         654                 :         61 :         v_as_SF = PySequence_Fast(v, "can only assign an iterable");
         655         [ -  + ]:         61 :         if(v_as_SF == NULL)
         656                 :          0 :             goto Error;
         657         [ +  + ]:         61 :         n = PySequence_Fast_GET_SIZE(v_as_SF);
         658         [ +  + ]:         61 :         vitem = PySequence_Fast_ITEMS(v_as_SF);
         659                 :            :     }
         660         [ -  + ]:      34317 :     if (ilow < 0)
         661                 :          0 :         ilow = 0;
         662         [ -  + ]:      34317 :     else if (ilow > Py_SIZE(a))
         663                 :          0 :         ilow = Py_SIZE(a);
         664                 :            :
         665         [ -  + ]:      34317 :     if (ihigh < ilow)
         666                 :          0 :         ihigh = ilow;
         667         [ -  + ]:      34317 :     else if (ihigh > Py_SIZE(a))
         668                 :          0 :         ihigh = Py_SIZE(a);
         669                 :            :
         670                 :      34317 :     norig = ihigh - ilow;
         671                 :            :     assert(norig >= 0);
         672                 :      34317 :     d = n - norig;
         673         [ +  + ]:      34317 :     if (Py_SIZE(a) + d == 0) {
         674                 :       7525 :         Py_XDECREF(v_as_SF);
         675                 :       7525 :         return _list_clear(a);
         676                 :            :     }
         677                 :      26792 :     item = a->ob_item;
         678                 :            :     /* recycle the items that we are about to remove */
         679                 :      26792 :     s = norig * sizeof(PyObject *);
         680                 :            :     /* If norig == 0, item might be NULL, in which case we may not memcpy from it. */
         681         [ +  + ]:      26792 :     if (s) {
         682         [ -  + ]:      26774 :         if (s > sizeof(recycle_on_stack)) {
         683                 :          0 :             recycle = (PyObject **)PyMem_Malloc(s);
         684         [ #  # ]:          0 :             if (recycle == NULL) {
         685                 :          0 :                 PyErr_NoMemory();
         686                 :          0 :                 goto Error;
         687                 :            :             }
         688                 :            :         }
         689                 :      26774 :         memcpy(recycle, &item[ilow], s);
         690                 :            :     }
         691                 :            :
         692         [ +  + ]:      26792 :     if (d < 0) { /* Delete -d items */
         693                 :            :         Py_ssize_t tail;
         694                 :      26735 :         tail = (Py_SIZE(a) - ihigh) * sizeof(PyObject *);
         695                 :      26735 :         memmove(&item[ihigh+d], &item[ihigh], tail);
         696         [ -  + ]:      26735 :         if (list_resize(a, Py_SIZE(a) + d) < 0) {
         697                 :          0 :             memmove(&item[ihigh], &item[ihigh+d], tail);
         698                 :          0 :             memcpy(&item[ilow], recycle, s);
         699                 :          0 :             goto Error;
         700                 :            :         }
         701                 :      26735 :         item = a->ob_item;
         702                 :            :     }
         703         [ +  + ]:         57 :     else if (d > 0) { /* Insert d items */
         704                 :         20 :         k = Py_SIZE(a);
         705         [ -  + ]:         20 :         if (list_resize(a, k+d) < 0)
         706                 :          0 :             goto Error;
         707                 :         20 :         item = a->ob_item;
         708                 :         20 :         memmove(&item[ihigh+d], &item[ihigh],
         709                 :         20 :             (k - ihigh)*sizeof(PyObject *));
         710                 :            :     }
         711         [ +  + ]:      27103 :     for (k = 0; k < n; k++, ilow++) {
         712                 :        311 :         PyObject *w = vitem[k];
         713                 :        311 :         item[ilow] = Py_XNewRef(w);
         714                 :            :     }
         715         [ +  + ]:      53806 :     for (k = norig - 1; k >= 0; --k)
         716                 :      27014 :         Py_XDECREF(recycle[k]);
         717                 :      26792 :     result = 0;
         718                 :      26792 :  Error:
         719         [ -  + ]:      26792 :     if (recycle != recycle_on_stack)
         720                 :          0 :         PyMem_Free(recycle);
         721                 :      26792 :     Py_XDECREF(v_as_SF);
         722                 :      26792 :     return result;
         723                 :            : #undef b
         724                 :            : }
         725                 :            :
         726                 :            : int
         727                 :      24907 : PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
         728                 :            : {
         729         [ -  + ]:      24907 :     if (!PyList_Check(a)) {
         730                 :          0 :         PyErr_BadInternalCall();
         731                 :          0 :         return -1;
         732                 :            :     }
         733                 :      24907 :     return list_ass_slice((PyListObject *)a, ilow, ihigh, v);
         734                 :            : }
         735                 :            :
         736                 :            : static PyObject *
         737                 :          0 : list_inplace_repeat(PyListObject *self, Py_ssize_t n)
         738                 :            : {
         739                 :          0 :     Py_ssize_t input_size = PyList_GET_SIZE(self);
         740   [ #  #  #  # ]:          0 :     if (input_size == 0 || n == 1) {
         741                 :          0 :         return Py_NewRef(self);
         742                 :            :     }
         743                 :            :
         744         [ #  # ]:          0 :     if (n < 1) {
         745                 :          0 :         (void)_list_clear(self);
         746                 :          0 :         return Py_NewRef(self);
         747                 :            :     }
         748                 :            :
         749         [ #  # ]:          0 :     if (input_size > PY_SSIZE_T_MAX / n) {
         750                 :          0 :         return PyErr_NoMemory();
         751                 :            :     }
         752                 :          0 :     Py_ssize_t output_size = input_size * n;
         753                 :            :
         754         [ #  # ]:          0 :     if (list_resize(self, output_size) < 0)
         755                 :          0 :         return NULL;
         756                 :            :
         757                 :          0 :     PyObject **items = self->ob_item;
         758         [ #  # ]:          0 :     for (Py_ssize_t j = 0; j < input_size; j++) {
         759                 :          0 :         _Py_RefcntAdd(items[j], n-1);
         760                 :            :     }
         761                 :          0 :     _Py_memory_repeat((char *)items, sizeof(PyObject *)*output_size,
         762                 :          0 :                       sizeof(PyObject *)*input_size);
         763                 :            :
         764                 :          0 :     return Py_NewRef(self);
         765                 :            : }
         766                 :            :
         767                 :            : static int
         768                 :       8142 : list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)
         769                 :            : {
         770         [ -  + ]:       8142 :     if (!valid_index(i, Py_SIZE(a))) {
         771                 :          0 :         PyErr_SetString(PyExc_IndexError,
         772                 :            :                         "list assignment index out of range");
         773                 :          0 :         return -1;
         774                 :            :     }
         775         [ +  + ]:       8142 :     if (v == NULL)
         776                 :       7850 :         return list_ass_slice(a, i, i+1, v);
         777                 :        292 :     Py_SETREF(a->ob_item[i], Py_NewRef(v));
         778                 :        292 :     return 0;
         779                 :            : }
         780                 :            :
         781                 :            : /*[clinic input]
         782                 :            : list.insert
         783                 :            :
         784                 :            :     index: Py_ssize_t
         785                 :            :     object: object
         786                 :            :     /
         787                 :            :
         788                 :            : Insert object before index.
         789                 :            : [clinic start generated code]*/
         790                 :            :
         791                 :            : static PyObject *
         792                 :        127 : list_insert_impl(PyListObject *self, Py_ssize_t index, PyObject *object)
         793                 :            : /*[clinic end generated code: output=7f35e32f60c8cb78 input=858514cf894c7eab]*/
         794                 :            : {
         795         [ +  - ]:        127 :     if (ins1(self, index, object) == 0)
         796                 :        127 :         Py_RETURN_NONE;
         797                 :          0 :     return NULL;
         798                 :            : }
         799                 :            :
         800                 :            : /*[clinic input]
         801                 :            : list.clear
         802                 :            :
         803                 :            : Remove all items from list.
         804                 :            : [clinic start generated code]*/
         805                 :            :
         806                 :            : static PyObject *
         807                 :          0 : list_clear_impl(PyListObject *self)
         808                 :            : /*[clinic end generated code: output=67a1896c01f74362 input=ca3c1646856742f6]*/
         809                 :            : {
         810                 :          0 :     _list_clear(self);
         811                 :          0 :     Py_RETURN_NONE;
         812                 :            : }
         813                 :            :
         814                 :            : /*[clinic input]
         815                 :            : list.copy
         816                 :            :
         817                 :            : Return a shallow copy of the list.
         818                 :            : [clinic start generated code]*/
         819                 :            :
         820                 :            : static PyObject *
         821                 :          0 : list_copy_impl(PyListObject *self)
         822                 :            : /*[clinic end generated code: output=ec6b72d6209d418e input=6453ab159e84771f]*/
         823                 :            : {
         824                 :          0 :     return list_slice(self, 0, Py_SIZE(self));
         825                 :            : }
         826                 :            :
         827                 :            : /*[clinic input]
         828                 :            : list.append
         829                 :            :
         830                 :            :      object: object
         831                 :            :      /
         832                 :            :
         833                 :            : Append object to the end of the list.
         834                 :            : [clinic start generated code]*/
         835                 :            :
         836                 :            : static PyObject *
         837                 :       7412 : list_append(PyListObject *self, PyObject *object)
         838                 :            : /*[clinic end generated code: output=7c096003a29c0eae input=43a3fe48a7066e91]*/
         839                 :            : {
         840         [ -  + ]:       7412 :     if (_PyList_AppendTakeRef(self, Py_NewRef(object)) < 0) {
         841                 :          0 :         return NULL;
         842                 :            :     }
         843                 :       7412 :     Py_RETURN_NONE;
         844                 :            : }
         845                 :            :
         846                 :            : /*[clinic input]
         847                 :            : list.extend
         848                 :            :
         849                 :            :      iterable: object
         850                 :            :      /
         851                 :            :
         852                 :            : Extend list by appending elements from the iterable.
         853                 :            : [clinic start generated code]*/
         854                 :            :
         855                 :            : static PyObject *
         856                 :      38765 : list_extend(PyListObject *self, PyObject *iterable)
         857                 :            : /*[clinic end generated code: output=630fb3bca0c8e789 input=9ec5ba3a81be3a4d]*/
         858                 :            : {
         859                 :            :     PyObject *it;      /* iter(v) */
         860                 :            :     Py_ssize_t m;                  /* size of self */
         861                 :            :     Py_ssize_t n;                  /* guess for size of iterable */
         862                 :            :     Py_ssize_t i;
         863                 :            :     PyObject *(*iternext)(PyObject *);
         864                 :            :
         865                 :            :     /* Special cases:
         866                 :            :        1) lists and tuples which can use PySequence_Fast ops
         867                 :            :        2) extending self to self requires making a copy first
         868                 :            :     */
         869   [ +  +  +  +  :      38765 :     if (PyList_CheckExact(iterable) || PyTuple_CheckExact(iterable) ||
                       -  + ]
         870                 :            :                 (PyObject *)self == iterable) {
         871                 :            :         PyObject **src, **dest;
         872                 :      18645 :         iterable = PySequence_Fast(iterable, "argument must be iterable");
         873         [ -  + ]:      18645 :         if (!iterable)
         874                 :          0 :             return NULL;
         875         [ +  + ]:      18645 :         n = PySequence_Fast_GET_SIZE(iterable);
         876         [ +  + ]:      18645 :         if (n == 0) {
         877                 :            :             /* short circuit when iterable is empty */
         878                 :        798 :             Py_DECREF(iterable);
         879                 :        798 :             Py_RETURN_NONE;
         880                 :            :         }
         881                 :      17847 :         m = Py_SIZE(self);
         882                 :            :         /* It should not be possible to allocate a list large enough to cause
         883                 :            :         an overflow on any relevant platform */
         884                 :            :         assert(m < PY_SSIZE_T_MAX - n);
         885         [ +  + ]:      17847 :         if (self->ob_item == NULL) {
         886         [ -  + ]:      16952 :             if (list_preallocate_exact(self, n) < 0) {
         887                 :          0 :                 return NULL;
         888                 :            :             }
         889                 :      16952 :             Py_SET_SIZE(self, n);
         890                 :            :         }
         891         [ -  + ]:        895 :         else if (list_resize(self, m + n) < 0) {
         892                 :          0 :             Py_DECREF(iterable);
         893                 :          0 :             return NULL;
         894                 :            :         }
         895                 :            :         /* note that we may still have self == iterable here for the
         896                 :            :          * situation a.extend(a), but the following code works
         897                 :            :          * in that case too.  Just make sure to resize self
         898                 :            :          * before calling PySequence_Fast_ITEMS.
         899                 :            :          */
         900                 :            :         /* populate the end of self with iterable's items */
         901         [ +  + ]:      17847 :         src = PySequence_Fast_ITEMS(iterable);
         902                 :      17847 :         dest = self->ob_item + m;
         903         [ +  + ]:      71912 :         for (i = 0; i < n; i++) {
         904                 :      54065 :             PyObject *o = src[i];
         905                 :      54065 :             dest[i] = Py_NewRef(o);
         906                 :            :         }
         907                 :      17847 :         Py_DECREF(iterable);
         908                 :      17847 :         Py_RETURN_NONE;
         909                 :            :     }
         910                 :            :
         911                 :      20120 :     it = PyObject_GetIter(iterable);
         912         [ -  + ]:      20120 :     if (it == NULL)
         913                 :          0 :         return NULL;
         914                 :      20120 :     iternext = *Py_TYPE(it)->tp_iternext;
         915                 :            :
         916                 :            :     /* Guess a result list size. */
         917                 :      20120 :     n = PyObject_LengthHint(iterable, 8);
         918         [ -  + ]:      20120 :     if (n < 0) {
         919                 :          0 :         Py_DECREF(it);
         920                 :          0 :         return NULL;
         921                 :            :     }
         922                 :      20120 :     m = Py_SIZE(self);
         923         [ +  - ]:      20120 :     if (m > PY_SSIZE_T_MAX - n) {
         924                 :            :         /* m + n overflowed; on the chance that n lied, and there really
         925                 :            :          * is enough room, ignore it.  If n was telling the truth, we'll
         926                 :            :          * eventually run out of memory during the loop.
         927                 :            :          */
         928                 :            :     }
         929         [ +  + ]:      20120 :     else if (self->ob_item == NULL) {
         930   [ +  +  -  + ]:      19955 :         if (n && list_preallocate_exact(self, n) < 0)
         931                 :          0 :             goto error;
         932                 :            :     }
         933                 :            :     else {
         934                 :            :         /* Make room. */
         935         [ -  + ]:        165 :         if (list_resize(self, m + n) < 0)
         936                 :          0 :             goto error;
         937                 :            :         /* Make the list sane again. */
         938                 :        165 :         Py_SET_SIZE(self, m);
         939                 :            :     }
         940                 :            :
         941                 :            :     /* Run iterator to exhaustion. */
         942                 :     290560 :     for (;;) {
         943                 :     310680 :         PyObject *item = iternext(it);
         944         [ +  + ]:     310680 :         if (item == NULL) {
         945         [ -  + ]:      20120 :             if (PyErr_Occurred()) {
         946         [ #  # ]:          0 :                 if (PyErr_ExceptionMatches(PyExc_StopIteration))
         947                 :          0 :                     PyErr_Clear();
         948                 :            :                 else
         949                 :          0 :                     goto error;
         950                 :            :             }
         951                 :      20120 :             break;
         952                 :            :         }
         953         [ +  + ]:     290560 :         if (Py_SIZE(self) < self->allocated) {
         954                 :            :             /* steals ref */
         955                 :     274071 :             PyList_SET_ITEM(self, Py_SIZE(self), item);
         956                 :     274071 :             Py_SET_SIZE(self, Py_SIZE(self) + 1);
         957                 :            :         }
         958                 :            :         else {
         959         [ -  + ]:      16489 :             if (_PyList_AppendTakeRef(self, item) < 0)
         960                 :          0 :                 goto error;
         961                 :            :         }
         962                 :            :     }
         963                 :            :
         964                 :            :     /* Cut back result list if initial guess was too large. */
         965         [ +  + ]:      20120 :     if (Py_SIZE(self) < self->allocated) {
         966         [ -  + ]:       2800 :         if (list_resize(self, Py_SIZE(self)) < 0)
         967                 :          0 :             goto error;
         968                 :            :     }
         969                 :            :
         970                 :      20120 :     Py_DECREF(it);
         971                 :      20120 :     Py_RETURN_NONE;
         972                 :            :
         973                 :          0 :   error:
         974                 :          0 :     Py_DECREF(it);
         975                 :          0 :     return NULL;
         976                 :            : }
         977                 :            :
         978                 :            : PyObject *
         979                 :      23285 : _PyList_Extend(PyListObject *self, PyObject *iterable)
         980                 :            : {
         981                 :      23285 :     return list_extend(self, iterable);
         982                 :            : }
         983                 :            :
         984                 :            : static PyObject *
         985                 :        224 : list_inplace_concat(PyListObject *self, PyObject *other)
         986                 :            : {
         987                 :            :     PyObject *result;
         988                 :            :
         989                 :        224 :     result = list_extend(self, other);
         990         [ -  + ]:        224 :     if (result == NULL)
         991                 :          0 :         return result;
         992                 :        224 :     Py_DECREF(result);
         993                 :        224 :     return Py_NewRef(self);
         994                 :            : }
         995                 :            :
         996                 :            : /*[clinic input]
         997                 :            : list.pop
         998                 :            :
         999                 :            :     index: Py_ssize_t = -1
        1000                 :            :     /
        1001                 :            :
        1002                 :            : Remove and return item at index (default last).
        1003                 :            :
        1004                 :            : Raises IndexError if list is empty or index is out of range.
        1005                 :            : [clinic start generated code]*/
        1006                 :            :
        1007                 :            : static PyObject *
        1008                 :       1537 : list_pop_impl(PyListObject *self, Py_ssize_t index)
        1009                 :            : /*[clinic end generated code: output=6bd69dcb3f17eca8 input=b83675976f329e6f]*/
        1010                 :            : {
        1011                 :            :     PyObject *v;
        1012                 :            :     int status;
        1013                 :            :
        1014         [ +  + ]:       1537 :     if (Py_SIZE(self) == 0) {
        1015                 :            :         /* Special-case most common failure cause */
        1016                 :          6 :         PyErr_SetString(PyExc_IndexError, "pop from empty list");
        1017                 :          6 :         return NULL;
        1018                 :            :     }
        1019         [ +  - ]:       1531 :     if (index < 0)
        1020                 :       1531 :         index += Py_SIZE(self);
        1021         [ -  + ]:       1531 :     if (!valid_index(index, Py_SIZE(self))) {
        1022                 :          0 :         PyErr_SetString(PyExc_IndexError, "pop index out of range");
        1023                 :          0 :         return NULL;
        1024                 :            :     }
        1025                 :            :
        1026                 :       1531 :     PyObject **items = self->ob_item;
        1027                 :       1531 :     v = items[index];
        1028                 :       1531 :     const Py_ssize_t size_after_pop = Py_SIZE(self) - 1;
        1029         [ +  + ]:       1531 :     if (size_after_pop == 0) {
        1030                 :       1168 :         Py_INCREF(v);
        1031                 :       1168 :         status = _list_clear(self);
        1032                 :            :     }
        1033                 :            :     else {
        1034         [ -  + ]:        363 :         if ((size_after_pop - index) > 0) {
        1035                 :          0 :             memmove(&items[index], &items[index+1], (size_after_pop - index) * sizeof(PyObject *));
        1036                 :            :         }
        1037                 :        363 :         status = list_resize(self, size_after_pop);
        1038                 :            :     }
        1039         [ +  - ]:       1531 :     if (status >= 0) {
        1040                 :       1531 :         return v; // and v now owns the reference the list had
        1041                 :            :     }
        1042                 :            :     else {
        1043                 :            :         // list resize failed, need to restore
        1044                 :          0 :         memmove(&items[index+1], &items[index], (size_after_pop - index)* sizeof(PyObject *));
        1045                 :          0 :         items[index] = v;
        1046                 :          0 :         return NULL;
        1047                 :            :     }
        1048                 :            : }
        1049                 :            :
        1050                 :            : /* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
        1051                 :            : static void
        1052                 :       8697 : reverse_slice(PyObject **lo, PyObject **hi)
        1053                 :            : {
        1054                 :            :     assert(lo && hi);
        1055                 :            :
        1056                 :       8697 :     --hi;
        1057         [ +  + ]:      18547 :     while (lo < hi) {
        1058                 :       9850 :         PyObject *t = *lo;
        1059                 :       9850 :         *lo = *hi;
        1060                 :       9850 :         *hi = t;
        1061                 :       9850 :         ++lo;
        1062                 :       9850 :         --hi;
        1063                 :            :     }
        1064                 :       8697 : }
        1065                 :            :
        1066                 :            : /* Lots of code for an adaptive, stable, natural mergesort.  There are many
        1067                 :            :  * pieces to this algorithm; read listsort.txt for overviews and details.
        1068                 :            :  */
        1069                 :            :
        1070                 :            : /* A sortslice contains a pointer to an array of keys and a pointer to
        1071                 :            :  * an array of corresponding values.  In other words, keys[i]
        1072                 :            :  * corresponds with values[i].  If values == NULL, then the keys are
        1073                 :            :  * also the values.
        1074                 :            :  *
        1075                 :            :  * Several convenience routines are provided here, so that keys and
        1076                 :            :  * values are always moved in sync.
        1077                 :            :  */
        1078                 :            :
        1079                 :            : typedef struct {
        1080                 :            :     PyObject **keys;
        1081                 :            :     PyObject **values;
        1082                 :            : } sortslice;
        1083                 :            :
        1084                 :            : Py_LOCAL_INLINE(void)
        1085                 :         31 : sortslice_copy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j)
        1086                 :            : {
        1087                 :         31 :     s1->keys[i] = s2->keys[j];
        1088         [ +  + ]:         31 :     if (s1->values != NULL)
        1089                 :          2 :         s1->values[i] = s2->values[j];
        1090                 :         31 : }
        1091                 :            :
        1092                 :            : Py_LOCAL_INLINE(void)
        1093                 :      11319 : sortslice_copy_incr(sortslice *dst, sortslice *src)
        1094                 :            : {
        1095                 :      11319 :     *dst->keys++ = *src->keys++;
        1096         [ +  + ]:      11319 :     if (dst->values != NULL)
        1097                 :       1046 :         *dst->values++ = *src->values++;
        1098                 :      11319 : }
        1099                 :            :
        1100                 :            : Py_LOCAL_INLINE(void)
        1101                 :      14195 : sortslice_copy_decr(sortslice *dst, sortslice *src)
        1102                 :            : {
        1103                 :      14195 :     *dst->keys-- = *src->keys--;
        1104         [ +  + ]:      14195 :     if (dst->values != NULL)
        1105                 :       1236 :         *dst->values-- = *src->values--;
        1106                 :      14195 : }
        1107                 :            :
        1108                 :            :
        1109                 :            : Py_LOCAL_INLINE(void)
        1110                 :        937 : sortslice_memcpy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j,
        1111                 :            :                  Py_ssize_t n)
        1112                 :            : {
        1113                 :        937 :     memcpy(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n);
        1114         [ +  + ]:        937 :     if (s1->values != NULL)
        1115                 :         54 :         memcpy(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n);
        1116                 :        937 : }
        1117                 :            :
        1118                 :            : Py_LOCAL_INLINE(void)
        1119                 :        586 : sortslice_memmove(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j,
        1120                 :            :                   Py_ssize_t n)
        1121                 :            : {
        1122                 :        586 :     memmove(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n);
        1123         [ +  + ]:        586 :     if (s1->values != NULL)
        1124                 :         34 :         memmove(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n);
        1125                 :        586 : }
        1126                 :            :
        1127                 :            : Py_LOCAL_INLINE(void)
        1128                 :      16952 : sortslice_advance(sortslice *slice, Py_ssize_t n)
        1129                 :            : {
        1130                 :      16952 :     slice->keys += n;
        1131         [ +  + ]:      16952 :     if (slice->values != NULL)
        1132                 :        191 :         slice->values += n;
        1133                 :      16952 : }
        1134                 :            :
        1135                 :            : /* Comparison function: ms->key_compare, which is set at run-time in
        1136                 :            :  * listsort_impl to optimize for various special cases.
        1137                 :            :  * Returns -1 on error, 1 if x < y, 0 if x >= y.
        1138                 :            :  */
        1139                 :            :
        1140                 :            : #define ISLT(X, Y) (*(ms->key_compare))(X, Y, ms)
        1141                 :            :
        1142                 :            : /* Compare X to Y via "<".  Goto "fail" if the comparison raises an
        1143                 :            :    error.  Else "k" is set to true iff X<Y, and an "if (k)" block is
        1144                 :            :    started.  It makes more sense in context <wink>.  X and Y are PyObject*s.
        1145                 :            : */
        1146                 :            : #define IFLT(X, Y) if ((k = ISLT(X, Y)) < 0) goto fail;  \
        1147                 :            :            if (k)
        1148                 :            :
        1149                 :            : /* The maximum number of entries in a MergeState's pending-runs stack.
        1150                 :            :  * For a list with n elements, this needs at most floor(log2(n)) + 1 entries
        1151                 :            :  * even if we didn't force runs to a minimal length.  So the number of bits
        1152                 :            :  * in a Py_ssize_t is plenty large enough for all cases.
        1153                 :            :  */
        1154                 :            : #define MAX_MERGE_PENDING (SIZEOF_SIZE_T * 8)
        1155                 :            :
        1156                 :            : /* When we get into galloping mode, we stay there until both runs win less
        1157                 :            :  * often than MIN_GALLOP consecutive times.  See listsort.txt for more info.
        1158                 :            :  */
        1159                 :            : #define MIN_GALLOP 7
        1160                 :            :
        1161                 :            : /* Avoid malloc for small temp arrays. */
        1162                 :            : #define MERGESTATE_TEMP_SIZE 256
        1163                 :            :
        1164                 :            : /* One MergeState exists on the stack per invocation of mergesort.  It's just
        1165                 :            :  * a convenient way to pass state around among the helper functions.
        1166                 :            :  */
        1167                 :            : struct s_slice {
        1168                 :            :     sortslice base;
        1169                 :            :     Py_ssize_t len;   /* length of run */
        1170                 :            :     int power; /* node "level" for powersort merge strategy */
        1171                 :            : };
        1172                 :            :
        1173                 :            : typedef struct s_MergeState MergeState;
        1174                 :            : struct s_MergeState {
        1175                 :            :     /* This controls when we get *into* galloping mode.  It's initialized
        1176                 :            :      * to MIN_GALLOP.  merge_lo and merge_hi tend to nudge it higher for
        1177                 :            :      * random data, and lower for highly structured data.
        1178                 :            :      */
        1179                 :            :     Py_ssize_t min_gallop;
        1180                 :            :
        1181                 :            :     Py_ssize_t listlen;     /* len(input_list) - read only */
        1182                 :            :     PyObject **basekeys;    /* base address of keys array - read only */
        1183                 :            :
        1184                 :            :     /* 'a' is temp storage to help with merges.  It contains room for
        1185                 :            :      * alloced entries.
        1186                 :            :      */
        1187                 :            :     sortslice a;        /* may point to temparray below */
        1188                 :            :     Py_ssize_t alloced;
        1189                 :            :
        1190                 :            :     /* A stack of n pending runs yet to be merged.  Run #i starts at
        1191                 :            :      * address base[i] and extends for len[i] elements.  It's always
        1192                 :            :      * true (so long as the indices are in bounds) that
        1193                 :            :      *
        1194                 :            :      *     pending[i].base + pending[i].len == pending[i+1].base
        1195                 :            :      *
        1196                 :            :      * so we could cut the storage for this, but it's a minor amount,
        1197                 :            :      * and keeping all the info explicit simplifies the code.
        1198                 :            :      */
        1199                 :            :     int n;
        1200                 :            :     struct s_slice pending[MAX_MERGE_PENDING];
        1201                 :            :
        1202                 :            :     /* 'a' points to this when possible, rather than muck with malloc. */
        1203                 :            :     PyObject *temparray[MERGESTATE_TEMP_SIZE];
        1204                 :            :
        1205                 :            :     /* This is the function we will use to compare two keys,
        1206                 :            :      * even when none of our special cases apply and we have to use
        1207                 :            :      * safe_object_compare. */
        1208                 :            :     int (*key_compare)(PyObject *, PyObject *, MergeState *);
        1209                 :            :
        1210                 :            :     /* This function is used by unsafe_object_compare to optimize comparisons
        1211                 :            :      * when we know our list is type-homogeneous but we can't assume anything else.
        1212                 :            :      * In the pre-sort check it is set equal to Py_TYPE(key)->tp_richcompare */
        1213                 :            :     PyObject *(*key_richcompare)(PyObject *, PyObject *, int);
        1214                 :            :
        1215                 :            :     /* This function is used by unsafe_tuple_compare to compare the first elements
        1216                 :            :      * of tuples. It may be set to safe_object_compare, but the idea is that hopefully
        1217                 :            :      * we can assume more, and use one of the special-case compares. */
        1218                 :            :     int (*tuple_elem_compare)(PyObject *, PyObject *, MergeState *);
        1219                 :            : };
        1220                 :            :
        1221                 :            : /* binarysort is the best method for sorting small arrays: it does
        1222                 :            :    few compares, but can do data movement quadratic in the number of
        1223                 :            :    elements.
        1224                 :            :    [lo, hi) is a contiguous slice of a list, and is sorted via
        1225                 :            :    binary insertion.  This sort is stable.
        1226                 :            :    On entry, must have lo <= start <= hi, and that [lo, start) is already
        1227                 :            :    sorted (pass start == lo if you don't know!).
        1228                 :            :    If islt() complains return -1, else 0.
        1229                 :            :    Even in case of error, the output slice will be some permutation of
        1230                 :            :    the input (nothing is lost or duplicated).
        1231                 :            : */
        1232                 :            : static int
        1233                 :      10186 : binarysort(MergeState *ms, sortslice lo, PyObject **hi, PyObject **start)
        1234                 :            : {
        1235                 :            :     Py_ssize_t k;
        1236                 :            :     PyObject **l, **p, **r;
        1237                 :            :     PyObject *pivot;
        1238                 :            :
        1239                 :            :     assert(lo.keys <= start && start <= hi);
        1240                 :            :     /* assert [lo, start) is sorted */
        1241         [ -  + ]:      10186 :     if (lo.keys == start)
        1242                 :          0 :         ++start;
        1243         [ +  + ]:      87242 :     for (; start < hi; ++start) {
        1244                 :            :         /* set l to where *start belongs */
        1245                 :      77056 :         l = lo.keys;
        1246                 :      77056 :         r = start;
        1247                 :      77056 :         pivot = *r;
        1248                 :            :         /* Invariants:
        1249                 :            :          * pivot >= all in [lo, l).
        1250                 :            :          * pivot  < all in [r, start).
        1251                 :            :          * The second is vacuously true at the start.
        1252                 :            :          */
        1253                 :            :         assert(l < r);
        1254                 :            :         do {
        1255                 :     259638 :             p = l + ((r - l) >> 1);
        1256   [ -  +  +  + ]:     259638 :             IFLT(pivot, *p)
        1257                 :     144463 :                 r = p;
        1258                 :            :             else
        1259                 :     115175 :                 l = p+1;
        1260         [ +  + ]:     259638 :         } while (l < r);
        1261                 :            :         assert(l == r);
        1262                 :            :         /* The invariants still hold, so pivot >= all in [lo, l) and
        1263                 :            :            pivot < all in [l, start), so pivot belongs at l.  Note
        1264                 :            :            that if there are elements equal to pivot, l points to the
        1265                 :            :            first slot after them -- that's why this sort is stable.
        1266                 :            :            Slide over to make room.
        1267                 :            :            Caution: using memmove is much slower under MSVC 5;
        1268                 :            :            we're not usually moving many slots. */
        1269         [ +  + ]:     555514 :         for (p = start; p > l; --p)
        1270                 :     478458 :             *p = *(p-1);
        1271                 :      77056 :         *l = pivot;
        1272         [ +  + ]:      77056 :         if (lo.values != NULL) {
        1273                 :        960 :             Py_ssize_t offset = lo.values - lo.keys;
        1274                 :        960 :             p = start + offset;
        1275                 :        960 :             pivot = *p;
        1276                 :        960 :             l += offset;
        1277         [ +  + ]:      14665 :             for (p = start + offset; p > l; --p)
        1278                 :      13705 :                 *p = *(p-1);
        1279                 :        960 :             *l = pivot;
        1280                 :            :         }
        1281                 :            :     }
        1282                 :      10186 :     return 0;
        1283                 :            :
        1284                 :          0 :  fail:
        1285                 :          0 :     return -1;
        1286                 :            : }
        1287                 :            :
        1288                 :            : /*
        1289                 :            : Return the length of the run beginning at lo, in the slice [lo, hi).  lo < hi
        1290                 :            : is required on entry.  "A run" is the longest ascending sequence, with
        1291                 :            :
        1292                 :            :     lo[0] <= lo[1] <= lo[2] <= ...
        1293                 :            :
        1294                 :            : or the longest descending sequence, with
        1295                 :            :
        1296                 :            :     lo[0] > lo[1] > lo[2] > ...
        1297                 :            :
        1298                 :            : Boolean *descending is set to 0 in the former case, or to 1 in the latter.
        1299                 :            : For its intended use in a stable mergesort, the strictness of the defn of
        1300                 :            : "descending" is needed so that the caller can safely reverse a descending
        1301                 :            : sequence without violating stability (strict > ensures there are no equal
        1302                 :            : elements to get out of order).
        1303                 :            :
        1304                 :            : Returns -1 in case of error.
        1305                 :            : */
        1306                 :            : static Py_ssize_t
        1307                 :      14549 : count_run(MergeState *ms, PyObject **lo, PyObject **hi, int *descending)
        1308                 :            : {
        1309                 :            :     Py_ssize_t k;
        1310                 :            :     Py_ssize_t n;
        1311                 :            :
        1312                 :            :     assert(lo < hi);
        1313                 :      14549 :     *descending = 0;
        1314                 :      14549 :     ++lo;
        1315         [ +  + ]:      14549 :     if (lo == hi)
        1316                 :          2 :         return 1;
        1317                 :            :
        1318                 :      14547 :     n = 2;
        1319   [ -  +  +  + ]:      14547 :     IFLT(*lo, *(lo-1)) {
        1320                 :       8646 :         *descending = 1;
        1321         [ +  + ]:      12939 :         for (lo = lo+1; lo < hi; ++lo, ++n) {
        1322   [ -  +  +  + ]:      10088 :             IFLT(*lo, *(lo-1))
        1323                 :            :                 ;
        1324                 :            :             else
        1325                 :       5795 :                 break;
        1326                 :            :         }
        1327                 :            :     }
        1328                 :            :     else {
        1329         [ +  + ]:      10097 :         for (lo = lo+1; lo < hi; ++lo, ++n) {
        1330   [ -  +  +  + ]:       8587 :             IFLT(*lo, *(lo-1))
        1331                 :       4391 :                 break;
        1332                 :            :         }
        1333                 :            :     }
        1334                 :            :
        1335                 :      14547 :     return n;
        1336                 :          0 : fail:
        1337                 :          0 :     return -1;
        1338                 :            : }
        1339                 :            :
        1340                 :            : /*
        1341                 :            : Locate the proper position of key in a sorted vector; if the vector contains
        1342                 :            : an element equal to key, return the position immediately to the left of
        1343                 :            : the leftmost equal element.  [gallop_right() does the same except returns
        1344                 :            : the position to the right of the rightmost equal element (if any).]
        1345                 :            :
        1346                 :            : "a" is a sorted vector with n elements, starting at a[0].  n must be > 0.
        1347                 :            :
        1348                 :            : "hint" is an index at which to begin the search, 0 <= hint < n.  The closer
        1349                 :            : hint is to the final result, the faster this runs.
        1350                 :            :
        1351                 :            : The return value is the int k in 0..n such that
        1352                 :            :
        1353                 :            :     a[k-1] < key <= a[k]
        1354                 :            :
        1355                 :            : pretending that *(a-1) is minus infinity and a[n] is plus infinity.  IOW,
        1356                 :            : key belongs at index k; or, IOW, the first k elements of a should precede
        1357                 :            : key, and the last n-k should follow key.
        1358                 :            :
        1359                 :            : Returns -1 on error.  See listsort.txt for info on the method.
        1360                 :            : */
        1361                 :            : static Py_ssize_t
        1362                 :        961 : gallop_left(MergeState *ms, PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
        1363                 :            : {
        1364                 :            :     Py_ssize_t ofs;
        1365                 :            :     Py_ssize_t lastofs;
        1366                 :            :     Py_ssize_t k;
        1367                 :            :
        1368                 :            :     assert(key && a && n > 0 && hint >= 0 && hint < n);
        1369                 :            :
        1370                 :        961 :     a += hint;
        1371                 :        961 :     lastofs = 0;
        1372                 :        961 :     ofs = 1;
        1373   [ -  +  +  + ]:        961 :     IFLT(*a, key) {
        1374                 :            :         /* a[hint] < key -- gallop right, until
        1375                 :            :          * a[hint + lastofs] < key <= a[hint + ofs]
        1376                 :            :          */
        1377                 :        606 :         const Py_ssize_t maxofs = n - hint;             /* &a[n-1] is highest */
        1378         [ +  + ]:       1039 :         while (ofs < maxofs) {
        1379   [ -  +  +  + ]:        721 :             IFLT(a[ofs], key) {
        1380                 :        433 :                 lastofs = ofs;
        1381                 :            :                 assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
        1382                 :        433 :                 ofs = (ofs << 1) + 1;
        1383                 :            :             }
        1384                 :            :             else                /* key <= a[hint + ofs] */
        1385                 :        288 :                 break;
        1386                 :            :         }
        1387         [ +  + ]:        606 :         if (ofs > maxofs)
        1388                 :         15 :             ofs = maxofs;
        1389                 :            :         /* Translate back to offsets relative to &a[0]. */
        1390                 :        606 :         lastofs += hint;
        1391                 :        606 :         ofs += hint;
        1392                 :            :     }
        1393                 :            :     else {
        1394                 :            :         /* key <= a[hint] -- gallop left, until
        1395                 :            :          * a[hint - ofs] < key <= a[hint - lastofs]
        1396                 :            :          */
        1397                 :        355 :         const Py_ssize_t maxofs = hint + 1;             /* &a[0] is lowest */
        1398         [ +  + ]:        864 :         while (ofs < maxofs) {
        1399   [ -  +  +  + ]:        777 :             IFLT(*(a-ofs), key)
        1400                 :        268 :                 break;
        1401                 :            :             /* key <= a[hint - ofs] */
        1402                 :        509 :             lastofs = ofs;
        1403                 :            :             assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
        1404                 :        509 :             ofs = (ofs << 1) + 1;
        1405                 :            :         }
        1406         [ +  + ]:        355 :         if (ofs > maxofs)
        1407                 :         28 :             ofs = maxofs;
        1408                 :            :         /* Translate back to positive offsets relative to &a[0]. */
        1409                 :        355 :         k = lastofs;
        1410                 :        355 :         lastofs = hint - ofs;
        1411                 :        355 :         ofs = hint - k;
        1412                 :            :     }
        1413                 :        961 :     a -= hint;
        1414                 :            :
        1415                 :            :     assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
        1416                 :            :     /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
        1417                 :            :      * right of lastofs but no farther right than ofs.  Do a binary
        1418                 :            :      * search, with invariant a[lastofs-1] < key <= a[ofs].
        1419                 :            :      */
        1420                 :        961 :     ++lastofs;
        1421         [ +  + ]:       1835 :     while (lastofs < ofs) {
        1422                 :        874 :         Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);
        1423                 :            :
        1424   [ -  +  +  + ]:        874 :         IFLT(a[m], key)
        1425                 :        493 :             lastofs = m+1;              /* a[m] < key */
        1426                 :            :         else
        1427                 :        381 :             ofs = m;                    /* key <= a[m] */
        1428                 :            :     }
        1429                 :            :     assert(lastofs == ofs);             /* so a[ofs-1] < key <= a[ofs] */
        1430                 :        961 :     return ofs;
        1431                 :            :
        1432                 :          0 : fail:
        1433                 :          0 :     return -1;
        1434                 :            : }
        1435                 :            :
        1436                 :            : /*
        1437                 :            : Exactly like gallop_left(), except that if key already exists in a[0:n],
        1438                 :            : finds the position immediately to the right of the rightmost equal value.
        1439                 :            :
        1440                 :            : The return value is the int k in 0..n such that
        1441                 :            :
        1442                 :            :     a[k-1] <= key < a[k]
        1443                 :            :
        1444                 :            : or -1 if error.
        1445                 :            :
        1446                 :            : The code duplication is massive, but this is enough different given that
        1447                 :            : we're sticking to "<" comparisons that it's much harder to follow if
        1448                 :            : written as one routine with yet another "left or right?" flag.
        1449                 :            : */
        1450                 :            : static Py_ssize_t
        1451                 :       1005 : gallop_right(MergeState *ms, PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
        1452                 :            : {
        1453                 :            :     Py_ssize_t ofs;
        1454                 :            :     Py_ssize_t lastofs;
        1455                 :            :     Py_ssize_t k;
        1456                 :            :
        1457                 :            :     assert(key && a && n > 0 && hint >= 0 && hint < n);
        1458                 :            :
        1459                 :       1005 :     a += hint;
        1460                 :       1005 :     lastofs = 0;
        1461                 :       1005 :     ofs = 1;
        1462   [ -  +  +  + ]:       1005 :     IFLT(key, *a) {
        1463                 :            :         /* key < a[hint] -- gallop left, until
        1464                 :            :          * a[hint - ofs] <= key < a[hint - lastofs]
        1465                 :            :          */
        1466                 :        637 :         const Py_ssize_t maxofs = hint + 1;             /* &a[0] is lowest */
        1467         [ +  + ]:       1186 :         while (ofs < maxofs) {
        1468   [ -  +  +  + ]:        760 :             IFLT(key, *(a-ofs)) {
        1469                 :        549 :                 lastofs = ofs;
        1470                 :            :                 assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
        1471                 :        549 :                 ofs = (ofs << 1) + 1;
        1472                 :            :             }
        1473                 :            :             else                /* a[hint - ofs] <= key */
        1474                 :        211 :                 break;
        1475                 :            :         }
        1476         [ +  + ]:        637 :         if (ofs > maxofs)
        1477                 :         11 :             ofs = maxofs;
        1478                 :            :         /* Translate back to positive offsets relative to &a[0]. */
        1479                 :        637 :         k = lastofs;
        1480                 :        637 :         lastofs = hint - ofs;
        1481                 :        637 :         ofs = hint - k;
        1482                 :            :     }
        1483                 :            :     else {
        1484                 :            :         /* a[hint] <= key -- gallop right, until
        1485                 :            :          * a[hint + lastofs] <= key < a[hint + ofs]
        1486                 :            :         */
        1487                 :        368 :         const Py_ssize_t maxofs = n - hint;             /* &a[n-1] is highest */
        1488         [ +  + ]:        969 :         while (ofs < maxofs) {
        1489   [ -  +  +  + ]:        892 :             IFLT(key, a[ofs])
        1490                 :        291 :                 break;
        1491                 :            :             /* a[hint + ofs] <= key */
        1492                 :        601 :             lastofs = ofs;
        1493                 :            :             assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
        1494                 :        601 :             ofs = (ofs << 1) + 1;
        1495                 :            :         }
        1496         [ +  + ]:        368 :         if (ofs > maxofs)
        1497                 :          8 :             ofs = maxofs;
        1498                 :            :         /* Translate back to offsets relative to &a[0]. */
        1499                 :        368 :         lastofs += hint;
        1500                 :        368 :         ofs += hint;
        1501                 :            :     }
        1502                 :       1005 :     a -= hint;
        1503                 :            :
        1504                 :            :     assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
        1505                 :            :     /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
        1506                 :            :      * right of lastofs but no farther right than ofs.  Do a binary
        1507                 :            :      * search, with invariant a[lastofs-1] <= key < a[ofs].
        1508                 :            :      */
        1509                 :       1005 :     ++lastofs;
        1510         [ +  + ]:       2123 :     while (lastofs < ofs) {
        1511                 :       1118 :         Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);
        1512                 :            :
        1513   [ -  +  +  + ]:       1118 :         IFLT(key, a[m])
        1514                 :        628 :             ofs = m;                    /* key < a[m] */
        1515                 :            :         else
        1516                 :        490 :             lastofs = m+1;              /* a[m] <= key */
        1517                 :            :     }
        1518                 :            :     assert(lastofs == ofs);             /* so a[ofs-1] <= key < a[ofs] */
        1519                 :       1005 :     return ofs;
        1520                 :            :
        1521                 :          0 : fail:
        1522                 :          0 :     return -1;
        1523                 :            : }
        1524                 :            :
        1525                 :            : /* Conceptually a MergeState's constructor. */
        1526                 :            : static void
        1527                 :      17202 : merge_init(MergeState *ms, Py_ssize_t list_size, int has_keyfunc,
        1528                 :            :            sortslice *lo)
        1529                 :            : {
        1530                 :            :     assert(ms != NULL);
        1531         [ +  + ]:      17202 :     if (has_keyfunc) {
        1532                 :            :         /* The temporary space for merging will need at most half the list
        1533                 :            :          * size rounded up.  Use the minimum possible space so we can use the
        1534                 :            :          * rest of temparray for other things.  In particular, if there is
        1535                 :            :          * enough extra space, listsort() will use it to store the keys.
        1536                 :            :          */
        1537                 :         27 :         ms->alloced = (list_size + 1) / 2;
        1538                 :            :
        1539                 :            :         /* ms->alloced describes how many keys will be stored at
        1540                 :            :            ms->temparray, but we also need to store the values.  Hence,
        1541                 :            :            ms->alloced is capped at half of MERGESTATE_TEMP_SIZE. */
        1542         [ +  + ]:         27 :         if (MERGESTATE_TEMP_SIZE / 2 < ms->alloced)
        1543                 :          2 :             ms->alloced = MERGESTATE_TEMP_SIZE / 2;
        1544                 :         27 :         ms->a.values = &ms->temparray[ms->alloced];
        1545                 :            :     }
        1546                 :            :     else {
        1547                 :      17175 :         ms->alloced = MERGESTATE_TEMP_SIZE;
        1548                 :      17175 :         ms->a.values = NULL;
        1549                 :            :     }
        1550                 :      17202 :     ms->a.keys = ms->temparray;
        1551                 :      17202 :     ms->n = 0;
        1552                 :      17202 :     ms->min_gallop = MIN_GALLOP;
        1553                 :      17202 :     ms->listlen = list_size;
        1554                 :      17202 :     ms->basekeys = lo->keys;
        1555                 :      17202 : }
        1556                 :            :
        1557                 :            : /* Free all the temp memory owned by the MergeState.  This must be called
        1558                 :            :  * when you're done with a MergeState, and may be called before then if
        1559                 :            :  * you want to free the temp memory early.
        1560                 :            :  */
        1561                 :            : static void
        1562                 :      17206 : merge_freemem(MergeState *ms)
        1563                 :            : {
        1564                 :            :     assert(ms != NULL);
        1565         [ +  + ]:      17206 :     if (ms->a.keys != ms->temparray) {
        1566                 :          4 :         PyMem_Free(ms->a.keys);
        1567                 :          4 :         ms->a.keys = NULL;
        1568                 :            :     }
        1569                 :      17206 : }
        1570                 :            :
        1571                 :            : /* Ensure enough temp memory for 'need' array slots is available.
        1572                 :            :  * Returns 0 on success and -1 if the memory can't be gotten.
        1573                 :            :  */
        1574                 :            : static int
        1575                 :          4 : merge_getmem(MergeState *ms, Py_ssize_t need)
        1576                 :            : {
        1577                 :            :     int multiplier;
        1578                 :            :
        1579                 :            :     assert(ms != NULL);
        1580         [ -  + ]:          4 :     if (need <= ms->alloced)
        1581                 :          0 :         return 0;
        1582                 :            :
        1583         [ +  - ]:          4 :     multiplier = ms->a.values != NULL ? 2 : 1;
        1584                 :            :
        1585                 :            :     /* Don't realloc!  That can cost cycles to copy the old data, but
        1586                 :            :      * we don't care what's in the block.
        1587                 :            :      */
        1588                 :          4 :     merge_freemem(ms);
        1589         [ -  + ]:          4 :     if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject *) / multiplier) {
        1590                 :          0 :         PyErr_NoMemory();
        1591                 :          0 :         return -1;
        1592                 :            :     }
        1593                 :          4 :     ms->a.keys = (PyObject **)PyMem_Malloc(multiplier * need
        1594                 :            :                                           * sizeof(PyObject *));
        1595         [ +  - ]:          4 :     if (ms->a.keys != NULL) {
        1596                 :          4 :         ms->alloced = need;
        1597         [ +  - ]:          4 :         if (ms->a.values != NULL)
        1598                 :          4 :             ms->a.values = &ms->a.keys[need];
        1599                 :          4 :         return 0;
        1600                 :            :     }
        1601                 :          0 :     PyErr_NoMemory();
        1602                 :          0 :     return -1;
        1603                 :            : }
        1604                 :            : #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 :   \
        1605                 :            :                                 merge_getmem(MS, NEED))
        1606                 :            :
        1607                 :            : /* Merge the na elements starting at ssa with the nb elements starting at
        1608                 :            :  * ssb.keys = ssa.keys + na in a stable way, in-place.  na and nb must be > 0.
        1609                 :            :  * Must also have that ssa.keys[na-1] belongs at the end of the merge, and
        1610                 :            :  * should have na <= nb.  See listsort.txt for more info.  Return 0 if
        1611                 :            :  * successful, -1 if error.
        1612                 :            :  */
        1613                 :            : static Py_ssize_t
        1614                 :        180 : merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na,
        1615                 :            :          sortslice ssb, Py_ssize_t nb)
        1616                 :            : {
        1617                 :            :     Py_ssize_t k;
        1618                 :            :     sortslice dest;
        1619                 :        180 :     int result = -1;            /* guilty until proved innocent */
        1620                 :            :     Py_ssize_t min_gallop;
        1621                 :            :
        1622                 :            :     assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
        1623                 :            :     assert(ssa.keys + na == ssb.keys);
        1624   [ +  +  -  + ]:        180 :     if (MERGE_GETMEM(ms, na) < 0)
        1625                 :          0 :         return -1;
        1626                 :        180 :     sortslice_memcpy(&ms->a, 0, &ssa, 0, na);
        1627                 :        180 :     dest = ssa;
        1628                 :        180 :     ssa = ms->a;
        1629                 :            :
        1630                 :        180 :     sortslice_copy_incr(&dest, &ssb);
        1631                 :        180 :     --nb;
        1632         [ -  + ]:        180 :     if (nb == 0)
        1633                 :          0 :         goto Succeed;
        1634         [ -  + ]:        180 :     if (na == 1)
        1635                 :          0 :         goto CopyB;
        1636                 :            :
        1637                 :        180 :     min_gallop = ms->min_gallop;
        1638                 :        283 :     for (;;) {
        1639                 :        463 :         Py_ssize_t acount = 0;          /* # of times A won in a row */
        1640                 :        463 :         Py_ssize_t bcount = 0;          /* # of times B won in a row */
        1641                 :            :
        1642                 :            :         /* Do the straightforward thing until (if ever) one run
        1643                 :            :          * appears to win consistently.
        1644                 :            :          */
        1645                 :            :         for (;;) {
        1646                 :       9949 :             assert(na > 1 && nb > 0);
        1647                 :      10412 :             k = ISLT(ssb.keys[0], ssa.keys[0]);
        1648         [ +  + ]:      10412 :             if (k) {
        1649         [ -  + ]:       5820 :                 if (k < 0)
        1650                 :          0 :                     goto Fail;
        1651                 :       5820 :                 sortslice_copy_incr(&dest, &ssb);
        1652                 :       5820 :                 ++bcount;
        1653                 :       5820 :                 acount = 0;
        1654                 :       5820 :                 --nb;
        1655         [ +  + ]:       5820 :                 if (nb == 0)
        1656                 :        146 :                     goto Succeed;
        1657         [ +  + ]:       5674 :                 if (bcount >= min_gallop)
        1658                 :        209 :                     break;
        1659                 :            :             }
        1660                 :            :             else {
        1661                 :       4592 :                 sortslice_copy_incr(&dest, &ssa);
        1662                 :       4592 :                 ++acount;
        1663                 :       4592 :                 bcount = 0;
        1664                 :       4592 :                 --na;
        1665         [ +  + ]:       4592 :                 if (na == 1)
        1666                 :         15 :                     goto CopyB;
        1667         [ +  + ]:       4577 :                 if (acount >= min_gallop)
        1668                 :         93 :                     break;
        1669                 :            :             }
        1670                 :            :         }
        1671                 :            :
        1672                 :            :         /* One run is winning so consistently that galloping may
        1673                 :            :          * be a huge win.  So try that, and continue galloping until
        1674                 :            :          * (if ever) neither run appears to be winning consistently
        1675                 :            :          * anymore.
        1676                 :            :          */
        1677                 :        302 :         ++min_gallop;
        1678                 :            :         do {
        1679                 :            :             assert(na > 1 && nb > 0);
        1680                 :        374 :             min_gallop -= min_gallop > 1;
        1681                 :        374 :             ms->min_gallop = min_gallop;
        1682                 :        374 :             k = gallop_right(ms, ssb.keys[0], ssa.keys, na, 0);
        1683                 :        374 :             acount = k;
        1684         [ +  + ]:        374 :             if (k) {
        1685         [ -  + ]:        171 :                 if (k < 0)
        1686                 :          0 :                     goto Fail;
        1687                 :        171 :                 sortslice_memcpy(&dest, 0, &ssa, 0, k);
        1688                 :        171 :                 sortslice_advance(&dest, k);
        1689                 :        171 :                 sortslice_advance(&ssa, k);
        1690                 :        171 :                 na -= k;
        1691         [ +  + ]:        171 :                 if (na == 1)
        1692                 :          2 :                     goto CopyB;
        1693                 :            :                 /* na==0 is impossible now if the comparison
        1694                 :            :                  * function is consistent, but we can't assume
        1695                 :            :                  * that it is.
        1696                 :            :                  */
        1697         [ -  + ]:        169 :                 if (na == 0)
        1698                 :          0 :                     goto Succeed;
        1699                 :            :             }
        1700                 :        372 :             sortslice_copy_incr(&dest, &ssb);
        1701                 :        372 :             --nb;
        1702         [ +  + ]:        372 :             if (nb == 0)
        1703                 :          9 :                 goto Succeed;
        1704                 :            :
        1705                 :        363 :             k = gallop_left(ms, ssa.keys[0], ssb.keys, nb, 0);
        1706                 :        363 :             bcount = k;
        1707         [ +  + ]:        363 :             if (k) {
        1708         [ -  + ]:        304 :                 if (k < 0)
        1709                 :          0 :                     goto Fail;
        1710                 :        304 :                 sortslice_memmove(&dest, 0, &ssb, 0, k);
        1711                 :        304 :                 sortslice_advance(&dest, k);
        1712                 :        304 :                 sortslice_advance(&ssb, k);
        1713                 :        304 :                 nb -= k;
        1714         [ +  + ]:        304 :                 if (nb == 0)
        1715                 :          8 :                     goto Succeed;
        1716                 :            :             }
        1717                 :        355 :             sortslice_copy_incr(&dest, &ssa);
        1718                 :        355 :             --na;
        1719         [ -  + ]:        355 :             if (na == 1)
        1720                 :          0 :                 goto CopyB;
        1721   [ +  +  +  + ]:        355 :         } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
        1722                 :        283 :         ++min_gallop;           /* penalize it for leaving galloping mode */
        1723                 :        283 :         ms->min_gallop = min_gallop;
        1724                 :            :     }
        1725                 :        163 : Succeed:
        1726                 :        163 :     result = 0;
        1727                 :        163 : Fail:
        1728         [ +  - ]:        163 :     if (na)
        1729                 :        163 :         sortslice_memcpy(&dest, 0, &ssa, 0, na);
        1730                 :        163 :     return result;
        1731                 :         17 : CopyB:
        1732                 :            :     assert(na == 1 && nb > 0);
        1733                 :            :     /* The last element of ssa belongs at the end of the merge. */
        1734                 :         17 :     sortslice_memmove(&dest, 0, &ssb, 0, nb);
        1735                 :         17 :     sortslice_copy(&dest, nb, &ssa, 0);
        1736                 :         17 :     return 0;
        1737                 :            : }
        1738                 :            :
        1739                 :            : /* Merge the na elements starting at pa with the nb elements starting at
        1740                 :            :  * ssb.keys = ssa.keys + na in a stable way, in-place.  na and nb must be > 0.
        1741                 :            :  * Must also have that ssa.keys[na-1] belongs at the end of the merge, and
        1742                 :            :  * should have na >= nb.  See listsort.txt for more info.  Return 0 if
        1743                 :            :  * successful, -1 if error.
        1744                 :            :  */
        1745                 :            : static Py_ssize_t
        1746                 :        131 : merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na,
        1747                 :            :          sortslice ssb, Py_ssize_t nb)
        1748                 :            : {
        1749                 :            :     Py_ssize_t k;
        1750                 :            :     sortslice dest, basea, baseb;
        1751                 :        131 :     int result = -1;            /* guilty until proved innocent */
        1752                 :            :     Py_ssize_t min_gallop;
        1753                 :            :
        1754                 :            :     assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
        1755                 :            :     assert(ssa.keys + na == ssb.keys);
        1756   [ +  +  -  + ]:        131 :     if (MERGE_GETMEM(ms, nb) < 0)
        1757                 :          0 :         return -1;
        1758                 :        131 :     dest = ssb;
        1759                 :        131 :     sortslice_advance(&dest, nb-1);
        1760                 :        131 :     sortslice_memcpy(&ms->a, 0, &ssb, 0, nb);
        1761                 :        131 :     basea = ssa;
        1762                 :        131 :     baseb = ms->a;
        1763                 :        131 :     ssb.keys = ms->a.keys + nb - 1;
        1764         [ +  + ]:        131 :     if (ssb.values != NULL)
        1765                 :          8 :         ssb.values = ms->a.values + nb - 1;
        1766                 :        131 :     sortslice_advance(&ssa, na - 1);
        1767                 :            :
        1768                 :        131 :     sortslice_copy_decr(&dest, &ssa);
        1769                 :        131 :     --na;
        1770         [ -  + ]:        131 :     if (na == 0)
        1771                 :          0 :         goto Succeed;
        1772         [ +  + ]:        131 :     if (nb == 1)
        1773                 :          2 :         goto CopyA;
        1774                 :            :
        1775                 :        129 :     min_gallop = ms->min_gallop;
        1776                 :        148 :     for (;;) {
        1777                 :        277 :         Py_ssize_t acount = 0;          /* # of times A won in a row */
        1778                 :        277 :         Py_ssize_t bcount = 0;          /* # of times B won in a row */
        1779                 :            :
        1780                 :            :         /* Do the straightforward thing until (if ever) one run
        1781                 :            :          * appears to win consistently.
        1782                 :            :          */
        1783                 :            :         for (;;) {
        1784                 :      13215 :             assert(na > 0 && nb > 1);
        1785                 :      13492 :             k = ISLT(ssb.keys[0], ssa.keys[0]);
        1786         [ +  + ]:      13492 :             if (k) {
        1787         [ -  + ]:       8074 :                 if (k < 0)
        1788                 :          0 :                     goto Fail;
        1789                 :       8074 :                 sortslice_copy_decr(&dest, &ssa);
        1790                 :       8074 :                 ++acount;
        1791                 :       8074 :                 bcount = 0;
        1792                 :       8074 :                 --na;
        1793         [ +  + ]:       8074 :                 if (na == 0)
        1794                 :         81 :                     goto Succeed;
        1795         [ +  + ]:       7993 :                 if (acount >= min_gallop)
        1796                 :        155 :                     break;
        1797                 :            :             }
        1798                 :            :             else {
        1799                 :       5418 :                 sortslice_copy_decr(&dest, &ssb);
        1800                 :       5418 :                 ++bcount;
        1801                 :       5418 :                 acount = 0;
        1802                 :       5418 :                 --nb;
        1803         [ +  + ]:       5418 :                 if (nb == 1)
        1804                 :         10 :                     goto CopyA;
        1805         [ +  + ]:       5408 :                 if (bcount >= min_gallop)
        1806                 :         31 :                     break;
        1807                 :            :             }
        1808                 :            :         }
        1809                 :            :
        1810                 :            :         /* One run is winning so consistently that galloping may
        1811                 :            :          * be a huge win.  So try that, and continue galloping until
        1812                 :            :          * (if ever) neither run appears to be winning consistently
        1813                 :            :          * anymore.
        1814                 :            :          */
        1815                 :        186 :         ++min_gallop;
        1816                 :            :         do {
        1817                 :            :             assert(na > 0 && nb > 1);
        1818                 :        320 :             min_gallop -= min_gallop > 1;
        1819                 :        320 :             ms->min_gallop = min_gallop;
        1820                 :        320 :             k = gallop_right(ms, ssb.keys[0], basea.keys, na, na-1);
        1821         [ -  + ]:        320 :             if (k < 0)
        1822                 :          0 :                 goto Fail;
        1823                 :        320 :             k = na - k;
        1824                 :        320 :             acount = k;
        1825         [ +  + ]:        320 :             if (k) {
        1826                 :        251 :                 sortslice_advance(&dest, -k);
        1827                 :        251 :                 sortslice_advance(&ssa, -k);
        1828                 :        251 :                 sortslice_memmove(&dest, 1, &ssa, 1, k);
        1829                 :        251 :                 na -= k;
        1830         [ +  + ]:        251 :                 if (na == 0)
        1831                 :         33 :                     goto Succeed;
        1832                 :            :             }
        1833                 :        287 :             sortslice_copy_decr(&dest, &ssb);
        1834                 :        287 :             --nb;
        1835         [ -  + ]:        287 :             if (nb == 1)
        1836                 :          0 :                 goto CopyA;
        1837                 :            :
        1838                 :        287 :             k = gallop_left(ms, ssa.keys[0], baseb.keys, nb, nb-1);
        1839         [ -  + ]:        287 :             if (k < 0)
        1840                 :          0 :                 goto Fail;
        1841                 :        287 :             k = nb - k;
        1842                 :        287 :             bcount = k;
        1843         [ +  + ]:        287 :             if (k) {
        1844                 :        175 :                 sortslice_advance(&dest, -k);
        1845                 :        175 :                 sortslice_advance(&ssb, -k);
        1846                 :        175 :                 sortslice_memcpy(&dest, 1, &ssb, 1, k);
        1847                 :        175 :                 nb -= k;
        1848         [ +  + ]:        175 :                 if (nb == 1)
        1849                 :          2 :                     goto CopyA;
        1850                 :            :                 /* nb==0 is impossible now if the comparison
        1851                 :            :                  * function is consistent, but we can't assume
        1852                 :            :                  * that it is.
        1853                 :            :                  */
        1854         [ -  + ]:        173 :                 if (nb == 0)
        1855                 :          0 :                     goto Succeed;
        1856                 :            :             }
        1857                 :        285 :             sortslice_copy_decr(&dest, &ssa);
        1858                 :        285 :             --na;
        1859         [ +  + ]:        285 :             if (na == 0)
        1860                 :          3 :                 goto Succeed;
        1861   [ +  +  +  + ]:        282 :         } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
        1862                 :        148 :         ++min_gallop;           /* penalize it for leaving galloping mode */
        1863                 :        148 :         ms->min_gallop = min_gallop;
        1864                 :            :     }
        1865                 :        117 : Succeed:
        1866                 :        117 :     result = 0;
        1867                 :        117 : Fail:
        1868         [ +  - ]:        117 :     if (nb)
        1869                 :        117 :         sortslice_memcpy(&dest, -(nb-1), &baseb, 0, nb);
        1870                 :        117 :     return result;
        1871                 :         14 : CopyA:
        1872                 :            :     assert(nb == 1 && na > 0);
        1873                 :            :     /* The first element of ssb belongs at the front of the merge. */
        1874                 :         14 :     sortslice_memmove(&dest, 1-na, &ssa, 1-na, na);
        1875                 :         14 :     sortslice_advance(&dest, -na);
        1876                 :         14 :     sortslice_advance(&ssa, -na);
        1877                 :         14 :     sortslice_copy(&dest, 0, &ssb, 0);
        1878                 :         14 :     return 0;
        1879                 :            : }
        1880                 :            :
        1881                 :            : /* Merge the two runs at stack indices i and i+1.
        1882                 :            :  * Returns 0 on success, -1 on error.
        1883                 :            :  */
        1884                 :            : static Py_ssize_t
        1885                 :        311 : merge_at(MergeState *ms, Py_ssize_t i)
        1886                 :            : {
        1887                 :            :     sortslice ssa, ssb;
        1888                 :            :     Py_ssize_t na, nb;
        1889                 :            :     Py_ssize_t k;
        1890                 :            :
        1891                 :            :     assert(ms != NULL);
        1892                 :            :     assert(ms->n >= 2);
        1893                 :            :     assert(i >= 0);
        1894                 :            :     assert(i == ms->n - 2 || i == ms->n - 3);
        1895                 :            :
        1896                 :        311 :     ssa = ms->pending[i].base;
        1897                 :        311 :     na = ms->pending[i].len;
        1898                 :        311 :     ssb = ms->pending[i+1].base;
        1899                 :        311 :     nb = ms->pending[i+1].len;
        1900                 :            :     assert(na > 0 && nb > 0);
        1901                 :            :     assert(ssa.keys + na == ssb.keys);
        1902                 :            :
        1903                 :            :     /* Record the length of the combined runs; if i is the 3rd-last
        1904                 :            :      * run now, also slide over the last run (which isn't involved
        1905                 :            :      * in this merge).  The current run i+1 goes away in any case.
        1906                 :            :      */
        1907                 :        311 :     ms->pending[i].len = na + nb;
        1908         [ -  + ]:        311 :     if (i == ms->n - 3)
        1909                 :          0 :         ms->pending[i+1] = ms->pending[i+2];
        1910                 :        311 :     --ms->n;
        1911                 :            :
        1912                 :            :     /* Where does b start in a?  Elements in a before that can be
        1913                 :            :      * ignored (already in place).
        1914                 :            :      */
        1915                 :        311 :     k = gallop_right(ms, *ssb.keys, ssa.keys, na, 0);
        1916         [ -  + ]:        311 :     if (k < 0)
        1917                 :          0 :         return -1;
        1918                 :        311 :     sortslice_advance(&ssa, k);
        1919                 :        311 :     na -= k;
        1920         [ -  + ]:        311 :     if (na == 0)
        1921                 :          0 :         return 0;
        1922                 :            :
        1923                 :            :     /* Where does a end in b?  Elements in b after that can be
        1924                 :            :      * ignored (already in place).
        1925                 :            :      */
        1926                 :        311 :     nb = gallop_left(ms, ssa.keys[na-1], ssb.keys, nb, nb-1);
        1927         [ -  + ]:        311 :     if (nb <= 0)
        1928                 :          0 :         return nb;
        1929                 :            :
        1930                 :            :     /* Merge what remains of the runs, using a temp array with
        1931                 :            :      * min(na, nb) elements.
        1932                 :            :      */
        1933         [ +  + ]:        311 :     if (na <= nb)
        1934                 :        180 :         return merge_lo(ms, ssa, na, ssb, nb);
        1935                 :            :     else
        1936                 :        131 :         return merge_hi(ms, ssa, na, ssb, nb);
        1937                 :            : }
        1938                 :            :
        1939                 :            : /* Two adjacent runs begin at index s1. The first run has length n1, and
        1940                 :            :  * the second run (starting at index s1+n1) has length n2. The list has total
        1941                 :            :  * length n.
        1942                 :            :  * Compute the "power" of the first run. See listsort.txt for details.
        1943                 :            :  */
        1944                 :            : static int
        1945                 :        311 : powerloop(Py_ssize_t s1, Py_ssize_t n1, Py_ssize_t n2, Py_ssize_t n)
        1946                 :            : {
        1947                 :        311 :     int result = 0;
        1948                 :            :     assert(s1 >= 0);
        1949                 :            :     assert(n1 > 0 && n2 > 0);
        1950                 :            :     assert(s1 + n1 + n2 <= n);
        1951                 :            :     /* midpoints a and b:
        1952                 :            :      * a = s1 + n1/2
        1953                 :            :      * b = s1 + n1 + n2/2 = a + (n1 + n2)/2
        1954                 :            :      *
        1955                 :            :      * Those may not be integers, though, because of the "/2". So we work with
        1956                 :            :      * 2*a and 2*b instead, which are necessarily integers. It makes no
        1957                 :            :      * difference to the outcome, since the bits in the expansion of (2*i)/n
        1958                 :            :      * are merely shifted one position from those of i/n.
        1959                 :            :      */
        1960                 :        311 :     Py_ssize_t a = 2 * s1 + n1;  /* 2*a */
        1961                 :        311 :     Py_ssize_t b = a + n1 + n2;  /* 2*b */
        1962                 :            :     /* Emulate a/n and b/n one bit a time, until bits differ. */
        1963                 :            :     for (;;) {
        1964                 :        625 :         ++result;
        1965         [ +  + ]:        625 :         if (a >= n) {  /* both quotient bits are 1 */
        1966                 :            :             assert(b >= a);
        1967                 :        150 :             a -= n;
        1968                 :        150 :             b -= n;
        1969                 :            :         }
        1970         [ +  + ]:        475 :         else if (b >= n) {  /* a/n bit is 0, b/n bit is 1 */
        1971                 :        311 :             break;
        1972                 :            :         } /* else both quotient bits are 0 */
        1973                 :            :         assert(a < b && b < n);
        1974                 :        314 :         a <<= 1;
        1975                 :        314 :         b <<= 1;
        1976                 :            :     }
        1977                 :        311 :     return result;
        1978                 :            : }
        1979                 :            :
        1980                 :            : /* The next run has been identified, of length n2.
        1981                 :            :  * If there's already a run on the stack, apply the "powersort" merge strategy:
        1982                 :            :  * compute the topmost run's "power" (depth in a conceptual binary merge tree)
        1983                 :            :  * and merge adjacent runs on the stack with greater power. See listsort.txt
        1984                 :            :  * for more info.
        1985                 :            :  *
        1986                 :            :  * It's the caller's responsibility to push the new run on the stack when this
        1987                 :            :  * returns.
        1988                 :            :  *
        1989                 :            :  * Returns 0 on success, -1 on error.
        1990                 :            :  */
        1991                 :            : static int
        1992                 :      14549 : found_new_run(MergeState *ms, Py_ssize_t n2)
        1993                 :            : {
        1994                 :            :     assert(ms);
        1995         [ +  + ]:      14549 :     if (ms->n) {
        1996                 :            :         assert(ms->n > 0);
        1997                 :        311 :         struct s_slice *p = ms->pending;
        1998                 :        311 :         Py_ssize_t s1 = p[ms->n - 1].base.keys - ms->basekeys; /* start index */
        1999                 :        311 :         Py_ssize_t n1 = p[ms->n - 1].len;
        2000                 :        311 :         int power = powerloop(s1, n1, n2, ms->listlen);
        2001   [ +  +  +  + ]:        438 :         while (ms->n > 1 && p[ms->n - 2].power > power) {
        2002         [ -  + ]:        127 :             if (merge_at(ms, ms->n - 2) < 0)
        2003                 :          0 :                 return -1;
        2004                 :            :         }
        2005                 :            :         assert(ms->n < 2 || p[ms->n - 2].power < power);
        2006                 :        311 :         p[ms->n - 1].power = power;
        2007                 :            :     }
        2008                 :      14549 :     return 0;
        2009                 :            : }
        2010                 :            :
        2011                 :            : /* Regardless of invariants, merge all runs on the stack until only one
        2012                 :            :  * remains.  This is used at the end of the mergesort.
        2013                 :            :  *
        2014                 :            :  * Returns 0 on success, -1 on error.
        2015                 :            :  */
        2016                 :            : static int
        2017                 :      14238 : merge_force_collapse(MergeState *ms)
        2018                 :            : {
        2019                 :      14238 :     struct s_slice *p = ms->pending;
        2020                 :            :
        2021                 :            :     assert(ms);
        2022         [ +  + ]:      14422 :     while (ms->n > 1) {
        2023                 :        184 :         Py_ssize_t n = ms->n - 2;
        2024   [ +  +  -  + ]:        184 :         if (n > 0 && p[n-1].len < p[n+1].len)
        2025                 :          0 :             --n;
        2026         [ -  + ]:        184 :         if (merge_at(ms, n) < 0)
        2027                 :          0 :             return -1;
        2028                 :            :     }
        2029                 :      14238 :     return 0;
        2030                 :            : }
        2031                 :            :
        2032                 :            : /* Compute a good value for the minimum run length; natural runs shorter
        2033                 :            :  * than this are boosted artificially via binary insertion.
        2034                 :            :  *
        2035                 :            :  * If n < 64, return n (it's too small to bother with fancy stuff).
        2036                 :            :  * Else if n is an exact power of 2, return 32.
        2037                 :            :  * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
        2038                 :            :  * strictly less than, an exact power of 2.
        2039                 :            :  *
        2040                 :            :  * See listsort.txt for more info.
        2041                 :            :  */
        2042                 :            : static Py_ssize_t
        2043                 :      14238 : merge_compute_minrun(Py_ssize_t n)
        2044                 :            : {
        2045                 :      14238 :     Py_ssize_t r = 0;           /* becomes 1 if any 1 bits are shifted off */
        2046                 :            :
        2047                 :            :     assert(n >= 0);
        2048         [ +  + ]:      14427 :     while (n >= 64) {
        2049                 :        189 :         r |= n & 1;
        2050                 :        189 :         n >>= 1;
        2051                 :            :     }
        2052                 :      14238 :     return n + r;
        2053                 :            : }
        2054                 :            :
        2055                 :            : static void
        2056                 :       8646 : reverse_sortslice(sortslice *s, Py_ssize_t n)
        2057                 :            : {
        2058                 :       8646 :     reverse_slice(s->keys, &s->keys[n]);
        2059         [ +  + ]:       8646 :     if (s->values != NULL)
        2060                 :          6 :         reverse_slice(s->values, &s->values[n]);
        2061                 :       8646 : }
        2062                 :            :
        2063                 :            : /* Here we define custom comparison functions to optimize for the cases one commonly
        2064                 :            :  * encounters in practice: homogeneous lists, often of one of the basic types. */
        2065                 :            :
        2066                 :            : /* This struct holds the comparison function and helper functions
        2067                 :            :  * selected in the pre-sort check. */
        2068                 :            :
        2069                 :            : /* These are the special case compare functions.
        2070                 :            :  * ms->key_compare will always point to one of these: */
        2071                 :            :
        2072                 :            : /* Heterogeneous compare: default, always safe to fall back on. */
        2073                 :            : static int
        2074                 :          0 : safe_object_compare(PyObject *v, PyObject *w, MergeState *ms)
        2075                 :            : {
        2076                 :            :     /* No assumptions necessary! */
        2077                 :          0 :     return PyObject_RichCompareBool(v, w, Py_LT);
        2078                 :            : }
        2079                 :            :
        2080                 :            : /* Homogeneous compare: safe for any two comparable objects of the same type.
        2081                 :            :  * (ms->key_richcompare is set to ob_type->tp_richcompare in the
        2082                 :            :  *  pre-sort check.)
        2083                 :            :  */
        2084                 :            : static int
        2085                 :       8711 : unsafe_object_compare(PyObject *v, PyObject *w, MergeState *ms)
        2086                 :            : {
        2087                 :            :     PyObject *res_obj; int res;
        2088                 :            :
        2089                 :            :     /* No assumptions, because we check first: */
        2090         [ -  + ]:       8711 :     if (Py_TYPE(v)->tp_richcompare != ms->key_richcompare)
        2091                 :          0 :         return PyObject_RichCompareBool(v, w, Py_LT);
        2092                 :            :
        2093                 :            :     assert(ms->key_richcompare != NULL);
        2094                 :       8711 :     res_obj = (*(ms->key_richcompare))(v, w, Py_LT);
        2095                 :            :
        2096         [ -  + ]:       8711 :     if (res_obj == Py_NotImplemented) {
        2097                 :          0 :         Py_DECREF(res_obj);
        2098                 :          0 :         return PyObject_RichCompareBool(v, w, Py_LT);
        2099                 :            :     }
        2100         [ -  + ]:       8711 :     if (res_obj == NULL)
        2101                 :          0 :         return -1;
        2102                 :            :
        2103         [ +  - ]:       8711 :     if (PyBool_Check(res_obj)) {
        2104                 :       8711 :         res = (res_obj == Py_True);
        2105                 :            :     }
        2106                 :            :     else {
        2107                 :          0 :         res = PyObject_IsTrue(res_obj);
        2108                 :            :     }
        2109                 :       8711 :     Py_DECREF(res_obj);
        2110                 :            :
        2111                 :            :     /* Note that we can't assert
        2112                 :            :      *     res == PyObject_RichCompareBool(v, w, Py_LT);
        2113                 :            :      * because of evil compare functions like this:
        2114                 :            :      *     lambda a, b:  int(random.random() * 3) - 1)
        2115                 :            :      * (which is actually in test_sort.py) */
        2116                 :       8711 :     return res;
        2117                 :            : }
        2118                 :            :
        2119                 :            : /* Latin string compare: safe for any two latin (one byte per char) strings. */
        2120                 :            : static int
        2121                 :     314040 : unsafe_latin_compare(PyObject *v, PyObject *w, MergeState *ms)
        2122                 :            : {
        2123                 :            :     Py_ssize_t len;
        2124                 :            :     int res;
        2125                 :            :
        2126                 :            :     /* Modified from Objects/unicodeobject.c:unicode_compare, assuming: */
        2127                 :            :     assert(Py_IS_TYPE(v, &PyUnicode_Type));
        2128                 :            :     assert(Py_IS_TYPE(w, &PyUnicode_Type));
        2129                 :            :     assert(PyUnicode_KIND(v) == PyUnicode_KIND(w));
        2130                 :            :     assert(PyUnicode_KIND(v) == PyUnicode_1BYTE_KIND);
        2131                 :            :
        2132         [ +  + ]:     314040 :     len = Py_MIN(PyUnicode_GET_LENGTH(v), PyUnicode_GET_LENGTH(w));
        2133                 :     314040 :     res = memcmp(PyUnicode_DATA(v), PyUnicode_DATA(w), len);
        2134                 :            :
        2135                 :     314040 :     res = (res != 0 ?
        2136         [ +  + ]:     314040 :            res < 0 :
        2137                 :       6822 :            PyUnicode_GET_LENGTH(v) < PyUnicode_GET_LENGTH(w));
        2138                 :            :
        2139                 :            :     assert(res == PyObject_RichCompareBool(v, w, Py_LT));;
        2140                 :     314040 :     return res;
        2141                 :            : }
        2142                 :            :
        2143                 :            : /* Bounded int compare: compare any two longs that fit in a single machine word. */
        2144                 :            : static int
        2145                 :       1110 : unsafe_long_compare(PyObject *v, PyObject *w, MergeState *ms)
        2146                 :            : {
        2147                 :            :     PyLongObject *vl, *wl; sdigit v0, w0; int res;
        2148                 :            :
        2149                 :            :     /* Modified from Objects/longobject.c:long_compare, assuming: */
        2150                 :            :     assert(Py_IS_TYPE(v, &PyLong_Type));
        2151                 :            :     assert(Py_IS_TYPE(w, &PyLong_Type));
        2152                 :            :     assert(Py_ABS(Py_SIZE(v)) <= 1);
        2153                 :            :     assert(Py_ABS(Py_SIZE(w)) <= 1);
        2154                 :            :
        2155                 :       1110 :     vl = (PyLongObject*)v;
        2156                 :       1110 :     wl = (PyLongObject*)w;
        2157                 :            :
        2158         [ +  - ]:       1110 :     v0 = Py_SIZE(vl) == 0 ? 0 : (sdigit)vl->long_value.ob_digit[0];
        2159         [ +  + ]:       1110 :     w0 = Py_SIZE(wl) == 0 ? 0 : (sdigit)wl->long_value.ob_digit[0];
        2160                 :            :
        2161         [ -  + ]:       1110 :     if (Py_SIZE(vl) < 0)
        2162                 :          0 :         v0 = -v0;
        2163         [ -  + ]:       1110 :     if (Py_SIZE(wl) < 0)
        2164                 :          0 :         w0 = -w0;
        2165                 :            :
        2166                 :       1110 :     res = v0 < w0;
        2167                 :            :     assert(res == PyObject_RichCompareBool(v, w, Py_LT));
        2168                 :       1110 :     return res;
        2169                 :            : }
        2170                 :            :
        2171                 :            : /* Float compare: compare any two floats. */
        2172                 :            : static int
        2173                 :          0 : unsafe_float_compare(PyObject *v, PyObject *w, MergeState *ms)
        2174                 :            : {
        2175                 :            :     int res;
        2176                 :            :
        2177                 :            :     /* Modified from Objects/floatobject.c:float_richcompare, assuming: */
        2178                 :            :     assert(Py_IS_TYPE(v, &PyFloat_Type));
        2179                 :            :     assert(Py_IS_TYPE(w, &PyFloat_Type));
        2180                 :            :
        2181                 :          0 :     res = PyFloat_AS_DOUBLE(v) < PyFloat_AS_DOUBLE(w);
        2182                 :            :     assert(res == PyObject_RichCompareBool(v, w, Py_LT));
        2183                 :          0 :     return res;
        2184                 :            : }
        2185                 :            :
        2186                 :            : /* Tuple compare: compare *any* two tuples, using
        2187                 :            :  * ms->tuple_elem_compare to compare the first elements, which is set
        2188                 :            :  * using the same pre-sort check as we use for ms->key_compare,
        2189                 :            :  * but run on the list [x[0] for x in L]. This allows us to optimize compares
        2190                 :            :  * on two levels (as long as [x[0] for x in L] is type-homogeneous.) The idea is
        2191                 :            :  * that most tuple compares don't involve x[1:]. */
        2192                 :            : static int
        2193                 :       9023 : unsafe_tuple_compare(PyObject *v, PyObject *w, MergeState *ms)
        2194                 :            : {
        2195                 :            :     PyTupleObject *vt, *wt;
        2196                 :            :     Py_ssize_t i, vlen, wlen;
        2197                 :            :     int k;
        2198                 :            :
        2199                 :            :     /* Modified from Objects/tupleobject.c:tuplerichcompare, assuming: */
        2200                 :            :     assert(Py_IS_TYPE(v, &PyTuple_Type));
        2201                 :            :     assert(Py_IS_TYPE(w, &PyTuple_Type));
        2202                 :            :     assert(Py_SIZE(v) > 0);
        2203                 :            :     assert(Py_SIZE(w) > 0);
        2204                 :            :
        2205                 :       9023 :     vt = (PyTupleObject *)v;
        2206                 :       9023 :     wt = (PyTupleObject *)w;
        2207                 :            :
        2208                 :       9023 :     vlen = Py_SIZE(vt);
        2209                 :       9023 :     wlen = Py_SIZE(wt);
        2210                 :            :
        2211   [ +  -  +  - ]:       9034 :     for (i = 0; i < vlen && i < wlen; i++) {
        2212                 :       9034 :         k = PyObject_RichCompareBool(vt->ob_item[i], wt->ob_item[i], Py_EQ);
        2213         [ -  + ]:       9034 :         if (k < 0)
        2214                 :          0 :             return -1;
        2215         [ +  + ]:       9034 :         if (!k)
        2216                 :       9023 :             break;
        2217                 :            :     }
        2218                 :            :
        2219   [ +  -  -  + ]:       9023 :     if (i >= vlen || i >= wlen)
        2220                 :          0 :         return vlen < wlen;
        2221                 :            :
        2222         [ +  + ]:       9023 :     if (i == 0)
        2223                 :       9012 :         return ms->tuple_elem_compare(vt->ob_item[i], wt->ob_item[i], ms);
        2224                 :            :     else
        2225                 :         11 :         return PyObject_RichCompareBool(vt->ob_item[i], wt->ob_item[i], Py_LT);
        2226                 :            : }
        2227                 :            :
        2228                 :            : /* An adaptive, stable, natural mergesort.  See listsort.txt.
        2229                 :            :  * Returns Py_None on success, NULL on error.  Even in case of error, the
        2230                 :            :  * list will be some permutation of its input state (nothing is lost or
        2231                 :            :  * duplicated).
        2232                 :            :  */
        2233                 :            : /*[clinic input]
        2234                 :            : list.sort
        2235                 :            :
        2236                 :            :     *
        2237                 :            :     key as keyfunc: object = None
        2238                 :            :     reverse: bool = False
        2239                 :            :
        2240                 :            : Sort the list in ascending order and return None.
        2241                 :            :
        2242                 :            : The sort is in-place (i.e. the list itself is modified) and stable (i.e. the
        2243                 :            : order of two equal elements is maintained).
        2244                 :            :
        2245                 :            : If a key function is given, apply it once to each list item and sort them,
        2246                 :            : ascending or descending, according to their function values.
        2247                 :            :
        2248                 :            : The reverse flag can be set to sort in descending order.
        2249                 :            : [clinic start generated code]*/
        2250                 :            :
        2251                 :            : static PyObject *
        2252                 :      17202 : list_sort_impl(PyListObject *self, PyObject *keyfunc, int reverse)
        2253                 :            : /*[clinic end generated code: output=57b9f9c5e23fbe42 input=a74c4cd3ec6b5c08]*/
        2254                 :            : {
        2255                 :            :     MergeState ms;
        2256                 :            :     Py_ssize_t nremaining;
        2257                 :            :     Py_ssize_t minrun;
        2258                 :            :     sortslice lo;
        2259                 :            :     Py_ssize_t saved_ob_size, saved_allocated;
        2260                 :            :     PyObject **saved_ob_item;
        2261                 :            :     PyObject **final_ob_item;
        2262                 :      17202 :     PyObject *result = NULL;            /* guilty until proved innocent */
        2263                 :            :     Py_ssize_t i;
        2264                 :            :     PyObject **keys;
        2265                 :            :
        2266                 :            :     assert(self != NULL);
        2267                 :            :     assert(PyList_Check(self));
        2268         [ +  + ]:      17202 :     if (keyfunc == Py_None)
        2269                 :         97 :         keyfunc = NULL;
        2270                 :            :
        2271                 :            :     /* The list is temporarily made empty, so that mutations performed
        2272                 :            :      * by comparison functions can't affect the slice of memory we're
        2273                 :            :      * sorting (allowing mutations during sorting is a core-dump
        2274                 :            :      * factory, since ob_item may change).
        2275                 :            :      */
        2276                 :      17202 :     saved_ob_size = Py_SIZE(self);
        2277                 :      17202 :     saved_ob_item = self->ob_item;
        2278                 :      17202 :     saved_allocated = self->allocated;
        2279                 :      17202 :     Py_SET_SIZE(self, 0);
        2280                 :      17202 :     self->ob_item = NULL;
        2281                 :      17202 :     self->allocated = -1; /* any operation will reset it to >= 0 */
        2282                 :            :
        2283         [ +  + ]:      17202 :     if (keyfunc == NULL) {
        2284                 :      17175 :         keys = NULL;
        2285                 :      17175 :         lo.keys = saved_ob_item;
        2286                 :      17175 :         lo.values = NULL;
        2287                 :            :     }
        2288                 :            :     else {
        2289         [ +  + ]:         27 :         if (saved_ob_size < MERGESTATE_TEMP_SIZE/2)
        2290                 :            :             /* Leverage stack space we allocated but won't otherwise use */
        2291                 :         25 :             keys = &ms.temparray[saved_ob_size+1];
        2292                 :            :         else {
        2293                 :          2 :             keys = PyMem_Malloc(sizeof(PyObject *) * saved_ob_size);
        2294         [ -  + ]:          2 :             if (keys == NULL) {
        2295                 :          0 :                 PyErr_NoMemory();
        2296                 :          0 :                 goto keyfunc_fail;
        2297                 :            :             }
        2298                 :            :         }
        2299                 :            :
        2300         [ +  + ]:       2288 :         for (i = 0; i < saved_ob_size ; i++) {
        2301                 :       2261 :             keys[i] = PyObject_CallOneArg(keyfunc, saved_ob_item[i]);
        2302         [ -  + ]:       2261 :             if (keys[i] == NULL) {
        2303         [ #  # ]:          0 :                 for (i=i-1 ; i>=0 ; i--)
        2304                 :          0 :                     Py_DECREF(keys[i]);
        2305         [ #  # ]:          0 :                 if (saved_ob_size >= MERGESTATE_TEMP_SIZE/2)
        2306                 :          0 :                     PyMem_Free(keys);
        2307                 :          0 :                 goto keyfunc_fail;
        2308                 :            :             }
        2309                 :            :         }
        2310                 :            :
        2311                 :         27 :         lo.keys = keys;
        2312                 :         27 :         lo.values = saved_ob_item;
        2313                 :            :     }
        2314                 :            :
        2315                 :            :
        2316                 :            :     /* The pre-sort check: here's where we decide which compare function to use.
        2317                 :            :      * How much optimization is safe? We test for homogeneity with respect to
        2318                 :            :      * several properties that are expensive to check at compare-time, and
        2319                 :            :      * set ms appropriately. */
        2320         [ +  + ]:      17202 :     if (saved_ob_size > 1) {
        2321                 :            :         /* Assume the first element is representative of the whole list. */
        2322   [ +  +  +  - ]:      14294 :         int keys_are_in_tuples = (Py_IS_TYPE(lo.keys[0], &PyTuple_Type) &&
        2323                 :         56 :                                   Py_SIZE(lo.keys[0]) > 0);
        2324                 :            :
        2325                 :      14238 :         PyTypeObject* key_type = (keys_are_in_tuples ?
        2326         [ +  + ]:      14238 :                                   Py_TYPE(PyTuple_GET_ITEM(lo.keys[0], 0)) :
        2327                 :      14182 :                                   Py_TYPE(lo.keys[0]));
        2328                 :            :
        2329                 :      14238 :         int keys_are_all_same_type = 1;
        2330                 :      14238 :         int strings_are_latin = 1;
        2331                 :      14238 :         int ints_are_bounded = 1;
        2332                 :            :
        2333                 :            :         /* Prove that assumption by checking every key. */
        2334         [ +  + ]:     128879 :         for (i=0; i < saved_ob_size; i++) {
        2335                 :            :
        2336   [ +  +  +  - ]:     117048 :             if (keys_are_in_tuples &&
        2337         [ -  + ]:       4814 :                 !(Py_IS_TYPE(lo.keys[i], &PyTuple_Type) && Py_SIZE(lo.keys[i]) != 0)) {
        2338                 :          0 :                 keys_are_in_tuples = 0;
        2339                 :          0 :                 keys_are_all_same_type = 0;
        2340                 :          0 :                 break;
        2341                 :            :             }
        2342                 :            :
        2343                 :            :             /* Note: for lists of tuples, key is the first element of the tuple
        2344                 :            :              * lo.keys[i], not lo.keys[i] itself! We verify type-homogeneity
        2345                 :            :              * for lists of tuples in the if-statement directly above. */
        2346                 :     114641 :             PyObject *key = (keys_are_in_tuples ?
        2347         [ +  + ]:     114641 :                              PyTuple_GET_ITEM(lo.keys[i], 0) :
        2348                 :     112234 :                              lo.keys[i]);
        2349                 :            :
        2350         [ -  + ]:     114641 :             if (!Py_IS_TYPE(key, key_type)) {
        2351                 :          0 :                 keys_are_all_same_type = 0;
        2352                 :            :                 /* If keys are in tuple we must loop over the whole list to make
        2353                 :            :                    sure all items are tuples */
        2354         [ #  # ]:          0 :                 if (!keys_are_in_tuples) {
        2355                 :          0 :                     break;
        2356                 :            :                 }
        2357                 :            :             }
        2358                 :            :
        2359         [ +  - ]:     114641 :             if (keys_are_all_same_type) {
        2360   [ +  +  +  +  :     115532 :                 if (key_type == &PyLong_Type &&
                       -  + ]
        2361                 :          0 :                     ints_are_bounded &&
        2362   [ -  -  +  + ]:       1782 :                     Py_ABS(Py_SIZE(key)) > 1) {
        2363                 :            :
        2364                 :          4 :                     ints_are_bounded = 0;
        2365                 :            :                 }
        2366   [ +  +  +  - ]:     114637 :                 else if (key_type == &PyUnicode_Type &&
        2367                 :     111478 :                          strings_are_latin &&
        2368         [ -  + ]:     111478 :                          PyUnicode_KIND(key) != PyUnicode_1BYTE_KIND) {
        2369                 :            :
        2370                 :          0 :                         strings_are_latin = 0;
        2371                 :            :                     }
        2372                 :            :                 }
        2373                 :            :             }
        2374                 :            :
        2375                 :            :         /* Choose the best compare, given what we now know about the keys. */
        2376         [ +  - ]:      14238 :         if (keys_are_all_same_type) {
        2377                 :            :
        2378   [ +  +  +  - ]:      14238 :             if (key_type == &PyUnicode_Type && strings_are_latin) {
        2379                 :      14101 :                 ms.key_compare = unsafe_latin_compare;
        2380                 :            :             }
        2381   [ +  +  +  + ]:        137 :             else if (key_type == &PyLong_Type && ints_are_bounded) {
        2382                 :         93 :                 ms.key_compare = unsafe_long_compare;
        2383                 :            :             }
        2384         [ -  + ]:         44 :             else if (key_type == &PyFloat_Type) {
        2385                 :          0 :                 ms.key_compare = unsafe_float_compare;
        2386                 :            :             }
        2387         [ +  - ]:         44 :             else if ((ms.key_richcompare = key_type->tp_richcompare) != NULL) {
        2388                 :         44 :                 ms.key_compare = unsafe_object_compare;
        2389                 :            :             }
        2390                 :            :             else {
        2391                 :          0 :                 ms.key_compare = safe_object_compare;
        2392                 :            :             }
        2393                 :            :         }
        2394                 :            :         else {
        2395                 :          0 :             ms.key_compare = safe_object_compare;
        2396                 :            :         }
        2397                 :            :
        2398         [ +  + ]:      14238 :         if (keys_are_in_tuples) {
        2399                 :            :             /* Make sure we're not dealing with tuples of tuples
        2400                 :            :              * (remember: here, key_type refers list [key[0] for key in keys]) */
        2401         [ -  + ]:         56 :             if (key_type == &PyTuple_Type) {
        2402                 :          0 :                 ms.tuple_elem_compare = safe_object_compare;
        2403                 :            :             }
        2404                 :            :             else {
        2405                 :         56 :                 ms.tuple_elem_compare = ms.key_compare;
        2406                 :            :             }
        2407                 :            :
        2408                 :         56 :             ms.key_compare = unsafe_tuple_compare;
        2409                 :            :         }
        2410                 :            :     }
        2411                 :            :     /* End of pre-sort check: ms is now set properly! */
        2412                 :            :
        2413                 :      17202 :     merge_init(&ms, saved_ob_size, keys != NULL, &lo);
        2414                 :            :
        2415                 :      17202 :     nremaining = saved_ob_size;
        2416         [ +  + ]:      17202 :     if (nremaining < 2)
        2417                 :       2964 :         goto succeed;
        2418                 :            :
        2419                 :            :     /* Reverse sort stability achieved by initially reversing the list,
        2420                 :            :     applying a stable forward sort, then reversing the final result. */
        2421         [ +  + ]:      14238 :     if (reverse) {
        2422         [ -  + ]:          3 :         if (keys != NULL)
        2423                 :          0 :             reverse_slice(&keys[0], &keys[saved_ob_size]);
        2424                 :          3 :         reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]);
        2425                 :            :     }
        2426                 :            :
        2427                 :            :     /* March over the array once, left to right, finding natural runs,
        2428                 :            :      * and extending short natural runs to minrun elements.
        2429                 :            :      */
        2430                 :      14238 :     minrun = merge_compute_minrun(nremaining);
        2431                 :            :     do {
        2432                 :            :         int descending;
        2433                 :            :         Py_ssize_t n;
        2434                 :            :
        2435                 :            :         /* Identify next run. */
        2436                 :      14549 :         n = count_run(&ms, lo.keys, lo.keys + nremaining, &descending);
        2437         [ -  + ]:      14549 :         if (n < 0)
        2438                 :          0 :             goto fail;
        2439         [ +  + ]:      14549 :         if (descending)
        2440                 :       8646 :             reverse_sortslice(&lo, n);
        2441                 :            :         /* If short, extend to min(minrun, nremaining). */
        2442         [ +  + ]:      14549 :         if (n < minrun) {
        2443                 :      10186 :             const Py_ssize_t force = nremaining <= minrun ?
        2444                 :            :                               nremaining : minrun;
        2445         [ -  + ]:      10186 :             if (binarysort(&ms, lo, lo.keys + force, lo.keys + n) < 0)
        2446                 :          0 :                 goto fail;
        2447                 :      10186 :             n = force;
        2448                 :            :         }
        2449                 :            :         /* Maybe merge pending runs. */
        2450                 :            :         assert(ms.n == 0 || ms.pending[ms.n -1].base.keys +
        2451                 :            :                             ms.pending[ms.n-1].len == lo.keys);
        2452         [ -  + ]:      14549 :         if (found_new_run(&ms, n) < 0)
        2453                 :          0 :             goto fail;
        2454                 :            :         /* Push new run on stack. */
        2455                 :            :         assert(ms.n < MAX_MERGE_PENDING);
        2456                 :      14549 :         ms.pending[ms.n].base = lo;
        2457                 :      14549 :         ms.pending[ms.n].len = n;
        2458                 :      14549 :         ++ms.n;
        2459                 :            :         /* Advance to find next run. */
        2460                 :      14549 :         sortslice_advance(&lo, n);
        2461                 :      14549 :         nremaining -= n;
        2462         [ +  + ]:      14549 :     } while (nremaining);
        2463                 :            :
        2464         [ -  + ]:      14238 :     if (merge_force_collapse(&ms) < 0)
        2465                 :          0 :         goto fail;
        2466                 :            :     assert(ms.n == 1);
        2467                 :            :     assert(keys == NULL
        2468                 :            :            ? ms.pending[0].base.keys == saved_ob_item
        2469                 :            :            : ms.pending[0].base.keys == &keys[0]);
        2470                 :            :     assert(ms.pending[0].len == saved_ob_size);
        2471                 :      14238 :     lo = ms.pending[0].base;
        2472                 :            :
        2473                 :      17202 : succeed:
        2474                 :      17202 :     result = Py_None;
        2475                 :      17202 : fail:
        2476         [ +  + ]:      17202 :     if (keys != NULL) {
        2477         [ +  + ]:       2288 :         for (i = 0; i < saved_ob_size; i++)
        2478                 :       2261 :             Py_DECREF(keys[i]);
        2479         [ +  + ]:         27 :         if (saved_ob_size >= MERGESTATE_TEMP_SIZE/2)
        2480                 :          2 :             PyMem_Free(keys);
        2481                 :            :     }
        2482                 :            :
        2483   [ -  +  -  - ]:      17202 :     if (self->allocated != -1 && result != NULL) {
        2484                 :            :         /* The user mucked with the list during the sort,
        2485                 :            :          * and we don't already have another error to report.
        2486                 :            :          */
        2487                 :          0 :         PyErr_SetString(PyExc_ValueError, "list modified during sort");
        2488                 :          0 :         result = NULL;
        2489                 :            :     }
        2490                 :            :
        2491   [ +  +  +  - ]:      17202 :     if (reverse && saved_ob_size > 1)
        2492                 :          3 :         reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);
        2493                 :            :
        2494                 :      17202 :     merge_freemem(&ms);
        2495                 :            :
        2496                 :      17202 : keyfunc_fail:
        2497                 :      17202 :     final_ob_item = self->ob_item;
        2498                 :      17202 :     i = Py_SIZE(self);
        2499                 :      17202 :     Py_SET_SIZE(self, saved_ob_size);
        2500                 :      17202 :     self->ob_item = saved_ob_item;
        2501                 :      17202 :     self->allocated = saved_allocated;
        2502         [ -  + ]:      17202 :     if (final_ob_item != NULL) {
        2503                 :            :         /* we cannot use _list_clear() for this because it does not
        2504                 :            :            guarantee that the list is really empty when it returns */
        2505         [ #  # ]:          0 :         while (--i >= 0) {
        2506                 :          0 :             Py_XDECREF(final_ob_item[i]);
        2507                 :            :         }
        2508                 :          0 :         PyMem_Free(final_ob_item);
        2509                 :            :     }
        2510                 :      17202 :     return Py_XNewRef(result);
        2511                 :            : }
        2512                 :            : #undef IFLT
        2513                 :            : #undef ISLT
        2514                 :            :
        2515                 :            : int
        2516                 :      17078 : PyList_Sort(PyObject *v)
        2517                 :            : {
        2518   [ +  -  -  + ]:      17078 :     if (v == NULL || !PyList_Check(v)) {
        2519                 :          0 :         PyErr_BadInternalCall();
        2520                 :          0 :         return -1;
        2521                 :            :     }
        2522                 :      17078 :     v = list_sort_impl((PyListObject *)v, NULL, 0);
        2523         [ -  + ]:      17078 :     if (v == NULL)
        2524                 :          0 :         return -1;
        2525                 :      17078 :     Py_DECREF(v);
        2526                 :      17078 :     return 0;
        2527                 :            : }
        2528                 :            :
        2529                 :            : /*[clinic input]
        2530                 :            : list.reverse
        2531                 :            :
        2532                 :            : Reverse *IN PLACE*.
        2533                 :            : [clinic start generated code]*/
        2534                 :            :
        2535                 :            : static PyObject *
        2536                 :         24 : list_reverse_impl(PyListObject *self)
        2537                 :            : /*[clinic end generated code: output=482544fc451abea9 input=eefd4c3ae1bc9887]*/
        2538                 :            : {
        2539         [ +  + ]:         24 :     if (Py_SIZE(self) > 1)
        2540                 :         16 :         reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
        2541                 :         24 :     Py_RETURN_NONE;
        2542                 :            : }
        2543                 :            :
        2544                 :            : int
        2545                 :         23 : PyList_Reverse(PyObject *v)
        2546                 :            : {
        2547                 :         23 :     PyListObject *self = (PyListObject *)v;
        2548                 :            :
        2549   [ +  -  -  + ]:         23 :     if (v == NULL || !PyList_Check(v)) {
        2550                 :          0 :         PyErr_BadInternalCall();
        2551                 :          0 :         return -1;
        2552                 :            :     }
        2553         [ +  - ]:         23 :     if (Py_SIZE(self) > 1)
        2554                 :         23 :         reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
        2555                 :         23 :     return 0;
        2556                 :            : }
        2557                 :            :
        2558                 :            : PyObject *
        2559                 :      18559 : PyList_AsTuple(PyObject *v)
        2560                 :            : {
        2561   [ +  -  -  + ]:      18559 :     if (v == NULL || !PyList_Check(v)) {
        2562                 :          0 :         PyErr_BadInternalCall();
        2563                 :          0 :         return NULL;
        2564                 :            :     }
        2565                 :      18559 :     return _PyTuple_FromArray(((PyListObject *)v)->ob_item, Py_SIZE(v));
        2566                 :            : }
        2567                 :            :
        2568                 :            : PyObject *
        2569                 :     165891 : _PyList_FromArraySteal(PyObject *const *src, Py_ssize_t n)
        2570                 :            : {
        2571         [ +  + ]:     165891 :     if (n == 0) {
        2572                 :     158224 :         return PyList_New(0);
        2573                 :            :     }
        2574                 :            :
        2575                 :       7667 :     PyListObject *list = (PyListObject *)PyList_New(n);
        2576         [ -  + ]:       7667 :     if (list == NULL) {
        2577         [ #  # ]:          0 :         for (Py_ssize_t i = 0; i < n; i++) {
        2578                 :          0 :             Py_DECREF(src[i]);
        2579                 :            :         }
        2580                 :          0 :         return NULL;
        2581                 :            :     }
        2582                 :            :
        2583                 :       7667 :     PyObject **dst = list->ob_item;
        2584                 :       7667 :     memcpy(dst, src, n * sizeof(PyObject *));
        2585                 :            :
        2586                 :       7667 :     return (PyObject *)list;
        2587                 :            : }
        2588                 :            :
        2589                 :            : /*[clinic input]
        2590                 :            : list.index
        2591                 :            :
        2592                 :            :     value: object
        2593                 :            :     start: slice_index(accept={int}) = 0
        2594                 :            :     stop: slice_index(accept={int}, c_default="PY_SSIZE_T_MAX") = sys.maxsize
        2595                 :            :     /
        2596                 :            :
        2597                 :            : Return first index of value.
        2598                 :            :
        2599                 :            : Raises ValueError if the value is not present.
        2600                 :            : [clinic start generated code]*/
        2601                 :            :
        2602                 :            : static PyObject *
        2603                 :          0 : list_index_impl(PyListObject *self, PyObject *value, Py_ssize_t start,
        2604                 :            :                 Py_ssize_t stop)
        2605                 :            : /*[clinic end generated code: output=ec51b88787e4e481 input=40ec5826303a0eb1]*/
        2606                 :            : {
        2607                 :            :     Py_ssize_t i;
        2608                 :            :
        2609         [ #  # ]:          0 :     if (start < 0) {
        2610                 :          0 :         start += Py_SIZE(self);
        2611         [ #  # ]:          0 :         if (start < 0)
        2612                 :          0 :             start = 0;
        2613                 :            :     }
        2614         [ #  # ]:          0 :     if (stop < 0) {
        2615                 :          0 :         stop += Py_SIZE(self);
        2616         [ #  # ]:          0 :         if (stop < 0)
        2617                 :          0 :             stop = 0;
        2618                 :            :     }
        2619   [ #  #  #  # ]:          0 :     for (i = start; i < stop && i < Py_SIZE(self); i++) {
        2620                 :          0 :         PyObject *obj = self->ob_item[i];
        2621                 :          0 :         Py_INCREF(obj);
        2622                 :          0 :         int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
        2623                 :          0 :         Py_DECREF(obj);
        2624         [ #  # ]:          0 :         if (cmp > 0)
        2625                 :          0 :             return PyLong_FromSsize_t(i);
        2626         [ #  # ]:          0 :         else if (cmp < 0)
        2627                 :          0 :             return NULL;
        2628                 :            :     }
        2629                 :          0 :     PyErr_Format(PyExc_ValueError, "%R is not in list", value);
        2630                 :          0 :     return NULL;
        2631                 :            : }
        2632                 :            :
        2633                 :            : /*[clinic input]
        2634                 :            : list.count
        2635                 :            :
        2636                 :            :      value: object
        2637                 :            :      /
        2638                 :            :
        2639                 :            : Return number of occurrences of value.
        2640                 :            : [clinic start generated code]*/
        2641                 :            :
        2642                 :            : static PyObject *
        2643                 :          0 : list_count(PyListObject *self, PyObject *value)
        2644                 :            : /*[clinic end generated code: output=b1f5d284205ae714 input=3bdc3a5e6f749565]*/
        2645                 :            : {
        2646                 :          0 :     Py_ssize_t count = 0;
        2647                 :            :     Py_ssize_t i;
        2648                 :            :
        2649         [ #  # ]:          0 :     for (i = 0; i < Py_SIZE(self); i++) {
        2650                 :          0 :         PyObject *obj = self->ob_item[i];
        2651         [ #  # ]:          0 :         if (obj == value) {
        2652                 :          0 :            count++;
        2653                 :          0 :            continue;
        2654                 :            :         }
        2655                 :          0 :         Py_INCREF(obj);
        2656                 :          0 :         int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
        2657                 :          0 :         Py_DECREF(obj);
        2658         [ #  # ]:          0 :         if (cmp > 0)
        2659                 :          0 :             count++;
        2660         [ #  # ]:          0 :         else if (cmp < 0)
        2661                 :          0 :             return NULL;
        2662                 :            :     }
        2663                 :          0 :     return PyLong_FromSsize_t(count);
        2664                 :            : }
        2665                 :            :
        2666                 :            : /*[clinic input]
        2667                 :            : list.remove
        2668                 :            :
        2669                 :            :      value: object
        2670                 :            :      /
        2671                 :            :
        2672                 :            : Remove first occurrence of value.
        2673                 :            :
        2674                 :            : Raises ValueError if the value is not present.
        2675                 :            : [clinic start generated code]*/
        2676                 :            :
        2677                 :            : static PyObject *
        2678                 :       1512 : list_remove(PyListObject *self, PyObject *value)
        2679                 :            : /*[clinic end generated code: output=f087e1951a5e30d1 input=2dc2ba5bb2fb1f82]*/
        2680                 :            : {
        2681                 :            :     Py_ssize_t i;
        2682                 :            :
        2683         [ +  + ]:       3788 :     for (i = 0; i < Py_SIZE(self); i++) {
        2684                 :       3786 :         PyObject *obj = self->ob_item[i];
        2685                 :       3786 :         Py_INCREF(obj);
        2686                 :       3786 :         int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
        2687                 :       3786 :         Py_DECREF(obj);
        2688         [ +  + ]:       3786 :         if (cmp > 0) {
        2689         [ +  - ]:       1510 :             if (list_ass_slice(self, i, i+1,
        2690                 :            :                                (PyObject *)NULL) == 0)
        2691                 :       1510 :                 Py_RETURN_NONE;
        2692                 :          0 :             return NULL;
        2693                 :            :         }
        2694         [ -  + ]:       2276 :         else if (cmp < 0)
        2695                 :          0 :             return NULL;
        2696                 :            :     }
        2697                 :          2 :     PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
        2698                 :          2 :     return NULL;
        2699                 :            : }
        2700                 :            :
        2701                 :            : static int
        2702                 :      31392 : list_traverse(PyListObject *o, visitproc visit, void *arg)
        2703                 :            : {
        2704                 :            :     Py_ssize_t i;
        2705                 :            :
        2706         [ +  + ]:    1315764 :     for (i = Py_SIZE(o); --i >= 0; )
        2707   [ +  -  -  + ]:    1284372 :         Py_VISIT(o->ob_item[i]);
        2708                 :      31392 :     return 0;
        2709                 :            : }
        2710                 :            :
        2711                 :            : static PyObject *
        2712                 :       2003 : list_richcompare(PyObject *v, PyObject *w, int op)
        2713                 :            : {
        2714                 :            :     PyListObject *vl, *wl;
        2715                 :            :     Py_ssize_t i;
        2716                 :            :
        2717   [ +  -  +  + ]:       2003 :     if (!PyList_Check(v) || !PyList_Check(w))
        2718                 :        610 :         Py_RETURN_NOTIMPLEMENTED;
        2719                 :            :
        2720                 :       1393 :     vl = (PyListObject *)v;
        2721                 :       1393 :     wl = (PyListObject *)w;
        2722                 :            :
        2723   [ +  +  -  +  :       1393 :     if (Py_SIZE(vl) != Py_SIZE(wl) && (op == Py_EQ || op == Py_NE)) {
                       -  - ]
        2724                 :            :         /* Shortcut: if the lengths differ, the lists differ */
        2725         [ +  - ]:        290 :         if (op == Py_EQ)
        2726                 :        290 :             Py_RETURN_FALSE;
        2727                 :            :         else
        2728                 :          0 :             Py_RETURN_TRUE;
        2729                 :            :     }
        2730                 :            :
        2731                 :            :     /* Search for the first index where items are different */
        2732   [ +  +  +  - ]:       3367 :     for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) {
        2733                 :       2268 :         PyObject *vitem = vl->ob_item[i];
        2734                 :       2268 :         PyObject *witem = wl->ob_item[i];
        2735         [ +  + ]:       2268 :         if (vitem == witem) {
        2736                 :         80 :             continue;
        2737                 :            :         }
        2738                 :            :
        2739                 :       2188 :         Py_INCREF(vitem);
        2740                 :       2188 :         Py_INCREF(witem);
        2741                 :       2188 :         int k = PyObject_RichCompareBool(vitem, witem, Py_EQ);
        2742                 :       2188 :         Py_DECREF(vitem);
        2743                 :       2188 :         Py_DECREF(witem);
        2744         [ -  + ]:       2188 :         if (k < 0)
        2745                 :          0 :             return NULL;
        2746         [ +  + ]:       2188 :         if (!k)
        2747                 :          4 :             break;
        2748                 :            :     }
        2749                 :            :
        2750   [ +  +  -  + ]:       1103 :     if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) {
        2751                 :            :         /* No more items to compare -- compare sizes */
        2752   [ +  +  -  -  :       1099 :         Py_RETURN_RICHCOMPARE(Py_SIZE(vl), Py_SIZE(wl), op);
              -  -  -  +  -
              -  +  -  -  -
                 -  -  -  -
                          - ]
        2753                 :            :     }
        2754                 :            :
        2755                 :            :     /* We have an item that differs -- shortcuts for EQ/NE */
        2756         [ -  + ]:          4 :     if (op == Py_EQ) {
        2757                 :          0 :         Py_RETURN_FALSE;
        2758                 :            :     }
        2759         [ +  - ]:          4 :     if (op == Py_NE) {
        2760                 :          4 :         Py_RETURN_TRUE;
        2761                 :            :     }
        2762                 :            :
        2763                 :            :     /* Compare the final item again using the proper operator */
        2764                 :          0 :     return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
        2765                 :            : }
        2766                 :            :
        2767                 :            : /*[clinic input]
        2768                 :            : list.__init__
        2769                 :            :
        2770                 :            :     iterable: object(c_default="NULL") = ()
        2771                 :            :     /
        2772                 :            :
        2773                 :            : Built-in mutable sequence.
        2774                 :            :
        2775                 :            : If no argument is given, the constructor creates a new empty list.
        2776                 :            : The argument must be an iterable if specified.
        2777                 :            : [clinic start generated code]*/
        2778                 :            :
        2779                 :            : static int
        2780                 :      14580 : list___init___impl(PyListObject *self, PyObject *iterable)
        2781                 :            : /*[clinic end generated code: output=0f3c21379d01de48 input=b3f3fe7206af8f6b]*/
        2782                 :            : {
        2783                 :            :     /* Verify list invariants established by PyType_GenericAlloc() */
        2784                 :            :     assert(0 <= Py_SIZE(self));
        2785                 :            :     assert(Py_SIZE(self) <= self->allocated || self->allocated == -1);
        2786                 :            :     assert(self->ob_item != NULL ||
        2787                 :            :            self->allocated == 0 || self->allocated == -1);
        2788                 :            :
        2789                 :            :     /* Empty previous contents */
        2790         [ -  + ]:      14580 :     if (self->ob_item != NULL) {
        2791                 :          0 :         (void)_list_clear(self);
        2792                 :            :     }
        2793         [ +  + ]:      14580 :     if (iterable != NULL) {
        2794                 :      14562 :         PyObject *rv = list_extend(self, iterable);
        2795         [ -  + ]:      14562 :         if (rv == NULL)
        2796                 :          0 :             return -1;
        2797                 :      14562 :         Py_DECREF(rv);
        2798                 :            :     }
        2799                 :      14580 :     return 0;
        2800                 :            : }
        2801                 :            :
        2802                 :            : static PyObject *
        2803                 :      14562 : list_vectorcall(PyObject *type, PyObject * const*args,
        2804                 :            :                 size_t nargsf, PyObject *kwnames)
        2805                 :            : {
        2806   [ -  +  -  - ]:      14562 :     if (!_PyArg_NoKwnames("list", kwnames)) {
        2807                 :          0 :         return NULL;
        2808                 :            :     }
        2809                 :      14562 :     Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);
        2810   [ +  -  -  +  :      14562 :     if (!_PyArg_CheckPositional("list", nargs, 0, 1)) {
                       -  - ]
        2811                 :          0 :         return NULL;
        2812                 :            :     }
        2813                 :            :
        2814                 :      14562 :     PyObject *list = PyType_GenericAlloc(_PyType_CAST(type), 0);
        2815         [ -  + ]:      14562 :     if (list == NULL) {
        2816                 :          0 :         return NULL;
        2817                 :            :     }
        2818         [ +  - ]:      14562 :     if (nargs) {
        2819         [ -  + ]:      14562 :         if (list___init___impl((PyListObject *)list, args[0])) {
        2820                 :          0 :             Py_DECREF(list);
        2821                 :          0 :             return NULL;
        2822                 :            :         }
        2823                 :            :     }
        2824                 :      14562 :     return list;
        2825                 :            : }
        2826                 :            :
        2827                 :            :
        2828                 :            : /*[clinic input]
        2829                 :            : list.__sizeof__
        2830                 :            :
        2831                 :            : Return the size of the list in memory, in bytes.
        2832                 :            : [clinic start generated code]*/
        2833                 :            :
        2834                 :            : static PyObject *
        2835                 :          0 : list___sizeof___impl(PyListObject *self)
        2836                 :            : /*[clinic end generated code: output=3417541f95f9a53e input=b8030a5d5ce8a187]*/
        2837                 :            : {
        2838                 :          0 :     size_t res = _PyObject_SIZE(Py_TYPE(self));
        2839                 :          0 :     res += (size_t)self->allocated * sizeof(void*);
        2840                 :          0 :     return PyLong_FromSize_t(res);
        2841                 :            : }
        2842                 :            :
        2843                 :            : static PyObject *list_iter(PyObject *seq);
        2844                 :            : static PyObject *list_subscript(PyListObject*, PyObject*);
        2845                 :            :
        2846                 :            : static PyMethodDef list_methods[] = {
        2847                 :            :     {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST,
        2848                 :            :      PyDoc_STR("__getitem__($self, index, /)\n--\n\nReturn self[index].")},
        2849                 :            :     LIST___REVERSED___METHODDEF
        2850                 :            :     LIST___SIZEOF___METHODDEF
        2851                 :            :     LIST_CLEAR_METHODDEF
        2852                 :            :     LIST_COPY_METHODDEF
        2853                 :            :     LIST_APPEND_METHODDEF
        2854                 :            :     LIST_INSERT_METHODDEF
        2855                 :            :     LIST_EXTEND_METHODDEF
        2856                 :            :     LIST_POP_METHODDEF
        2857                 :            :     LIST_REMOVE_METHODDEF
        2858                 :            :     LIST_INDEX_METHODDEF
        2859                 :            :     LIST_COUNT_METHODDEF
        2860                 :            :     LIST_REVERSE_METHODDEF
        2861                 :            :     LIST_SORT_METHODDEF
        2862                 :            :     {"__class_getitem__", Py_GenericAlias, METH_O|METH_CLASS, PyDoc_STR("See PEP 585")},
        2863                 :            :     {NULL,              NULL}           /* sentinel */
        2864                 :            : };
        2865                 :            :
        2866                 :            : static PySequenceMethods list_as_sequence = {
        2867                 :            :     (lenfunc)list_length,                       /* sq_length */
        2868                 :            :     (binaryfunc)list_concat,                    /* sq_concat */
        2869                 :            :     (ssizeargfunc)list_repeat,                  /* sq_repeat */
        2870                 :            :     (ssizeargfunc)list_item,                    /* sq_item */
        2871                 :            :     0,                                          /* sq_slice */
        2872                 :            :     (ssizeobjargproc)list_ass_item,             /* sq_ass_item */
        2873                 :            :     0,                                          /* sq_ass_slice */
        2874                 :            :     (objobjproc)list_contains,                  /* sq_contains */
        2875                 :            :     (binaryfunc)list_inplace_concat,            /* sq_inplace_concat */
        2876                 :            :     (ssizeargfunc)list_inplace_repeat,          /* sq_inplace_repeat */
        2877                 :            : };
        2878                 :            :
        2879                 :            : static PyObject *
        2880                 :       4049 : list_subscript(PyListObject* self, PyObject* item)
        2881                 :            : {
        2882         [ +  + ]:       4049 :     if (_PyIndex_Check(item)) {
        2883                 :            :         Py_ssize_t i;
        2884                 :       1027 :         i = PyNumber_AsSsize_t(item, PyExc_IndexError);
        2885   [ +  +  -  + ]:       1027 :         if (i == -1 && PyErr_Occurred())
        2886                 :          0 :             return NULL;
        2887         [ +  + ]:       1027 :         if (i < 0)
        2888                 :        283 :             i += PyList_GET_SIZE(self);
        2889                 :       1027 :         return list_item(self, i);
        2890                 :            :     }
        2891         [ +  - ]:       3022 :     else if (PySlice_Check(item)) {
        2892                 :            :         Py_ssize_t start, stop, step, slicelength, i;
        2893                 :            :         size_t cur;
        2894                 :            :         PyObject* result;
        2895                 :            :         PyObject* it;
        2896                 :            :         PyObject **src, **dest;
        2897                 :            :
        2898         [ -  + ]:       3022 :         if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
        2899                 :          0 :             return NULL;
        2900                 :            :         }
        2901                 :       3022 :         slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
        2902                 :            :                                             step);
        2903                 :            :
        2904         [ +  + ]:       3022 :         if (slicelength <= 0) {
        2905                 :       2373 :             return PyList_New(0);
        2906                 :            :         }
        2907         [ +  - ]:        649 :         else if (step == 1) {
        2908                 :        649 :             return list_slice(self, start, stop);
        2909                 :            :         }
        2910                 :            :         else {
        2911                 :          0 :             result = list_new_prealloc(slicelength);
        2912         [ #  # ]:          0 :             if (!result) return NULL;
        2913                 :            :
        2914                 :          0 :             src = self->ob_item;
        2915                 :          0 :             dest = ((PyListObject *)result)->ob_item;
        2916         [ #  # ]:          0 :             for (cur = start, i = 0; i < slicelength;
        2917                 :          0 :                  cur += (size_t)step, i++) {
        2918                 :          0 :                 it = Py_NewRef(src[cur]);
        2919                 :          0 :                 dest[i] = it;
        2920                 :            :             }
        2921                 :          0 :             Py_SET_SIZE(result, slicelength);
        2922                 :          0 :             return result;
        2923                 :            :         }
        2924                 :            :     }
        2925                 :            :     else {
        2926                 :          0 :         PyErr_Format(PyExc_TypeError,
        2927                 :            :                      "list indices must be integers or slices, not %.200s",
        2928                 :          0 :                      Py_TYPE(item)->tp_name);
        2929                 :          0 :         return NULL;
        2930                 :            :     }
        2931                 :            : }
        2932                 :            :
        2933                 :            : static int
        2934                 :        470 : list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
        2935                 :            : {
        2936         [ +  + ]:        470 :     if (_PyIndex_Check(item)) {
        2937                 :        420 :         Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
        2938   [ +  +  -  + ]:        420 :         if (i == -1 && PyErr_Occurred())
        2939                 :          0 :             return -1;
        2940         [ +  + ]:        420 :         if (i < 0)
        2941                 :        311 :             i += PyList_GET_SIZE(self);
        2942                 :        420 :         return list_ass_item(self, i, value);
        2943                 :            :     }
        2944         [ +  - ]:         50 :     else if (PySlice_Check(item)) {
        2945                 :            :         Py_ssize_t start, stop, step, slicelength;
        2946                 :            :
        2947         [ -  + ]:         50 :         if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
        2948                 :          0 :             return -1;
        2949                 :            :         }
        2950                 :         50 :         slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
        2951                 :            :                                             step);
        2952                 :            :
        2953         [ +  - ]:         50 :         if (step == 1)
        2954                 :         50 :             return list_ass_slice(self, start, stop, value);
        2955                 :            :
        2956                 :            :         /* Make sure s[5:2] = [..] inserts at the right place:
        2957                 :            :            before 5, not before 2. */
        2958   [ #  #  #  # ]:          0 :         if ((step < 0 && start < stop) ||
        2959   [ #  #  #  # ]:          0 :             (step > 0 && start > stop))
        2960                 :          0 :             stop = start;
        2961                 :            :
        2962         [ #  # ]:          0 :         if (value == NULL) {
        2963                 :            :             /* delete slice */
        2964                 :            :             PyObject **garbage;
        2965                 :            :             size_t cur;
        2966                 :            :             Py_ssize_t i;
        2967                 :            :             int res;
        2968                 :            :
        2969         [ #  # ]:          0 :             if (slicelength <= 0)
        2970                 :          0 :                 return 0;
        2971                 :            :
        2972         [ #  # ]:          0 :             if (step < 0) {
        2973                 :          0 :                 stop = start + 1;
        2974                 :          0 :                 start = stop + step*(slicelength - 1) - 1;
        2975                 :          0 :                 step = -step;
        2976                 :            :             }
        2977                 :            :
        2978                 :            :             garbage = (PyObject**)
        2979                 :          0 :                 PyMem_Malloc(slicelength*sizeof(PyObject*));
        2980         [ #  # ]:          0 :             if (!garbage) {
        2981                 :          0 :                 PyErr_NoMemory();
        2982                 :          0 :                 return -1;
        2983                 :            :             }
        2984                 :            :
        2985                 :            :             /* drawing pictures might help understand these for
        2986                 :            :                loops. Basically, we memmove the parts of the
        2987                 :            :                list that are *not* part of the slice: step-1
        2988                 :            :                items for each item that is part of the slice,
        2989                 :            :                and then tail end of the list that was not
        2990                 :            :                covered by the slice */
        2991                 :          0 :             for (cur = start, i = 0;
        2992         [ #  # ]:          0 :                  cur < (size_t)stop;
        2993                 :          0 :                  cur += step, i++) {
        2994                 :          0 :                 Py_ssize_t lim = step - 1;
        2995                 :            :
        2996                 :          0 :                 garbage[i] = PyList_GET_ITEM(self, cur);
        2997                 :            :
        2998         [ #  # ]:          0 :                 if (cur + step >= (size_t)Py_SIZE(self)) {
        2999                 :          0 :                     lim = Py_SIZE(self) - cur - 1;
        3000                 :            :                 }
        3001                 :            :
        3002                 :          0 :                 memmove(self->ob_item + cur - i,
        3003                 :          0 :                     self->ob_item + cur + 1,
        3004                 :            :                     lim * sizeof(PyObject *));
        3005                 :            :             }
        3006                 :          0 :             cur = start + (size_t)slicelength * step;
        3007         [ #  # ]:          0 :             if (cur < (size_t)Py_SIZE(self)) {
        3008                 :          0 :                 memmove(self->ob_item + cur - slicelength,
        3009                 :          0 :                     self->ob_item + cur,
        3010                 :          0 :                     (Py_SIZE(self) - cur) *
        3011                 :            :                      sizeof(PyObject *));
        3012                 :            :             }
        3013                 :            :
        3014                 :          0 :             Py_SET_SIZE(self, Py_SIZE(self) - slicelength);
        3015                 :          0 :             res = list_resize(self, Py_SIZE(self));
        3016                 :            :
        3017         [ #  # ]:          0 :             for (i = 0; i < slicelength; i++) {
        3018                 :          0 :                 Py_DECREF(garbage[i]);
        3019                 :            :             }
        3020                 :          0 :             PyMem_Free(garbage);
        3021                 :            :
        3022                 :          0 :             return res;
        3023                 :            :         }
        3024                 :            :         else {
        3025                 :            :             /* assign slice */
        3026                 :            :             PyObject *ins, *seq;
        3027                 :            :             PyObject **garbage, **seqitems, **selfitems;
        3028                 :            :             Py_ssize_t i;
        3029                 :            :             size_t cur;
        3030                 :            :
        3031                 :            :             /* protect against a[::-1] = a */
        3032         [ #  # ]:          0 :             if (self == (PyListObject*)value) {
        3033                 :          0 :                 seq = list_slice((PyListObject*)value, 0,
        3034                 :            :                                    PyList_GET_SIZE(value));
        3035                 :            :             }
        3036                 :            :             else {
        3037                 :          0 :                 seq = PySequence_Fast(value,
        3038                 :            :                                       "must assign iterable "
        3039                 :            :                                       "to extended slice");
        3040                 :            :             }
        3041         [ #  # ]:          0 :             if (!seq)
        3042                 :          0 :                 return -1;
        3043                 :            :
        3044   [ #  #  #  # ]:          0 :             if (PySequence_Fast_GET_SIZE(seq) != slicelength) {
        3045         [ #  # ]:          0 :                 PyErr_Format(PyExc_ValueError,
        3046                 :            :                     "attempt to assign sequence of "
        3047                 :            :                     "size %zd to extended slice of "
        3048                 :            :                     "size %zd",
        3049                 :          0 :                          PySequence_Fast_GET_SIZE(seq),
        3050                 :            :                          slicelength);
        3051                 :          0 :                 Py_DECREF(seq);
        3052                 :          0 :                 return -1;
        3053                 :            :             }
        3054                 :            :
        3055         [ #  # ]:          0 :             if (!slicelength) {
        3056                 :          0 :                 Py_DECREF(seq);
        3057                 :          0 :                 return 0;
        3058                 :            :             }
        3059                 :            :
        3060                 :            :             garbage = (PyObject**)
        3061                 :          0 :                 PyMem_Malloc(slicelength*sizeof(PyObject*));
        3062         [ #  # ]:          0 :             if (!garbage) {
        3063                 :          0 :                 Py_DECREF(seq);
        3064                 :          0 :                 PyErr_NoMemory();
        3065                 :          0 :                 return -1;
        3066                 :            :             }
        3067                 :            :
        3068                 :          0 :             selfitems = self->ob_item;
        3069         [ #  # ]:          0 :             seqitems = PySequence_Fast_ITEMS(seq);
        3070         [ #  # ]:          0 :             for (cur = start, i = 0; i < slicelength;
        3071                 :          0 :                  cur += (size_t)step, i++) {
        3072                 :          0 :                 garbage[i] = selfitems[cur];
        3073                 :          0 :                 ins = Py_NewRef(seqitems[i]);
        3074                 :          0 :                 selfitems[cur] = ins;
        3075                 :            :             }
        3076                 :            :
        3077         [ #  # ]:          0 :             for (i = 0; i < slicelength; i++) {
        3078                 :          0 :                 Py_DECREF(garbage[i]);
        3079                 :            :             }
        3080                 :            :
        3081                 :          0 :             PyMem_Free(garbage);
        3082                 :          0 :             Py_DECREF(seq);
        3083                 :            :
        3084                 :          0 :             return 0;
        3085                 :            :         }
        3086                 :            :     }
        3087                 :            :     else {
        3088                 :          0 :         PyErr_Format(PyExc_TypeError,
        3089                 :            :                      "list indices must be integers or slices, not %.200s",
        3090                 :          0 :                      Py_TYPE(item)->tp_name);
        3091                 :          0 :         return -1;
        3092                 :            :     }
        3093                 :            : }
        3094                 :            :
        3095                 :            : static PyMappingMethods list_as_mapping = {
        3096                 :            :     (lenfunc)list_length,
        3097                 :            :     (binaryfunc)list_subscript,
        3098                 :            :     (objobjargproc)list_ass_subscript
        3099                 :            : };
        3100                 :            :
        3101                 :            : PyTypeObject PyList_Type = {
        3102                 :            :     PyVarObject_HEAD_INIT(&PyType_Type, 0)
        3103                 :            :     "list",
        3104                 :            :     sizeof(PyListObject),
        3105                 :            :     0,
        3106                 :            :     (destructor)list_dealloc,                   /* tp_dealloc */
        3107                 :            :     0,                                          /* tp_vectorcall_offset */
        3108                 :            :     0,                                          /* tp_getattr */
        3109                 :            :     0,                                          /* tp_setattr */
        3110                 :            :     0,                                          /* tp_as_async */
        3111                 :            :     (reprfunc)list_repr,                        /* tp_repr */
        3112                 :            :     0,                                          /* tp_as_number */
        3113                 :            :     &list_as_sequence,                          /* tp_as_sequence */
        3114                 :            :     &list_as_mapping,                           /* tp_as_mapping */
        3115                 :            :     PyObject_HashNotImplemented,                /* tp_hash */
        3116                 :            :     0,                                          /* tp_call */
        3117                 :            :     0,                                          /* tp_str */
        3118                 :            :     PyObject_GenericGetAttr,                    /* tp_getattro */
        3119                 :            :     0,                                          /* tp_setattro */
        3120                 :            :     0,                                          /* tp_as_buffer */
        3121                 :            :     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
        3122                 :            :         Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS |
        3123                 :            :         _Py_TPFLAGS_MATCH_SELF | Py_TPFLAGS_SEQUENCE,  /* tp_flags */
        3124                 :            :     list___init____doc__,                       /* tp_doc */
        3125                 :            :     (traverseproc)list_traverse,                /* tp_traverse */
        3126                 :            :     (inquiry)_list_clear,                       /* tp_clear */
        3127                 :            :     list_richcompare,                           /* tp_richcompare */
        3128                 :            :     0,                                          /* tp_weaklistoffset */
        3129                 :            :     list_iter,                                  /* tp_iter */
        3130                 :            :     0,                                          /* tp_iternext */
        3131                 :            :     list_methods,                               /* tp_methods */
        3132                 :            :     0,                                          /* tp_members */
        3133                 :            :     0,                                          /* tp_getset */
        3134                 :            :     0,                                          /* tp_base */
        3135                 :            :     0,                                          /* tp_dict */
        3136                 :            :     0,                                          /* tp_descr_get */
        3137                 :            :     0,                                          /* tp_descr_set */
        3138                 :            :     0,                                          /* tp_dictoffset */
        3139                 :            :     (initproc)list___init__,                    /* tp_init */
        3140                 :            :     PyType_GenericAlloc,                        /* tp_alloc */
        3141                 :            :     PyType_GenericNew,                          /* tp_new */
        3142                 :            :     PyObject_GC_Del,                            /* tp_free */
        3143                 :            :     .tp_vectorcall = list_vectorcall,
        3144                 :            : };
        3145                 :            :
        3146                 :            : /*********************** List Iterator **************************/
        3147                 :            :
        3148                 :            : static void listiter_dealloc(_PyListIterObject *);
        3149                 :            : static int listiter_traverse(_PyListIterObject *, visitproc, void *);
        3150                 :            : static PyObject *listiter_next(_PyListIterObject *);
        3151                 :            : static PyObject *listiter_len(_PyListIterObject *, PyObject *);
        3152                 :            : static PyObject *listiter_reduce_general(void *_it, int forward);
        3153                 :            : static PyObject *listiter_reduce(_PyListIterObject *, PyObject *);
        3154                 :            : static PyObject *listiter_setstate(_PyListIterObject *, PyObject *state);
        3155                 :            :
        3156                 :            : PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
        3157                 :            : PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
        3158                 :            : PyDoc_STRVAR(setstate_doc, "Set state information for unpickling.");
        3159                 :            :
        3160                 :            : static PyMethodDef listiter_methods[] = {
        3161                 :            :     {"__length_hint__", (PyCFunction)listiter_len, METH_NOARGS, length_hint_doc},
        3162                 :            :     {"__reduce__", (PyCFunction)listiter_reduce, METH_NOARGS, reduce_doc},
        3163                 :            :     {"__setstate__", (PyCFunction)listiter_setstate, METH_O, setstate_doc},
        3164                 :            :     {NULL,              NULL}           /* sentinel */
        3165                 :            : };
        3166                 :            :
        3167                 :            : PyTypeObject PyListIter_Type = {
        3168                 :            :     PyVarObject_HEAD_INIT(&PyType_Type, 0)
        3169                 :            :     "list_iterator",                            /* tp_name */
        3170                 :            :     sizeof(_PyListIterObject),                  /* tp_basicsize */
        3171                 :            :     0,                                          /* tp_itemsize */
        3172                 :            :     /* methods */
        3173                 :            :     (destructor)listiter_dealloc,               /* tp_dealloc */
        3174                 :            :     0,                                          /* tp_vectorcall_offset */
        3175                 :            :     0,                                          /* tp_getattr */
        3176                 :            :     0,                                          /* tp_setattr */
        3177                 :            :     0,                                          /* tp_as_async */
        3178                 :            :     0,                                          /* tp_repr */
        3179                 :            :     0,                                          /* tp_as_number */
        3180                 :            :     0,                                          /* tp_as_sequence */
        3181                 :            :     0,                                          /* tp_as_mapping */
        3182                 :            :     0,                                          /* tp_hash */
        3183                 :            :     0,                                          /* tp_call */
        3184                 :            :     0,                                          /* tp_str */
        3185                 :            :     PyObject_GenericGetAttr,                    /* tp_getattro */
        3186                 :            :     0,                                          /* tp_setattro */
        3187                 :            :     0,                                          /* tp_as_buffer */
        3188                 :            :     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
        3189                 :            :     0,                                          /* tp_doc */
        3190                 :            :     (traverseproc)listiter_traverse,            /* tp_traverse */
        3191                 :            :     0,                                          /* tp_clear */
        3192                 :            :     0,                                          /* tp_richcompare */
        3193                 :            :     0,                                          /* tp_weaklistoffset */
        3194                 :            :     PyObject_SelfIter,                          /* tp_iter */
        3195                 :            :     (iternextfunc)listiter_next,                /* tp_iternext */
        3196                 :            :     listiter_methods,                           /* tp_methods */
        3197                 :            :     0,                                          /* tp_members */
        3198                 :            : };
        3199                 :            :
        3200                 :            :
        3201                 :            : static PyObject *
        3202                 :     160150 : list_iter(PyObject *seq)
        3203                 :            : {
        3204                 :            :     _PyListIterObject *it;
        3205                 :            :
        3206         [ -  + ]:     160150 :     if (!PyList_Check(seq)) {
        3207                 :          0 :         PyErr_BadInternalCall();
        3208                 :          0 :         return NULL;
        3209                 :            :     }
        3210                 :     160150 :     it = PyObject_GC_New(_PyListIterObject, &PyListIter_Type);
        3211         [ -  + ]:     160150 :     if (it == NULL)
        3212                 :          0 :         return NULL;
        3213                 :     160150 :     it->it_index = 0;
        3214                 :     160150 :     it->it_seq = (PyListObject *)Py_NewRef(seq);
        3215                 :     160150 :     _PyObject_GC_TRACK(it);
        3216                 :     160150 :     return (PyObject *)it;
        3217                 :            : }
        3218                 :            :
        3219                 :            : static void
        3220                 :     160150 : listiter_dealloc(_PyListIterObject *it)
        3221                 :            : {
        3222                 :     160150 :     _PyObject_GC_UNTRACK(it);
        3223                 :     160150 :     Py_XDECREF(it->it_seq);
        3224                 :     160150 :     PyObject_GC_Del(it);
        3225                 :     160150 : }
        3226                 :            :
        3227                 :            : static int
        3228                 :         46 : listiter_traverse(_PyListIterObject *it, visitproc visit, void *arg)
        3229                 :            : {
        3230   [ +  -  -  + ]:         46 :     Py_VISIT(it->it_seq);
        3231                 :         46 :     return 0;
        3232                 :            : }
        3233                 :            :
        3234                 :            : static PyObject *
        3235                 :    1022438 : listiter_next(_PyListIterObject *it)
        3236                 :            : {
        3237                 :            :     PyListObject *seq;
        3238                 :            :     PyObject *item;
        3239                 :            :
        3240                 :            :     assert(it != NULL);
        3241                 :    1022438 :     seq = it->it_seq;
        3242         [ -  + ]:    1022438 :     if (seq == NULL)
        3243                 :          0 :         return NULL;
        3244                 :            :     assert(PyList_Check(seq));
        3245                 :            :
        3246         [ +  + ]:    1022438 :     if (it->it_index < PyList_GET_SIZE(seq)) {
        3247                 :     985537 :         item = PyList_GET_ITEM(seq, it->it_index);
        3248                 :     985537 :         ++it->it_index;
        3249                 :     985537 :         return Py_NewRef(item);
        3250                 :            :     }
        3251                 :            :
        3252                 :      36901 :     it->it_seq = NULL;
        3253                 :      36901 :     Py_DECREF(seq);
        3254                 :      36901 :     return NULL;
        3255                 :            : }
        3256                 :            :
        3257                 :            : static PyObject *
        3258                 :        103 : listiter_len(_PyListIterObject *it, PyObject *Py_UNUSED(ignored))
        3259                 :            : {
        3260                 :            :     Py_ssize_t len;
        3261         [ +  - ]:        103 :     if (it->it_seq) {
        3262                 :        103 :         len = PyList_GET_SIZE(it->it_seq) - it->it_index;
        3263         [ +  - ]:        103 :         if (len >= 0)
        3264                 :        103 :             return PyLong_FromSsize_t(len);
        3265                 :            :     }
        3266                 :          0 :     return PyLong_FromLong(0);
        3267                 :            : }
        3268                 :            :
        3269                 :            : static PyObject *
        3270                 :          0 : listiter_reduce(_PyListIterObject *it, PyObject *Py_UNUSED(ignored))
        3271                 :            : {
        3272                 :          0 :     return listiter_reduce_general(it, 1);
        3273                 :            : }
        3274                 :            :
        3275                 :            : static PyObject *
        3276                 :          0 : listiter_setstate(_PyListIterObject *it, PyObject *state)
        3277                 :            : {
        3278                 :          0 :     Py_ssize_t index = PyLong_AsSsize_t(state);
        3279   [ #  #  #  # ]:          0 :     if (index == -1 && PyErr_Occurred())
        3280                 :          0 :         return NULL;
        3281         [ #  # ]:          0 :     if (it->it_seq != NULL) {
        3282         [ #  # ]:          0 :         if (index < 0)
        3283                 :          0 :             index = 0;
        3284         [ #  # ]:          0 :         else if (index > PyList_GET_SIZE(it->it_seq))
        3285                 :          0 :             index = PyList_GET_SIZE(it->it_seq); /* iterator exhausted */
        3286                 :          0 :         it->it_index = index;
        3287                 :            :     }
        3288                 :          0 :     Py_RETURN_NONE;
        3289                 :            : }
        3290                 :            :
        3291                 :            : /*********************** List Reverse Iterator **************************/
        3292                 :            :
        3293                 :            : typedef struct {
        3294                 :            :     PyObject_HEAD
        3295                 :            :     Py_ssize_t it_index;
        3296                 :            :     PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
        3297                 :            : } listreviterobject;
        3298                 :            :
        3299                 :            : static void listreviter_dealloc(listreviterobject *);
        3300                 :            : static int listreviter_traverse(listreviterobject *, visitproc, void *);
        3301                 :            : static PyObject *listreviter_next(listreviterobject *);
        3302                 :            : static PyObject *listreviter_len(listreviterobject *, PyObject *);
        3303                 :            : static PyObject *listreviter_reduce(listreviterobject *, PyObject *);
        3304                 :            : static PyObject *listreviter_setstate(listreviterobject *, PyObject *);
        3305                 :            :
        3306                 :            : static PyMethodDef listreviter_methods[] = {
        3307                 :            :     {"__length_hint__", (PyCFunction)listreviter_len, METH_NOARGS, length_hint_doc},
        3308                 :            :     {"__reduce__", (PyCFunction)listreviter_reduce, METH_NOARGS, reduce_doc},
        3309                 :            :     {"__setstate__", (PyCFunction)listreviter_setstate, METH_O, setstate_doc},
        3310                 :            :     {NULL,              NULL}           /* sentinel */
        3311                 :            : };
        3312                 :            :
        3313                 :            : PyTypeObject PyListRevIter_Type = {
        3314                 :            :     PyVarObject_HEAD_INIT(&PyType_Type, 0)
        3315                 :            :     "list_reverseiterator",                     /* tp_name */
        3316                 :            :     sizeof(listreviterobject),                  /* tp_basicsize */
        3317                 :            :     0,                                          /* tp_itemsize */
        3318                 :            :     /* methods */
        3319                 :            :     (destructor)listreviter_dealloc,            /* tp_dealloc */
        3320                 :            :     0,                                          /* tp_vectorcall_offset */
        3321                 :            :     0,                                          /* tp_getattr */
        3322                 :            :     0,                                          /* tp_setattr */
        3323                 :            :     0,                                          /* tp_as_async */
        3324                 :            :     0,                                          /* tp_repr */
        3325                 :            :     0,                                          /* tp_as_number */
        3326                 :            :     0,                                          /* tp_as_sequence */
        3327                 :            :     0,                                          /* tp_as_mapping */
        3328                 :            :     0,                                          /* tp_hash */
        3329                 :            :     0,                                          /* tp_call */
        3330                 :            :     0,                                          /* tp_str */
        3331                 :            :     PyObject_GenericGetAttr,                    /* tp_getattro */
        3332                 :            :     0,                                          /* tp_setattro */
        3333                 :            :     0,                                          /* tp_as_buffer */
        3334                 :            :     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
        3335                 :            :     0,                                          /* tp_doc */
        3336                 :            :     (traverseproc)listreviter_traverse,         /* tp_traverse */
        3337                 :            :     0,                                          /* tp_clear */
        3338                 :            :     0,                                          /* tp_richcompare */
        3339                 :            :     0,                                          /* tp_weaklistoffset */
        3340                 :            :     PyObject_SelfIter,                          /* tp_iter */
        3341                 :            :     (iternextfunc)listreviter_next,             /* tp_iternext */
        3342                 :            :     listreviter_methods,                /* tp_methods */
        3343                 :            :     0,
        3344                 :            : };
        3345                 :            :
        3346                 :            : /*[clinic input]
        3347                 :            : list.__reversed__
        3348                 :            :
        3349                 :            : Return a reverse iterator over the list.
        3350                 :            : [clinic start generated code]*/
        3351                 :            :
        3352                 :            : static PyObject *
        3353                 :        268 : list___reversed___impl(PyListObject *self)
        3354                 :            : /*[clinic end generated code: output=b166f073208c888c input=eadb6e17f8a6a280]*/
        3355                 :            : {
        3356                 :            :     listreviterobject *it;
        3357                 :            :
        3358                 :        268 :     it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type);
        3359         [ -  + ]:        268 :     if (it == NULL)
        3360                 :          0 :         return NULL;
        3361                 :            :     assert(PyList_Check(self));
        3362                 :        268 :     it->it_index = PyList_GET_SIZE(self) - 1;
        3363                 :        268 :     it->it_seq = (PyListObject*)Py_NewRef(self);
        3364                 :        268 :     PyObject_GC_Track(it);
        3365                 :        268 :     return (PyObject *)it;
        3366                 :            : }
        3367                 :            :
        3368                 :            : static void
        3369                 :        268 : listreviter_dealloc(listreviterobject *it)
        3370                 :            : {
        3371                 :        268 :     PyObject_GC_UnTrack(it);
        3372                 :        268 :     Py_XDECREF(it->it_seq);
        3373                 :        268 :     PyObject_GC_Del(it);
        3374                 :        268 : }
        3375                 :            :
        3376                 :            : static int
        3377                 :          0 : listreviter_traverse(listreviterobject *it, visitproc visit, void *arg)
        3378                 :            : {
        3379   [ #  #  #  # ]:          0 :     Py_VISIT(it->it_seq);
        3380                 :          0 :     return 0;
        3381                 :            : }
        3382                 :            :
        3383                 :            : static PyObject *
        3384                 :        360 : listreviter_next(listreviterobject *it)
        3385                 :            : {
        3386                 :            :     PyObject *item;
        3387                 :            :     Py_ssize_t index;
        3388                 :            :     PyListObject *seq;
        3389                 :            :
        3390                 :            :     assert(it != NULL);
        3391                 :        360 :     seq = it->it_seq;
        3392         [ -  + ]:        360 :     if (seq == NULL) {
        3393                 :          0 :         return NULL;
        3394                 :            :     }
        3395                 :            :     assert(PyList_Check(seq));
        3396                 :            :
        3397                 :        360 :     index = it->it_index;
        3398   [ +  +  +  - ]:        360 :     if (index>=0 && index < PyList_GET_SIZE(seq)) {
        3399                 :        122 :         item = PyList_GET_ITEM(seq, index);
        3400                 :        122 :         it->it_index--;
        3401                 :        122 :         return Py_NewRef(item);
        3402                 :            :     }
        3403                 :        238 :     it->it_index = -1;
        3404                 :        238 :     it->it_seq = NULL;
        3405                 :        238 :     Py_DECREF(seq);
        3406                 :        238 :     return NULL;
        3407                 :            : }
        3408                 :            :
        3409                 :            : static PyObject *
        3410                 :          0 : listreviter_len(listreviterobject *it, PyObject *Py_UNUSED(ignored))
        3411                 :            : {
        3412                 :          0 :     Py_ssize_t len = it->it_index + 1;
        3413   [ #  #  #  # ]:          0 :     if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len)
        3414                 :          0 :         len = 0;
        3415                 :          0 :     return PyLong_FromSsize_t(len);
        3416                 :            : }
        3417                 :            :
        3418                 :            : static PyObject *
        3419                 :          0 : listreviter_reduce(listreviterobject *it, PyObject *Py_UNUSED(ignored))
        3420                 :            : {
        3421                 :          0 :     return listiter_reduce_general(it, 0);
        3422                 :            : }
        3423                 :            :
        3424                 :            : static PyObject *
        3425                 :          0 : listreviter_setstate(listreviterobject *it, PyObject *state)
        3426                 :            : {
        3427                 :          0 :     Py_ssize_t index = PyLong_AsSsize_t(state);
        3428   [ #  #  #  # ]:          0 :     if (index == -1 && PyErr_Occurred())
        3429                 :          0 :         return NULL;
        3430         [ #  # ]:          0 :     if (it->it_seq != NULL) {
        3431         [ #  # ]:          0 :         if (index < -1)
        3432                 :          0 :             index = -1;
        3433         [ #  # ]:          0 :         else if (index > PyList_GET_SIZE(it->it_seq) - 1)
        3434                 :          0 :             index = PyList_GET_SIZE(it->it_seq) - 1;
        3435                 :          0 :         it->it_index = index;
        3436                 :            :     }
        3437                 :          0 :     Py_RETURN_NONE;
        3438                 :            : }
        3439                 :            :
        3440                 :            : /* common pickling support */
        3441                 :            :
        3442                 :            : static PyObject *
        3443                 :          0 : listiter_reduce_general(void *_it, int forward)
        3444                 :            : {
        3445                 :            :     PyObject *list;
        3446                 :            :
        3447                 :            :     /* _PyEval_GetBuiltin can invoke arbitrary code,
        3448                 :            :      * call must be before access of iterator pointers.
        3449                 :            :      * see issue #101765 */
        3450                 :            :
        3451                 :            :     /* the objects are not the same, index is of different types! */
        3452         [ #  # ]:          0 :     if (forward) {
        3453                 :          0 :         PyObject *iter = _PyEval_GetBuiltin(&_Py_ID(iter));
        3454         [ #  # ]:          0 :         if (!iter) {
        3455                 :          0 :             return NULL;
        3456                 :            :         }
        3457                 :          0 :         _PyListIterObject *it = (_PyListIterObject *)_it;
        3458         [ #  # ]:          0 :         if (it->it_seq) {
        3459                 :          0 :             return Py_BuildValue("N(O)n", iter, it->it_seq, it->it_index);
        3460                 :            :         }
        3461                 :          0 :         Py_DECREF(iter);
        3462                 :            :     } else {
        3463                 :          0 :         PyObject *reversed = _PyEval_GetBuiltin(&_Py_ID(reversed));
        3464         [ #  # ]:          0 :         if (!reversed) {
        3465                 :          0 :             return NULL;
        3466                 :            :         }
        3467                 :          0 :         listreviterobject *it = (listreviterobject *)_it;
        3468         [ #  # ]:          0 :         if (it->it_seq) {
        3469                 :          0 :             return Py_BuildValue("N(O)n", reversed, it->it_seq, it->it_index);
        3470                 :            :         }
        3471                 :          0 :         Py_DECREF(reversed);
        3472                 :            :     }
        3473                 :            :     /* empty iterator, create an empty list */
        3474                 :          0 :     list = PyList_New(0);
        3475         [ #  # ]:          0 :     if (list == NULL)
        3476                 :          0 :         return NULL;
        3477                 :          0 :     return Py_BuildValue("N(N)", _PyEval_GetBuiltin(&_Py_ID(iter)), list);
        3478                 :            : }

Generated by: LCOV version 1.14