/src/cpython/Objects/sliceobject.c

Source
/*
Written by Jim Hugunin and Chris Chase.

This includes both the singular ellipsis object and slice objects.

Guido, feel free to do whatever you want in the way of copyrights
for this file.
*/

/*
Py_Ellipsis encodes the '...' rubber index token. It is similar to
the Py_NoneStruct in that there is no way to create other objects of
this type and there is exactly one in existence.
*/

#include "Python.h"
#include "pycore_abstract.h"      // _PyIndex_Check()
#include "pycore_freelist.h"      // _Py_FREELIST_FREE(), _Py_FREELIST_POP()
#include "pycore_long.h"          // _PyLong_GetZero()
#include "pycore_modsupport.h"    // _PyArg_NoKeywords()
#include "pycore_object.h"        // _PyObject_GC_TRACK()
#include "pycore_sliceobject.h"   // _PyBuildSlice_ConsumeRefs


#define _PySlice_CAST(op) _Py_CAST(PySliceObject*, (op))


static PyObject *
ellipsis_new(PyTypeObject *type, PyObject *args, PyObject *kwargs)
{
    if (PyTuple_GET_SIZE(args) || (kwargs && PyDict_GET_SIZE(kwargs))) {
        PyErr_SetString(PyExc_TypeError, "EllipsisType takes no arguments");
        return NULL;
    }
    return Py_Ellipsis;
}

static void
ellipsis_dealloc(PyObject *ellipsis)
{
    /* This should never get called, but we also don't want to SEGV if
     * we accidentally decref Ellipsis out of existence. Instead,
     * since Ellipsis is an immortal object, re-set the reference count.
     */
    _Py_SetImmortal(ellipsis);
}

static PyObject *
ellipsis_repr(PyObject *op)
{
    return PyUnicode_FromString("Ellipsis");
}

static PyObject *
ellipsis_reduce(PyObject *op, PyObject *Py_UNUSED(ignored))
{
    return PyUnicode_FromString("Ellipsis");
}

static PyMethodDef ellipsis_methods[] = {
    {"__reduce__", ellipsis_reduce, METH_NOARGS, NULL},
    {NULL, NULL}
};

PyDoc_STRVAR(ellipsis_doc,
"ellipsis()\n"
"--\n\n"
"The type of the Ellipsis singleton.");

PyTypeObject PyEllipsis_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "ellipsis",                         /* tp_name */
    0,                                  /* tp_basicsize */
    0,                                  /* tp_itemsize */
    ellipsis_dealloc,                   /* tp_dealloc */
    0,                                  /* tp_vectorcall_offset */
    0,                                  /* tp_getattr */
    0,                                  /* tp_setattr */
    0,                                  /* tp_as_async */
    ellipsis_repr,                      /* tp_repr */
    0,                                  /* tp_as_number */
    0,                                  /* tp_as_sequence */
    0,                                  /* tp_as_mapping */
    0,                                  /* tp_hash */
    0,                                  /* tp_call */
    0,                                  /* tp_str */
    PyObject_GenericGetAttr,            /* tp_getattro */
    0,                                  /* tp_setattro */
    0,                                  /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT,                 /* tp_flags */
    ellipsis_doc,                       /* tp_doc */
    0,                                  /* tp_traverse */
    0,                                  /* tp_clear */
    0,                                  /* tp_richcompare */
    0,                                  /* tp_weaklistoffset */
    0,                                  /* tp_iter */
    0,                                  /* tp_iternext */
    ellipsis_methods,                   /* tp_methods */
    0,                                  /* tp_members */
    0,                                  /* tp_getset */
    0,                                  /* tp_base */
    0,                                  /* tp_dict */
    0,                                  /* tp_descr_get */
    0,                                  /* tp_descr_set */
    0,                                  /* tp_dictoffset */
    0,                                  /* tp_init */
    0,                                  /* tp_alloc */
    ellipsis_new,                       /* tp_new */
};

PyObject _Py_EllipsisObject = _PyObject_HEAD_INIT(&PyEllipsis_Type);


/* Slice object implementation */

/* start, stop, and step are python objects with None indicating no
   index is present.
*/

static PySliceObject *
_PyBuildSlice_Consume2(PyObject *start, PyObject *stop, PyObject *step)
{
    assert(start != NULL && stop != NULL && step != NULL);
    PySliceObject *obj = _Py_FREELIST_POP(PySliceObject, slices);
    if (obj == NULL) {
        obj = PyObject_GC_New(PySliceObject, &PySlice_Type);
        if (obj == NULL) {
            goto error;
        }
    }

    obj->start = start;
    obj->stop = stop;
    obj->step = Py_NewRef(step);

    _PyObject_GC_TRACK(obj);
    return obj;
error:
    Py_DECREF(start);
    Py_DECREF(stop);
    return NULL;
}

PyObject *
PySlice_New(PyObject *start, PyObject *stop, PyObject *step)
{
    if (step == NULL) {
        step = Py_None;
    }
    if (start == NULL) {
        start = Py_None;
    }
    if (stop == NULL) {
        stop = Py_None;
    }
    return (PyObject *)_PyBuildSlice_Consume2(Py_NewRef(start),
                                              Py_NewRef(stop), step);
}

PyObject *
_PyBuildSlice_ConsumeRefs(PyObject *start, PyObject *stop)
{
    assert(start != NULL && stop != NULL);
    return (PyObject *)_PyBuildSlice_Consume2(start, stop, Py_None);
}

PyObject *
_PySlice_FromIndices(Py_ssize_t istart, Py_ssize_t istop)
{
    PyObject *start, *end, *slice;
    start = PyLong_FromSsize_t(istart);
    if (!start)
        return NULL;
    end = PyLong_FromSsize_t(istop);
    if (!end) {
        Py_DECREF(start);
        return NULL;
    }

    slice = PySlice_New(start, end, NULL);
    Py_DECREF(start);
    Py_DECREF(end);
    return slice;
}

