LCOV - code coverage report
Current view: top level - Objects - rangeobject.c (source / functions) Hit Total Coverage
Test: CPython lcov report Lines: 451 548 82.3 %
Date: 2022-07-07 18:19:46 Functions: 35 36 97.2 %

          Line data    Source code
       1             : /* Range object implementation */
       2             : 
       3             : #include "Python.h"
       4             : #include "pycore_abstract.h"      // _PyIndex_Check()
       5             : #include "pycore_range.h"
       6             : #include "pycore_long.h"          // _PyLong_GetZero()
       7             : #include "pycore_tuple.h"         // _PyTuple_ITEMS()
       8             : #include "structmember.h"         // PyMemberDef
       9             : 
      10             : /* Support objects whose length is > PY_SSIZE_T_MAX.
      11             : 
      12             :    This could be sped up for small PyLongs if they fit in a Py_ssize_t.
      13             :    This only matters on Win64.  Though we could use long long which
      14             :    would presumably help perf.
      15             : */
      16             : 
      17             : typedef struct {
      18             :     PyObject_HEAD
      19             :     PyObject *start;
      20             :     PyObject *stop;
      21             :     PyObject *step;
      22             :     PyObject *length;
      23             : } rangeobject;
      24             : 
      25             : /* Helper function for validating step.  Always returns a new reference or
      26             :    NULL on error.
      27             : */
      28             : static PyObject *
      29      224463 : validate_step(PyObject *step)
      30             : {
      31             :     /* No step specified, use a step of 1. */
      32      224463 :     if (!step)
      33       93326 :         return PyLong_FromLong(1);
      34             : 
      35      131137 :     step = PyNumber_Index(step);
      36      131137 :     if (step && _PyLong_Sign(step) == 0) {
      37           3 :         PyErr_SetString(PyExc_ValueError,
      38             :                         "range() arg 3 must not be zero");
      39           3 :         Py_CLEAR(step);
      40             :     }
      41             : 
      42      131137 :     return step;
      43             : }
      44             : 
      45             : static PyObject *
      46             : compute_range_length(PyObject *start, PyObject *stop, PyObject *step);
      47             : 
      48             : static rangeobject *
      49     1286890 : make_range_object(PyTypeObject *type, PyObject *start,
      50             :                   PyObject *stop, PyObject *step)
      51             : {
      52     1286890 :     rangeobject *obj = NULL;
      53             :     PyObject *length;
      54     1286890 :     length = compute_range_length(start, stop, step);
      55     1286890 :     if (length == NULL) {
      56           0 :         return NULL;
      57             :     }
      58     1286890 :     obj = PyObject_New(rangeobject, type);
      59     1286890 :     if (obj == NULL) {
      60           0 :         Py_DECREF(length);
      61           0 :         return NULL;
      62             :     }
      63     1286890 :     obj->start = start;
      64     1286890 :     obj->stop = stop;
      65     1286890 :     obj->step = step;
      66     1286890 :     obj->length = length;
      67     1286890 :     return obj;
      68             : }
      69             : 
      70             : /* XXX(nnorwitz): should we error check if the user passes any empty ranges?
      71             :    range(-10)
      72             :    range(0, -5)
      73             :    range(0, 5, -1)
      74             : */
      75             : static PyObject *
      76     1027620 : range_from_array(PyTypeObject *type, PyObject *const *args, Py_ssize_t num_args)
      77             : {
      78             :     rangeobject *obj;
      79     1027620 :     PyObject *start = NULL, *stop = NULL, *step = NULL;
      80             : 
      81     1027620 :     switch (num_args) {
      82      131149 :         case 3:
      83      131149 :             step = args[2];
      84             :             /* fallthrough */
      85      224481 :         case 2:
      86             :             /* Convert borrowed refs to owned refs */
      87      224481 :             start = PyNumber_Index(args[0]);
      88      224481 :             if (!start) {
      89          11 :                 return NULL;
      90             :             }
      91      224470 :             stop = PyNumber_Index(args[1]);
      92      224470 :             if (!stop) {
      93           7 :                 Py_DECREF(start);
      94           7 :                 return NULL;
      95             :             }
      96      224463 :             step = validate_step(step);  /* Caution, this can clear exceptions */
      97      224463 :             if (!step) {
      98           7 :                 Py_DECREF(start);
      99           7 :                 Py_DECREF(stop);
     100           7 :                 return NULL;
     101             :             }
     102      224456 :             break;
     103      803128 :         case 1:
     104      803128 :             stop = PyNumber_Index(args[0]);
     105      803128 :             if (!stop) {
     106           5 :                 return NULL;
     107             :             }
     108      803123 :             start = _PyLong_GetZero();
     109      803123 :             Py_INCREF(start);
     110      803123 :             step = _PyLong_GetOne();
     111      803123 :             Py_INCREF(step);
     112      803123 :             break;
     113           3 :         case 0:
     114           3 :             PyErr_SetString(PyExc_TypeError,
     115             :                             "range expected at least 1 argument, got 0");
     116           3 :             return NULL;
     117           3 :         default:
     118           3 :             PyErr_Format(PyExc_TypeError,
     119             :                          "range expected at most 3 arguments, got %zd",
     120             :                          num_args);
     121           3 :             return NULL;
     122             :     }
     123     1027580 :     obj = make_range_object(type, start, stop, step);
     124     1027580 :     if (obj != NULL) {
     125     1027580 :         return (PyObject *) obj;
     126             :     }
     127             : 
     128             :     /* Failed to create object, release attributes */
     129           0 :     Py_DECREF(start);
     130           0 :     Py_DECREF(stop);
     131           0 :     Py_DECREF(step);
     132           0 :     return NULL;
     133             : }
     134             : 
     135             : static PyObject *
     136           0 : range_new(PyTypeObject *type, PyObject *args, PyObject *kw)
     137             : {
     138           0 :     if (!_PyArg_NoKeywords("range", kw))
     139           0 :         return NULL;
     140             : 
     141           0 :     return range_from_array(type, _PyTuple_ITEMS(args), PyTuple_GET_SIZE(args));
     142             : }
     143             : 
     144             : 
     145             : static PyObject *
     146     1027620 : range_vectorcall(PyTypeObject *type, PyObject *const *args,
     147             :                  size_t nargsf, PyObject *kwnames)
     148             : {
     149     1027620 :     Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);
     150     1027620 :     if (!_PyArg_NoKwnames("range", kwnames)) {
     151           0 :         return NULL;
     152             :     }
     153     1027620 :     return range_from_array(type, args, nargs);
     154             : }
     155             : 
     156             : PyDoc_STRVAR(range_doc,
     157             : "range(stop) -> range object\n\
     158             : range(start, stop[, step]) -> range object\n\
     159             : \n\
     160             : Return an object that produces a sequence of integers from start (inclusive)\n\
     161             : to stop (exclusive) by step.  range(i, j) produces i, i+1, i+2, ..., j-1.\n\
     162             : start defaults to 0, and stop is omitted!  range(4) produces 0, 1, 2, 3.\n\
     163             : These are exactly the valid indices for a list of 4 elements.\n\
     164             : When step is given, it specifies the increment (or decrement).");
     165             : 
     166             : static void
     167     1286890 : range_dealloc(rangeobject *r)
     168             : {
     169     1286890 :     Py_DECREF(r->start);
     170     1286890 :     Py_DECREF(r->stop);
     171     1286890 :     Py_DECREF(r->step);
     172     1286890 :     Py_DECREF(r->length);
     173     1286890 :     PyObject_Free(r);
     174     1286890 : }
     175             : 
     176             : /* Return number of items in range (lo, hi, step) as a PyLong object,
     177             :  * when arguments are PyLong objects.  Arguments MUST return 1 with
     178             :  * PyLong_Check().  Return NULL when there is an error.
     179             :  */
     180             : static PyObject*
     181     1286890 : compute_range_length(PyObject *start, PyObject *stop, PyObject *step)
     182             : {
     183             :     /* -------------------------------------------------------------
     184             :     Algorithm is equal to that of get_len_of_range(), but it operates
     185             :     on PyObjects (which are assumed to be PyLong objects).
     186             :     ---------------------------------------------------------------*/
     187             :     int cmp_result;
     188             :     PyObject *lo, *hi;
     189     1286890 :     PyObject *diff = NULL;
     190     1286890 :     PyObject *tmp1 = NULL, *tmp2 = NULL, *result;
     191             :                 /* holds sub-expression evaluations */
     192             : 
     193     1286890 :     PyObject *zero = _PyLong_GetZero();  // borrowed reference
     194     1286890 :     PyObject *one = _PyLong_GetOne();  // borrowed reference
     195             : 
     196     1286890 :     cmp_result = PyObject_RichCompareBool(step, zero, Py_GT);
     197     1286890 :     if (cmp_result == -1)
     198           0 :         return NULL;
     199             : 
     200     1286890 :     if (cmp_result == 1) {
     201      939286 :         lo = start;
     202      939286 :         hi = stop;
     203      939286 :         Py_INCREF(step);
     204             :     } else {
     205      347602 :         lo = stop;
     206      347602 :         hi = start;
     207      347602 :         step = PyNumber_Negative(step);
     208      347602 :         if (!step)
     209           0 :             return NULL;
     210             :     }
     211             : 
     212             :     /* if (lo >= hi), return length of 0. */
     213     1286890 :     cmp_result = PyObject_RichCompareBool(lo, hi, Py_GE);
     214     1286890 :     if (cmp_result != 0) {
     215       88874 :         Py_DECREF(step);
     216       88874 :         if (cmp_result < 0)
     217           0 :             return NULL;
     218       88874 :         result = zero;
     219       88874 :         Py_INCREF(result);
     220       88874 :         return result;
     221             :     }
     222             : 
     223     1198010 :     if ((tmp1 = PyNumber_Subtract(hi, lo)) == NULL)
     224           0 :         goto Fail;
     225             : 
     226     1198010 :     if ((diff = PyNumber_Subtract(tmp1, one)) == NULL)
     227           0 :         goto Fail;
     228             : 
     229     1198010 :     if ((tmp2 = PyNumber_FloorDivide(diff, step)) == NULL)
     230           0 :         goto Fail;
     231             : 
     232     1198010 :     if ((result = PyNumber_Add(tmp2, one)) == NULL)
     233           0 :         goto Fail;
     234             : 
     235     1198010 :     Py_DECREF(tmp2);
     236     1198010 :     Py_DECREF(diff);
     237     1198010 :     Py_DECREF(step);
     238     1198010 :     Py_DECREF(tmp1);
     239     1198010 :     return result;
     240             : 
     241           0 :   Fail:
     242           0 :     Py_DECREF(step);
     243           0 :     Py_XDECREF(tmp2);
     244           0 :     Py_XDECREF(diff);
     245           0 :     Py_XDECREF(tmp1);
     246           0 :     return NULL;
     247             : }
     248             : 
     249             : static Py_ssize_t
     250      148256 : range_length(rangeobject *r)
     251             : {
     252      148256 :     return PyLong_AsSsize_t(r->length);
     253             : }
     254             : 
     255             : static PyObject *
     256      954365 : compute_item(rangeobject *r, PyObject *i)
     257             : {
     258             :     PyObject *incr, *result;
     259             :     /* PyLong equivalent to:
     260             :      *    return r->start + (i * r->step)
     261             :      */
     262      954365 :     if (r->step == _PyLong_GetOne()) {
     263      915477 :         result = PyNumber_Add(r->start, i);
     264             :     }
     265             :     else {
     266       38888 :         incr = PyNumber_Multiply(i, r->step);
     267       38888 :         if (!incr) {
     268           0 :             return NULL;
     269             :         }
     270       38888 :         result = PyNumber_Add(r->start, incr);
     271       38888 :         Py_DECREF(incr);
     272             :     }
     273      954365 :     return result;
     274             : }
     275             : 
     276             : static PyObject *
     277      437126 : compute_range_item(rangeobject *r, PyObject *arg)
     278             : {
     279      437126 :     PyObject *zero = _PyLong_GetZero();  // borrowed reference
     280             :     int cmp_result;
     281             :     PyObject *i, *result;
     282             : 
     283             :     /* PyLong equivalent to:
     284             :      *   if (arg < 0) {
     285             :      *     i = r->length + arg
     286             :      *   } else {
     287             :      *     i = arg
     288             :      *   }
     289             :      */
     290      437126 :     cmp_result = PyObject_RichCompareBool(arg, zero, Py_LT);
     291      437126 :     if (cmp_result == -1) {
     292           0 :         return NULL;
     293             :     }
     294      437126 :     if (cmp_result == 1) {
     295          17 :         i = PyNumber_Add(r->length, arg);
     296          17 :         if (!i) {
     297           0 :           return NULL;
     298             :         }
     299             :     } else {
     300      437109 :         i = arg;
     301      437109 :         Py_INCREF(i);
     302             :     }
     303             : 
     304             :     /* PyLong equivalent to:
     305             :      *   if (i < 0 || i >= r->length) {
     306             :      *     <report index out of bounds>
     307             :      *   }
     308             :      */
     309      437126 :     cmp_result = PyObject_RichCompareBool(i, zero, Py_LT);
     310      437126 :     if (cmp_result == 0) {
     311      437122 :         cmp_result = PyObject_RichCompareBool(i, r->length, Py_GE);
     312             :     }
     313      437126 :     if (cmp_result == -1) {
     314           0 :        Py_DECREF(i);
     315           0 :        return NULL;
     316             :     }
     317      437126 :     if (cmp_result == 1) {
     318         335 :         Py_DECREF(i);
     319         335 :         PyErr_SetString(PyExc_IndexError,
     320             :                         "range object index out of range");
     321         335 :         return NULL;
     322             :     }
     323             : 
     324      436791 :     result = compute_item(r, i);
     325      436791 :     Py_DECREF(i);
     326      436791 :     return result;
     327             : }
     328             : 
     329             : static PyObject *
     330      167797 : range_item(rangeobject *r, Py_ssize_t i)
     331             : {
     332      167797 :     PyObject *res, *arg = PyLong_FromSsize_t(i);
     333      167797 :     if (!arg) {
     334           0 :         return NULL;
     335             :     }
     336      167797 :     res = compute_range_item(r, arg);
     337      167797 :     Py_DECREF(arg);
     338      167797 :     return res;
     339             : }
     340             : 
     341             : static PyObject *
     342      258789 : compute_slice(rangeobject *r, PyObject *_slice)
     343             : {
     344      258789 :     PySliceObject *slice = (PySliceObject *) _slice;
     345             :     rangeobject *result;
     346      258789 :     PyObject *start = NULL, *stop = NULL, *step = NULL;
     347      258789 :     PyObject *substart = NULL, *substop = NULL, *substep = NULL;
     348             :     int error;
     349             : 
     350      258789 :     error = _PySlice_GetLongIndices(slice, r->length, &start, &stop, &step);
     351      258789 :     if (error == -1)
     352           2 :         return NULL;
     353             : 
     354      258787 :     substep = PyNumber_Multiply(r->step, step);
     355      258787 :     if (substep == NULL) goto fail;
     356      258787 :     Py_CLEAR(step);
     357             : 
     358      258787 :     substart = compute_item(r, start);
     359      258787 :     if (substart == NULL) goto fail;
     360      258787 :     Py_CLEAR(start);
     361             : 
     362      258787 :     substop = compute_item(r, stop);
     363      258787 :     if (substop == NULL) goto fail;
     364      258787 :     Py_CLEAR(stop);
     365             : 
     366      258787 :     result = make_range_object(Py_TYPE(r), substart, substop, substep);
     367      258787 :     if (result != NULL) {
     368      258787 :         return (PyObject *) result;
     369             :     }
     370           0 : fail:
     371           0 :     Py_XDECREF(start);
     372           0 :     Py_XDECREF(stop);
     373           0 :     Py_XDECREF(step);
     374           0 :     Py_XDECREF(substart);
     375           0 :     Py_XDECREF(substop);
     376           0 :     Py_XDECREF(substep);
     377           0 :     return NULL;
     378             : }
     379             : 
     380             : /* Assumes (PyLong_CheckExact(ob) || PyBool_Check(ob)) */
     381             : static int
     382         177 : range_contains_long(rangeobject *r, PyObject *ob)
     383             : {
     384         177 :     PyObject *zero = _PyLong_GetZero();  // borrowed reference
     385             :     int cmp1, cmp2, cmp3;
     386         177 :     PyObject *tmp1 = NULL;
     387         177 :     PyObject *tmp2 = NULL;
     388         177 :     int result = -1;
     389             : 
     390             :     /* Check if the value can possibly be in the range. */
     391             : 
     392         177 :     cmp1 = PyObject_RichCompareBool(r->step, zero, Py_GT);
     393         177 :     if (cmp1 == -1)
     394           0 :         goto end;
     395         177 :     if (cmp1 == 1) { /* positive steps: start <= ob < stop */
     396         159 :         cmp2 = PyObject_RichCompareBool(r->start, ob, Py_LE);
     397         159 :         cmp3 = PyObject_RichCompareBool(ob, r->stop, Py_LT);
     398             :     }
     399             :     else { /* negative steps: stop < ob <= start */
     400          18 :         cmp2 = PyObject_RichCompareBool(ob, r->start, Py_LE);
     401          18 :         cmp3 = PyObject_RichCompareBool(r->stop, ob, Py_LT);
     402             :     }
     403             : 
     404         177 :     if (cmp2 == -1 || cmp3 == -1) /* TypeError */
     405           0 :         goto end;
     406         177 :     if (cmp2 == 0 || cmp3 == 0) { /* ob outside of range */
     407          48 :         result = 0;
     408          48 :         goto end;
     409             :     }
     410             : 
     411             :     /* Check that the stride does not invalidate ob's membership. */
     412         129 :     tmp1 = PyNumber_Subtract(ob, r->start);
     413         129 :     if (tmp1 == NULL)
     414           0 :         goto end;
     415         129 :     tmp2 = PyNumber_Remainder(tmp1, r->step);
     416         129 :     if (tmp2 == NULL)
     417           0 :         goto end;
     418             :     /* result = ((int(ob) - start) % step) == 0 */
     419         129 :     result = PyObject_RichCompareBool(tmp2, zero, Py_EQ);
     420         177 :   end:
     421         177 :     Py_XDECREF(tmp1);
     422         177 :     Py_XDECREF(tmp2);
     423         177 :     return result;
     424             : }
     425             : 
     426             : static int
     427         171 : range_contains(rangeobject *r, PyObject *ob)
     428             : {
     429         171 :     if (PyLong_CheckExact(ob) || PyBool_Check(ob))
     430         153 :         return range_contains_long(r, ob);
     431             : 
     432          18 :     return (int)_PySequence_IterSearch((PyObject*)r, ob,
     433             :                                        PY_ITERSEARCH_CONTAINS);
     434             : }
     435             : 
     436             : /* Compare two range objects.  Return 1 for equal, 0 for not equal
     437             :    and -1 on error.  The algorithm is roughly the C equivalent of
     438             : 
     439             :    if r0 is r1:
     440             :        return True
     441             :    if len(r0) != len(r1):
     442             :        return False
     443             :    if not len(r0):
     444             :        return True
     445             :    if r0.start != r1.start:
     446             :        return False
     447             :    if len(r0) == 1:
     448             :        return True
     449             :    return r0.step == r1.step
     450             : */
     451             : static int
     452        9885 : range_equals(rangeobject *r0, rangeobject *r1)
     453             : {
     454             :     int cmp_result;
     455             : 
     456        9885 :     if (r0 == r1)
     457          33 :         return 1;
     458        9852 :     cmp_result = PyObject_RichCompareBool(r0->length, r1->length, Py_EQ);
     459             :     /* Return False or error to the caller. */
     460        9852 :     if (cmp_result != 1)
     461         266 :         return cmp_result;
     462        9586 :     cmp_result = PyObject_Not(r0->length);
     463             :     /* Return True or error to the caller. */
     464        9586 :     if (cmp_result != 0)
     465        6202 :         return cmp_result;
     466        3384 :     cmp_result = PyObject_RichCompareBool(r0->start, r1->start, Py_EQ);
     467             :     /* Return False or error to the caller. */
     468        3384 :     if (cmp_result != 1)
     469          18 :         return cmp_result;
     470        3366 :     cmp_result = PyObject_RichCompareBool(r0->length, _PyLong_GetOne(), Py_EQ);
     471             :     /* Return True or error to the caller. */
     472        3366 :     if (cmp_result != 0)
     473        2052 :         return cmp_result;
     474        1314 :     return PyObject_RichCompareBool(r0->step, r1->step, Py_EQ);
     475             : }
     476             : 
     477             : static PyObject *
     478        9926 : range_richcompare(PyObject *self, PyObject *other, int op)
     479             : {
     480             :     int result;
     481             : 
     482        9926 :     if (!PyRange_Check(other))
     483          33 :         Py_RETURN_NOTIMPLEMENTED;
     484        9893 :     switch (op) {
     485        9885 :     case Py_NE:
     486             :     case Py_EQ:
     487        9885 :         result = range_equals((rangeobject*)self, (rangeobject*)other);
     488        9885 :         if (result == -1)
     489           0 :             return NULL;
     490        9885 :         if (op == Py_NE)
     491         123 :             result = !result;
     492        9885 :         if (result)
     493        9668 :             Py_RETURN_TRUE;
     494             :         else
     495         217 :             Py_RETURN_FALSE;
     496           8 :     case Py_LE:
     497             :     case Py_GE:
     498             :     case Py_LT:
     499             :     case Py_GT:
     500           8 :         Py_RETURN_NOTIMPLEMENTED;
     501           0 :     default:
     502           0 :         PyErr_BadArgument();
     503           0 :         return NULL;
     504             :     }
     505             : }
     506             : 
     507             : /* Hash function for range objects.  Rough C equivalent of
     508             : 
     509             :    if not len(r):
     510             :        return hash((len(r), None, None))
     511             :    if len(r) == 1:
     512             :        return hash((len(r), r.start, None))
     513             :    return hash((len(r), r.start, r.step))
     514             : */
     515             : static Py_hash_t
     516          56 : range_hash(rangeobject *r)
     517             : {
     518             :     PyObject *t;
     519          56 :     Py_hash_t result = -1;
     520             :     int cmp_result;
     521             : 
     522          56 :     t = PyTuple_New(3);
     523          56 :     if (!t)
     524           0 :         return -1;
     525          56 :     Py_INCREF(r->length);
     526          56 :     PyTuple_SET_ITEM(t, 0, r->length);
     527          56 :     cmp_result = PyObject_Not(r->length);
     528          56 :     if (cmp_result == -1)
     529           0 :         goto end;
     530          56 :     if (cmp_result == 1) {
     531          20 :         Py_INCREF(Py_None);
     532          20 :         Py_INCREF(Py_None);
     533          20 :         PyTuple_SET_ITEM(t, 1, Py_None);
     534          20 :         PyTuple_SET_ITEM(t, 2, Py_None);
     535             :     }
     536             :     else {
     537          36 :         Py_INCREF(r->start);
     538          36 :         PyTuple_SET_ITEM(t, 1, r->start);
     539          36 :         cmp_result = PyObject_RichCompareBool(r->length, _PyLong_GetOne(), Py_EQ);
     540          36 :         if (cmp_result == -1)
     541           0 :             goto end;
     542          36 :         if (cmp_result == 1) {
     543          20 :             Py_INCREF(Py_None);
     544          20 :             PyTuple_SET_ITEM(t, 2, Py_None);
     545             :         }
     546             :         else {
     547          16 :             Py_INCREF(r->step);
     548          16 :             PyTuple_SET_ITEM(t, 2, r->step);
     549             :         }
     550             :     }
     551          56 :     result = PyObject_Hash(t);
     552          56 :   end:
     553          56 :     Py_DECREF(t);
     554          56 :     return result;
     555             : }
     556             : 
     557             : static PyObject *
     558          13 : range_count(rangeobject *r, PyObject *ob)
     559             : {
     560          13 :     if (PyLong_CheckExact(ob) || PyBool_Check(ob)) {
     561          12 :         int result = range_contains_long(r, ob);
     562          12 :         if (result == -1)
     563           0 :             return NULL;
     564          12 :         return PyLong_FromLong(result);
     565             :     } else {
     566             :         Py_ssize_t count;
     567           1 :         count = _PySequence_IterSearch((PyObject*)r, ob, PY_ITERSEARCH_COUNT);
     568           1 :         if (count == -1)
     569           0 :             return NULL;
     570           1 :         return PyLong_FromSsize_t(count);
     571             :     }
     572             : }
     573             : 
     574             : static PyObject *
     575          14 : range_index(rangeobject *r, PyObject *ob)
     576             : {
     577             :     int contains;
     578             : 
     579          14 :     if (!PyLong_CheckExact(ob) && !PyBool_Check(ob)) {
     580             :         Py_ssize_t index;
     581           2 :         index = _PySequence_IterSearch((PyObject*)r, ob, PY_ITERSEARCH_INDEX);
     582           2 :         if (index == -1)
     583           1 :             return NULL;
     584           1 :         return PyLong_FromSsize_t(index);
     585             :     }
     586             : 
     587          12 :     contains = range_contains_long(r, ob);
     588          12 :     if (contains == -1)
     589           0 :         return NULL;
     590             : 
     591          12 :     if (contains) {
     592          10 :         PyObject *idx = PyNumber_Subtract(ob, r->start);
     593          10 :         if (idx == NULL) {
     594           0 :             return NULL;
     595             :         }
     596             : 
     597          10 :         if (r->step == _PyLong_GetOne()) {
     598           7 :             return idx;
     599             :         }
     600             : 
     601             :         /* idx = (ob - r.start) // r.step */
     602           3 :         PyObject *sidx = PyNumber_FloorDivide(idx, r->step);
     603           3 :         Py_DECREF(idx);
     604           3 :         return sidx;
     605             :     }
     606             : 
     607             :     /* object is not in the range */
     608           2 :     PyErr_Format(PyExc_ValueError, "%R is not in range", ob);
     609           2 :     return NULL;
     610             : }
     611             : 
     612             : static PySequenceMethods range_as_sequence = {
     613             :     (lenfunc)range_length,      /* sq_length */
     614             :     0,                          /* sq_concat */
     615             :     0,                          /* sq_repeat */
     616             :     (ssizeargfunc)range_item,   /* sq_item */
     617             :     0,                          /* sq_slice */
     618             :     0,                          /* sq_ass_item */
     619             :     0,                          /* sq_ass_slice */
     620             :     (objobjproc)range_contains, /* sq_contains */
     621             : };
     622             : 
     623             : static PyObject *
     624          43 : range_repr(rangeobject *r)
     625             : {
     626             :     Py_ssize_t istep;
     627             : 
     628             :     /* Check for special case values for printing.  We don't always
     629             :        need the step value.  We don't care about overflow. */
     630          43 :     istep = PyNumber_AsSsize_t(r->step, NULL);
     631          43 :     if (istep == -1 && PyErr_Occurred()) {
     632           0 :         assert(!PyErr_ExceptionMatches(PyExc_OverflowError));
     633           0 :         return NULL;
     634             :     }
     635             : 
     636          43 :     if (istep == 1)
     637          26 :         return PyUnicode_FromFormat("range(%R, %R)", r->start, r->stop);
     638             :     else
     639          17 :         return PyUnicode_FromFormat("range(%R, %R, %R)",
     640             :                                     r->start, r->stop, r->step);
     641             : }
     642             : 
     643             : /* Pickling support */
     644             : static PyObject *
     645         572 : range_reduce(rangeobject *r, PyObject *args)
     646             : {
     647         572 :     return Py_BuildValue("(O(OOO))", Py_TYPE(r),
     648             :                          r->start, r->stop, r->step);
     649             : }
     650             : 
     651             : static PyObject *
     652      528120 : range_subscript(rangeobject* self, PyObject* item)
     653             : {
     654      528120 :     if (_PyIndex_Check(item)) {
     655             :         PyObject *i, *result;
     656      269329 :         i = PyNumber_Index(item);
     657      269329 :         if (!i)
     658           0 :             return NULL;
     659      269329 :         result = compute_range_item(self, i);
     660      269329 :         Py_DECREF(i);
     661      269329 :         return result;
     662             :     }
     663      258791 :     if (PySlice_Check(item)) {
     664      258789 :         return compute_slice(self, item);
     665             :     }
     666           2 :     PyErr_Format(PyExc_TypeError,
     667             :                  "range indices must be integers or slices, not %.200s",
     668           2 :                  Py_TYPE(item)->tp_name);
     669           2 :     return NULL;
     670             : }
     671             : 
     672             : 
     673             : static PyMappingMethods range_as_mapping = {
     674             :         (lenfunc)range_length,       /* mp_length */
     675             :         (binaryfunc)range_subscript, /* mp_subscript */
     676             :         (objobjargproc)0,            /* mp_ass_subscript */
     677             : };
     678             : 
     679             : static int
     680        4088 : range_bool(rangeobject* self)
     681             : {
     682        4088 :     return PyObject_IsTrue(self->length);
     683             : }
     684             : 
     685             : static PyNumberMethods range_as_number = {
     686             :     .nb_bool = (inquiry)range_bool,
     687             : };
     688             : 
     689             : static PyObject * range_iter(PyObject *seq);
     690             : static PyObject * range_reverse(PyObject *seq, PyObject *Py_UNUSED(ignored));
     691             : 
     692             : PyDoc_STRVAR(reverse_doc,
     693             : "Return a reverse iterator.");
     694             : 
     695             : PyDoc_STRVAR(count_doc,
     696             : "rangeobject.count(value) -> integer -- return number of occurrences of value");
     697             : 
     698             : PyDoc_STRVAR(index_doc,
     699             : "rangeobject.index(value) -> integer -- return index of value.\n"
     700             : "Raise ValueError if the value is not present.");
     701             : 
     702             : static PyMethodDef range_methods[] = {
     703             :     {"__reversed__",    range_reverse,              METH_NOARGS, reverse_doc},
     704             :     {"__reduce__",      (PyCFunction)range_reduce,  METH_VARARGS},
     705             :     {"count",           (PyCFunction)range_count,   METH_O,      count_doc},
     706             :     {"index",           (PyCFunction)range_index,   METH_O,      index_doc},
     707             :     {NULL,              NULL}           /* sentinel */
     708             : };
     709             : 
     710             : static PyMemberDef range_members[] = {
     711             :     {"start",   T_OBJECT_EX,    offsetof(rangeobject, start),   READONLY},
     712             :     {"stop",    T_OBJECT_EX,    offsetof(rangeobject, stop),    READONLY},
     713             :     {"step",    T_OBJECT_EX,    offsetof(rangeobject, step),    READONLY},
     714             :     {0}
     715             : };
     716             : 
     717             : PyTypeObject PyRange_Type = {
     718             :         PyVarObject_HEAD_INIT(&PyType_Type, 0)
     719             :         "range",                /* Name of this type */
     720             :         sizeof(rangeobject),    /* Basic object size */
     721             :         0,                      /* Item size for varobject */
     722             :         (destructor)range_dealloc, /* tp_dealloc */
     723             :         0,                      /* tp_vectorcall_offset */
     724             :         0,                      /* tp_getattr */
     725             :         0,                      /* tp_setattr */
     726             :         0,                      /* tp_as_async */
     727             :         (reprfunc)range_repr,   /* tp_repr */
     728             :         &range_as_number,       /* tp_as_number */
     729             :         &range_as_sequence,     /* tp_as_sequence */
     730             :         &range_as_mapping,      /* tp_as_mapping */
     731             :         (hashfunc)range_hash,   /* tp_hash */
     732             :         0,                      /* tp_call */
     733             :         0,                      /* tp_str */
     734             :         PyObject_GenericGetAttr,  /* tp_getattro */
     735             :         0,                      /* tp_setattro */
     736             :         0,                      /* tp_as_buffer */
     737             :         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_SEQUENCE,  /* tp_flags */
     738             :         range_doc,              /* tp_doc */
     739             :         0,                      /* tp_traverse */
     740             :         0,                      /* tp_clear */
     741             :         range_richcompare,      /* tp_richcompare */
     742             :         0,                      /* tp_weaklistoffset */
     743             :         range_iter,             /* tp_iter */
     744             :         0,                      /* tp_iternext */
     745             :         range_methods,          /* tp_methods */
     746             :         range_members,          /* tp_members */
     747             :         0,                      /* tp_getset */
     748             :         0,                      /* tp_base */
     749             :         0,                      /* tp_dict */
     750             :         0,                      /* tp_descr_get */
     751             :         0,                      /* tp_descr_set */
     752             :         0,                      /* tp_dictoffset */
     753             :         0,                      /* tp_init */
     754             :         0,                      /* tp_alloc */
     755             :         range_new,              /* tp_new */
     756             :         .tp_vectorcall = (vectorcallfunc)range_vectorcall
     757             : };
     758             : 
     759             : /*********************** range Iterator **************************/
     760             : 
     761             : /* There are 2 types of iterators, one for C longs, the other for
     762             :    Python ints (ie, PyObjects).  This should make iteration fast
     763             :    in the normal case, but possible for any numeric value.
     764             : */
     765             : 
     766             : static PyObject *
     767    10925800 : rangeiter_next(_PyRangeIterObject *r)
     768             : {
     769    10925800 :     if (r->index < r->len)
     770             :         /* cast to unsigned to avoid possible signed overflow
     771             :            in intermediate calculations. */
     772    10834800 :         return PyLong_FromLong((long)(r->start +
     773    10834800 :                                       (unsigned long)(r->index++) * r->step));
     774       91053 :     return NULL;
     775             : }
     776             : 
     777             : static PyObject *
     778         434 : rangeiter_len(_PyRangeIterObject *r, PyObject *Py_UNUSED(ignored))
     779             : {
     780         434 :     return PyLong_FromLong(r->len - r->index);
     781             : }
     782             : 
     783             : PyDoc_STRVAR(length_hint_doc,
     784             :              "Private method returning an estimate of len(list(it)).");
     785             : 
     786             : static PyObject *
     787         432 : rangeiter_reduce(_PyRangeIterObject *r, PyObject *Py_UNUSED(ignored))
     788             : {
     789         432 :     PyObject *start=NULL, *stop=NULL, *step=NULL;
     790             :     PyObject *range;
     791             : 
     792             :     /* create a range object for pickling */
     793         432 :     start = PyLong_FromLong(r->start);
     794         432 :     if (start == NULL)
     795           0 :         goto err;
     796         432 :     stop = PyLong_FromLong(r->start + r->len * r->step);
     797         432 :     if (stop == NULL)
     798           0 :         goto err;
     799         432 :     step = PyLong_FromLong(r->step);
     800         432 :     if (step == NULL)
     801           0 :         goto err;
     802         432 :     range = (PyObject*)make_range_object(&PyRange_Type,
     803             :                                start, stop, step);
     804         432 :     if (range == NULL)
     805           0 :         goto err;
     806             :     /* return the result */
     807         432 :     return Py_BuildValue(
     808             :             "N(N)l", _PyEval_GetBuiltin(&_Py_ID(iter)), range, r->index);
     809           0 : err:
     810           0 :     Py_XDECREF(start);
     811           0 :     Py_XDECREF(stop);
     812           0 :     Py_XDECREF(step);
     813           0 :     return NULL;
     814             : }
     815             : 
     816             : static PyObject *
     817         624 : rangeiter_setstate(_PyRangeIterObject *r, PyObject *state)
     818             : {
     819         624 :     long index = PyLong_AsLong(state);
     820         624 :     if (index == -1 && PyErr_Occurred())
     821           0 :         return NULL;
     822             :     /* silently clip the index value */
     823         624 :     if (index < 0)
     824           0 :         index = 0;
     825         624 :     else if (index > r->len)
     826           0 :         index = r->len; /* exhausted iterator */
     827         624 :     r->index = index;
     828         624 :     Py_RETURN_NONE;
     829             : }
     830             : 
     831             : PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
     832             : PyDoc_STRVAR(setstate_doc, "Set state information for unpickling.");
     833             : 
     834             : static PyMethodDef rangeiter_methods[] = {
     835             :     {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS,
     836             :         length_hint_doc},
     837             :     {"__reduce__", (PyCFunction)rangeiter_reduce, METH_NOARGS,
     838             :         reduce_doc},
     839             :     {"__setstate__", (PyCFunction)rangeiter_setstate, METH_O,
     840             :         setstate_doc},
     841             :     {NULL,              NULL}           /* sentinel */
     842             : };
     843             : 
     844             : PyTypeObject PyRangeIter_Type = {
     845             :         PyVarObject_HEAD_INIT(&PyType_Type, 0)
     846             :         "range_iterator",                       /* tp_name */
     847             :         sizeof(_PyRangeIterObject),             /* tp_basicsize */
     848             :         0,                                      /* tp_itemsize */
     849             :         /* methods */
     850             :         (destructor)PyObject_Del,               /* tp_dealloc */
     851             :         0,                                      /* tp_vectorcall_offset */
     852             :         0,                                      /* tp_getattr */
     853             :         0,                                      /* tp_setattr */
     854             :         0,                                      /* tp_as_async */
     855             :         0,                                      /* tp_repr */
     856             :         0,                                      /* tp_as_number */
     857             :         0,                                      /* tp_as_sequence */
     858             :         0,                                      /* tp_as_mapping */
     859             :         0,                                      /* tp_hash */
     860             :         0,                                      /* tp_call */
     861             :         0,                                      /* tp_str */
     862             :         PyObject_GenericGetAttr,                /* tp_getattro */
     863             :         0,                                      /* tp_setattro */
     864             :         0,                                      /* tp_as_buffer */
     865             :         Py_TPFLAGS_DEFAULT,                     /* tp_flags */
     866             :         0,                                      /* tp_doc */
     867             :         0,                                      /* tp_traverse */
     868             :         0,                                      /* tp_clear */
     869             :         0,                                      /* tp_richcompare */
     870             :         0,                                      /* tp_weaklistoffset */
     871             :         PyObject_SelfIter,                      /* tp_iter */
     872             :         (iternextfunc)rangeiter_next,           /* tp_iternext */
     873             :         rangeiter_methods,                      /* tp_methods */
     874             :         0,                                      /* tp_members */
     875             : };
     876             : 
     877             : /* Return number of items in range (lo, hi, step).  step != 0
     878             :  * required.  The result always fits in an unsigned long.
     879             :  */
     880             : static unsigned long
     881     1010380 : get_len_of_range(long lo, long hi, long step)
     882             : {
     883             :     /* -------------------------------------------------------------
     884             :     If step > 0 and lo >= hi, or step < 0 and lo <= hi, the range is empty.
     885             :     Else for step > 0, if n values are in the range, the last one is
     886             :     lo + (n-1)*step, which must be <= hi-1.  Rearranging,
     887             :     n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives
     888             :     the proper value.  Since lo < hi in this case, hi-lo-1 >= 0, so
     889             :     the RHS is non-negative and so truncation is the same as the
     890             :     floor.  Letting M be the largest positive long, the worst case
     891             :     for the RHS numerator is hi=M, lo=-M-1, and then
     892             :     hi-lo-1 = M-(-M-1)-1 = 2*M.  Therefore unsigned long has enough
     893             :     precision to compute the RHS exactly.  The analysis for step < 0
     894             :     is similar.
     895             :     ---------------------------------------------------------------*/
     896     1010380 :     assert(step != 0);
     897     1010380 :     if (step > 0 && lo < hi)
     898      650730 :         return 1UL + (hi - 1UL - lo) / step;
     899      359652 :     else if (step < 0 && lo > hi)
     900      301108 :         return 1UL + (lo - 1UL - hi) / (0UL - step);
     901             :     else
     902       58544 :         return 0UL;
     903             : }
     904             : 
     905             : /* Initialize a rangeiter object.  If the length of the rangeiter object
     906             :    is not representable as a C long, OverflowError is raised. */
     907             : 
     908             : static PyObject *
     909     1009480 : fast_range_iter(long start, long stop, long step, long len)
     910             : {
     911     1009480 :     _PyRangeIterObject *it = PyObject_New(_PyRangeIterObject, &PyRangeIter_Type);
     912     1009480 :     if (it == NULL)
     913           0 :         return NULL;
     914     1009480 :     it->start = start;
     915     1009480 :     it->step = step;
     916     1009480 :     it->len = len;
     917     1009480 :     it->index = 0;
     918     1009480 :     return (PyObject *)it;
     919             : }
     920             : 
     921             : typedef struct {
     922             :     PyObject_HEAD
     923             :     PyObject *index;
     924             :     PyObject *start;
     925             :     PyObject *step;
     926             :     PyObject *len;
     927             : } longrangeiterobject;
     928             : 
     929             : static PyObject *
     930          97 : longrangeiter_len(longrangeiterobject *r, PyObject *no_args)
     931             : {
     932          97 :     return PyNumber_Subtract(r->len, r->index);
     933             : }
     934             : 
     935             : static PyObject *
     936          90 : longrangeiter_reduce(longrangeiterobject *r, PyObject *Py_UNUSED(ignored))
     937             : {
     938          90 :     PyObject *product, *stop=NULL;
     939             :     PyObject *range;
     940             : 
     941             :     /* create a range object for pickling.  Must calculate the "stop" value */
     942          90 :     product = PyNumber_Multiply(r->len, r->step);
     943          90 :     if (product == NULL)
     944           0 :         return NULL;
     945          90 :     stop = PyNumber_Add(r->start, product);
     946          90 :     Py_DECREF(product);
     947          90 :     if (stop ==  NULL)
     948           0 :         return NULL;
     949          90 :     Py_INCREF(r->start);
     950          90 :     Py_INCREF(r->step);
     951          90 :     range =  (PyObject*)make_range_object(&PyRange_Type,
     952             :                                r->start, stop, r->step);
     953          90 :     if (range == NULL) {
     954           0 :         Py_DECREF(r->start);
     955           0 :         Py_DECREF(stop);
     956           0 :         Py_DECREF(r->step);
     957           0 :         return NULL;
     958             :     }
     959             : 
     960             :     /* return the result */
     961          90 :     return Py_BuildValue(
     962             :             "N(N)O", _PyEval_GetBuiltin(&_Py_ID(iter)), range, r->index);
     963             : }
     964             : 
     965             : static PyObject *
     966         132 : longrangeiter_setstate(longrangeiterobject *r, PyObject *state)
     967             : {
     968         132 :     PyObject *zero = _PyLong_GetZero();  // borrowed reference
     969             :     int cmp;
     970             : 
     971             :     /* clip the value */
     972         132 :     cmp = PyObject_RichCompareBool(state, zero, Py_LT);
     973         132 :     if (cmp < 0)
     974           0 :         return NULL;
     975         132 :     if (cmp > 0) {
     976           0 :         state = zero;
     977             :     }
     978             :     else {
     979         132 :         cmp = PyObject_RichCompareBool(r->len, state, Py_LT);
     980         132 :         if (cmp < 0)
     981           0 :             return NULL;
     982         132 :         if (cmp > 0)
     983           0 :             state = r->len;
     984             :     }
     985         132 :     Py_INCREF(state);
     986         132 :     Py_XSETREF(r->index, state);
     987         132 :     Py_RETURN_NONE;
     988             : }
     989             : 
     990             : static PyMethodDef longrangeiter_methods[] = {
     991             :     {"__length_hint__", (PyCFunction)longrangeiter_len, METH_NOARGS,
     992             :         length_hint_doc},
     993             :     {"__reduce__", (PyCFunction)longrangeiter_reduce, METH_NOARGS,
     994             :         reduce_doc},
     995             :     {"__setstate__", (PyCFunction)longrangeiter_setstate, METH_O,
     996             :         setstate_doc},
     997             :     {NULL,              NULL}           /* sentinel */
     998             : };
     999             : 
    1000             : static void
    1001       21048 : longrangeiter_dealloc(longrangeiterobject *r)
    1002             : {
    1003       21048 :     Py_XDECREF(r->index);
    1004       21048 :     Py_XDECREF(r->start);
    1005       21048 :     Py_XDECREF(r->step);
    1006       21048 :     Py_XDECREF(r->len);
    1007       21048 :     PyObject_Free(r);
    1008       21048 : }
    1009             : 
    1010             : static PyObject *
    1011      679361 : longrangeiter_next(longrangeiterobject *r)
    1012             : {
    1013             :     PyObject *product, *new_index, *result;
    1014      679361 :     if (PyObject_RichCompareBool(r->index, r->len, Py_LT) != 1)
    1015       11224 :         return NULL;
    1016             : 
    1017      668137 :     new_index = PyNumber_Add(r->index, _PyLong_GetOne());
    1018      668137 :     if (!new_index)
    1019           0 :         return NULL;
    1020             : 
    1021      668137 :     product = PyNumber_Multiply(r->index, r->step);
    1022      668137 :     if (!product) {
    1023           0 :         Py_DECREF(new_index);
    1024           0 :         return NULL;
    1025             :     }
    1026             : 
    1027      668137 :     result = PyNumber_Add(r->start, product);
    1028      668137 :     Py_DECREF(product);
    1029      668137 :     if (result) {
    1030      668137 :         Py_SETREF(r->index, new_index);
    1031             :     }
    1032             :     else {
    1033           0 :         Py_DECREF(new_index);
    1034             :     }
    1035             : 
    1036      668137 :     return result;
    1037             : }
    1038             : 
    1039             : PyTypeObject PyLongRangeIter_Type = {
    1040             :         PyVarObject_HEAD_INIT(&PyType_Type, 0)
    1041             :         "longrange_iterator",                   /* tp_name */
    1042             :         sizeof(longrangeiterobject),            /* tp_basicsize */
    1043             :         0,                                      /* tp_itemsize */
    1044             :         /* methods */
    1045             :         (destructor)longrangeiter_dealloc,      /* tp_dealloc */
    1046             :         0,                                      /* tp_vectorcall_offset */
    1047             :         0,                                      /* tp_getattr */
    1048             :         0,                                      /* tp_setattr */
    1049             :         0,                                      /* tp_as_async */
    1050             :         0,                                      /* tp_repr */
    1051             :         0,                                      /* tp_as_number */
    1052             :         0,                                      /* tp_as_sequence */
    1053             :         0,                                      /* tp_as_mapping */
    1054             :         0,                                      /* tp_hash */
    1055             :         0,                                      /* tp_call */
    1056             :         0,                                      /* tp_str */
    1057             :         PyObject_GenericGetAttr,                /* tp_getattro */
    1058             :         0,                                      /* tp_setattro */
    1059             :         0,                                      /* tp_as_buffer */
    1060             :         Py_TPFLAGS_DEFAULT,                     /* tp_flags */
    1061             :         0,                                      /* tp_doc */
    1062             :         0,                                      /* tp_traverse */
    1063             :         0,                                      /* tp_clear */
    1064             :         0,                                      /* tp_richcompare */
    1065             :         0,                                      /* tp_weaklistoffset */
    1066             :         PyObject_SelfIter,                      /* tp_iter */
    1067             :         (iternextfunc)longrangeiter_next,       /* tp_iternext */
    1068             :         longrangeiter_methods,                  /* tp_methods */
    1069             :         0,
    1070             : };
    1071             : 
    1072             : static PyObject *
    1073      990266 : range_iter(PyObject *seq)
    1074             : {
    1075      990266 :     rangeobject *r = (rangeobject *)seq;
    1076             :     longrangeiterobject *it;
    1077             :     long lstart, lstop, lstep;
    1078             :     unsigned long ulen;
    1079             : 
    1080      990266 :     assert(PyRange_Check(seq));
    1081             : 
    1082             :     /* If all three fields and the length convert to long, use the int
    1083             :      * version */
    1084      990266 :     lstart = PyLong_AsLong(r->start);
    1085      990266 :     if (lstart == -1 && PyErr_Occurred()) {
    1086        4608 :         PyErr_Clear();
    1087        4608 :         goto long_range;
    1088             :     }
    1089      985658 :     lstop = PyLong_AsLong(r->stop);
    1090      985658 :     if (lstop == -1 && PyErr_Occurred()) {
    1091        6379 :         PyErr_Clear();
    1092        6379 :         goto long_range;
    1093             :     }
    1094      979279 :     lstep = PyLong_AsLong(r->step);
    1095      979279 :     if (lstep == -1 && PyErr_Occurred()) {
    1096           0 :         PyErr_Clear();
    1097           0 :         goto long_range;
    1098             :     }
    1099      979279 :     ulen = get_len_of_range(lstart, lstop, lstep);
    1100      979279 :     if (ulen > (unsigned long)LONG_MAX) {
    1101         150 :         goto long_range;
    1102             :     }
    1103             :     /* check for potential overflow of lstart + ulen * lstep */
    1104      979129 :     if (ulen) {
    1105      923801 :         if (lstep > 0) {
    1106      624371 :             if (lstop > LONG_MAX - (lstep - 1))
    1107          70 :                 goto long_range;
    1108             :         }
    1109             :         else {
    1110      299430 :             if (lstop < LONG_MIN + (-1 - lstep))
    1111         572 :                 goto long_range;
    1112             :         }
    1113             :     }
    1114      978487 :     return fast_range_iter(lstart, lstop, lstep, (long)ulen);
    1115             : 
    1116       11779 :   long_range:
    1117       11779 :     it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
    1118       11779 :     if (it == NULL)
    1119           0 :         return NULL;
    1120             : 
    1121       11779 :     it->start = r->start;
    1122       11779 :     it->step = r->step;
    1123       11779 :     it->len = r->length;
    1124       11779 :     it->index = _PyLong_GetZero();
    1125       11779 :     Py_INCREF(it->start);
    1126       11779 :     Py_INCREF(it->step);
    1127       11779 :     Py_INCREF(it->len);
    1128       11779 :     Py_INCREF(it->index);
    1129       11779 :     return (PyObject *)it;
    1130             : }
    1131             : 
    1132             : static PyObject *
    1133       40259 : range_reverse(PyObject *seq, PyObject *Py_UNUSED(ignored))
    1134             : {
    1135       40259 :     rangeobject *range = (rangeobject*) seq;
    1136             :     longrangeiterobject *it;
    1137             :     PyObject *sum, *diff, *product;
    1138             :     long lstart, lstop, lstep, new_start, new_stop;
    1139             :     unsigned long ulen;
    1140             : 
    1141       40259 :     assert(PyRange_Check(seq));
    1142             : 
    1143             :     /* reversed(range(start, stop, step)) can be expressed as
    1144             :        range(start+(n-1)*step, start-step, -step), where n is the number of
    1145             :        integers in the range.
    1146             : 
    1147             :        If each of start, stop, step, -step, start-step, and the length
    1148             :        of the iterator is representable as a C long, use the int
    1149             :        version.  This excludes some cases where the reversed range is
    1150             :        representable as a range_iterator, but it's good enough for
    1151             :        common cases and it makes the checks simple. */
    1152             : 
    1153       40259 :     lstart = PyLong_AsLong(range->start);
    1154       40259 :     if (lstart == -1 && PyErr_Occurred()) {
    1155        4501 :         PyErr_Clear();
    1156        4501 :         goto long_range;
    1157             :     }
    1158       35758 :     lstop = PyLong_AsLong(range->stop);
    1159       35758 :     if (lstop == -1 && PyErr_Occurred()) {
    1160        3150 :         PyErr_Clear();
    1161        3150 :         goto long_range;
    1162             :     }
    1163       32608 :     lstep = PyLong_AsLong(range->step);
    1164       32608 :     if (lstep == -1 && PyErr_Occurred()) {
    1165           0 :         PyErr_Clear();
    1166           0 :         goto long_range;
    1167             :     }
    1168             :     /* check for possible overflow of -lstep */
    1169       32608 :     if (lstep == LONG_MIN)
    1170        1225 :         goto long_range;
    1171             : 
    1172             :     /* check for overflow of lstart - lstep:
    1173             : 
    1174             :        for lstep > 0, need only check whether lstart - lstep < LONG_MIN.
    1175             :        for lstep < 0, need only check whether lstart - lstep > LONG_MAX
    1176             : 
    1177             :        Rearrange these inequalities as:
    1178             : 
    1179             :            lstart - LONG_MIN < lstep  (lstep > 0)
    1180             :            LONG_MAX - lstart < -lstep  (lstep < 0)
    1181             : 
    1182             :        and compute both sides as unsigned longs, to avoid the
    1183             :        possibility of undefined behaviour due to signed overflow. */
    1184             : 
    1185       31383 :     if (lstep > 0) {
    1186       27707 :          if ((unsigned long)lstart - LONG_MIN < (unsigned long)lstep)
    1187         105 :             goto long_range;
    1188             :     }
    1189             :     else {
    1190        3676 :         if (LONG_MAX - (unsigned long)lstart < 0UL - lstep)
    1191         175 :             goto long_range;
    1192             :     }
    1193             : 
    1194       31103 :     ulen = get_len_of_range(lstart, lstop, lstep);
    1195       31103 :     if (ulen > (unsigned long)LONG_MAX)
    1196         113 :         goto long_range;
    1197             : 
    1198       30990 :     new_stop = lstart - lstep;
    1199       30990 :     new_start = (long)(new_stop + ulen * lstep);
    1200       30990 :     return fast_range_iter(new_start, new_stop, -lstep, (long)ulen);
    1201             : 
    1202        9269 : long_range:
    1203        9269 :     it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
    1204        9269 :     if (it == NULL)
    1205           0 :         return NULL;
    1206        9269 :     it->index = it->start = it->step = NULL;
    1207             : 
    1208             :     /* start + (len - 1) * step */
    1209        9269 :     it->len = range->length;
    1210        9269 :     Py_INCREF(it->len);
    1211             : 
    1212        9269 :     diff = PyNumber_Subtract(it->len, _PyLong_GetOne());
    1213        9269 :     if (!diff)
    1214           0 :         goto create_failure;
    1215             : 
    1216        9269 :     product = PyNumber_Multiply(diff, range->step);
    1217        9269 :     Py_DECREF(diff);
    1218        9269 :     if (!product)
    1219           0 :         goto create_failure;
    1220             : 
    1221        9269 :     sum = PyNumber_Add(range->start, product);
    1222        9269 :     Py_DECREF(product);
    1223        9269 :     it->start = sum;
    1224        9269 :     if (!it->start)
    1225           0 :         goto create_failure;
    1226             : 
    1227        9269 :     it->step = PyNumber_Negative(range->step);
    1228        9269 :     if (!it->step)
    1229           0 :         goto create_failure;
    1230             : 
    1231        9269 :     it->index = _PyLong_GetZero();
    1232        9269 :     Py_INCREF(it->index);
    1233        9269 :     return (PyObject *)it;
    1234             : 
    1235           0 : create_failure:
    1236           0 :     Py_DECREF(it);
    1237           0 :     return NULL;
    1238             : }

Generated by: LCOV version 1.14