Convert to rich comparisons:

- sort's docompare() calls RichCompare(Py_LT).

- list_contains(), list_index(), listcount(), listremove() call
  RichCompare(Py_EQ).

- Get rid of list_compare(), in favor of new list_richcompare().  The
  latter does some nice shortcuts, like when == or != is requested, it
  first compares the lengths for trivial accept/reject.  Then it goes
  over the items until it finds an index where the items differe; then
  it does more shortcut magic to minimize the number of additional
  comparisons.

- Aligned the comments for large struct initializers.

1 files changed, 163 insertions, 90 deletions

diff --git a/Objects/listobject.c b/Objects/listobject.c
index 59b1912..f57f6fb 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -246,19 +246,6 @@ list_repr(PyListObject *v)
 }
 
 static int
-list_compare(PyListObject *v, PyListObject *w)
-{
-	int i;
-	
-	for (i = 0; i < v->ob_size && i < w->ob_size; i++) {
-		int cmp = PyObject_Compare(v->ob_item[i], w->ob_item[i]);
-		if (cmp != 0)
-			return cmp;
-	}
-	return v->ob_size - w->ob_size;
-}
-
-static int
 list_length(PyListObject *a)
 {
 	return a->ob_size;
@@ -269,13 +256,14 @@ list_length(PyListObject *a)
 static int
 list_contains(PyListObject *a, PyObject *el)
 {
-	int i, cmp;
+	int i;
 
 	for (i = 0; i < a->ob_size; ++i) {
-		cmp = PyObject_Compare(el, PyList_GET_ITEM(a, i));
-		if (cmp == 0)
+		int cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
+						   Py_EQ);
+		if (cmp > 0)
 			return 1;
-		if (PyErr_Occurred())
+		else if (cmp < 0)
 			return -1;
 	}
 	return 0;
@@ -725,10 +713,16 @@ docompare(PyObject *x, PyObject *y, PyObject *compare)
 	int i;
 
 	if (compare == NULL) {
-		i = PyObject_Compare(x, y);
-		if (i && PyErr_Occurred())
-			i = CMPERROR;
-		return i;
+		/* NOTE: we rely on the fact here that the sorting algorithm
+		   only ever checks whether k<0, i.e., whether x<y.  So we
+		   invoke the rich comparison function with Py_LT ('<'), and
+		   return -1 when it returns true and 0 when it returns
+		   false. */
+		i = PyObject_RichCompareBool(x, y, Py_LT);
+		if (i < 0)
+			return CMPERROR;
+		else
+			return -i;
 	}
 
 	args = Py_BuildValue("(OO)", x, y);
@@ -1344,9 +1338,10 @@ listindex(PyListObject *self, PyObject *args)
 	if (!PyArg_ParseTuple_Compat1(args, "O:index", &v))
 		return NULL;
 	for (i = 0; i < self->ob_size; i++) {
-		if (PyObject_Compare(self->ob_item[i], v) == 0)
+		int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
+		if (cmp > 0)
 			return PyInt_FromLong((long)i);
-		if (PyErr_Occurred())
+		else if (cmp < 0)
 			return NULL;
 	}
 	PyErr_SetString(PyExc_ValueError, "list.index(x): x not in list");
@@ -1363,9 +1358,10 @@ listcount(PyListObject *self, PyObject *args)
 	if (!PyArg_ParseTuple_Compat1(args, "O:count", &v))
 		return NULL;
 	for (i = 0; i < self->ob_size; i++) {
-		if (PyObject_Compare(self->ob_item[i], v) == 0)
+		int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
+		if (cmp > 0)
 			count++;
-		if (PyErr_Occurred())
+		else if (cmp < 0)
 			return NULL;
 	}
 	return PyInt_FromLong((long)count);
@@ -1380,14 +1376,15 @@ listremove(PyListObject *self, PyObject *args)
 	if (!PyArg_ParseTuple_Compat1(args, "O:remove", &v))
 		return NULL;
 	for (i = 0; i < self->ob_size; i++) {
-		if (PyObject_Compare(self->ob_item[i], v) == 0) {
+		int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
+		if (cmp > 0) {
 			if (list_ass_slice(self, i, i+1,
 					   (PyObject *)NULL) != 0)
 				return NULL;
 			Py_INCREF(Py_None);
 			return Py_None;
 		}
-		if (PyErr_Occurred())
+		else if (cmp < 0)
 			return NULL;
 	}
 	PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
@@ -1418,6 +1415,78 @@ list_clear(PyListObject *lp)
 	return 0;
 }
 
+static PyObject *
+list_richcompare(PyObject *v, PyObject *w, int op)
+{
+	PyListObject *vl, *wl;
+	int i;
+
+	if (!PyList_Check(v) || !PyList_Check(w)) {
+		Py_INCREF(Py_NotImplemented);
+		return Py_NotImplemented;
+	}
+
+	vl = (PyListObject *)v;
+	wl = (PyListObject *)w;
+
+	if (vl->ob_size != wl->ob_size && (op == Py_EQ || op == Py_NE)) {
+		/* Shortcut: if the lengths differ, the lists differ */
+		PyObject *res;
+		if (op == Py_EQ)
+			res = Py_False;
+		else
+			res = Py_True;
+		Py_INCREF(res);
+		return res;
+	}
+
+	/* Search for the first index where items are different */
+	for (i = 0; i < vl->ob_size && i < wl->ob_size; i++) {
+		int k = PyObject_RichCompareBool(vl->ob_item[i],
+						 wl->ob_item[i], Py_EQ);
+		if (k < 0)
+			return NULL;
+		if (!k)
+			break;
+	}
+
+	if (i >= vl->ob_size || i >= wl->ob_size) {
+		/* No more items to compare -- compare sizes */
+		int vs = vl->ob_size;
+		int ws = wl->ob_size;
+		int cmp;
+		PyObject *res;
+		switch (op) {
+		case Py_LT: cmp = vs <  ws; break;
+		case Py_LE: cmp = ws <= ws; break;
+		case Py_EQ: cmp = vs == ws; break;
+		case Py_NE: cmp = vs != ws; break;
+		case Py_GT: cmp = vs >  ws; break;
+		case Py_GE: cmp = vs >= ws; break;
+		default: return NULL; /* cannot happen */
+		}
+		if (cmp)
+			res = Py_True;
+		else
+			res = Py_False;
+		Py_INCREF(res);
+		return res;
+	}
+
+	/* We have an item that differs -- shortcuts for EQ/NE */
+	if (op == Py_EQ) {
+		Py_INCREF(Py_False);
+		return Py_False;
+	}
+	if (op == Py_NE) {
+		Py_INCREF(Py_True);
+		return Py_True;
+	}
+
+	/* Compare the final item again using the proper operator */
+	return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
+}
+
 static char append_doc[] =
 "L.append(object) -- append object to end";
 static char extend_doc[] =
@@ -1438,15 +1507,15 @@ static char sort_doc[] =
 "L.sort([cmpfunc]) -- sort *IN PLACE*; if given, cmpfunc(x, y) -> -1, 0, 1";
 
 static PyMethodDef list_methods[] = {
-	{"append",	(PyCFunction)listappend, METH_VARARGS, append_doc},
-	{"insert",	(PyCFunction)listinsert, METH_VARARGS, insert_doc},
-	{"extend",      (PyCFunction)listextend, METH_VARARGS, extend_doc},
-	{"pop",		(PyCFunction)listpop, METH_VARARGS, pop_doc},
-	{"remove",	(PyCFunction)listremove, METH_VARARGS, remove_doc},
-	{"index",	(PyCFunction)listindex, METH_VARARGS, index_doc},
-	{"count",	(PyCFunction)listcount, METH_VARARGS, count_doc},
+	{"append",	(PyCFunction)listappend,  METH_VARARGS, append_doc},
+	{"insert",	(PyCFunction)listinsert,  METH_VARARGS, insert_doc},
+	{"extend",      (PyCFunction)listextend,  METH_VARARGS, extend_doc},
+	{"pop",		(PyCFunction)listpop, 	  METH_VARARGS, pop_doc},
+	{"remove",	(PyCFunction)listremove,  METH_VARARGS, remove_doc},
+	{"index",	(PyCFunction)listindex,   METH_VARARGS, index_doc},
+	{"count",	(PyCFunction)listcount,   METH_VARARGS, count_doc},
 	{"reverse",	(PyCFunction)listreverse, METH_VARARGS, reverse_doc},
-	{"sort",	(PyCFunction)listsort, METH_VARARGS, sort_doc},
+	{"sort",	(PyCFunction)listsort, 	  METH_VARARGS, sort_doc},
 	{NULL,		NULL}		/* sentinel */
 };
 
@@ -1457,16 +1526,16 @@ list_getattr(PyListObject *f, char *name)
 }
 
 static PySequenceMethods list_as_sequence = {
-	(inquiry)list_length, /*sq_length*/
-	(binaryfunc)list_concat, /*sq_concat*/
-	(intargfunc)list_repeat, /*sq_repeat*/
-	(intargfunc)list_item, /*sq_item*/
-	(intintargfunc)list_slice, /*sq_slice*/
-	(intobjargproc)list_ass_item, /*sq_ass_item*/
-	(intintobjargproc)list_ass_slice, /*sq_ass_slice*/
-	(objobjproc)list_contains, /*sq_contains*/
-	(binaryfunc)list_inplace_concat, /*sq_inplace_concat*/
-	(intargfunc)list_inplace_repeat, /*sq_inplace_repeat*/
+	(inquiry)list_length,			/* sq_length */
+	(binaryfunc)list_concat,		/* sq_concat */
+	(intargfunc)list_repeat,		/* sq_repeat */
+	(intargfunc)list_item,			/* sq_item */
+	(intintargfunc)list_slice,		/* sq_slice */
+	(intobjargproc)list_ass_item,		/* sq_ass_item */
+	(intintobjargproc)list_ass_slice,	/* sq_ass_slice */
+	(objobjproc)list_contains,		/* sq_contains */
+	(binaryfunc)list_inplace_concat,	/* sq_inplace_concat */
+	(intargfunc)list_inplace_repeat,	/* sq_inplace_repeat */
 };
 
 PyTypeObject PyList_Type = {
@@ -1475,25 +1544,26 @@ PyTypeObject PyList_Type = {
 	"list",
 	sizeof(PyListObject) + PyGC_HEAD_SIZE,
 	0,
-	(destructor)list_dealloc, /*tp_dealloc*/
-	(printfunc)list_print, /*tp_print*/
-	(getattrfunc)list_getattr, /*tp_getattr*/
-	0,		/*tp_setattr*/
-	(cmpfunc)list_compare, /*tp_compare*/
-	(reprfunc)list_repr, /*tp_repr*/
-	0,		/*tp_as_number*/
-	&list_as_sequence,	/*tp_as_sequence*/
-	0,		/*tp_as_mapping*/
-	0,		/*tp_hash*/
-	0,		/*tp_call*/
-	0,		/*tp_str*/
-	0,		/*tp_getattro*/
-	0,		/*tp_setattro*/
-	0,		/*tp_as_buffer*/
-	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_GC,	/*tp_flags*/
- 	0,		/* tp_doc */
- 	(traverseproc)list_traverse,	/* tp_traverse */
- 	(inquiry)list_clear,	/* tp_clear */
+	(destructor)list_dealloc,		/* tp_dealloc */
+	(printfunc)list_print,			/* tp_print */
+	(getattrfunc)list_getattr,		/* tp_getattr */
+	0,					/* tp_setattr */
+	0,					/* tp_compare */
+	(reprfunc)list_repr,			/* tp_repr */
+	0,					/* tp_as_number */
+	&list_as_sequence,			/* tp_as_sequence */
+	0,					/* tp_as_mapping */
+	0,					/* tp_hash */
+	0,					/* tp_call */
+	0,					/* tp_str */
+	0,					/* tp_getattro */
+	0,					/* tp_setattro */
+	0,					/* tp_as_buffer */
+	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_GC,	/* tp_flags */
+ 	0,					/* tp_doc */
+ 	(traverseproc)list_traverse,		/* tp_traverse */
+ 	(inquiry)list_clear,			/* tp_clear */
+	list_richcompare,			/* tp_richcompare */
 };
 
 
@@ -1536,14 +1606,14 @@ immutable_list_ass(void)
 }
 
 static PySequenceMethods immutable_list_as_sequence = {
-	(inquiry)list_length, /*sq_length*/
-	(binaryfunc)list_concat, /*sq_concat*/
-	(intargfunc)list_repeat, /*sq_repeat*/
-	(intargfunc)list_item, /*sq_item*/
-	(intintargfunc)list_slice, /*sq_slice*/
-	(intobjargproc)immutable_list_ass, /*sq_ass_item*/
-	(intintobjargproc)immutable_list_ass, /*sq_ass_slice*/
-	(objobjproc)list_contains, /*sq_contains*/
+	(inquiry)list_length,			/* sq_length */
+	(binaryfunc)list_concat,		/* sq_concat */
+	(intargfunc)list_repeat,		/* sq_repeat */
+	(intargfunc)list_item,			/* sq_item */
+	(intintargfunc)list_slice,		/* sq_slice */
+	(intobjargproc)immutable_list_ass,	/* sq_ass_item */
+	(intintobjargproc)immutable_list_ass,	/* sq_ass_slice */
+	(objobjproc)list_contains,		/* sq_contains */
 };
 
 static PyTypeObject immutable_list_type = {
@@ -1552,22 +1622,25 @@ static PyTypeObject immutable_list_type = {
 	"list (immutable, during sort)",
 	sizeof(PyListObject) + PyGC_HEAD_SIZE,
 	0,
-	0,		/*tp_dealloc*/ /* Cannot happen */
-	(printfunc)list_print, /*tp_print*/
-	(getattrfunc)immutable_list_getattr, /*tp_getattr*/
-	0,		/*tp_setattr*/
-	0,		/*tp_compare*/ /* Won't be called */
-	(reprfunc)list_repr, /*tp_repr*/
-	0,		/*tp_as_number*/
-	&immutable_list_as_sequence,	/*tp_as_sequence*/
-	0,		/*tp_as_mapping*/
-	0,		/*tp_hash*/
-	0,		/*tp_call*/
-	0,		/*tp_str*/
-	0,		/*tp_getattro*/
-	0,		/*tp_setattro*/
-	0,		/*tp_as_buffer*/
-	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_GC,	/*tp_flags*/
- 	0,		/* tp_doc */
- 	(traverseproc)list_traverse,	/* tp_traverse */
+	0, /* Cannot happen */			/* tp_dealloc */
+	(printfunc)list_print,			/* tp_print */
+	(getattrfunc)immutable_list_getattr,	/* tp_getattr */
+	0,					/* tp_setattr */
+	0, /* Won't be called */		/* tp_compare */
+	(reprfunc)list_repr,			/* tp_repr */
+	0,					/* tp_as_number */
+	&immutable_list_as_sequence,		/* tp_as_sequence */
+	0,					/* tp_as_mapping */
+	0,					/* tp_hash */
+	0,					/* tp_call */
+	0,					/* tp_str */
+	0,					/* tp_getattro */
+	0,					/* tp_setattro */
+	0,					/* tp_as_buffer */
+	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_GC,	/* tp_flags */
+ 	0,					/* tp_doc */
+ 	(traverseproc)list_traverse,		/* tp_traverse */
+	0,					/* tp_clear */
+	list_richcompare,			/* tp_richcompare */
+	/* NOTE: This is *not* the standard list_type struct! */
 };