Skip to content

Commit 2b3eb40

Browse files
arigoarigo
committed
Deleting cyclic object comparison.
SF patch 825639 http://mail.python.org/pipermail/python-dev/2003-October/039445.html
1 parent 0e4f764 commit 2b3eb40

9 files changed

Lines changed: 109 additions & 275 deletions

File tree

‎Include/ceval.h‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,9 +43,23 @@ PyAPI_FUNC(int) Py_FlushLine(void);
4343
PyAPI_FUNC(int) Py_AddPendingCall(int (*func)(void *), void *arg);
4444
PyAPI_FUNC(int) Py_MakePendingCalls(void);
4545

46+
/* Protection against deeply nested recursive calls */
4647
PyAPI_FUNC(void) Py_SetRecursionLimit(int);
4748
PyAPI_FUNC(int) Py_GetRecursionLimit(void);
4849

50+
#define Py_EnterRecursiveCall(where) \
51+
(_Py_MakeRecCheck(PyThreadState_GET()->recursion_depth) && \
52+
_Py_CheckRecursiveCall(where))
53+
#define Py_LeaveRecursiveCall() \
54+
(--PyThreadState_GET()->recursion_depth)
55+
PyAPI_FUNC(int) _Py_CheckRecursiveCall(char *where);
56+
PyAPI_DATA(int) _Py_CheckRecursionLimit;
57+
#ifdef USE_STACKCHECK
58+
# define _Py_MakeRecCheck(x) (++(x) > --_Py_CheckRecursionLimit)
59+
#else
60+
# define _Py_MakeRecCheck(x) (++(x) > _Py_CheckRecursionLimit)
61+
#endif
62+
4963
PyAPI_FUNC(char *) PyEval_GetFuncName(PyObject *);
5064
PyAPI_FUNC(char *) PyEval_GetFuncDesc(PyObject *);
5165

‎Lib/test/pickletester.py‎

Lines changed: 10 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -424,29 +424,26 @@ def test_recursive_list(self):
424424
for proto in protocols:
425425
s = self.dumps(l, proto)
426426
x = self.loads(s)
427-
self.assertEqual(x, l)
428-
self.assertEqual(x, x[0])
429-
self.assertEqual(id(x), id(x[0]))
427+
self.assertEqual(len(x), 1)
428+
self.assert_(x is x[0])
430429

431430
def test_recursive_dict(self):
432431
d = {}
433432
d[1] = d
434433
for proto in protocols:
435434
s = self.dumps(d, proto)
436435
x = self.loads(s)
437-
self.assertEqual(x, d)
438-
self.assertEqual(x[1], x)
439-
self.assertEqual(id(x[1]), id(x))
436+
self.assertEqual(x.keys(), [1])
437+
self.assert_(x[1] is x)
440438

441439
def test_recursive_inst(self):
442440
i = C()
443441
i.attr = i
444442
for proto in protocols:
445443
s = self.dumps(i, 2)
446444
x = self.loads(s)
447-
self.assertEqual(x, i)
448-
self.assertEqual(x.attr, x)
449-
self.assertEqual(id(x.attr), id(x))
445+
self.assertEqual(dir(x), dir(i))
446+
self.assert_(x.attr is x)
450447

451448
def test_recursive_multi(self):
452449
l = []
@@ -457,12 +454,10 @@ def test_recursive_multi(self):
457454
for proto in protocols:
458455
s = self.dumps(l, proto)
459456
x = self.loads(s)
460-
self.assertEqual(x, l)
461-
self.assertEqual(x[0], i)
462-
self.assertEqual(x[0].attr, d)
463-
self.assertEqual(x[0].attr[1], x)
464-
self.assertEqual(x[0].attr[1][0], i)
465-
self.assertEqual(x[0].attr[1][0].attr, d)
457+
self.assertEqual(len(x), 1)
458+
self.assertEqual(dir(x[0]), dir(i))
459+
self.assertEqual(x[0].attr.keys(), [1])
460+
self.assert_(x[0].attr[1] is x)
466461

