nobu	2013-12-03 22:32:24 +0900 (Tue, 03 Dec 2013)

  New Revision: 43981

  http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=43981

  Log:
    hash.c: same hash value for similar constructs
    
    * hash.c (rb_hash_recursive): make similar (recursive) constructs
      return same hash value.  execute recursively, and rewind to the
      topmost frame with an object which .eql? to the recursive
      object, if recursion is detected.

  Modified files:
    trunk/ChangeLog
    trunk/hash.c
    trunk/test/ruby/test_array.rb
    trunk/test/ruby/test_thread.rb
Index: ChangeLog
===================================================================
--- ChangeLog	(revision 43980)
+++ ChangeLog	(revision 43981)
@@ -1,4 +1,9 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1
-Tue Dec  3 22:18:27 2013  Nobuyoshi Nakada  <nobu@r...>
+Tue Dec  3 22:32:18 2013  Nobuyoshi Nakada  <nobu@r...>
+
+	* hash.c (rb_hash_recursive): make similar (recursive) constructs
+	  return same hash value.  execute recursively, and rewind to the
+	  topmost frame with an object which .eql? to the recursive
+	  object, if recursion is detected.
 
 	* hash.c (rb_hash): detect recursion for all `hash' methods.  each
 	  `hash' methods no longer need to use rb_exec_recursive().
Index: hash.c
===================================================================
--- hash.c	(revision 43980)
+++ hash.c	(revision 43981)
@@ -48,7 +48,7 @@ rb_hash_freeze(VALUE hash) https://github.com/ruby/ruby/blob/trunk/hash.c#L48
 VALUE rb_cHash;
 
 static VALUE envtbl;
-static ID id_hash, id_yield, id_default;
+static ID id_hash, id_yield, id_default, id_recursive_hash;
 
 VALUE
 rb_hash_set_ifnone(VALUE hash, VALUE ifnone)
@@ -76,6 +76,71 @@ rb_any_cmp(VALUE a, VALUE b) https://github.com/ruby/ruby/blob/trunk/hash.c#L76
     return !rb_eql(a, b);
 }
 
+struct hash_recursive_args {
+    VALUE (*func)(VALUE, VALUE, int);
+    VALUE obj;
+    VALUE arg;
+};
+
+static VALUE
+call_hash(RB_BLOCK_CALL_FUNC_ARGLIST(tag, data))
+{
+    struct hash_recursive_args *p = (struct hash_recursive_args *)tag;
+    return p->func(p->obj, p->arg, 0);
+}
+
+static VALUE
+rb_hash_recursive(VALUE (*func)(VALUE, VALUE, int), VALUE obj, VALUE arg)
+{
+    VALUE hval;
+    VALUE thread = rb_thread_current();
+    VALUE recursion_list = rb_thread_local_aref(thread, id_recursive_hash);
+    struct hash_recursive_args args;
+    long len = 0;
+    int state;
+
+    if (!NIL_P(recursion_list) && (len = RARRAY_LEN(recursion_list)) > 0) {
+	VALUE outer;
+	struct hash_recursive_args *outerp;
+	const VALUE *ptr = RARRAY_CONST_PTR(recursion_list);
+	long i = 0;
+	do {
+	    outerp = (struct hash_recursive_args *)(ptr[i] & ~FIXNUM_FLAG);
+	    if (outerp->obj == obj) {
+		len = i;
+		for (i = 0; i < len; ++i) {
+		    outer = RARRAY_AREF(recursion_list, i) & ~FIXNUM_FLAG;
+		    outerp = (struct hash_recursive_args *)outer;
+		    if (rb_eql(obj, outerp->obj)) {
+			rb_throw_obj(outer, outer);
+		    }
+		}
+		outer = RARRAY_AREF(recursion_list, len) & ~FIXNUM_FLAG;
+		outerp = (struct hash_recursive_args *)outer;
+		rb_throw_obj(outer, outer);
+	    }
+	} while (++i < len);
+    }
+    else {
+	recursion_list = rb_ary_new();
+	rb_thread_local_aset(thread, id_recursive_hash, recursion_list);
+    }
+    args.func = func;
+    args.obj = obj;
+    args.arg = arg;
+    rb_ary_push(recursion_list, (VALUE)&args | FIXNUM_FLAG);
+    hval = rb_catch_protect((VALUE)&args, call_hash, (VALUE)&args, &state);
+    if (RARRAY_LEN(recursion_list) >= len) {
+	rb_ary_set_len(recursion_list, len);
+	if (len == 0) rb_thread_local_aset(thread, id_recursive_hash, Qnil);
+    }
+    if (state) rb_jump_tag(state);
+    if (hval == (VALUE)&args) {
+	hval = (*func)(obj, arg, 1);
+    }
+    return hval;
+}
+
 static VALUE
 hash_recursive(VALUE obj, VALUE arg, int recurse)
 {
@@ -89,7 +154,7 @@ hash_recursive(VALUE obj, VALUE arg, int https://github.com/ruby/ruby/blob/trunk/hash.c#L154
 VALUE
 rb_hash(VALUE obj)
 {
-    VALUE hval = rb_exec_recursive_paired(hash_recursive, obj, obj, 0);
+    VALUE hval = rb_hash_recursive(hash_recursive, obj, 0);
   retry:
     switch (TYPE(hval)) {
       case T_FIXNUM:
Index: test/ruby/test_array.rb
===================================================================
--- test/ruby/test_array.rb	(revision 43980)
+++ test/ruby/test_array.rb	(revision 43981)
@@ -2053,6 +2053,7 @@ class TestArray < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/ruby/test_array.rb#L2053
     assert_not_equal([[1]].hash, [[2]].hash)
     a = []
     a << a
+    assert_equal([[a]].hash, a.hash)
     assert_not_equal([a, 1].hash, [a, 2].hash)
     assert_not_equal([a, a].hash, a.hash) # Implementation dependent
   end
Index: test/ruby/test_thread.rb
===================================================================
--- test/ruby/test_thread.rb	(revision 43980)
+++ test/ruby/test_thread.rb	(revision 43981)
@@ -467,6 +467,19 @@ class TestThread < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/ruby/test_thread.rb#L467
     m.unlock
   end
 
+  def test_recursive_outer
+    arr = []
+    obj = Struct.new(:foo, :visited).new(arr, false)
+    arr << obj
+    def obj.hash
+      self[:visited] = true
+      super
+      raise "recursive_outer should short circuit intermediate calls"
+    end
+    assert_nothing_raised {arr.hash}
+    assert(obj[:visited], "obj.hash was not called")
+  end
+
   def test_thread_instance_variable
     bug4389 = '[ruby-core:35192]'
     assert_in_out_err([], <<-INPUT, %w(), [], bug4389)

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/