range: lean and mean

Objects/rangeobject.c

 /* Range object implementation */
 
 #include "Python.h"
 
 /* Support objects whose length is > PY_SSIZE_T_MAX.
 
    This could be sped up for small PyLongs if they fit in an Py_ssize_t.
    This only matters on Win64.  Though we could use PY_LONG_LONG which
    would presumably help perf.
 */
 
 typedef struct {
     PyObject_HEAD
     PyObject *start;
     PyObject *stop;
     PyObject *step;
+    PyObject *length;

[mvloewis_gmail.com, 2008/05/02 05:43:57]

What is the purpose of caching the length in the range
object? The iterators already have a copy of the length.

[GvR, 2008/05/02 13:52:47]

On 2008/05/02 05:43:57, mvloewis wrote:
> What is the purpose of caching the length in the range
> object? The iterators already have a copy of the length.

See line 651 -- the range_reverse() function uses it.

[Benjamin, 2008/05/02 16:56:18]

On 2008/05/02 05:43:57, mvloewis wrote:
> What is the purpose of caching the length in the range
> object? The iterators already have a copy of the length.

In the next patch, I'm also going to use it in range_iter.

 } rangeobject;
 
 /* Helper function for validating step.  Always returns a new reference or
    NULL on error. 
 */
 static PyObject *
 validate_step(PyObject *step)
 {
     /* No step specified, use a step of 1. */
     if (!step)
         return PyLong_FromLong(1);
 
     step = PyNumber_Index(step);
     if (step) {
         Py_ssize_t istep = PyNumber_AsSsize_t(step, NULL);
         if (istep == -1 && PyErr_Occurred()) {
             /* Ignore OverflowError, we know the value isn't 0. */
             PyErr_Clear();
         }
         else if (istep == 0) {
             PyErr_SetString(PyExc_ValueError,
                             "range() arg 3 must not be zero");
             Py_CLEAR(step);
         }
     }
 
     return step;
 }
+
+static PyObject* range_compute_length(PyObject *start,
+                                       PyObject *stop, PyObject *step);

[GvR, 2008/05/02 13:52:47]

This line is indented one space too many.

 
 /* XXX(nnorwitz): should we error check if the user passes any empty ranges?
    range(-10)
    range(0, -5)
    range(0, 5, -1)
 */
 static PyObject *
 range_new(PyTypeObject *type, PyObject *args, PyObject *kw)
 {
     rangeobject *obj = NULL;
-    PyObject *start = NULL, *stop = NULL, *step = NULL;
+    PyObject *start = NULL, *stop = NULL, *step = NULL, *length = NULL;
 
     if (!_PyArg_NoKeywords("range()", kw))
         return NULL;
 
     if (PyTuple_Size(args) <= 1) {
         if (!PyArg_UnpackTuple(args, "range", 1, 1, &stop))
             goto Fail;
         stop = PyNumber_Index(stop);
         if (!stop)
             goto Fail;
         start = PyLong_FromLong(0);
         step = PyLong_FromLong(1);
         if (!start || !step)
             goto Fail;
     }
     else {
         if (!PyArg_UnpackTuple(args, "range", 2, 3,
                                &start, &stop, &step))
             goto Fail;
 
         /* Convert borrowed refs to owned refs */
         start = PyNumber_Index(start);
         stop = PyNumber_Index(stop);
         step = validate_step(step);
         if (!start || !stop || !step)
             goto Fail;
     }
 
+    length = range_compute_length(start, stop, step);
+    if (length == NULL)
+        goto Fail;
     obj = PyObject_New(rangeobject, &PyRange_Type);
     if (obj == NULL)
         goto Fail;
     obj->start = start;
     obj->stop = stop;
     obj->step = step;
+    obj->length = length;
     return (PyObject *) obj;
 
 Fail:
     Py_XDECREF(start);
     Py_XDECREF(stop);
     Py_XDECREF(step);
+    Py_XDECREF(length);
     return NULL;
 }
 
 PyDoc_STRVAR(range_doc,
 "range([start,] stop[, step]) -> range object\n\
 \n\
-Returns an iterator that generates the numbers in the range on demand.");
+Returns a virtual sequence of numbers from start to stop by step.");

[GvR, 2008/05/02 13:52:47]

I really don't want to use the word sequence here.  Maybe:

