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