From 4a3dd2dcc2fae12b6736822731848c557b80d0e3 Mon Sep 17 00:00:00 2001 From: Jeremy Hylton Date: Fri, 14 Apr 2000 19:13:24 +0000 Subject: Fix PR#7 comparisons of recursive objects Note that comparisons of deeply nested objects can still dump core in extreme cases. --- Include/object.h | 3 ++ Lib/test/test_b1.py | 9 ++++ Objects/object.c | 115 ++++++++++++++++++++++++++++++++++++++++++++++++++-- Python/pythonrun.c | 2 + 4 files changed, 126 insertions(+), 3 deletions(-) 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) PyNumber_CoerceEx Py_PROTO((PyObject **, PyObject **)); 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 @@ print 'cmp' 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 @@ do_cmp(v, w) 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 @@ PyObject_Compare(v, w) 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 @@ PyObject_Compare(v, w) /* 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 @@ Py_Initialize() /* 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__"); -- cgit v0.12