¿Por qué esta recursión NO es infinita?

Question

Mis amigos y yo estamos trabajando en algunos ejercicios básicos de Ruby para familiarizarnos con el idioma, y ​​hemos encontrado un comportamiento interesante que todavía no hemos podido comprender. Básicamente, estamos creando un tipo de datos tree donde solo hay una clase, node, que contiene exactamente un valor y una matriz de cero o más nodes. Estamos usando el corredor de prueba autospec de rspec. En un momento comenzamos a escribir pruebas para rechazar la recursión infinita (una estructura de árbol circular).

Aquí está nuestra prueba:

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 

Aquí está la clase 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 

Esperamos que la última línea de la prueba para dar lugar a un bucle infinito hasta que los desbordamientos de pila, ya que debe continuamente compare los nodos secundarios entre sí y nunca encuentre un nodo hoja. (Estamos bajo la impresión de que el operador == en una matriz iterará sobre la matriz y llamará al == en cada niño, según the array page of RubyDoc). Pero si lanzamos un puts en el método == para ver la frecuencia con que se llama, descubrimos que se llama exactamente tres veces y luego pasa la prueba.

¿Qué nos falta?

Editar: Tenga en cuenta que si reemplazamos be_false en la prueba con be_true, la prueba falla. Por lo tanto, definitivamente cree que las matrices no son iguales, simplemente no está recurriendo a ellas (aparte de las tres llamadas distintas al ==).

Answer 1

Si hace clic en el nombre del método de la RubyDoc se enlazó a, verá la fuente (en C) del método 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); 
} 

Esta aplicación (en concreto el "recursive_equal") sugiere que Array#== ya implementa la protección infinita de recursión que busca.