/* List object implementation */

#include "Python.h"

#include "pycore_abstract.h" // _PyIndex_Check()

#include "pycore_object.h"

#include "pycore_tupleobject.h"

#include "pycore_accu.h"

#ifdef STDC_HEADERS

#include <stddef.h>

#else

#include <sys/types.h> /* For size_t */

#endif

/*[clinic input]

class list "PyListObject *" "&PyList_Type"

[clinic start generated code]*/

/*[clinic end generated code: output=da39a3ee5e6b4b0d input=f9b222678f9f71e0]*/

#include "clinic/listobject.c.h"

/* Ensure ob_item has room for at least newsize elements, and set

* ob_size to newsize. If newsize > ob_size on entry, the content

* of the new slots at exit is undefined heap trash; it's the caller's

* responsibility to overwrite them with sane values.

* The number of allocated elements may grow, shrink, or stay the same.

* Failure is impossible if newsize <= self.allocated on entry, although

* that partly relies on an assumption that the system realloc() never

* fails when passed a number of bytes <= the number of bytes last

* allocated (the C standard doesn't guarantee this, but it's hard to

* imagine a realloc implementation where it wouldn't be true).

* Note that self->ob_item may change, and even if newsize is less

* than ob_size on entry.

*/

static int

list_resize(PyListObject *self, Py_ssize_t newsize)

{

PyObject **items;

size_t new_allocated, num_allocated_bytes;

Py_ssize_t allocated = self->allocated;

/* Bypass realloc() when a previous overallocation is large enough

to accommodate the newsize. If the newsize falls lower than half

the allocated size, then proceed with the realloc() to shrink the list.

*/

if (allocated >= newsize && newsize >= (allocated >> 1)) {

assert(self->ob_item != NULL || newsize == 0);

Py_SET_SIZE(self, newsize);

return 0;

}

/* This over-allocates proportional to the list size, making room

* for additional growth. The over-allocation is mild, but is

* enough to give linear-time amortized behavior over a long

* sequence of appends() in the presence of a poorly-performing

* system realloc().

* Add padding to make the allocated size multiple of 4.

* The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...

* Note: new_allocated won't overflow because the largest possible value

* is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.

*/

new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

/* Do not overallocate if the new size is closer to overalocated size

* than to the old size.

*/

if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))

new_allocated = ((size_t)newsize + 3) & ~(size_t)3;

if (newsize == 0)

new_allocated = 0;

if (new_allocated <= (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {

num_allocated_bytes = new_allocated * sizeof(PyObject *);

items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);

}

else {

// integer overflow

items = NULL;

}

if (items == NULL) {

PyErr_NoMemory();

return -1;

}

self->ob_item = items;

Py_SET_SIZE(self, newsize);

self->allocated = new_allocated;

return 0;

}

static int

list_preallocate_exact(PyListObject *self, Py_ssize_t size)

{

assert(self->ob_item == NULL);

assert(size > 0);

PyObject **items = PyMem_New(PyObject*, size);

if (items == NULL) {

PyErr_NoMemory();

return -1;

}

self->ob_item = items;

self->allocated = size;

return 0;

}

/* Empty list reuse scheme to save calls to malloc and free */

#ifndef PyList_MAXFREELIST

# define PyList_MAXFREELIST 80

#endif

static PyListObject *free_list[PyList_MAXFREELIST];

static int numfree = 0;

void

_PyList_ClearFreeList(void)

{

while (numfree) {

PyListObject *op = free_list[--numfree];

assert(PyList_CheckExact(op));

PyObject_GC_Del(op);

}

}

void

_PyList_Fini(void)

{

_PyList_ClearFreeList();

}

/* Print summary info about the state of the optimized allocator */

void

_PyList_DebugMallocStats(FILE *out)

{

_PyDebugAllocatorStats(out,

"free PyListObject",

numfree, sizeof(PyListObject));

}

PyObject *

PyList_New(Py_ssize_t size)

{

PyListObject *op;

if (size < 0) {

PyErr_BadInternalCall();

return NULL;

}

if (numfree) {

numfree--;

op = free_list[numfree];

_Py_NewReference((PyObject *)op);

} else {

op = PyObject_GC_New(PyListObject, &PyList_Type);

if (op == NULL)

return NULL;

}

if (size <= 0)

op->ob_item = NULL;

else {

op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));

