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