Why is this recursion NOT infinite?

Question

My friends and I are working on some basic Ruby exercises to get a feel for the language, and we've run into an interesting behavior that we're yet unable to understand. Basically, we're creating a tree data type where there's just one class, node, which contains exactly one value and an array of zero or more nodes. We're using rspec's autospec test runner. At one point we started writing tests to disallow infinite recursion (a circular tree structure).

Here's our test:

it "breaks on a circular reference, which we will fix later" do
  tree1 = Node.new 1
  tree2 = Node.new 1
  tree2.add_child tree1
  tree1.add_child tree2
  (tree1 == tree2).should be_false
end

Here's the Node class:

class Node
  attr_accessor :value
  attr_reader :nodes

  def initialize initial_value = nil
    @value = initial_value
    @nodes = []
  end

  def add_child child
    @nodes.push child
    @nodes.sort! { |node1, node2| node1.value <=> node2.value }
  end

  def == node
    return (@value == node.value) && (@nodes == node.nodes)
  end
end

We expect the last line of the test to result in an infinite recursion until the stack overflows, because it should continually compare the child nodes with each other and never find a leaf node. (We're under the impression that the == operator on an array will iterate over the array and call == on each child, based on the array page of RubyDoc.) But if we throw a puts into the == method to see how often it's called, we discover that it's called exactly three times and then the test passes.

What are we missing?

Edit: Note that if we replace be_false in the test with be_true then the test fails. So it definitely thinks the arrays are not equal, it's just not recursing over them (aside from the three distinct calls to ==).

Answer 1

If you click on the method name of the RubyDoc you linked to, you will see the source (in C) of the Array#== method:

{
    // [...]
    if (RARRAY(ary1)->len != RARRAY(ary2)->len) return Qfalse;
    if (rb_inspecting_p(ary1)) return Qfalse;
    return rb_protect_inspect(recursive_equal, ary1, ary2);
}

This implementation (specifically the "recursive_equal") suggests that Array#== already implements the infinite recursion protection you're after.

Answer 2

Where is the recursive call?

Putting aside the question, "how is this a tree?" I guess I am confused how you think tree1==tree2 should not terminate. After you instantiate 2 "trees" and make the two add_child calls you have two object with the value of 1 and an array of size 1. The nested arrays inside that 1 element are not iterated over by ==