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