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