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