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