range: lean and mean

Objects/rangeobject.c

 /* Range object implementation */
 
 #include "Python.h"
+#include "structmember.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)
@@ skipping 10 matching lines @@
             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.

+                                      PyObject *stop, PyObject *step);
 
 /* 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;
@@ skipping 42 matching lines @@
     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 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.

+Return 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?

- */
+/*Return number of items in range (lo, hi, step), when arguments are
+* PyLong objects. step > 0 required. Return a PyLong with the length.
+* Return NULL when there is an error.*/
 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 *diff = NULL;
@@ skipping 79 matching lines @@
         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 */
-    0,                          /* sq_item */
-    0,                          /* sq_slice */
-    0,                          /* sq_ass_item */ 
-    0,                          /* sq_ass_slice */ 
-    0,                          /* sq_contains */ 
+static PyMemberDef range_members[] = {
+    {"start", T_OBJECT, offsetof(rangeobject, start), READONLY},
+    {"stop", T_OBJECT, offsetof(rangeobject, stop), READONLY},
+    {"step", T_OBJECT, offsetof(rangeobject, step), READONLY},
+    {0}
 };
 
 static PyObject * range_iter(PyObject *seq);
 static PyObject * range_reverse(PyObject *seq);
 
 PyDoc_STRVAR(reverse_doc,
 "Returns a reverse iterator.");
+
+static PySequenceMethods range_as_sequence = {
+    (lenfunc)range_length,  /* sq_length */
+    0,                      /* sq_concat */
+    0,                      /* sq_repeat */
+    0,                      /* sq_item */
+    0,                      /* sq_slice */
+    0,                      /* sq_ass_item */
+    0,                      /* sq_ass_slice */
+    0,                      /* sq_contains */
+    0,                      /* sq_inplace_concat */
+    0,                      /* sq_inplace_repeat */
+};
 
 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 */
+        &range_as_sequence,      /* tp_as_sequence */
         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 */
-        range_getset,           /* tp_getset */

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

Please use spaces to indent the comment.

+        range_members,          /* tp_members */
+        0,                      /* tp_getset */
         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 24 matching lines @@
 rangeiter_len(rangeiterobject *r)
 {
     return PyLong_FromLong(r->len - r->index);
 }
 
 typedef struct {
     PyObject_HEAD
     PyObject *index;
     PyObject *start;
     PyObject *step;
-    PyObject *len;
+    PyObject *length;
 } longrangeiterobject;
 
 static PyObject *
 longrangeiter_len(longrangeiterobject *r, PyObject *no_args)
 {
-    return PyNumber_Subtract(r->len, r->index);
+    return PyNumber_Subtract(r->length, r->index);
 }
 
 static PyObject *rangeiter_new(PyTypeObject *, PyObject *args, PyObject *kw);
 
 PyDoc_STRVAR(length_hint_doc,
              "Private method returning an estimate of len(list(it)).");
 
 static PyMethodDef rangeiter_methods[] = {
     {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS,
         length_hint_doc},
@@ skipping 107 matching lines @@
         length_hint_doc},
     {NULL,              NULL}           /* sentinel */
 };
 
 static void
 longrangeiter_dealloc(longrangeiterobject *r)
 {
     Py_XDECREF(r->index);
     Py_XDECREF(r->start);
     Py_XDECREF(r->step);
-    Py_XDECREF(r->len);
+    Py_XDECREF(r->length);
     PyObject_Del(r);
 }
 
 static PyObject *
 longrangeiter_next(longrangeiterobject *r)
 {
     PyObject *one, *product, *new_index, *result;
-    if (PyObject_RichCompareBool(r->index, r->len, Py_LT) != 1)
+    if (PyObject_RichCompareBool(r->index, r->length, Py_LT) != 1)
         return NULL;
 
     one = PyLong_FromLong(1);
     if (!one)
         return NULL;
 
     product = PyNumber_Multiply(r->index, r->step);
     if (!product) {
         Py_DECREF(one);
         return NULL;
@@ skipping 47 matching lines @@
         (iternextfunc)longrangeiter_next,       /* tp_iternext */
         longrangeiter_methods,                  /* tp_methods */
         0,
 };
 
 static PyObject *
 range_iter(PyObject *seq)
 {
     rangeobject *r = (rangeobject *)seq;
     longrangeiterobject *it;
-    PyObject *tmp, *len;
     long lstart, lstop, lstep;
 
     assert(PyRange_Check(seq));
 
     /* If all three fields convert to long, use the int version */
     lstart = PyLong_AsLong(r->start);
     if (lstart != -1 || !PyErr_Occurred()) {
         lstop = PyLong_AsLong(r->stop);
         if (lstop != -1 || !PyErr_Occurred()) {
             lstep = PyLong_AsLong(r->step);
             if (lstep != -1 || !PyErr_Occurred())
                 return int_range_iter(lstart, lstop, lstep);
         }
     }
     /* Some conversion failed, so there is an error set. Clear it,
        and try again with a long range. */
     PyErr_Clear();
 
     it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
     if (it == NULL)
         return NULL;
 
     /* Do all initialization here, so we can DECREF on failure. */
     it->start = r->start;
     it->step = r->step;
     Py_INCREF(it->start);
     Py_INCREF(it->step);
 
-    it->len = it->index = NULL;
-
-    /* Calculate length: (r->stop - r->start) / r->step */
-    tmp = PyNumber_Subtract(r->stop, r->start);
-    if (!tmp)
-        goto create_failure;
-    len = PyNumber_FloorDivide(tmp, r->step);
-    Py_DECREF(tmp);
-    if (!len)
-        goto create_failure;
-    it->len = len;
+    Py_INCREF(r->length);
+    it->length = r->length;
     it->index = PyLong_FromLong(0);
-    if (!it->index)
+    if (it->index == NULL)
         goto create_failure;
 
     return (PyObject *)it;
 
 create_failure:
     Py_DECREF(it);
     return NULL;
 }
 
 static PyObject *
@@ skipping 28 matching lines @@
             }
         }
     }
     PyErr_Clear();
 
     it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
     if (it == NULL)
         return NULL;
 
     /* start + (len - 1) * step */
+    Py_INCREF(range->length);
     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;
 
     product = PyNumber_Multiply(len, range->step);
     if (!product)
         goto create_failure;
 
     sum = PyNumber_Add(range->start, product);
     Py_DECREF(product);
     it->start = sum;
     if (!it->start)
         goto create_failure;
     it->step = PyNumber_Negative(range->step);
     if (!it->step) {
         Py_DECREF(it->start);
         PyObject_Del(it);
         return NULL;
     }
 
     /* Steal reference to len. */
-    it->len = len;
+    it->length = len;
 
     it->index = PyLong_FromLong(0);
     if (!it->index) {
         Py_DECREF(it);
         return NULL;
     }
 
     return (PyObject *)it;
 
 create_failure:
     Py_XDECREF(len);
     PyObject_Del(it);
     return NULL;
 }