arraymodule.c

/* Array object implementation */

/* An array is a uniform list -- all items have the same type.
   The item type is restricted to simple C types like int or float */

#ifndef Py_BUILD_CORE_BUILTIN
#  define Py_BUILD_CORE_MODULE 1
#endif

#include "Python.h"
#include "pycore_bytesobject.h"   // _PyBytes_Repeat
#include "pycore_call.h"          // _PyObject_CallMethod()
#include "pycore_ceval.h"         // _PyEval_GetBuiltin()
#include "pycore_modsupport.h"    // _PyArg_NoKeywords()
#include "pycore_moduleobject.h"  // _PyModule_GetState()

#include <stddef.h>               // offsetof()
#include <stdbool.h>

/*[clinic input]
module array
[clinic start generated code]*/
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=7d1b8d7f5958fd83]*/

struct arrayobject; /* Forward */
static struct PyModuleDef arraymodule;

/* All possible arraydescr values are defined in the vector "descriptors"
 * below.  That's defined later because the appropriate get and set
 * functions aren't visible yet.
 */
struct arraydescr {
    char typecode;
    int itemsize;
    PyObject * (*getitem)(struct arrayobject *, Py_ssize_t);
    int (*setitem)(struct arrayobject *, Py_ssize_t, PyObject *);
    int (*compareitems)(const void *, const void *, Py_ssize_t);
    const char *formats;
    int is_integer_type;
    int is_signed;
};

typedef struct arrayobject {
    PyObject_VAR_HEAD
    char *ob_item;
    Py_ssize_t allocated;
    const struct arraydescr *ob_descr;
    PyObject *weakreflist; /* List of weak references */
    Py_ssize_t ob_exports;  /* Number of exported buffers */
} arrayobject;

typedef struct {
    PyObject_HEAD
    Py_ssize_t index;
    arrayobject *ao;
    PyObject* (*getitem)(struct arrayobject *, Py_ssize_t);
} arrayiterobject;

typedef struct {
    PyTypeObject *ArrayType;
    PyTypeObject *ArrayIterType;

    PyObject *array_reconstructor;

    PyObject *str_read;
    PyObject *str_write;
    PyObject *str___dict__;
    PyObject *str_iter;
} array_state;

static array_state *
get_array_state(PyObject *module)
{
    return (array_state *)_PyModule_GetState(module);
}

#define find_array_state_by_type(tp) \
    (get_array_state(PyType_GetModuleByDef(tp, &arraymodule)))
#define get_array_state_by_class(cls) \
    (get_array_state(PyType_GetModule(cls)))

enum machine_format_code {
    UNKNOWN_FORMAT = -1,
    /* UNKNOWN_FORMAT is used to indicate that the machine format for an
     * array type code cannot be interpreted. When this occurs, a list of
     * Python objects is used to represent the content of the array
     * instead of using the memory content of the array directly. In that
     * case, the array_reconstructor mechanism is bypassed completely, and
     * the standard array constructor is used instead.
     *
     * This is will most likely occur when the machine doesn't use IEEE
     * floating-point numbers.
     */

    UNSIGNED_INT8 = 0,
    SIGNED_INT8 = 1,
    UNSIGNED_INT16_LE = 2,
    UNSIGNED_INT16_BE = 3,
    SIGNED_INT16_LE = 4,
    SIGNED_INT16_BE = 5,
    UNSIGNED_INT32_LE = 6,
    UNSIGNED_INT32_BE = 7,
    SIGNED_INT32_LE = 8,
    SIGNED_INT32_BE = 9,
    UNSIGNED_INT64_LE = 10,
    UNSIGNED_INT64_BE = 11,
    SIGNED_INT64_LE = 12,
    SIGNED_INT64_BE = 13,
    IEEE_754_FLOAT_LE = 14,
    IEEE_754_FLOAT_BE = 15,
    IEEE_754_DOUBLE_LE = 16,
    IEEE_754_DOUBLE_BE = 17,
    UTF16_LE = 18,
    UTF16_BE = 19,
    UTF32_LE = 20,
    UTF32_BE = 21
};
#define MACHINE_FORMAT_CODE_MIN 0
#define MACHINE_FORMAT_CODE_MAX 21


