From: Christoph Rippel <crippel@...>
Date: 2001-02-26T07:37:19+09:00
Subject: [ruby-talk:11553] Re: Array bugs?

> From: ts [mailto:decoux@moulon.inra.fr]
[...]

>  I'll try to explain what do ruby actually
> 
> M> def f(x); [x,x]; end
> M> def g(x); f f f f f f f f x; end
> M> (g g g 1) == (g g g 1) #=> true
> 
>  In this case it do something like this :
>    
>    class Array
>       def ==(other)
>          each_index do |i|
>             return false if not self[i] == other[i]
>          end
>          true
>       end
>    end

to be exact 

class Array
	def ==(other)
		return false unless other.kind_of? Array
		return false unless length == other.length
		# unfortunately the id-sanity check 
		# return true if  id == other.id
		# is missing - Why?	    	
          	each_index do |i|
             	return false if not self[i] == other[i]
          	end
          	true
       end
end

> 
>  This explain why it has problem with recursive array.
> 
> >> 
> >> def f(x); [x,x]; end
> >> def g(x); f f f f f f f f x; end
> >> p (g g g 1)
> 
>  In this case inspect is protected, and ruby do (this is *very* simplified) 
> 
>    class Array
>       def inspect
>          return '[]' if empty?
>          return '[...]' if @inspect.include? id
>          begin
>             @inspect.push id
>             str = '['
>             each do |i|
>                str << i.inspect
>             end
> 	    str << ']'
>          ensure
>             @inspect.pop
>          end
>          str
>       end
>    end
> 
>  where @inspect is in reality a thread local variable.
>
>  This is why it take a very long time to find 'p (g g g 1)' because all
> recursive calls are replaced with a 'begin ... ensure'

interesting ...  

> C> ##########################
> C> p ([1,3,3,[3,4],"a"] == [1,3,3,[3,4],"a"]) 
> C> p ([1,3,3,[3,4],"a"] == [1,3,3,[3,4],"b"])
> 
> C> ##########################
> C> a =[1,2,3]; a << a; b =[1,2]; b << b;  a  << a; b << a; 
> C> p a - b; p a; p b
> 
>  In this case it give the good result

good, but you told me that 

> pigeon% ruby -e 'a=[1]; a << a; b = [1] ; b << b; p b - a '
> [[1, [...]]]
> pigeon%

did this change? I get [] - that is  ''a == b '' - 
but this decision is debatable (the ladder interpretation
means that you identify array's with a special kind of
``marked graphs''). Anyway I thought about this problem
a little longer ...

Since ruby's equality algorithm  (for non-recursive array's- 
the  ``id-sanity check'' should be added so) never terminates
for RCO's, recursive container Objects (or whatever you want
to call them) it seems to me that you are basically free to
choose between ``a == b''  and ``a != b''. (The ladder
scheme basically boils down to infinite loop protection - 
see below.)

(Besides their entertaining curiosity value for me;-)  RCO's 
seem like very bad  ``type citizens'' - in many computer
languages you cannot form them and in math they are strictly
forbidden since they let to inconsistencies.

On the practical side the infinite recursion problem is
a consequence that you are performing an unsupported 
operation (that includes asking for equality! - if the 
objects are unequal you are still fine) and throwing an
exception actually seems like the right thing to-do - a  
''catchable'' ``SystemStackError'' exception is as good as
any other exception IMO.
Ideally the formation of an RCO would be flagged with an
exception at creation time but such a scheme would bring
the language to a crawl (that's a problem with liberal
languages like ruby that they cannot be practically
defended against all abuses at runtime).  

