Bug #1448: [patch] Proper handling of recursive arrays

Hi,

At Sat, 9 May 2009 11:47:53 +0900,
Marc-Andre Lafortune wrote in [ruby-core:23402]:
> The attached patch fixes all of these problems :-)

But reverts old problems.

$ ./ruby -e 'x={};x[1]=x;y={};y[1]=y; p x==y'
-e:1:in `==': stack level too deep (SystemStackError)
	from -e:1:in `=='
	from -e:1:in `=='
	from -e:1:in `=='
	from -e:1:in `=='
	from -e:1:in `=='
	from -e:1:in `=='
	from -e:1:in `=='
	from -e:1:in `=='
	 ... 5124 levels...
	from -e:1:in `=='
	from -e:1:in `=='
	from -e:1:in `=='
	from -e:1:in `<main>'

Also, note that arg of rb_exec_recursive() is not restricted to
a real VALUE.

> * Last problem:
> There is one more problem that my patch doesn't cover (lack
> of mri-fu): hashes for recursive structures are incorrect. As
> per the official doc, "a.eql? b" should imply "a.hash ==
> b.hash". On the other hand, we have (before or after my
> patch):
> a = [x]
> x.eql? a  # ==> true
> a.eql? x  # ==> true
> x.hash == a.hash # ==> false, should have same hash

I wonder it may be false positive.

$ ruby -e 'x=[];x<<x;a=[x]; p a, x'
[[[...]]]
[[...]]

But no idea right now.

A patch based on yours.


Index: array.c
===================================================================
--- array.c	(revision 23373)
+++ array.c	(working copy)
@@ -2729,5 +2729,5 @@ recursive_equal(VALUE ary1, VALUE ary2, 
     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)))
@@ -2762,5 +2762,5 @@ rb_ary_equal(VALUE ary1, VALUE ary2)
     }
     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);
 }

@@ -2770,5 +2770,5 @@ recursive_eql(VALUE ary1, VALUE ary2, in
     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)))
@@ -2792,5 +2792,5 @@ rb_ary_eql(VALUE ary1, VALUE ary2)
     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);
 }

@@ -2859,5 +2859,5 @@ recursive_cmp(VALUE ary1, VALUE ary2, in
     long i, len;

-    if (recur) return Qnil;
+    if (recur) return Qundef;	/* Subtle! */
     len = RARRAY_LEN(ary1);
     if (len > RARRAY_LEN(ary2)) {
@@ -2901,5 +2901,5 @@ 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);
     if (v != Qundef) return v;
     len = RARRAY_LEN(ary1) - RARRAY_LEN(ary2);
Index: hash.c
===================================================================
--- hash.c	(revision 23373)
+++ hash.c	(working copy)
@@ -1489,5 +1489,5 @@ hash_equal(VALUE hash1, VALUE hash2, int
     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, (VALUE)&data);
 }

Index: thread.c
===================================================================
--- thread.c	(revision 23373)
+++ thread.c	(working copy)
@@ -3311,5 +3311,5 @@ 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) {
@@ -3317,10 +3317,23 @@ recursive_check(VALUE hash, VALUE obj)
     }
     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;
     }
@@ -3328,7 +3341,7 @@ recursive_check(VALUE hash, VALUE obj)

 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());
@@ -3345,20 +3358,31 @@ recursive_push(VALUE hash, VALUE obj)
 	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));
@@ -3366,19 +3390,34 @@ recursive_pop(VALUE hash, VALUE obj)
     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, 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 arg, VALUE pairid)
 {
     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);
     }
@@ -3387,5 +3426,5 @@ rb_exec_recursive(VALUE (*func) (VALUE, 
 	int state;

-	hash = recursive_push(hash, objid);
+	hash = recursive_push(hash, objid, pairid);
 	PUSH_TAG();
 	if ((state = EXEC_TAG()) == 0) {
@@ -3393,5 +3432,5 @@ rb_exec_recursive(VALUE (*func) (VALUE, 
 	}
 	POP_TAG();
-	recursive_pop(hash, objid);
+	recursive_pop(hash, objid, pairid);
 	if (state)
 	    JUMP_TAG(state);
@@ -3400,4 +3439,16 @@ rb_exec_recursive(VALUE (*func) (VALUE, 
 }

+VALUE
+rb_exec_recursive(VALUE (*func) (VALUE, VALUE, int), VALUE obj, VALUE arg)
+{
+    return exec_recursive(func, obj, arg, 0);
+}
+
+VALUE
+rb_exec_recursive_paired(VALUE (*func) (VALUE, VALUE, int), VALUE obj, VALUE arg)
+{
+    return exec_recursive(func, obj, arg, rb_obj_id(arg));
+}
+
 /* tracer */

Index: include/ruby/intern.h
===================================================================
--- include/ruby/intern.h	(revision 23373)
+++ include/ruby/intern.h	(working copy)
@@ -341,4 +341,5 @@ 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);
 /* file.c */
 VALUE rb_file_s_expand_path(int, VALUE *);


-- 
Nobu Nakada

• File recursion2.patch added

Oups, completely forgot to finish the hash part.
The problem was that I was not pairing hash1 with hash2 but with the temporary struct made for the comparison. This is fixed in the included patch. I have updated rubyspecs (core/hash/equal_value_spec) with complex recursive hash tests. Specs now test recursive hashes, even when formed differently but with the same content, and arrays containing hashes containing arrays...

For the false positive: firstly, the example you show is already == in the current version. The equality for arrays is "do they contain the same elements in the same order". For recursive arrays, it's easier to think about the reverse: arrays are not equal if there is a mismatch between one element and the corresponding one. [a] and a don't have such a mismatch.

PS: Thanks for prettying up my code! I had difficulty applying the patch, I hope everything made it through.

Hi,

At Sun, 10 May 2009 07:37:31 +0900,
Marc-Andre Lafortune wrote in [ruby-core:23412]:
> File recursion2.patch added

This patch seems nice to me.  I'm afraid matz may not like the
name rb_exec_recursive_paired().  Is it OK?

-- 
Nobu Nakada

Nobuyoshi Nakada wrote:
> This patch seems nice to me.
> I'm afraid matz may not like the name rb_exec_recursive_paired().  Is it OK?

'rb_exec_recursive_paired' is the name that came to my mind because it checks recursion on a pair of objects. Maybe 'rb_exec_recursive_on_pair' or 'rb_exec_recursive_with_pair' would be even better. As long as a good name is chosen, I'll be happy :-)

Thanks

• Status changed from Open to Closed
• % Done changed from 0 to 100

Applied in changeset r23557.