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