Objects/rangeobject.c

   1 /* Range object implementation */
   2
   3 #include "Python.h"
   4
   5 /* Support objects whose length is > PY_SSIZE_T_MAX.
   6
   7    This could be sped up for small PyLongs if they fit in an Py_ssize_t.
   8    This only matters on Win64.  Though we could use PY_LONG_LONG which
   9    would presumably help perf.
  10 */
  11
  12 typedef struct {
  13     PyObject_HEAD
  14     PyObject *start;
  15     PyObject *stop;
  16     PyObject *step;
  17 } rangeobject;
  18
  19 /* Helper function for validating step.  Always returns a new reference or
  20    NULL on error.
  21 */
  22 static PyObject *
  23 validate_step(PyObject *step)
  24 {
  25     /* No step specified, use a step of 1. */
  26     if (!step)
  27         return PyLong_FromLong(1);
  28
  29     step = PyNumber_Index(step);
  30     if (step) {
  31         Py_ssize_t istep = PyNumber_AsSsize_t(step, NULL);
  32         if (istep == -1 && PyErr_Occurred()) {
  33             /* Ignore OverflowError, we know the value isn't 0. */
  34             PyErr_Clear();
  35         }
  36         else if (istep == 0) {
  37             PyErr_SetString(PyExc_ValueError,
  38                             "range() arg 3 must not be zero");
  39             Py_CLEAR(step);
  40         }
  41     }
  42
  43     return step;
  44 }
  45
  46 /* XXX(nnorwitz): should we error check if the user passes any empty ranges?
  47    range(-10)
  48    range(0, -5)
  49    range(0, 5, -1)
  50 */
  51 static PyObject *
  52 range_new(PyTypeObject *type, PyObject *args, PyObject *kw)
  53 {
  54     rangeobject *obj = NULL;
  55     PyObject *start = NULL, *stop = NULL, *step = NULL;
  56
  57     if (!_PyArg_NoKeywords("range()", kw))
  58         return NULL;
  59
  60     if (PyTuple_Size(args) <= 1) {
  61         if (!PyArg_UnpackTuple(args, "range", 1, 1, &stop))
  62             return NULL;
  63         stop = PyNumber_Index(stop);
  64         if (!stop)
  65             return NULL;
  66         start = PyLong_FromLong(0);
  67         if (!start) {
  68             Py_DECREF(stop);
  69             return NULL;
  70         }
  71         step = PyLong_FromLong(1);
  72         if (!step) {
  73             Py_DECREF(stop);
  74             Py_DECREF(start);
  75             return NULL;
  76         }
  77     }
  78     else {
  79         if (!PyArg_UnpackTuple(args, "range", 2, 3,
  80                                &start, &stop, &step))
  81             return NULL;
  82
  83         /* Convert borrowed refs to owned refs */
  84         start = PyNumber_Index(start);
  85         if (!start)
  86             return NULL;
  87         stop = PyNumber_Index(stop);
  88         if (!stop) {
  89             Py_DECREF(start);
  90             return NULL;
  91         }
  92         step = validate_step(step);    /* Caution, this can clear exceptions */
  93         if (!step) {
  94             Py_DECREF(start);
  95             Py_DECREF(stop);
  96             return NULL;
  97         }
  98     }
  99
 100     obj = PyObject_New(rangeobject, &PyRange_Type);
 101     if (obj == NULL)
 102         goto Fail;
 103     obj->start = start;
 104     obj->stop = stop;
 105     obj->step = step;
 106     return (PyObject *) obj;
 107
 108 Fail:
 109     Py_XDECREF(start);
 110     Py_XDECREF(stop);
 111     Py_XDECREF(step);
 112     return NULL;
 113 }
 114
 115 PyDoc_STRVAR(range_doc,
 116 "range([start,] stop[, step]) -> range object\n\
 117 \n\
 118 Returns an iterator that generates the numbers in the range on demand.");
 119
 120 static void
 121 range_dealloc(rangeobject *r)
 122 {
 123     Py_DECREF(r->start);
 124     Py_DECREF(r->stop);
 125     Py_DECREF(r->step);
 126     PyObject_Del(r);
 127 }
 128
 129 /* Return number of items in range (lo, hi, step) as a PyLong object,
 130  * when arguments are PyLong objects.  Arguments MUST return 1 with
 131  * PyLong_Check().  Return NULL when there is an error.
 132  */
 133 static PyObject*
 134 range_length_obj(rangeobject *r)
 135 {
 136     /* -------------------------------------------------------------
 137     Algorithm is equal to that of get_len_of_range(), but it operates
 138     on PyObjects (which are assumed to be PyLong objects).
 139     ---------------------------------------------------------------*/
 140     int cmp_result;
 141     PyObject *lo, *hi;
 142     PyObject *step = NULL;
 143     PyObject *diff = NULL;
 144     PyObject *one = NULL;
 145     PyObject *tmp1 = NULL, *tmp2 = NULL, *result;
 146                 /* holds sub-expression evaluations */
 147
 148     PyObject *zero = PyLong_FromLong(0);
 149     if (zero == NULL)
 150         return NULL;
 151     cmp_result = PyObject_RichCompareBool(r->step, zero, Py_GT);
 152     Py_DECREF(zero);
 153     if (cmp_result == -1)
 154         return NULL;
 155
 156     if (cmp_result == 1) {
 157         lo = r->start;
 158         hi = r->stop;
 159         step = r->step;
 160         Py_INCREF(step);
 161     } else {
 162         lo = r->stop;
 163         hi = r->start;
 164         step = PyNumber_Negative(r->step);
 165         if (!step)
 166             return NULL;
 167     }
 168
 169     /* if (lo >= hi), return length of 0. */
 170     if (PyObject_RichCompareBool(lo, hi, Py_GE) == 1) {
 171         Py_XDECREF(step);
 172         return PyLong_FromLong(0);
 173     }
 174
 175     if ((one = PyLong_FromLong(1L)) == NULL)
 176         goto Fail;
 177
 178     if ((tmp1 = PyNumber_Subtract(hi, lo)) == NULL)
 179         goto Fail;
 180
 181     if ((diff = PyNumber_Subtract(tmp1, one)) == NULL)
 182         goto Fail;
 183
 184     if ((tmp2 = PyNumber_FloorDivide(diff, step)) == NULL)
 185         goto Fail;
 186
 187     if ((result = PyNumber_Add(tmp2, one)) == NULL)
 188         goto Fail;
 189
 190     Py_DECREF(tmp2);
 191     Py_DECREF(diff);
 192     Py_DECREF(step);
 193     Py_DECREF(tmp1);
 194     Py_DECREF(one);
 195     return result;
 196
 197   Fail:
 198     Py_XDECREF(tmp2);
 199     Py_XDECREF(diff);
 200     Py_XDECREF(step);
 201     Py_XDECREF(tmp1);
 202     Py_XDECREF(one);
 203     return NULL;
 204 }
 205
 206 static Py_ssize_t
 207 range_length(rangeobject *r)
 208 {
 209     PyObject *len = range_length_obj(r);
 210     Py_ssize_t result = -1;
 211     if (len) {
 212         result = PyLong_AsSsize_t(len);
 213         Py_DECREF(len);
 214     }
 215     return result;
 216 }
 217
 218 /* range(...)[x] is necessary for:  seq[:] = range(...) */
 219
 220 static PyObject *
 221 range_item(rangeobject *r, Py_ssize_t i)
 222 {
 223     Py_ssize_t len = range_length(r);
 224     PyObject *rem, *incr, *result;
 225
 226     /* XXX(nnorwitz): should negative indices be supported? */
 227     /* XXX(nnorwitz): should support range[x] where x > PY_SSIZE_T_MAX? */
 228     if (i < 0 || i >= len) {
 229         if (!PyErr_Occurred())
 230             PyErr_SetString(PyExc_IndexError,
 231                             "range object index out of range");
 232         return NULL;
 233     }
 234
 235     /* XXX(nnorwitz): optimize for short ints. */
 236     rem = PyLong_FromSsize_t(i);
 237     if (!rem)
 238         return NULL;
 239     incr = PyNumber_Multiply(rem, r->step);
 240     Py_DECREF(rem);
 241     if (!incr)
 242         return NULL;
 243     result = PyNumber_Add(r->start, incr);
 244     Py_DECREF(incr);
 245     return result;
 246 }
 247
 248 static PyObject *
 249 range_repr(rangeobject *r)
 250 {
 251     Py_ssize_t istep;
 252
 253     /* Check for special case values for printing.  We don't always
 254        need the step value.  We don't care about errors
 255        (it means overflow), so clear the errors. */
 256     istep = PyNumber_AsSsize_t(r->step, NULL);
 257     if (istep != 1 || (istep == -1 && PyErr_Occurred())) {
 258         PyErr_Clear();
 259     }
 260
 261     if (istep == 1)
 262         return PyUnicode_FromFormat("range(%R, %R)", r->start, r->stop);
 263     else
 264         return PyUnicode_FromFormat("range(%R, %R, %R)",
 265                                     r->start, r->stop, r->step);
 266 }
 267
 268 /* Pickling support */
 269 static PyObject *
 270 range_reduce(rangeobject *r, PyObject *args)
 271 {
 272         return Py_BuildValue("(O(OOO))", Py_TYPE(r),
 273                          r->start, r->stop, r->step);
 274 }
 275
 276 static PySequenceMethods range_as_sequence = {
 277     (lenfunc)range_length,      /* sq_length */
 278     0,                  /* sq_concat */
 279     0,                  /* sq_repeat */
 280     (ssizeargfunc)range_item, /* sq_item */
 281     0,                  /* sq_slice */
 282 };
 283
 284 static PyObject * range_iter(PyObject *seq);
 285 static PyObject * range_reverse(PyObject *seq);
 286
 287 PyDoc_STRVAR(reverse_doc,
 288 "Returns a reverse iterator.");
 289
 290 static PyMethodDef range_methods[] = {
 291     {"__reversed__",    (PyCFunction)range_reverse, METH_NOARGS,
 292         reverse_doc},
 293     {"__reduce__",      (PyCFunction)range_reduce, METH_VARARGS},
 294     {NULL,              NULL}           /* sentinel */
 295 };
 296
 297 PyTypeObject PyRange_Type = {
 298         PyVarObject_HEAD_INIT(&PyType_Type, 0)
 299         "range",                /* Name of this type */
 300         sizeof(rangeobject),    /* Basic object size */
 301         0,                      /* Item size for varobject */
 302         (destructor)range_dealloc, /* tp_dealloc */
 303         0,                      /* tp_print */
 304         0,                      /* tp_getattr */
 305         0,                      /* tp_setattr */
 306         0,                      /* tp_reserved */
 307         (reprfunc)range_repr,   /* tp_repr */
 308         0,                      /* tp_as_number */
 309         &range_as_sequence,     /* tp_as_sequence */
 310         0,                      /* tp_as_mapping */
 311         0,                      /* tp_hash */
 312         0,                      /* tp_call */
 313         0,                      /* tp_str */
 314         PyObject_GenericGetAttr,  /* tp_getattro */
 315         0,                      /* tp_setattro */
 316         0,                      /* tp_as_buffer */
 317         Py_TPFLAGS_DEFAULT,     /* tp_flags */
 318         range_doc,              /* tp_doc */
 319         0,                      /* tp_traverse */
 320         0,                      /* tp_clear */
 321         0,                      /* tp_richcompare */
 322         0,                      /* tp_weaklistoffset */
 323         range_iter,             /* tp_iter */
 324         0,                      /* tp_iternext */
 325         range_methods,          /* tp_methods */
 326         0,                      /* tp_members */
 327         0,                      /* tp_getset */
 328         0,                      /* tp_base */
 329         0,                      /* tp_dict */
 330         0,                      /* tp_descr_get */
 331         0,                      /* tp_descr_set */
 332         0,                      /* tp_dictoffset */
 333         0,                      /* tp_init */
 334         0,                      /* tp_alloc */
 335         range_new,              /* tp_new */
 336 };
 337
 338 /*********************** range Iterator **************************/
 339
 340 /* There are 2 types of iterators, one for C longs, the other for
 341    Python longs (ie, PyObjects).  This should make iteration fast
 342    in the normal case, but possible for any numeric value.
 343 */
 344
 345 typedef struct {
 346         PyObject_HEAD
 347         long    index;
 348         long    start;
 349         long    step;
 350         long    len;
 351 } rangeiterobject;
 352
 353 static PyObject *
 354 rangeiter_next(rangeiterobject *r)
 355 {
 356     if (r->index < r->len)
 357         /* cast to unsigned to avoid possible signed overflow
 358            in intermediate calculations. */
 359         return PyLong_FromLong((long)(r->start +
 360                                       (unsigned long)(r->index++) * r->step));
 361     return NULL;
 362 }
 363
 364 static PyObject *
 365 rangeiter_len(rangeiterobject *r)
 366 {
 367     return PyLong_FromLong(r->len - r->index);
 368 }
 369
 370 typedef struct {
 371     PyObject_HEAD
 372     PyObject *index;
 373     PyObject *start;
 374     PyObject *step;
 375     PyObject *len;
 376 } longrangeiterobject;
 377
 378 static PyObject *
 379 longrangeiter_len(longrangeiterobject *r, PyObject *no_args)
 380 {
 381     return PyNumber_Subtract(r->len, r->index);
 382 }
 383
 384 static PyObject *rangeiter_new(PyTypeObject *, PyObject *args, PyObject *kw);
 385
 386 PyDoc_STRVAR(length_hint_doc,
 387              "Private method returning an estimate of len(list(it)).");
 388
 389 static PyMethodDef rangeiter_methods[] = {
 390     {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS,
 391         length_hint_doc},
 392     {NULL,              NULL}           /* sentinel */
 393 };
 394
 395 PyTypeObject PyRangeIter_Type = {
 396         PyVarObject_HEAD_INIT(&PyType_Type, 0)
 397         "range_iterator",                        /* tp_name */
 398         sizeof(rangeiterobject),                /* tp_basicsize */
 399         0,                                      /* tp_itemsize */
 400         /* methods */
 401         (destructor)PyObject_Del,               /* tp_dealloc */
 402         0,                                      /* tp_print */
 403         0,                                      /* tp_getattr */
 404         0,                                      /* tp_setattr */
 405         0,                                      /* tp_reserved */
 406         0,                                      /* tp_repr */
 407         0,                                      /* tp_as_number */
 408         0,                                      /* tp_as_sequence */
 409         0,                                      /* tp_as_mapping */
 410         0,                                      /* tp_hash */
 411         0,                                      /* tp_call */
 412         0,                                      /* tp_str */
 413         PyObject_GenericGetAttr,                /* tp_getattro */
 414         0,                                      /* tp_setattro */
 415         0,                                      /* tp_as_buffer */
 416         Py_TPFLAGS_DEFAULT,                     /* tp_flags */
 417         0,                                      /* tp_doc */
 418         0,                                      /* tp_traverse */
 419         0,                                      /* tp_clear */
 420         0,                                      /* tp_richcompare */
 421         0,                                      /* tp_weaklistoffset */
 422         PyObject_SelfIter,                      /* tp_iter */
 423         (iternextfunc)rangeiter_next,           /* tp_iternext */
 424         rangeiter_methods,                      /* tp_methods */
 425         0,                                      /* tp_members */
 426         0,                                      /* tp_getset */
 427         0,                                      /* tp_base */
 428         0,                                      /* tp_dict */
 429         0,                                      /* tp_descr_get */
 430         0,                                      /* tp_descr_set */
 431         0,                                      /* tp_dictoffset */
 432         0,                                      /* tp_init */
 433         0,                                      /* tp_alloc */
 434         rangeiter_new,                          /* tp_new */
 435 };
 436
 437 /* Return number of items in range (lo, hi, step).  step != 0
 438  * required.  The result always fits in an unsigned long.
 439  */
 440 static unsigned long
 441 get_len_of_range(long lo, long hi, long step)
 442 {
 443     /* -------------------------------------------------------------
 444     If step > 0 and lo >= hi, or step < 0 and lo <= hi, the range is empty.
 445     Else for step > 0, if n values are in the range, the last one is
 446     lo + (n-1)*step, which must be <= hi-1.  Rearranging,
 447     n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives
 448     the proper value.  Since lo < hi in this case, hi-lo-1 >= 0, so
 449     the RHS is non-negative and so truncation is the same as the
 450     floor.  Letting M be the largest positive long, the worst case
 451     for the RHS numerator is hi=M, lo=-M-1, and then
 452     hi-lo-1 = M-(-M-1)-1 = 2*M.  Therefore unsigned long has enough
 453     precision to compute the RHS exactly.  The analysis for step < 0
 454     is similar.
 455     ---------------------------------------------------------------*/
 456     assert(step != 0);
 457     if (step > 0 && lo < hi)
 458         return 1UL + (hi - 1UL - lo) / step;
 459     else if (step < 0 && lo > hi)
 460         return 1UL + (lo - 1UL - hi) / (0UL - step);
 461     else
 462         return 0UL;
 463 }
 464
 465 /* Initialize a rangeiter object.  If the length of the rangeiter object
 466    is not representable as a C long, OverflowError is raised. */
 467
 468 static PyObject *
 469 int_range_iter(long start, long stop, long step)
 470 {
 471     rangeiterobject *it = PyObject_New(rangeiterobject, &PyRangeIter_Type);
 472     unsigned long ulen;
 473     if (it == NULL)
 474         return NULL;
 475     it->start = start;
 476     it->step = step;
 477     ulen = get_len_of_range(start, stop, step);
 478     if (ulen > (unsigned long)LONG_MAX) {
 479         Py_DECREF(it);
 480         PyErr_SetString(PyExc_OverflowError,
 481                         "range too large to represent as a range_iterator");
 482         return NULL;
 483     }
 484     it->len = (long)ulen;
 485     it->index = 0;
 486     return (PyObject *)it;
 487 }
 488
 489 static PyObject *
 490 rangeiter_new(PyTypeObject *type, PyObject *args, PyObject *kw)
 491 {
 492     long start, stop, step;
 493
 494     if (!_PyArg_NoKeywords("rangeiter()", kw))
 495         return NULL;
 496
 497     if (!PyArg_ParseTuple(args, "lll;rangeiter() requires 3 int arguments",
 498                           &start, &stop, &step))
 499         return NULL;
 500
 501     return int_range_iter(start, stop, step);
 502 }
 503
 504 static PyMethodDef longrangeiter_methods[] = {
 505     {"__length_hint__", (PyCFunction)longrangeiter_len, METH_NOARGS,
 506         length_hint_doc},
 507     {NULL,              NULL}           /* sentinel */
 508 };
 509
 510 static void
 511 longrangeiter_dealloc(longrangeiterobject *r)
 512 {
 513     Py_XDECREF(r->index);
 514     Py_XDECREF(r->start);
 515     Py_XDECREF(r->step);
 516     Py_XDECREF(r->len);
 517     PyObject_Del(r);
 518 }
 519
 520 static PyObject *
 521 longrangeiter_next(longrangeiterobject *r)
 522 {
 523     PyObject *one, *product, *new_index, *result;
 524     if (PyObject_RichCompareBool(r->index, r->len, Py_LT) != 1)
 525         return NULL;
 526
 527     one = PyLong_FromLong(1);
 528     if (!one)
 529         return NULL;
 530
 531     new_index = PyNumber_Add(r->index, one);
 532     Py_DECREF(one);
 533     if (!new_index)
 534         return NULL;
 535
 536     product = PyNumber_Multiply(r->index, r->step);
 537     if (!product) {
 538         Py_DECREF(new_index);
 539         return NULL;
 540     }
 541
 542     result = PyNumber_Add(r->start, product);
 543     Py_DECREF(product);
 544     if (result) {
 545         Py_DECREF(r->index);
 546         r->index = new_index;
 547     }
 548     else {
 549         Py_DECREF(new_index);
 550     }
 551
 552     return result;
 553 }
 554
 555 PyTypeObject PyLongRangeIter_Type = {
 556         PyVarObject_HEAD_INIT(&PyType_Type, 0)
 557         "longrange_iterator",                   /* tp_name */
 558         sizeof(longrangeiterobject),            /* tp_basicsize */
 559         0,                                      /* tp_itemsize */
 560         /* methods */
 561         (destructor)longrangeiter_dealloc,      /* tp_dealloc */
 562         0,                                      /* tp_print */
 563         0,                                      /* tp_getattr */
 564         0,                                      /* tp_setattr */
 565         0,                                      /* tp_reserved */
 566         0,                                      /* tp_repr */
 567         0,                                      /* tp_as_number */
 568         0,                                      /* tp_as_sequence */
 569         0,                                      /* tp_as_mapping */
 570         0,                                      /* tp_hash */
 571         0,                                      /* tp_call */
 572         0,                                      /* tp_str */
 573         PyObject_GenericGetAttr,                /* tp_getattro */
 574         0,                                      /* tp_setattro */
 575         0,                                      /* tp_as_buffer */
 576         Py_TPFLAGS_DEFAULT,                     /* tp_flags */
 577         0,                                      /* tp_doc */
 578         0,                                      /* tp_traverse */
 579         0,                                      /* tp_clear */
 580         0,                                      /* tp_richcompare */
 581         0,                                      /* tp_weaklistoffset */
 582         PyObject_SelfIter,                      /* tp_iter */
 583         (iternextfunc)longrangeiter_next,       /* tp_iternext */
 584         longrangeiter_methods,                  /* tp_methods */
 585         0,
 586 };
 587
 588 static PyObject *
 589 range_iter(PyObject *seq)
 590 {
 591     rangeobject *r = (rangeobject *)seq;
 592     longrangeiterobject *it;
 593     long lstart, lstop, lstep;
 594     PyObject *int_it;
 595
 596     assert(PyRange_Check(seq));
 597
 598     /* If all three fields and the length convert to long, use the int
 599      * version */
 600     lstart = PyLong_AsLong(r->start);
 601     if (lstart == -1 && PyErr_Occurred()) {
 602         PyErr_Clear();
 603         goto long_range;
 604     }
 605     lstop = PyLong_AsLong(r->stop);
 606     if (lstop == -1 && PyErr_Occurred()) {
 607         PyErr_Clear();
 608         goto long_range;
 609     }
 610     lstep = PyLong_AsLong(r->step);
 611     if (lstep == -1 && PyErr_Occurred()) {
 612         PyErr_Clear();
 613         goto long_range;
 614     }
 615     int_it = int_range_iter(lstart, lstop, lstep);
 616     if (int_it == NULL && PyErr_ExceptionMatches(PyExc_OverflowError)) {
 617         PyErr_Clear();
 618         goto long_range;
 619     }
 620     return (PyObject *)int_it;
 621
 622   long_range:
 623     it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
 624     if (it == NULL)
 625         return NULL;
 626
 627     /* Do all initialization here, so we can DECREF on failure. */
 628     it->start = r->start;
 629     it->step = r->step;
 630     Py_INCREF(it->start);
 631     Py_INCREF(it->step);
 632
 633     it->len = it->index = NULL;
 634
 635     it->len = range_length_obj(r);
 636     if (!it->len)
 637         goto create_failure;
 638     it->index = PyLong_FromLong(0);
 639     if (!it->index)
 640         goto create_failure;
 641
 642     return (PyObject *)it;
 643
 644 create_failure:
 645     Py_DECREF(it);
 646     return NULL;
 647 }
 648
 649 static PyObject *
 650 range_reverse(PyObject *seq)
 651 {
 652     rangeobject *range = (rangeobject*) seq;
 653     longrangeiterobject *it;
 654     PyObject *one, *sum, *diff, *len = NULL, *product;
 655     long lstart, lstop, lstep, new_start, new_stop;
 656     unsigned long ulen;
 657
 658     assert(PyRange_Check(seq));
 659
 660     /* reversed(range(start, stop, step)) can be expressed as
 661        range(start+(n-1)*step, start-step, -step), where n is the number of
 662        integers in the range.
 663
 664        If each of start, stop, step, -step, start-step, and the length
 665        of the iterator is representable as a C long, use the int
 666        version.  This excludes some cases where the reversed range is
 667        representable as a range_iterator, but it's good enough for
 668        common cases and it makes the checks simple. */
 669
 670     lstart = PyLong_AsLong(range->start);
 671     if (lstart == -1 && PyErr_Occurred()) {
 672         PyErr_Clear();
 673         goto long_range;
 674     }
 675     lstop = PyLong_AsLong(range->stop);
 676     if (lstop == -1 && PyErr_Occurred()) {
 677         PyErr_Clear();
 678         goto long_range;
 679     }
 680     lstep = PyLong_AsLong(range->step);
 681     if (lstep == -1 && PyErr_Occurred()) {
 682         PyErr_Clear();
 683         goto long_range;
 684     }
 685     /* check for possible overflow of -lstep */
 686     if (lstep == LONG_MIN)
 687         goto long_range;
 688
 689     /* check for overflow of lstart - lstep:
 690
 691        for lstep > 0, need only check whether lstart - lstep < LONG_MIN.
 692        for lstep < 0, need only check whether lstart - lstep > LONG_MAX
 693
 694        Rearrange these inequalities as:
 695
 696            lstart - LONG_MIN < lstep  (lstep > 0)
 697            LONG_MAX - lstart < -lstep  (lstep < 0)
 698
 699        and compute both sides as unsigned longs, to avoid the
 700        possibility of undefined behaviour due to signed overflow. */
 701
 702     if (lstep > 0) {
 703          if ((unsigned long)lstart - LONG_MIN < (unsigned long)lstep)
 704             goto long_range;
 705     }
 706     else {
 707         if (LONG_MAX - (unsigned long)lstart < 0UL - lstep)
 708             goto long_range;
 709     }
 710
 711     ulen = get_len_of_range(lstart, lstop, lstep);
 712     if (ulen > (unsigned long)LONG_MAX)
 713         goto long_range;
 714
 715     new_stop = lstart - lstep;
 716     new_start = (long)(new_stop + ulen * lstep);
 717     return int_range_iter(new_start, new_stop, -lstep);
 718
 719 long_range:
 720     it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
 721     if (it == NULL)
 722         return NULL;
 723
 724     /* start + (len - 1) * step */
 725     len = range_length_obj(range);
 726     if (!len)
 727         goto create_failure;
 728
 729     /* Steal reference to len. */
 730     it->len = len;
 731
 732     one = PyLong_FromLong(1);
 733     if (!one)
 734         goto create_failure;
 735
 736     diff = PyNumber_Subtract(len, one);
 737     Py_DECREF(one);
 738     if (!diff)
 739         goto create_failure;
 740
 741     product = PyNumber_Multiply(diff, range->step);
 742     Py_DECREF(diff);
 743     if (!product)
 744         goto create_failure;
 745
 746     sum = PyNumber_Add(range->start, product);
 747     Py_DECREF(product);
 748     it->start = sum;
 749     if (!it->start)
 750         goto create_failure;
 751
 752     it->step = PyNumber_Negative(range->step);
 753     if (!it->step)
 754         goto create_failure;
 755
 756     it->index = PyLong_FromLong(0);
 757     if (!it->index)
 758         goto create_failure;
 759
 760     return (PyObject *)it;
 761
 762 create_failure:
 763     Py_DECREF(it);
 764     return NULL;
 765 }