if (op->ob_item == NULL) {

Py_DECREF(op);

return PyErr_NoMemory();

}

}

Py_SET_SIZE(op, size);

op->allocated = size;

_PyObject_GC_TRACK(op);

return (PyObject *) op;

}

static PyObject *

list_new_prealloc(Py_ssize_t size)

{

assert(size > 0);

PyListObject *op = (PyListObject *) PyList_New(0);

if (op == NULL) {

return NULL;

}

assert(op->ob_item == NULL);

op->ob_item = PyMem_New(PyObject *, size);

if (op->ob_item == NULL) {

Py_DECREF(op);

return PyErr_NoMemory();

}

op->allocated = size;

return (PyObject *) op;

}

Py_ssize_t

PyList_Size(PyObject *op)

{

if (!PyList_Check(op)) {

PyErr_BadInternalCall();

return -1;

}

else

return Py_SIZE(op);

}

static inline int

valid_index(Py_ssize_t i, Py_ssize_t limit)

{

/* The cast to size_t lets us use just a single comparison

to check whether i is in the range: 0 <= i < limit.

See: Section 14.2 "Bounds Checking" in the Agner Fog

optimization manual found at:

https://www.agner.org/optimize/optimizing_cpp.pdf

*/

return (size_t) i < (size_t) limit;

}

static PyObject *indexerr = NULL;

PyObject *

PyList_GetItem(PyObject *op, Py_ssize_t i)

{

if (!PyList_Check(op)) {

PyErr_BadInternalCall();

return NULL;

}

if (!valid_index(i, Py_SIZE(op))) {

if (indexerr == NULL) {

indexerr = PyUnicode_FromString(

"list index out of range");

if (indexerr == NULL)

return NULL;

}

PyErr_SetObject(PyExc_IndexError, indexerr);

return NULL;

}

return ((PyListObject *)op) -> ob_item[i];

}

int

PyList_SetItem(PyObject *op, Py_ssize_t i,

PyObject *newitem)

{

PyObject **p;

if (!PyList_Check(op)) {

Py_XDECREF(newitem);

PyErr_BadInternalCall();

return -1;

}

if (!valid_index(i, Py_SIZE(op))) {

Py_XDECREF(newitem);

PyErr_SetString(PyExc_IndexError,

"list assignment index out of range");

return -1;

}

p = ((PyListObject *)op) -> ob_item + i;

Py_XSETREF(*p, newitem);

return 0;

}

static int

ins1(PyListObject *self, Py_ssize_t where, PyObject *v)

{

Py_ssize_t i, n = Py_SIZE(self);

PyObject **items;

if (v == NULL) {

PyErr_BadInternalCall();

return -1;

}

if (n == PY_SSIZE_T_MAX) {

PyErr_SetString(PyExc_OverflowError,

"cannot add more objects to list");

return -1;

}

if (list_resize(self, n+1) < 0)

return -1;

if (where < 0) {

where += n;

if (where < 0)

where = 0;

}

if (where > n)

where = n;

items = self->ob_item;

for (i = n; --i >= where; )

items[i+1] = items[i];

Py_INCREF(v);

items[where] = v;

return 0;

}

int

PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)

{

if (!PyList_Check(op)) {

PyErr_BadInternalCall();

return -1;

}

return ins1((PyListObject *)op, where, newitem);

}

static int

app1(PyListObject *self, PyObject *v)

{

Py_ssize_t n = PyList_GET_SIZE(self);

assert (v != NULL);

if (n == PY_SSIZE_T_MAX) {

PyErr_SetString(PyExc_OverflowError,

"cannot add more objects to list");

return -1;

}

if (list_resize(self, n+1) < 0)

return -1;

Py_INCREF(v);

PyList_SET_ITEM(self, n, v);

return 0;

}

int

PyList_Append(PyObject *op, PyObject *newitem)

{

if (PyList_Check(op) && (newitem != NULL))

return app1((PyListObject *)op, newitem);

PyErr_BadInternalCall();

return -1;

}

/* Methods */

static void

list_dealloc(PyListObject *op)

{

Py_ssize_t i;

PyObject_GC_UnTrack(op);

Py_TRASHCAN_BEGIN(op, list_dealloc)

if (op->ob_item != NULL) {

/* Do it backwards, for Christian Tismer.

There's a simple test case where somehow this reduces

thrashing when a *very* large list is created and

immediately deleted. */

i = Py_SIZE(op);

while (--i >= 0) {

Py_XDECREF(op->ob_item[i]);

}

PyMem_FREE(op->ob_item);

}

if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))

