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 "structmember.h"
18
19 static PyObject *
ellipsis_repr(PyObject * op)20 ellipsis_repr(PyObject *op)
21 {
22 return PyString_FromString("Ellipsis");
23 }
24
25 PyTypeObject PyEllipsis_Type = {
26 PyVarObject_HEAD_INIT(&PyType_Type, 0)
27 "ellipsis", /* tp_name */
28 0, /* tp_basicsize */
29 0, /* tp_itemsize */
30 0, /*never called*/ /* tp_dealloc */
31 0, /* tp_print */
32 0, /* tp_getattr */
33 0, /* tp_setattr */
34 0, /* tp_compare */
35 ellipsis_repr, /* tp_repr */
36 0, /* tp_as_number */
37 0, /* tp_as_sequence */
38 0, /* tp_as_mapping */
39 0, /* tp_hash */
40 0, /* tp_call */
41 0, /* tp_str */
42 PyObject_GenericGetAttr, /* tp_getattro */
43 0, /* tp_setattro */
44 0, /* tp_as_buffer */
45 Py_TPFLAGS_DEFAULT, /* tp_flags */
46 };
47
48 PyObject _Py_EllipsisObject = {
49 _PyObject_EXTRA_INIT
50 1, &PyEllipsis_Type
51 };
52
53
54 /* Slice object implementation
55
56 start, stop, and step are python objects with None indicating no
57 index is present.
58 */
59
60 PyObject *
PySlice_New(PyObject * start,PyObject * stop,PyObject * step)61 PySlice_New(PyObject *start, PyObject *stop, PyObject *step)
62 {
63 PySliceObject *obj = PyObject_GC_New(PySliceObject, &PySlice_Type);
64
65 if (obj == NULL)
66 return NULL;
67
68 if (step == NULL) step = Py_None;
69 Py_INCREF(step);
70 if (start == NULL) start = Py_None;
71 Py_INCREF(start);
72 if (stop == NULL) stop = Py_None;
73 Py_INCREF(stop);
74
75 obj->step = step;
76 obj->start = start;
77 obj->stop = stop;
78
79 _PyObject_GC_TRACK(obj);
80 return (PyObject *) obj;
81 }
82
83 PyObject *
_PySlice_FromIndices(Py_ssize_t istart,Py_ssize_t istop)84 _PySlice_FromIndices(Py_ssize_t istart, Py_ssize_t istop)
85 {
86 PyObject *start, *end, *slice;
87 start = PyInt_FromSsize_t(istart);
88 if (!start)
89 return NULL;
90 end = PyInt_FromSsize_t(istop);
91 if (!end) {
92 Py_DECREF(start);
93 return NULL;
94 }
95
96 slice = PySlice_New(start, end, NULL);
97 Py_DECREF(start);
98 Py_DECREF(end);
99 return slice;
100 }
101
102 int
PySlice_GetIndices(PySliceObject * r,Py_ssize_t length,Py_ssize_t * start,Py_ssize_t * stop,Py_ssize_t * step)103 PySlice_GetIndices(PySliceObject *r, Py_ssize_t length,
104 Py_ssize_t *start, Py_ssize_t *stop, Py_ssize_t *step)
105 {
106 /* XXX support long ints */
107 if (r->step == Py_None) {
108 *step = 1;
109 } else {
110 if (!_PyAnyInt_Check(r->step)) return -1;
111 *step = PyInt_AsSsize_t(r->step);
112 }
113 if (r->start == Py_None) {
114 *start = *step < 0 ? length-1 : 0;
115 } else {
116 if (!_PyAnyInt_Check(r->start)) return -1;
117 *start = PyInt_AsSsize_t(r->start);
118 if (*start < 0) *start += length;
119 }
120 if (r->stop == Py_None) {
121 *stop = *step < 0 ? -1 : length;
122 } else {
123 if (!_PyAnyInt_Check(r->stop)) return -1;
124 *stop = PyInt_AsSsize_t(r->stop);
125 if (*stop < 0) *stop += length;
126 }
127 if (*stop > length) return -1;
128 if (*start >= length) return -1;
129 if (*step == 0) return -1;
130 return 0;
131 }
132
133 int
_PySlice_Unpack(PyObject * _r,Py_ssize_t * start,Py_ssize_t * stop,Py_ssize_t * step)134 _PySlice_Unpack(PyObject *_r,
135 Py_ssize_t *start, Py_ssize_t *stop, Py_ssize_t *step)
136 {
137 PySliceObject *r = (PySliceObject *)_r;
138 /* this is harder to get right than you might think */
139
140 assert(PY_SSIZE_T_MIN + 1 <= -PY_SSIZE_T_MAX);
141
142 if (r->step == Py_None) {
143 *step = 1;
144 }
145 else {
146 if (!_PyEval_SliceIndex(r->step, step)) return -1;
147 if (*step == 0) {
148 PyErr_SetString(PyExc_ValueError,
149 "slice step cannot be zero");
150 return -1;
151 }
152 /* Here *step might be -PY_SSIZE_T_MAX-1; in this case we replace it
153 * with -PY_SSIZE_T_MAX. This doesn't affect the semantics, and it
154 * guards against later undefined behaviour resulting from code that
155 * does "step = -step" as part of a slice reversal.
156 */
157 if (*step < -PY_SSIZE_T_MAX)
158 *step = -PY_SSIZE_T_MAX;
159 }
160
161 if (r->start == Py_None) {
162 *start = *step < 0 ? PY_SSIZE_T_MAX : 0;
163 }
164 else {
165 if (!_PyEval_SliceIndex(r->start, start)) return -1;
166 }
167
168 if (r->stop == Py_None) {
169 *stop = *step < 0 ? PY_SSIZE_T_MIN : PY_SSIZE_T_MAX;
170 }
171 else {
172 if (!_PyEval_SliceIndex(r->stop, stop)) return -1;
173 }
174
175 return 0;
176 }
177
178 Py_ssize_t
_PySlice_AdjustIndices(Py_ssize_t length,Py_ssize_t * start,Py_ssize_t * stop,Py_ssize_t step)179 _PySlice_AdjustIndices(Py_ssize_t length,
180 Py_ssize_t *start, Py_ssize_t *stop, Py_ssize_t step)
181 {
182 /* this is harder to get right than you might think */
183
184 assert(step != 0);
185 assert(step >= -PY_SSIZE_T_MAX);
186
187 if (*start < 0) {
188 *start += length;
189 if (*start < 0) {
190 *start = (step < 0) ? -1 : 0;
191 }
192 }
193 else if (*start >= length) {
194 *start = (step < 0) ? length - 1 : length;
195 }
196
197 if (*stop < 0) {
198 *stop += length;
199 if (*stop < 0) {
200 *stop = (step < 0) ? -1 : 0;
201 }
202 }
203 else if (*stop >= length) {
204 *stop = (step < 0) ? length - 1 : length;
205 }
206
207 if (step < 0) {
208 if (*stop < *start) {
209 return (*start - *stop - 1) / (-step) + 1;
210 }
211 }
212 else {
213 if (*start < *stop) {
214 return (*stop - *start - 1) / step + 1;
215 }
216 }
217 return 0;
218 }
219
220 #undef PySlice_GetIndicesEx
221
222 int
PySlice_GetIndicesEx(PySliceObject * r,Py_ssize_t length,Py_ssize_t * start,Py_ssize_t * stop,Py_ssize_t * step,Py_ssize_t * slicelength)223 PySlice_GetIndicesEx(PySliceObject *r, Py_ssize_t length,
224 Py_ssize_t *start, Py_ssize_t *stop, Py_ssize_t *step,
225 Py_ssize_t *slicelength)
226 {
227 if (_PySlice_Unpack((PyObject *)r, start, stop, step) < 0)
228 return -1;
229 *slicelength = _PySlice_AdjustIndices(length, start, stop, *step);
230 return 0;
231 }
232
233 static PyObject *
slice_new(PyTypeObject * type,PyObject * args,PyObject * kw)234 slice_new(PyTypeObject *type, PyObject *args, PyObject *kw)
235 {
236 PyObject *start, *stop, *step;
237
238 start = stop = step = NULL;
239
240 if (!_PyArg_NoKeywords("slice()", kw))
241 return NULL;
242
243 if (!PyArg_UnpackTuple(args, "slice", 1, 3, &start, &stop, &step))
244 return NULL;
245
246 /* This swapping of stop and start is to maintain similarity with
247 range(). */
248 if (stop == NULL) {
249 stop = start;
250 start = NULL;
251 }
252 return PySlice_New(start, stop, step);
253 }
254
255 PyDoc_STRVAR(slice_doc,
256 "slice(stop)\n\
257 slice(start, stop[, step])\n\
258 \n\
259 Create a slice object. This is used for extended slicing (e.g. a[0:10:2]).");
260
261 static void
slice_dealloc(PySliceObject * r)262 slice_dealloc(PySliceObject *r)
263 {
264 _PyObject_GC_UNTRACK(r);
265 Py_DECREF(r->step);
266 Py_DECREF(r->start);
267 Py_DECREF(r->stop);
268 PyObject_GC_Del(r);
269 }
270
271 static PyObject *
slice_repr(PySliceObject * r)272 slice_repr(PySliceObject *r)
273 {
274 PyObject *s, *comma;
275
276 s = PyString_FromString("slice(");
277 comma = PyString_FromString(", ");
278 PyString_ConcatAndDel(&s, PyObject_Repr(r->start));
279 PyString_Concat(&s, comma);
280 PyString_ConcatAndDel(&s, PyObject_Repr(r->stop));
281 PyString_Concat(&s, comma);
282 PyString_ConcatAndDel(&s, PyObject_Repr(r->step));
283 PyString_ConcatAndDel(&s, PyString_FromString(")"));
284 Py_DECREF(comma);
285 return s;
286 }
287
288 static PyMemberDef slice_members[] = {
289 {"start", T_OBJECT, offsetof(PySliceObject, start), READONLY},
290 {"stop", T_OBJECT, offsetof(PySliceObject, stop), READONLY},
291 {"step", T_OBJECT, offsetof(PySliceObject, step), READONLY},
292 {0}
293 };
294
295 static PyObject*
slice_indices(PySliceObject * self,PyObject * len)296 slice_indices(PySliceObject* self, PyObject* len)
297 {
298 Py_ssize_t ilen, start, stop, step;
299
300 ilen = PyNumber_AsSsize_t(len, PyExc_OverflowError);
301
302 if (ilen == -1 && PyErr_Occurred()) {
303 return NULL;
304 }
305
306 if (_PySlice_Unpack((PyObject *)self, &start, &stop, &step) < 0) {
307 return NULL;
308 }
309 _PySlice_AdjustIndices(ilen, &start, &stop, step);
310
311 return Py_BuildValue("(nnn)", start, stop, step);
312 }
313
314 PyDoc_STRVAR(slice_indices_doc,
315 "S.indices(len) -> (start, stop, stride)\n\
316 \n\
317 Assuming a sequence of length len, calculate the start and stop\n\
318 indices, and the stride length of the extended slice described by\n\
319 S. Out of bounds indices are clipped in a manner consistent with the\n\
320 handling of normal slices.");
321
322 static PyObject *
slice_reduce(PySliceObject * self)323 slice_reduce(PySliceObject* self)
324 {
325 return Py_BuildValue("O(OOO)", Py_TYPE(self), self->start, self->stop, self->step);
326 }
327
328 PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
329
330 static PyMethodDef slice_methods[] = {
331 {"indices", (PyCFunction)slice_indices,
332 METH_O, slice_indices_doc},
333 {"__reduce__", (PyCFunction)slice_reduce,
334 METH_NOARGS, reduce_doc},
335 {NULL, NULL}
336 };
337
338 static int
slice_compare(PySliceObject * v,PySliceObject * w)339 slice_compare(PySliceObject *v, PySliceObject *w)
340 {
341 int result = 0;
342
343 if (v == w)
344 return 0;
345
346 if (PyObject_Cmp(v->start, w->start, &result) < 0)
347 return -2;
348 if (result != 0)
349 return result;
350 if (PyObject_Cmp(v->stop, w->stop, &result) < 0)
351 return -2;
352 if (result != 0)
353 return result;
354 if (PyObject_Cmp(v->step, w->step, &result) < 0)
355 return -2;
356 return result;
357 }
358
359 static long
slice_hash(PySliceObject * v)360 slice_hash(PySliceObject *v)
361 {
362 PyErr_SetString(PyExc_TypeError, "unhashable type");
363 return -1L;
364 }
365
366 static int
slice_traverse(PySliceObject * v,visitproc visit,void * arg)367 slice_traverse(PySliceObject *v, visitproc visit, void *arg)
368 {
369 Py_VISIT(v->start);
370 Py_VISIT(v->stop);
371 Py_VISIT(v->step);
372 return 0;
373 }
374
375 PyTypeObject PySlice_Type = {
376 PyVarObject_HEAD_INIT(&PyType_Type, 0)
377 "slice", /* Name of this type */
378 sizeof(PySliceObject), /* Basic object size */
379 0, /* Item size for varobject */
380 (destructor)slice_dealloc, /* tp_dealloc */
381 0, /* tp_print */
382 0, /* tp_getattr */
383 0, /* tp_setattr */
384 (cmpfunc)slice_compare, /* tp_compare */
385 (reprfunc)slice_repr, /* tp_repr */
386 0, /* tp_as_number */
387 0, /* tp_as_sequence */
388 0, /* tp_as_mapping */
389 (hashfunc)slice_hash, /* tp_hash */
390 0, /* tp_call */
391 0, /* tp_str */
392 PyObject_GenericGetAttr, /* tp_getattro */
393 0, /* tp_setattro */
394 0, /* tp_as_buffer */
395 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
396 slice_doc, /* tp_doc */
397 (traverseproc)slice_traverse, /* tp_traverse */
398 0, /* tp_clear */
399 0, /* tp_richcompare */
400 0, /* tp_weaklistoffset */
401 0, /* tp_iter */
402 0, /* tp_iternext */
403 slice_methods, /* tp_methods */
404 slice_members, /* tp_members */
405 0, /* tp_getset */
406 0, /* tp_base */
407 0, /* tp_dict */
408 0, /* tp_descr_get */
409 0, /* tp_descr_set */
410 0, /* tp_dictoffset */
411 0, /* tp_init */
412 0, /* tp_alloc */
413 slice_new, /* tp_new */
414 };
415