blob: 8e74132807365a2e334d9ba72c024d649b4e37cb [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
Serhiy Storchaka6a7b3a72016-04-17 08:32:47 +03008 This could be sped up for small PyLongs if they fit in a Py_ssize_t.
Benjamin Petersonaf580df2016-09-06 10:46:49 -07009 This only matters on Win64. Though we could use long long which
Guido van Rossum805365e2007-05-07 22:24:25 +000010 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);
Serhiy Storchaka5d062d72016-06-18 09:51:55 +030032 if (step && _PyLong_Sign(step) == 0) {
33 PyErr_SetString(PyExc_ValueError,
34 "range() arg 3 must not be zero");
35 Py_CLEAR(step);
Guido van Rossum805365e2007-05-07 22:24:25 +000036 }
37
38 return step;
Raymond Hettingerc4c453f2002-06-05 23:12:45 +000039}
40
Nick Coghlan37ee8502010-12-03 14:26:13 +000041static PyObject *
42compute_range_length(PyObject *start, PyObject *stop, PyObject *step);
43
44static rangeobject *
45make_range_object(PyTypeObject *type, PyObject *start,
46 PyObject *stop, PyObject *step)
47{
48 rangeobject *obj = NULL;
49 PyObject *length;
50 length = compute_range_length(start, stop, step);
51 if (length == NULL) {
52 return NULL;
53 }
54 obj = PyObject_New(rangeobject, type);
55 if (obj == NULL) {
56 Py_DECREF(length);
57 return NULL;
58 }
59 obj->start = start;
60 obj->stop = stop;
61 obj->step = step;
62 obj->length = length;
63 return obj;
64}
65
Guido van Rossum805365e2007-05-07 22:24:25 +000066/* XXX(nnorwitz): should we error check if the user passes any empty ranges?
67 range(-10)
68 range(0, -5)
69 range(0, 5, -1)
70*/
Raymond Hettingerc4c453f2002-06-05 23:12:45 +000071static PyObject *
Benjamin Petersona1864f32010-11-20 23:05:39 +000072range_new(PyTypeObject *type, PyObject *args, PyObject *kw)
73{
Nick Coghlan37ee8502010-12-03 14:26:13 +000074 rangeobject *obj;
Guido van Rossum805365e2007-05-07 22:24:25 +000075 PyObject *start = NULL, *stop = NULL, *step = NULL;
Raymond Hettingerc4c453f2002-06-05 23:12:45 +000076
Guido van Rossum805365e2007-05-07 22:24:25 +000077 if (!_PyArg_NoKeywords("range()", kw))
78 return NULL;
Georg Brandl02c42872005-08-26 06:42:30 +000079
Guido van Rossum805365e2007-05-07 22:24:25 +000080 if (PyTuple_Size(args) <= 1) {
81 if (!PyArg_UnpackTuple(args, "range", 1, 1, &stop))
Raymond Hettinger94f55832009-06-12 18:40:16 +000082 return NULL;
Guido van Rossum805365e2007-05-07 22:24:25 +000083 stop = PyNumber_Index(stop);
84 if (!stop)
Raymond Hettinger94f55832009-06-12 18:40:16 +000085 return NULL;
Christian Heimes217cfd12007-12-02 14:31:20 +000086 start = PyLong_FromLong(0);
Raymond Hettinger94f55832009-06-12 18:40:16 +000087 if (!start) {
88 Py_DECREF(stop);
89 return NULL;
90 }
Christian Heimes217cfd12007-12-02 14:31:20 +000091 step = PyLong_FromLong(1);
Raymond Hettinger94f55832009-06-12 18:40:16 +000092 if (!step) {
93 Py_DECREF(stop);
94 Py_DECREF(start);
95 return NULL;
96 }
Guido van Rossum805365e2007-05-07 22:24:25 +000097 }
98 else {
99 if (!PyArg_UnpackTuple(args, "range", 2, 3,
100 &start, &stop, &step))
Raymond Hettinger94f55832009-06-12 18:40:16 +0000101 return NULL;
Tim Petersfeec4532004-08-08 07:17:39 +0000102
Guido van Rossum805365e2007-05-07 22:24:25 +0000103 /* Convert borrowed refs to owned refs */
104 start = PyNumber_Index(start);
Raymond Hettinger94f55832009-06-12 18:40:16 +0000105 if (!start)
106 return NULL;
Guido van Rossum805365e2007-05-07 22:24:25 +0000107 stop = PyNumber_Index(stop);
Raymond Hettinger94f55832009-06-12 18:40:16 +0000108 if (!stop) {
109 Py_DECREF(start);
110 return NULL;
111 }
112 step = validate_step(step); /* Caution, this can clear exceptions */
113 if (!step) {
114 Py_DECREF(start);
115 Py_DECREF(stop);
116 return NULL;
117 }
Guido van Rossum805365e2007-05-07 22:24:25 +0000118 }
119
Nick Coghlan37ee8502010-12-03 14:26:13 +0000120 obj = make_range_object(type, start, stop, step);
121 if (obj != NULL)
122 return (PyObject *) obj;
Guido van Rossum805365e2007-05-07 22:24:25 +0000123
Nick Coghlan37ee8502010-12-03 14:26:13 +0000124 /* Failed to create object, release attributes */
Serhiy Storchakacfdfbb42016-06-18 09:44:03 +0300125 Py_DECREF(start);
126 Py_DECREF(stop);
127 Py_DECREF(step);
Guido van Rossum805365e2007-05-07 22:24:25 +0000128 return NULL;
Raymond Hettingerc4c453f2002-06-05 23:12:45 +0000129}
130
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000131PyDoc_STRVAR(range_doc,
Chris Jerdonek83fe2e12012-10-07 14:48:36 -0700132"range(stop) -> range object\n\
133range(start, stop[, step]) -> range object\n\
Raymond Hettingerc4c453f2002-06-05 23:12:45 +0000134\n\
Benjamin Petersonac22c6b2015-04-22 09:16:07 -0400135Return an object that produces a sequence of integers from start (inclusive)\n\
136to stop (exclusive) by step. range(i, j) produces i, i+1, i+2, ..., j-1.\n\
137start defaults to 0, and stop is omitted! range(4) produces 0, 1, 2, 3.\n\
138These are exactly the valid indices for a list of 4 elements.\n\
139When step is given, it specifies the increment (or decrement).");
Raymond Hettingerc4c453f2002-06-05 23:12:45 +0000140
Guido van Rossum805365e2007-05-07 22:24:25 +0000141static void
Benjamin Petersona1864f32010-11-20 23:05:39 +0000142range_dealloc(rangeobject *r)
143{
Guido van Rossum805365e2007-05-07 22:24:25 +0000144 Py_DECREF(r->start);
145 Py_DECREF(r->stop);
146 Py_DECREF(r->step);
Nick Coghlan37ee8502010-12-03 14:26:13 +0000147 Py_DECREF(r->length);
Amaury Forgeot d'Arcb7f17e42007-11-15 20:52:21 +0000148 PyObject_Del(r);
Guido van Rossum805365e2007-05-07 22:24:25 +0000149}
150
Mark Dickinson732166d2009-06-28 22:08:40 +0000151/* Return number of items in range (lo, hi, step) as a PyLong object,
152 * when arguments are PyLong objects. Arguments MUST return 1 with
153 * PyLong_Check(). Return NULL when there is an error.
Guido van Rossum805365e2007-05-07 22:24:25 +0000154 */
155static PyObject*
Nick Coghlan37ee8502010-12-03 14:26:13 +0000156compute_range_length(PyObject *start, PyObject *stop, PyObject *step)
Benjamin Petersona1864f32010-11-20 23:05:39 +0000157{
Guido van Rossum805365e2007-05-07 22:24:25 +0000158 /* -------------------------------------------------------------
159 Algorithm is equal to that of get_len_of_range(), but it operates
Benjamin Petersona47af9c2009-06-24 21:14:38 +0000160 on PyObjects (which are assumed to be PyLong objects).
Guido van Rossum805365e2007-05-07 22:24:25 +0000161 ---------------------------------------------------------------*/
Mark Dickinson211c6252009-02-01 10:28:51 +0000162 int cmp_result;
Guido van Rossum805365e2007-05-07 22:24:25 +0000163 PyObject *lo, *hi;
Guido van Rossum805365e2007-05-07 22:24:25 +0000164 PyObject *diff = NULL;
165 PyObject *one = NULL;
166 PyObject *tmp1 = NULL, *tmp2 = NULL, *result;
167 /* holds sub-expression evaluations */
168
169 PyObject *zero = PyLong_FromLong(0);
170 if (zero == NULL)
171 return NULL;
Nick Coghlan37ee8502010-12-03 14:26:13 +0000172 cmp_result = PyObject_RichCompareBool(step, zero, Py_GT);
Guido van Rossum805365e2007-05-07 22:24:25 +0000173 Py_DECREF(zero);
Mark Dickinson211c6252009-02-01 10:28:51 +0000174 if (cmp_result == -1)
Guido van Rossum805365e2007-05-07 22:24:25 +0000175 return NULL;
176
Mark Dickinson211c6252009-02-01 10:28:51 +0000177 if (cmp_result == 1) {
Nick Coghlan37ee8502010-12-03 14:26:13 +0000178 lo = start;
179 hi = stop;
Guido van Rossum805365e2007-05-07 22:24:25 +0000180 Py_INCREF(step);
181 } else {
Nick Coghlan37ee8502010-12-03 14:26:13 +0000182 lo = stop;
183 hi = start;
184 step = PyNumber_Negative(step);
Guido van Rossum805365e2007-05-07 22:24:25 +0000185 if (!step)
186 return NULL;
187 }
188
189 /* if (lo >= hi), return length of 0. */
Serhiy Storchakafa494fd2015-05-30 17:45:22 +0300190 cmp_result = PyObject_RichCompareBool(lo, hi, Py_GE);
191 if (cmp_result != 0) {
Serhiy Storchakacfdfbb42016-06-18 09:44:03 +0300192 Py_DECREF(step);
Serhiy Storchakafa494fd2015-05-30 17:45:22 +0300193 if (cmp_result < 0)
194 return NULL;
Guido van Rossum805365e2007-05-07 22:24:25 +0000195 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:
Serhiy Storchakacfdfbb42016-06-18 09:44:03 +0300221 Py_DECREF(step);
Guido van Rossum805365e2007-05-07 22:24:25 +0000222 Py_XDECREF(tmp2);
223 Py_XDECREF(diff);
Guido van Rossum805365e2007-05-07 22:24:25 +0000224 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;
Serhiy Storchaka009b8112015-03-18 21:53:15 +0200990
Kristján Valur Jónsson25dded02014-03-05 13:47:57 +0000991 /* 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) {
Serhiy Storchaka48842712016-04-06 09:45:48 +0300997 Py_XSETREF(r->index, zero);
Kristján Valur Jónsson25dded02014-03-05 13:47:57 +0000998 Py_RETURN_NONE;
999 }
1000 Py_DECREF(zero);
1001 if (cmp < 0)
1002 return NULL;
1003
1004 cmp = PyObject_RichCompareBool(r->len, state, Py_LT);
1005 if (cmp < 0)
1006 return NULL;
1007 if (cmp > 0)
1008 state = r->len;
Serhiy Storchaka009b8112015-03-18 21:53:15 +02001009
Serhiy Storchaka4a1e70f2015-12-27 12:36:18 +02001010 Py_INCREF(state);
Serhiy Storchaka48842712016-04-06 09:45:48 +03001011 Py_XSETREF(r->index, state);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001012 Py_RETURN_NONE;
1013}
1014
Guido van Rossum805365e2007-05-07 22:24:25 +00001015static PyMethodDef longrangeiter_methods[] = {
1016 {"__length_hint__", (PyCFunction)longrangeiter_len, METH_NOARGS,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001017 length_hint_doc},
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001018 {"__reduce__", (PyCFunction)longrangeiter_reduce, METH_NOARGS,
1019 reduce_doc},
1020 {"__setstate__", (PyCFunction)longrangeiter_setstate, METH_O,
1021 setstate_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001022 {NULL, NULL} /* sentinel */
Guido van Rossum805365e2007-05-07 22:24:25 +00001023};
1024
1025static void
Benjamin Petersona1864f32010-11-20 23:05:39 +00001026longrangeiter_dealloc(longrangeiterobject *r)
1027{
Guido van Rossum805365e2007-05-07 22:24:25 +00001028 Py_XDECREF(r->index);
Guido van Rossum317e7742007-05-08 15:18:31 +00001029 Py_XDECREF(r->start);
1030 Py_XDECREF(r->step);
1031 Py_XDECREF(r->len);
Amaury Forgeot d'Arcb7f17e42007-11-15 20:52:21 +00001032 PyObject_Del(r);
Guido van Rossum805365e2007-05-07 22:24:25 +00001033}
1034
1035static PyObject *
Benjamin Petersona1864f32010-11-20 23:05:39 +00001036longrangeiter_next(longrangeiterobject *r)
1037{
Guido van Rossum805365e2007-05-07 22:24:25 +00001038 PyObject *one, *product, *new_index, *result;
1039 if (PyObject_RichCompareBool(r->index, r->len, Py_LT) != 1)
1040 return NULL;
1041
1042 one = PyLong_FromLong(1);
1043 if (!one)
1044 return NULL;
1045
Guido van Rossum805365e2007-05-07 22:24:25 +00001046 new_index = PyNumber_Add(r->index, one);
1047 Py_DECREF(one);
Benjamin Peterson36fbb732009-11-16 00:34:25 +00001048 if (!new_index)
1049 return NULL;
1050
1051 product = PyNumber_Multiply(r->index, r->step);
1052 if (!product) {
1053 Py_DECREF(new_index);
Guido van Rossum805365e2007-05-07 22:24:25 +00001054 return NULL;
1055 }
1056
1057 result = PyNumber_Add(r->start, product);
1058 Py_DECREF(product);
1059 if (result) {
Serhiy Storchaka57a01d32016-04-10 18:05:40 +03001060 Py_SETREF(r->index, new_index);
Guido van Rossum805365e2007-05-07 22:24:25 +00001061 }
Benjamin Peterson36fbb732009-11-16 00:34:25 +00001062 else {
1063 Py_DECREF(new_index);
1064 }
Guido van Rossum805365e2007-05-07 22:24:25 +00001065
1066 return result;
1067}
1068
Christian Heimesa22e8bd2007-11-29 22:35:39 +00001069PyTypeObject PyLongRangeIter_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001070 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1071 "longrange_iterator", /* tp_name */
1072 sizeof(longrangeiterobject), /* tp_basicsize */
1073 0, /* tp_itemsize */
1074 /* methods */
1075 (destructor)longrangeiter_dealloc, /* tp_dealloc */
1076 0, /* tp_print */
1077 0, /* tp_getattr */
1078 0, /* tp_setattr */
1079 0, /* tp_reserved */
1080 0, /* tp_repr */
1081 0, /* tp_as_number */
1082 0, /* tp_as_sequence */
1083 0, /* tp_as_mapping */
1084 0, /* tp_hash */
1085 0, /* tp_call */
1086 0, /* tp_str */
1087 PyObject_GenericGetAttr, /* tp_getattro */
1088 0, /* tp_setattro */
1089 0, /* tp_as_buffer */
1090 Py_TPFLAGS_DEFAULT, /* tp_flags */
1091 0, /* tp_doc */
1092 0, /* tp_traverse */
1093 0, /* tp_clear */
1094 0, /* tp_richcompare */
1095 0, /* tp_weaklistoffset */
1096 PyObject_SelfIter, /* tp_iter */
1097 (iternextfunc)longrangeiter_next, /* tp_iternext */
1098 longrangeiter_methods, /* tp_methods */
1099 0,
Raymond Hettinger48165d42002-06-05 20:08:48 +00001100};
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001101
1102static PyObject *
Benjamin Petersona1864f32010-11-20 23:05:39 +00001103range_iter(PyObject *seq)
1104{
Guido van Rossum805365e2007-05-07 22:24:25 +00001105 rangeobject *r = (rangeobject *)seq;
1106 longrangeiterobject *it;
Martin v. Löwis84451042007-12-20 22:57:23 +00001107 long lstart, lstop, lstep;
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001108 PyObject *int_it;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001109
Guido van Rossum805365e2007-05-07 22:24:25 +00001110 assert(PyRange_Check(seq));
Martin v. Löwis84451042007-12-20 22:57:23 +00001111
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001112 /* If all three fields and the length convert to long, use the int
1113 * version */
Martin v. Löwis84451042007-12-20 22:57:23 +00001114 lstart = PyLong_AsLong(r->start);
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001115 if (lstart == -1 && PyErr_Occurred()) {
1116 PyErr_Clear();
1117 goto long_range;
Martin v. Löwis84451042007-12-20 22:57:23 +00001118 }
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001119 lstop = PyLong_AsLong(r->stop);
1120 if (lstop == -1 && PyErr_Occurred()) {
1121 PyErr_Clear();
1122 goto long_range;
1123 }
1124 lstep = PyLong_AsLong(r->step);
1125 if (lstep == -1 && PyErr_Occurred()) {
1126 PyErr_Clear();
1127 goto long_range;
1128 }
Nick Coghlan37ee8502010-12-03 14:26:13 +00001129 int_it = fast_range_iter(lstart, lstop, lstep);
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001130 if (int_it == NULL && PyErr_ExceptionMatches(PyExc_OverflowError)) {
1131 PyErr_Clear();
1132 goto long_range;
1133 }
1134 return (PyObject *)int_it;
1135
1136 long_range:
Christian Heimesa22e8bd2007-11-29 22:35:39 +00001137 it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
Guido van Rossum805365e2007-05-07 22:24:25 +00001138 if (it == NULL)
1139 return NULL;
Guido van Rossum317e7742007-05-08 15:18:31 +00001140
1141 /* Do all initialization here, so we can DECREF on failure. */
Guido van Rossum805365e2007-05-07 22:24:25 +00001142 it->start = r->start;
Guido van Rossum317e7742007-05-08 15:18:31 +00001143 it->step = r->step;
Nick Coghlan37ee8502010-12-03 14:26:13 +00001144 it->len = r->length;
Guido van Rossum317e7742007-05-08 15:18:31 +00001145 Py_INCREF(it->start);
1146 Py_INCREF(it->step);
Nick Coghlan37ee8502010-12-03 14:26:13 +00001147 Py_INCREF(it->len);
Guido van Rossum317e7742007-05-08 15:18:31 +00001148
Guido van Rossum805365e2007-05-07 22:24:25 +00001149 it->index = PyLong_FromLong(0);
1150 if (!it->index)
1151 goto create_failure;
1152
Guido van Rossum805365e2007-05-07 22:24:25 +00001153 return (PyObject *)it;
1154
1155create_failure:
Guido van Rossum317e7742007-05-08 15:18:31 +00001156 Py_DECREF(it);
Guido van Rossum805365e2007-05-07 22:24:25 +00001157 return NULL;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001158}
1159
1160static PyObject *
Benjamin Petersona1864f32010-11-20 23:05:39 +00001161range_reverse(PyObject *seq)
1162{
Guido van Rossum805365e2007-05-07 22:24:25 +00001163 rangeobject *range = (rangeobject*) seq;
1164 longrangeiterobject *it;
Nick Coghlan37ee8502010-12-03 14:26:13 +00001165 PyObject *one, *sum, *diff, *product;
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001166 long lstart, lstop, lstep, new_start, new_stop;
1167 unsigned long ulen;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001168
Guido van Rossum805365e2007-05-07 22:24:25 +00001169 assert(PyRange_Check(seq));
Martin v. Löwis84451042007-12-20 22:57:23 +00001170
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001171 /* reversed(range(start, stop, step)) can be expressed as
1172 range(start+(n-1)*step, start-step, -step), where n is the number of
1173 integers in the range.
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001174
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001175 If each of start, stop, step, -step, start-step, and the length
1176 of the iterator is representable as a C long, use the int
1177 version. This excludes some cases where the reversed range is
1178 representable as a range_iterator, but it's good enough for
1179 common cases and it makes the checks simple. */
1180
1181 lstart = PyLong_AsLong(range->start);
1182 if (lstart == -1 && PyErr_Occurred()) {
1183 PyErr_Clear();
1184 goto long_range;
1185 }
1186 lstop = PyLong_AsLong(range->stop);
1187 if (lstop == -1 && PyErr_Occurred()) {
1188 PyErr_Clear();
1189 goto long_range;
1190 }
1191 lstep = PyLong_AsLong(range->step);
1192 if (lstep == -1 && PyErr_Occurred()) {
1193 PyErr_Clear();
1194 goto long_range;
1195 }
1196 /* check for possible overflow of -lstep */
1197 if (lstep == LONG_MIN)
1198 goto long_range;
1199
1200 /* check for overflow of lstart - lstep:
1201
1202 for lstep > 0, need only check whether lstart - lstep < LONG_MIN.
1203 for lstep < 0, need only check whether lstart - lstep > LONG_MAX
1204
1205 Rearrange these inequalities as:
1206
1207 lstart - LONG_MIN < lstep (lstep > 0)
1208 LONG_MAX - lstart < -lstep (lstep < 0)
1209
1210 and compute both sides as unsigned longs, to avoid the
1211 possibility of undefined behaviour due to signed overflow. */
1212
1213 if (lstep > 0) {
1214 if ((unsigned long)lstart - LONG_MIN < (unsigned long)lstep)
1215 goto long_range;
1216 }
1217 else {
1218 if (LONG_MAX - (unsigned long)lstart < 0UL - lstep)
1219 goto long_range;
1220 }
1221
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001222 ulen = get_len_of_range(lstart, lstop, lstep);
1223 if (ulen > (unsigned long)LONG_MAX)
1224 goto long_range;
1225
1226 new_stop = lstart - lstep;
1227 new_start = (long)(new_stop + ulen * lstep);
Nick Coghlan37ee8502010-12-03 14:26:13 +00001228 return fast_range_iter(new_start, new_stop, -lstep);
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001229
1230long_range:
Christian Heimesa22e8bd2007-11-29 22:35:39 +00001231 it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
Guido van Rossum805365e2007-05-07 22:24:25 +00001232 if (it == NULL)
1233 return NULL;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001234
Guido van Rossum805365e2007-05-07 22:24:25 +00001235 /* start + (len - 1) * step */
Nick Coghlan37ee8502010-12-03 14:26:13 +00001236 it->len = range->length;
1237 Py_INCREF(it->len);
Benjamin Peterson36fbb732009-11-16 00:34:25 +00001238
Guido van Rossum805365e2007-05-07 22:24:25 +00001239 one = PyLong_FromLong(1);
1240 if (!one)
1241 goto create_failure;
1242
Nick Coghlan37ee8502010-12-03 14:26:13 +00001243 diff = PyNumber_Subtract(it->len, one);
Guido van Rossum805365e2007-05-07 22:24:25 +00001244 Py_DECREF(one);
1245 if (!diff)
1246 goto create_failure;
1247
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001248 product = PyNumber_Multiply(diff, range->step);
1249 Py_DECREF(diff);
Guido van Rossum805365e2007-05-07 22:24:25 +00001250 if (!product)
1251 goto create_failure;
1252
1253 sum = PyNumber_Add(range->start, product);
1254 Py_DECREF(product);
1255 it->start = sum;
1256 if (!it->start)
1257 goto create_failure;
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001258
Guido van Rossum805365e2007-05-07 22:24:25 +00001259 it->step = PyNumber_Negative(range->step);
Benjamin Peterson36fbb732009-11-16 00:34:25 +00001260 if (!it->step)
Mark Dickinsond550c9a2009-11-15 09:57:26 +00001261 goto create_failure;
Guido van Rossum805365e2007-05-07 22:24:25 +00001262
1263 it->index = PyLong_FromLong(0);
Benjamin Peterson36fbb732009-11-16 00:34:25 +00001264 if (!it->index)
1265 goto create_failure;
Guido van Rossum805365e2007-05-07 22:24:25 +00001266
1267 return (PyObject *)it;
1268
1269create_failure:
Benjamin Peterson36fbb732009-11-16 00:34:25 +00001270 Py_DECREF(it);
Guido van Rossum805365e2007-05-07 22:24:25 +00001271 return NULL;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001272}