Perché questa ricorsione NON è infinita?

Question

I miei amici e io stiamo lavorando ad alcuni esercizi di base su Ruby per avere un'idea del linguaggio, e ci imbattiamo in un comportamento interessante che non siamo ancora in grado di capire. Fondamentalmente, stiamo creando un tipo di dati tree in cui esiste una sola classe, node, che contiene esattamente un valore e un array pari a zero o più nodes. Stiamo utilizzando il test runner autospec di rspec. A un certo punto abbiamo iniziato a scrivere test per non consentire la ricorsione infinita (una struttura ad albero circolare).

Ecco la nostra prova:

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 

Ecco la classe 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 

Ci aspettiamo che l'ultima riga del test al risultato in una ricorsione infinita fino agli overflow dello stack, perché dovrebbe continuamente confrontare i nodi figlio tra loro e non trovare mai un nodo foglia. (Abbiamo l'impressione che l'operatore == su un array itererà sull'array e chiamerà == su ogni bambino, in base a the array page of RubyDoc.) Ma se lanciamo un puts nel metodo == per vedere quanto spesso viene chiamato, scopriamo che è chiamato esattamente tre volte e poi passa il test.

Cosa ci manca?

Modifica: Si noti che se si sostituisce be_false nel test con be_true, il test ha esito negativo. Quindi sicuramente pensa che gli array non siano uguali, non si ripercuote su di essi (a parte le tre chiamate distinte a ==).

Answer 1

Se si fa clic sul nome del metodo della RubyDoc si è collegato al, si vedrà la sorgente (in C) del metodo 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); 
} 

Questa implementazione (in particolare il "recursive_equal") suggerisce che Array#== implementa già la protezione di ricorsione infinita che stai cercando.