[Python-checkins] CVS: python/dist/src/Objects object.c,2.106,2.107
Guido van Rossum
gvanrossum@users.sourceforge.net
Wed, 17 Jan 2001 13:27:04 -0800
Update of /cvsroot/python/python/dist/src/Objects
In directory usw-pr-cvs1:/tmp/cvs-serv14991
Modified Files:
object.c
Log Message:
Deal properly (?) with comparing recursive datastructures.
- Use the compare nesting level and in-progress dictionary properly in
PyObject_RichCompare().
- Change the in-progress code to use static variables instead of
globals (both the nesting level and the key for the thread dict were
globals but have no reason to be globals; the key can even be a
function-static variable in get_inprogress_dict()).
- Rewrote try_rich_to_3way_compare() to benefit from the similarity of
the three cases, making it table-driven.
- In try_rich_to_3way_compare(), test for EQ before LT and GT. This
turns out essential when comparing recursive UserList instances;
with the old code, these would recurse into rich comparison three
times for each nesting level up to NESTING_LIMIT/2, making the total
number of calls in the order of 3**(NESTING_LIMIT/2)!
NOTE: I'm not 100% comfortable with this. It works for the standard
test suite (which compares a few trivial recursive data structures
only), but I'm not sure that the in-progress dictionary is used
properly by the rich comparison code. Jeremy suggested that maybe the
operation should be included in the dict. Currently I presume that
objects in the dict are equal unless proven otherwise, and I set the
outcome for the rich comparison accordingly: true for operators EQ,
LE, GE, and false for the other three. But Jeremy seems to think that
there may be counter-examples where this doesn't do the right thing.
Index: object.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/object.c,v
retrieving revision 2.106
retrieving revision 2.107
diff -C2 -r2.106 -r2.107
*** object.c 2001/01/17 17:09:53 2.106
--- object.c 2001/01/17 21:27:02 2.107
***************
*** 377,414 ****
try_rich_to_3way_compare(PyObject *v, PyObject *w)
{
if (v->ob_type->tp_richcompare == NULL &&
w->ob_type->tp_richcompare == NULL)
return 2; /* Shortcut */
! switch (try_rich_compare_bool(v, w, Py_LT)) {
! case -1: /* Error */
! return -1;
! case 0: /* False: not less */
! break;
! case 1: /* True: less */
! return -1;
! case 2: /* NotImplemented */
! break;
! }
! switch (try_rich_compare_bool(v, w, Py_GT)) {
! case -1: /* Error */
! return -1;
! case 0: /* False: not greater */
! break;
! case 1: /* True: greater */
! return 1;
! case 2: /* NotImplemented */
! break;
! }
! switch (try_rich_compare_bool(v, w, Py_EQ)) {
! case -1: /* Error */
! return -1;
! case 0: /* False: not equal */
! break;
! case 1: /* True: equal */
! return 0;
! case 2: /* NotImplemented */
! break;
}
! return 2; /* XXX Even if all three returned FALSE?! */
}
--- 377,402 ----
try_rich_to_3way_compare(PyObject *v, PyObject *w)
{
+ static struct { int op; int outcome; } tries[3] = {
+ /* Try this operator, and if it is true, use this outcome: */
+ {Py_EQ, 0},
+ {Py_LT, -1},
+ {Py_GT, 1},
+ };
+ int i;
+
if (v->ob_type->tp_richcompare == NULL &&
w->ob_type->tp_richcompare == NULL)
return 2; /* Shortcut */
!
! for (i = 0; i < 3; i++) {
! switch (try_rich_compare_bool(v, w, tries[i].op)) {
! case -1:
! return -1;
! case 1:
! return tries[i].outcome;
! }
}
!
! return 2;
}
***************
*** 530,537 ****
return default_3way_compare(v, w);
}
-
- PyObject *_PyCompareState_Key;
! /* _PyCompareState_nesting is incremented before calling compare (for
some types) and decremented on exit. If the count exceeds the
nesting limit, enable code to detect circular data structures.
--- 518,523 ----
return default_3way_compare(v, w);
}
! /* compare_nesting is incremented before calling compare (for
some types) and decremented on exit. If the count exceeds the
nesting limit, enable code to detect circular data structures.
***************
*** 542,552 ****
#define NESTING_LIMIT 500
#endif
! int _PyCompareState_nesting = 0;
static PyObject*
get_inprogress_dict(void)
{
PyObject *tstate_dict, *inprogress;
tstate_dict = PyThreadState_GetDict();
if (tstate_dict == NULL) {
--- 528,545 ----
#define NESTING_LIMIT 500
#endif
! static int compare_nesting = 0;
static PyObject*
get_inprogress_dict(void)
{
+ static PyObject *key;
PyObject *tstate_dict, *inprogress;
+ if (key == NULL) {
+ key = PyString_InternFromString("cmp_state");
+ if (key == NULL)
+ return NULL;
+ }
+
tstate_dict = PyThreadState_GetDict();
if (tstate_dict == NULL) {
***************
*** 554,564 ****
return NULL;
}
! inprogress = PyDict_GetItem(tstate_dict, _PyCompareState_Key);
if (inprogress == NULL) {
inprogress = PyDict_New();
if (inprogress == NULL)
return NULL;
! if (PyDict_SetItem(tstate_dict, _PyCompareState_Key,
! inprogress) == -1) {
Py_DECREF(inprogress);
return NULL;
--- 547,556 ----
return NULL;
}
! inprogress = PyDict_GetItem(tstate_dict, key);
if (inprogress == NULL) {
inprogress = PyDict_New();
if (inprogress == NULL)
return NULL;
! if (PyDict_SetItem(tstate_dict, key, inprogress) == -1) {
Py_DECREF(inprogress);
return NULL;
***************
*** 657,662 ****
vtp = v->ob_type;
wtp = w->ob_type;
! _PyCompareState_nesting++;
! if (_PyCompareState_nesting > NESTING_LIMIT &&
(vtp->tp_as_mapping
|| PyInstance_Check(v)
--- 649,654 ----
vtp = v->ob_type;
wtp = w->ob_type;
! compare_nesting++;
! if (compare_nesting > NESTING_LIMIT &&
(vtp->tp_as_mapping
|| PyInstance_Check(v)
***************
*** 691,695 ****
}
exit_cmp:
! _PyCompareState_nesting--;
return result < 0 ? -1 : result;
}
--- 683,687 ----
}
exit_cmp:
! compare_nesting--;
return result < 0 ? -1 : result;
}
***************
*** 739,766 ****
assert(Py_LT <= op && op <= Py_GE);
! if (_PyCompareState_nesting > NESTING_LIMIT) {
! /* Too deeply nested -- assume equal */
! /* XXX This is an unfair shortcut!
! Should use the same logic as PyObject_Compare. */
! switch (op) {
! case Py_LT:
! case Py_NE:
! case Py_GT:
! res = Py_False;
! break;
! case Py_LE:
! case Py_EQ:
! case Py_GE:
! res = Py_True;
! break;
}
! Py_INCREF(res);
! return res;
}
!
! _PyCompareState_nesting++;
! res = do_richcmp(v, w, op);
! _PyCompareState_nesting--;
!
return res;
}
--- 731,773 ----
assert(Py_LT <= op && op <= Py_GE);
! compare_nesting++;
! if (compare_nesting > NESTING_LIMIT &&
! (v->ob_type->tp_as_mapping
! || PyInstance_Check(v)
! || (v->ob_type->tp_as_sequence && !PyString_Check(v)))) {
! /* try to detect circular data structures */
! PyObject *inprogress, *pair;
!
! inprogress = get_inprogress_dict();
! if (inprogress == NULL) {
! res = NULL;
! goto exit_cmp;
}
! pair = make_pair(v, w);
! if (PyDict_GetItem(inprogress, pair)) {
! /* already comparing these objects. assume
! they're equal until shown otherwise */
! Py_DECREF(pair);
! if (op == Py_EQ || op == Py_LE || op == Py_GE)
! res = Py_True;
! else
! res = Py_False;
! Py_INCREF(res);
! goto exit_cmp;
! }
! if (PyDict_SetItem(inprogress, pair, pair) == -1) {
! res = NULL;
! goto exit_cmp;
! }
! res = do_richcmp(v, w, op);
! /* XXX DelItem shouldn't fail */
! PyDict_DelItem(inprogress, pair);
! Py_DECREF(pair);
}
! else {
! res = do_richcmp(v, w, op);
! }
! exit_cmp:
! compare_nesting--;
return res;
}