1 /* Range object implementation */
2
3 #include "Python.h"
4
5 typedef struct {
6 PyObject_HEAD
7 long start;
8 long step;
9 long len;
10 } rangeobject;
11
12 /* Return number of items in range (lo, hi, step). step != 0
13 * required. The result always fits in an unsigned long.
14 */
15 static unsigned long
get_len_of_range(long lo,long hi,long step)16 get_len_of_range(long lo, long hi, long step)
17 {
18 /* -------------------------------------------------------------
19 If step > 0 and lo >= hi, or step < 0 and lo <= hi, the range is empty.
20 Else for step > 0, if n values are in the range, the last one is
21 lo + (n-1)*step, which must be <= hi-1. Rearranging,
22 n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives
23 the proper value. Since lo < hi in this case, hi-lo-1 >= 0, so
24 the RHS is non-negative and so truncation is the same as the
25 floor. Letting M be the largest positive long, the worst case
26 for the RHS numerator is hi=M, lo=-M-1, and then
27 hi-lo-1 = M-(-M-1)-1 = 2*M. Therefore unsigned long has enough
28 precision to compute the RHS exactly. The analysis for step < 0
29 is similar.
30 ---------------------------------------------------------------*/
31 assert(step != 0);
32 if (step > 0 && lo < hi)
33 return 1UL + (hi - 1UL - lo) / step;
34 else if (step < 0 && lo > hi)
35 return 1UL + (lo - 1UL - hi) / (0UL - step);
36 else
37 return 0UL;
38 }
39
40 /* Return a stop value suitable for reconstructing the xrange from
41 * a (start, stop, step) triple. Used in range_repr and range_reduce.
42 * Computes start + len * step, clipped to the range [LONG_MIN, LONG_MAX].
43 */
44 static long
get_stop_for_range(rangeobject * r)45 get_stop_for_range(rangeobject *r)
46 {
47 long last;
48
49 if (r->len == 0)
50 return r->start;
51
52 /* The tricky bit is avoiding overflow. We first compute the last entry in
53 the xrange, start + (len - 1) * step, which is guaranteed to lie within
54 the range of a long, and then add step to it. See the range_reverse
55 comments for an explanation of the casts below.
56 */
57 last = (long)(r->start + (unsigned long)(r->len - 1) * r->step);
58 if (r->step > 0)
59 return last > LONG_MAX - r->step ? LONG_MAX : last + r->step;
60 else
61 return last < LONG_MIN - r->step ? LONG_MIN : last + r->step;
62 }
63
64 static PyObject *
range_new(PyTypeObject * type,PyObject * args,PyObject * kw)65 range_new(PyTypeObject *type, PyObject *args, PyObject *kw)
66 {
67 rangeobject *obj;
68 long ilow = 0, ihigh = 0, istep = 1;
69 unsigned long n;
70
71 if (!_PyArg_NoKeywords("xrange()", kw))
72 return NULL;
73
74 if (PyTuple_Size(args) <= 1) {
75 if (!PyArg_ParseTuple(args,
76 "l;xrange() requires 1-3 int arguments",
77 &ihigh))
78 return NULL;
79 }
80 else {
81 if (!PyArg_ParseTuple(args,
82 "ll|l;xrange() requires 1-3 int arguments",
83 &ilow, &ihigh, &istep))
84 return NULL;
85 }
86 if (istep == 0) {
87 PyErr_SetString(PyExc_ValueError, "xrange() arg 3 must not be zero");
88 return NULL;
89 }
90 n = get_len_of_range(ilow, ihigh, istep);
91 if (n > (unsigned long)LONG_MAX || (long)n > PY_SSIZE_T_MAX) {
92 PyErr_SetString(PyExc_OverflowError,
93 "xrange() result has too many items");
94 return NULL;
95 }
96
97 obj = PyObject_New(rangeobject, &PyRange_Type);
98 if (obj == NULL)
99 return NULL;
100 obj->start = ilow;
101 obj->len = (long)n;
102 obj->step = istep;
103 return (PyObject *) obj;
104 }
105
106 PyDoc_STRVAR(range_doc,
107 "xrange(stop) -> xrange object\n\
108 xrange(start, stop[, step]) -> xrange object\n\
109 \n\
110 Like range(), but instead of returning a list, returns an object that\n\
111 generates the numbers in the range on demand. For looping, this is \n\
112 slightly faster than range() and more memory efficient.");
113
114 static PyObject *
range_item(rangeobject * r,Py_ssize_t i)115 range_item(rangeobject *r, Py_ssize_t i)
116 {
117 if (i < 0 || i >= r->len) {
118 PyErr_SetString(PyExc_IndexError,
119 "xrange object index out of range");
120 return NULL;
121 }
122 /* do calculation entirely using unsigned longs, to avoid
123 undefined behaviour due to signed overflow. */
124 return PyInt_FromLong((long)(r->start + (unsigned long)i * r->step));
125 }
126
127 static Py_ssize_t
range_length(rangeobject * r)128 range_length(rangeobject *r)
129 {
130 return (Py_ssize_t)(r->len);
131 }
132
133 static PyObject *
range_repr(rangeobject * r)134 range_repr(rangeobject *r)
135 {
136 PyObject *rtn;
137
138 if (r->start == 0 && r->step == 1)
139 rtn = PyString_FromFormat("xrange(%ld)",
140 get_stop_for_range(r));
141
142 else if (r->step == 1)
143 rtn = PyString_FromFormat("xrange(%ld, %ld)",
144 r->start,
145 get_stop_for_range(r));
146
147 else
148 rtn = PyString_FromFormat("xrange(%ld, %ld, %ld)",
149 r->start,
150 get_stop_for_range(r),
151 r->step);
152 return rtn;
153 }
154
155 /* Pickling support */
156 static PyObject *
range_reduce(rangeobject * r,PyObject * args)157 range_reduce(rangeobject *r, PyObject *args)
158 {
159 return Py_BuildValue("(O(lll))", Py_TYPE(r),
160 r->start,
161 get_stop_for_range(r),
162 r->step);
163 }
164
165 static PySequenceMethods range_as_sequence = {
166 (lenfunc)range_length, /* sq_length */
167 0, /* sq_concat */
168 0, /* sq_repeat */
169 (ssizeargfunc)range_item, /* sq_item */
170 0, /* sq_slice */
171 };
172
173 static PyObject * range_iter(PyObject *seq);
174 static PyObject * range_reverse(PyObject *seq);
175
176 PyDoc_STRVAR(reverse_doc,
177 "Returns a reverse iterator.");
178
179 static PyMethodDef range_methods[] = {
180 {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS, reverse_doc},
181 {"__reduce__", (PyCFunction)range_reduce, METH_VARARGS},
182 {NULL, NULL} /* sentinel */
183 };
184
185 PyTypeObject PyRange_Type = {
186 PyVarObject_HEAD_INIT(&PyType_Type, 0)
187 "xrange", /* Name of this type */
188 sizeof(rangeobject), /* Basic object size */
189 0, /* Item size for varobject */
190 (destructor)PyObject_Del, /* tp_dealloc */
191 0, /* tp_print */
192 0, /* tp_getattr */
193 0, /* tp_setattr */
194 0, /* tp_compare */
195 (reprfunc)range_repr, /* tp_repr */
196 0, /* tp_as_number */
197 &range_as_sequence, /* tp_as_sequence */
198 0, /* tp_as_mapping */
199 0, /* tp_hash */
200 0, /* tp_call */
201 0, /* tp_str */
202 PyObject_GenericGetAttr, /* tp_getattro */
203 0, /* tp_setattro */
204 0, /* tp_as_buffer */
205 Py_TPFLAGS_DEFAULT, /* tp_flags */
206 range_doc, /* tp_doc */
207 0, /* tp_traverse */
208 0, /* tp_clear */
209 0, /* tp_richcompare */
210 0, /* tp_weaklistoffset */
211 range_iter, /* tp_iter */
212 0, /* tp_iternext */
213 range_methods, /* tp_methods */
214 0, /* tp_members */
215 0, /* tp_getset */
216 0, /* tp_base */
217 0, /* tp_dict */
218 0, /* tp_descr_get */
219 0, /* tp_descr_set */
220 0, /* tp_dictoffset */
221 0, /* tp_init */
222 0, /* tp_alloc */
223 range_new, /* tp_new */
224 };
225
226 /*********************** Xrange Iterator **************************/
227
228 typedef struct {
229 PyObject_HEAD
230 long index;
231 long start;
232 long step;
233 long len;
234 } rangeiterobject;
235
236 static PyObject *
rangeiter_next(rangeiterobject * r)237 rangeiter_next(rangeiterobject *r)
238 {
239 if (r->index < r->len)
240 return PyInt_FromLong(r->start + (r->index++) * r->step);
241 return NULL;
242 }
243
244 static PyObject *
rangeiter_len(rangeiterobject * r)245 rangeiter_len(rangeiterobject *r)
246 {
247 return PyInt_FromLong(r->len - r->index);
248 }
249
250 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
251
252 static PyMethodDef rangeiter_methods[] = {
253 {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS, length_hint_doc},
254 {NULL, NULL} /* sentinel */
255 };
256
257 static PyTypeObject Pyrangeiter_Type = {
258 PyVarObject_HEAD_INIT(&PyType_Type, 0)
259 "rangeiterator", /* tp_name */
260 sizeof(rangeiterobject), /* tp_basicsize */
261 0, /* tp_itemsize */
262 /* methods */
263 (destructor)PyObject_Del, /* tp_dealloc */
264 0, /* tp_print */
265 0, /* tp_getattr */
266 0, /* tp_setattr */
267 0, /* tp_compare */
268 0, /* tp_repr */
269 0, /* tp_as_number */
270 0, /* tp_as_sequence */
271 0, /* tp_as_mapping */
272 0, /* tp_hash */
273 0, /* tp_call */
274 0, /* tp_str */
275 PyObject_GenericGetAttr, /* tp_getattro */
276 0, /* tp_setattro */
277 0, /* tp_as_buffer */
278 Py_TPFLAGS_DEFAULT, /* tp_flags */
279 0, /* tp_doc */
280 0, /* tp_traverse */
281 0, /* tp_clear */
282 0, /* tp_richcompare */
283 0, /* tp_weaklistoffset */
284 PyObject_SelfIter, /* tp_iter */
285 (iternextfunc)rangeiter_next, /* tp_iternext */
286 rangeiter_methods, /* tp_methods */
287 0,
288 };
289
290 static PyObject *
range_iter(PyObject * seq)291 range_iter(PyObject *seq)
292 {
293 rangeiterobject *it;
294
295 if (!PyRange_Check(seq)) {
296 PyErr_BadInternalCall();
297 return NULL;
298 }
299 it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);
300 if (it == NULL)
301 return NULL;
302 it->index = 0;
303 it->start = ((rangeobject *)seq)->start;
304 it->step = ((rangeobject *)seq)->step;
305 it->len = ((rangeobject *)seq)->len;
306 return (PyObject *)it;
307 }
308
309 static PyObject *
range_reverse(PyObject * seq)310 range_reverse(PyObject *seq)
311 {
312 rangeiterobject *it;
313 long start, step, len;
314
315 if (!PyRange_Check(seq)) {
316 PyErr_BadInternalCall();
317 return NULL;
318 }
319 it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);
320 if (it == NULL)
321 return NULL;
322
323 start = ((rangeobject *)seq)->start;
324 step = ((rangeobject *)seq)->step;
325 len = ((rangeobject *)seq)->len;
326
327 it->index = 0;
328 it->len = len;
329 /* the casts below guard against signed overflow by turning it
330 into unsigned overflow instead. The correctness of this
331 code still depends on conversion from unsigned long to long
332 wrapping modulo ULONG_MAX+1, which isn't guaranteed (see
333 C99 6.3.1.3p3) but seems to hold in practice for all
334 platforms we're likely to meet.
335
336 If step == LONG_MIN then we still end up with LONG_MIN
337 after negation; but this works out, since we've still got
338 the correct value modulo ULONG_MAX+1, and the range_item
339 calculation is also done modulo ULONG_MAX+1.
340 */
341 it->start = (long)(start + (unsigned long)(len-1) * step);
342 it->step = (long)(0UL-step);
343
344 return (PyObject *)it;
345 }
346