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

PyObject *
_PyBuildSlice_ConsumeRefs(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 = step;

    _PyObject_GC_TRACK(obj);
    return (PyObject *)obj;
error:
    Py_DECREF(start);
    Py_DECREF(stop);
    Py_DECREF(step);
    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 _PyBuildSlice_ConsumeRefs(Py_NewRef(start),
                                              Py_NewRef(stop), Py_NewRef(step));
}

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 = _PyBuildSlice_ConsumeRefs(start, end, Py_None);
    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.\n\
\n\
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-05-30 06:18

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