Почему эта рекурсия НЕ бесконечна?

Question

Мои друзья и я работаем над некоторыми базовыми упражнениями на Ruby, чтобы почувствовать язык, и мы столкнулись с интересным поведением, которое мы пока не можем понять. По сути, мы создаем тип данных tree, в котором есть только один класс, node, который содержит ровно одно значение и массив с нулем или более nodes. Мы используем rspec . В какой-то момент мы начали писать тесты, чтобы запретить бесконечную рекурсию (круговая древовидная структура).

Вот наш тест:

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#== уже реализует защиту от бесконечной рекурсии, которую вы ищете.