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 a Py_ssize_t.
9 This only matters on Win64. Though we could use 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 *
validate_step(PyObject * step)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 && _PyLong_Sign(step) == 0) {
33 PyErr_SetString(PyExc_ValueError,
34 "range() arg 3 must not be zero");
35 Py_CLEAR(step);
36 }
37
38 return step;
39 }
40
41 static PyObject *
42 compute_range_length(PyObject *start, PyObject *stop, PyObject *step);
43
44 static rangeobject *
make_range_object(PyTypeObject * type,PyObject * start,PyObject * stop,PyObject * step)45 make_range_object(PyTypeObject *type, PyObject *start,
46 PyObject *stop, PyObject *step)
47 {
48 rangeobject *obj = NULL;
49 PyObject *length;
50 length = compute_range_length(start, stop, step);
51 if (length == NULL) {
52 return NULL;
53 }
54 obj = PyObject_New(rangeobject, type);
55 if (obj == NULL) {
56 Py_DECREF(length);
57 return NULL;
58 }
59 obj->start = start;
60 obj->stop = stop;
61 obj->step = step;
62 obj->length = length;
63 return obj;
64 }
65
66 /* XXX(nnorwitz): should we error check if the user passes any empty ranges?
67 range(-10)
68 range(0, -5)
69 range(0, 5, -1)
70 */
71 static PyObject *
range_new(PyTypeObject * type,PyObject * args,PyObject * kw)72 range_new(PyTypeObject *type, PyObject *args, PyObject *kw)
73 {
74 rangeobject *obj;
75 PyObject *start = NULL, *stop = NULL, *step = NULL;
76
77 if (!_PyArg_NoKeywords("range()", kw))
78 return NULL;
79
80 if (PyTuple_Size(args) <= 1) {
81 if (!PyArg_UnpackTuple(args, "range", 1, 1, &stop))
82 return NULL;
83 stop = PyNumber_Index(stop);
84 if (!stop)
85 return NULL;
86 start = PyLong_FromLong(0);
87 if (!start) {
88 Py_DECREF(stop);
89 return NULL;
90 }
91 step = PyLong_FromLong(1);
92 if (!step) {
93 Py_DECREF(stop);
94 Py_DECREF(start);
95 return NULL;
96 }
97 }
98 else {
99 if (!PyArg_UnpackTuple(args, "range", 2, 3,
100 &start, &stop, &step))
101 return NULL;
102
103 /* Convert borrowed refs to owned refs */
104 start = PyNumber_Index(start);
105 if (!start)
106 return NULL;
107 stop = PyNumber_Index(stop);
108 if (!stop) {
109 Py_DECREF(start);
110 return NULL;
111 }
112 step = validate_step(step); /* Caution, this can clear exceptions */
113 if (!step) {
114 Py_DECREF(start);
115 Py_DECREF(stop);
116 return NULL;
117 }
118 }
119
120 obj = make_range_object(type, start, stop, step);
121 if (obj != NULL)
122 return (PyObject *) obj;
123
124 /* Failed to create object, release attributes */
125 Py_DECREF(start);
126 Py_DECREF(stop);
127 Py_DECREF(step);
128 return NULL;
129 }
130
131 PyDoc_STRVAR(range_doc,
132 "range(stop) -> range object\n\
133 range(start, stop[, step]) -> range object\n\
134 \n\
135 Return an object that produces a sequence of integers from start (inclusive)\n\
136 to stop (exclusive) by step. range(i, j) produces i, i+1, i+2, ..., j-1.\n\
137 start defaults to 0, and stop is omitted! range(4) produces 0, 1, 2, 3.\n\
138 These are exactly the valid indices for a list of 4 elements.\n\
139 When step is given, it specifies the increment (or decrement).");
140
141 static void
range_dealloc(rangeobject * r)142 range_dealloc(rangeobject *r)
143 {
144 Py_DECREF(r->start);
145 Py_DECREF(r->stop);
146 Py_DECREF(r->step);
147 Py_DECREF(r->length);
148 PyObject_Del(r);
149 }
150
151 /* Return number of items in range (lo, hi, step) as a PyLong object,
152 * when arguments are PyLong objects. Arguments MUST return 1 with
153 * PyLong_Check(). Return NULL when there is an error.
154 */
155 static PyObject*
compute_range_length(PyObject * start,PyObject * stop,PyObject * step)156 compute_range_length(PyObject *start, PyObject *stop, PyObject *step)
157 {
158 /* -------------------------------------------------------------
159 Algorithm is equal to that of get_len_of_range(), but it operates
160 on PyObjects (which are assumed to be PyLong objects).
161 ---------------------------------------------------------------*/
162 int cmp_result;
163 PyObject *lo, *hi;
164 PyObject *diff = NULL;
165 PyObject *one = NULL;
166 PyObject *tmp1 = NULL, *tmp2 = NULL, *result;
167 /* holds sub-expression evaluations */
168
169 PyObject *zero = PyLong_FromLong(0);
170 if (zero == NULL)
171 return NULL;
172 cmp_result = PyObject_RichCompareBool(step, zero, Py_GT);
173 Py_DECREF(zero);
174 if (cmp_result == -1)
175 return NULL;
176
177 if (cmp_result == 1) {
178 lo = start;
179 hi = stop;
180 Py_INCREF(step);
181 } else {
182 lo = stop;
183 hi = start;
184 step = PyNumber_Negative(step);
185 if (!step)
186 return NULL;
187 }
188
189 /* if (lo >= hi), return length of 0. */
190 cmp_result = PyObject_RichCompareBool(lo, hi, Py_GE);
191 if (cmp_result != 0) {
192 Py_DECREF(step);
193 if (cmp_result < 0)
194 return NULL;
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_DECREF(step);
222 Py_XDECREF(tmp2);
223 Py_XDECREF(diff);
224 Py_XDECREF(tmp1);
225 Py_XDECREF(one);
226 return NULL;
227 }
228
229 static Py_ssize_t
range_length(rangeobject * r)230 range_length(rangeobject *r)
231 {
232 return PyLong_AsSsize_t(r->length);
233 }
234
235 static PyObject *
compute_item(rangeobject * r,PyObject * i)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 *
compute_range_item(rangeobject * r,PyObject * arg)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 *
range_item(rangeobject * r,Py_ssize_t i)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 *
compute_slice(rangeobject * r,PyObject * _slice)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
range_contains_long(rangeobject * r,PyObject * ob)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
range_contains(rangeobject * r,PyObject * ob)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
range_equals(rangeobject * r0,rangeobject * r1)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 *
range_richcompare(PyObject * self,PyObject * other,int op)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
range_hash(rangeobject * r)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 *
range_count(rangeobject * r,PyObject * ob)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 *
range_index(rangeobject * r,PyObject * ob)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 *
range_repr(rangeobject * r)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 *
range_reduce(rangeobject * r,PyObject * args)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 *
range_subscript(rangeobject * self,PyObject * item)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 *
rangeiter_next(rangeiterobject * r)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 *
rangeiter_len(rangeiterobject * r)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 *
rangeiter_reduce(rangeiterobject * r)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 *
rangeiter_setstate(rangeiterobject * r,PyObject * state)805 rangeiter_setstate(rangeiterobject *r, PyObject *state)
806 {
807 long index = PyLong_AsLong(state);
808 if (index == -1 && PyErr_Occurred())
809 return NULL;
810 /* silently clip the index value */
811 if (index < 0)
812 index = 0;
813 else if (index > r->len)
814 index = r->len; /* exhausted iterator */
815 r->index = index;
816 Py_RETURN_NONE;
817 }
818
819 PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
820 PyDoc_STRVAR(setstate_doc, "Set state information for unpickling.");
821
822 static PyMethodDef rangeiter_methods[] = {
823 {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS,
824 length_hint_doc},
825 {"__reduce__", (PyCFunction)rangeiter_reduce, METH_NOARGS,
826 reduce_doc},
827 {"__setstate__", (PyCFunction)rangeiter_setstate, METH_O,
828 setstate_doc},
829 {NULL, NULL} /* sentinel */
830 };
831
832 static PyObject *rangeiter_new(PyTypeObject *, PyObject *args, PyObject *kw);
833
834 PyTypeObject PyRangeIter_Type = {
835 PyVarObject_HEAD_INIT(&PyType_Type, 0)
836 "range_iterator", /* tp_name */
837 sizeof(rangeiterobject), /* tp_basicsize */
838 0, /* tp_itemsize */
839 /* methods */
840 (destructor)PyObject_Del, /* tp_dealloc */
841 0, /* tp_print */
842 0, /* tp_getattr */
843 0, /* tp_setattr */
844 0, /* tp_reserved */
845 0, /* tp_repr */
846 0, /* tp_as_number */
847 0, /* tp_as_sequence */
848 0, /* tp_as_mapping */
849 0, /* tp_hash */
850 0, /* tp_call */
851 0, /* tp_str */
852 PyObject_GenericGetAttr, /* tp_getattro */
853 0, /* tp_setattro */
854 0, /* tp_as_buffer */
855 Py_TPFLAGS_DEFAULT, /* tp_flags */
856 0, /* tp_doc */
857 0, /* tp_traverse */
858 0, /* tp_clear */
859 0, /* tp_richcompare */
860 0, /* tp_weaklistoffset */
861 PyObject_SelfIter, /* tp_iter */
862 (iternextfunc)rangeiter_next, /* tp_iternext */
863 rangeiter_methods, /* tp_methods */
864 0, /* tp_members */
865 0, /* tp_getset */
866 0, /* tp_base */
867 0, /* tp_dict */
868 0, /* tp_descr_get */
869 0, /* tp_descr_set */
870 0, /* tp_dictoffset */
871 0, /* tp_init */
872 0, /* tp_alloc */
873 rangeiter_new, /* tp_new */
874 };
875
876 /* Return number of items in range (lo, hi, step). step != 0
877 * required. The result always fits in an unsigned long.
878 */
879 static unsigned long
get_len_of_range(long lo,long hi,long step)880 get_len_of_range(long lo, long hi, long step)
881 {
882 /* -------------------------------------------------------------
883 If step > 0 and lo >= hi, or step < 0 and lo <= hi, the range is empty.
884 Else for step > 0, if n values are in the range, the last one is
885 lo + (n-1)*step, which must be <= hi-1. Rearranging,
886 n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives
887 the proper value. Since lo < hi in this case, hi-lo-1 >= 0, so
888 the RHS is non-negative and so truncation is the same as the
889 floor. Letting M be the largest positive long, the worst case
890 for the RHS numerator is hi=M, lo=-M-1, and then
891 hi-lo-1 = M-(-M-1)-1 = 2*M. Therefore unsigned long has enough
892 precision to compute the RHS exactly. The analysis for step < 0
893 is similar.
894 ---------------------------------------------------------------*/
895 assert(step != 0);
896 if (step > 0 && lo < hi)
897 return 1UL + (hi - 1UL - lo) / step;
898 else if (step < 0 && lo > hi)
899 return 1UL + (lo - 1UL - hi) / (0UL - step);
900 else
901 return 0UL;
902 }
903
904 /* Initialize a rangeiter object. If the length of the rangeiter object
905 is not representable as a C long, OverflowError is raised. */
906
907 static PyObject *
fast_range_iter(long start,long stop,long step)908 fast_range_iter(long start, long stop, long step)
909 {
910 rangeiterobject *it = PyObject_New(rangeiterobject, &PyRangeIter_Type);
911 unsigned long ulen;
912 if (it == NULL)
913 return NULL;
914 it->start = start;
915 it->step = step;
916 ulen = get_len_of_range(start, stop, step);
917 if (ulen > (unsigned long)LONG_MAX) {
918 Py_DECREF(it);
919 PyErr_SetString(PyExc_OverflowError,
920 "range too large to represent as a range_iterator");
921 return NULL;
922 }
923 it->len = (long)ulen;
924 it->index = 0;
925 return (PyObject *)it;
926 }
927
928 static PyObject *
rangeiter_new(PyTypeObject * type,PyObject * args,PyObject * kw)929 rangeiter_new(PyTypeObject *type, PyObject *args, PyObject *kw)
930 {
931 long start, stop, step;
932
933 if (PyErr_WarnEx(PyExc_DeprecationWarning,
934 "range_iterator(): creating instances of range_iterator "
935 "by calling range_iterator type is deprecated",
936 1)) {
937 return NULL;
938 }
939
940 if (!_PyArg_NoKeywords("range_iterator()", kw)) {
941 return NULL;
942 }
943
944 if (!PyArg_ParseTuple(args,
945 "lll;range_iterator() requires 3 int arguments",
946 &start, &stop, &step)) {
947 return NULL;
948 }
949 if (step == 0) {
950 PyErr_SetString(PyExc_ValueError,
951 "range_iterator() arg 3 must not be zero");
952 return NULL;
953 }
954
955 return fast_range_iter(start, stop, step);
956 }
957
958 typedef struct {
959 PyObject_HEAD
960 PyObject *index;
961 PyObject *start;
962 PyObject *step;
963 PyObject *len;
964 } longrangeiterobject;
965
966 static PyObject *
longrangeiter_len(longrangeiterobject * r,PyObject * no_args)967 longrangeiter_len(longrangeiterobject *r, PyObject *no_args)
968 {
969 return PyNumber_Subtract(r->len, r->index);
970 }
971
972 static PyObject *
longrangeiter_reduce(longrangeiterobject * r)973 longrangeiter_reduce(longrangeiterobject *r)
974 {
975 PyObject *product, *stop=NULL;
976 PyObject *range;
977
978 /* create a range object for pickling. Must calculate the "stop" value */
979 product = PyNumber_Multiply(r->len, r->step);
980 if (product == NULL)
981 return NULL;
982 stop = PyNumber_Add(r->start, product);
983 Py_DECREF(product);
984 if (stop == NULL)
985 return NULL;
986 Py_INCREF(r->start);
987 Py_INCREF(r->step);
988 range = (PyObject*)make_range_object(&PyRange_Type,
989 r->start, stop, r->step);
990 if (range == NULL) {
991 Py_DECREF(r->start);
992 Py_DECREF(stop);
993 Py_DECREF(r->step);
994 return NULL;
995 }
996
997 /* return the result */
998 return Py_BuildValue("N(N)O", _PyObject_GetBuiltin("iter"), range, r->index);
999 }
1000
1001 static PyObject *
longrangeiter_setstate(longrangeiterobject * r,PyObject * state)1002 longrangeiter_setstate(longrangeiterobject *r, PyObject *state)
1003 {
1004 int cmp;
1005
1006 /* clip the value */
1007 PyObject *zero = PyLong_FromLong(0);
1008 if (zero == NULL)
1009 return NULL;
1010 cmp = PyObject_RichCompareBool(state, zero, Py_LT);
1011 if (cmp > 0) {
1012 Py_XSETREF(r->index, zero);
1013 Py_RETURN_NONE;
1014 }
1015 Py_DECREF(zero);
1016 if (cmp < 0)
1017 return NULL;
1018
1019 cmp = PyObject_RichCompareBool(r->len, state, Py_LT);
1020 if (cmp < 0)
1021 return NULL;
1022 if (cmp > 0)
1023 state = r->len;
1024
1025 Py_INCREF(state);
1026 Py_XSETREF(r->index, state);
1027 Py_RETURN_NONE;
1028 }
1029
1030 static PyMethodDef longrangeiter_methods[] = {
1031 {"__length_hint__", (PyCFunction)longrangeiter_len, METH_NOARGS,
1032 length_hint_doc},
1033 {"__reduce__", (PyCFunction)longrangeiter_reduce, METH_NOARGS,
1034 reduce_doc},
1035 {"__setstate__", (PyCFunction)longrangeiter_setstate, METH_O,
1036 setstate_doc},
1037 {NULL, NULL} /* sentinel */
1038 };
1039
1040 static void
longrangeiter_dealloc(longrangeiterobject * r)1041 longrangeiter_dealloc(longrangeiterobject *r)
1042 {
1043 Py_XDECREF(r->index);
1044 Py_XDECREF(r->start);
1045 Py_XDECREF(r->step);
1046 Py_XDECREF(r->len);
1047 PyObject_Del(r);
1048 }
1049
1050 static PyObject *
longrangeiter_next(longrangeiterobject * r)1051 longrangeiter_next(longrangeiterobject *r)
1052 {
1053 PyObject *one, *product, *new_index, *result;
1054 if (PyObject_RichCompareBool(r->index, r->len, Py_LT) != 1)
1055 return NULL;
1056
1057 one = PyLong_FromLong(1);
1058 if (!one)
1059 return NULL;
1060
1061 new_index = PyNumber_Add(r->index, one);
1062 Py_DECREF(one);
1063 if (!new_index)
1064 return NULL;
1065
1066 product = PyNumber_Multiply(r->index, r->step);
1067 if (!product) {
1068 Py_DECREF(new_index);
1069 return NULL;
1070 }
1071
1072 result = PyNumber_Add(r->start, product);
1073 Py_DECREF(product);
1074 if (result) {
1075 Py_SETREF(r->index, new_index);
1076 }
1077 else {
1078 Py_DECREF(new_index);
1079 }
1080
1081 return result;
1082 }
1083
1084 PyTypeObject PyLongRangeIter_Type = {
1085 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1086 "longrange_iterator", /* tp_name */
1087 sizeof(longrangeiterobject), /* tp_basicsize */
1088 0, /* tp_itemsize */
1089 /* methods */
1090 (destructor)longrangeiter_dealloc, /* tp_dealloc */
1091 0, /* tp_print */
1092 0, /* tp_getattr */
1093 0, /* tp_setattr */
1094 0, /* tp_reserved */
1095 0, /* tp_repr */
1096 0, /* tp_as_number */
1097 0, /* tp_as_sequence */
1098 0, /* tp_as_mapping */
1099 0, /* tp_hash */
1100 0, /* tp_call */
1101 0, /* tp_str */
1102 PyObject_GenericGetAttr, /* tp_getattro */
1103 0, /* tp_setattro */
1104 0, /* tp_as_buffer */
1105 Py_TPFLAGS_DEFAULT, /* tp_flags */
1106 0, /* tp_doc */
1107 0, /* tp_traverse */
1108 0, /* tp_clear */
1109 0, /* tp_richcompare */
1110 0, /* tp_weaklistoffset */
1111 PyObject_SelfIter, /* tp_iter */
1112 (iternextfunc)longrangeiter_next, /* tp_iternext */
1113 longrangeiter_methods, /* tp_methods */
1114 0,
1115 };
1116
1117 static PyObject *
range_iter(PyObject * seq)1118 range_iter(PyObject *seq)
1119 {
1120 rangeobject *r = (rangeobject *)seq;
1121 longrangeiterobject *it;
1122 long lstart, lstop, lstep;
1123 PyObject *int_it;
1124
1125 assert(PyRange_Check(seq));
1126
1127 /* If all three fields and the length convert to long, use the int
1128 * version */
1129 lstart = PyLong_AsLong(r->start);
1130 if (lstart == -1 && PyErr_Occurred()) {
1131 PyErr_Clear();
1132 goto long_range;
1133 }
1134 lstop = PyLong_AsLong(r->stop);
1135 if (lstop == -1 && PyErr_Occurred()) {
1136 PyErr_Clear();
1137 goto long_range;
1138 }
1139 lstep = PyLong_AsLong(r->step);
1140 if (lstep == -1 && PyErr_Occurred()) {
1141 PyErr_Clear();
1142 goto long_range;
1143 }
1144 int_it = fast_range_iter(lstart, lstop, lstep);
1145 if (int_it == NULL && PyErr_ExceptionMatches(PyExc_OverflowError)) {
1146 PyErr_Clear();
1147 goto long_range;
1148 }
1149 return (PyObject *)int_it;
1150
1151 long_range:
1152 it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
1153 if (it == NULL)
1154 return NULL;
1155
1156 /* Do all initialization here, so we can DECREF on failure. */
1157 it->start = r->start;
1158 it->step = r->step;
1159 it->len = r->length;
1160 Py_INCREF(it->start);
1161 Py_INCREF(it->step);
1162 Py_INCREF(it->len);
1163
1164 it->index = PyLong_FromLong(0);
1165 if (!it->index)
1166 goto create_failure;
1167
1168 return (PyObject *)it;
1169
1170 create_failure:
1171 Py_DECREF(it);
1172 return NULL;
1173 }
1174
1175 static PyObject *
range_reverse(PyObject * seq)1176 range_reverse(PyObject *seq)
1177 {
1178 rangeobject *range = (rangeobject*) seq;
1179 longrangeiterobject *it;
1180 PyObject *one, *sum, *diff, *product;
1181 long lstart, lstop, lstep, new_start, new_stop;
1182 unsigned long ulen;
1183
1184 assert(PyRange_Check(seq));
1185
1186 /* reversed(range(start, stop, step)) can be expressed as
1187 range(start+(n-1)*step, start-step, -step), where n is the number of
1188 integers in the range.
1189
1190 If each of start, stop, step, -step, start-step, and the length
1191 of the iterator is representable as a C long, use the int
1192 version. This excludes some cases where the reversed range is
1193 representable as a range_iterator, but it's good enough for
1194 common cases and it makes the checks simple. */
1195
1196 lstart = PyLong_AsLong(range->start);
1197 if (lstart == -1 && PyErr_Occurred()) {
1198 PyErr_Clear();
1199 goto long_range;
1200 }
1201 lstop = PyLong_AsLong(range->stop);
1202 if (lstop == -1 && PyErr_Occurred()) {
1203 PyErr_Clear();
1204 goto long_range;
1205 }
1206 lstep = PyLong_AsLong(range->step);
1207 if (lstep == -1 && PyErr_Occurred()) {
1208 PyErr_Clear();
1209 goto long_range;
1210 }
1211 /* check for possible overflow of -lstep */
1212 if (lstep == LONG_MIN)
1213 goto long_range;
1214
1215 /* check for overflow of lstart - lstep:
1216
1217 for lstep > 0, need only check whether lstart - lstep < LONG_MIN.
1218 for lstep < 0, need only check whether lstart - lstep > LONG_MAX
1219
1220 Rearrange these inequalities as:
1221
1222 lstart - LONG_MIN < lstep (lstep > 0)
1223 LONG_MAX - lstart < -lstep (lstep < 0)
1224
1225 and compute both sides as unsigned longs, to avoid the
1226 possibility of undefined behaviour due to signed overflow. */
1227
1228 if (lstep > 0) {
1229 if ((unsigned long)lstart - LONG_MIN < (unsigned long)lstep)
1230 goto long_range;
1231 }
1232 else {
1233 if (LONG_MAX - (unsigned long)lstart < 0UL - lstep)
1234 goto long_range;
1235 }
1236
1237 ulen = get_len_of_range(lstart, lstop, lstep);
1238 if (ulen > (unsigned long)LONG_MAX)
1239 goto long_range;
1240
1241 new_stop = lstart - lstep;
1242 new_start = (long)(new_stop + ulen * lstep);
1243 return fast_range_iter(new_start, new_stop, -lstep);
1244
1245 long_range:
1246 it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
1247 if (it == NULL)
1248 return NULL;
1249
1250 /* start + (len - 1) * step */
1251 it->len = range->length;
1252 Py_INCREF(it->len);
1253
1254 one = PyLong_FromLong(1);
1255 if (!one)
1256 goto create_failure;
1257
1258 diff = PyNumber_Subtract(it->len, one);
1259 Py_DECREF(one);
1260 if (!diff)
1261 goto create_failure;
1262
1263 product = PyNumber_Multiply(diff, range->step);
1264 Py_DECREF(diff);
1265 if (!product)
1266 goto create_failure;
1267
1268 sum = PyNumber_Add(range->start, product);
1269 Py_DECREF(product);
1270 it->start = sum;
1271 if (!it->start)
1272 goto create_failure;
1273
1274 it->step = PyNumber_Negative(range->step);
1275 if (!it->step)
1276 goto create_failure;
1277
1278 it->index = PyLong_FromLong(0);
1279 if (!it->index)
1280 goto create_failure;
1281
1282 return (PyObject *)it;
1283
1284 create_failure:
1285 Py_DECREF(it);
1286 return NULL;
1287 }
1288