int
PySlice_GetIndices(PyObject *_r, Py_ssize_t length,
                   Py_ssize_t *start, Py_ssize_t *stop, Py_ssize_t *step)
{
    PySliceObject *r = (PySliceObject*)_r;
    /* XXX support long ints */
    if (r->step == Py_None) {
        *step = 1;
    } else {
        if (!PyLong_Check(r->step)) return -1;
        *step = PyLong_AsSsize_t(r->step);
    }
    if (r->start == Py_None) {
        *start = *step < 0 ? length-1 : 0;
    } else {
        if (!PyLong_Check(r->start)) return -1;
        *start = PyLong_AsSsize_t(r->start);
        if (*start < 0) *start += length;
    }
    if (r->stop == Py_None) {
        *stop = *step < 0 ? -1 : length;
    } else {
        if (!PyLong_Check(r->stop)) return -1;
        *stop = PyLong_AsSsize_t(r->stop);
        if (*stop < 0) *stop += length;
    }
    if (*stop > length) return -1;
    if (*start >= length) return -1;
    if (*step == 0) return -1;
    return 0;
}

int
PySlice_Unpack(PyObject *_r,
               Py_ssize_t *start, Py_ssize_t *stop, Py_ssize_t *step)
{
    PySliceObject *r = (PySliceObject*)_r;
    /* this is harder to get right than you might think */

    static_assert(PY_SSIZE_T_MIN + 1 <= -PY_SSIZE_T_MAX,
                  "-PY_SSIZE_T_MAX < PY_SSIZE_T_MIN + 1");

    if (r->step == Py_None) {
        *step = 1;
    }
    else {
        if (!_PyEval_SliceIndex(r->step, step)) return -1;
        if (*step == 0) {
            PyErr_SetString(PyExc_ValueError,
                            "slice step cannot be zero");
            return -1;
        }
        /* Here *step might be -PY_SSIZE_T_MAX-1; in this case we replace it
         * with -PY_SSIZE_T_MAX.  This doesn't affect the semantics, and it
         * guards against later undefined behaviour resulting from code that
         * does "step = -step" as part of a slice reversal.
         */
        if (*step < -PY_SSIZE_T_MAX)
            *step = -PY_SSIZE_T_MAX;
    }

    if (r->start == Py_None) {
        *start = *step < 0 ? PY_SSIZE_T_MAX : 0;
    }
    else {
        if (!_PyEval_SliceIndex(r->start, start)) return -1;
    }

    if (r->stop == Py_None) {
        *stop = *step < 0 ? PY_SSIZE_T_MIN : PY_SSIZE_T_MAX;
    }
    else {
        if (!_PyEval_SliceIndex(r->stop, stop)) return -1;
    }

    return 0;
}

Py_ssize_t
PySlice_AdjustIndices(Py_ssize_t length,
                      Py_ssize_t *start, Py_ssize_t *stop, Py_ssize_t step)
{
    /* this is harder to get right than you might think */

    assert(step != 0);
    assert(step >= -PY_SSIZE_T_MAX);

    if (*start < 0) {
        *start += length;
        if (*start < 0) {
            *start = (step < 0) ? -1 : 0;
        }
    }
    else if (*start >= length) {
        *start = (step < 0) ? length - 1 : length;
    }

    if (*stop < 0) {
        *stop += length;
        if (*stop < 0) {
            *stop = (step < 0) ? -1 : 0;
        }
    }
    else if (*stop >= length) {
        *stop = (step < 0) ? length - 1 : length;
    }

    if (step < 0) {
        if (*stop < *start) {
            return (*start - *stop - 1) / (-step) + 1;
        }
    }
    else {
        if (*start < *stop) {
            return (*stop - *start - 1) / step + 1;
        }
    }
    return 0;
}

#undef PySlice_GetIndicesEx

int
PySlice_GetIndicesEx(PyObject *_r, Py_ssize_t length,
                     Py_ssize_t *start, Py_ssize_t *stop, Py_ssize_t *step,
                     Py_ssize_t *slicelength)
{
    if (PySlice_Unpack(_r, start, stop, step) < 0)
        return -1;
    *slicelength = PySlice_AdjustIndices(length, start, stop, *step);
    return 0;
}

static PyObject *
slice_new(PyTypeObject *type, PyObject *args, PyObject *kw)
{
    PyObject *start, *stop, *step;

    start = stop = step = NULL;

    if (!_PyArg_NoKeywords("slice", kw))
        return NULL;

    if (!PyArg_UnpackTuple(args, "slice", 1, 3, &start, &stop, &step))
        return NULL;

    /* This swapping of stop and start is to maintain similarity with
       range(). */
    if (stop == NULL) {
        stop = start;
        start = NULL;
    }
    return PySlice_New(start, stop, step);
}

PyDoc_STRVAR(slice_doc,
"slice(stop)\n\
slice(start, stop[, step])\n\
\n\
Create a slice object.  This is used for extended slicing (e.g. a[0:10:2]).");

static void
slice_dealloc(PyObject *op)
{
    PySliceObject *r = _PySlice_CAST(op);
    PyObject_GC_UnTrack(r);
    Py_DECREF(r->step);
    Py_DECREF(r->start);
    Py_DECREF(r->stop);
    _Py_FREELIST_FREE(slices, r, PyObject_GC_Del);
}

static PyObject *
slice_repr(PyObject *op)
{
    PySliceObject *r = _PySlice_CAST(op);
    return PyUnicode_FromFormat("slice(%R, %R, %R)",
                                r->start, r->stop, r->step);
}

static PyMemberDef slice_members[] = {
    {"start", _Py_T_OBJECT, offsetof(PySliceObject, start), Py_READONLY},
    {"stop", _Py_T_OBJECT, offsetof(PySliceObject, stop), Py_READONLY},
    {"step", _Py_T_OBJECT, offsetof(PySliceObject, step), Py_READONLY},
    {0}
};

/* Helper function to convert a slice argument to a PyLong, and raise TypeError
   with a suitable message on failure. */

static PyObject*
evaluate_slice_index(PyObject *v)
{
    if (_PyIndex_Check(v)) {
        return PyNumber_Index(v);
    }
    else {
        PyErr_SetString(PyExc_TypeError,
                        "slice indices must be integers or "
                        "None or have an __index__ method");
        return NULL;
    }
}

/* Compute slice indices given a slice and length.  Return -1 on failure.  Used
   by slice.indices and rangeobject slicing.  Assumes that `len` is a
   nonnegative instance of PyLong. */

