• Guido van Rossum's avatar
    Deal properly (?) with comparing recursive datastructures. · cd4f1c7b
    Guido van Rossum authored
    - 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.
    cd4f1c7b
object.c 33.5 KB