/*
 * Must come after arrayobject, arrayiterobject,
 * and enum machine_code_type definitions.
 */
#include "clinic/arraymodule.c.h"

#define array_Check(op, state) PyObject_TypeCheck(op, state->ArrayType)

static int
array_resize(arrayobject *self, Py_ssize_t newsize)
{
    char *items;
    size_t _new_size;

    if (self->ob_exports > 0 && newsize != Py_SIZE(self)) {
        PyErr_SetString(PyExc_BufferError,
            "cannot resize an array that is exporting buffers");
        return -1;
    }

    /* Bypass realloc() when a previous overallocation is large enough
       to accommodate the newsize.  If the newsize is 16 smaller than the
       current size, then proceed with the realloc() to shrink the array.
    */

    if (self->allocated >= newsize &&
        Py_SIZE(self) < newsize + 16 &&
        self->ob_item != NULL) {
        Py_SET_SIZE(self, newsize);
        return 0;
    }

    if (newsize == 0) {
        PyMem_Free(self->ob_item);
        self->ob_item = NULL;
        Py_SET_SIZE(self, 0);
        self->allocated = 0;
        return 0;
    }

    /* This over-allocates proportional to the array 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().
     * The growth pattern is:  0, 4, 8, 16, 25, 34, 46, 56, 67, 79, ...
     * Note, the pattern starts out the same as for lists but then
     * grows at a smaller rate so that larger arrays only overallocate
     * by about 1/16th -- this is done because arrays are presumed to be more
     * memory critical.
     */

    _new_size = (newsize >> 4) + (Py_SIZE(self) < 8 ? 3 : 7) + newsize;
    items = self->ob_item;
    /* XXX The following multiplication and division does not optimize away
       like it does for lists since the size is not known at compile time */
    if (_new_size <= ((~(size_t)0) / self->ob_descr->itemsize))
        PyMem_RESIZE(items, char, (_new_size * self->ob_descr->itemsize));
    else
        items = NULL;
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SET_SIZE(self, newsize);
    self->allocated = _new_size;
    return 0;
}

/****************************************************************************
Get and Set functions for each type.
A Get function takes an arrayobject* and an integer index, returning the
array value at that index wrapped in an appropriate PyObject*.
A Set function takes an arrayobject, integer index, and PyObject*; sets
the array value at that index to the raw C data extracted from the PyObject*,
and returns 0 if successful, else nonzero on failure (PyObject* not of an
appropriate type or value).
Note that the basic Get and Set functions do NOT check that the index is
in bounds; that's the responsibility of the caller.
****************************************************************************/

static PyObject *
b_getitem(arrayobject *ap, Py_ssize_t i)
{
    long x = ((signed char *)ap->ob_item)[i];
    return PyLong_FromLong(x);
}

static int
b_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    short x;
    /* PyArg_Parse's 'b' formatter is for an unsigned char, therefore
       must use the next size up that is signed ('h') and manually do
       the overflow checking */
    if (!PyArg_Parse(v, "h;array item must be integer", &x))
        return -1;
    else if (x < -128) {
        PyErr_SetString(PyExc_OverflowError,
            "signed char is less than minimum");
        return -1;
    }
    else if (x > 127) {
        PyErr_SetString(PyExc_OverflowError,
            "signed char is greater than maximum");
        return -1;
    }
    if (i >= 0)
        ((char *)ap->ob_item)[i] = (char)x;
    return 0;
}

static PyObject *
BB_getitem(arrayobject *ap, Py_ssize_t i)
{
    long x = ((unsigned char *)ap->ob_item)[i];
    return PyLong_FromLong(x);
}

static int
BB_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    unsigned char x;
    /* 'B' == unsigned char, maps to PyArg_Parse's 'b' formatter */
    if (!PyArg_Parse(v, "b;array item must be integer", &x))
        return -1;
    if (i >= 0)
        ((unsigned char *)ap->ob_item)[i] = x;
    return 0;
}

static PyObject *
u_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyUnicode_FromOrdinal(((wchar_t *) ap->ob_item)[i]);
}

