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

Question

我正在实现一个函数来比较两个 JavaScript 对象的“深度”相等性。这个函数的框架现在看起来像这样:

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

问题是在它说的地方放什么 //???检测到循环引用。理想情况下，我希望能够说这些对象是深度相等的:

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 如果其参数为假则抛出异常。
• have_all_the_same_properties(x, y) 如果 x 和 y 的 getOwnPropertyNames 列表不是，则抛出异常相同。
• 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));