blob: d6b42793b1415e47233594c163971756476f92b4 [file] [log] [blame]
Guido van Rossum12d12c51993-10-26 17:58:25 +00001/* Range object implementation */
2
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003#include "Python.h"
Benjamin Peterson878ce382011-11-05 15:17:52 -04004#include "structmember.h"
Thomas Woutersefafcea2001-07-09 12:30:54 +00005
Guido van Rossum805365e2007-05-07 22:24:25 +00006/* 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
Guido van Rossum12d12c51993-10-26 17:58:25 +000013typedef struct {
Guido van Rossum805365e2007-05-07 22:24:25 +000014 PyObject_HEAD
15 PyObject *start;
16 PyObject *stop;
17 PyObject *step;
Nick Coghlan37ee8502010-12-03 14:26:13 +000018 PyObject *length;
Guido van Rossum12d12c51993-10-26 17:58:25 +000019} rangeobject;
20
Guido van Rossum805365e2007-05-07 22:24:25 +000021/* Helper function for validating step. Always returns a new reference or
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000022 NULL on error.
Guido van Rossum805365e2007-05-07 22:24:25 +000023*/
24static PyObject *
Benjamin Petersona1864f32010-11-20 23:05:39 +000025validate_step(PyObject *step)
26{
Guido van Rossum805365e2007-05-07 22:24:25 +000027 /* No step specified, use a step of 1. */
28 if (!step)
Christian Heimes217cfd12007-12-02 14:31:20 +000029 return PyLong_FromLong(1);
Guido van Rossum805365e2007-05-07 22:24:25 +000030
31 step = PyNumber_Index(step);
32 if (step) {
33 Py_ssize_t istep = PyNumber_AsSsize_t(step, NULL);
34 if (istep == -1 && PyErr_Occurred()) {
35 /* Ignore OverflowError, we know the value isn't 0. */
36 PyErr_Clear();
37 }
38 else if (istep == 0) {
39 PyErr_SetString(PyExc_ValueError,
40 "range() arg 3 must not be zero");
41 Py_CLEAR(step);
42 }
43 }
44
45 return step;
Raymond Hettingerc4c453f2002-06-05 23:12:45 +000046}
47
Nick Coghlan37ee8502010-12-03 14:26:13 +000048static PyObject *
49compute_range_length(PyObject *start, PyObject *stop, PyObject *step);
50
51static rangeobject *
52make_range_object(PyTypeObject *type, PyObject *start,
53 PyObject *stop, PyObject *step)
54{
55 rangeobject *obj = NULL;
56 PyObject *length;
57 length = compute_range_length(start, stop, step);
58 if (length == NULL) {
59 return NULL;
60 }
61 obj = PyObject_New(rangeobject, type);
62 if (obj == NULL) {
63 Py_DECREF(length);
64 return NULL;
65 }
66 obj->start = start;
67 obj->stop = stop;
68 obj->step = step;
69 obj->length = length;
70 return obj;
71}
72
Guido van Rossum805365e2007-05-07 22:24:25 +000073/* 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*/
Raymond Hettingerc4c453f2002-06-05 23:12:45 +000078static PyObject *
Benjamin Petersona1864f32010-11-20 23:05:39 +000079range_new(PyTypeObject *type, PyObject *args, PyObject *kw)
80{
Nick Coghlan37ee8502010-12-03 14:26:13 +000081 rangeobject *obj;
Guido van Rossum805365e2007-05-07 22:24:25 +000082 PyObject *start = NULL, *stop = NULL, *step = NULL;
Raymond Hettingerc4c453f2002-06-05 23:12:45 +000083
Guido van Rossum805365e2007-05-07 22:24:25 +000084 if (!_PyArg_NoKeywords("range()", kw))
85 return NULL;
Georg Brandl02c42872005-08-26 06:42:30 +000086
Guido van Rossum805365e2007-05-07 22:24:25 +000087 if (PyTuple_Size(args) <= 1) {
88 if (!PyArg_UnpackTuple(args, "range", 1, 1, &stop))
Raymond Hettinger94f55832009-06-12 18:40:16 +000089 return NULL;
Guido van Rossum805365e2007-05-07 22:24:25 +000090 stop = PyNumber_Index(stop);
91 if (!stop)
Raymond Hettinger94f55832009-06-12 18:40:16 +000092 return NULL;
Christian Heimes217cfd12007-12-02 14:31:20 +000093 start = PyLong_FromLong(0);
Raymond Hettinger94f55832009-06-12 18:40:16 +000094 if (!start) {
95 Py_DECREF(stop);
96 return NULL;
97 }
Christian Heimes217cfd12007-12-02 14:31:20 +000098 step = PyLong_FromLong(1);
Raymond Hettinger94f55832009-06-12 18:40:16 +000099 if (!step) {
100 Py_DECREF(stop);
101 Py_DECREF(start);
102 return NULL;
103 }
Guido van Rossum805365e2007-05-07 22:24:25 +0000104 }
105 else {
106 if (!PyArg_UnpackTuple(args, "range", 2, 3,
107 &start, &stop, &step))
Raymond Hettinger94f55832009-06-12 18:40:16 +0000108 return NULL;
Tim Petersfeec4532004-08-08 07:17:39 +0000109
Guido van Rossum805365e2007-05-07 22:24:25 +0000110 /* Convert borrowed refs to owned refs */
111 start = PyNumber_Index(start);
Raymond Hettinger94f55832009-06-12 18:40:16 +0000112 if (!start)
113 return NULL;
Guido van Rossum805365e2007-05-07 22:24:25 +0000114 stop = PyNumber_Index(stop);
Raymond Hettinger94f55832009-06-12 18:40:16 +0000115 if (!stop) {
116 Py_DECREF(start);
117 return NULL;
118 }
119 step = validate_step(step); /* Caution, this can clear exceptions */
120 if (!step) {
121 Py_DECREF(start);
122 Py_DECREF(stop);
123 return NULL;
124 }
Guido van Rossum805365e2007-05-07 22:24:25 +0000125 }
126
Nick Coghlan37ee8502010-12-03 14:26:13 +0000127 obj = make_range_object(type, start, stop, step);
128 if (obj != NULL)
129 return (PyObject *) obj;
Guido van Rossum805365e2007-05-07 22:24:25 +0000130
Nick Coghlan37ee8502010-12-03 14:26:13 +0000131 /* Failed to create object, release attributes */
Guido van Rossum805365e2007-05-07 22:24:25 +0000132 Py_XDECREF(start);
133 Py_XDECREF(stop);
134 Py_XDECREF(step);
135 return NULL;
Raymond Hettingerc4c453f2002-06-05 23:12:45 +0000136}
137
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000138PyDoc_STRVAR(range_doc,
Chris Jerdonek83fe2e12012-10-07 14:48:36 -0700139"range(stop) -> range object\n\
140range(start, stop[, step]) -> range object\n\
Raymond Hettingerc4c453f2002-06-05 23:12:45 +0000141\n\
Ezio Melotti5792ce12013-10-06 00:36:45 +0300142Return a virtual sequence of numbers from start to stop by step.");
Raymond Hettingerc4c453f2002-06-05 23:12:45 +0000143
Guido van Rossum805365e2007-05-07 22:24:25 +0000144static void
Benjamin Petersona1864f32010-11-20 23:05:39 +0000145range_dealloc(rangeobject *r)
146{
Guido van Rossum805365e2007-05-07 22:24:25 +0000147 Py_DECREF(r->start);
148 Py_DECREF(r->stop);
149 Py_DECREF(r->step);
Nick Coghlan37ee8502010-12-03 14:26:13 +0000150 Py_DECREF(r->length);
Amaury Forgeot d'Arcb7f17e42007-11-15 20:52:21 +0000151 PyObject_Del(r);
Guido van Rossum805365e2007-05-07 22:24:25 +0000152}
153
Mark Dickinson732166d2009-06-28 22:08:40 +0000154/* Return number of items in range (lo, hi, step) as a PyLong object,
155 * when arguments are PyLong objects. Arguments MUST return 1 with
156 * PyLong_Check(). Return NULL when there is an error.
Guido van Rossum805365e2007-05-07 22:24:25 +0000157 */
158static PyObject*
Nick Coghlan37ee8502010-12-03 14:26:13 +0000159compute_range_length(PyObject *start, PyObject *stop, PyObject *step)
Benjamin Petersona1864f32010-11-20 23:05:39 +0000160{
Guido van Rossum805365e2007-05-07 22:24:25 +0000161 /* -------------------------------------------------------------
162 Algorithm is equal to that of get_len_of_range(), but it operates
Benjamin Petersona47af9c2009-06-24 21:14:38 +0000163 on PyObjects (which are assumed to be PyLong objects).
Guido van Rossum805365e2007-05-07 22:24:25 +0000164 ---------------------------------------------------------------*/
Mark Dickinson211c6252009-02-01 10:28:51 +0000165 int cmp_result;
Guido van Rossum805365e2007-05-07 22:24:25 +0000166 PyObject *lo, *hi;
Guido van Rossum805365e2007-05-07 22:24:25 +0000167 PyObject *diff = NULL;
168 PyObject *one = NULL;
169 PyObject *tmp1 = NULL, *tmp2 = NULL, *result;
170 /* holds sub-expression evaluations */
171
172 PyObject *zero = PyLong_FromLong(0);
173 if (zero == NULL)
174 return NULL;
Nick Coghlan37ee8502010-12-03 14:26:13 +0000175 cmp_result = PyObject_RichCompareBool(step, zero, Py_GT);
Guido van Rossum805365e2007-05-07 22:24:25 +0000176 Py_DECREF(zero);
Mark Dickinson211c6252009-02-01 10:28:51 +0000177 if (cmp_result == -1)
Guido van Rossum805365e2007-05-07 22:24:25 +0000178 return NULL;
179
Mark Dickinson211c6252009-02-01 10:28:51 +0000180 if (cmp_result == 1) {
Nick Coghlan37ee8502010-12-03 14:26:13 +0000181 lo = start;
182 hi = stop;
Guido van Rossum805365e2007-05-07 22:24:25 +0000183 Py_INCREF(step);
184 } else {
Nick Coghlan37ee8502010-12-03 14:26:13 +0000185 lo = stop;
186 hi = start;
187 step = PyNumber_Negative(step);
Guido van Rossum805365e2007-05-07 22:24:25 +0000188 if (!step)
189 return NULL;
190 }
191
192 /* if (lo >= hi), return length of 0. */
Mark Dickinson211c6252009-02-01 10:28:51 +0000193 if (PyObject_RichCompareBool(lo, hi, Py_GE) == 1) {
Guido van Rossum805365e2007-05-07 22:24:25 +0000194 Py_XDECREF(step);
195 return PyLong_FromLong(0);
196 }
197
198 if ((one = PyLong_FromLong(1L)) == NULL)
199 goto Fail;
200
201 if ((tmp1 = PyNumber_Subtract(hi, lo)) == NULL)
202 goto Fail;
203
204 if ((diff = PyNumber_Subtract(tmp1, one)) == NULL)
205 goto Fail;
206
207 if ((tmp2 = PyNumber_FloorDivide(diff, step)) == NULL)
208 goto Fail;
209
210 if ((result = PyNumber_Add(tmp2, one)) == NULL)
211 goto Fail;
212
213 Py_DECREF(tmp2);
214 Py_DECREF(diff);
215 Py_DECREF(step);
216 Py_DECREF(tmp1);
217 Py_DECREF(one);
218 return result;
219
220 Fail:
221 Py_XDECREF(tmp2);
222 Py_XDECREF(diff);
223 Py_XDECREF(step);
224 Py_XDECREF(tmp1);
225 Py_XDECREF(one);
226 return NULL;
Guido van Rossum12d12c51993-10-26 17:58:25 +0000227}
228
Martin v. Löwis18e16552006-02-15 17:27:45 +0000229static Py_ssize_t
Benjamin Petersona1864f32010-11-20 23:05:39 +0000230range_length(rangeobject *r)
231{
Nick Coghlan37ee8502010-12-03 14:26:13 +0000232 return PyLong_AsSsize_t(r->length);
Guido van Rossum805365e2007-05-07 22:24:25 +0000233}
234
Guido van Rossum805365e2007-05-07 22:24:25 +0000235static PyObject *
Nick Coghlane993b102011-01-12 03:15:52 +0000236compute_item(rangeobject *r, PyObject *i)
Benjamin Petersona1864f32010-11-20 23:05:39 +0000237{
Nick Coghlane993b102011-01-12 03:15:52 +0000238 PyObject *incr, *result;
239 /* PyLong equivalent to:
240 * return r->start + (i * r->step)
241 */
242 incr = PyNumber_Multiply(i, r->step);
Guido van Rossum805365e2007-05-07 22:24:25 +0000243 if (!incr)
244 return NULL;
245 result = PyNumber_Add(r->start, incr);
246 Py_DECREF(incr);
247 return result;
Guido van Rossum7d6aa511993-12-21 22:50:31 +0000248}
249
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000250static PyObject *
Nick Coghlane993b102011-01-12 03:15:52 +0000251compute_range_item(rangeobject *r, PyObject *arg)
Benjamin Petersona1864f32010-11-20 23:05:39 +0000252{
Nick Coghlane993b102011-01-12 03:15:52 +0000253 int cmp_result;
254 PyObject *i, *result;
Tim Petersd976ab72004-08-08 06:29:10 +0000255
Nick Coghlane993b102011-01-12 03:15:52 +0000256 PyObject *zero = PyLong_FromLong(0);
257 if (zero == NULL)
258 return NULL;
Nick Coghlan37ee8502010-12-03 14:26:13 +0000259
Nick Coghlane993b102011-01-12 03:15:52 +0000260 /* PyLong equivalent to:
261 * if (arg < 0) {
262 * i = r->length + arg
263 * } else {
264 * i = arg
265 * }
266 */
267 cmp_result = PyObject_RichCompareBool(arg, zero, Py_LT);
268 if (cmp_result == -1) {
269 Py_DECREF(zero);
Nick Coghlan37ee8502010-12-03 14:26:13 +0000270 return NULL;
Guido van Rossum805365e2007-05-07 22:24:25 +0000271 }
Nick Coghlane993b102011-01-12 03:15:52 +0000272 if (cmp_result == 1) {
273 i = PyNumber_Add(r->length, arg);
274 if (!i) {
275 Py_DECREF(zero);
276 return NULL;
277 }
278 } else {
279 i = arg;
280 Py_INCREF(i);
281 }
282
283 /* PyLong equivalent to:
284 * if (i < 0 || i >= r->length) {
285 * <report index out of bounds>
286 * }
287 */
288 cmp_result = PyObject_RichCompareBool(i, zero, Py_LT);
289 Py_DECREF(zero);
290 if (cmp_result == 0) {
291 cmp_result = PyObject_RichCompareBool(i, r->length, Py_GE);
292 }
293 if (cmp_result == -1) {
294 Py_DECREF(i);
295 return NULL;
296 }
297 if (cmp_result == 1) {
298 Py_DECREF(i);
299 PyErr_SetString(PyExc_IndexError,
300 "range object index out of range");
301 return NULL;
302 }
303
304 result = compute_item(r, i);
305 Py_DECREF(i);
306 return result;
307}
308
309static PyObject *
310range_item(rangeobject *r, Py_ssize_t i)
311{
Antoine Pitroua103b962012-05-16 14:37:54 +0200312 PyObject *res, *arg = PyLong_FromSsize_t(i);
Nick Coghlane993b102011-01-12 03:15:52 +0000313 if (!arg) {
314 return NULL;
315 }
Benjamin Peterson547d4852011-01-13 04:22:54 +0000316 res = compute_range_item(r, arg);
317 Py_DECREF(arg);
318 return res;
Nick Coghlane993b102011-01-12 03:15:52 +0000319}
320
Nick Coghlane993b102011-01-12 03:15:52 +0000321static PyObject *
322compute_slice(rangeobject *r, PyObject *_slice)
323{
324 PySliceObject *slice = (PySliceObject *) _slice;
325 rangeobject *result;
326 PyObject *start = NULL, *stop = NULL, *step = NULL;
327 PyObject *substart = NULL, *substop = NULL, *substep = NULL;
Mark Dickinsonffdb2c22012-11-17 19:18:10 +0000328 int error;
Nick Coghlane993b102011-01-12 03:15:52 +0000329
Mark Dickinsonffdb2c22012-11-17 19:18:10 +0000330 error = _PySlice_GetLongIndices(slice, r->length, &start, &stop, &step);
331 if (error == -1)
332 return NULL;
Nick Coghlane993b102011-01-12 03:15:52 +0000333
334 substep = PyNumber_Multiply(r->step, step);
335 if (substep == NULL) goto fail;
336 Py_CLEAR(step);
337
338 substart = compute_item(r, start);
339 if (substart == NULL) goto fail;
340 Py_CLEAR(start);
341
Mark Dickinsonffdb2c22012-11-17 19:18:10 +0000342 substop = compute_item(r, stop);
343 if (substop == NULL) goto fail;
Nick Coghlane993b102011-01-12 03:15:52 +0000344 Py_CLEAR(stop);
345
346 result = make_range_object(Py_TYPE(r), substart, substop, substep);
347 if (result != NULL) {
348 return (PyObject *) result;
349 }
350fail:
351 Py_XDECREF(start);
352 Py_XDECREF(stop);
353 Py_XDECREF(step);
354 Py_XDECREF(substart);
355 Py_XDECREF(substop);
356 Py_XDECREF(substep);
357 return NULL;
Alexandre Vassalotti75056072008-06-10 04:03:04 +0000358}
359
Daniel Stutzbach9f0cbf12010-09-13 21:16:29 +0000360/* Assumes (PyLong_CheckExact(ob) || PyBool_Check(ob)) */
361static int
Benjamin Petersona1864f32010-11-20 23:05:39 +0000362range_contains_long(rangeobject *r, PyObject *ob)
363{
Daniel Stutzbach9f0cbf12010-09-13 21:16:29 +0000364 int cmp1, cmp2, cmp3;
365 PyObject *tmp1 = NULL;
366 PyObject *tmp2 = NULL;
367 PyObject *zero = NULL;
368 int result = -1;
369
370 zero = PyLong_FromLong(0);
371 if (zero == NULL) /* MemoryError in int(0) */
372 goto end;
373
374 /* Check if the value can possibly be in the range. */
375
376 cmp1 = PyObject_RichCompareBool(r->step, zero, Py_GT);
377 if (cmp1 == -1)
378 goto end;
379 if (cmp1 == 1) { /* positive steps: start <= ob < stop */
380 cmp2 = PyObject_RichCompareBool(r->start, ob, Py_LE);
381 cmp3 = PyObject_RichCompareBool(ob, r->stop, Py_LT);
382 }
383 else { /* negative steps: stop < ob <= start */
384 cmp2 = PyObject_RichCompareBool(ob, r->start, Py_LE);
385 cmp3 = PyObject_RichCompareBool(r->stop, ob, Py_LT);
386 }
387
388 if (cmp2 == -1 || cmp3 == -1) /* TypeError */
389 goto end;
390 if (cmp2 == 0 || cmp3 == 0) { /* ob outside of range */
391 result = 0;
392 goto end;
393 }
394
395 /* Check that the stride does not invalidate ob's membership. */
396 tmp1 = PyNumber_Subtract(ob, r->start);
397 if (tmp1 == NULL)
398 goto end;
399 tmp2 = PyNumber_Remainder(tmp1, r->step);
400 if (tmp2 == NULL)
401 goto end;
402 /* result = (int(ob) - start % step) == 0 */
403 result = PyObject_RichCompareBool(tmp2, zero, Py_EQ);
404 end:
405 Py_XDECREF(tmp1);
406 Py_XDECREF(tmp2);
407 Py_XDECREF(zero);
408 return result;
409}
410
Mark Dickinson3e124ae2009-09-22 21:47:24 +0000411static int
Benjamin Petersona1864f32010-11-20 23:05:39 +0000412range_contains(rangeobject *r, PyObject *ob)
413{
Daniel Stutzbach9f0cbf12010-09-13 21:16:29 +0000414 if (PyLong_CheckExact(ob) || PyBool_Check(ob))
415 return range_contains_long(r, ob);
Mark Dickinson3e124ae2009-09-22 21:47:24 +0000416
Mark Dickinson3e124ae2009-09-22 21:47:24 +0000417 return (int)_PySequence_IterSearch((PyObject*)r, ob,
418 PY_ITERSEARCH_CONTAINS);
419}
420
Mark Dickinson36645682011-10-23 19:53:01 +0100421/* Compare two range objects. Return 1 for equal, 0 for not equal
422 and -1 on error. The algorithm is roughly the C equivalent of
423
424 if r0 is r1:
425 return True
426 if len(r0) != len(r1):
427 return False
428 if not len(r0):
429 return True
430 if r0.start != r1.start:
431 return False
432 if len(r0) == 1:
433 return True
434 return r0.step == r1.step
435*/
436static int
437range_equals(rangeobject *r0, rangeobject *r1)
438{
439 int cmp_result;
440 PyObject *one;
441
442 if (r0 == r1)
443 return 1;
444 cmp_result = PyObject_RichCompareBool(r0->length, r1->length, Py_EQ);
445 /* Return False or error to the caller. */
446 if (cmp_result != 1)
447 return cmp_result;
448 cmp_result = PyObject_Not(r0->length);
449 /* Return True or error to the caller. */
450 if (cmp_result != 0)
451 return cmp_result;
452 cmp_result = PyObject_RichCompareBool(r0->start, r1->start, Py_EQ);
453 /* Return False or error to the caller. */
454 if (cmp_result != 1)
455 return cmp_result;
456 one = PyLong_FromLong(1);
457 if (!one)
458 return -1;
459 cmp_result = PyObject_RichCompareBool(r0->length, one, Py_EQ);
460 Py_DECREF(one);
461 /* Return True or error to the caller. */
462 if (cmp_result != 0)
463 return cmp_result;
464 return PyObject_RichCompareBool(r0->step, r1->step, Py_EQ);
465}
466
467static PyObject *
468range_richcompare(PyObject *self, PyObject *other, int op)
469{
470 int result;
471
472 if (!PyRange_Check(other))
473 Py_RETURN_NOTIMPLEMENTED;
474 switch (op) {
475 case Py_NE:
476 case Py_EQ:
477 result = range_equals((rangeobject*)self, (rangeobject*)other);
478 if (result == -1)
479 return NULL;
480 if (op == Py_NE)
481 result = !result;
482 if (result)
483 Py_RETURN_TRUE;
484 else
485 Py_RETURN_FALSE;
486 case Py_LE:
487 case Py_GE:
488 case Py_LT:
489 case Py_GT:
490 Py_RETURN_NOTIMPLEMENTED;
491 default:
492 PyErr_BadArgument();
493 return NULL;
494 }
495}
496
497/* Hash function for range objects. Rough C equivalent of
498
499 if not len(r):
500 return hash((len(r), None, None))
501 if len(r) == 1:
502 return hash((len(r), r.start, None))
503 return hash((len(r), r.start, r.step))
504*/
505static Py_hash_t
506range_hash(rangeobject *r)
507{
508 PyObject *t;
509 Py_hash_t result = -1;
510 int cmp_result;
511
512 t = PyTuple_New(3);
513 if (!t)
514 return -1;
515 Py_INCREF(r->length);
516 PyTuple_SET_ITEM(t, 0, r->length);
517 cmp_result = PyObject_Not(r->length);
518 if (cmp_result == -1)
519 goto end;
520 if (cmp_result == 1) {
521 Py_INCREF(Py_None);
522 Py_INCREF(Py_None);
523 PyTuple_SET_ITEM(t, 1, Py_None);
524 PyTuple_SET_ITEM(t, 2, Py_None);
525 }
526 else {
527 PyObject *one;
528 Py_INCREF(r->start);
529 PyTuple_SET_ITEM(t, 1, r->start);
530 one = PyLong_FromLong(1);
531 if (!one)
532 goto end;
533 cmp_result = PyObject_RichCompareBool(r->length, one, Py_EQ);
534 Py_DECREF(one);
535 if (cmp_result == -1)
536 goto end;
537 if (cmp_result == 1) {
538 Py_INCREF(Py_None);
539 PyTuple_SET_ITEM(t, 2, Py_None);
540 }
541 else {
542 Py_INCREF(r->step);
543 PyTuple_SET_ITEM(t, 2, r->step);
544 }
545 }
546 result = PyObject_Hash(t);
547 end:
548 Py_DECREF(t);
549 return result;
550}
551
Daniel Stutzbach9f0cbf12010-09-13 21:16:29 +0000552static PyObject *
Benjamin Petersona1864f32010-11-20 23:05:39 +0000553range_count(rangeobject *r, PyObject *ob)
554{
Daniel Stutzbach9f0cbf12010-09-13 21:16:29 +0000555 if (PyLong_CheckExact(ob) || PyBool_Check(ob)) {
Georg Brandl7e5343b2010-11-20 22:40:10 +0000556 int result = range_contains_long(r, ob);
557 if (result == -1)
558 return NULL;
559 else if (result)
Benjamin Peterson0b458d52010-11-20 22:35:41 +0000560 return PyLong_FromLong(1);
Daniel Stutzbach9f0cbf12010-09-13 21:16:29 +0000561 else
Benjamin Peterson0b458d52010-11-20 22:35:41 +0000562 return PyLong_FromLong(0);
Daniel Stutzbach9f0cbf12010-09-13 21:16:29 +0000563 } else {
564 Py_ssize_t count;
565 count = _PySequence_IterSearch((PyObject*)r, ob, PY_ITERSEARCH_COUNT);
566 if (count == -1)
567 return NULL;
568 return PyLong_FromSsize_t(count);
569 }
570}
571
572static PyObject *
Benjamin Petersona1864f32010-11-20 23:05:39 +0000573range_index(rangeobject *r, PyObject *ob)
574{
Daniel Stutzbach9f0cbf12010-09-13 21:16:29 +0000575 int contains;
Daniel Stutzbach9f0cbf12010-09-13 21:16:29 +0000576
577 if (!PyLong_CheckExact(ob) && !PyBool_Check(ob)) {
578 Py_ssize_t index;
579 index = _PySequence_IterSearch((PyObject*)r, ob, PY_ITERSEARCH_INDEX);
580 if (index == -1)
581 return NULL;
582 return PyLong_FromSsize_t(index);
583 }
584
585 contains = range_contains_long(r, ob);
586 if (contains == -1)
587 return NULL;
588
Benjamin Peterson155614b2010-11-20 22:44:32 +0000589 if (contains) {
590 PyObject *idx, *tmp = PyNumber_Subtract(ob, r->start);
591 if (tmp == NULL)
592 return NULL;
593 /* idx = (ob - r.start) // r.step */
594 idx = PyNumber_FloorDivide(tmp, r->step);
595 Py_DECREF(tmp);
596 return idx;
597 }
Daniel Stutzbach9f0cbf12010-09-13 21:16:29 +0000598
599 /* object is not in the range */
Benjamin Peterson155614b2010-11-20 22:44:32 +0000600 PyErr_Format(PyExc_ValueError, "%R is not in range", ob);
Daniel Stutzbach9f0cbf12010-09-13 21:16:29 +0000601 return NULL;
602}
603
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000604static PySequenceMethods range_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000605 (lenfunc)range_length, /* sq_length */
Nick Coghlan37ee8502010-12-03 14:26:13 +0000606 0, /* sq_concat */
607 0, /* sq_repeat */
608 (ssizeargfunc)range_item, /* sq_item */
609 0, /* sq_slice */
610 0, /* sq_ass_item */
611 0, /* sq_ass_slice */
Mark Dickinson3e124ae2009-09-22 21:47:24 +0000612 (objobjproc)range_contains, /* sq_contains */
Guido van Rossum12d12c51993-10-26 17:58:25 +0000613};
614
Nick Coghlan37ee8502010-12-03 14:26:13 +0000615static PyObject *
616range_repr(rangeobject *r)
617{
618 Py_ssize_t istep;
619
620 /* Check for special case values for printing. We don't always
621 need the step value. We don't care about errors
622 (it means overflow), so clear the errors. */
623 istep = PyNumber_AsSsize_t(r->step, NULL);
624 if (istep != 1 || (istep == -1 && PyErr_Occurred())) {
625 PyErr_Clear();
626 }
627
628 if (istep == 1)
629 return PyUnicode_FromFormat("range(%R, %R)", r->start, r->stop);
630 else
631 return PyUnicode_FromFormat("range(%R, %R, %R)",
632 r->start, r->stop, r->step);
633}
634
635/* Pickling support */
636static PyObject *
637range_reduce(rangeobject *r, PyObject *args)
638{
639 return Py_BuildValue("(O(OOO))", Py_TYPE(r),
640 r->start, r->stop, r->step);
641}
642
643static PyObject *
644range_subscript(rangeobject* self, PyObject* item)
645{
646 if (PyIndex_Check(item)) {
Nick Coghlane993b102011-01-12 03:15:52 +0000647 PyObject *i, *result;
648 i = PyNumber_Index(item);
649 if (!i)
Nick Coghlan37ee8502010-12-03 14:26:13 +0000650 return NULL;
Nick Coghlane993b102011-01-12 03:15:52 +0000651 result = compute_range_item(self, i);
652 Py_DECREF(i);
653 return result;
Nick Coghlan37ee8502010-12-03 14:26:13 +0000654 }
655 if (PySlice_Check(item)) {
Nick Coghlane993b102011-01-12 03:15:52 +0000656 return compute_slice(self, item);
Nick Coghlan37ee8502010-12-03 14:26:13 +0000657 }
658 PyErr_Format(PyExc_TypeError,
659 "range indices must be integers or slices, not %.200s",
660 item->ob_type->tp_name);
661 return NULL;
662}
663
664
665static PyMappingMethods range_as_mapping = {
666 (lenfunc)range_length, /* mp_length */
667 (binaryfunc)range_subscript, /* mp_subscript */
668 (objobjargproc)0, /* mp_ass_subscript */
669};
670
Jeremy Hylton938ace62002-07-17 16:30:39 +0000671static PyObject * range_iter(PyObject *seq);
Raymond Hettinger85c20a42003-11-06 14:06:48 +0000672static PyObject * range_reverse(PyObject *seq);
673
674PyDoc_STRVAR(reverse_doc,
Ezio Melotti5792ce12013-10-06 00:36:45 +0300675"Return a reverse iterator.");
Raymond Hettinger85c20a42003-11-06 14:06:48 +0000676
Daniel Stutzbach9f0cbf12010-09-13 21:16:29 +0000677PyDoc_STRVAR(count_doc,
678"rangeobject.count(value) -> integer -- return number of occurrences of value");
679
680PyDoc_STRVAR(index_doc,
681"rangeobject.index(value, [start, [stop]]) -> integer -- return index of value.\n"
Ezio Melotti5792ce12013-10-06 00:36:45 +0300682"Raise ValueError if the value is not present.");
Daniel Stutzbach9f0cbf12010-09-13 21:16:29 +0000683
Raymond Hettinger85c20a42003-11-06 14:06:48 +0000684static PyMethodDef range_methods[] = {
Daniel Stutzbach9f0cbf12010-09-13 21:16:29 +0000685 {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS, reverse_doc},
686 {"__reduce__", (PyCFunction)range_reduce, METH_VARARGS},
687 {"count", (PyCFunction)range_count, METH_O, count_doc},
688 {"index", (PyCFunction)range_index, METH_O, index_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000689 {NULL, NULL} /* sentinel */
Raymond Hettinger85c20a42003-11-06 14:06:48 +0000690};
Raymond Hettinger48165d42002-06-05 20:08:48 +0000691
Benjamin Peterson878ce382011-11-05 15:17:52 -0400692static PyMemberDef range_members[] = {
693 {"start", T_OBJECT_EX, offsetof(rangeobject, start), READONLY},
694 {"stop", T_OBJECT_EX, offsetof(rangeobject, stop), READONLY},
695 {"step", T_OBJECT_EX, offsetof(rangeobject, step), READONLY},
696 {0}
697};
698
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000699PyTypeObject PyRange_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000700 PyVarObject_HEAD_INIT(&PyType_Type, 0)
701 "range", /* Name of this type */
702 sizeof(rangeobject), /* Basic object size */
703 0, /* Item size for varobject */
704 (destructor)range_dealloc, /* tp_dealloc */
705 0, /* tp_print */
706 0, /* tp_getattr */
707 0, /* tp_setattr */
708 0, /* tp_reserved */
709 (reprfunc)range_repr, /* tp_repr */
710 0, /* tp_as_number */
711 &range_as_sequence, /* tp_as_sequence */
Nick Coghlan37ee8502010-12-03 14:26:13 +0000712 &range_as_mapping, /* tp_as_mapping */
Mark Dickinson36645682011-10-23 19:53:01 +0100713 (hashfunc)range_hash, /* tp_hash */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000714 0, /* tp_call */
715 0, /* tp_str */
716 PyObject_GenericGetAttr, /* tp_getattro */
717 0, /* tp_setattro */
718 0, /* tp_as_buffer */
719 Py_TPFLAGS_DEFAULT, /* tp_flags */
720 range_doc, /* tp_doc */
721 0, /* tp_traverse */
722 0, /* tp_clear */
Mark Dickinson36645682011-10-23 19:53:01 +0100723 range_richcompare, /* tp_richcompare */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000724 0, /* tp_weaklistoffset */
725 range_iter, /* tp_iter */
726 0, /* tp_iternext */
727 range_methods, /* tp_methods */
Benjamin Peterson878ce382011-11-05 15:17:52 -0400728 range_members, /* tp_members */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000729 0, /* tp_getset */
730 0, /* tp_base */
731 0, /* tp_dict */
732 0, /* tp_descr_get */
733 0, /* tp_descr_set */
734 0, /* tp_dictoffset */
735 0, /* tp_init */
736 0, /* tp_alloc */
737 range_new, /* tp_new */
Guido van Rossum12d12c51993-10-26 17:58:25 +0000738};
Raymond Hettinger48165d42002-06-05 20:08:48 +0000739
Walter Dörwald4ad94212007-05-21 18:01:17 +0000740/*********************** range Iterator **************************/
Raymond Hettinger48165d42002-06-05 20:08:48 +0000741
Guido van Rossum805365e2007-05-07 22:24:25 +0000742/* There are 2 types of iterators, one for C longs, the other for
Serhiy Storchaka95949422013-08-27 19:40:23 +0300743 Python ints (ie, PyObjects). This should make iteration fast
Guido van Rossum805365e2007-05-07 22:24:25 +0000744 in the normal case, but possible for any numeric value.
745*/
746
Raymond Hettinger48165d42002-06-05 20:08:48 +0000747typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000748 PyObject_HEAD
749 long index;
750 long start;
751 long step;
752 long len;
Raymond Hettinger48165d42002-06-05 20:08:48 +0000753} rangeiterobject;
754
Raymond Hettinger85c20a42003-11-06 14:06:48 +0000755static PyObject *
Benjamin Petersona1864f32010-11-20 23:05:39 +0000756rangeiter_next(rangeiterobject *r)
757{
Guido van Rossum805365e2007-05-07 22:24:25 +0000758 if (r->index < r->len)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000759 /* cast to unsigned to avoid possible signed overflow
Mark Dickinsonb43dbc22009-11-15 12:56:08 +0000760 in intermediate calculations. */
761 return PyLong_FromLong((long)(r->start +
762 (unsigned long)(r->index++) * r->step));
Guido van Rossum805365e2007-05-07 22:24:25 +0000763 return NULL;
Raymond Hettinger48165d42002-06-05 20:08:48 +0000764}
765
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000766static PyObject *
Benjamin Petersona1864f32010-11-20 23:05:39 +0000767rangeiter_len(rangeiterobject *r)
768{
Christian Heimes217cfd12007-12-02 14:31:20 +0000769 return PyLong_FromLong(r->len - r->index);
Raymond Hettingeref9bf402004-03-10 10:10:42 +0000770}
771
Guido van Rossum805365e2007-05-07 22:24:25 +0000772PyDoc_STRVAR(length_hint_doc,
773 "Private method returning an estimate of len(list(it)).");
Raymond Hettingeref9bf402004-03-10 10:10:42 +0000774
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000775static PyObject *
776rangeiter_reduce(rangeiterobject *r)
777{
778 PyObject *start=NULL, *stop=NULL, *step=NULL;
779 PyObject *range;
Chris Jerdonek042fa652012-10-07 14:56:27 -0700780
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000781 /* create a range object for pickling */
782 start = PyLong_FromLong(r->start);
783 if (start == NULL)
784 goto err;
785 stop = PyLong_FromLong(r->start + r->len * r->step);
786 if (stop == NULL)
787 goto err;
788 step = PyLong_FromLong(r->step);
789 if (step == NULL)
790 goto err;
791 range = (PyObject*)make_range_object(&PyRange_Type,
792 start, stop, step);
793 if (range == NULL)
794 goto err;
795 /* return the result */
Antoine Pitroua7013882012-04-05 00:04:20 +0200796 return Py_BuildValue("N(N)i", _PyObject_GetBuiltin("iter"), range, r->index);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000797err:
798 Py_XDECREF(start);
799 Py_XDECREF(stop);
800 Py_XDECREF(step);
801 return NULL;
802}
803
804static PyObject *
805rangeiter_setstate(rangeiterobject *r, PyObject *state)
806{
807 long index = PyLong_AsLong(state);
808 if (index == -1 && PyErr_Occurred())
809 return NULL;
Kristján Valur Jónsson25dded02014-03-05 13:47:57 +0000810 /* silently clip the index value */
811 if (index < 0)
812 index = 0;
813 else if (index > r->len)
814 index = r->len; /* exhausted iterator */
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000815 r->index = index;
816 Py_RETURN_NONE;
817}
818
819PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
820PyDoc_STRVAR(setstate_doc, "Set state information for unpickling.");
821
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000822static PyMethodDef rangeiter_methods[] = {
Guido van Rossum805365e2007-05-07 22:24:25 +0000823 {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000824 length_hint_doc},
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000825 {"__reduce__", (PyCFunction)rangeiter_reduce, METH_NOARGS,
826 reduce_doc},
827 {"__setstate__", (PyCFunction)rangeiter_setstate, METH_O,
828 setstate_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000829 {NULL, NULL} /* sentinel */
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000830};
Raymond Hettingeref9bf402004-03-10 10:10:42 +0000831
Nick Coghlan37ee8502010-12-03 14:26:13 +0000832static PyObject *rangeiter_new(PyTypeObject *, PyObject *args, PyObject *kw);
833
Christian Heimesa22e8bd2007-11-29 22:35:39 +0000834PyTypeObject PyRangeIter_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000835 PyVarObject_HEAD_INIT(&PyType_Type, 0)
836 "range_iterator", /* tp_name */
837 sizeof(rangeiterobject), /* tp_basicsize */
838 0, /* tp_itemsize */
839 /* methods */
840 (destructor)PyObject_Del, /* tp_dealloc */
841 0, /* tp_print */
842 0, /* tp_getattr */
843 0, /* tp_setattr */
844 0, /* tp_reserved */
845 0, /* tp_repr */
846 0, /* tp_as_number */
847 0, /* tp_as_sequence */
848 0, /* tp_as_mapping */
849 0, /* tp_hash */
850 0, /* tp_call */
851 0, /* tp_str */
852 PyObject_GenericGetAttr, /* tp_getattro */
853 0, /* tp_setattro */
854 0, /* tp_as_buffer */
855 Py_TPFLAGS_DEFAULT, /* tp_flags */
856 0, /* tp_doc */
857 0, /* tp_traverse */
858 0, /* tp_clear */
859 0, /* tp_richcompare */
860 0, /* tp_weaklistoffset */
861 PyObject_SelfIter, /* tp_iter */
862 (iternextfunc)rangeiter_next, /* tp_iternext */
863 rangeiter_methods, /* tp_methods */
864 0, /* tp_members */
865 0, /* tp_getset */
866 0, /* tp_base */
867 0, /* tp_dict */
868 0, /* tp_descr_get */
869 0, /* tp_descr_set */
870 0, /* tp_dictoffset */
871 0, /* tp_init */
872 0, /* tp_alloc */
873 rangeiter_new, /* tp_new */
Guido van Rossum805365e2007-05-07 22:24:25 +0000874};
875
Mark Dickinsond550c9a2009-11-15 09:57:26 +0000876/* Return number of items in range (lo, hi, step). step != 0
877 * required. The result always fits in an unsigned long.
Guido van Rossum805365e2007-05-07 22:24:25 +0000878 */
Mark Dickinsond550c9a2009-11-15 09:57:26 +0000879static unsigned long
Benjamin Petersona1864f32010-11-20 23:05:39 +0000880get_len_of_range(long lo, long hi, long step)
881{
Guido van Rossum805365e2007-05-07 22:24:25 +0000882 /* -------------------------------------------------------------
Mark Dickinsond550c9a2009-11-15 09:57:26 +0000883 If step > 0 and lo >= hi, or step < 0 and lo <= hi, the range is empty.
884 Else for step > 0, if n values are in the range, the last one is
Guido van Rossum805365e2007-05-07 22:24:25 +0000885 lo + (n-1)*step, which must be <= hi-1. Rearranging,
886 n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives
887 the proper value. Since lo < hi in this case, hi-lo-1 >= 0, so
888 the RHS is non-negative and so truncation is the same as the
889 floor. Letting M be the largest positive long, the worst case
890 for the RHS numerator is hi=M, lo=-M-1, and then
891 hi-lo-1 = M-(-M-1)-1 = 2*M. Therefore unsigned long has enough
Mark Dickinsond550c9a2009-11-15 09:57:26 +0000892 precision to compute the RHS exactly. The analysis for step < 0
893 is similar.
Guido van Rossum805365e2007-05-07 22:24:25 +0000894 ---------------------------------------------------------------*/
Mark Dickinsond550c9a2009-11-15 09:57:26 +0000895 assert(step != 0);
896 if (step > 0 && lo < hi)
897 return 1UL + (hi - 1UL - lo) / step;
898 else if (step < 0 && lo > hi)
899 return 1UL + (lo - 1UL - hi) / (0UL - step);
900 else
901 return 0UL;
Guido van Rossum805365e2007-05-07 22:24:25 +0000902}
903
Mark Dickinsond550c9a2009-11-15 09:57:26 +0000904/* Initialize a rangeiter object. If the length of the rangeiter object
905 is not representable as a C long, OverflowError is raised. */
906
Guido van Rossum805365e2007-05-07 22:24:25 +0000907static PyObject *
Nick Coghlan37ee8502010-12-03 14:26:13 +0000908fast_range_iter(long start, long stop, long step)
Benjamin Petersona1864f32010-11-20 23:05:39 +0000909{
Christian Heimesa22e8bd2007-11-29 22:35:39 +0000910 rangeiterobject *it = PyObject_New(rangeiterobject, &PyRangeIter_Type);
Mark Dickinsond550c9a2009-11-15 09:57:26 +0000911 unsigned long ulen;
Guido van Rossum805365e2007-05-07 22:24:25 +0000912 if (it == NULL)
913 return NULL;
914 it->start = start;
915 it->step = step;
Mark Dickinsond550c9a2009-11-15 09:57:26 +0000916 ulen = get_len_of_range(start, stop, step);
917 if (ulen > (unsigned long)LONG_MAX) {
Benjamin Peterson36fbb732009-11-16 00:34:25 +0000918 Py_DECREF(it);
Mark Dickinsond550c9a2009-11-15 09:57:26 +0000919 PyErr_SetString(PyExc_OverflowError,
920 "range too large to represent as a range_iterator");
921 return NULL;
922 }
923 it->len = (long)ulen;
Guido van Rossum805365e2007-05-07 22:24:25 +0000924 it->index = 0;
925 return (PyObject *)it;
926}
927
928static PyObject *
Benjamin Petersona1864f32010-11-20 23:05:39 +0000929rangeiter_new(PyTypeObject *type, PyObject *args, PyObject *kw)
930{
Guido van Rossum805365e2007-05-07 22:24:25 +0000931 long start, stop, step;
932
933 if (!_PyArg_NoKeywords("rangeiter()", kw))
934 return NULL;
935
936 if (!PyArg_ParseTuple(args, "lll;rangeiter() requires 3 int arguments",
937 &start, &stop, &step))
938 return NULL;
939
Nick Coghlan37ee8502010-12-03 14:26:13 +0000940 return fast_range_iter(start, stop, step);
941}
942
943typedef struct {
944 PyObject_HEAD
945 PyObject *index;
946 PyObject *start;
947 PyObject *step;
948 PyObject *len;
949} longrangeiterobject;
950
951static PyObject *
952longrangeiter_len(longrangeiterobject *r, PyObject *no_args)
953{
954 return PyNumber_Subtract(r->len, r->index);
Guido van Rossum805365e2007-05-07 22:24:25 +0000955}
956
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000957static PyObject *
958longrangeiter_reduce(longrangeiterobject *r)
959{
960 PyObject *product, *stop=NULL;
961 PyObject *range;
962
963 /* create a range object for pickling. Must calculate the "stop" value */
964 product = PyNumber_Multiply(r->len, r->step);
965 if (product == NULL)
966 return NULL;
967 stop = PyNumber_Add(r->start, product);
968 Py_DECREF(product);
969 if (stop == NULL)
970 return NULL;
971 Py_INCREF(r->start);
972 Py_INCREF(r->step);
973 range = (PyObject*)make_range_object(&PyRange_Type,
974 r->start, stop, r->step);
975 if (range == NULL) {
976 Py_DECREF(r->start);
977 Py_DECREF(stop);
978 Py_DECREF(r->step);
979 return NULL;
980 }
981
982 /* return the result */
Antoine Pitroua7013882012-04-05 00:04:20 +0200983 return Py_BuildValue("N(N)O", _PyObject_GetBuiltin("iter"), range, r->index);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000984}
985
986static PyObject *
987longrangeiter_setstate(longrangeiterobject *r, PyObject *state)
988{
Kristján Valur Jónsson25dded02014-03-05 13:47:57 +0000989 int cmp;
990
991 /* clip the value */
992 PyObject *zero = PyLong_FromLong(0);
993 if (zero == NULL)
994 return NULL;
995 cmp = PyObject_RichCompareBool(state, zero, Py_LT);
996 if (cmp > 0) {
997 Py_CLEAR(r->index);
998 r->index = zero;
999 Py_RETURN_NONE;
1000 }
1001 Py_DECREF(zero);
1002 if (cmp < 0)
1003 return NULL;
1004
1005 cmp = PyObject_RichCompareBool(r->len, state, Py_LT);
1006 if (cmp < 0)
1007 return NULL;
1008 if (cmp > 0)
1009 state = r->len;
1010
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001011 Py_CLEAR(r->index);
1012 r->index = state;
1013 Py_INCREF(r->index);
1014 Py_RETURN_NONE;
1015}
1016
Guido van Rossum805365e2007-05-07 22:24:25 +00001017static PyMethodDef longrangeiter_methods[] = {
1018 {"__length_hint__", (PyCFunction)longrangeiter_len, METH_NOARGS,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001019 length_hint_doc},
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001020 {"__reduce__", (PyCFunction)longrangeiter_reduce, METH_NOARGS,
1021 reduce_doc},
1022 {"__setstate__", (PyCFunction)longrangeiter_setstate, METH_O,
1023 setstate_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001024 {NULL, NULL} /* sentinel */
Guido van Rossum805365e2007-05-07 22:24:25 +00001025};
1026
1027static void
Benjamin Petersona1864f32010-11-20 23:05:39 +00001028longrangeiter_dealloc(longrangeiterobject *r)
1029{
Guido van Rossum805365e2007-05-07 22:24:25 +00001030 Py_XDECREF(r->index);
Guido van Rossum317e7742007-05-08 15:18:31 +00001031 Py_XDECREF(r->start);
1032 Py_XDECREF(r->step);
1033 Py_XDECREF(r->len);
Amaury Forgeot d'Arcb7f17e42007-11-15 20:52:21 +00001034 PyObject_Del(r);
Guido van Rossum805365e2007-05-07 22:24:25 +00001035}
1036
1037static PyObject *
Benjamin Petersona1864f32010-11-20 23:05:39 +00001038longrangeiter_next(longrangeiterobject *r)
1039{
Guido van Rossum805365e2007-05-07 22:24:25 +00001040 PyObject *one, *product, *new_index, *result;
1041 if (PyObject_RichCompareBool(r->index, r->len, Py_LT) != 1)
1042 return NULL;
1043
1044 one = PyLong_FromLong(1);
1045 if (!one)
1046 return NULL;
1047
Guido van Rossum805365e2007-05-07 22:24:25 +00001048 new_index = PyNumber_Add(r->index, one);
1049 Py_DECREF(one);
Benjamin Peterson36fbb732009-11-16 00:34:25 +00001050 if (!new_index)
1051 return NULL;
1052
1053 product = PyNumber_Multiply(r->index, r->step);
1054 if (!product) {
1055 Py_DECREF(new_index);
Guido van Rossum805365e2007-05-07 22:24:25 +00001056 return NULL;
1057 }
1058
1059 result = PyNumber_Add(r->start, product);
1060 Py_DECREF(product);
1061 if (result) {
1062 Py_DECREF(r->index);
1063 r->index = new_index;
1064 }
Benjamin Peterson36fbb732009-11-16 00:34:25 +00001065 else {
1066 Py_DECREF(new_index);
1067 }
Guido van Rossum805365e2007-05-07 22:24:25 +00001068
1069 return result;
1070}
1071
Christian Heimesa22e8bd2007-11-29 22:35:39 +00001072PyTypeObject PyLongRangeIter_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001073 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1074 "longrange_iterator", /* tp_name */
1075 sizeof(longrangeiterobject), /* tp_basicsize */
1076 0, /* tp_itemsize */
1077 /* methods */
1078 (destructor)longrangeiter_dealloc, /* tp_dealloc */
1079 0, /* tp_print */
1080 0, /* tp_getattr */
1081 0, /* tp_setattr */
1082 0, /* tp_reserved */
1083 0, /* tp_repr */
1084 0, /* tp_as_number */
1085 0, /* tp_as_sequence */
1086 0, /* tp_as_mapping */
1087 0, /* tp_hash */
1088 0, /* tp_call */
1089 0, /* tp_str */
1090 PyObject_GenericGetAttr, /* tp_getattro */
1091 0, /* tp_setattro */
1092 0, /* tp_as_buffer */
1093 Py_TPFLAGS_DEFAULT, /* tp_flags */
1094 0, /* tp_doc */
1095 0, /* tp_traverse */
1096 0, /* tp_clear */
1097 0, /* tp_richcompare */
1098 0, /* tp_weaklistoffset */
1099 PyObject_SelfIter, /* tp_iter */
1100 (iternextfunc)longrangeiter_next, /* tp_iternext */
1101 longrangeiter_methods, /* tp_methods */
1102 0,
Raymond Hettinger48165d42002-06-05 20:08:48 +00001103};
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001104
1105static PyObject *
Benjamin Petersona1864f32010-11-20 23:05:39 +00001106range_iter(PyObject *seq)
1107{
Guido van Rossum805365e2007-05-07 22:24:25 +00001108 rangeobject *r = (rangeobject *)seq;
1109 longrangeiterobject *it;
Martin v. Löwis84451042007-12-20 22:57:23 +00001110 long lstart, lstop, lstep;
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001111 PyObject *int_it;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001112
Guido van Rossum805365e2007-05-07 22:24:25 +00001113 assert(PyRange_Check(seq));
Martin v. Löwis84451042007-12-20 22:57:23 +00001114
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001115 /* If all three fields and the length convert to long, use the int
1116 * version */
Martin v. Löwis84451042007-12-20 22:57:23 +00001117 lstart = PyLong_AsLong(r->start);
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001118 if (lstart == -1 && PyErr_Occurred()) {
1119 PyErr_Clear();
1120 goto long_range;
Martin v. Löwis84451042007-12-20 22:57:23 +00001121 }
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001122 lstop = PyLong_AsLong(r->stop);
1123 if (lstop == -1 && PyErr_Occurred()) {
1124 PyErr_Clear();
1125 goto long_range;
1126 }
1127 lstep = PyLong_AsLong(r->step);
1128 if (lstep == -1 && PyErr_Occurred()) {
1129 PyErr_Clear();
1130 goto long_range;
1131 }
Nick Coghlan37ee8502010-12-03 14:26:13 +00001132 int_it = fast_range_iter(lstart, lstop, lstep);
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001133 if (int_it == NULL && PyErr_ExceptionMatches(PyExc_OverflowError)) {
1134 PyErr_Clear();
1135 goto long_range;
1136 }
1137 return (PyObject *)int_it;
1138
1139 long_range:
Christian Heimesa22e8bd2007-11-29 22:35:39 +00001140 it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
Guido van Rossum805365e2007-05-07 22:24:25 +00001141 if (it == NULL)
1142 return NULL;
Guido van Rossum317e7742007-05-08 15:18:31 +00001143
1144 /* Do all initialization here, so we can DECREF on failure. */
Guido van Rossum805365e2007-05-07 22:24:25 +00001145 it->start = r->start;
Guido van Rossum317e7742007-05-08 15:18:31 +00001146 it->step = r->step;
Nick Coghlan37ee8502010-12-03 14:26:13 +00001147 it->len = r->length;
Guido van Rossum317e7742007-05-08 15:18:31 +00001148 Py_INCREF(it->start);
1149 Py_INCREF(it->step);
Nick Coghlan37ee8502010-12-03 14:26:13 +00001150 Py_INCREF(it->len);
Guido van Rossum317e7742007-05-08 15:18:31 +00001151
Guido van Rossum805365e2007-05-07 22:24:25 +00001152 it->index = PyLong_FromLong(0);
1153 if (!it->index)
1154 goto create_failure;
1155
Guido van Rossum805365e2007-05-07 22:24:25 +00001156 return (PyObject *)it;
1157
1158create_failure:
Guido van Rossum317e7742007-05-08 15:18:31 +00001159 Py_DECREF(it);
Guido van Rossum805365e2007-05-07 22:24:25 +00001160 return NULL;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001161}
1162
1163static PyObject *
Benjamin Petersona1864f32010-11-20 23:05:39 +00001164range_reverse(PyObject *seq)
1165{
Guido van Rossum805365e2007-05-07 22:24:25 +00001166 rangeobject *range = (rangeobject*) seq;
1167 longrangeiterobject *it;
Nick Coghlan37ee8502010-12-03 14:26:13 +00001168 PyObject *one, *sum, *diff, *product;
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001169 long lstart, lstop, lstep, new_start, new_stop;
1170 unsigned long ulen;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001171
Guido van Rossum805365e2007-05-07 22:24:25 +00001172 assert(PyRange_Check(seq));
Martin v. Löwis84451042007-12-20 22:57:23 +00001173
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001174 /* reversed(range(start, stop, step)) can be expressed as
1175 range(start+(n-1)*step, start-step, -step), where n is the number of
1176 integers in the range.
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001177
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001178 If each of start, stop, step, -step, start-step, and the length
1179 of the iterator is representable as a C long, use the int
1180 version. This excludes some cases where the reversed range is
1181 representable as a range_iterator, but it's good enough for
1182 common cases and it makes the checks simple. */
1183
1184 lstart = PyLong_AsLong(range->start);
1185 if (lstart == -1 && PyErr_Occurred()) {
1186 PyErr_Clear();
1187 goto long_range;
1188 }
1189 lstop = PyLong_AsLong(range->stop);
1190 if (lstop == -1 && PyErr_Occurred()) {
1191 PyErr_Clear();
1192 goto long_range;
1193 }
1194 lstep = PyLong_AsLong(range->step);
1195 if (lstep == -1 && PyErr_Occurred()) {
1196 PyErr_Clear();
1197 goto long_range;
1198 }
1199 /* check for possible overflow of -lstep */
1200 if (lstep == LONG_MIN)
1201 goto long_range;
1202
1203 /* check for overflow of lstart - lstep:
1204
1205 for lstep > 0, need only check whether lstart - lstep < LONG_MIN.
1206 for lstep < 0, need only check whether lstart - lstep > LONG_MAX
1207
1208 Rearrange these inequalities as:
1209
1210 lstart - LONG_MIN < lstep (lstep > 0)
1211 LONG_MAX - lstart < -lstep (lstep < 0)
1212
1213 and compute both sides as unsigned longs, to avoid the
1214 possibility of undefined behaviour due to signed overflow. */
1215
1216 if (lstep > 0) {
1217 if ((unsigned long)lstart - LONG_MIN < (unsigned long)lstep)
1218 goto long_range;
1219 }
1220 else {
1221 if (LONG_MAX - (unsigned long)lstart < 0UL - lstep)
1222 goto long_range;
1223 }
1224
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001225 ulen = get_len_of_range(lstart, lstop, lstep);
1226 if (ulen > (unsigned long)LONG_MAX)
1227 goto long_range;
1228
1229 new_stop = lstart - lstep;
1230 new_start = (long)(new_stop + ulen * lstep);
Nick Coghlan37ee8502010-12-03 14:26:13 +00001231 return fast_range_iter(new_start, new_stop, -lstep);
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001232
1233long_range:
Christian Heimesa22e8bd2007-11-29 22:35:39 +00001234 it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
Guido van Rossum805365e2007-05-07 22:24:25 +00001235 if (it == NULL)
1236 return NULL;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001237
Guido van Rossum805365e2007-05-07 22:24:25 +00001238 /* start + (len - 1) * step */
Nick Coghlan37ee8502010-12-03 14:26:13 +00001239 it->len = range->length;
1240 Py_INCREF(it->len);
Benjamin Peterson36fbb732009-11-16 00:34:25 +00001241
Guido van Rossum805365e2007-05-07 22:24:25 +00001242 one = PyLong_FromLong(1);
1243 if (!one)
1244 goto create_failure;
1245
Nick Coghlan37ee8502010-12-03 14:26:13 +00001246 diff = PyNumber_Subtract(it->len, one);
Guido van Rossum805365e2007-05-07 22:24:25 +00001247 Py_DECREF(one);
1248 if (!diff)
1249 goto create_failure;
1250
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001251 product = PyNumber_Multiply(diff, range->step);
1252 Py_DECREF(diff);
Guido van Rossum805365e2007-05-07 22:24:25 +00001253 if (!product)
1254 goto create_failure;
1255
1256 sum = PyNumber_Add(range->start, product);
1257 Py_DECREF(product);
1258 it->start = sum;
1259 if (!it->start)
1260 goto create_failure;
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001261
Guido van Rossum805365e2007-05-07 22:24:25 +00001262 it->step = PyNumber_Negative(range->step);
Benjamin Peterson36fbb732009-11-16 00:34:25 +00001263 if (!it->step)
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001264 goto create_failure;
Guido van Rossum805365e2007-05-07 22:24:25 +00001265
1266 it->index = PyLong_FromLong(0);
Benjamin Peterson36fbb732009-11-16 00:34:25 +00001267 if (!it->index)
1268 goto create_failure;
Guido van Rossum805365e2007-05-07 22:24:25 +00001269
1270 return (PyObject *)it;
1271
1272create_failure:
Benjamin Peterson36fbb732009-11-16 00:34:25 +00001273 Py_DECREF(it);
Guido van Rossum805365e2007-05-07 22:24:25 +00001274 return NULL;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001275}