From: Marc-Andre Lafortune <redmine@...>
Date: 2009-08-05T05:34:02+09:00
Subject: [ruby-core:24761] [Bug #1852] Enumerable's #hash Raises ArgumentError When Recursive Values are Present

Issue #1852 has been updated by Marc-Andre Lafortune.


I agree wholeheartedly with Run Paint. As I pointed in my patch for recursive equality (http://redmine.ruby-lang.org/issues/show/1448 ), the ideal solution is that recursive structures have their hash collide to the same value. That value can be chosen arbitrarily. I should have updated ticket #1298 in that regard.

I only see disadvantages to the new behavior of raising an exception. As was pointed out, real world usage of recursive structures is probably rare, but I believe a reasonable solution can be implemented and could only improve Ruby. The recent behavior of disallowing recursive structures as hash indexes could also be reverted (ticket #1298).

The algorithm is simple: the top-level #hash should return the magic constant when detection is detected.

Although the C implementation will probably be pretty different, here's a Ruby implementation given as an example. This relies on an exception being thrown when all the catches have been exited, i.e. we're at the top level #hash method.

  HASH_FOR_RECURSIVE_STRUCTURES = -42

  class Array
    def hash
      catch :recursion_detected_for_hash do
        return calculate_hash_value unless recursion_detected
      end
      throw :recursion_detected_for_hash rescue HASH_FOR_RECURSIVE_STRUCTURES
    end
  end
  
  class Hash
    # exact same code...
  end

  # Same with Structs and Range (see ticket #1885)

Note: To be completely consistent, it is imperative that the top level returns the constant, even if the recursion is detected in another class. This is to avoid some complex cases like:

  a = []; h = {:e => a}; a << h
  b = []; i = {:e => b}; b << i
  j = {:e => b}

  # h, i and j should have the same hash.
  # j.hash will detect the recursion in Array#hash (for b),
  # while h.hash and i.hash will detect it in Hash#hash (for h and i)

----------------------------------------
http://redmine.ruby-lang.org/issues/show/1852

----------------------------------------
http://redmine.ruby-lang.org