[Python-checkins] CVS: python/dist/src/Objects object.c,2.107,2.108
Guido van Rossum
gvanrossum@users.sourceforge.net
Thu, 18 Jan 2001 14:07:08 -0800
Update of /cvsroot/python/python/dist/src/Objects
In directory usw-pr-cvs1:/tmp/cvs-serv17212
Modified Files:
object.c
Log Message:
Changes to recursive-object comparisons, having to do with a test case
I found where rich comparison of unequal recursive objects gave
unintuituve results. In a discussion with Tim, where we discovered
that our intuition on when a<=b should be true was failing, we decided
to outlaw ordering comparisons on recursive objects. (Once we have
fixed our intuition and designed a matching algorithm that's practical
and reasonable to implement, we can allow such orderings again.)
- Refactored the recursive-object comparison framework; more is now
done in the support routines so less needs to be done in the calling
routines (even at the expense of slowing it down a bit -- this
should normally never be invoked, it's mostly just there to avoid
blowing up the interpreter).
- Changed the framework so that the comparison operator used is also
stored. (The dictionary now stores triples (v, w, op) instead of
pairs (v, w).)
- Changed the nesting limit to a more reasonable small 20; this only
slows down comparisons of very deeply nested objects (unlikely to
occur in practice), while speeding up comparisons of recursive
objects (previously, this would first waste time and space on 500
nested comparisons before it would start detecting recursion).
- Changed rich comparisons for recursive objects to raise a ValueError
exception when recursion is detected for ordering oprators (<, <=,
>, >=).
Unrelated change:
- Moved PyObject_Unicode() to just under PyObject_Str(), where it
belongs. MAL's patch must've inserted in a random spot between two
functions in the file -- between two helpers for rich comparison...
Index: object.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/object.c,v
retrieving revision 2.107
retrieving revision 2.108
diff -C2 -r2.107 -r2.108
*** object.c 2001/01/17 21:27:02 2.107
--- object.c 2001/01/18 22:07:06 2.108
***************
*** 309,312 ****
--- 309,360 ----
}
+ PyObject *
+ PyObject_Unicode(PyObject *v)
+ {
+ PyObject *res;
+
+ if (v == NULL)
+ res = PyString_FromString("<NULL>");
+ else if (PyUnicode_Check(v)) {
+ Py_INCREF(v);
+ return v;
+ }
+ else if (PyString_Check(v))
+ res = v;
+ else if (v->ob_type->tp_str != NULL)
+ res = (*v->ob_type->tp_str)(v);
+ else {
+ PyObject *func;
+ static PyObject *strstr;
+ if (strstr == NULL) {
+ strstr= PyString_InternFromString("__str__");
+ if (strstr == NULL)
+ return NULL;
+ }
+ if (!PyInstance_Check(v) ||
+ (func = PyObject_GetAttr(v, strstr)) == NULL) {
+ PyErr_Clear();
+ res = PyObject_Repr(v);
+ }
+ else {
+ res = PyEval_CallObject(func, (PyObject *)NULL);
+ Py_DECREF(func);
+ }
+ }
+ if (res == NULL)
+ return NULL;
+ if (!PyUnicode_Check(res)) {
+ PyObject* str;
+ str = PyUnicode_FromObject(res);
+ Py_DECREF(res);
+ if (str)
+ res = str;
+ else
+ return NULL;
+ }
+ return res;
+ }
+
+
/* Map rich comparison operators to their swapped version, e.g. LT --> GT */
static int swapped_op[] = {Py_GT, Py_GE, Py_EQ, Py_NE, Py_LT, Py_LE};
***************
*** 522,531 ****
some types) and decremented on exit. If the count exceeds the
nesting limit, enable code to detect circular data structures.
*/
! #ifdef macintosh
! #define NESTING_LIMIT 60
! #else
! #define NESTING_LIMIT 500
! #endif
static int compare_nesting = 0;
--- 570,581 ----
some types) and decremented on exit. If the count exceeds the
nesting limit, enable code to detect circular data structures.
+
+ This is a tunable parameter that should only affect the performance
+ of comparisons, nothing else. Setting it high makes comparing deeply
+ nested non-cyclical data structures faster, but makes comparing cyclical
+ data structures slower.
*/
! #define NESTING_LIMIT 20
!
static int compare_nesting = 0;
***************
*** 547,550 ****
--- 597,601 ----
return NULL;
}
+
inprogress = PyDict_GetItem(tstate_dict, key);
if (inprogress == NULL) {
***************
*** 558,636 ****
Py_DECREF(inprogress);
}
- return inprogress;
- }
! PyObject *
! PyObject_Unicode(PyObject *v)
! {
! PyObject *res;
!
! if (v == NULL)
! res = PyString_FromString("<NULL>");
! else if (PyUnicode_Check(v)) {
! Py_INCREF(v);
! return v;
! }
! else if (PyString_Check(v))
! res = v;
! else if (v->ob_type->tp_str != NULL)
! res = (*v->ob_type->tp_str)(v);
! else {
! PyObject *func;
! static PyObject *strstr;
! if (strstr == NULL) {
! strstr= PyString_InternFromString("__str__");
! if (strstr == NULL)
! return NULL;
! }
! if (!PyInstance_Check(v) ||
! (func = PyObject_GetAttr(v, strstr)) == NULL) {
! PyErr_Clear();
! res = PyObject_Repr(v);
! }
! else {
! res = PyEval_CallObject(func, (PyObject *)NULL);
! Py_DECREF(func);
! }
! }
! if (res == NULL)
! return NULL;
! if (!PyUnicode_Check(res)) {
! PyObject* str;
! str = PyUnicode_FromObject(res);
! Py_DECREF(res);
! if (str)
! res = str;
! else
! return NULL;
! }
! return res;
}
static PyObject *
! make_pair(PyObject *v, PyObject *w)
{
! PyObject *pair;
Py_uintptr_t iv = (Py_uintptr_t)v;
Py_uintptr_t iw = (Py_uintptr_t)w;
! pair = PyTuple_New(2);
! if (pair == NULL) {
return NULL;
! }
if (iv <= iw) {
! 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(PyObject *v, PyObject *w)
{
! PyTypeObject *vtp, *wtp;
int result;
--- 609,680 ----
Py_DECREF(inprogress);
}
! return inprogress;
}
static PyObject *
! check_recursion(PyObject *v, PyObject *w, int op)
{
! PyObject *inprogress;
! PyObject *token;
Py_uintptr_t iv = (Py_uintptr_t)v;
Py_uintptr_t iw = (Py_uintptr_t)w;
+ PyObject *x, *y, *z;
! inprogress = get_inprogress_dict();
! if (inprogress == NULL)
return NULL;
!
! token = PyTuple_New(3);
! if (token == NULL)
! return NULL;
!
if (iv <= iw) {
! PyTuple_SET_ITEM(token, 0, x = PyLong_FromVoidPtr((void *)v));
! PyTuple_SET_ITEM(token, 1, y = PyLong_FromVoidPtr((void *)w));
! if (op >= 0)
! op = swapped_op[op];
} else {
! PyTuple_SET_ITEM(token, 0, x = PyLong_FromVoidPtr((void *)w));
! PyTuple_SET_ITEM(token, 1, y = PyLong_FromVoidPtr((void *)v));
! }
! PyTuple_SET_ITEM(token, 2, z = PyInt_FromLong((long)op));
! if (x == NULL || y == NULL || z == NULL) {
! Py_DECREF(token);
! return NULL;
! }
!
! if (PyDict_GetItem(inprogress, token) != NULL) {
! Py_DECREF(token);
! return Py_None; /* Without INCREF! */
}
!
! if (PyDict_SetItem(inprogress, token, token) < 0) {
! Py_DECREF(token);
! return NULL;
! }
!
! return token;
}
+ static void
+ delete_token(PyObject *token)
+ {
+ PyObject *inprogress;
+
+ if (token == NULL || token == Py_None)
+ return;
+ inprogress = get_inprogress_dict();
+ if (inprogress == NULL)
+ PyErr_Clear();
+ else
+ PyDict_DelItem(inprogress, token);
+ Py_DECREF(token);
+ }
+
int
PyObject_Compare(PyObject *v, PyObject *w)
{
! PyTypeObject *vtp;
int result;
***************
*** 648,686 ****
return 0;
vtp = v->ob_type;
- wtp = w->ob_type;
compare_nesting++;
if (compare_nesting > NESTING_LIMIT &&
(vtp->tp_as_mapping
! || PyInstance_Check(v)
! || (vtp->tp_as_sequence && !PyString_Check(v)))) {
/* try to detect circular data structures */
! PyObject *inprogress, *pair;
! inprogress = get_inprogress_dict();
! if (inprogress == NULL) {
! result = -1;
! 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);
result = 0;
- goto exit_cmp;
}
! if (PyDict_SetItem(inprogress, pair, pair) == -1) {
! result = -1;
! goto exit_cmp;
}
- result = do_cmp(v, w);
- /* XXX DelItem shouldn't fail */
- PyDict_DelItem(inprogress, pair);
- Py_DECREF(pair);
}
else {
result = do_cmp(v, w);
}
- exit_cmp:
compare_nesting--;
return result < 0 ? -1 : result;
--- 692,720 ----
return 0;
vtp = v->ob_type;
compare_nesting++;
if (compare_nesting > NESTING_LIMIT &&
(vtp->tp_as_mapping
! || (vtp->tp_as_sequence
! && !PyString_Check(v)
! && !PyTuple_Check(v)))) {
/* try to detect circular data structures */
! PyObject *token = check_recursion(v, w, -1);
! if (token == NULL) {
! result = -1;
}
! else if (token == Py_None) {
/* already comparing these objects. assume
they're equal until shown otherwise */
result = 0;
}
! else {
! result = do_cmp(v, w);
! delete_token(token);
}
}
else {
result = do_cmp(v, w);
}
compare_nesting--;
return result < 0 ? -1 : result;
***************
*** 734,772 ****
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;
--- 768,802 ----
if (compare_nesting > NESTING_LIMIT &&
(v->ob_type->tp_as_mapping
! || (v->ob_type->tp_as_sequence
! && !PyString_Check(v)
! && !PyTuple_Check(v)))) {
/* try to detect circular data structures */
! PyObject *token = check_recursion(v, w, op);
! if (token == NULL) {
! res = NULL;
}
! else if (token == Py_None) {
! /* already comparing these objects with this operator.
! assume they're equal until shown otherwise */
! if (op == Py_EQ)
res = Py_True;
! else if (op == Py_NE)
res = Py_False;
! else {
! PyErr_SetString(PyExc_ValueError,
! "can't order recursive values");
! res = NULL;
! }
! Py_XINCREF(res);
}
! else {
! res = do_richcmp(v, w, op);
! delete_token(token);
}
}
else {
res = do_richcmp(v, w, op);
}
compare_nesting--;
return res;