1 /* 2 Written by Jim Hugunin and Chris Chase. 3 4 This includes both the singular ellipsis object and slice objects. 5 6 Guido, feel free to do whatever you want in the way of copyrights 7 for this file. 8 */ 9 10 /* 11 Py_Ellipsis encodes the '...' rubber index token. It is similar to 12 the Py_NoneStruct in that there is no way to create other objects of 13 this type and there is exactly one in existence. 14 */ 15 16 #include "Python.h" 17 #include "structmember.h" 18 19 static PyObject * 20 ellipsis_new(PyTypeObject *type, PyObject *args, PyObject *kwargs) 21 { 22 if (PyTuple_GET_SIZE(args) || (kwargs && PyDict_Size(kwargs))) { 23 PyErr_SetString(PyExc_TypeError, "EllipsisType takes no arguments"); 24 return NULL; 25 } 26 Py_INCREF(Py_Ellipsis); 27 return Py_Ellipsis; 28 } 29 30 static PyObject * 31 ellipsis_repr(PyObject *op) 32 { 33 return PyUnicode_FromString("Ellipsis"); 34 } 35 36 static PyObject * 37 ellipsis_reduce(PyObject *op) 38 { 39 return PyUnicode_FromString("Ellipsis"); 40 } 41 42 static PyMethodDef ellipsis_methods[] = { 43 {"__reduce__", (PyCFunction)ellipsis_reduce, METH_NOARGS, NULL}, 44 {NULL, NULL} 45 }; 46 47 PyTypeObject PyEllipsis_Type = { 48 PyVarObject_HEAD_INIT(&PyType_Type, 0) 49 "ellipsis", /* tp_name */ 50 0, /* tp_basicsize */ 51 0, /* tp_itemsize */ 52 0, /*never called*/ /* tp_dealloc */ 53 0, /* tp_print */ 54 0, /* tp_getattr */ 55 0, /* tp_setattr */ 56 0, /* tp_reserved */ 57 ellipsis_repr, /* tp_repr */ 58 0, /* tp_as_number */ 59 0, /* tp_as_sequence */ 60 0, /* tp_as_mapping */ 61 0, /* tp_hash */ 62 0, /* tp_call */ 63 0, /* tp_str */ 64 PyObject_GenericGetAttr, /* tp_getattro */ 65 0, /* tp_setattro */ 66 0, /* tp_as_buffer */ 67 Py_TPFLAGS_DEFAULT, /* tp_flags */ 68 0, /* tp_doc */ 69 0, /* tp_traverse */ 70 0, /* tp_clear */ 71 0, /* tp_richcompare */ 72 0, /* tp_weaklistoffset */ 73 0, /* tp_iter */ 74 0, /* tp_iternext */ 75 ellipsis_methods, /* tp_methods */ 76 0, /* tp_members */ 77 0, /* tp_getset */ 78 0, /* tp_base */ 79 0, /* tp_dict */ 80 0, /* tp_descr_get */ 81 0, /* tp_descr_set */ 82 0, /* tp_dictoffset */ 83 0, /* tp_init */ 84 0, /* tp_alloc */ 85 ellipsis_new, /* tp_new */ 86 }; 87 88 PyObject _Py_EllipsisObject = { 89 _PyObject_EXTRA_INIT 90 1, &PyEllipsis_Type 91 }; 92 93 94 /* Slice object implementation */ 95 96 /* Using a cache is very effective since typically only a single slice is 97 * created and then deleted again 98 */ 99 static PySliceObject *slice_cache = NULL; 100 void PySlice_Fini(void) 101 { 102 PySliceObject *obj = slice_cache; 103 if (obj != NULL) { 104 slice_cache = NULL; 105 PyObject_GC_Del(obj); 106 } 107 } 108 109 /* start, stop, and step are python objects with None indicating no 110 index is present. 111 */ 112 113 PyObject * 114 PySlice_New(PyObject *start, PyObject *stop, PyObject *step) 115 { 116 PySliceObject *obj; 117 if (slice_cache != NULL) { 118 obj = slice_cache; 119 slice_cache = NULL; 120 _Py_NewReference((PyObject *)obj); 121 } else { 122 obj = PyObject_GC_New(PySliceObject, &PySlice_Type); 123 if (obj == NULL) 124 return NULL; 125 } 126 127 if (step == NULL) step = Py_None; 128 Py_INCREF(step); 129 if (start == NULL) start = Py_None; 130 Py_INCREF(start); 131 if (stop == NULL) stop = Py_None; 132 Py_INCREF(stop); 133 134 obj->step = step; 135 obj->start = start; 136 obj->stop = stop; 137 138 _PyObject_GC_TRACK(obj); 139 return (PyObject *) obj; 140 } 141 142 PyObject * 143 _PySlice_FromIndices(Py_ssize_t istart, Py_ssize_t istop) 144 { 145 PyObject *start, *end, *slice; 146 start = PyLong_FromSsize_t(istart); 147 if (!start) 148 return NULL; 149 end = PyLong_FromSsize_t(istop); 150 if (!end) { 151 Py_DECREF(start); 152 return NULL; 153 } 154 155 slice = PySlice_New(start, end, NULL); 156 Py_DECREF(start); 157 Py_DECREF(end); 158 return slice; 159 } 160 161 int 162 PySlice_GetIndices(PyObject *_r, Py_ssize_t length, 163 Py_ssize_t *start, Py_ssize_t *stop, Py_ssize_t *step) 164 { 165 PySliceObject *r = (PySliceObject*)_r; 166 /* XXX support long ints */ 167 if (r->step == Py_None) { 168 *step = 1; 169 } else { 170 if (!PyLong_Check(r->step)) return -1; 171 *step = PyLong_AsSsize_t(r->step); 172 } 173 if (r->start == Py_None) { 174 *start = *step < 0 ? length-1 : 0; 175 } else { 176 if (!PyLong_Check(r->start)) return -1; 177 *start = PyLong_AsSsize_t(r->start); 178 if (*start < 0) *start += length; 179 } 180 if (r->stop == Py_None) { 181 *stop = *step < 0 ? -1 : length; 182 } else { 183 if (!PyLong_Check(r->stop)) return -1; 184 *stop = PyLong_AsSsize_t(r->stop); 185 if (*stop < 0) *stop += length; 186 } 187 if (*stop > length) return -1; 188 if (*start >= length) return -1; 189 if (*step == 0) return -1; 190 return 0; 191 } 192 193 int 194 PySlice_Unpack(PyObject *_r, 195 Py_ssize_t *start, Py_ssize_t *stop, Py_ssize_t *step) 196 { 197 PySliceObject *r = (PySliceObject*)_r; 198 /* this is harder to get right than you might think */ 199 200 if (r->step == Py_None) { 201 *step = 1; 202 } 203 else { 204 if (!_PyEval_SliceIndex(r->step, step)) return -1; 205 if (*step == 0) { 206 PyErr_SetString(PyExc_ValueError, 207 "slice step cannot be zero"); 208 return -1; 209 } 210 /* Here *step might be -PY_SSIZE_T_MAX-1; in this case we replace it 211 * with -PY_SSIZE_T_MAX. This doesn't affect the semantics, and it 212 * guards against later undefined behaviour resulting from code that 213 * does "step = -step" as part of a slice reversal. 214 */ 215 if (*step < -PY_SSIZE_T_MAX) 216 *step = -PY_SSIZE_T_MAX; 217 } 218 219 if (r->start == Py_None) { 220 *start = *step < 0 ? PY_SSIZE_T_MAX-1 : 0;; 221 } 222 else { 223 if (!_PyEval_SliceIndex(r->start, start)) return -1; 224 } 225 226 if (r->stop == Py_None) { 227 *stop = *step < 0 ? -PY_SSIZE_T_MAX : PY_SSIZE_T_MAX; 228 } 229 else { 230 if (!_PyEval_SliceIndex(r->stop, stop)) return -1; 231 } 232 233 return 0; 234 } 235 236 Py_ssize_t 237 PySlice_AdjustIndices(Py_ssize_t length, 238 Py_ssize_t *start, Py_ssize_t *stop, Py_ssize_t step) 239 { 240 /* this is harder to get right than you might think */ 241 242 assert(step != 0); 243 assert(step >= -PY_SSIZE_T_MAX); 244 245 if (*start < 0) { 246 *start += length; 247 if (*start < 0) { 248 *start = (step < 0) ? -1 : 0; 249 } 250 } 251 else if (*start >= length) { 252 *start = (step < 0) ? length - 1 : length; 253 } 254 255 if (*stop < 0) { 256 *stop += length; 257 if (*stop < 0) { 258 *stop = (step < 0) ? -1 : 0; 259 } 260 } 261 else if (*stop >= length) { 262 *stop = (step < 0) ? length - 1 : length; 263 } 264 265 if (step < 0) { 266 if (*stop < *start) { 267 return (*start - *stop - 1) / (-step) + 1; 268 } 269 } 270 else { 271 if (*start < *stop) { 272 return (*stop - *start - 1) / step + 1; 273 } 274 } 275 return 0; 276 } 277 278 #undef PySlice_GetIndicesEx 279 280 int 281 PySlice_GetIndicesEx(PyObject *_r, Py_ssize_t length, 282 Py_ssize_t *start, Py_ssize_t *stop, Py_ssize_t *step, 283 Py_ssize_t *slicelength) 284 { 285 if (PySlice_Unpack(_r, start, stop, step) < 0) 286 return -1; 287 *slicelength = PySlice_AdjustIndices(length, start, stop, *step); 288 return 0; 289 } 290 291 static PyObject * 292 slice_new(PyTypeObject *type, PyObject *args, PyObject *kw) 293 { 294 PyObject *start, *stop, *step; 295 296 start = stop = step = NULL; 297 298 if (!_PyArg_NoKeywords("slice()", kw)) 299 return NULL; 300 301 if (!PyArg_UnpackTuple(args, "slice", 1, 3, &start, &stop, &step)) 302 return NULL; 303 304 /* This swapping of stop and start is to maintain similarity with 305 range(). */ 306 if (stop == NULL) { 307 stop = start; 308 start = NULL; 309 } 310 return PySlice_New(start, stop, step); 311 } 312 313 PyDoc_STRVAR(slice_doc, 314 "slice(stop)\n\ 315 slice(start, stop[, step])\n\ 316 \n\ 317 Create a slice object. This is used for extended slicing (e.g. a[0:10:2])."); 318 319 static void 320 slice_dealloc(PySliceObject *r) 321 { 322 _PyObject_GC_UNTRACK(r); 323 Py_DECREF(r->step); 324 Py_DECREF(r->start); 325 Py_DECREF(r->stop); 326 if (slice_cache == NULL) 327 slice_cache = r; 328 else 329 PyObject_GC_Del(r); 330 } 331 332 static PyObject * 333 slice_repr(PySliceObject *r) 334 { 335 return PyUnicode_FromFormat("slice(%R, %R, %R)", r->start, r->stop, r->step); 336 } 337 338 static PyMemberDef slice_members[] = { 339 {"start", T_OBJECT, offsetof(PySliceObject, start), READONLY}, 340 {"stop", T_OBJECT, offsetof(PySliceObject, stop), READONLY}, 341 {"step", T_OBJECT, offsetof(PySliceObject, step), READONLY}, 342 {0} 343 }; 344 345 /* Helper function to convert a slice argument to a PyLong, and raise TypeError 346 with a suitable message on failure. */ 347 348 static PyObject* 349 evaluate_slice_index(PyObject *v) 350 { 351 if (PyIndex_Check(v)) { 352 return PyNumber_Index(v); 353 } 354 else { 355 PyErr_SetString(PyExc_TypeError, 356 "slice indices must be integers or " 357 "None or have an __index__ method"); 358 return NULL; 359 } 360 } 361 362 /* Compute slice indices given a slice and length. Return -1 on failure. Used 363 by slice.indices and rangeobject slicing. Assumes that `len` is a 364 nonnegative instance of PyLong. */ 365 366 int 367 _PySlice_GetLongIndices(PySliceObject *self, PyObject *length, 368 PyObject **start_ptr, PyObject **stop_ptr, 369 PyObject **step_ptr) 370 { 371 PyObject *start=NULL, *stop=NULL, *step=NULL; 372 PyObject *upper=NULL, *lower=NULL; 373 int step_is_negative, cmp_result; 374 375 /* Convert step to an integer; raise for zero step. */ 376 if (self->step == Py_None) { 377 step = PyLong_FromLong(1L); 378 if (step == NULL) 379 goto error; 380 step_is_negative = 0; 381 } 382 else { 383 int step_sign; 384 step = evaluate_slice_index(self->step); 385 if (step == NULL) 386 goto error; 387 step_sign = _PyLong_Sign(step); 388 if (step_sign == 0) { 389 PyErr_SetString(PyExc_ValueError, 390 "slice step cannot be zero"); 391 goto error; 392 } 393 step_is_negative = step_sign < 0; 394 } 395 396 /* Find lower and upper bounds for start and stop. */ 397 if (step_is_negative) { 398 lower = PyLong_FromLong(-1L); 399 if (lower == NULL) 400 goto error; 401 402 upper = PyNumber_Add(length, lower); 403 if (upper == NULL) 404 goto error; 405 } 406 else { 407 lower = PyLong_FromLong(0L); 408 if (lower == NULL) 409 goto error; 410 411 upper = length; 412 Py_INCREF(upper); 413 } 414 415 /* Compute start. */ 416 if (self->start == Py_None) { 417 start = step_is_negative ? upper : lower; 418 Py_INCREF(start); 419 } 420 else { 421 start = evaluate_slice_index(self->start); 422 if (start == NULL) 423 goto error; 424 425 if (_PyLong_Sign(start) < 0) { 426 /* start += length */ 427 PyObject *tmp = PyNumber_Add(start, length); 428 Py_DECREF(start); 429 start = tmp; 430 if (start == NULL) 431 goto error; 432 433 cmp_result = PyObject_RichCompareBool(start, lower, Py_LT); 434 if (cmp_result < 0) 435 goto error; 436 if (cmp_result) { 437 Py_INCREF(lower); 438 Py_DECREF(start); 439 start = lower; 440 } 441 } 442 else { 443 cmp_result = PyObject_RichCompareBool(start, upper, Py_GT); 444 if (cmp_result < 0) 445 goto error; 446 if (cmp_result) { 447 Py_INCREF(upper); 448 Py_DECREF(start); 449 start = upper; 450 } 451 } 452 } 453 454 /* Compute stop. */ 455 if (self->stop == Py_None) { 456 stop = step_is_negative ? lower : upper; 457 Py_INCREF(stop); 458 } 459 else { 460 stop = evaluate_slice_index(self->stop); 461 if (stop == NULL) 462 goto error; 463 464 if (_PyLong_Sign(stop) < 0) { 465 /* stop += length */ 466 PyObject *tmp = PyNumber_Add(stop, length); 467 Py_DECREF(stop); 468 stop = tmp; 469 if (stop == NULL) 470 goto error; 471 472 cmp_result = PyObject_RichCompareBool(stop, lower, Py_LT); 473 if (cmp_result < 0) 474 goto error; 475 if (cmp_result) { 476 Py_INCREF(lower); 477 Py_DECREF(stop); 478 stop = lower; 479 } 480 } 481 else { 482 cmp_result = PyObject_RichCompareBool(stop, upper, Py_GT); 483 if (cmp_result < 0) 484 goto error; 485 if (cmp_result) { 486 Py_INCREF(upper); 487 Py_DECREF(stop); 488 stop = upper; 489 } 490 } 491 } 492 493 *start_ptr = start; 494 *stop_ptr = stop; 495 *step_ptr = step; 496 Py_DECREF(upper); 497 Py_DECREF(lower); 498 return 0; 499 500 error: 501 *start_ptr = *stop_ptr = *step_ptr = NULL; 502 Py_XDECREF(start); 503 Py_XDECREF(stop); 504 Py_XDECREF(step); 505 Py_XDECREF(upper); 506 Py_XDECREF(lower); 507 return -1; 508 } 509 510 /* Implementation of slice.indices. */ 511 512 static PyObject* 513 slice_indices(PySliceObject* self, PyObject* len) 514 { 515 PyObject *start, *stop, *step; 516 PyObject *length; 517 int error; 518 519 /* Convert length to an integer if necessary; raise for negative length. */ 520 length = PyNumber_Index(len); 521 if (length == NULL) 522 return NULL; 523 524 if (_PyLong_Sign(length) < 0) { 525 PyErr_SetString(PyExc_ValueError, 526 "length should not be negative"); 527 Py_DECREF(length); 528 return NULL; 529 } 530 531 error = _PySlice_GetLongIndices(self, length, &start, &stop, &step); 532 Py_DECREF(length); 533 if (error == -1) 534 return NULL; 535 else 536 return Py_BuildValue("(NNN)", start, stop, step); 537 } 538 539 PyDoc_STRVAR(slice_indices_doc, 540 "S.indices(len) -> (start, stop, stride)\n\ 541 \n\ 542 Assuming a sequence of length len, calculate the start and stop\n\ 543 indices, and the stride length of the extended slice described by\n\ 544 S. Out of bounds indices are clipped in a manner consistent with the\n\ 545 handling of normal slices."); 546 547 static PyObject * 548 slice_reduce(PySliceObject* self) 549 { 550 return Py_BuildValue("O(OOO)", Py_TYPE(self), self->start, self->stop, self->step); 551 } 552 553 PyDoc_STRVAR(reduce_doc, "Return state information for pickling."); 554 555 static PyMethodDef slice_methods[] = { 556 {"indices", (PyCFunction)slice_indices, 557 METH_O, slice_indices_doc}, 558 {"__reduce__", (PyCFunction)slice_reduce, 559 METH_NOARGS, reduce_doc}, 560 {NULL, NULL} 561 }; 562 563 static PyObject * 564 slice_richcompare(PyObject *v, PyObject *w, int op) 565 { 566 PyObject *t1; 567 PyObject *t2; 568 PyObject *res; 569 570 if (!PySlice_Check(v) || !PySlice_Check(w)) 571 Py_RETURN_NOTIMPLEMENTED; 572 573 if (v == w) { 574 /* XXX Do we really need this shortcut? 575 There's a unit test for it, but is that fair? */ 576 switch (op) { 577 case Py_EQ: 578 case Py_LE: 579 case Py_GE: 580 res = Py_True; 581 break; 582 default: 583 res = Py_False; 584 break; 585 } 586 Py_INCREF(res); 587 return res; 588 } 589 590 t1 = PyTuple_New(3); 591 if (t1 == NULL) 592 return NULL; 593 t2 = PyTuple_New(3); 594 if (t2 == NULL) { 595 Py_DECREF(t1); 596 return NULL; 597 } 598 599 PyTuple_SET_ITEM(t1, 0, ((PySliceObject *)v)->start); 600 PyTuple_SET_ITEM(t1, 1, ((PySliceObject *)v)->stop); 601 PyTuple_SET_ITEM(t1, 2, ((PySliceObject *)v)->step); 602 PyTuple_SET_ITEM(t2, 0, ((PySliceObject *)w)->start); 603 PyTuple_SET_ITEM(t2, 1, ((PySliceObject *)w)->stop); 604 PyTuple_SET_ITEM(t2, 2, ((PySliceObject *)w)->step); 605 606 res = PyObject_RichCompare(t1, t2, op); 607 608 PyTuple_SET_ITEM(t1, 0, NULL); 609 PyTuple_SET_ITEM(t1, 1, NULL); 610 PyTuple_SET_ITEM(t1, 2, NULL); 611 PyTuple_SET_ITEM(t2, 0, NULL); 612 PyTuple_SET_ITEM(t2, 1, NULL); 613 PyTuple_SET_ITEM(t2, 2, NULL); 614 615 Py_DECREF(t1); 616 Py_DECREF(t2); 617 618 return res; 619 } 620 621 static int 622 slice_traverse(PySliceObject *v, visitproc visit, void *arg) 623 { 624 Py_VISIT(v->start); 625 Py_VISIT(v->stop); 626 Py_VISIT(v->step); 627 return 0; 628 } 629 630 PyTypeObject PySlice_Type = { 631 PyVarObject_HEAD_INIT(&PyType_Type, 0) 632 "slice", /* Name of this type */ 633 sizeof(PySliceObject), /* Basic object size */ 634 0, /* Item size for varobject */ 635 (destructor)slice_dealloc, /* tp_dealloc */ 636 0, /* tp_print */ 637 0, /* tp_getattr */ 638 0, /* tp_setattr */ 639 0, /* tp_reserved */ 640 (reprfunc)slice_repr, /* tp_repr */ 641 0, /* tp_as_number */ 642 0, /* tp_as_sequence */ 643 0, /* tp_as_mapping */ 644 PyObject_HashNotImplemented, /* tp_hash */ 645 0, /* tp_call */ 646 0, /* tp_str */ 647 PyObject_GenericGetAttr, /* tp_getattro */ 648 0, /* tp_setattro */ 649 0, /* tp_as_buffer */ 650 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */ 651 slice_doc, /* tp_doc */ 652 (traverseproc)slice_traverse, /* tp_traverse */ 653 0, /* tp_clear */ 654 slice_richcompare, /* tp_richcompare */ 655 0, /* tp_weaklistoffset */ 656 0, /* tp_iter */ 657 0, /* tp_iternext */ 658 slice_methods, /* tp_methods */ 659 slice_members, /* tp_members */ 660 0, /* tp_getset */ 661 0, /* tp_base */ 662 0, /* tp_dict */ 663 0, /* tp_descr_get */ 664 0, /* tp_descr_set */ 665 0, /* tp_dictoffset */ 666 0, /* tp_init */ 667 0, /* tp_alloc */ 668 slice_new, /* tp_new */ 669 }; 670
