为什么这种递归不是无限的？

Question

我和我的朋友正在进行一些基本的Ruby练习以了解语言,我们遇到了一个我们无法理解的有趣行为.基本上,我们创建的tree数据类型只有一个类node,它只包含一个值和一个零或更多的数组nodes.我们正在使用rspec的autospec测试运行器.有一次,我们开始编写测试以禁止无限递归(循环树结构).

这是我们的测试:

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

这是Node类:

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

我们希望测试的最后一行导致无限递归,直到堆栈溢出,因为它应该不断地将子节点相互比较,并且永远不会找到叶节点.(我们的印象是==数组上的运算符将迭代数组并==根据RubyDoc的数组页面调用每个子进程.)但是如果我们puts在==方法中抛出一个方法来查看它被调用的频率,我们发现它被称为正好三次,然后测试通过.

我们缺少什么？

编辑:请注意,如果我们be_false在测试中替换,be_true则测试失败.所以它绝对认为数组不相等,它只是不会对它们进行递归(除了三个不同的调用==).

Answer 1

如果单击链接到的RubyDoc的方法名称,您将看到该方法的源(在C中)Array#==:

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

这个实现(特别是"recursive_equal")表明Array#==已经实现了你所追求的无限递归保护.