int
_PySlice_GetLongIndices(PySliceObject *self, PyObject *length,
                        PyObject **start_ptr, PyObject **stop_ptr,
                        PyObject **step_ptr)
{
    PyObject *start=NULL, *stop=NULL, *step=NULL;
    PyObject *upper=NULL, *lower=NULL;
    int step_is_negative, cmp_result;

    /* Convert step to an integer; raise for zero step. */
    if (self->step == Py_None) {
        step = _PyLong_GetOne();
        step_is_negative = 0;
    }
    else {
        step = evaluate_slice_index(self->step);
        if (step == NULL) {
            goto error;
        }
        assert(PyLong_Check(step));

        int step_sign;
        (void)PyLong_GetSign(step, &step_sign);
        if (step_sign == 0) {
            PyErr_SetString(PyExc_ValueError,
                            "slice step cannot be zero");
            goto error;
        }
        step_is_negative = step_sign < 0;
    }

    /* Find lower and upper bounds for start and stop. */
    if (step_is_negative) {
        lower = PyLong_FromLong(-1L);
        if (lower == NULL)
            goto error;

        upper = PyNumber_Add(length, lower);
        if (upper == NULL)
            goto error;
    }
    else {
        lower = _PyLong_GetZero();
        upper = Py_NewRef(length);
    }

    /* Compute start. */
    if (self->start == Py_None) {
        start = Py_NewRef(step_is_negative ? upper : lower);
    }
    else {
        start = evaluate_slice_index(self->start);
        if (start == NULL)
            goto error;

        if (_PyLong_IsNegative((PyLongObject *)start)) {
            /* start += length */
            PyObject *tmp = PyNumber_Add(start, length);
            Py_SETREF(start, tmp);
            if (start == NULL)
                goto error;

            cmp_result = PyObject_RichCompareBool(start, lower, Py_LT);
            if (cmp_result < 0)
                goto error;
            if (cmp_result) {
                Py_SETREF(start, Py_NewRef(lower));
            }
        }
        else {
            cmp_result = PyObject_RichCompareBool(start, upper, Py_GT);
            if (cmp_result < 0)
                goto error;
            if (cmp_result) {
                Py_SETREF(start, Py_NewRef(upper));
            }
        }
    }

    /* Compute stop. */
    if (self->stop == Py_None) {
        stop = Py_NewRef(step_is_negative ? lower : upper);
    }
    else {
        stop = evaluate_slice_index(self->stop);
        if (stop == NULL)
            goto error;

        if (_PyLong_IsNegative((PyLongObject *)stop)) {
            /* stop += length */
            PyObject *tmp = PyNumber_Add(stop, length);
            Py_SETREF(stop, tmp);
            if (stop == NULL)
                goto error;

            cmp_result = PyObject_RichCompareBool(stop, lower, Py_LT);
            if (cmp_result < 0)
                goto error;
            if (cmp_result) {
                Py_SETREF(stop, Py_NewRef(lower));
            }
        }
        else {
            cmp_result = PyObject_RichCompareBool(stop, upper, Py_GT);
            if (cmp_result < 0)
                goto error;
            if (cmp_result) {
                Py_SETREF(stop, Py_NewRef(upper));
            }
        }
    }

    *start_ptr = start;
    *stop_ptr = stop;
    *step_ptr = step;
    Py_DECREF(upper);
    Py_DECREF(lower);
    return 0;

  error:
    *start_ptr = *stop_ptr = *step_ptr = NULL;
    Py_XDECREF(start);
    Py_XDECREF(stop);
    Py_XDECREF(step);
    Py_XDECREF(upper);
    Py_XDECREF(lower);
    return -1;
}

/* Implementation of slice.indices. */

static PyObject*
slice_indices(PyObject *op, PyObject* len)
{
    PySliceObject *self = _PySlice_CAST(op);
    PyObject *start, *stop, *step;
    PyObject *length;
    int error;

    /* Convert length to an integer if necessary; raise for negative length. */
    length = PyNumber_Index(len);
    if (length == NULL)
        return NULL;

    if (_PyLong_IsNegative((PyLongObject *)length)) {
        PyErr_SetString(PyExc_ValueError,
                        "length should not be negative");
        Py_DECREF(length);
        return NULL;
    }

    error = _PySlice_GetLongIndices(self, length, &start, &stop, &step);
    Py_DECREF(length);
    if (error == -1)
        return NULL;
    else
        return Py_BuildValue("(NNN)", start, stop, step);
}

PyDoc_STRVAR(slice_indices_doc,
"S.indices(len) -> (start, stop, stride)\n\
\n\
Assuming a sequence of length len, calculate the start and stop\n\
indices, and the stride length of the extended slice described by\n\
S. Out of bounds indices are clipped in a manner consistent with the\n\
handling of normal slices.");

static PyObject *
slice_reduce(PyObject *op, PyObject *Py_UNUSED(ignored))
{
    PySliceObject *self = _PySlice_CAST(op);
    return Py_BuildValue("O(OOO)", Py_TYPE(self), self->start, self->stop, self->step);
}

PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");

static PyMethodDef slice_methods[] = {
    {"indices", slice_indices, METH_O, slice_indices_doc},
    {"__reduce__", slice_reduce, METH_NOARGS, reduce_doc},
    {"__class_getitem__", Py_GenericAlias, METH_O|METH_CLASS, "See PEP 585"},
    {NULL, NULL}
};

static PyObject *
slice_richcompare(PyObject *v, PyObject *w, int op)
{
    if (!PySlice_Check(v) || !PySlice_Check(w))
        Py_RETURN_NOTIMPLEMENTED;

    if (v == w) {
        PyObject *res;
        /* XXX Do we really need this shortcut?
           There's a unit test for it, but is that fair? */
        switch (op) {
        case Py_EQ:
        case Py_LE:
        case Py_GE:
            res = Py_True;
            break;
        default:
            res = Py_False;
            break;
        }
        return Py_NewRef(res);
    }


    PyObject *t1 = PyTuple_Pack(3,
                                ((PySliceObject *)v)->start,
                                ((PySliceObject *)v)->stop,
                                ((PySliceObject *)v)->step);
    if (t1 == NULL) {
        return NULL;
    }

    PyObject *t2 = PyTuple_Pack(3,
                                ((PySliceObject *)w)->start,
                                ((PySliceObject *)w)->stop,
                                ((PySliceObject *)w)->step);
    if (t2 == NULL) {
        Py_DECREF(t1);
        return NULL;
    }

    PyObject *res = PyObject_RichCompare(t1, t2, op);
    Py_DECREF(t1);
    Py_DECREF(t2);
    return res;
}

