Structural equivalence of Ruby objects

I have generalized the recursion-safe routine used to compare two arrays, so that it now determines whether two objects are "structurally equivalent". It is fairly powerful, being able to track recursion across instance variables, arrays...

What's this good for?

The obvious application would be checking whether some objects returned by the code under test have the desired structure.

Examples

Here's a taste of what it can do... I'll be using the following class to illustrate the semantics of #struct_eql?.

 class A
   attr_accessor :a, :b
   
   def initialize(a,b)
     @a, @b = a, b
   end
 end

Let's perform some simple tests:

 a = A.new(1, 2)
 a.struct_eql?(A.new(2,3))                       # => true

A.new(2,3) is considered "structurally equivalent" to A.new(1,2) because both objects have two instance variables named @a and @b, and they both refer to Fixnum objects. That's simple, and explains why the following don't match:

 a.struct_eql?(A.new("",1))                      # => false

Object identity

We've seen the basics of the definition of "structural equivalence" proposed here, but there's more. In the above examples, we had another implicit condition:

 a.struct_eql?(A.new(1,1))                       # => false

The "structural equivalence" conditions expressed by A.new(1,2).struct_eql?(b) could be rephrased as:

• b must be an object of class A (or descendants)
• b must have two instance variables named @a and @b
• @a and @b must refer to two Fixnum objects
• @a must be different from @b

The last condition can be reversed to express things like "both instance variables must be equal":

 a = A.new(1,1)
 a.struct_eql?(A.new(2,2))                       # => true
 a.struct_eql?(A.new(2,1))                       # => false

Recursive structures

We can test recursive data for structural equivalence:

 a.b = a
 a.struct_eql?(A.new(2,A.new(2,nil)))            # => false
 a.struct_eql?(A.new(1,1))                       # => false
 b = A.new(5, nil)
 b.b = b
 a.struct_eql?(b)                                # => true
  
 b = A.new(2,2)
 b.b = b
 a.struct_eql?(b)                                # => true

It is also possible to perform tests which involve both object identity and recursion at a time:

 a.b = A.new(A.new(2,A.new(1,a)), 2)             
 b = A.new(5,nil)
 b.b = A.new(A.new(5,A.new(5,b)), 5)
 a.struct_eql?(b)                                # => false

a and b aren't structurally equal in the above example because b.b.a.a is equal to b.b.a.b.a, which was prohibited by the original expression:

 a.b = A.new(A.new(2,A.new(1,a)), 2)             
                   ^       ^
                different values

We get the expected result if those values are changed suitably:

 b.b = A.new(A.new(1,A.new(5,b)), 1)
 a.struct_eql?(b)                                # => true

More stuff

We're not limited to mere Fixnums. For instance, we can check that the two instance variables of an A object refer to the same object:

 o = Object.new
 A.new(o,o).struct_eql? A.new("", "")            # => false
 string = ""
 A.new(o,o).struct_eql? A.new(string, string)    # => true

And we can test recursive data structures with arrays:

 arr = []
 arr << arr
 a = A.new(1, arr)
 a.struct_eql?(A.new(1,[[]]))                    # => false
 arr2 = []
 arr2 << arr2
 b = A.new(4, arr2)
 a.struct_eql?(b)                                # => true

 arr << a
 a.struct_eql?(b)                                # => false
 arr2 << b
 a.struct_eql?(b)                                # => true

More about this coming soon...

Implementation

Usual warning

There's some fun in coding this, and it's not quite the same after reading the solution...

Code

See the original recursion-safe structural comparison routine for arrays for some explanations...

struct_eql.rb

class Object
  def struct_object_id
    object_id
  end
  
  def immediate?
    [FalseClass, TrueClass, NilClass, Fixnum, Symbol].any?{|x| x === self}
  end
end

class Array
  def struct_eql?(o, counter = [0], my_rec = {}, his_rec = {}, helper = {})
    return true if o.struct_object_id == struct_object_id
    return false unless self.class === o
    return false if o.size != size
    
    counter[0] += 1
    my_rec[struct_object_id] = his_rec[o.struct_object_id] = counter[0]
    
    size.times do |i|
      x, y = self[i], o[i]
      if [x,y].any?{|object| object.immediate? }
        return false unless x.struct_eql?(y, counter, my_rec, his_rec, helper)
        next
      end
      xid, yid = x.struct_object_id, y.struct_object_id
      if Array === x and Array === y
        if my_rec[xid] || his_rec[yid]
          if my_rec[xid] != his_rec[yid]
            return false
          else # equal
            next
          end
        else
          return false unless x.struct_eql?(y, counter, my_rec, his_rec, helper)
        end
      elsif Array === x # y is not an array...
        return false
      else
        # general case
        return false unless x.struct_eql?(y, counter, my_rec, his_rec, helper)
      end
    end
    
    true
  end
end

class Object
  def struct_eql?(other, counter = [0], my_rec = {}, his_rec = {}, helper = {})
    return true if other.struct_object_id == struct_object_id
    return false unless self.class === other
    return true if immediate?
    return false unless instance_variables.sort == other.instance_variables.sort
    
    counter[0] += 1
    my_rec[struct_object_id] = his_rec[other.struct_object_id] = counter[0]

    instance_variables.map do |iv|
      x, y = [self, other].map{|obj| obj.instance_variable_get(iv)}
      xid, yid = [x,y].map{|obj| obj.struct_object_id }
      xtag, ytag = my_rec[xid], his_rec[yid]
      if xtag || ytag
        if xtag == ytag
          next
        else
          return false
        end
      end

      counter[0] += 1
      my_rec[xid] = his_rec[yid] = counter[0]

      return false unless x.struct_eql?(y, counter, my_rec, his_rec, helper)
    end
    true
  end
end

Stuff I was too lazy to code (or exercise left to the reader :)

How do we define "structural equivalence" for unordered containers like hashes? If we try to match all the key/value pairs, we might end up having to backtrack... But we can surely find a weaker condition, easy to implement yet useful, a bit more developed than the following:

 # Very little checking at the moment...
 class Hash
   def struct_eql?(other, counter = [0], my_rec = {}, his_rec = {}, helper = {})
     return false unless self.class === other
     return false unless self.size == other.size

     true
   end
 end