tree 7642bddcd61c7ef3383109e62a116b46ae3e3bbc
parent a99202a017b69f176c27a4f2cee222a9b4fa9a11
author Guido van Rossum <guido@python.org> 979766822 +0000
committer Guido van Rossum <guido@python.org> 979766822 +0000
HG:extra convert_revision:svn%3A6015fed2-1504-0410-9fe1-9d1591cc4771/python/branches/legacy-trunk%4018824

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.