static int
slice_traverse(PyObject *op, visitproc visit, void *arg)
{
    PySliceObject *v = _PySlice_CAST(op);
    Py_VISIT(v->start);
    Py_VISIT(v->stop);
    Py_VISIT(v->step);
    return 0;
}

/* code based on tuplehash() of Objects/tupleobject.c */
#if SIZEOF_PY_UHASH_T > 4
#define _PyHASH_XXPRIME_1 ((Py_uhash_t)11400714785074694791ULL)
#define _PyHASH_XXPRIME_2 ((Py_uhash_t)14029467366897019727ULL)
#define _PyHASH_XXPRIME_5 ((Py_uhash_t)2870177450012600261ULL)
#define _PyHASH_XXROTATE(x) ((x << 31) | (x >> 33))  /* Rotate left 31 bits */
#else
#define _PyHASH_XXPRIME_1 ((Py_uhash_t)2654435761UL)
#define _PyHASH_XXPRIME_2 ((Py_uhash_t)2246822519UL)
#define _PyHASH_XXPRIME_5 ((Py_uhash_t)374761393UL)
#define _PyHASH_XXROTATE(x) ((x << 13) | (x >> 19))  /* Rotate left 13 bits */
#endif

static Py_hash_t
slice_hash(PyObject *op)
{
    PySliceObject *v = _PySlice_CAST(op);
    Py_uhash_t acc = _PyHASH_XXPRIME_5;
#define _PyHASH_SLICE_PART(com) { \
    Py_uhash_t lane = PyObject_Hash(v->com); \
    if(lane == (Py_uhash_t)-1) { \
        return -1; \
    } \
    acc += lane * _PyHASH_XXPRIME_2; \
    acc = _PyHASH_XXROTATE(acc); \
    acc *= _PyHASH_XXPRIME_1; \
}
    _PyHASH_SLICE_PART(start);
    _PyHASH_SLICE_PART(stop);
    _PyHASH_SLICE_PART(step);
#undef _PyHASH_SLICE_PART
    if(acc == (Py_uhash_t)-1) {
        return 1546275796;
    }
    return acc;
}

PyTypeObject PySlice_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "slice",                    /* Name of this type */
    sizeof(PySliceObject),      /* Basic object size */
    0,                          /* Item size for varobject */
    slice_dealloc,                              /* tp_dealloc */
    0,                                          /* tp_vectorcall_offset */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_as_async */
    slice_repr,                                 /* tp_repr */
    0,                                          /* tp_as_number */
    0,                                          /* tp_as_sequence */
    0,                                          /* tp_as_mapping */
    slice_hash,                                 /* tp_hash */
    0,                                          /* tp_call */
    0,                                          /* tp_str */
    PyObject_GenericGetAttr,                    /* tp_getattro */
    0,                                          /* tp_setattro */
    0,                                          /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,    /* tp_flags */
    slice_doc,                                  /* tp_doc */
    slice_traverse,                             /* tp_traverse */
    0,                                          /* tp_clear */
    slice_richcompare,                          /* tp_richcompare */
    0,                                          /* tp_weaklistoffset */
    0,                                          /* tp_iter */
    0,                                          /* tp_iternext */
    slice_methods,                              /* tp_methods */
    slice_members,                              /* tp_members */
    0,                                          /* tp_getset */
    0,                                          /* tp_base */
    0,                                          /* tp_dict */
    0,                                          /* tp_descr_get */
    0,                                          /* tp_descr_set */
    0,                                          /* tp_dictoffset */
    0,                                          /* tp_init */
    0,                                          /* tp_alloc */
    slice_new,                                  /* tp_new */
};

Coverage Report

Created: 2026-02-26 06:53

