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

Question

I am implementing a function that compares two JavaScript objects for "deep" equality. The skeleton of this function, right now, looks like this:

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

The question is what to put where it says // ??? cyclic reference detected. Ideally, I would like to be able to say that these objects are deep-equal:

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

and these objects are not 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;

Notes:

• assert throws an exception if its argument is false.
• have_all_the_same_properties(x, y) throws an exception if the getOwnPropertyNames lists of x and y are not identical.
• is_scalar(x) is effectively the same as typeof x !== 'object'.
• I used a for-of loop in the code above for brevity's sake, but ES6 features are not available in the interpreter this will actually run on.

Answer 1

Here's a pretty easy extension to your algorithm that checks for circular references. It keeps the exp corresponding to each act object on a separate stack, such that it will have the same index as any act which is referenced within itself.

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