Fix PR#7 comparisons of recursive objects
Note that comparisons of deeply nested objects can still dump core in
extreme cases.
diff --git a/Include/object.h b/Include/object.h
index 77f5c55..fabf0b6 100644
--- a/Include/object.h
+++ b/Include/object.h
@@ -284,6 +284,9 @@
extern DL_IMPORT(int) Py_ReprEnter Py_PROTO((PyObject *));
extern DL_IMPORT(void) Py_ReprLeave Py_PROTO((PyObject *));
+/* tstate dict key for PyObject_Compare helper */
+extern PyObject *_PyCompareState_Key;
+
/* Flag bits for printing: */
#define Py_PRINT_RAW 1 /* No string quotes etc. */
diff --git a/Lib/test/test_b1.py b/Lib/test/test_b1.py
index 6a89d22..b063e5a 100644
--- a/Lib/test/test_b1.py
+++ b/Lib/test/test_b1.py
@@ -63,6 +63,15 @@
if cmp(-1, 1) <> -1: raise TestFailed, 'cmp(-1, 1)'
if cmp(1, -1) <> 1: raise TestFailed, 'cmp(1, -1)'
if cmp(1, 1) <> 0: raise TestFailed, 'cmp(1, 1)'
+# verify that circular objects are handled
+a = []; a.append(a)
+b = []; b.append(b)
+from UserList import UserList
+c = UserList(); c.append(c)
+if cmp(a, b) != 0: raise TestFailed, "cmp(%s, %s)" % (a, b)
+if cmp(b, c) != 0: raise TestFailed, "cmp(%s, %s)" % (b, c)
+if cmp(c, a) != 0: raise TestFailed, "cmp(%s, %s)" % (c, a)
+if cmp(a, c) != 0: raise TestFailed, "cmp(%s, %s)" % (a, c)
print 'coerce'
if fcmp(coerce(1, 1.1), (1.0, 1.1)): raise TestFailed, 'coerce(1, 1.1)'
diff --git a/Objects/object.c b/Objects/object.c
index 968fdd0..bd1d17f 100644
--- a/Objects/object.c
+++ b/Objects/object.c
@@ -298,11 +298,67 @@
return PyInt_FromLong(c);
}
+PyObject *_PyCompareState_Key;
+
+/* _PyCompareState_nesting is incremented beforing call compare (for
+ some types) and decremented on exit. If the count exceeds the
+ nesting limit, enable code to detect circular data structures.
+*/
+#define NESTING_LIMIT 500
+int _PyCompareState_nesting = 0;
+
+static PyObject*
+get_inprogress_dict()
+{
+ PyObject *tstate_dict, *inprogress;
+
+ tstate_dict = PyThreadState_GetDict();
+ if (tstate_dict == NULL) {
+ PyErr_BadInternalCall();
+ return NULL;
+ }
+ inprogress = PyDict_GetItem(tstate_dict, _PyCompareState_Key);
+ if (inprogress == NULL) {
+ PyErr_Clear();
+ inprogress = PyDict_New();
+ if (inprogress == NULL)
+ return NULL;
+ if (PyDict_SetItem(tstate_dict, _PyCompareState_Key,
+ inprogress) == -1) {
+ Py_DECREF(inprogress);
+ return NULL;
+ }
+ }
+ return inprogress;
+}
+
+static PyObject *
+make_pair(v, w)
+ PyObject *v, *w;
+{
+ PyObject *pair;
+
+ pair = PyTuple_New(2);
+ if (pair == NULL) {
+ return NULL;
+ }
+ if ((long)v <= (long)w) {
+ PyTuple_SET_ITEM(pair, 0, PyLong_FromVoidPtr((void *)v));
+ PyTuple_SET_ITEM(pair, 1, PyLong_FromVoidPtr((void *)w));
+ } else {
+ PyTuple_SET_ITEM(pair, 0, PyLong_FromVoidPtr((void *)w));
+ PyTuple_SET_ITEM(pair, 1, PyLong_FromVoidPtr((void *)v));
+ }
+ return pair;
+}
+
int
PyObject_Compare(v, w)
PyObject *v, *w;
{
PyTypeObject *vtp, *wtp;
+ int result;
+
if (v == NULL || w == NULL) {
PyErr_BadInternalCall();
return -1;
@@ -314,7 +370,32 @@
int c;
if (!PyInstance_Check(v))
return -PyObject_Compare(w, v);
- res = do_cmp(v, w);
+ if (++_PyCompareState_nesting > NESTING_LIMIT) {
+ PyObject *inprogress, *pair;
+
+ inprogress = get_inprogress_dict();
+ if (inprogress == NULL) {
+ return -1;
+ }
+ pair = make_pair(v, w);
+ if (PyDict_GetItem(inprogress, pair)) {
+ /* already comparing these objects. assume
+ they're equal until shown otherwise */
+ Py_DECREF(pair);
+ --_PyCompareState_nesting;
+ return 0;
+ }
+ if (PyDict_SetItem(inprogress, pair, pair) == -1) {
+ return -1;
+ }
+ res = do_cmp(v, w);
+ _PyCompareState_nesting--;
+ /* XXX DelItem shouldn't fail */
+ PyDict_DelItem(inprogress, pair);
+ Py_DECREF(pair);
+ } else {
+ res = do_cmp(v, w);
+ }
if (res == NULL)
return -1;
if (!PyInt_Check(res)) {
@@ -369,9 +450,37 @@
/* Numerical types compare smaller than all other types */
return strcmp(vname, wname);
}
- if (vtp->tp_compare == NULL)
+ if (vtp->tp_compare == NULL) {
return (v < w) ? -1 : 1;
- return (*vtp->tp_compare)(v, w);
+ }
+ if (++_PyCompareState_nesting > NESTING_LIMIT
+ && (vtp->tp_as_mapping
+ || (vtp->tp_as_sequence && !PyString_Check(v)))) {
+ PyObject *inprogress, *pair;
+
+ inprogress = get_inprogress_dict();
+ if (inprogress == NULL) {
+ return -1;
+ }
+ pair = make_pair(v, w);
+ if (PyDict_GetItem(inprogress, pair)) {
+ /* already comparing these objects. assume
+ they're equal until shown otherwise */
+ _PyCompareState_nesting--;
+ Py_DECREF(pair);
+ return 0;
+ }
+ if (PyDict_SetItem(inprogress, pair, pair) == -1) {
+ return -1;
+ }
+ result = (*vtp->tp_compare)(v, w);
+ _PyCompareState_nesting--;
+ PyDict_DelItem(inprogress, pair); /* XXX shouldn't fail */
+ Py_DECREF(pair);
+ } else {
+ result = (*vtp->tp_compare)(v, w);
+ }
+ return result;
}
long
diff --git a/Python/pythonrun.c b/Python/pythonrun.c
index eb93d47..0ae15fa 100644
--- a/Python/pythonrun.c
+++ b/Python/pythonrun.c
@@ -149,6 +149,8 @@
/* Init Unicode implementation; relies on the codec registry */
_PyUnicode_Init();
+ _PyCompareState_Key = PyString_InternFromString("cmp_state");
+
bimod = _PyBuiltin_Init_1();
if (bimod == NULL)
Py_FatalError("Py_Initialize: can't initialize __builtin__");