<br>I updated the patches destined for the trunk (slice-object support for all objects that supported simple slicing, and actual extended slicing support for most of them) and checked them in. Next stop is cleaning up the actual slice-removal bits. I do have two remaining issues: what do we do about PyMapping_Check(), and should I make the post an actual PEP? I'm thinking PyMapping_Check() should be removed, or made to look at tp_as_sequence->sq_item instead of tp_as_sequence->sq_slice and deprecated. I also think this change should be documented in an actual PEP, as it'll be a pretty big change for any C extension implementing simple slices but not slice-object support.
<br><br><div><span class="gmail_quote">On 8/24/07, <b class="gmail_sendername">Thomas Wouters</b> <<a href="mailto:thomas@python.org">thomas@python.org</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>I did some work at last year's Google sprint on removing the simple slicing API (__getslice__, tp_as_sequence->sq_slice) in favour of the more flexible sliceobject API (__getitem__ and tp_as_mapping->mp_subscript using slice objects as index.) For some more detail, see the semi-PEP below. (I hesitate to call it a PEP because it's way past the Py3k PEP deadline, but the email I was originally going to send on this subject grew in such a size that I figured I might as well use PEP layout and use the opportunity to record some best practices and behaviour. And the change should probably be recorded in a PEP anyway, even though it has never been formally proposed, just taken as a given.)
<br><br>If anyone is bored and/or interested in doing some complicated work, there is still a bit of (optional) work to be done in this area: I uploaded patches to be applied to the trunk SF 8 months ago -- extended slicing support for a bunch of types. Some of that extended slicing support is limited to step-1 slices, though, most notably
UserString.MutableString and ctypes. I can guarantee adding non-step-1 support to them is a challenging and fulfilling exercise, having done it for several types, but I can't muster the intellectual stamina to do it for these (to me) fringe types. The patches can be found in Roundup:
<a href="http://bugs.python.org/issue?%40search_text=&title=&%40columns=title&id=&%40columns=id&creation=&creator=twouters&activity=&%40columns=activity&%40sort=activity&actor=&type=&components=&versions=&severity=&dependencies=&assignee=&keywords=&priority=&%40group=priority&status=1&%40columns=status&resolution=&%40pagesize=50&%40startwith=0&%40action=search" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
http://bugs.python.org/issue?%40search_text=&title=&%40columns=title&id=&%40columns=id&creation=&creator=twouters&activity=&%40columns=activity&%40sort=activity&actor=&type=&components=&versions=&severity=&dependencies=&assignee=&keywords=&priority=&%40group=priority&status=1&%40columns=status&resolution=&%40pagesize=50&%40startwith=0&%40action=search
</a> (there doesn't seem to be a shorter URL; just search for issues created by 'twouters' instead.)<br clear="all"><br>If nobody cares, I will be checking these patches into the trunk this weekend (after updating them), and then update and check in the rest of the p3yk-noslice branch into the py3k branch.
<br><br>Abstract<br>========<br><br>This proposal discusses getting rid of the two types of slicing Python uses,<br>``simple`` and ``extended``. Extended slicing was added later, and uses a<br>different API at both the C and the Python level for backward compatibility.
<br>Extended slicing can express everything simple slicing can express,<br>however, making the simple slicing API practically redundant.<br><br>A Tale of Two APIs<br>==================<br><br>Simple slicing is a slice operation without a step, Ellipsis or tuple of
<br>slices -- the archetypical slice of just `start` and/or `stop`, with a<br>single colon separating them and both sides being optional::<br><br> L[1:3]<br> L[2:]<br> L[:-5]<br> L[:]<br><br>An extended slice is any slice that isn't simple::
<br><br> L[1:5:2]<br> L[1:3, 8:10]<br> L[1, ..., 5:-2]<br> L[1:3:]<br><br>(Note that the presence of an extra colon in the last example makes the very<br>first simple slice an extended slice, but otherwise expresses the exact same
<br>slicing operation.)<br><br>In applying a simple slice, Python does the work of translating omitted, out<br>of bounds or negative indices into the appropriate actual indices, based on<br>the length of the sequence. The normalized ``start`` and ``stop`` indices
<br>are then passed to the appropriate method: ``__getslice__``,<br>``__setslice__`` or ``__delslice__`` for Python classes,<br>``tp_as_sequence``'s ``sq_slice`` or ``sq_ass_slice`` for C types.<br><br>For extended slicing, no special handling of slice indices is done. The
<br>indices in ``start:stop:step`` are wrapped in a ``slice`` object, with<br>missing indices represented as None. The indices are otherwise taken as-is.<br>The sequence object is then indexed with the slice object as if it were a
<br>mapping: ``__getitem__``,`` __setitem__`` or ``__delitem__`` for Python<br>classes, ``tp_as_mapping``'s ``mp_subscript`` or ``mp_ass_subscript``.<br>It is entirely up to the sequence to interpret the meaning of missing, out
<br>of bounds or negative indices, let alone non-numerical indices like tuples<br>or Ellipsis or arbitrary objects. <br><br>Since at least Python 2.1, applying a simple slice to an object that does not<br>implement the simple slicing API will fall back to using extended slicing,
<br>calling __getitem__ (or mp_subscript) instead of __getslice__ (or sq_slice),<br>and similarly for slice assignment/deletion.<br><br>Problems<br>========<br><br>Aside from the obvious disadvantage of having two ways to do the same thing,
<br>simple slicing is an inconvenient wart for several reasons:<br><br> 1) It (passively) promotes supporting only simple slicing, as observed by<br> the builtin types only supporting extended slicing many years after
<br>
extended slicing was introduced.<br><br> 2) The Python VM dedicates 12 of its opcodes, about 11%, to support<br> simple slicing, and effectively reserves another 13 for code<br> convenience. Reducing the Big Switch in the bytecode interpreter
<br> would certainly not hurt Python performance.<br><br> 5) The same goes for the number of functions, macros and function-pointers<br> supporting simple slicing, although the impact would be maintainability<br> and readability of the source rather than performance.
<br><br>Proposed Solution<br>=================<br><br>The proposed solution, as implemented in the p3yk-noslice SVN branch, gets<br>rid of the simple slicing methods and PyType entries. The simple C API<br>(using ``Py_ssize_t`` for start and stop) remains, but creates a slice
<br>object as necessary instead. Various types had to be updated to support<br>slice objects, or improve the simple slicing case of extended slicing.<br><br>The result is that ``__getslice__``, ``__setslice__`` and ``__delslice__`` are no longer
<br>called in any situation. Classes that delegate ``__getitem__`` (or the C<br>equivalent) to a sequence type get any slicing behaviour of that type for<br>free. Classes that implement their own slicing will have to be modified to
<br>accept slice objects and process the indices themselves. This means that at<br>the C level, like is already the case at the Python level, the same method<br>is used for mapping-like access as for slicing. C types will still want to
<br>implement ``tp_as_sequence->sq_item``, but that function will only be called<br>when using the ``PySequence_*Item()`` API. Those API functions do not (yet) fall<br>back to using ``tp_as_mapping->mp_subscript``, although they possibly should.
<br><br>A casualty of this change is ``PyMapping_Check()``. It used to check for<br>``tp_as_mapping`` being available, and was modified to check for<br>``tp_as_mapping`` but *not* ``tp_as_sequence->sq_slice`` when extended
<br>slicing was added to the builtin types. It could conceivably check for<br>``tp_as_sequence->sq_item`` instead of ``sq_slice``, but the added value is<br>unclear (especially considering ABCs.) In the standard library and CPython
<br>itself, ``PyMapping_Check()`` is used mostly to provide early errors, for<br>instance by checking the arguments to ``exec()``.<br><br>Alternate Solution<br>------------------<br><br>A possible alternative to removing simple slicing completely, would be to
<br>introduce a new typestruct hook, with the same signature as<br>``tp_as_mapping->mp_subscript``, which would be called for slicing<br>operations. All as-mapping index operations would have to fall back to this<br>new ``sq_extended_slice`` hook, in order for ``seq[slice(...)]`` to work as
<br>expected. For some added efficiency and error-checking, expressions using<br>actual slice syntax could compile into bytecodes specific for slicing (of<br>which there would only be three, instead of twelve.) This approach would
<br>simplify C types wanting to support extended slicing but not<br>arbitrary-object indexing (and vice-versa) somewhat, but the benefit seems<br>too small to warrant the added complexity in the CPython runtime itself.<br>
<br><br>Implementing Extended Slicing<br>=============================<br><br>Supporting extended slicing in C types is not as easily done as supporting<br>simple slicing. There are a number of edgecases in interpreting the odder
<br>combinations of ``start``, ``stop`` and ``step``. This section tries to give<br>some explanations and best practices.<br><br>Extended Slicing in C<br>---------------------<br><br>Because the mapping API takes precedence over the sequence API, any
<br>``tp_as_mapping->mp_subscript`` and ``tp_as_mapping->mp_ass_subscript``<br>functions need to proper typechecks on their argument. In Python 2.5 and<br>later, this is best done using ``PyIndex_Check()`` and ``PySlice_Check()``
<br>(and possibly ``PyTuple_Check()`` and comparison against ``Py_Ellipsis``.)<br>For compatibility with Python 2.4 and earlier, ``PyIndex_Check()`` would<br>have to be replaced with ``PyInt_Check()`` and ``PyLong_Check()``.
<br><br>Indices that pass ``PyIndex_Check()`` should be converted to a<br>``Py_ssize_t`` using ``PyIndex_AsSsizeT()`` and delegated to<br>``tp_as_sequence->sq_item``. (For compatibility with Python 2.4, use<br>``PyNumber_AsLong()`` and downcast to an ``int`` instead.)
<br><br>The exact meaning of tuples of slices, and of Ellipsis, is up to the type,<br>as no standard-library types support it. It may be useful to use the same<br>convention as the Numpy package. Slices inside tuples, if supported, should
<br>probably follow the same rules as direct slices.<br><br>From slice objects, correct indices can be extracted with<br>``PySlice_GetIndicesEx()``. Negative and out-of-bounds indices will be<br>adjusted based on the provided length, but a negative ``step``, and a
<br>``stop`` before a ``step`` are kept as-is. This means that, for a getslice<br>operation, a simple for-loop can be used to visit the correct items in the<br>correct order::<br><br> for (cur = start, i = 0; i < slicelength; cur += step, i++)
<br> dest[i] = src[cur];<br><br><br>If ``PySlice_GetIndicesEx()`` is not appropriate, the individual indices can<br>be extracted from the ``PySlice`` object. If the indices are to be converted<br>to C types, that should be done using ``PyIndex_Check()``,
<br>``PyIndex_AsSsizeT()`` and the ``Py_ssize_t`` type, except that ``None``<br>should be accepted as the default value for the index.<br><br>For deleting slices (``mp_ass_subscript`` called with ``NULL`` as<br>value) where the order does not matter, a reverse slice can be turned into
<br>the equivalent forward slice with::<br><br> if (step < 0) {<br> stop = start + 1;<br> start = stop + step*(slicelength - 1) - 1;<br> step = -step;<br> }<br><br><br>For slice assignment with a ``step`` other than 1, it's usually necessary to
<br>require the source iterable to have the same length as the slice. When<br>assigning to a slice of length 0, care needs to be taken to select the right<br>insertion point. For a slice S[5:2], the correct insertion point is before
<br>index 5, not before index 2.<br><br>For both deleting slice and slice assignment, it is important to remember<br>arbitrary Python code may be executed when calling Py_DECREF() or otherwise<br>interacting with arbitrary objects. Because of that, it's important your
<br>datatype stays consistent throughout the operation. Either operate on a copy<br>of your datatype, or delay (for instance) Py_DECREF() calls until the<br>datatype is updated. The latter is usually done by keeping a scratchpad of
<br>to-be-DECREF'ed items.<br><br>Extended slicing in Python<br>--------------------------<br><br>The simplest way to support extended slicing in Python is by delegating to<br>an underlying type that already supports extended slicing. The class can
<br>simply index the underlying type with the slice object (or tuple) it was<br>indexed with.<br><br>Barring that, the Python code will have to pretty much apply<br>the same logic as the C type. ``PyIndex_AsSsizeT()`` is available as
<br>``operator.index()``, with a ``try/except`` block replacing<br>``PyIndex_Check()``. ``isinstance(o, slice)`` and ``sliceobj.indices()``<br>replace ``PySlice_Check()`` and ``PySlice_GetIndices()``, but the slicelength
<br>
(which is provided by ``PySlice_GetIndicesEx()``) has to be calculated<br>manually.<br><br>Testing extended slicing<br>------------------------<br><br>Proper tests of extended slicing capabilities should at least include the
<br>following (if the operations are supported), assuming a sequence of<br>length 10. Triple-colon notation is used everywhere so it uses extended<br>slicing even in Python 2.5 and earlier::<br><br> S[2:5:] (same as S[2:5])
<br> S[5:2:] (same as S[5:2], an empty slice)<br> S[::] (same as S[:], a copy of the sequence)<br> S[:2:] (same as S[:2])<br> S[:11:] (same as S[:11], a copy of the sequence)<br> S[5::] (same as S[5:])<br> S[-11::] (same as S[-11:], a copy of the sequence)
<br> S[-5:2:1] (same as S[:2])<br> S[-5:-2:2] (same as S[-5:-2], an empty slice)<br> S[5:2:-1] (the reverse of S[2:4])<br> S[-2:-5:-1] (the reverse of S[-4:-1])<br><br> S[:5:2] ([ S[0], S[2], S[4] ]))<br> S[9::2] ([ S[9] ])
<br> S[8::2] ([ S[8] ])<br> S[7::2] ([ S[7], S[9]])<br> S[1::-1] ([ S[1], S[0] ])<br> S[1:0:-1] ([ S[1] ], does not include S[0]!)<br> S[1:-1:-1] (an empty slice)<br> S[::10] ([ S[0] ])<br> S[::-10] ([ S[9] ])
<br><br> S[2:5:] = [1, 2, 3] ([ S[2], S[3], S[4] ] become [1, 2, 3])<br> S[2:5:] = [1] (S[2] becomes 1, S[3] and S[4] are deleted)<br> S[5:2:] = [1, 2, 3] ([1, 2, 3] inserted before S[5])<br> S[2:5:2] = [1, 2] ([ S[2], S[4] ] become [1, 2])
<br> S[5:2:-2] = [1, 2] ([ S[3], S[5] ] become [2, 1])<br> S[3::3] = [1, 2, 3] ([ S[3], S[6], S[9] ] become [1, 2, 3])<br> S[:-5:-2] = [1, 2] ([ S[7], S[9] ] become [2, 1])<br><br> S[::-1] = S (reverse S in-place awkwardly)
<br> S[:5:] = S (replaces S[:5] with a copy of S)<br><br> S[2:5:2] = [1, 2, 3] (error: assigning length-3 to slicelength-2)<br> S[2:5:2] = None (error: need iterable)<br><br><br>
</blockquote></div><br><br clear="all"><br>-- <br>Thomas Wouters <<a href="mailto:thomas@python.org">thomas@python.org</a>><br><br>Hi! I'm a .signature virus! copy me into your .signature file to help me spread!