static int
u_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    PyObject *u;
    if (!PyArg_Parse(v, "U;array item must be unicode character", &u)) {
        return -1;
    }

    Py_ssize_t len = PyUnicode_AsWideChar(u, NULL, 0);
    if (len != 2) {
        PyErr_SetString(PyExc_TypeError,
                        "array item must be unicode character");
        return -1;
    }

    wchar_t w;
    len = PyUnicode_AsWideChar(u, &w, 1);
    assert(len == 1);

    if (i >= 0) {
        ((wchar_t *)ap->ob_item)[i] = w;
    }
    return 0;
}

static PyObject *
w_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyUnicode_FromOrdinal(((Py_UCS4 *) ap->ob_item)[i]);
}

static int
w_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    PyObject *u;
    if (!PyArg_Parse(v, "U;array item must be unicode character", &u)) {
        return -1;
    }

    if (PyUnicode_GetLength(u) != 1) {
        PyErr_SetString(PyExc_TypeError,
                        "array item must be unicode character");
        return -1;
    }

    if (i >= 0) {
        ((Py_UCS4 *)ap->ob_item)[i] = PyUnicode_READ_CHAR(u, 0);
    }
    return 0;
}

static PyObject *
h_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromLong((long) ((short *)ap->ob_item)[i]);
}


static int
h_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    short x;
    /* 'h' == signed short, maps to PyArg_Parse's 'h' formatter */
    if (!PyArg_Parse(v, "h;array item must be integer", &x))
        return -1;
    if (i >= 0)
                 ((short *)ap->ob_item)[i] = x;
    return 0;
}

static PyObject *
HH_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromLong((long) ((unsigned short *)ap->ob_item)[i]);
}

static int
HH_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    int x;
    /* PyArg_Parse's 'h' formatter is for a signed short, therefore
       must use the next size up and manually do the overflow checking */
    if (!PyArg_Parse(v, "i;array item must be integer", &x))
        return -1;
    else if (x < 0) {
        PyErr_SetString(PyExc_OverflowError,
            "unsigned short is less than minimum");
        return -1;
    }
    else if (x > USHRT_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "unsigned short is greater than maximum");
        return -1;
    }
    if (i >= 0)
        ((short *)ap->ob_item)[i] = (short)x;
    return 0;
}

static PyObject *
i_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromLong((long) ((int *)ap->ob_item)[i]);
}

static int
i_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    int x;
    /* 'i' == signed int, maps to PyArg_Parse's 'i' formatter */
    if (!PyArg_Parse(v, "i;array item must be integer", &x))
        return -1;
    if (i >= 0)
                 ((int *)ap->ob_item)[i] = x;
    return 0;
}

static PyObject *
II_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromUnsignedLong(
        (unsigned long) ((unsigned int *)ap->ob_item)[i]);
}

static int
II_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    unsigned long x;
    int do_decref = 0; /* if nb_int was called */

    if (!PyLong_Check(v)) {
        v = _PyNumber_Index(v);
        if (NULL == v) {
            return -1;
        }
        do_decref = 1;
    }
    x = PyLong_AsUnsignedLong(v);
    if (x == (unsigned long)-1 && PyErr_Occurred()) {
        if (do_decref) {
            Py_DECREF(v);
        }
        return -1;
    }
    if (x > UINT_MAX) {
        PyErr_SetString(PyExc_OverflowError,
                        "unsigned int is greater than maximum");
        if (do_decref) {
            Py_DECREF(v);
        }
        return -1;
    }
    if (i >= 0)
        ((unsigned int *)ap->ob_item)[i] = (unsigned int)x;

    if (do_decref) {
        Py_DECREF(v);
    }
    return 0;
}

static PyObject *
l_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromLong(((long *)ap->ob_item)[i]);
}

static int
l_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    long x;
    if (!PyArg_Parse(v, "l;array item must be integer", &x))
        return -1;
    if (i >= 0)
                 ((long *)ap->ob_item)[i] = x;
    return 0;
}

static PyObject *
LL_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromUnsignedLong(((unsigned long *)ap->ob_item)[i]);
}

static int
LL_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    unsigned long x;
    int do_decref = 0; /* if nb_int was called */

    if (!PyLong_Check(v)) {
        v = _PyNumber_Index(v);
        if (NULL == v) {
            return -1;
        }
        do_decref = 1;
    }
    x = PyLong_AsUnsignedLong(v);
    if (x == (unsigned long)-1 && PyErr_Occurred()) {
        if (do_decref) {
            Py_DECREF(v);
        }
        return -1;
    }
    if (i >= 0)
        ((unsigned long *)ap->ob_item)[i] = x;

    if (do_decref) {
        Py_DECREF(v);
    }
    return 0;
}

