LCOV - code coverage report
Current view: | top level - Objects - rangeobject.c (source / functions) |  |  | Hit | Total | Coverage
Test: | CPython 3.12 LCOV report [commit 5e6661bce9] |  | Lines: | 185 | 563 | 32.9 %
Date: | 2023-03-20 08:15:36 |  | Functions: | 17 | 37 | 45.9 %
|  |  | Branches: | 86 | 306 | 28.1 %

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

Generated by: LCOV version 1.14