SF bug 433228: repr(list) woes when len(list) big.

Gave Python linear-time repr() implementations for dicts, lists, strings.
This means, e.g., that repr(range(50000)) is no longer 50x slower than
pprint.pprint() in 2.2 <wink>.

I don't consider this a bugfix candidate, as it's a performance boost.

Added _PyString_Join() to the internal string API.  If we want that in the
public API, fine, but then it requires runtime error checks instead of
asserts.

5 files changed, 193 insertions, 56 deletions

diff --git a/Include/stringobject.h b/Include/stringobject.h
index fbcff314d1..96f371ee7e 100644
--- a/Include/stringobject.h
+++ b/Include/stringobject.h
@@ -77,6 +77,10 @@ extern DL_IMPORT(void) _Py_ReleaseInternedStrings(void);
 #define PyString_AS_STRING(op) (((PyStringObject *)(op))->ob_sval)
 #define PyString_GET_SIZE(op)  (((PyStringObject *)(op))->ob_size)
 
+/* _PyString_Join(sep, x) is like sep.join(x).  sep must be PyStringObject*,
+   x must be an iterable object. */
+extern DL_IMPORT(PyObject *) _PyString_Join(PyObject *sep, PyObject *x);
+
 /* --- Generic Codecs ----------------------------------------------------- */
 
 /* Create an object by decoding the encoded string s of the
diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 21cc6c6ce1..42bfd40213 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -809,42 +809,80 @@ dict_print(register dictobject *mp, register FILE *fp, register int flags)
 static PyObject *
 dict_repr(dictobject *mp)
 {
-	auto PyObject *v;
-	PyObject *sepa, *colon;
-	register int i;
-	register int any;
+	int i, pos;
+	PyObject *s, *temp, *colon = NULL;
+	PyObject *pieces = NULL, *result = NULL;
+	PyObject *key, *value;
 
-	i = Py_ReprEnter((PyObject*)mp);
+	i = Py_ReprEnter((PyObject *)mp);
 	if (i != 0) {
-		if (i > 0)
-			return PyString_FromString("{...}");
-		return NULL;
+		return i > 0 ? PyString_FromString("{...}") : NULL;
 	}
 
-	v = PyString_FromString("{");
-	sepa = PyString_FromString(", ");
-	colon = PyString_FromString(": ");
-	any = 0;
-	for (i = 0; i <= mp->ma_mask && v; i++) {
-		dictentry *ep = mp->ma_table + i;
-		PyObject *pvalue = ep->me_value;
-		if (pvalue != NULL) {
-			/* Prevent PyObject_Repr from deleting value during
-			   key format */
-			Py_INCREF(pvalue);
-			if (any++)
-				PyString_Concat(&v, sepa);
-			PyString_ConcatAndDel(&v, PyObject_Repr(ep->me_key));
-			PyString_Concat(&v, colon);
-			PyString_ConcatAndDel(&v, PyObject_Repr(pvalue));
-			Py_DECREF(pvalue);
-		}
+	if (mp->ma_used == 0) {
+		result = PyString_FromString("{}");
+		goto Done;
 	}
