* thread.c (rb_exec_recursive_paired): new function for proper

  handling of recursive arrays.  [EXPERIMENTAL] [ruby-core:23402]

* array.c (rb_ary_equal, rb_ary_eql, rb_ary_cmp): use above.

* hash.c (hash_equal): ditto.


git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@23557 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

5 files changed, 87 insertions, 26 deletions

diff --git a/ChangeLog b/ChangeLog
index eb109cafa5..61b2a498e6 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+Sun May 24 22:48:17 2009  Nobuyoshi Nakada  <nobu@ruby-lang.org>
+
+	* thread.c (rb_exec_recursive_paired): new function for proper
+	  handling of recursive arrays.  [EXPERIMENTAL] [ruby-core:23402]
+
+	* array.c (rb_ary_equal, rb_ary_eql, rb_ary_cmp): use above.
+
+	* hash.c (hash_equal): ditto.
+
 Sun May 24 22:39:33 2009  Nobuyoshi Nakada  <nobu@ruby-lang.org>
 
 	* error.c (syserr_initialize): errno is int.
diff --git a/array.c b/array.c
index 5c3112b94f..3d53bc8ef7 100644
--- a/array.c
+++ b/array.c
@@ -2740,7 +2740,7 @@ recursive_equal(VALUE ary1, VALUE ary2, int recur)
 {
     long i;
 
-    if (recur) return Qfalse;
+    if (recur) return Qtrue; /* Subtle! */
     for (i=0; i<RARRAY_LEN(ary1); i++) {
 	if (!rb_equal(rb_ary_elt(ary1, i), rb_ary_elt(ary2, i)))
 	    return Qfalse;
@@ -2773,7 +2773,7 @@ rb_ary_equal(VALUE ary1, VALUE ary2)
 	return rb_equal(ary2, ary1);
     }
     if (RARRAY_LEN(ary1) != RARRAY_LEN(ary2)) return Qfalse;
-    return rb_exec_recursive(recursive_equal, ary1, ary2);
+    return rb_exec_recursive_paired(recursive_equal, ary1, ary2, ary2);
 }
 
 static VALUE
