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

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

本文关键字：循环 引用 对象 结构上 检测 是否      更新时间：2023-09-26

我正在实现一个函数，比较两个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);
}

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

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

和这些对象不是 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;

指出:

  • assert在参数为false时抛出异常。
  • have_all_the_same_properties(x, y)抛出异常，如果x和y的getOwnPropertyNames列表不相同。
  • is_scalar(x)的与typeof x !== 'object'的相同。为了简洁起见，我在上面的代码中使用了for-of循环，但是ES6的特性是在解释器中没有可用。

这是对循环引用检查算法的一个非常简单的扩展。它将exp与每个act对象保持在一个单独的堆栈上，这样它将具有与自身引用的任何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));

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

相关文章：