-	PyString_ConcatAndDel(&v, PyString_FromString("}"));
-	Py_ReprLeave((PyObject*)mp);
-	Py_XDECREF(sepa);
+
+	pieces = PyList_New(0);
+	if (pieces == NULL)
+		goto Done;
+
+	colon = PyString_FromString(": ");
+	if (colon == NULL)
+		goto Done;
+
+	/* Do repr() on each key+value pair, and insert ": " between them.
+	   Note that repr may mutate the dict. */
+	pos = 0;
+	while (PyDict_Next((PyObject *)mp, &pos, &key, &value)) {
+		int status;
+		/* Prevent repr from deleting value during key format. */
+		Py_INCREF(value);
+		s = PyObject_Repr(key);
+		PyString_Concat(&s, colon);
+		PyString_ConcatAndDel(&s, PyObject_Repr(value));
+		Py_DECREF(value);
+		if (s == NULL)
+			goto Done;
+		status = PyList_Append(pieces, s);
+		Py_DECREF(s);  /* append created a new ref */
+		if (status < 0)
+			goto Done;
+	}
+
+	/* Add "{}" decorations to the first and last items. */
+	assert(PyList_GET_SIZE(pieces) > 0);
+	s = PyString_FromString("{");
+	if (s == NULL)
+		goto Done;
+	temp = PyList_GET_ITEM(pieces, 0);
+	PyString_ConcatAndDel(&s, temp);
+	PyList_SET_ITEM(pieces, 0, s);
+	if (s == NULL)
+		goto Done;
+
+	s = PyString_FromString("}");
+	if (s == NULL)
+		goto Done;
+	temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
+	PyString_ConcatAndDel(&temp, s);
+	PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
+	if (temp == NULL)
+		goto Done;
+
+	/* Paste them all together with ", " between. */
+	s = PyString_FromString(", ");
+	if (s == NULL)
+		goto Done;
+	result = _PyString_Join(s, pieces);
+	Py_DECREF(s);	
+
+Done:
+	Py_XDECREF(pieces);
 	Py_XDECREF(colon);
-	return v;
+	Py_ReprLeave((PyObject *)mp);
+	return result;
 }
 
 static int
diff --git a/Objects/listobject.c b/Objects/listobject.c
index e595c85082..6fb3145d36 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -246,26 +246,68 @@ list_print(PyListObject *op, FILE *fp, int flags)
 static PyObject *
 list_repr(PyListObject *v)
 {
-	PyObject *s, *comma;
 	int i;
+	PyObject *s, *temp;
+	PyObject *pieces = NULL, *result = NULL;
 
 	i = Py_ReprEnter((PyObject*)v);
 	if (i != 0) {
-		if (i > 0)
-			return PyString_FromString("[...]");
-		return NULL;
+		return i > 0 ? PyString_FromString("[...]") : NULL;
 	}
-	s = PyString_FromString("[");
-	comma = PyString_FromString(", ");
-	for (i = 0; i < v->ob_size && s != NULL; i++) {
-		if (i > 0)
-			PyString_Concat(&s, comma);
-		PyString_ConcatAndDel(&s, PyObject_Repr(v->ob_item[i]));
+
+	if (v->ob_size == 0) {
+		result = PyString_FromString("[]");
+		goto Done;
 	}
-	Py_XDECREF(comma);
-	PyString_ConcatAndDel(&s, PyString_FromString("]"));
+
+	pieces = PyList_New(0);
+	if (pieces == NULL)
+		goto Done;
+
+	/* Do repr() on each element.  Note that this may mutate the list,
+	   so must refetch the list size on each iteration. */
+	for (i = 0; i < v->ob_size; ++i) {
+		int status;
+		s = PyObject_Repr(v->ob_item[i]);
+		if (s == NULL)
+			goto Done;
+		status = PyList_Append(pieces, s);
+		Py_DECREF(s);  /* append created a new ref */
+		if (status < 0)
+			goto Done;
+	}
+
+	/* Add "[]" decorations to the first and last items. */
+	assert(PyList_GET_SIZE(pieces) > 0);
+	s = PyString_FromString("[");
+	if (s == NULL)
+		goto Done;
+	temp = PyList_GET_ITEM(pieces, 0);
+	PyString_ConcatAndDel(&s, temp);
+	PyList_SET_ITEM(pieces, 0, s);
+	if (s == NULL)
+		goto Done;
+
+	s = PyString_FromString("]");
+	if (s == NULL)
+		goto Done;
+	temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
+	PyString_ConcatAndDel(&temp, s);
+	PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
+	if (temp == NULL)
+		goto Done;
+
+	/* Paste them all together with ", " between. */
+	s = PyString_FromString(", ");
+	if (s == NULL)
+		goto Done;
+	result = _PyString_Join(s, pieces);
+	Py_DECREF(s);	
+
+Done:
+	Py_XDECREF(pieces);
 	Py_ReprLeave((PyObject *)v);
-	return s;
+	return result;
 }
 
 static int
diff --git a/Objects/stringobject.c b/Objects/stringobject.c
index bcf51474ec..24443d8323 100644
--- a/Objects/stringobject.c
+++ b/Objects/stringobject.c
@@ -1031,6 +1031,23 @@ string_join(PyStringObject *self, PyObject *args)
 	return res;
 }
 