@@ -2781,7 +2781,7 @@ recursive_eql(VALUE ary1, VALUE ary2, int recur)
 {
     long i;
 
-    if (recur) return Qfalse;
+    if (recur) return Qtrue; /* Subtle! */
     for (i=0; i<RARRAY_LEN(ary1); i++) {
 	if (!rb_eql(rb_ary_elt(ary1, i), rb_ary_elt(ary2, i)))
 	    return Qfalse;
@@ -2803,7 +2803,7 @@ rb_ary_eql(VALUE ary1, VALUE ary2)
     if (ary1 == ary2) return Qtrue;
     if (TYPE(ary2) != T_ARRAY) return Qfalse;
     if (RARRAY_LEN(ary1) != RARRAY_LEN(ary2)) return Qfalse;
-    return rb_exec_recursive(recursive_eql, ary1, ary2);
+    return rb_exec_recursive_paired(recursive_eql, ary1, ary2, ary2);
 }
 
 static VALUE
@@ -2870,7 +2870,7 @@ recursive_cmp(VALUE ary1, VALUE ary2, int recur)
 {
     long i, len;
 
-    if (recur) return Qnil;
+    if (recur) return Qundef;	/* Subtle! */
     len = RARRAY_LEN(ary1);
     if (len > RARRAY_LEN(ary2)) {
 	len = RARRAY_LEN(ary2);
@@ -2912,7 +2912,7 @@ rb_ary_cmp(VALUE ary1, VALUE ary2)
 
     ary2 = to_ary(ary2);
     if (ary1 == ary2) return INT2FIX(0);
-    v = rb_exec_recursive(recursive_cmp, ary1, ary2);
+    v = rb_exec_recursive_paired(recursive_cmp, ary1, ary2, ary2);
     if (v != Qundef) return v;
     len = RARRAY_LEN(ary1) - RARRAY_LEN(ary2);
     if (len == 0) return INT2FIX(0);
diff --git a/hash.c b/hash.c
index 79e253e266..5405410fd1 100644
--- a/hash.c
+++ b/hash.c
@@ -1451,7 +1451,7 @@ recursive_eql(VALUE hash, VALUE dt, int recur)
 {
     struct equal_data *data;
 
-    if (recur) return Qfalse;
+    if (recur) return Qtrue;	/* Subtle! */
     data = (struct equal_data*)dt;
     data->result = Qtrue;
     rb_hash_foreach(hash, eql_i, dt);
@@ -1488,7 +1488,7 @@ hash_equal(VALUE hash1, VALUE hash2, int eql)
 
     data.tbl = RHASH(hash2)->ntbl;
     data.eql = eql;
-    return rb_exec_recursive(recursive_eql, hash1, (VALUE)&data);
+    return rb_exec_recursive_paired(recursive_eql, hash1, hash2, (VALUE)&data);
 }
 
 /*
diff --git a/include/ruby/intern.h b/include/ruby/intern.h
index ae443859d6..ec6527fc3a 100644
--- a/include/ruby/intern.h
+++ b/include/ruby/intern.h
@@ -340,6 +340,7 @@ VALUE rb_thread_local_aset(VALUE, ID, VALUE);
 void rb_thread_atfork(void);
 void rb_thread_atfork_before_exec(void);
 VALUE rb_exec_recursive(VALUE(*)(VALUE, VALUE, int),VALUE,VALUE);
+VALUE rb_exec_recursive_paired(VALUE(*)(VALUE, VALUE, int),VALUE,VALUE,VALUE);
 /* file.c */
 VALUE rb_file_s_expand_path(int, VALUE *);
 VALUE rb_file_expand_path(VALUE, VALUE);
diff --git a/thread.c b/thread.c
index 69b02e3d5e..d2eeca32e6 100644
--- a/thread.c
+++ b/thread.c
@@ -3310,26 +3310,39 @@ rb_barrier_destroy(VALUE self)
 static ID recursive_key;
 
 static VALUE
-recursive_check(VALUE hash, VALUE obj)
+recursive_check(VALUE hash, VALUE obj, VALUE paired_obj)
 {
     if (NIL_P(hash) || TYPE(hash) != T_HASH) {
 	return Qfalse;
     }
     else {
-	VALUE list = rb_hash_aref(hash, ID2SYM(rb_frame_this_func()));
+	VALUE sym = ID2SYM(rb_frame_this_func());
+	VALUE list = rb_hash_aref(hash, sym);
+	VALUE pair_list;
 
 	if (NIL_P(list) || TYPE(list) != T_HASH)
 	    return Qfalse;
-	if (NIL_P(rb_hash_lookup(list, obj)))
+	pair_list = rb_hash_lookup2(list, obj, Qundef);
+	if (pair_list == Qundef)
 	    return Qfalse;
+	if (paired_obj) {
+	    if (TYPE(pair_list) != T_HASH) {
+		if (pair_list != paired_obj)
+		    return Qfalse;
+	    }
+	    else {
+		if (NIL_P(rb_hash_lookup(pair_list, paired_obj)))
+		    return Qfalse;
+	    }
+	}
 	return Qtrue;
     }
 }
 
 static VALUE
-recursive_push(VALUE hash, VALUE obj)
+recursive_push(VALUE hash, VALUE obj, VALUE paired_obj)
 {
-    VALUE list, sym;
+    VALUE list, sym, pair_list;
 
     sym = ID2SYM(rb_frame_this_func());
     if (NIL_P(hash) || TYPE(hash) != T_HASH) {
@@ -3344,61 +3357,99 @@ recursive_push(VALUE hash, VALUE obj)
 	list = rb_hash_new();
 	rb_hash_aset(hash, sym, list);
     }
-    rb_hash_aset(list, obj, Qtrue);
+    if (!paired_obj) {
+	rb_hash_aset(list, obj, Qtrue);
+    }
+    else if ((pair_list = rb_hash_lookup2(list, obj, Qundef)) == Qundef) {
+	rb_hash_aset(list, obj, paired_obj);
+    }
+    else {
+	if (TYPE(pair_list) != T_HASH){
+	    VALUE other_paired_obj = pair_list;
+	    pair_list = rb_hash_new();
+	    rb_hash_aset(pair_list, other_paired_obj, Qtrue);
+	    rb_hash_aset(list, obj, pair_list);
+	}
+	rb_hash_aset(pair_list, paired_obj, Qtrue);
+    }
     return hash;
 }
 
 static void
-recursive_pop(VALUE hash, VALUE obj)
+recursive_pop(VALUE hash, VALUE obj, VALUE paired_obj)
 {
-    VALUE list, sym;
+    VALUE list, sym, pair_list, symname, thrname;
 
     sym = ID2SYM(rb_frame_this_func());
     if (NIL_P(hash) || TYPE(hash) != T_HASH) {
-	VALUE symname;
-	VALUE thrname;
 	symname = rb_inspect(sym);
 	thrname = rb_inspect(rb_thread_current());
-
 	rb_raise(rb_eTypeError, "invalid inspect_tbl hash for %s in %s",
 		 StringValuePtr(symname), StringValuePtr(thrname));
     }
     list = rb_hash_aref(hash, sym);
     if (NIL_P(list) || TYPE(list) != T_HASH) {
-	VALUE symname = rb_inspect(sym);
-	VALUE thrname = rb_inspect(rb_thread_current());
+	symname = rb_inspect(sym);
+	thrname = rb_inspect(rb_thread_current());
 	rb_raise(rb_eTypeError, "invalid inspect_tbl list for %s in %s",
 		 StringValuePtr(symname), StringValuePtr(thrname));
     }
+    if (paired_obj) {
+	pair_list = rb_hash_lookup2(list, obj, Qundef);
+	if (pair_list == Qundef) {
+	    symname = rb_inspect(sym);
+	    thrname = rb_inspect(rb_thread_current());
+	    rb_raise(rb_eTypeError, "invalid inspect_tbl pair_list for %s in %s",
+		     StringValuePtr(symname), StringValuePtr(thrname));
+	}
+	if (TYPE(pair_list) == T_HASH) {
+	    rb_hash_delete(pair_list, paired_obj);
+	    if (!RHASH_EMPTY_P(pair_list)) {
+		return; /* keep hash until is empty */
+	    }
+	}
+    }
     rb_hash_delete(list, obj);
 }
 
-VALUE
-rb_exec_recursive(VALUE (*func) (VALUE, VALUE, int), VALUE obj, VALUE arg)
+static VALUE
+exec_recursive(VALUE (*func) (VALUE, VALUE, int), VALUE obj, VALUE pairid, VALUE arg)
 {
     volatile VALUE hash = rb_thread_local_aref(rb_thread_current(), recursive_key);
     VALUE objid = rb_obj_id(obj);
 
-    if (recursive_check(hash, objid)) {
+    if (recursive_check(hash, objid, pairid)) {
 	return (*func) (obj, arg, Qtrue);
     }
     else {
 	VALUE result = Qundef;
 	int state;
 
-	hash = recursive_push(hash, objid);
+	hash = recursive_push(hash, objid, pairid);
 	PUSH_TAG();
 	if ((state = EXEC_TAG()) == 0) {
 	    result = (*func) (obj, arg, Qfalse);
 	}
 	POP_TAG();
-	recursive_pop(hash, objid);
+	recursive_pop(hash, objid, pairid);
 	if (state)
 	    JUMP_TAG(state);
 	return result;
     }
 }
 
+VALUE
+rb_exec_recursive(VALUE (*func) (VALUE, VALUE, int), VALUE obj, VALUE arg)
+{
+    return exec_recursive(func, obj, 0, arg);
+}
+
+VALUE
+rb_exec_recursive_paired(VALUE (*func) (VALUE, VALUE, int), VALUE obj, VALUE paired_obj, VALUE arg)
+{
+    return exec_recursive(func, obj, rb_obj_id(paired_obj), arg);
+}
+
 /* tracer */
 
 static rb_event_hook_t *