Returns an arithmetic progression of numbers from start to stop (exclusive) by
step.

 
 static void
 range_dealloc(rangeobject *r)
 {
     Py_DECREF(r->start);
     Py_DECREF(r->stop);
     Py_DECREF(r->step);
+    Py_DECREF(r->length);
     PyObject_Del(r);
 }
 
 /* Return number of items in range (lo, hi, step), when arguments are
  * PyInt or PyLong objects.  step > 0 required.  Return a value < 0 if
  * & only if the true value is too large to fit in a signed long.
  * Arguments MUST return 1 with either PyLong_Check() or
  * PyLong_Check().  Return -1 when there is an error.

[GvR, 2008/05/02 13:52:47]

Not your fault, but this comment still references PyInt vs. PyLong, *and*
"either PyLong_Check() or PyLong_Check()" makes no sense (must've been
automatically changed in the past from "PyInt_Check() or PyLong_Check()").  Mind
fixing this?

  */
-static PyObject*
-range_length_obj(rangeobject *r)
+static PyObject *
+range_compute_length(PyObject *start, PyObject *stop, PyObject *step)
 {
     /* -------------------------------------------------------------
     Algorithm is equal to that of get_len_of_range(), but it operates
     on PyObjects (which are assumed to be PyLong or PyInt objects).
     ---------------------------------------------------------------*/
     int cmp_result, cmp_call;
     PyObject *lo, *hi;
-    PyObject *step = NULL;
     PyObject *diff = NULL;
     PyObject *one = NULL;
     PyObject *tmp1 = NULL, *tmp2 = NULL, *result;
                 /* holds sub-expression evaluations */
 
     PyObject *zero = PyLong_FromLong(0);
     if (zero == NULL)
         return NULL;
-    cmp_call = PyObject_Cmp(r->step, zero, &cmp_result);
+    cmp_call = PyObject_Cmp(step, zero, &cmp_result);
     Py_DECREF(zero);
     if (cmp_call == -1)
         return NULL;
 
     assert(cmp_result != 0);
     if (cmp_result > 0) {
-        lo = r->start;
-        hi = r->stop;
-        step = r->step;
+        lo = start;
+        hi = stop;
         Py_INCREF(step);
     } else {
-        lo = r->stop;
-        hi = r->start;
-        step = PyNumber_Negative(r->step);
+        lo = stop;
+        hi = start;
+        step = PyNumber_Negative(step);
         if (!step)
-            return NULL;
+            goto Fail;
     }
 
     /* if (lo >= hi), return length of 0. */
     if (PyObject_Compare(lo, hi) >= 0) {
         Py_XDECREF(step);
         return PyLong_FromLong(0);
     }
 
     if ((one = PyLong_FromLong(1L)) == NULL)
         goto Fail;
@@ skipping 22 matching lines @@
     Py_XDECREF(diff);
     Py_XDECREF(step);
     Py_XDECREF(tmp1);
     Py_XDECREF(one);
     return NULL;
 }
 
 static Py_ssize_t
 range_length(rangeobject *r)
 {
-    PyObject *len = range_length_obj(r);
-    Py_ssize_t result = -1;
-    if (len) {
-        result = PyLong_AsSsize_t(len);
-        Py_DECREF(len);
-    }
-    return result;
+    return PyLong_AsSsize_t(r->length);
 }
 
-/* range(...)[x] is necessary for:  seq[:] = range(...) */
-
-static PyObject *
-range_item(rangeobject *r, Py_ssize_t i)
-{
-    Py_ssize_t len = range_length(r);
-    PyObject *rem, *incr, *result;
-
-    /* XXX(nnorwitz): should negative indices be supported? */
-    /* XXX(nnorwitz): should support range[x] where x > PY_SSIZE_T_MAX? */
-    if (i < 0 || i >= len) {
-        if (!PyErr_Occurred())
-            PyErr_SetString(PyExc_IndexError,
-                            "range object index out of range");
-        return NULL;
-    }
-
-    /* XXX(nnorwitz): optimize for short ints. */
-    rem = PyLong_FromSsize_t(i);
-    if (!rem)
-        return NULL;
-    incr = PyNumber_Multiply(rem, r->step);
-    Py_DECREF(rem);
-    if (!incr)
-        return NULL;
-    result = PyNumber_Add(r->start, incr);
-    Py_DECREF(incr);
-    return result;
-}
 
 static PyObject *
 range_repr(rangeobject *r)
 {
     Py_ssize_t istep;
 
     /* Check for special case values for printing.  We don't always
        need the step value.  We don't care about errors
        (it means overflow), so clear the errors. */
     istep = PyNumber_AsSsize_t(r->step, NULL);
     if (istep != 1 || (istep == -1 && PyErr_Occurred())) {
         PyErr_Clear();
     }
 
     if (istep == 1)
         return PyUnicode_FromFormat("range(%R, %R)", r->start, r->stop);
     else
         return PyUnicode_FromFormat("range(%R, %R, %R)",
                                     r->start, r->stop, r->step);
 }
 
