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 *
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)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;
PySlice_Fini(void)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 *
PySlice_New(PyObject * start,PyObject * stop,PyObject * step)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 *
_PySlice_FromIndices(Py_ssize_t istart,Py_ssize_t istop)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
PySlice_GetIndices(PyObject * _r,Py_ssize_t length,Py_ssize_t * start,Py_ssize_t * stop,Py_ssize_t * step)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
PySlice_Unpack(PyObject * _r,Py_ssize_t * start,Py_ssize_t * stop,Py_ssize_t * step)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
PySlice_AdjustIndices(Py_ssize_t length,Py_ssize_t * start,Py_ssize_t * stop,Py_ssize_t step)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
PySlice_GetIndicesEx(PyObject * _r,Py_ssize_t length,Py_ssize_t * start,Py_ssize_t * stop,Py_ssize_t * step,Py_ssize_t * slicelength)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 *
slice_new(PyTypeObject * type,PyObject * args,PyObject * kw)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
slice_dealloc(PySliceObject * r)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 *
slice_repr(PySliceObject * r)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*
evaluate_slice_index(PyObject * v)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
_PySlice_GetLongIndices(PySliceObject * self,PyObject * length,PyObject ** start_ptr,PyObject ** stop_ptr,PyObject ** step_ptr)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*
slice_indices(PySliceObject * self,PyObject * len)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 *
slice_reduce(PySliceObject * self)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 *
slice_richcompare(PyObject * v,PyObject * w,int op)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
slice_traverse(PySliceObject * v,visitproc visit,void * arg)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