static PyObject *
q_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromLongLong(((long long *)ap->ob_item)[i]);
}

static int
q_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    long long x;
    if (!PyArg_Parse(v, "L;array item must be integer", &x))
        return -1;
    if (i >= 0)
        ((long long *)ap->ob_item)[i] = x;
    return 0;
}

static PyObject *
QQ_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromUnsignedLongLong(
        ((unsigned long long *)ap->ob_item)[i]);
}

static int
QQ_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    unsigned long long x;
    int do_decref = 0; /* if nb_int was called */

    if (!PyLong_Check(v)) {
        v = _PyNumber_Index(v);
        if (NULL == v) {
            return -1;
        }
        do_decref = 1;
    }
    x = PyLong_AsUnsignedLongLong(v);
    if (x == (unsigned long long)-1 && PyErr_Occurred()) {
        if (do_decref) {
            Py_DECREF(v);
        }
        return -1;
    }
    if (i >= 0)
        ((unsigned long long *)ap->ob_item)[i] = x;

    if (do_decref) {
        Py_DECREF(v);
    }
    return 0;
}

static PyObject *
f_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyFloat_FromDouble((double) ((float *)ap->ob_item)[i]);
}

static int
f_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    float x;
    if (!PyArg_Parse(v, "f;array item must be float", &x))
        return -1;
    if (i >= 0)
                 ((float *)ap->ob_item)[i] = x;
    return 0;
}

static PyObject *
d_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyFloat_FromDouble(((double *)ap->ob_item)[i]);
}

static int
d_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    double x;
    if (!PyArg_Parse(v, "d;array item must be float", &x))
        return -1;
    if (i >= 0)
                 ((double *)ap->ob_item)[i] = x;
    return 0;
}

#define DEFINE_COMPAREITEMS(code, type) \
    static int \
    code##_compareitems(const void *lhs, const void *rhs, Py_ssize_t length) \
    { \
        const type *a = lhs, *b = rhs; \
        for (Py_ssize_t i = 0; i < length; ++i) \
            if (a[i] != b[i]) \
                return a[i] < b[i] ? -1 : 1; \
        return 0; \
    }

DEFINE_COMPAREITEMS(b, signed char)
DEFINE_COMPAREITEMS(BB, unsigned char)
DEFINE_COMPAREITEMS(u, wchar_t)
DEFINE_COMPAREITEMS(w, Py_UCS4)
DEFINE_COMPAREITEMS(h, short)
DEFINE_COMPAREITEMS(HH, unsigned short)
DEFINE_COMPAREITEMS(i, int)
DEFINE_COMPAREITEMS(II, unsigned int)
DEFINE_COMPAREITEMS(l, long)
DEFINE_COMPAREITEMS(LL, unsigned long)
DEFINE_COMPAREITEMS(q, long long)
DEFINE_COMPAREITEMS(QQ, unsigned long long)

/* Description of types.
 *
 * Don't forget to update typecode_to_mformat_code() if you add a new
 * typecode.
 */
static const struct arraydescr descriptors[] = {
    {'b', 1, b_getitem, b_setitem, b_compareitems, "b", 1, 1},
    {'B', 1, BB_getitem, BB_setitem, BB_compareitems, "B", 1, 0},
    {'u', sizeof(wchar_t), u_getitem, u_setitem, u_compareitems, "u", 0, 0},
    {'w', sizeof(Py_UCS4), w_getitem, w_setitem, w_compareitems, "w", 0, 0,},
    {'h', sizeof(short), h_getitem, h_setitem, h_compareitems, "h", 1, 1},
    {'H', sizeof(short), HH_getitem, HH_setitem, HH_compareitems, "H", 1, 0},
    {'i', sizeof(int), i_getitem, i_setitem, i_compareitems, "i", 1, 1},
    {'I', sizeof(int), II_getitem, II_setitem, II_compareitems, "I", 1, 0},
    {'l', sizeof(long), l_getitem, l_setitem, l_compareitems, "l", 1, 1},
    {'L', sizeof(long), LL_getitem, LL_setitem, LL_compareitems, "L", 1, 0},
    {'q', sizeof(long long), q_getitem, q_setitem, q_compareitems, "q", 1, 1},
    {'Q', sizeof(long long), QQ_getitem, QQ_setitem, QQ_compareitems, "Q", 1, 0},
    {'f', sizeof(float), f_getitem, f_setitem, NULL, "f", 0, 0},
    {'d', sizeof(double), d_getitem, d_setitem, NULL, "d", 0, 0},
    {'\0', 0, 0, 0, 0, 0, 0} /* Sentinel */
};

