Skip Montanaro's patch, SF 559833, exposing xrange type in builtins.

Also, added more regression tests to cover the new type and test its
conformity with range().

4 files changed, 91 insertions, 46 deletions

diff --git a/Lib/test/test_b2.py b/Lib/test/test_b2.py
index 459fd6b..a8bc22a 100644
--- a/Lib/test/test_b2.py
+++ b/Lib/test/test_b2.py
@@ -295,6 +295,11 @@ if tuple(xrange(10)) != tuple(range(10)): raise TestFailed, 'xrange(10)'
 if tuple(xrange(5,10)) != tuple(range(5,10)): raise TestFailed, 'xrange(5,10)'
 if tuple(xrange(0,10,2)) != tuple(range(0,10,2)):
     raise TestFailed, 'xrange(0,10,2)'
+x = xrange(10); a = iter(x); b = iter(a)  # test clearing of SF bug 564601
+if id(x) == id(a): raise TestFailed, "xrange doesn't have a separate iterator"
+if id(a) != id(b): raise TestFailed, "xrange iterator not behaving like range"
+if type(x) != xrange: raise TestFailed, "xrange type not exposed"  # SF 559833
+if list(x) != list(x): raise TestFailed, "xrange should be restartable"
 
 print 'zip'
 a = (1, 2, 3)
diff --git a/Lib/types.py b/Lib/types.py
index 0d51743..da0e597 100644
--- a/Lib/types.py
+++ b/Lib/types.py
@@ -62,7 +62,7 @@ BuiltinMethodType = type([].append)     # Same as BuiltinFunctionType
 
 ModuleType = type(sys)
 FileType = file
-XRangeType = type(xrange(0))
+XRangeType = xrange
 
 try:
     raise TypeError
diff --git a/Objects/rangeobject.c b/Objects/rangeobject.c
index 002f94a..0ac4687 100644
--- a/Objects/rangeobject.c
+++ b/Objects/rangeobject.c
@@ -47,6 +47,76 @@ PyRange_New(long start, long len, long step, int reps)
 	return (PyObject *) obj;
 }
 
