Restructure comparison dramatically. There is no longer a default

*ordering* between objects; there is only a default equality test
(defined by an object being equal to itself only).  Read the comment
in object.c.  The current implementation never uses a three-way
comparison to compute a rich comparison, but it does use a rich
comparison to compute a three-way comparison.  I'm not quite done
ripping out all the calls to PyObject_Compare/Cmp, or replacing
tp_compare implementations with tp_richcompare implementations;
but much of that has happened (to make most unit tests pass).

The following tests still fail, because I need help deciding
or understanding:

test_codeop -- depends on comparing code objects
test_datetime -- need Tim Peters' opinion
test_marshal -- depends on comparing code objects
test_mutants -- need help understanding it

The problem with test_codeop and test_marshal is this: these tests
compare two different code objects and expect them to be equal.
Is that still a feature we'd like to support?  I've temporarily
removed the comparison and hash code from code objects, so they
use the default (equality by pointer only) comparison.

For the other two tests, run them to see for yourself.
(There may be more failing test with "-u all".)

A general problem with getting lots of these tests to pass is
the reality that for object types that have a natural total ordering,
implementing __cmp__ is much more convenient than implementing
__eq__, __ne__, __lt__, and so on.  Should we go back to allowing
__cmp__ to provide a total ordering?  Should we provide some other
way to implement rich comparison with a single method override?
Alex proposed a __key__() method; I've considered a __richcmp__()
method.  Or perhaps __cmp__() just shouldn't be killed off...

1 files changed, 34 insertions, 132 deletions

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index b3fdbf1..320befb 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -582,6 +582,36 @@ PyDict_GetItem(PyObject *op, PyObject *key)
 	return ep->me_value;
 }
 
