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