+static PyObject *
+range_getstart(rangeobject *obj)
+{
+    return obj->start;
+}
+
+static PyObject *
+range_getstop(rangeobject *obj)
+{
+    return obj->stop;
+}
+
+static PyObject *
+range_getstep(rangeobject *obj)
+{
+    return obj->step;
+}
+
+static PyGetSetDef range_getset[] = {
+    {"start", (getter)range_getstart, NULL, "The start of the range"},
+    {"stop", (getter)range_getstop, NULL, "Where the range stops."},
+    {"step", (getter)range_getstep, NULL, "How much the range jumps."},
+    {0},
+};
+
 static PySequenceMethods range_as_sequence = {
     (lenfunc)range_length,      /* sq_length */

[GvR, 2008/05/02 13:52:47]

The latest discussion on the list suggests to remove __len__ and instead make
this value available as __length_hint__ (or whatever the magic method is).

-    0,                  /* sq_concat */
-    0,                  /* sq_repeat */
-    (ssizeargfunc)range_item, /* sq_item */
-    0,                  /* sq_slice */
+    0,                          /* sq_concat */
+    0,                          /* sq_repeat */
+    0,                          /* sq_item */
+    0,                          /* sq_slice */
+    0,                          /* sq_ass_item */ 
+    0,                          /* sq_ass_slice */ 
+    0,                          /* sq_contains */ 
 };
 
 static PyObject * range_iter(PyObject *seq);
 static PyObject * range_reverse(PyObject *seq);
 
 PyDoc_STRVAR(reverse_doc,
 "Returns a reverse iterator.");
 
 static PyMethodDef range_methods[] = {
     {"__reversed__",    (PyCFunction)range_reverse, METH_NOARGS,
         reverse_doc},
     {NULL,              NULL}           /* sentinel */
 };
 
 PyTypeObject PyRange_Type = {
         PyVarObject_HEAD_INIT(&PyType_Type, 0)
         "range",                /* Name of this type */
         sizeof(rangeobject),    /* Basic object size */
         0,                      /* Item size for varobject */
         (destructor)range_dealloc, /* tp_dealloc */
         0,                      /* tp_print */
         0,                      /* tp_getattr */
         0,                      /* tp_setattr */
         0,                      /* tp_compare */
         (reprfunc)range_repr,   /* tp_repr */
         0,                      /* tp_as_number */
         &range_as_sequence,     /* tp_as_sequence */
-        0,                      /* tp_as_mapping */
+        0,                      /* tp_as_mapping */
         0,                      /* tp_hash */
         0,                      /* tp_call */
         0,                      /* tp_str */
         PyObject_GenericGetAttr,  /* tp_getattro */
         0,                      /* tp_setattro */
         0,                      /* tp_as_buffer */
         Py_TPFLAGS_DEFAULT,     /* tp_flags */
         range_doc,              /* tp_doc */
         0,                      /* tp_traverse */
         0,                      /* tp_clear */
         0,                      /* tp_richcompare */
         0,                      /* tp_weaklistoffset */
         range_iter,             /* tp_iter */
         0,                      /* tp_iternext */
         range_methods,          /* tp_methods */
         0,                      /* tp_members */
-        0,                      /* tp_getset */
+        range_getset,           /* tp_getset */

[GvR, 2008/05/02 13:52:47]

Please use spaces to indent the comment.

         0,                      /* tp_base */
         0,                      /* tp_dict */
         0,                      /* tp_descr_get */
         0,                      /* tp_descr_set */
         0,                      /* tp_dictoffset */
         0,                      /* tp_init */
         0,                      /* tp_alloc */
         range_new,              /* tp_new */
 };
 
@@ skipping 324 matching lines @@
             }
         }
     }
     PyErr_Clear();
 
     it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
     if (it == NULL)
         return NULL;
 
     /* start + (len - 1) * step */
-    len = range_length_obj(range);
-    if (!len)
-        goto create_failure;
+    len = range->length;
 
     one = PyLong_FromLong(1);
     if (!one)
         goto create_failure;
 
     diff = PyNumber_Subtract(len, one);
     Py_DECREF(one);
     if (!diff)
         goto create_failure;
 
@@ skipping 22 matching lines @@
         return NULL;
     }
 
     return (PyObject *)it;
 
 create_failure:
     Py_XDECREF(len);
     PyObject_Del(it);
     return NULL;
 }