Project

General

Profile

Actions

Bug #1448

closed

[patch] Proper handling of recursive arrays

Added by marcandre (Marc-Andre Lafortune) over 15 years ago. Updated over 13 years ago.

Status:
Closed
Assignee:
-
Target version:
ruby -v:
ruby 1.9.2dev (2009-05-09 trunk 23371) [i386-darwin9.6.0]
Backport:
[ruby-core:23402]

Description

=begin
Dealing with recursive arrays & hashes can be tricky.

The current handling of recursive arrays is much improved over that of Ruby 1.8.6. Array comparison still has some bugs though.

For instance:
x = []; x << x
y = [[x]]
x == y # ==> true
y == x # ==> false, should be true!

Morevoer, recursive arrays that are built the same way are not recognized as equal:
z = []; z << z
x == z # ==> false, should be true!

Needless to say, arrays that have the same elements (e.g. a single element, containing a single element, ...) but built differently way are not recognized as equal:
stone = []; stepping = [stone]; stone << stepping
x == stepping # ==> false, would be nice to be true!

The attached patch fixes all of these problems :-)

  • How:
    The function rb_exec_recursive handles the recursivity by pushing and poping the elements it encounters for a given method (for example eql?). For such comparisons, instead of keeping track of the elements it encounters, I modified it so that it keeps track of both the elements being compared. A recursion is detected only when a matching pair is found.

This takes care of the first problem. For the next two, we only need to observe that if we have a recursion on the pair (x,y) when comparing x and y, then it is because they are not different! Changing the return value for recursive cases from nil (not comparable) / false (different) to Qundef (unknown yet) makes comparison of complex recursive "trees" work beautifully. I've added some cute samples in rubyspecs (core/array/shared/equal.rb)

  • Implementation details:
    Previous recursive_push/pop/check maintained a hash of encountered object ids, setting hash[obj] = true. I modified them so that in "paired" cases, it sets hash[obj] = paired_obj. If a pair (obj, different_paired_obj) is encountered later on, I set hash[obj] to {paired_obj => true, different_paired_obj => true}.

This way, there is basically no runtime cost to this technique, except in the complex recursive cases. Only for these complex cases is there a small additional cost for the hash creation/destruction.

  • 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

The solution is that when calculating the hash for an array, if a recursion is detected, then the hash should return a fixed value (say 0 or -length) for the original array. Currently, 0 is returned but at the level that the recursion is detected. In Ruby pseudo-code, it would look like:

 static VALUE
 recursive_hash(VALUE ary, VALUE dummy, int recur)
 {
     long i, h;
     VALUE n;

     if (recur) {
  •       raise HashingRecursionDetected
    
  •       return LONG2FIX(0);
      }
      h = rb_hash_start(RARRAY_LEN(ary));
      for (i=0; i<RARRAY_LEN(ary); i++) {
          n = rb_hash(RARRAY_PTR(ary)[i]);
          h = rb_hash_uint(h, NUM2LONG(n));
      }
      h = rb_hash_end(h);
      return LONG2FIX(h);
    

    }

    static VALUE
    rb_ary_hash(VALUE ary)
    {
    return rb_exec_recursive(recursive_hash, ary, 0);

  • rescue HashingRecursionDetected
  •   return -length
    
    }

A similar modification must be made for hash.c.

Thanks

Marc-André Lafortune
=end


Files

recursion.patch (7.51 KB) recursion.patch marcandre (Marc-Andre Lafortune), 05/09/2009 11:47 AM
recursion2.patch (7.37 KB) recursion2.patch marcandre (Marc-Andre Lafortune), 05/10/2009 07:37 AM

Related issues 2 (0 open2 closed)

Related to Ruby master - Bug #11385: `==` with bidirectional/cyclic dependencyRejectedcoreActions
Has duplicate Ruby master - Bug #1508: Recursive arrays with the same structure are not eql?.Closed05/24/2009Actions
Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0