467462
def test_garyp(self):
468463
self.assertRaises(self.error, self.loads, 'garyp')

‎Lib/test/test_builtin.py‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -167,16 +167,16 @@ def test_cmp(self):
167167
self.assertEqual(cmp(-1, 1), -1)
168168
self.assertEqual(cmp(1, -1), 1)
169169
self.assertEqual(cmp(1, 1), 0)
170-
# verify that circular objects are handled
170+
# verify that circular objects are not handled
171171
a = []; a.append(a)
172172
b = []; b.append(b)
173173
from UserList import UserList
174174
c = UserList(); c.append(c)
175-
self.assertEqual(cmp(a, b), 0)
176-
self.assertEqual(cmp(b, c), 0)
177-
self.assertEqual(cmp(c, a), 0)
178-
self.assertEqual(cmp(a, c), 0)
179-
# okay, now break the cycles
175+
self.assertRaises(RuntimeError, cmp, a, b)
176+
self.assertRaises(RuntimeError, cmp, b, c)
177+
self.assertRaises(RuntimeError, cmp, c, a)
178+
self.assertRaises(RuntimeError, cmp, a, c)
179+
# okay, now break the cycles
180180
a.pop(); b.pop(); c.pop()
181181
self.assertRaises(TypeError, cmp)
182182

‎Lib/test/test_copy.py‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -272,10 +272,10 @@ def test_deepcopy_reflexive_list(self):
272272
x = []
273273
x.append(x)
274274
y = copy.deepcopy(x)
275-
self.assertEqual(y, x)
275+
self.assertRaises(RuntimeError, cmp, y, x)
276276
self.assert_(y is not x)
277-
self.assert_(y[0] is not x[0])
278-
self.assert_(y is y[0])
277+
self.assert_(y[0] is y)
278+
self.assertEqual(len(y), 1)
279279

280280
def test_deepcopy_tuple(self):
281281
x = ([1, 2], 3)
@@ -288,7 +288,7 @@ def test_deepcopy_reflexive_tuple(self):
288288
x = ([],)
289289
x[0].append(x)
290290
y = copy.deepcopy(x)
291-
self.assertEqual(y, x)
291+
self.assertRaises(RuntimeError, cmp, y, x)
292292
self.assert_(y is not x)
293293
self.assert_(y[0] is not x[0])
294294
self.assert_(y[0][0] is y)
@@ -304,10 +304,10 @@ def test_deepcopy_reflexive_dict(self):
304304
x = {}
305305
x['foo'] = x
306306
y = copy.deepcopy(x)
307-
self.assertEqual(y, x)
307+
self.assertRaises(RuntimeError, cmp, y, x)
308308
self.assert_(y is not x)
309309
self.assert_(y['foo'] is y)
310-
self.assertEqual(y, {'foo': y})
310+
self.assertEqual(len(y), 1)
311311

312312
def test_deepcopy_keepalive(self):
313313
memo = {}

‎Lib/test/test_richcmp.py‎

Lines changed: 21 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -224,57 +224,36 @@ def do(bad):
224224
self.assertRaises(Exc, func, Bad())
225225

226226
def test_recursion(self):
227-
# Check comparison for recursive objects
227+
# Check that comparison for recursive objects fails gracefully
228228
from UserList import UserList
229-
a = UserList(); a.append(a)
230-
b = UserList(); b.append(b)
231-
232-
self.assert_(a == b)
233-
self.assert_(not a != b)
234-
a.append(1)
235-
self.assert_(a == a[0])
236-
self.assert_(not a != a[0])
237-
self.assert_(a != b)
238-
self.assert_(not a == b)
239-
b.append(0)
240-
self.assert_(a != b)
241-
self.assert_(not a == b)
242-
a[1] = -1
243-
self.assert_(a != b)
244-
self.assert_(not a == b)
245-
246229
a = UserList()
247230
b = UserList()
248231
a.append(b)
249232
b.append(a)
250-
self.assert_(a == b)
251-
self.assert_(not a != b)
233+
self.assertRaises(RuntimeError, operator.eq, a, b)
234+
self.assertRaises(RuntimeError, operator.ne, a, b)
235+
self.assertRaises(RuntimeError, operator.lt, a, b)
236+
self.assertRaises(RuntimeError, operator.le, a, b)
237+
self.assertRaises(RuntimeError, operator.gt, a, b)
238+
self.assertRaises(RuntimeError, operator.ge, a, b)
252239

