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