/****************************************************************************
Implementations of array object methods.
****************************************************************************/
/*[clinic input]
class array.array "arrayobject *" "ArrayType"
[clinic start generated code]*/
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=a5c29edf59f176a3]*/

static PyObject *
newarrayobject(PyTypeObject *type, Py_ssize_t size, const struct arraydescr *descr)
{
    arrayobject *op;
    size_t nbytes;

    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }

    /* Check for overflow */
    if (size > PY_SSIZE_T_MAX / descr->itemsize) {
        return PyErr_NoMemory();
    }
    nbytes = size * descr->itemsize;
    op = (arrayobject *) type->tp_alloc(type, 0);
    if (op == NULL) {
        return NULL;
    }
    op->ob_descr = descr;
    op->allocated = size;
    op->weakreflist = NULL;
    Py_SET_SIZE(op, size);
    if (size <= 0) {
        op->ob_item = NULL;
    }
    else {
        op->ob_item = PyMem_NEW(char, nbytes);
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
    }
    op->ob_exports = 0;
    return (PyObject *) op;
}

static PyObject *
getarrayitem(PyObject *op, Py_ssize_t i)
{
#ifndef NDEBUG
    array_state *state = find_array_state_by_type(Py_TYPE(op));
    assert(array_Check(op, state));
#endif
    arrayobject *ap;
    ap = (arrayobject *)op;
    assert(i>=0 && i<Py_SIZE(ap));
    return (*ap->ob_descr->getitem)(ap, i);
}

static int
ins1(arrayobject *self, Py_ssize_t where, PyObject *v)
{
    char *items;
    Py_ssize_t n = Py_SIZE(self);
    if (v == NULL) {
        PyErr_BadInternalCall();
        return -1;
    }
    if ((*self->ob_descr->setitem)(self, -1, v) < 0)
        return -1;

    if (array_resize(self, n+1) == -1)
        return -1;
    items = self->ob_item;
    if (where < 0) {
        where += n;
        if (where < 0)
            where = 0;
    }
    if (where > n)
        where = n;
    /* appends don't need to call memmove() */
    if (where != n)
        memmove(items + (where+1)*self->ob_descr->itemsize,
            items + where*self->ob_descr->itemsize,
            (n-where)*self->ob_descr->itemsize);
    return (*self->ob_descr->setitem)(self, where, v);
}

/* Methods */

static int
array_tp_traverse(arrayobject *op, visitproc visit, void *arg)
{
    Py_VISIT(Py_TYPE(op));
    return 0;
}

static void
array_dealloc(arrayobject *op)
{
    PyTypeObject *tp = Py_TYPE(op);
    PyObject_GC_UnTrack(op);

    if (op->weakreflist != NULL)
        PyObject_ClearWeakRefs((PyObject *) op);
    if (op->ob_item != NULL)
        PyMem_Free(op->ob_item);
    tp->tp_free(op);
    Py_DECREF(tp);
}