253240
b.append(17)
241+
# Even recursive lists of different lengths are different,
242+
# but they cannot be ordered
243+
self.assert_(not (a == b))
254244
self.assert_(a != b)
255-
self.assert_(not a == b)
245+
self.assertRaises(RuntimeError, operator.lt, a, b)
246+
self.assertRaises(RuntimeError, operator.le, a, b)
247+
self.assertRaises(RuntimeError, operator.gt, a, b)
248+
self.assertRaises(RuntimeError, operator.ge, a, b)
256249
a.append(17)
257-
self.assert_(a == b)
258-
self.assert_(not a != b)
259-
260-
def test_recursion2(self):
261-
# This test exercises the circular structure handling code
262-
# in PyObject_RichCompare()
263-
class Weird(object):
264-
def __eq__(self, other):
265-
return self != other
266-
def __ne__(self, other):
267-
return self == other
268-
def __lt__(self, other):
269-
return self > other
270-
def __gt__(self, other):
271-
return self < other
272-
273-
self.assert_(Weird() == Weird())
274-
self.assert_(not (Weird() != Weird()))
275-
276-
for op in opmap["lt"]:
277-
self.assertRaises(ValueError, op, Weird(), Weird())
250+
self.assertRaises(RuntimeError, operator.eq, a, b)
251+
self.assertRaises(RuntimeError, operator.ne, a, b)
252+
a.insert(0, 11)
253+
b.insert(0, 12)
254+
self.assert_(not (a == b))
255+
self.assert_(a != b)
256+
self.assert_(a < b)
278257

279258
class DictTest(unittest.TestCase):
280259

‎Misc/NEWS‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -47,6 +47,10 @@ Core and builtins
4747
- obj.__contains__() now returns True/False instead of 1/0. SF patch
4848
820195.
4949

50+
- Python no longer tries to be smart about recursive comparisons.
51+
When comparing containers with cyclic references to themselves it
52+
will now just hit the recursion limit. See SF patch 825639.
53+
5054
Extension modules
5155
-----------------
5256

‎Objects/classobject.c‎

Lines changed: 4 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1970,7 +1970,6 @@ instance_iternext(PyInstanceObject *self)
19701970
static PyObject *
19711971
instance_call(PyObject *func, PyObject *arg, PyObject *kw)
19721972
{
1973-
PyThreadState *tstate = PyThreadState_GET();
19741973
PyObject *res, *call = PyObject_GetAttrString(func, "__call__");
19751974
if (call == NULL) {
19761975
PyInstanceObject *inst = (PyInstanceObject*) func;
@@ -1990,14 +1989,13 @@ instance_call(PyObject *func, PyObject *arg, PyObject *kw)
19901989
a() # infinite recursion
19911990
This bounces between instance_call() and PyObject_Call() without
19921991
ever hitting eval_frame() (which has the main recursion check). */
1993-
if (tstate->recursion_depth++ > Py_GetRecursionLimit()) {
1994-
PyErr_SetString(PyExc_RuntimeError,
1995-
"maximum __call__ recursion depth exceeded");
1992+
if (Py_EnterRecursiveCall(" in __call__")) {
19961993
res = NULL;
19971994
}
1998-
else
1995+
else {
19991996
res = PyObject_Call(call, arg, kw);
2000-
tstate->recursion_depth--;
1997+
Py_LeaveRecursiveCall();
1998+
}
20011999
Py_DECREF(call);
20022000
return res;
20032001
}

0 commit comments

Comments
 (0)