#include "Python.h"

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

#include "pycore_interp.h" // PyInterpreterState.list

#include "pycore_list.h" // struct _Py_list_state, _PyListIterObject

#include "pycore_object.h" // _PyObject_GC_TRACK()

#include "pycore_tuple.h" // _PyTuple_FromArray()

#include <stddef.h>

#include "clinic/listobject.c.h"

_Py_DECLARE_STR(list_err, "list index out of range");

#if PyList_MAXFREELIST > 0

static struct _Py_list_state *

get_list_state(void)

{

PyInterpreterState *interp = _PyInterpreterState_GET();

return &interp->list;

}

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

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

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

/* Do not overallocate if the new size is closer to overallocated 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);

/* Since the Python memory allocator has granularity of 16 bytes on 64-bit

size = (size + 1) & ~(size_t)1;

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

if (items == NULL) {

PyErr_NoMemory();

return -1;

}

self->ob_item = items;

self->allocated = size;

return 0;

}

_PyList_ClearFreeList(PyInterpreterState *interp)

{

#if PyList_MAXFREELIST > 0

struct _Py_list_state *state = &interp->list;

while (state->numfree) {

PyListObject *op = state->free_list[--state->numfree];

assert(PyList_CheckExact(op));

PyObject_GC_Del(op);

}

}

_PyList_Fini(PyInterpreterState *interp)

{

_PyList_ClearFreeList(interp);

#if defined(Py_DEBUG) && PyList_MAXFREELIST > 0

struct _Py_list_state *state = &interp->list;

state->numfree = -1;

}

_PyList_DebugMallocStats(FILE *out)

{

#if PyList_MAXFREELIST > 0

struct _Py_list_state *state = get_list_state();

_PyDebugAllocatorStats(out,

"free PyListObject",

state->numfree, sizeof(PyListObject));

}

PyObject *

PyList_New(Py_ssize_t size)

{

PyListObject *op;

if (size < 0) {

PyErr_BadInternalCall();

return NULL;

}

#if PyList_MAXFREELIST > 0

struct _Py_list_state *state = get_list_state();

#ifdef Py_DEBUG

// PyList_New() must not be called after _PyList_Fini()

assert(state->numfree != -1);

if (PyList_MAXFREELIST && state->numfree) {

state->numfree--;

op = state->free_list[state->numfree];

OBJECT_STAT_INC(from_freelist);

_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;

}

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

return (size_t) i < (size_t) limit;

}

PyObject *

PyList_GetItem(PyObject *op, Py_ssize_t i)

{

if (!PyList_Check(op)) {

PyErr_BadInternalCall();

return NULL;

}

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

_Py_DECLARE_STR(list_err, "list index out of range");

PyErr_SetObject(PyExc_IndexError, &_Py_STR(list_err));

return NULL;

}

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

}

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;

}

assert((size_t)n + 1 < PY_SSIZE_T_MAX);

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;

}

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

{

if (!PyList_Check(op)) {

PyErr_BadInternalCall();

return -1;

}

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

}

_PyList_AppendTakeRefListResize(PyListObject *self, PyObject *newitem)

{

Py_ssize_t len = PyList_GET_SIZE(self);

assert(self->allocated == -1 || self->allocated == len);

if (list_resize(self, len + 1) < 0) {

Py_DECREF(newitem);

return -1;

}

PyList_SET_ITEM(self, len, newitem);

return 0;

}

PyList_Append(PyObject *op, PyObject *newitem)

{

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

Py_INCREF(newitem);

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

}

PyErr_BadInternalCall();

return -1;

}

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.

i = Py_SIZE(op);

while (--i >= 0) {

Py_XDECREF(op->ob_item[i]);

}

PyMem_Free(op->ob_item);

}

#if PyList_MAXFREELIST > 0

struct _Py_list_state *state = get_list_state();

#ifdef Py_DEBUG

// list_dealloc() must not be called after _PyList_Fini()

assert(state->numfree != -1);

if (state->numfree < PyList_MAXFREELIST && PyList_CheckExact(op)) {

state->free_list[state->numfree++] = op;

OBJECT_STAT_INC(to_freelist);

}

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,

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))) {

PyErr_SetObject(PyExc_IndexError, &_Py_STR(list_err));

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)

assert((size_t)Py_SIZE(a) + (size_t)Py_SIZE(b) < PY_SSIZE_T_MAX);

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)

{

const Py_ssize_t input_size = Py_SIZE(a);

if (input_size == 0 || n <= 0)

return PyList_New(0);

assert(n > 0);

if (input_size > PY_SSIZE_T_MAX / n)

return PyErr_NoMemory();

Py_ssize_t output_size = input_size * n;

PyListObject *np = (PyListObject *) list_new_prealloc(output_size);

if (np == NULL)

return NULL;

PyObject **dest = np->ob_item;

if (input_size == 1) {

PyObject *elem = a->ob_item[0];

_Py_RefcntAdd(elem, n);

PyObject **dest_end = dest + output_size;

while (dest < dest_end) {

*dest++ = elem;

}

}

else {

PyObject **src = a->ob_item;

PyObject **src_end = src + input_size;

while (src < src_end) {

_Py_RefcntAdd(*src, n);

*dest++ = *src++;

}

_Py_memory_repeat((char *)np->ob_item, sizeof(PyObject *)*output_size,

sizeof(PyObject *)*input_size);

}

Py_SET_SIZE(np, output_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

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.

return 0;

}

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

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

}

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)

{

Py_ssize_t input_size = PyList_GET_SIZE(self);

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

Py_INCREF(self);

return (PyObject *)self;

}

if (n < 1) {

(void)_list_clear(self);

Py_INCREF(self);

return (PyObject *)self;

}

if (input_size > PY_SSIZE_T_MAX / n) {

return PyErr_NoMemory();

}

Py_ssize_t output_size = input_size * n;

if (list_resize(self, output_size) < 0)

return NULL;

PyObject **items = self->ob_item;

for (Py_ssize_t j = 0; j < input_size; j++) {

_Py_RefcntAdd(items[j], n-1);

}

_Py_memory_repeat((char *)items, sizeof(PyObject *)*output_size,

sizeof(PyObject *)*input_size);

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;

}

static PyObject *

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

{

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

Py_RETURN_NONE;

return NULL;

}

static PyObject *

list_clear_impl(PyListObject *self)

{

_list_clear(self);

Py_RETURN_NONE;

}

static PyObject *

list_copy_impl(PyListObject *self)

{

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

}

static PyObject *

list_append(PyListObject *self, PyObject *object)

{

if (_PyList_AppendTakeRef(self, Py_NewRef(object)) < 0) {

return NULL;

}

Py_RETURN_NONE;

}

static PyObject *

list_extend(PyListObject *self, PyObject *iterable)

{

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

Py_ssize_t m; /* size of self */

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

Py_ssize_t i;

PyObject *(*iternext)(PyObject *);

/* Special cases:

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

assert(m < PY_SSIZE_T_MAX - n);

if (self->ob_item == NULL) {

if (list_preallocate_exact(self, n) < 0) {

return NULL;

}

Py_SET_SIZE(self, n);

}

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

Py_DECREF(iterable);

return NULL;

}

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

/* 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

}

else if (self->ob_item == NULL) {

if (n && list_preallocate_exact(self, n) < 0)

goto error;

}

else {

/* Make room. */

if (list_resize(self, m + n) < 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 {

if (_PyList_AppendTakeRef(self, item) < 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;