← Back to branch summary

~ubuntu-branches/ubuntu/trusty/python3.4/trusty-proposed

« back to all changes in this revision

Viewing changes to Objects/rangeobject.c

  • Committer: Package Import Robot
  • Author(s): Matthias Klose
  • Date: 2013-11-25 09:44:27 UTC
  • Revision ID: package-import@ubuntu.com-20131125094427-lzxj8ap5w01lmo7f
Tags: upstream-3.4~b1
Import upstream version 3.4~b1

Show diffs side-by-side

added added

removed removed

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