Test deep equality *with sharing* of JavaScript objects

Question

Much ink has been spilled on the subject of testing two objects for deep equality in JavaScript. None, however, seem to care about distinguishing the following two objects:

var o1 = [{},{}];
var subitem = {};
var o2 = [subitem, subitem];
var o3 = [{}, {}];

Most deep equality algorithms would say that o1, o2 and o3 are equal. I want an algorithm that says that o1 and o2 are not equal, but o1 and o3 are equal. To put it differently, I want an algorithm that tells me if the pointer graphs have the same structure or not. I care about this because if I have an a modification of the first element is reflected in the second in o2, but not in o1.

This means that deep equality of cyclic structures should work:

var o1 = [];
o1.push(o1);
var o2 = [];
o2.push(o2);
// deepGraphEqual(o1, o2) == true
var o3 = [[]];
o3[0].push(o3);
// deepGraphEqual(o1, o3) == false

If you're going to avoid mutating the items, you are probably going to need ECMAScript6 maps, so I'll accept solutions that use those.

Answer 1

Version with no ES6 features that runs in quadratic time:

function deepGraphEqual(a, b) {
    var left = [], right = [], has = Object.prototype.hasOwnProperty;
    function visit(a, b) {
        var i, k;
        if (typeof a !== 'object' || typeof b !== 'object' || a === null || b === null)
            return a === b;
        if (Object.getPrototypeOf(a) !== Object.getPrototypeOf(b))
            return false;
        for (i = 0; i < left.length; i++) {
            if (a === left[i])
                return b === right[i];
            if (b === right[i])
                return a === left[i];
        }
        for (k in a)
            if (has.call(a, k) && !has.call(b, k))
                return false;
        for (k in b)
            if (has.call(b, k) && !has.call(a, k))
                return false;
        left.push(a);
        right.push(b);
        for (k in a)
            if (has.call(a, k) && !visit(a[k], b[k]))
                return false;
        return true;
    }
    return visit(a, b);
}

Version with ES6 Map that runs in linear time:

function deepGraphEqual(a, b) {
    let left = new Map(), right = new Map(), has = Object.prototype.hasOwnProperty;
    function visit(a, b) {
        if (typeof a !== 'object' || typeof b !== 'object' || a === null || b === null)
            return a === b;
        if (Object.getPrototypeOf(a) !== Object.getPrototypeOf(b))
            return false;
        if (left.has(a))
            return left.get(a) === b
        if (right.has(b))
            return right.get(b) === a
        for (let k in a)
            if (has.call(a, k) && !has.call(b, k))
                return false;
        for (let k in b)
            if (has.call(b, k) && !has.call(a, k))
                return false;
        left.set(a, b);
        right.set(b, a);
        for (let k in a)
            if (has.call(a, k) && !visit(a[k], b[k]))
                return false;
        return true;
    }
    return visit(a, b);
}