Line	Count	Source
1		/*
2		Written by Jim Hugunin and Chris Chase.
3
4		This includes both the singular ellipsis object and slice objects.
5
6		Guido, feel free to do whatever you want in the way of copyrights
7		for this file.
8		*/
9
10		/*
11		Py_Ellipsis encodes the '...' rubber index token. It is similar to
12		the Py_NoneStruct in that there is no way to create other objects of
13		this type and there is exactly one in existence.
14		*/
15
16		#include "Python.h"
17		#include "pycore_abstract.h" // _PyIndex_Check()
18		#include "pycore_freelist.h" // _Py_FREELIST_FREE(), _Py_FREELIST_POP()
19		#include "pycore_long.h" // _PyLong_GetZero()
20		#include "pycore_modsupport.h" // _PyArg_NoKeywords()
21		#include "pycore_object.h" // _PyObject_GC_TRACK()
22		#include "pycore_sliceobject.h" // _PyBuildSlice_ConsumeRefs
23
24
25	85.1M	#define _PySlice_CAST(op) _Py_CAST(PySliceObject*, (op))
26
27
28		static PyObject *
29		ellipsis_new(PyTypeObject type, PyObject args, PyObject *kwargs)
30	0	{
31	0	if (PyTuple_GET_SIZE(args) \|\| (kwargs && PyDict_GET_SIZE(kwargs))) {
32	0	PyErr_SetString(PyExc_TypeError, "EllipsisType takes no arguments");
33	0	return NULL;
34	0	}
35	0	return Py_Ellipsis;
36	0	}
37
38		static void
39		ellipsis_dealloc(PyObject *ellipsis)
40	0	{
41		/* This should never get called, but we also don't want to SEGV if
42		* we accidentally decref Ellipsis out of existence. Instead,
43		* since Ellipsis is an immortal object, re-set the reference count.
44		*/
45	0	_Py_SetImmortal(ellipsis);
46	0	}
47
48		static PyObject *
49		ellipsis_repr(PyObject *op)
50	0	{
51	0	return PyUnicode_FromString("Ellipsis");
52	0	}
53
54		static PyObject *
55		ellipsis_reduce(PyObject op, PyObject Py_UNUSED(ignored))
56	0	{
57	0	return PyUnicode_FromString("Ellipsis");
58	0	}
59
60		static PyMethodDef ellipsis_methods[] = {
61		{"__reduce__", ellipsis_reduce, METH_NOARGS, NULL},
62		{NULL, NULL}
63		};
64
65		PyDoc_STRVAR(ellipsis_doc,
66		"ellipsis()\n"
67		"--\n\n"
68		"The type of the Ellipsis singleton.");
69
70		PyTypeObject PyEllipsis_Type = {
71		PyVarObject_HEAD_INIT(&PyType_Type, 0)
72		"ellipsis", /* tp_name */
73		0, /* tp_basicsize */
74		0, /* tp_itemsize */
75		ellipsis_dealloc, /* tp_dealloc */
76		0, /* tp_vectorcall_offset */
77		0, /* tp_getattr */
78		0, /* tp_setattr */
79		0, /* tp_as_async */
80		ellipsis_repr, /* tp_repr */
81		0, /* tp_as_number */
82		0, /* tp_as_sequence */
83		0, /* tp_as_mapping */
84		0, /* tp_hash */
85		0, /* tp_call */
86		0, /* tp_str */
87		PyObject_GenericGetAttr, /* tp_getattro */
88		0, /* tp_setattro */
89		0, /* tp_as_buffer */
90		Py_TPFLAGS_DEFAULT, /* tp_flags */
91		ellipsis_doc, /* tp_doc */
92		0, /* tp_traverse */
93		0, /* tp_clear */
94		0, /* tp_richcompare */
95		0, /* tp_weaklistoffset */
96		0, /* tp_iter */
97		0, /* tp_iternext */
98		ellipsis_methods, /* tp_methods */
99		0, /* tp_members */
100		0, /* tp_getset */
101		0, /* tp_base */
102		0, /* tp_dict */
103		0, /* tp_descr_get */
104		0, /* tp_descr_set */
105		0, /* tp_dictoffset */
106		0, /* tp_init */
107		0, /* tp_alloc */
108		ellipsis_new, /* tp_new */
109		};
110
111		PyObject _Py_EllipsisObject = _PyObject_HEAD_INIT(&PyEllipsis_Type);
112
113
114		/* Slice object implementation */
115
116		/* start, stop, and step are python objects with None indicating no
117		index is present.
118		*/
119
120		static PySliceObject *
121		_PyBuildSlice_Consume2(PyObject start, PyObject stop, PyObject *step)
122	84.7M	{
123	84.7M	assert(start != NULL && stop != NULL && step != NULL);
124	84.7M	PySliceObject *obj = _Py_FREELIST_POP(PySliceObject, slices);
125	84.7M	if (obj == NULL) {
126	2.91k	obj = PyObject_GC_New(PySliceObject, &PySlice_Type);
127	2.91k	if (obj == NULL) {
128	0	goto error;
129	0	}
130	2.91k	}
131
132	84.7M	obj->start = start;
133	84.7M	obj->stop = stop;
134	84.7M	obj->step = Py_NewRef(step);
135
136	84.7M	_PyObject_GC_TRACK(obj);
137	84.7M	return obj;
138	0	error:
139	0	Py_DECREF(start);
140	0	Py_DECREF(stop);
141	0	return NULL;
142	84.7M	}
143
144		PyObject *
145		PySlice_New(PyObject start, PyObject stop, PyObject *step)
146	1.88M	{
147	1.88M	if (step == NULL) {
148	256	step = Py_None;
149	256	}
150	1.88M	if (start == NULL) {
151	32	start = Py_None;
152	32	}
153	1.88M	if (stop == NULL) {
154	26	stop = Py_None;
155	26	}
156	1.88M	return (PyObject *)_PyBuildSlice_Consume2(Py_NewRef(start),
157	1.88M	Py_NewRef(stop), step);
158	1.88M	}
159
160		PyObject *
161		_PyBuildSlice_ConsumeRefs(PyObject start, PyObject stop)
162	82.8M	{
163	82.8M	assert(start != NULL && stop != NULL);
164	82.8M	return (PyObject *)_PyBuildSlice_Consume2(start, stop, Py_None);
165	82.8M	}
166
167		PyObject *
168		_PySlice_FromIndices(Py_ssize_t istart, Py_ssize_t istop)
169	164	{
170	164	PyObject start, end, *slice;
171	164	start = PyLong_FromSsize_t(istart);
172	164	if (!start)
173	0	return NULL;
174	164	end = PyLong_FromSsize_t(istop);
175	164	if (!end) {
176	0	Py_DECREF(start);
177	0	return NULL;
178	0	}
179
180	164	slice = PySlice_New(start, end, NULL);
181	164	Py_DECREF(start);
182	164	Py_DECREF(end);
183	164	return slice;
184	164	}
185
186		int
187		PySlice_GetIndices(PyObject *_r, Py_ssize_t length,
188		Py_ssize_t start, Py_ssize_t stop, Py_ssize_t *step)
189	0	{
190	0	PySliceObject r = (PySliceObject)_r;
191		/* XXX support long ints */
192	0	if (r->step == Py_None) {
193	0	*step = 1;
194	0	} else {
195	0	if (!PyLong_Check(r->step)) return -1;
196	0	*step = PyLong_AsSsize_t(r->step);
197	0	}
198	0	if (r->start == Py_None) {
199	0	start = step < 0 ? length-1 : 0;
200	0	} else {
201	0	if (!PyLong_Check(r->start)) return -1;
202	0	*start = PyLong_AsSsize_t(r->start);
203	0	if (start < 0) start += length;
204	0	}
205	0	if (r->stop == Py_None) {
206	0	stop = step < 0 ? -1 : length;
207	0	} else {
208	0	if (!PyLong_Check(r->stop)) return -1;
209	0	*stop = PyLong_AsSsize_t(r->stop);
210	0	if (stop < 0) stop += length;
211	0	}
212	0	if (*stop > length) return -1;
213	0	if (*start >= length) return -1;
214	0	if (*step == 0) return -1;
215	0	return 0;
216	0	}
217
218		int
219		PySlice_Unpack(PyObject *_r,
220		Py_ssize_t start, Py_ssize_t stop, Py_ssize_t *step)
221	134M	{
222	134M	PySliceObject r = (PySliceObject)_r;
223		/* this is harder to get right than you might think */
224
225	134M	static_assert(PY_SSIZE_T_MIN + 1 <= -PY_SSIZE_T_MAX,
226	134M	"-PY_SSIZE_T_MAX < PY_SSIZE_T_MIN + 1");
227
228	134M	if (r->step == Py_None) {
229	134M	*step = 1;
230	134M	}
231	113k	else {
232	113k	if (!_PyEval_SliceIndex(r->step, step)) return -1;
233	113k	if (*step == 0) {
234	0	PyErr_SetString(PyExc_ValueError,
235	0	"slice step cannot be zero");
236	0	return -1;
237	0	}
238		/* Here *step might be -PY_SSIZE_T_MAX-1; in this case we replace it
239		* with -PY_SSIZE_T_MAX. This doesn't affect the semantics, and it
240		* guards against later undefined behaviour resulting from code that
241		* does "step = -step" as part of a slice reversal.
242		*/
243	113k	if (*step < -PY_SSIZE_T_MAX)
244	0	*step = -PY_SSIZE_T_MAX;
245	113k	}
246
247	134M	if (r->start == Py_None) {
248	32.2M	start = step < 0 ? PY_SSIZE_T_MAX : 0;
249	32.2M	}
250	102M	else {
251	102M	if (!_PyEval_SliceIndex(r->start, start)) return -1;
252	102M	}
253
254	134M	if (r->stop == Py_None) {
255	29.7M	stop = step < 0 ? PY_SSIZE_T_MIN : PY_SSIZE_T_MAX;
256	29.7M	}
257	105M	else {
258	105M	if (!_PyEval_SliceIndex(r->stop, stop)) return -1;
259	105M	}
260
261	134M	return 0;
262	134M	}
263
264		Py_ssize_t
265		PySlice_AdjustIndices(Py_ssize_t length,
266		Py_ssize_t start, Py_ssize_t stop, Py_ssize_t step)
267	134M	{
268		/* this is harder to get right than you might think */
269
270	134M	assert(step != 0);
271	134M	assert(step >= -PY_SSIZE_T_MAX);
272
273	134M	if (*start < 0) {
274	2.44M	*start += length;
275	2.44M	if (*start < 0) {
276	0	*start = (step < 0) ? -1 : 0;
277	0	}
278	2.44M	}
279	132M	else if (*start >= length) {
280	9.72M	*start = (step < 0) ? length - 1 : length;
281	9.72M	}
282
283	134M	if (*stop < 0) {
284	2.51M	*stop += length;
285	2.51M	if (*stop < 0) {
286	113k	*stop = (step < 0) ? -1 : 0;
287	113k	}
288	2.51M	}
289	132M	else if (*stop >= length) {
290	37.7M	*stop = (step < 0) ? length - 1 : length;
291	37.7M	}
292
293	134M	if (step < 0) {
294	113k	if (stop < start) {
295	113k	return (start - stop - 1) / (-step) + 1;
296	113k	}
297	113k	}
298	134M	else {
299	134M	if (start < stop) {
300	119M	return (stop - start - 1) / step + 1;
301	119M	}
302	134M	}
303	15.0M	return 0;
304	134M	}
305
306		#undef PySlice_GetIndicesEx
307
308		int
309		PySlice_GetIndicesEx(PyObject *_r, Py_ssize_t length,
310		Py_ssize_t start, Py_ssize_t stop, Py_ssize_t *step,
311		Py_ssize_t *slicelength)
312	0	{
313	0	if (PySlice_Unpack(_r, start, stop, step) < 0)
314	0	return -1;
315	0	slicelength = PySlice_AdjustIndices(length, start, stop, step);
316	0	return 0;
317	0	}
318
319		static PyObject *
320		slice_new(PyTypeObject type, PyObject args, PyObject *kw)
321	12	{
322	12	PyObject start, stop, *step;
323
324	12	start = stop = step = NULL;
325
326	12	if (!_PyArg_NoKeywords("slice", kw))
327	0	return NULL;
328
329	12	if (!PyArg_UnpackTuple(args, "slice", 1, 3, &start, &stop, &step))
330	0	return NULL;
331
332		/* This swapping of stop and start is to maintain similarity with
333		range(). */
334	12	if (stop == NULL) {
335	6	stop = start;
336	6	start = NULL;
337	6	}
338	12	return PySlice_New(start, stop, step);
339	12	}
340
341		PyDoc_STRVAR(slice_doc,
342		"slice(stop)\n\
343		slice(start, stop[, step])\n\
344		\n\
345		Create a slice object. This is used for extended slicing (e.g. a[0:10:2]).");
346
347		static void
348		slice_dealloc(PyObject *op)
349	84.7M	{
350	84.7M	PySliceObject *r = _PySlice_CAST(op);
351	84.7M	PyObject_GC_UnTrack(r);
352	84.7M	Py_DECREF(r->step);
353	84.7M	Py_DECREF(r->start);
354	84.7M	Py_DECREF(r->stop);
355	84.7M	_Py_FREELIST_FREE(slices, r, PyObject_GC_Del);
356	84.7M	}
357
358		static PyObject *
359		slice_repr(PyObject *op)
360	0	{
361	0	PySliceObject *r = _PySlice_CAST(op);
362	0	return PyUnicode_FromFormat("slice(%R, %R, %R)",
363	0	r->start, r->stop, r->step);
364	0	}
365
366		static PyMemberDef slice_members[] = {
367		{"start", _Py_T_OBJECT, offsetof(PySliceObject, start), Py_READONLY},
368		{"stop", _Py_T_OBJECT, offsetof(PySliceObject, stop), Py_READONLY},
369		{"step", _Py_T_OBJECT, offsetof(PySliceObject, step), Py_READONLY},
370		{0}
371		};
372
373		/* Helper function to convert a slice argument to a PyLong, and raise TypeError
374		with a suitable message on failure. */
375
376		static PyObject*
377		evaluate_slice_index(PyObject *v)
378	1.76M	{
379	1.76M	if (_PyIndex_Check(v)) {
380	1.76M	return PyNumber_Index(v);
381	1.76M	}
382	0	else {
383	0	PyErr_SetString(PyExc_TypeError,
384	0	"slice indices must be integers or "
385	0	"None or have an __index__ method");
386	0	return NULL;
387	0	}
388	1.76M	}
389
390		/* Compute slice indices given a slice and length. Return -1 on failure. Used
391		by slice.indices and rangeobject slicing. Assumes that `len` is a
392		nonnegative instance of PyLong. */
393
394		int
395		_PySlice_GetLongIndices(PySliceObject self, PyObject length,
396		PyObject start_ptr, PyObject stop_ptr,
397		PyObject **step_ptr)
398	1.76M	{
399	1.76M	PyObject start=NULL, stop=NULL, *step=NULL;
400	1.76M	PyObject upper=NULL, lower=NULL;
401	1.76M	int step_is_negative, cmp_result;
402
403		/* Convert step to an integer; raise for zero step. */
404	1.76M	if (self->step == Py_None) {
405	0	step = _PyLong_GetOne();
406	0	step_is_negative = 0;
407	0	}
408	1.76M	else {
409	1.76M	step = evaluate_slice_index(self->step);
410	1.76M	if (step == NULL) {
411	0	goto error;
412	0	}
413	1.76M	assert(PyLong_Check(step));
414
415	1.76M	int step_sign;
416	1.76M	(void)PyLong_GetSign(step, &step_sign);
417	1.76M	if (step_sign == 0) {
418	0	PyErr_SetString(PyExc_ValueError,
419	0	"slice step cannot be zero");
420	0	goto error;
421	0	}
422	1.76M	step_is_negative = step_sign < 0;
423	1.76M	}
424
425		/* Find lower and upper bounds for start and stop. */
426	1.76M	if (step_is_negative) {
427	1.76M	lower = PyLong_FromLong(-1L);
428	1.76M	if (lower == NULL)
429	0	goto error;
430
431	1.76M	upper = PyNumber_Add(length, lower);
432	1.76M	if (upper == NULL)
433	0	goto error;
434	1.76M	}
435	0	else {
436	0	lower = _PyLong_GetZero();
437	0	upper = Py_NewRef(length);
438	0	}
439
440		/* Compute start. */
441	1.76M	if (self->start == Py_None) {
442	1.76M	start = Py_NewRef(step_is_negative ? upper : lower);
443	1.76M	}
444	0	else {
445	0	start = evaluate_slice_index(self->start);
446	0	if (start == NULL)
447	0	goto error;
448
449	0	if (_PyLong_IsNegative((PyLongObject *)start)) {
450		/* start += length */
451	0	PyObject *tmp = PyNumber_Add(start, length);
452	0	Py_SETREF(start, tmp);
453	0	if (start == NULL)
454	0	goto error;
455
456	0	cmp_result = PyObject_RichCompareBool(start, lower, Py_LT);
457	0	if (cmp_result < 0)
458	0	goto error;
459	0	if (cmp_result) {
460	0	Py_SETREF(start, Py_NewRef(lower));
461	0	}
462	0	}
463	0	else {
464	0	cmp_result = PyObject_RichCompareBool(start, upper, Py_GT);
465	0	if (cmp_result < 0)
466	0	goto error;
467	0	if (cmp_result) {
468	0	Py_SETREF(start, Py_NewRef(upper));
469	0	}
470	0	}
471	0	}
472
473		/* Compute stop. */
474	1.76M	if (self->stop == Py_None) {
475	1.76M	stop = Py_NewRef(step_is_negative ? lower : upper);
476	1.76M	}
477	0	else {
478	0	stop = evaluate_slice_index(self->stop);
479	0	if (stop == NULL)
480	0	goto error;
481
482	0	if (_PyLong_IsNegative((PyLongObject *)stop)) {
483		/* stop += length */
484	0	PyObject *tmp = PyNumber_Add(stop, length);
485	0	Py_SETREF(stop, tmp);
486	0	if (stop == NULL)
487	0	goto error;
488
489	0	cmp_result = PyObject_RichCompareBool(stop, lower, Py_LT);
490	0	if (cmp_result < 0)
491	0	goto error;
492	0	if (cmp_result) {
493	0	Py_SETREF(stop, Py_NewRef(lower));
494	0	}
495	0	}
496	0	else {
497	0	cmp_result = PyObject_RichCompareBool(stop, upper, Py_GT);
498	0	if (cmp_result < 0)
499	0	goto error;
500	0	if (cmp_result) {
501	0	Py_SETREF(stop, Py_NewRef(upper));
502	0	}
503	0	}
504	0	}
505
506	1.76M	*start_ptr = start;
507	1.76M	*stop_ptr = stop;
508	1.76M	*step_ptr = step;
509	1.76M	Py_DECREF(upper);
510	1.76M	Py_DECREF(lower);
511	1.76M	return 0;
512
513	0	error:
514	0	start_ptr = stop_ptr = *step_ptr = NULL;
515	0	Py_XDECREF(start);
516	0	Py_XDECREF(stop);
517	0	Py_XDECREF(step);
518	0	Py_XDECREF(upper);
519	0	Py_XDECREF(lower);
520	0	return -1;
521	1.76M	}
522
523		/* Implementation of slice.indices. */
524
525		static PyObject*
526		slice_indices(PyObject op, PyObject len)
527	0	{
528	0	PySliceObject *self = _PySlice_CAST(op);
529	0	PyObject start, stop, *step;
530	0	PyObject *length;
531	0	int error;
532
533		/* Convert length to an integer if necessary; raise for negative length. */
534	0	length = PyNumber_Index(len);
535	0	if (length == NULL)
536	0	return NULL;
537
538	0	if (_PyLong_IsNegative((PyLongObject *)length)) {
539	0	PyErr_SetString(PyExc_ValueError,
540	0	"length should not be negative");
541	0	Py_DECREF(length);
542	0	return NULL;
543	0	}
544
545	0	error = _PySlice_GetLongIndices(self, length, &start, &stop, &step);
546	0	Py_DECREF(length);
547	0	if (error == -1)
548	0	return NULL;
549	0	else
550	0	return Py_BuildValue("(NNN)", start, stop, step);
551	0	}
552
553		PyDoc_STRVAR(slice_indices_doc,
554		"S.indices(len) -> (start, stop, stride)\n\
555		\n\
556		Assuming a sequence of length len, calculate the start and stop\n\
557		indices, and the stride length of the extended slice described by\n\
558		S. Out of bounds indices are clipped in a manner consistent with the\n\
559		handling of normal slices.");
560
561		static PyObject *
562		slice_reduce(PyObject op, PyObject Py_UNUSED(ignored))
563	0	{
564	0	PySliceObject *self = _PySlice_CAST(op);
565	0	return Py_BuildValue("O(OOO)", Py_TYPE(self), self->start, self->stop, self->step);
566	0	}
567
568		PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
569
570		static PyMethodDef slice_methods[] = {
571		{"indices", slice_indices, METH_O, slice_indices_doc},
572		{"__reduce__", slice_reduce, METH_NOARGS, reduce_doc},
573		{"__class_getitem__", Py_GenericAlias, METH_O\|METH_CLASS, "See PEP 585"},
574		{NULL, NULL}
575		};
576
577		static PyObject *
578		slice_richcompare(PyObject v, PyObject w, int op)
579	40	{
580	40	if (!PySlice_Check(v) \|\| !PySlice_Check(w))
581	0	Py_RETURN_NOTIMPLEMENTED;
582
583	40	if (v == w) {
584	0	PyObject *res;
585		/* XXX Do we really need this shortcut?
586		There's a unit test for it, but is that fair? */
587	0	switch (op) {
588	0	case Py_EQ:
589	0	case Py_LE:
590	0	case Py_GE:
591	0	res = Py_True;
592	0	break;
593	0	default:
594	0	res = Py_False;
595	0	break;
596	0	}
597	0	return Py_NewRef(res);
598	0	}
599
600
601	40	PyObject *t1 = PyTuple_Pack(3,
602	40	((PySliceObject *)v)->start,
603	40	((PySliceObject *)v)->stop,
604	40	((PySliceObject *)v)->step);
605	40	if (t1 == NULL) {
606	0	return NULL;
607	0	}
608
609	40	PyObject *t2 = PyTuple_Pack(3,
610	40	((PySliceObject *)w)->start,
611	40	((PySliceObject *)w)->stop,
612	40	((PySliceObject *)w)->step);
613	40	if (t2 == NULL) {
614	0	Py_DECREF(t1);
615	0	return NULL;
616	0	}
617
618	40	PyObject *res = PyObject_RichCompare(t1, t2, op);
619	40	Py_DECREF(t1);
620	40	Py_DECREF(t2);
621	40	return res;
622	40	}
623
624		static int
625		slice_traverse(PyObject op, visitproc visit, void arg)
626	333k	{
627	333k	PySliceObject *v = _PySlice_CAST(op);
628	333k	Py_VISIT(v->start);
629	333k	Py_VISIT(v->stop);
630	333k	Py_VISIT(v->step);
631	333k	return 0;
632	333k	}
633
634		/* code based on tuplehash() of Objects/tupleobject.c */
635		#if SIZEOF_PY_UHASH_T > 4
636	654	#define _PyHASH_XXPRIME_1 ((Py_uhash_t)11400714785074694791ULL)
637	654	#define _PyHASH_XXPRIME_2 ((Py_uhash_t)14029467366897019727ULL)
638	218	#define _PyHASH_XXPRIME_5 ((Py_uhash_t)2870177450012600261ULL)
639	654	#define _PyHASH_XXROTATE(x) ((x << 31) \| (x >> 33)) /* Rotate left 31 bits */
640		#else
641		#define _PyHASH_XXPRIME_1 ((Py_uhash_t)2654435761UL)
642		#define _PyHASH_XXPRIME_2 ((Py_uhash_t)2246822519UL)
643		#define _PyHASH_XXPRIME_5 ((Py_uhash_t)374761393UL)
644		#define _PyHASH_XXROTATE(x) ((x << 13) \| (x >> 19)) /* Rotate left 13 bits */
645		#endif
646
647		static Py_hash_t
648		slice_hash(PyObject *op)
649	218	{
650	218	PySliceObject *v = _PySlice_CAST(op);
651	218	Py_uhash_t acc = _PyHASH_XXPRIME_5;
652	654	#define _PyHASH_SLICE_PART(com) { \
653	654	Py_uhash_t lane = PyObject_Hash(v->com); \
654	654	if(lane == (Py_uhash_t)-1) { \
655	0	return -1; \
656	0	} \
657	654	acc += lane * _PyHASH_XXPRIME_2; \
658	654	acc = _PyHASH_XXROTATE(acc); \
659	654	acc *= _PyHASH_XXPRIME_1; \
660	654	}
661	218	_PyHASH_SLICE_PART(start);
662	218	_PyHASH_SLICE_PART(stop);
663	218	_PyHASH_SLICE_PART(step);
664	218	#undef _PyHASH_SLICE_PART
665	218	if(acc == (Py_uhash_t)-1) {
666	0	return 1546275796;
667	0	}
668	218	return acc;
669	218	}
670
671		PyTypeObject PySlice_Type = {
672		PyVarObject_HEAD_INIT(&PyType_Type, 0)
673		"slice", /* Name of this type */
674		sizeof(PySliceObject), /* Basic object size */
675		0, /* Item size for varobject */
676		slice_dealloc, /* tp_dealloc */
677		0, /* tp_vectorcall_offset */
678		0, /* tp_getattr */
679		0, /* tp_setattr */
680		0, /* tp_as_async */
681		slice_repr, /* tp_repr */
682		0, /* tp_as_number */
683		0, /* tp_as_sequence */
684		0, /* tp_as_mapping */
685		slice_hash, /* tp_hash */
686		0, /* tp_call */
687		0, /* tp_str */
688		PyObject_GenericGetAttr, /* tp_getattro */
689		0, /* tp_setattro */
690		0, /* tp_as_buffer */
691		Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC, /* tp_flags */
692		slice_doc, /* tp_doc */
693		slice_traverse, /* tp_traverse */
694		0, /* tp_clear */
695		slice_richcompare, /* tp_richcompare */
696		0, /* tp_weaklistoffset */
697		0, /* tp_iter */
698		0, /* tp_iternext */
699		slice_methods, /* tp_methods */
700		slice_members, /* tp_members */
701		0, /* tp_getset */
702		0, /* tp_base */
703		0, /* tp_dict */
704		0, /* tp_descr_get */
705		0, /* tp_descr_set */
706		0, /* tp_dictoffset */
707		0, /* tp_init */
708		0, /* tp_alloc */
709		slice_new, /* tp_new */
710		};