free_list[numfree++] = op;

else

Py_TYPE(op)->tp_free((PyObject *)op);

Py_TRASHCAN_END

}

static PyObject *

list_repr(PyListObject *v)

{

Py_ssize_t i;

PyObject *s;

_PyUnicodeWriter writer;

if (Py_SIZE(v) == 0) {

return PyUnicode_FromString("[]");

}

i = Py_ReprEnter((PyObject*)v);

if (i != 0) {

return i > 0 ? PyUnicode_FromString("[...]") : NULL;

}

_PyUnicodeWriter_Init(&writer);

writer.overallocate = 1;

/* "[" + "1" + ", 2" * (len - 1) + "]" */

writer.min_length = 1 + 1 + (2 + 1) * (Py_SIZE(v) - 1) + 1;

if (_PyUnicodeWriter_WriteChar(&writer, '[') < 0)

goto error;

/* Do repr() on each element. Note that this may mutate the list,

so must refetch the list size on each iteration. */

for (i = 0; i < Py_SIZE(v); ++i) {

if (i > 0) {

if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)

goto error;

}

s = PyObject_Repr(v->ob_item[i]);

if (s == NULL)

goto error;

if (_PyUnicodeWriter_WriteStr(&writer, s) < 0) {

Py_DECREF(s);

goto error;

}

Py_DECREF(s);

}

writer.overallocate = 0;

if (_PyUnicodeWriter_WriteChar(&writer, ']') < 0)

goto error;

Py_ReprLeave((PyObject *)v);

return _PyUnicodeWriter_Finish(&writer);

error:

_PyUnicodeWriter_Dealloc(&writer);

Py_ReprLeave((PyObject *)v);

return NULL;

}

static Py_ssize_t

list_length(PyListObject *a)

{

return Py_SIZE(a);

}

static int

list_contains(PyListObject *a, PyObject *el)

{

PyObject *item;

Py_ssize_t i;

int cmp;

for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i) {

item = PyList_GET_ITEM(a, i);

Py_INCREF(item);

cmp = PyObject_RichCompareBool(item, el, Py_EQ);

Py_DECREF(item);

}

return cmp;

}

static PyObject *

list_item(PyListObject *a, Py_ssize_t i)

{

if (!valid_index(i, Py_SIZE(a))) {

if (indexerr == NULL) {

indexerr = PyUnicode_FromString(

"list index out of range");

if (indexerr == NULL)

return NULL;

}

PyErr_SetObject(PyExc_IndexError, indexerr);

return NULL;

}

Py_INCREF(a->ob_item[i]);

return a->ob_item[i];

}

static PyObject *

list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)

{

PyListObject *np;

PyObject **src, **dest;

Py_ssize_t i, len;

len = ihigh - ilow;

if (len <= 0) {

return PyList_New(0);

}

np = (PyListObject *) list_new_prealloc(len);

if (np == NULL)

return NULL;

src = a->ob_item + ilow;

dest = np->ob_item;

for (i = 0; i < len; i++) {

PyObject *v = src[i];

Py_INCREF(v);

dest[i] = v;

}

Py_SET_SIZE(np, len);

return (PyObject *)np;

}

PyObject *

PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)

{

if (!PyList_Check(a)) {

PyErr_BadInternalCall();

return NULL;

}

if (ilow < 0) {

ilow = 0;

}

else if (ilow > Py_SIZE(a)) {

ilow = Py_SIZE(a);

}

if (ihigh < ilow) {

ihigh = ilow;

}

else if (ihigh > Py_SIZE(a)) {

ihigh = Py_SIZE(a);

}

return list_slice((PyListObject *)a, ilow, ihigh);

}

static PyObject *

list_concat(PyListObject *a, PyObject *bb)