+PyObject *_PyString_Join(PyObject *sep, PyObject *x)
+{
+	PyObject* args;
+	PyObject* result = NULL;
+
+	assert(sep != NULL && PyString_Check(sep));
+	assert(x != NULL);
+	args = PyTuple_New(1);
+	if (args != NULL) {
+		Py_INCREF(x);
+		PyTuple_SET_ITEM(args, 0, x);
+		result = string_join((PyStringObject *)sep, args);
+		Py_DECREF(args);
+	}
+	return result;
+}
+
 static long
 string_find_internal(PyStringObject *self, PyObject *args, int dir)
 {
diff --git a/Objects/tupleobject.c b/Objects/tupleobject.c
index 17ec1a0183..538cc704d2 100644
--- a/Objects/tupleobject.c
+++ b/Objects/tupleobject.c
@@ -184,20 +184,56 @@ tupleprint(PyTupleObject *op, FILE *fp, int flags)
 static PyObject *
 tuplerepr(PyTupleObject *v)
 {
-	PyObject *s, *comma;
-	int i;
+	int i, n;
+	PyObject *s, *temp;
+	PyObject *pieces, *result = NULL;
+
+	n = v->ob_size;
+	if (n == 0)
+		return PyString_FromString("()");
+
+	pieces = PyTuple_New(n);
+	if (pieces == NULL)
+		return NULL;
+
+	/* Do repr() on each element. */
+	for (i = 0; i < n; ++i) {
+		s = PyObject_Repr(v->ob_item[i]);
+		if (s == NULL)
+			goto Done;
+		PyTuple_SET_ITEM(pieces, i, s);
+	}
+
+	/* Add "()" decorations to the first and last items. */
+	assert(n > 0);
 	s = PyString_FromString("(");
-	comma = PyString_FromString(", ");
-	for (i = 0; i < v->ob_size && s != NULL; i++) {
-		if (i > 0)
-			PyString_Concat(&s, comma);
-		PyString_ConcatAndDel(&s, PyObject_Repr(v->ob_item[i]));
-	}
-	Py_DECREF(comma);
-	if (v->ob_size == 1)
-		PyString_ConcatAndDel(&s, PyString_FromString(","));
-	PyString_ConcatAndDel(&s, PyString_FromString(")"));
-	return s;
+	if (s == NULL)
+		goto Done;
+	temp = PyTuple_GET_ITEM(pieces, 0);
+	PyString_ConcatAndDel(&s, temp);
+	PyTuple_SET_ITEM(pieces, 0, s);
+	if (s == NULL)
+		goto Done;
+
+	s = PyString_FromString(n == 1 ? ",)" : ")");
+	if (s == NULL)
+		goto Done;
+	temp = PyTuple_GET_ITEM(pieces, n-1);
+	PyString_ConcatAndDel(&temp, s);
+	PyTuple_SET_ITEM(pieces, n-1, temp);
+	if (temp == NULL)
+		goto Done;
+
+	/* Paste them all together with ", " between. */
+	s = PyString_FromString(", ");
+	if (s == NULL)
+		goto Done;
+	result = _PyString_Join(s, pieces);
+	Py_DECREF(s);	
+
+Done:
+	Py_DECREF(pieces);
+	return result;
 }
 
 static long