+/* Return number of items in range/xrange (lo, hi, step).  step > 0
+ * required.  Return a value < 0 if & only if the true value is too
+ * large to fit in a signed long.
+ */
+static long
+get_len_of_range(long lo, long hi, long step)
+{
+	/* -------------------------------------------------------------
+	If lo >= hi, the range is empty.
+	Else if n values are in the range, the last one is
+	lo + (n-1)*step, which must be <= hi-1.  Rearranging,
+	n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives
+	the proper value.  Since lo < hi in this case, hi-lo-1 >= 0, so
+	the RHS is non-negative and so truncation is the same as the
+	floor.  Letting M be the largest positive long, the worst case
+	for the RHS numerator is hi=M, lo=-M-1, and then
+	hi-lo-1 = M-(-M-1)-1 = 2*M.  Therefore unsigned long has enough
+	precision to compute the RHS exactly.
+	---------------------------------------------------------------*/
+	long n = 0;
+	if (lo < hi) {
+		unsigned long uhi = (unsigned long)hi;
+		unsigned long ulo = (unsigned long)lo;
+		unsigned long diff = uhi - ulo - 1;
+		n = (long)(diff / (unsigned long)step + 1);
+	}
+	return n;
+}
+
+static PyObject *
+range_new(PyTypeObject *type, PyObject *args, PyObject *kw)
+{
+	long ilow = 0, ihigh = 0, istep = 1;
+	long n;
+
+	if (PyTuple_Size(args) <= 1) {
+		if (!PyArg_ParseTuple(args,
+				"l;xrange() requires 1-3 int arguments",
+				&ihigh))
+			return NULL;
+	}
+	else {
+		if (!PyArg_ParseTuple(args,
+				"ll|l;xrange() requires 1-3 int arguments",
+				&ilow, &ihigh, &istep))
+			return NULL;
+	}
+	if (istep == 0) {
+		PyErr_SetString(PyExc_ValueError, "xrange() arg 3 must not be zero");
+		return NULL;
+	}
+	if (istep > 0)
+		n = get_len_of_range(ilow, ihigh, istep);
+	else
+		n = get_len_of_range(ihigh, ilow, -istep);
+	if (n < 0) {
+		PyErr_SetString(PyExc_OverflowError,
+				"xrange() result has too many items");
+		return NULL;
+	}
+	return PyRange_New(ilow, n, istep, 1);
+}
+
+static char range_doc[] =
+"xrange([start,] stop[, step]) -> xrange object\n\
+\n\
+Like range(), but instead of returning a list, returns an object that\n\
+generates the numbers in the range on demand.  This is slightly slower\n\
+than range() but more memory efficient.";
+
 static PyObject *
 range_item(rangeobject *r, int i)
 {
@@ -118,12 +188,24 @@ PyTypeObject PyRange_Type = {
 	0,				/* tp_setattro */
 	0,				/* tp_as_buffer */
 	Py_TPFLAGS_DEFAULT,		/* tp_flags */
-	0,				/* tp_doc */
+	range_doc,			/* tp_doc */
 	0,				/* tp_traverse */
 	0,				/* tp_clear */
 	0,				/* tp_richcompare */
 	0,				/* tp_weaklistoffset */
-	(getiterfunc)range_iter,	/* tp_iter */	
+	(getiterfunc)range_iter,	/* tp_iter */
+	0,				/* tp_iternext */
+	0,				/* tp_methods */	
+	0,				/* 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 */
 };
 
 /*********************** Xrange Iterator **************************/
diff --git a/Python/bltinmodule.c b/Python/bltinmodule.c
index fba1b49..5aa6bc7 100644
--- a/Python/bltinmodule.c
+++ b/Python/bltinmodule.c
@@ -1365,48 +1365,6 @@ These are exactly the valid indices for a list of 4 elements.";
 
 
 static PyObject *
-builtin_xrange(PyObject *self, PyObject *args)
-{
-	long ilow = 0, ihigh = 0, istep = 1;
-	long n;
-
-	if (PyTuple_Size(args) <= 1) {
-		if (!PyArg_ParseTuple(args,
-				"l;xrange() requires 1-3 int arguments",
-				&ihigh))
-			return NULL;
-	}
-	else {
-		if (!PyArg_ParseTuple(args,
-				"ll|l;xrange() requires 1-3 int arguments",
-				&ilow, &ihigh, &istep))
-			return NULL;
-	}
-	if (istep == 0) {
-		PyErr_SetString(PyExc_ValueError, "xrange() arg 3 must not be zero");
-		return NULL;
-	}
-	if (istep > 0)
-		n = get_len_of_range(ilow, ihigh, istep);
-	else
-		n = get_len_of_range(ihigh, ilow, -istep);
-	if (n < 0) {
-		PyErr_SetString(PyExc_OverflowError,
-				"xrange() result has too many items");
-		return NULL;
-	}
-	return PyRange_New(ilow, n, istep, 1);
-}
-
-static char xrange_doc[] =
-"xrange([start,] stop[, step]) -> xrange object\n\
-\n\
-Like range(), but instead of returning a list, returns an object that\n\
-generates the numbers in the range on demand.  This is slightly slower\n\
-than range() but more memory efficient.";
-
-
-static PyObject *
 builtin_raw_input(PyObject *self, PyObject *args)
 {
 	PyObject *v = NULL;
@@ -1860,7 +1818,6 @@ static PyMethodDef builtin_methods[] = {
  	{"unichr",	builtin_unichr,     METH_VARARGS, unichr_doc},
 #endif
  	{"vars",	builtin_vars,       METH_VARARGS, vars_doc},
- 	{"xrange",	builtin_xrange,     METH_VARARGS, xrange_doc},
   	{"zip",         builtin_zip,        METH_VARARGS, zip_doc},
 	{NULL,		NULL},
 };
@@ -1909,6 +1866,7 @@ _PyBuiltin_Init(void)
 	SETBUILTIN("super",		&PySuper_Type);
 	SETBUILTIN("tuple",		&PyTuple_Type);
 	SETBUILTIN("type",		&PyType_Type);
+	SETBUILTIN("xrange",		&PyRange_Type);
 
 	/* Note that open() is just an alias of file(). */
 	SETBUILTIN("open",		&PyFile_Type);