How can I detect recursive arrays and hashes?

Question

How can I detect arrays or hashes that include a recursive structure like a, b, and c below?

• Simplest instance of recursive array

  a = []
  a[0] = a
  a # => [[...]]
  

• Recursion cycle/depth is not one

  b = [[], :foo]
  b[0][0] = b
  b # => [[[...]], :foo]
  

• Recursion at a non-root level

  c = [a, :foo]
  c # => [[...], :foo]
  

Answer 1

I love recursion.

Here's a decent way, iterating through everything and keeping a hash of objects you have seen (for fast lookup)

class Object
  def is_recursive?(known = {})
    false
  end
end

module Enumerable
  def is_recursive?(known = {})
    return true if known.include?(self)
    known[self] = true
    begin
      any? do |*args|
        args.any?{|item| item.is_recursive?(known)}
      end
    ensure
      known[self] = false
    end
  end
end

x = []; x << x
p x.is_recursive? # => true
p ({x => 42}).is_recursive? # => true
p [{foo: x}].is_recursive? # => true
p [[[[[[:foo], {bar: [42]}]]]]].is_recursive? # => false

Mind you, this is a bit rough and you could run into trouble. For example you'd have endless loops with [1..Float::INFINITY].is_recursive?, although that's easily salvable with

class Range
  def is_recursive?(known = {})
    false # optimization
  end
end

Answer 2

You can't flatten a recursive array, so you could check it by:

begin
  a.flatten
rescue ArgumentError => e
  e.to_s =~ /recursive/
end