Rileva se il riferimento ciclico nell'oggetto A è strutturalmente uguale al riferimento ciclico nell'oggetto B

Question

Sto implementando una funzione che confronta due oggetti JavaScript per l'uguaglianza "profonda". Lo scheletro di questa funzione, in questo momento, si presenta così:

function check_equal(actual, expected) { 
    var stack = []; 
    function check_equal_r(act, exp) { 
     if (is_scalar(act) || is_scalar(exp)) { 
      assert(act === exp); 

     } else if (stack.indexOf(act) == -1) { 
      assert(have_all_the_same_properties(act, exp)); 
      stack.push(act); 
      for (var k of Object.getOwnPropertyNames(exp)) { 
       check_equal_r(act[k], exp[k]); 
      } 
      stack.pop(act); 

     } else { 
      // ??? cyclic reference detected 
     } 
    } 
    check_equal_r(act, exp); 
} 

La domanda è: cosa mettere in cui si dice // ??? cyclic reference detected. Idealmente, vorrei poter dire che questi oggetti sono profonde-uguali:

var a = {foo:1, bar:2, baz:null}, 
    b = {foo:1, bar:2, baz:null}; 
a.baz = a; 
b.baz = b; 

e questi oggetti sono non deep-equal:

var a = { car: 1, cdr: { car: 2, cdr: null } }; 
var b = { car: 1, cdr: { car: 2, cdr: null } }; 
a.cdr.cdr = a; 
b.cdr.cdr = b.cdr; 

Note:

• assert genera un'eccezione se il suo argomento è falso.
• have_all_the_same_properties(x, y) genera un'eccezione se gli elenchi getOwnPropertyNames di x e non sono identici.
• is_scalar(x) è efficace uguale a typeof x !== 'object'.
• Ho usato un ciclo for-of nel codice di cui sopra per brevità, ma le funzioni ES6 sono non disponibili nell'interprete su cui verrà effettivamente eseguito.

Answer 1

Ecco un'estensione piuttosto semplice all'algoritmo che controlla i riferimenti circolari. Mantiene il exp corrispondente a ciascun oggetto act su uno stack separato, in modo che abbia lo stesso indice di qualsiasi act a cui viene fatto riferimento all'interno di se stesso.

function is_scalar(v) { 
    return typeof v !== 'object'; 
} 

function have_all_the_same_properties(x, y) { 
    var xprops = Object.getOwnPropertyNames(x), 
     yprops = Object.getOwnPropertyNames(y); 
    if (xprops.length === yprops.length) { 
     return xprops.every(function (prop) { 
      return yprops.indexOf(prop) !== -1; 
     }); 
    } 
    return false; 
} 

function check_equal(actual, expected) { 
    var stack = []; 
    var expected_stack = []; 
    function check_equal_r(act, exp) { 
     if (is_scalar(act) || is_scalar(exp)) { 
      return act === exp; 
     } else { 
      var i = stack.indexOf(act); 
      if (i == -1) { 
       if (have_all_the_same_properties(act, exp)) { 
        stack.push(act); 
        expected_stack.push(exp); 
        var res = Object.getOwnPropertyNames(exp).every(function (k) { 
         return check_equal_r(act[k], exp[k]); 
        }); 
        expected_stack.pop(); 
        stack.pop(); 
        return res; 
       } else { 
        return false; 
       } 
      } else { 
       return expected_stack[i] === exp; 
      } 
     } 
    } 
    return check_equal_r(actual, expected); 
} 

var a = {foo:1, bar:2, baz:null}, 
    b = {foo:1, bar:2, baz:null}; 
a.baz = a; 
b.baz = b; 

console.log(check_equal(a, b)); 

var c = { car: 1, cdr: { car: 2, cdr: null } }; 
var d = { car: 1, cdr: { car: 2, cdr: null } }; 
c.cdr.cdr = c; 
d.cdr.cdr = d.cdr; 

console.log(check_equal(c, d)); 

Answer 2

La risposta di Chris è corretta. Recentemente ho scritto una funzione util per il controllo dell'uguaglianza profonda e ho bisogno di coprire anche le dipendenze circolari. Ecco il codice su github (https://github.com/ryancat/simple-deep-equal) che copre anche il caso NaN.