static PyObject *
array_richcompare(PyObject *v, PyObject *w, int op)
{
    array_state *state = find_array_state_by_type(Py_TYPE(v));
    arrayobject *va, *wa;
    PyObject *vi = NULL;
    PyObject *wi = NULL;
    Py_ssize_t i, k;
    PyObject *res;

    if (!array_Check(v, state) || !array_Check(w, state))
        Py_RETURN_NOTIMPLEMENTED;

    va = (arrayobject *)v;
    wa = (arrayobject *)w;

    if (Py_SIZE(va) != Py_SIZE(wa) && (op == Py_EQ || op == Py_NE)) {
        /* Shortcut: if the lengths differ, the arrays differ */
        if (op == Py_EQ)
            res = Py_False;
        else
            res = Py_True;
        return Py_NewRef(res);
    }

    if (va->ob_descr == wa->ob_descr && va->ob_descr->compareitems != NULL) {
        /* Fast path:
           arrays with same types can have their buffers compared directly */
        Py_ssize_t common_length = Py_MIN(Py_SIZE(va), Py_SIZE(wa));
        int result = va->ob_descr->compareitems(va->ob_item, wa->ob_item,
                                                common_length);
        if (result == 0)
            goto compare_sizes;

        int cmp;
        switch (op) {
        case Py_LT: cmp = result < 0; break;
        case Py_LE: cmp = result <= 0; break;
        case Py_EQ: cmp = result == 0; break;
        case Py_NE: cmp = result != 0; break;
        case Py_GT: cmp = result > 0; break;
        case Py_GE: cmp = result >= 0; break;
        default: return NULL; /* cannot happen */
        }
        PyObject *res = cmp ? Py_True : Py_False;
        return Py_NewRef(res);
    }


    /* Search for the first index where items are different */
    k = 1;
    for (i = 0; i < Py_SIZE(va) && i < Py_SIZE(wa); i++) {
        vi = getarrayitem(v, i);
        if (vi == NULL) {
            return NULL;
        }
        wi = getarrayitem(w, i);
        if (wi == NULL) {
            Py_DECREF(vi);
            return NULL;
        }
        k = PyObject_RichCompareBool(vi, wi, Py_EQ);
        if (k == 0)
            break; /* Keeping vi and wi alive! */
        Py_DECREF(vi);
        Py_DECREF(wi);
        if (k < 0)
            return NULL;
    }

    if (k) {
        /* No more items to compare -- compare sizes */
        compare_sizes: ;
        Py_ssize_t vs = Py_SIZE(va);
        Py_ssize_t ws = Py_SIZE(wa);
        int cmp;
        switch (op) {
        case Py_LT: cmp = vs <  ws; break;
        case Py_LE: cmp = vs <= ws; break;
        /* If the lengths were not equal,
           the earlier fast-path check would have caught that. */
        case Py_EQ: assert(vs == ws); cmp = 1; break;
        case Py_NE: assert(vs == ws); cmp = 0; break;
        case Py_GT: cmp = vs >  ws; break;
        case Py_GE: cmp = vs >= ws; break;
        default: return NULL; /* cannot happen */
        }
        if (cmp)
            res = Py_True;
        else
            res = Py_False;
        return Py_NewRef(res);
    }

    /* We have an item that differs.  First, shortcuts for EQ/NE */
    if (op == Py_EQ) {
        res = Py_NewRef(Py_False);
    }
    else if (op == Py_NE) {
        res = Py_NewRef(Py_True);
    }
    else {
        /* Compare the final item again using the proper operator */
        res = PyObject_RichCompare(vi, wi, op);
    }
    Py_DECREF(vi);
    Py_DECREF(wi);
    return res;
}

static Py_ssize_t
array_length(arrayobject *a)
{
    return Py_SIZE(a);
}

static PyObject *
array_item(arrayobject *a, Py_ssize_t i)
{
    if (i < 0 || i >= Py_SIZE(a)) {
        PyErr_SetString(PyExc_IndexError, "array index out of range");
        return NULL;
    }
    return getarrayitem((PyObject *)a, i);
}

static PyObject *
array_slice(arrayobject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
    array_state *state = find_array_state_by_type(Py_TYPE(a));
    arrayobject *np;

    if (ilow < 0)
        ilow = 0;
    else if (ilow > Py_SIZE(a))
        ilow = Py_SIZE(a);
    if (ihigh < 0)
        ihigh = 0;
    if (ihigh < ilow)
        ihigh = ilow;
    else if (ihigh > Py_SIZE(a))
        ihigh = Py_SIZE(a);
    np = (arrayobject *) newarrayobject(state->ArrayType, ihigh - ilow, a->ob_descr);
    if (np == NULL)
        return NULL;
    if (ihigh > ilow) {
        memcpy(np->ob_item, a->ob_item + ilow * a->ob_descr->itemsize,
               (ihigh-ilow) * a->ob_descr->itemsize);
    }
    return (PyObject *)np;
}

