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