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