/*[clinic input]
array.array.clear

Remove all items from the array.
[clinic start generated code]*/

static PyObject *
array_array_clear_impl(arrayobject *self)
/*[clinic end generated code: output=5efe0417062210a9 input=5dffa30e94e717a4]*/
{
    if (array_resize(self, 0) == -1) {
        return NULL;
    }
    Py_RETURN_NONE;
}

/*[clinic input]
array.array.__copy__

Return a copy of the array.
[clinic start generated code]*/

static PyObject *
array_array___copy___impl(arrayobject *self)
/*[clinic end generated code: output=dec7c3f925d9619e input=ad1ee5b086965f09]*/
{
    return array_slice(self, 0, Py_SIZE(self));
}

/*[clinic input]
array.array.__deepcopy__

    unused: object
    /

Return a copy of the array.
[clinic start generated code]*/

static PyObject *
array_array___deepcopy__(arrayobject *self, PyObject *unused)
/*[clinic end generated code: output=1ec748d8e14a9faa input=2405ecb4933748c4]*/
{
    return array_array___copy___impl(self);
}

static PyObject *
array_concat(arrayobject *a, PyObject *bb)
{
    array_state *state = find_array_state_by_type(Py_TYPE(a));
    Py_ssize_t size;
    arrayobject *np;
    if (!array_Check(bb, state)) {
        PyErr_Format(PyExc_TypeError,
             "can only append array (not \"%.200s\") to array",
                 Py_TYPE(bb)->tp_name);
        return NULL;
    }
#define b ((arrayobject *)bb)
    if (a->ob_descr != b->ob_descr) {
        PyErr_BadArgument();
        return NULL;
    }
    if (Py_SIZE(a) > PY_SSIZE_T_MAX - Py_SIZE(b)) {
        return PyErr_NoMemory();
    }
    size = Py_SIZE(a) + Py_SIZE(b);
    np = (arrayobject *) newarrayobject(state->ArrayType, size, a->ob_descr);
    if (np == NULL) {
        return NULL;
    }
    if (Py_SIZE(a) > 0) {
        memcpy(np->ob_item, a->ob_item, Py_SIZE(a)*a->ob_descr->itemsize);
    }
    if (Py_SIZE(b) > 0) {
        memcpy(np->ob_item + Py_SIZE(a)*a->ob_descr->itemsize,
               b->ob_item, Py_SIZE(b)*b->ob_descr->itemsize);
    }
    return (PyObject *)np;
#undef b
}

static PyObject *
array_repeat(arrayobject *a, Py_ssize_t n)
{
    array_state *state = find_array_state_by_type(Py_TYPE(a));

    if (n < 0)
        n = 0;
    const Py_ssize_t array_length = Py_SIZE(a);
    if ((array_length != 0) && (n > PY_SSIZE_T_MAX / array_length)) {
        return PyErr_NoMemory();
    }
    Py_ssize_t size = array_length * n;
    arrayobject* np = (arrayobject *) newarrayobject(state->ArrayType, size, a->ob_descr);
    if (np == NULL)
        return NULL;
    if (size == 0)
        return (PyObject *)np;

    const Py_ssize_t oldbytes = array_length * a->ob_descr->itemsize;
    const Py_ssize_t newbytes = oldbytes * n;
    _PyBytes_Repeat(np->ob_item, newbytes, a->ob_item, oldbytes);

    return (PyObject *)np;
}

static int
array_del_slice(arrayobject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
    char *item;
    Py_ssize_t d; /* Change in size */
    if (ilow < 0)
        ilow = 0;
    else if (ilow > Py_SIZE(a))
        ilow = Py_SIZE(a);
    if (ihigh < 0)
        ihigh = 0;
    if (ihigh < ilow)
        ihigh = ilow;
    else if (ihigh > Py_SIZE(a))
        ihigh = Py_SIZE(a);
    item = a->ob_item;
    d = ihigh-ilow;
    /* Issue #4509: If the array has exported buffers and the slice
       assignment would change the size of the array, fail early to make
       sure we don't modify it. */
    if (d != 0 && a->ob_exports > 0) {
        PyErr_SetString(PyExc_BufferError,
            "cannot resize an array that is exporting buffers");
        return -1;