Comparison of cyclic objects (was RE: [Python-Dev] trashcan and PR#7)

[Jeremy Hylton]

Here it is contextified.  One small difference from the previous patch
is that NESTING_LIMIT is now only 1000.  I think this is sufficient to
cover commonly occuring nested containers.

Jeremy

Index: Include/object.h
===================================================================
RCS file: /projects/cvsroot/python/dist/src/Include/object.h,v
retrieving revision 2.52
diff -c -r2.52 object.h
*** object.h	2000/03/21 16:14:47	2.52
--- object.h	2000/04/13 21:50:10
***************
*** 284,289 ****
--- 284,292 ----
  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. */
  
Index: Python/pythonrun.c
===================================================================
RCS file: /projects/cvsroot/python/dist/src/Python/pythonrun.c,v
retrieving revision 2.91
diff -c -r2.91 pythonrun.c
*** pythonrun.c	2000/03/10 23:03:54	2.91
--- pythonrun.c	2000/04/13 21:50:25
***************
*** 149,154 ****
--- 149,156 ----
  	/* 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__");
Index: Objects/object.c
===================================================================
RCS file: /projects/cvsroot/python/dist/src/Objects/object.c,v
retrieving revision 2.67
diff -c -r2.67 object.c
*** object.c	2000/04/10 13:42:33	2.67
--- object.c	2000/04/13 21:44:42
***************
*** 298,308 ****
--- 298,316 ----
  	return PyInt_FromLong(c);
  }
  
+ PyObject *_PyCompareState_Key;
+ 
+ int _PyCompareState_nesting = 0;
+ int _PyCompareState_flag = 0;
+ #define NESTING_LIMIT 1000
+ 
  int
  PyObject_Compare(v, w)
  	PyObject *v, *w;
  {
  	PyTypeObject *vtp, *wtp;
+ 	int result;
+ 
  	if (v == NULL || w == NULL) {
  		PyErr_BadInternalCall();
  		return -1;
***************
*** 369,377 ****
  		/* Numerical types compare smaller than all other types */
  		return strcmp(vname, wname);
  	}
! 	if (vtp->tp_compare == NULL)
  		return (v < w) ? -1 : 1;
! 	return (*vtp->tp_compare)(v, w);
  }
  
  long
--- 377,443 ----
  		/* Numerical types compare smaller than all other types */
  		return strcmp(vname, wname);
  	}
! 	if (vtp->tp_compare == NULL) {
  		return (v < w) ? -1 : 1;
! 	}
! 	++_PyCompareState_nesting;
! 	if (_PyCompareState_nesting > NESTING_LIMIT)
! 		_PyCompareState_flag = 1;
! 	if (_PyCompareState_flag &&
! 	    (vtp->tp_as_mapping || (vtp->tp_as_sequence &&
! 				   !PyString_Check(v))))
! 	{
! 		PyObject *tstate_dict, *cmp_dict, *pair;
! 
! 		tstate_dict = PyThreadState_GetDict();
! 		if (tstate_dict == NULL) {
! 			PyErr_BadInternalCall();
! 			return -1;
! 		} 
! 		cmp_dict = PyDict_GetItem(tstate_dict, _PyCompareState_Key);
! 		if (cmp_dict == NULL) {
! 			cmp_dict = PyDict_New();
! 			if (cmp_dict == NULL)
! 				return -1;
! 			PyDict_SetItem(tstate_dict,
! 				       _PyCompareState_Key,
! 				       cmp_dict);  
! 		}
! 
! 		pair = PyTuple_New(2);
! 		if (pair == NULL) {
! 			return -1;
! 		}
! 		if ((long)v <= (long)w) {
! 			PyTuple_SET_ITEM(pair, 0, PyInt_FromLong((long)v));
! 			PyTuple_SET_ITEM(pair, 1, PyInt_FromLong((long)w));
! 		} else {
! 			PyTuple_SET_ITEM(pair, 0, PyInt_FromLong((long)w));
! 			PyTuple_SET_ITEM(pair, 1, PyInt_FromLong((long)v));
! 		}
! 		if (PyDict_GetItem(cmp_dict, pair)) {
! 			/* already comparing these objects.  assume
! 			   they're equal until shown otherwise 
! 			*/
! 			Py_DECREF(pair);
! 			--_PyCompareState_nesting;
! 			if (_PyCompareState_nesting == 0)
! 				_PyCompareState_flag = 0;
! 			return 0;
! 		}
! 		if (PyDict_SetItem(cmp_dict, pair, pair) == -1) {
! 			return -1;
! 		}
! 		result = (*vtp->tp_compare)(v, w);
! 		PyDict_DelItem(cmp_dict, pair);
! 		Py_DECREF(pair);
! 	} else {
! 		result = (*vtp->tp_compare)(v, w);
! 	}
! 	--_PyCompareState_nesting;
! 	if (_PyCompareState_nesting == 0)
! 		_PyCompareState_flag = 0;
! 	return result;
  }
  
  long