检测对象A中的循环引用是否与对象B中的循环引用在结构上相同

Question

我正在实现一个函数来比较两个 JavaScript 对象的 "deep" 相等性。这个函数的框架现在看起来像这样：

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);
}

问题是在它说的地方放什么 // ??? cyclic reference detected。理想情况下，我希望能够说这些对象是深度相等的：

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

并且这些对象不深度相等：

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;

备注：

assert 如果参数为 false 则抛出异常。

x

y

getOwnPropertyNames

have_all_the_same_properties(x, y) 将抛出异常。
is_scalar(x) 实际上 与 typeof x !== 'object'.
为了简洁起见，我在上面的代码中使用了 for-of 循环，但 ES6 功能在解释器中不可用，这实际上运行可用。

Answer 1

这是一个非常简单的算法扩展，用于检查循环引用。它将对应于每个 act 对象的 exp 保存在一个单独的堆栈上，这样它将与在其自身内引用的任何 act 具有相同的索引。

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

克里斯的回答是正确的。我最近写了一个用于深度相等性检查的 util 函数，也需要覆盖循环依赖。这是 github (https://github.com/ryancat/simple-deep-equal) 上的代码，它也涵盖了 NaN 的情况。

检测对象A中的循环引用是否与对象B中的循环引用在结构上相同

Detect whether cyclic reference in object A is structurally the same as cyclic reference in object B

javascript

object

cyclic-reference