{

Py_ssize_t size;

Py_ssize_t i;

PyObject **src, **dest;

PyListObject *np;

if (!PyList_Check(bb)) {

PyErr_Format(PyExc_TypeError,

"can only concatenate list (not \"%.200s\") to list",

Py_TYPE(bb)->tp_name);

return NULL;

}

#define b ((PyListObject *)bb)

if (Py_SIZE(a) > PY_SSIZE_T_MAX - Py_SIZE(b))

return PyErr_NoMemory();

size = Py_SIZE(a) + Py_SIZE(b);

if (size == 0) {

return PyList_New(0);

}

np = (PyListObject *) list_new_prealloc(size);

if (np == NULL) {

return NULL;

}

src = a->ob_item;

dest = np->ob_item;

for (i = 0; i < Py_SIZE(a); i++) {

PyObject *v = src[i];

Py_INCREF(v);

dest[i] = v;

}

src = b->ob_item;

dest = np->ob_item + Py_SIZE(a);

for (i = 0; i < Py_SIZE(b); i++) {

PyObject *v = src[i];

Py_INCREF(v);

dest[i] = v;

}

Py_SET_SIZE(np, size);

return (PyObject *)np;

#undef b

}

static PyObject *

list_repeat(PyListObject *a, Py_ssize_t n)

{

Py_ssize_t i, j;

Py_ssize_t size;

PyListObject *np;

PyObject **p, **items;

PyObject *elem;

if (n < 0)

n = 0;

if (n > 0 && Py_SIZE(a) > PY_SSIZE_T_MAX / n)

return PyErr_NoMemory();

size = Py_SIZE(a) * n;

if (size == 0)

return PyList_New(0);

np = (PyListObject *) list_new_prealloc(size);

if (np == NULL)

return NULL;

if (Py_SIZE(a) == 1) {

items = np->ob_item;

elem = a->ob_item[0];

for (i = 0; i < n; i++) {

items[i] = elem;

Py_INCREF(elem);

}

}

else {

p = np->ob_item;

items = a->ob_item;

for (i = 0; i < n; i++) {

for (j = 0; j < Py_SIZE(a); j++) {

*p = items[j];

Py_INCREF(*p);

p++;

}

}

}

Py_SET_SIZE(np, size);

return (PyObject *) np;

}

static int

_list_clear(PyListObject *a)

{

Py_ssize_t i;

PyObject **item = a->ob_item;

if (item != NULL) {

/* Because XDECREF can recursively invoke operations on

this list, we make it empty first. */

i = Py_SIZE(a);

Py_SET_SIZE(a, 0);

a->ob_item = NULL;

a->allocated = 0;

while (--i >= 0) {

Py_XDECREF(item[i]);

}

PyMem_FREE(item);

}

/* Never fails; the return value can be ignored.

Note that there is no guarantee that the list is actually empty

at this point, because XDECREF may have populated it again! */

return 0;

}

/* a[ilow:ihigh] = v if v != NULL.

* del a[ilow:ihigh] if v == NULL.

*

* Special speed gimmick: when v is NULL and ihigh - ilow <= 8, it's

* guaranteed the call cannot fail.

*/

static int

list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)

