Python code coverage for Objects/rangeobject.c

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