+/* Variant of PyDict_GetItem() that doesn't suppress exceptions.
+   This returns NULL *with* an exception set if an exception occurred.
+   It returns NULL *without* an exception set if the key wasn't present.
+*/
+PyObject *
+PyDict_GetItemWithError(PyObject *op, PyObject *key)
+{
+	long hash;
+	dictobject *mp = (dictobject *)op;
+	dictentry *ep;
+
+	if (!PyDict_Check(op)) {
+		PyErr_BadInternalCall();
+		return NULL;
+	}
+	if (!PyString_CheckExact(key) ||
+	    (hash = ((PyStringObject *) key)->ob_shash) == -1)
+	{
+		hash = PyObject_Hash(key);
+		if (hash == -1) {
+			return NULL;
+		}
+	}
+
+	ep = (mp->ma_lookup)(mp, key, hash);
+	if (ep == NULL)
+		return NULL;
+	return ep->me_value;
+}
+
 /* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
  * dictionary if it's merely replacing the value for an existing key.
  * This means that it's safe to loop over a dictionary with PyDict_Next()
@@ -1432,136 +1462,6 @@ PyDict_Items(PyObject *mp)
 	return dict_items((dictobject *)mp);
 }
 
-/* Subroutine which returns the smallest key in a for which b's value
-   is different or absent.  The value is returned too, through the
-   pval argument.  Both are NULL if no key in a is found for which b's status
-   differs.  The refcounts on (and only on) non-NULL *pval and function return
-   values must be decremented by the caller (characterize() increments them
-   to ensure that mutating comparison and PyDict_GetItem calls can't delete
-   them before the caller is done looking at them). */
-
-static PyObject *
-characterize(dictobject *a, dictobject *b, PyObject **pval)
-{
-	PyObject *akey = NULL; /* smallest key in a s.t. a[akey] != b[akey] */
-	PyObject *aval = NULL; /* a[akey] */
-	Py_ssize_t i;
-	int cmp;
-
-	for (i = 0; i <= a->ma_mask; i++) {
-		PyObject *thiskey, *thisaval, *thisbval;
-		if (a->ma_table[i].me_value == NULL)
-			continue;
-		thiskey = a->ma_table[i].me_key;
-		Py_INCREF(thiskey);  /* keep alive across compares */
-		if (akey != NULL) {
-			cmp = PyObject_RichCompareBool(akey, thiskey, Py_LT);
-			if (cmp < 0) {
-				Py_DECREF(thiskey);
-				goto Fail;
-			}
-			if (cmp > 0 ||
-			    i > a->ma_mask ||
-			    a->ma_table[i].me_value == NULL)
-			{
-				/* Not the *smallest* a key; or maybe it is
-				 * but the compare shrunk the dict so we can't
-				 * find its associated value anymore; or
-				 * maybe it is but the compare deleted the
-				 * a[thiskey] entry.
-				 */
-				Py_DECREF(thiskey);
-				continue;
-			}
-		}
-
-		/* Compare a[thiskey] to b[thiskey]; cmp <- true iff equal. */
-		thisaval = a->ma_table[i].me_value;
-		assert(thisaval);
-		Py_INCREF(thisaval);   /* keep alive */
-		thisbval = PyDict_GetItem((PyObject *)b, thiskey);
-		if (thisbval == NULL)
-			cmp = 0;
-		else {
-			/* both dicts have thiskey:  same values? */
-			cmp = PyObject_RichCompareBool(
-						thisaval, thisbval, Py_EQ);
-			if (cmp < 0) {
-		    		Py_DECREF(thiskey);
-		    		Py_DECREF(thisaval);
-		    		goto Fail;
-			}
-		}
-		if (cmp == 0) {
-			/* New winner. */
-			Py_XDECREF(akey);
-			Py_XDECREF(aval);
-			akey = thiskey;
-			aval = thisaval;
-		}
-		else {
-			Py_DECREF(thiskey);
-			Py_DECREF(thisaval);
-		}
-	}
-	*pval = aval;
-	return akey;
-
-Fail:
-	Py_XDECREF(akey);
-	Py_XDECREF(aval);
-	*pval = NULL;
-	return NULL;
-}
-
-static int
-dict_compare(dictobject *a, dictobject *b)
-{
-	PyObject *adiff, *bdiff, *aval, *bval;
-	int res;
-
-	/* Compare lengths first */
-	if (a->ma_used < b->ma_used)
-		return -1;	/* a is shorter */
-	else if (a->ma_used > b->ma_used)
-		return 1;	/* b is shorter */
-
-	/* Same length -- check all keys */
-	bdiff = bval = NULL;
-	adiff = characterize(a, b, &aval);
-	if (adiff == NULL) {
-		assert(!aval);
-		/* Either an error, or a is a subset with the same length so
-		 * must be equal.
-		 */
-		res = PyErr_Occurred() ? -1 : 0;
-		goto Finished;
-	}
-	bdiff = characterize(b, a, &bval);
-	if (bdiff == NULL && PyErr_Occurred()) {
-		assert(!bval);
-		res = -1;
-		goto Finished;
-	}
-	res = 0;
-	if (bdiff) {
-		/* bdiff == NULL "should be" impossible now, but perhaps
-		 * the last comparison done by the characterize() on a had
-		 * the side effect of making the dicts equal!
-		 */
-		res = PyObject_Compare(adiff, bdiff);
-	}
-	if (res == 0 && bval != NULL)
-		res = PyObject_Compare(aval, bval);
-
-Finished:
-	Py_XDECREF(adiff);
-	Py_XDECREF(bdiff);
-	Py_XDECREF(aval);
-	Py_XDECREF(bval);
-	return res;
-}
-
 /* Return 1 if dicts equal, 0 if not, -1 if error.
  * Gets out as soon as any difference is detected.
  * Uses only Py_EQ comparison.
@@ -1585,9 +1485,11 @@ dict_equal(dictobject *a, dictobject *b)
 			/* temporarily bump aval's refcount to ensure it stays
 			   alive until we're done with it */
 			Py_INCREF(aval);
-			bval = PyDict_GetItem((PyObject *)b, key);
+			bval = PyDict_GetItemWithError((PyObject *)b, key);
 			if (bval == NULL) {
 				Py_DECREF(aval);
+				if (PyErr_Occurred())
+					return -1;
 				return 0;
 			}
 			cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
@@ -2028,7 +1930,7 @@ PyTypeObject PyDict_Type = {
 	(printfunc)dict_print,			/* tp_print */
 	0,					/* tp_getattr */
 	0,					/* tp_setattr */
-	(cmpfunc)dict_compare,			/* tp_compare */
+	0,					/* tp_compare */
 	(reprfunc)dict_repr,			/* tp_repr */
 	0,					/* tp_as_number */
 	&dict_as_sequence,			/* tp_as_sequence */