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