In conclusion I believe that the right thing to do is to
remove all infinite recursion protections against
RCO's - if you want to shoot your self in the foot you 
are free to-do so ... that would mean removing the 
infinite recursion protection from  #flatten(!) (the 
algorithm rejects some non recursive arrays anyway) - 
and guard  critical sections by trying  to catch 
``SystemStackError'' exceptions if you suspect that
a RCO might occur.
Unfortunately the taint/freeze scheme does not protected
against RCO's so adding some RCO detection facilities
might be a good idea? Maybe add an equality (flatten,
hash) for RCO's  passed on an untangle scheme as a
Module? (but I doubt that there will be many takers.)

  
> C> ##########################
> C> def f(x); [x,x]; end
> C> def g(x); f f f f f f f f x; end
> C> def h(x); g g g g g g g g x; end
> C> def i(x);  h h h h h h h h x; end
> C> def j(x); i i i i  i i i   x;end
> 
> C> p (j(1) == j(1))
> 
>  Here it take too long time to compute it.

it would take 2**(8*8*8*7 +1) - 1 = 2**3585 - 1 Object
comparisons (not counting the length comparisions and 
type check) - note who ever that the memory usage in 
contrast to a true RCO won't go through the roof -  

Christoph

Ps.  Could you send me your patch? - maybe I could
take a look at it?. Anyway try ``your ruby'' on a 
couple of nasty potentially equal recursive arrays.


----------------------------
$ ruby UntangleVar.rb
true
false
[[1, [...]]]
[3]
[1, 2, 3, [...], [...]]
[1, 2, [...], [1, 2, 3, [...], [...]]]
[3]
[1, 2, 3, [...], [...]]
[1, 2, [...], [1, 2, 3, [...], [...]]]
[[1, 2, 3, [...], [...]]]
[[1, 2, 3, [...], [...]]]
true
----------------------------
class Object
def  no_loop (id_bag) ; true end		
end


class IdBag
def initialize
	@bag = {}	
end
def initialize
	@bag = {}
end
def  include_pair a, b
	@bag[a+ (b << Fixnum::Maxlog)] = 1
end	
def included_pair? a,b
	@bag.key?  (a+ (b << Fixnum::Maxlog))
end
private
class Fixnum
Maxlog =  32  
end	                    
end                        

	
class Array
def  no_loop (id_bag)
		level_id_bag = IdBag.new
		each do  |r|
			next if level_id_bag.included_pair? id, r.id
			level_id_bag.include_pair id, r.id
			return false unless r.detect_loop (id_bag)
			return false if id_bag.included_pair? id, r.id
			id_bag.include_pair id,r.id
		end
		return true
end		
alias :old_equal :==
def ==(other)
	return true if id == other.id
	return false unless no_loop(IdBag.new)
	self.old_equal other
end
end
	

p ([1,3,3,[3,4],"a"] == [1,3,3,[3,4],"a"]) 
p ([1,3,3,[3,4],"a"] == [1,3,3,[3,4],"b"])
a=[1]; a << a; b = [1] ; b << b; p b - a 
a =[1,2,3]; a << a; b =[1,2]; b << b;  a  << a; b << a; 
p a - b; p a; p b
c = [1,2,3]; c << c; b =[1,2]; b << b;  c  << c; b << c; 
p c - b, c, b
p c - a, a - c


def f(x); [x,x]; end
def g(x); f f f f f f f f x; end
def h(x); g g g g g g g g x; end
def i(x);  h h h h h h h h x; end
def j(x); i i i i  i i i   x;end

p ((f f  1) == (f f 1))


----------------------------
Recursion unprotected (corrected) flatten
not tested

class Array
def flatten
	res = []
	each do |i|
		if i.kind_of? Array 	
			res+= i.flatten
		else
			res << i
		end
	end
	res
end
end

----------------------------
Recursion limited hash value
not tested

class Object
def protected_hash(level)
    #ignore level
    hash
end
end

class Array
def protected_hash (level)
	return 0 if level < 1
	hsh = 0  	
	each do |i| 
		hsh ^= i.protected_hash (level- 1) 
  	end
	return hsh
end
def hash
	untangled_hash 5
end
end
----------------------------