{

/* Because [X]DECREF can recursively invoke list operations on

this list, we must postpone all [X]DECREF activity until

after the list is back in its canonical shape. Therefore

we must allocate an additional array, 'recycle', into which

we temporarily copy the items that are deleted from the

list. :-( */

PyObject *recycle_on_stack[8];

PyObject **recycle = recycle_on_stack; /* will allocate more if needed */

PyObject **item;

PyObject **vitem = NULL;

PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */

Py_ssize_t n; /* # of elements in replacement list */

Py_ssize_t norig; /* # of elements in list getting replaced */

Py_ssize_t d; /* Change in size */

Py_ssize_t k;

size_t s;

int result = -1; /* guilty until proved innocent */

#define b ((PyListObject *)v)

if (v == NULL)

n = 0;

else {

if (a == b) {

/* Special case "a[i:j] = a" -- copy b first */

v = list_slice(b, 0, Py_SIZE(b));

if (v == NULL)

return result;

result = list_ass_slice(a, ilow, ihigh, v);

Py_DECREF(v);

return result;

}

v_as_SF = PySequence_Fast(v, "can only assign an iterable");

if(v_as_SF == NULL)

goto Error;

n = PySequence_Fast_GET_SIZE(v_as_SF);

vitem = PySequence_Fast_ITEMS(v_as_SF);

}

if (ilow < 0)

ilow = 0;

else if (ilow > Py_SIZE(a))

ilow = Py_SIZE(a);

if (ihigh < ilow)

ihigh = ilow;

else if (ihigh > Py_SIZE(a))

ihigh = Py_SIZE(a);

norig = ihigh - ilow;

assert(norig >= 0);

d = n - norig;

if (Py_SIZE(a) + d == 0) {

Py_XDECREF(v_as_SF);

return _list_clear(a);

}

item = a->ob_item;

/* recycle the items that we are about to remove */

s = norig * sizeof(PyObject *);

/* If norig == 0, item might be NULL, in which case we may not memcpy from it. */

if (s) {

if (s > sizeof(recycle_on_stack)) {

recycle = (PyObject **)PyMem_MALLOC(s);

if (recycle == NULL) {

PyErr_NoMemory();

goto Error;

}

}

memcpy(recycle, &item[ilow], s);

}

if (d < 0) { /* Delete -d items */

Py_ssize_t tail;

tail = (Py_SIZE(a) - ihigh) * sizeof(PyObject *);

memmove(&item[ihigh+d], &item[ihigh], tail);

if (list_resize(a, Py_SIZE(a) + d) < 0) {

memmove(&item[ihigh], &item[ihigh+d], tail);

memcpy(&item[ilow], recycle, s);

goto Error;

}

item = a->ob_item;

}

else if (d > 0) { /* Insert d items */

k = Py_SIZE(a);

if (list_resize(a, k+d) < 0)

goto Error;

item = a->ob_item;

memmove(&item[ihigh+d], &item[ihigh],

(k - ihigh)*sizeof(PyObject *));

}

for (k = 0; k < n; k++, ilow++) {

PyObject *w = vitem[k];

Py_XINCREF(w);

item[ilow] = w;

}

for (k = norig - 1; k >= 0; --k)

Py_XDECREF(recycle[k]);

result = 0;

Error:

if (recycle != recycle_on_stack)

PyMem_FREE(recycle);

Py_XDECREF(v_as_SF);

return result;

#undef b

}

int

PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)

{

if (!PyList_Check(a)) {

PyErr_BadInternalCall();

return -1;

}

return list_ass_slice((PyListObject *)a, ilow, ihigh, v);

}

static PyObject *

list_inplace_repeat(PyListObject *self, Py_ssize_t n)

{

PyObject **items;

Py_ssize_t size, i, j, p;

size = PyList_GET_SIZE(self);

if (size == 0 || n == 1) {

Py_INCREF(self);

return (PyObject *)self;

}

if (n < 1) {

(void)_list_clear(self);

Py_INCREF(self);

return (PyObject *)self;

}

if (size > PY_SSIZE_T_MAX / n) {

return PyErr_NoMemory();

}

if (list_resize(self, size*n) < 0)

return NULL;

p = size;

items = self->ob_item;

for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */

for (j = 0; j < size; j++) {

PyObject *o = items[j];

Py_INCREF(o);

items[p++] = o;

}

}

Py_INCREF(self);

return (PyObject *)self;

}

static int

list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)

{

if (!valid_index(i, Py_SIZE(a))) {

PyErr_SetString(PyExc_IndexError,

"list assignment index out of range");

return -1;

}

if (v == NULL)

return list_ass_slice(a, i, i+1, v);

Py_INCREF(v);

Py_SETREF(a->ob_item[i], v);

return 0;

}

/*[clinic input]

list.insert

index: Py_ssize_t

object: object

/

Insert object before index.

[clinic start generated code]*/

static PyObject *

list_insert_impl(PyListObject *self, Py_ssize_t index, PyObject *object)

/*[clinic end generated code: output=7f35e32f60c8cb78 input=858514cf894c7eab]*/

{

if (ins1(self, index, object) == 0)

Py_RETURN_NONE;

return NULL;

}

/*[clinic input]

list.clear

Remove all items from list.

[clinic start generated code]*/

static PyObject *

list_clear_impl(PyListObject *self)

/*[clinic end generated code: output=67a1896c01f74362 input=ca3c1646856742f6]*/

{

_list_clear(self);

Py_RETURN_NONE;

}

/*[clinic input]

list.copy

Return a shallow copy of the list.

[clinic start generated code]*/

static PyObject *

list_copy_impl(PyListObject *self)

/*[clinic end generated code: output=ec6b72d6209d418e input=6453ab159e84771f]*/

{

return list_slice(self, 0, Py_SIZE(self));

}

/*[clinic input]

list.append

object: object

/

Append object to the end of the list.

[clinic start generated code]*/

static PyObject *

list_append(PyListObject *self, PyObject *object)

