ruby - 为什么这个递归不是无限的？

Question

我和我的 friend 们正在做一些基本的 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

这是节点类:

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

我们期望测试的最后一行会导致无限递归直到堆栈溢出，因为它应该不断地相互比较子节点并且永远找不到叶节点。 (我们的印象是数组上的 == 运算符将遍历数组并根据 the array page of RubyDoc 对每个子项调用 ==。)但是如果我们抛出 puts进入==方法查看它被调用的频率，我们发现它被调用了 3 次，然后测试通过。

我们缺少什么？

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

Answer 1

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

{
    // [...]
    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#== 已经实现了您所追求的无限递归保护。