/*[clinic end generated code: output=7c096003a29c0eae input=43a3fe48a7066e91]*/

{

if (app1(self, object) == 0)

Py_RETURN_NONE;

return NULL;

}

/*[clinic input]

list.extend

iterable: object

/

Extend list by appending elements from the iterable.

[clinic start generated code]*/

static PyObject *

list_extend(PyListObject *self, PyObject *iterable)

/*[clinic end generated code: output=630fb3bca0c8e789 input=9ec5ba3a81be3a4d]*/

{

PyObject *it; /* iter(v) */

Py_ssize_t m; /* size of self */

Py_ssize_t n; /* guess for size of iterable */

Py_ssize_t mn; /* m + n */

Py_ssize_t i;

PyObject *(*iternext)(PyObject *);

/* Special cases:

1) lists and tuples which can use PySequence_Fast ops

2) extending self to self requires making a copy first

*/

if (PyList_CheckExact(iterable) || PyTuple_CheckExact(iterable) ||

(PyObject *)self == iterable) {

PyObject **src, **dest;

iterable = PySequence_Fast(iterable, "argument must be iterable");

if (!iterable)

return NULL;

n = PySequence_Fast_GET_SIZE(iterable);

if (n == 0) {

/* short circuit when iterable is empty */

Py_DECREF(iterable);

Py_RETURN_NONE;

}

m = Py_SIZE(self);

/* It should not be possible to allocate a list large enough to cause

an overflow on any relevant platform */

assert(m < PY_SSIZE_T_MAX - n);

if (list_resize(self, m + n) < 0) {

Py_DECREF(iterable);

return NULL;

}

/* note that we may still have self == iterable here for the

* situation a.extend(a), but the following code works

* in that case too. Just make sure to resize self

* before calling PySequence_Fast_ITEMS.

*/

/* populate the end of self with iterable's items */

src = PySequence_Fast_ITEMS(iterable);

dest = self->ob_item + m;

for (i = 0; i < n; i++) {

PyObject *o = src[i];

Py_INCREF(o);

dest[i] = o;

}

Py_DECREF(iterable);

Py_RETURN_NONE;

}

it = PyObject_GetIter(iterable);

if (it == NULL)

return NULL;

iternext = *Py_TYPE(it)->tp_iternext;

/* Guess a result list size. */

n = PyObject_LengthHint(iterable, 8);

if (n < 0) {

Py_DECREF(it);

return NULL;

}

m = Py_SIZE(self);

if (m > PY_SSIZE_T_MAX - n) {

/* m + n overflowed; on the chance that n lied, and there really

* is enough room, ignore it. If n was telling the truth, we'll

* eventually run out of memory during the loop.

*/

}

else {

mn = m + n;

/* Make room. */

if (list_resize(self, mn) < 0)

goto error;

/* Make the list sane again. */

Py_SET_SIZE(self, m);

}

/* Run iterator to exhaustion. */

for (;;) {

PyObject *item = iternext(it);

if (item == NULL) {

if (PyErr_Occurred()) {

if (PyErr_ExceptionMatches(PyExc_StopIteration))

PyErr_Clear();

else

goto error;

}

break;

}

if (Py_SIZE(self) < self->allocated) {

/* steals ref */

PyList_SET_ITEM(self, Py_SIZE(self), item);

Py_SET_SIZE(self, Py_SIZE(self) + 1);

}

else {

int status = app1(self, item);

Py_DECREF(item); /* append creates a new ref */

if (status < 0)

goto error;

}

}

/* Cut back result list if initial guess was too large. */

if (Py_SIZE(self) < self->allocated) {

if (list_resize(self, Py_SIZE(self)) < 0)

goto error;

}

Py_DECREF(it);

Py_RETURN_NONE;

error:

Py_DECREF(it);

return NULL;

}

PyObject *

_PyList_Extend(PyListObject *self, PyObject *iterable)

{

return list_extend(self, iterable);

}

static PyObject *

list_inplace_concat(PyListObject *self, PyObject *other)

{

PyObject *result;

result = list_extend(self, other);

if (result == NULL)

return result;

Py_DECREF(result);

Py_INCREF(self);

return (PyObject *)self;

}

/*[clinic input]

list.pop

index: Py_ssize_t = -1

/

Remove and return item at index (default last).

Raises IndexError if list is empty or index is out of range.

[clinic start generated code]*/