Comparing circular (self-referenced) objects in JavaScript

Question

I am comparing two objects that contains values as string, number, array and object. To this point there is no problem. When I am trying to compare self-referenced objects I am getting the following error RangeError: Maximum call stack size exceeded. Self-referenced objects should be considered equal if they are referenced to the same level of the other object. My question is how to implement it. Here is my code :

const equalsComplex = function(value, other) {
  // Get the value type
  const type = Object.prototype.toString.call(value);

  // If the two objects are not the same type, return false
  if (type !== Object.prototype.toString.call(other)) return false;

  // If items are not an object or array, return false
  if (['[object Array]', '[object Object]'].indexOf(type) < 0) return false;

  // Compare the length of the length of the two items
  const valueLen =
    type === '[object Array]' ? value.length : Object.keys(value).length;
  const otherLen =
    type === '[object Array]' ? other.length : Object.keys(other).length;
  if (valueLen !== otherLen) return false;

  // Compare two items
  const compare = function(item1, item2) {
    // Get the object type
    const itemType = Object.prototype.toString.call(item1);

    // If an object or array, compare recursively
    if (['[object Array]', '[object Object]'].indexOf(itemType) >= 0) {
      if (!equalsComplex(item1, item2)) return false;
    }

    // Otherwise, do a simple comparison
    else {
      // If the two items are not the same type, return false
      if (itemType !== Object.prototype.toString.call(item2)) return false;

      // Else if it's a function, convert to a string and compare
      // Otherwise, just compare
      if (itemType === '[object Function]') {
        if (item1.toString() !== item2.toString()) return false;
      } else {
        if (item1 !== item2) return false;
      }
    }
  };

  // Compare properties
  if (type === '[object Array]') {
    for (let i = 0; i < valueLen; i++) {
      if (compare(value[i], other[i]) === false) return false;
    }
  } else {
    for (let key in value) {
      if (value.hasOwnProperty(key)) {
        if (compare(value[key], other[key]) === false) return false;
      }
    }
  }

  // If nothing failed, return true
  return true;
};
const r = { a: 1 };
r.b = r;
const d = { a: 1 };
d.b = d;

console.log(
  equalsComplex(
    {
      a: 2,
      b: '2',
      c: false,
      g: [
        { a: { j: undefined } },
        { a: 2, b: '2', c: false, g: [{ a: { j: undefined } }] },
        r
      ]
    },
    {
      a: 2,
      b: '2',
      c: false,
      g: [
        { a: { j: undefined } },
        { a: 2, b: '2', c: false, g: [{ a: { j: undefined } }] },
        r
      ]
    }
  )
);

Answer 1

Before we begin

Is there a reason you aren't using an existing library like deep-equal? Sometimes it's easier to use code that's already written for you than to write it yourself

Now fixing a few simple issues in the code

For starters, utilizing Object.prototype.toString to determine the type feels like a hack, and might risk bugs in the future if different browsers implement the toString method differently. If someone knows whether or not the toString method's return value is explicitly defined in the ECMAScript specification, please chime in. Otherwise, I would avoid this hack, because JavaScript provides a perfect alternative: typeof https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/typeof

Interestingly typeof value will return the same for both objects and arrays, because as far as ECMAScript is concerned, arrays are a subclass of objects. Therefore your later comparison for [Object object] and [Object Array] can be simplified to just checking the type for object

Once you start using typeof value instead of Object.prototype.toString.apply(value), you will need a way to differentiate objects from arrays for comparison. For this purpose, you can use Array.isArray

On to the meat of the problem

Now regarding self-references, the issue you're referring to is a cycle. A simple cycle would be:

var a = {};
a.foo = a;

This creates the cycle: a.foo.foo.foo.foo.foo.... == a

There is a nice way to check if two references point to the same object in JavaScript, which is good for determining when equality is true, but it won't help in the case when equality is false. To check if two references point to the same object, just use the == operator! This returns true is the objects point to the exact same instance in memory. For instance:

var a = {foo: "bar"}
var b = {foo: "bar"}
var c = a;

a == b; // false
a == c; // true
b == c; // false

So you can trivially see if two references are the same by checking that item1 == item2

But when they don't equal, you will still do a complexCompare, which will dive into each self-reference, and will have the same stack overflow. To resolve this, you need a way to detect cycles. As with deep equality, there are libraries for this, but for intellectual reasons we'll see if we can recreate them.

To do this, we need to remember every other object we've seen, and compare with them as we recurse. A simple solution might look like:

var objectsWeveSeen = [];

function decycle(obj) {
    for (var key in obj) {
        if (typeof obj[key] == "object") {
            for (var i = 0; i < objectsWeveSeen.length; i++) {
                if (objectsWeveSeen[i] == obj[key]) {
                    obj[key] = "CYCLE! -- originally seen at index " + i;
                }
            }
            objectsWeveSeen.push(obj[key]);
        }
    }
}

(NOTE: This decycle function is destructive. It modifies the original object. Also, this decycle function isn't recursive, so it actually sucks. But it at least gives you the general idea and you can try to write your own, or look at how others have done it)

We could then pass an object to it like so:

var a = {foo: {}};
a.baz = a.foo;
console.log(decycle(a));
// Outputs: {foo: {}, baz: "CYCLE! -- originally seen at index 0"}

Since this object lacks cycles, you can now perform your complex comparison on it:

complexCompare(decycle(a));

Of course there are still some edge cases to consider. Are two Date objects equivalent if they reference the same time, but have different timezones? Does null equal null? And my simple decycle algorithm fails to account for a reference to the root object, it only remembers all keys that it has seen (although this should be simple for you to add if you think about it)

A not-quite-perfect but working-on-it solution

I haven't written out a perfect deep-equals implementation for two reasons:

1. I feel like writing code is the best way to learn, not copying and pasting it from others
2. I'm sure there are edge cases I'm not thinking about (which is the reason you should use a battle-tested library like Lodash instead of writing your own code) and by admitting that this is an incomplete solution instead of selling it as what it isn't, you will be encouraged to go find someone who has written a more complete answer

function complexCompare(value, other) {
    var objectsWeveSeen = [];
    function nonDestructiveDecycle(obj) {
        var newObj = {};
        for (var key in obj) {
            newObj[key] = obj[key];
            if (typeof obj[key] == "object") {
                for (var i = 0; i < objectsWeveSeen.length; i++) {
                    if (objectsWeveSeen[i] == obj[key]) {
                        newObj[key] = "CYCLE! -- originally seen at index " + i;
                        break;
                    }
                }
                objectsWeveSeen.push(obj[key]);
            }
        }
        return newObj;
    }

    var type = typeof value;
    if (type !== typeof other) return false;

    if (type !== "object") return value === other;

    if (Array.isArray(value)) {
        if (!Array.isArray(other)) return false;

        if (value.length !== other.length) return false;

        for (var i = 0; i < value.length; i++) {
            if (!complexCompare(value[i], other[i])) return false;
        }

        return true;
    }

    // TODO: Handle other "object" types, like Date

    // Now we're dealing with JavaScript Objects...
    var decycledValue = nonDestructiveDecycle(value);
    var decycleOther = nonDestructiveDecycle(other);

    for (var key in value) {
        if (!complexCompare(decycledValue[key], decycleOther[key])) return false;
    }

    return true;
}

Update

In response to comments:

== versus ===

== performs a "loose" comparison between two variables. For instance, 3 == "3" will return true. === performs a "strict" comparison between two variables. So 3 === "3" will return false. In our case, you can use whichever you prefer and there should be no difference in the outcome, because:

• typeof always returns a string. Therefore typeof x == typeof y is the exact same as typeof x === typeof y
• If you check that two variables are the same type before you compare their values, you should never run into one of the edge cases where == and === return different results. For instance, 0 == false but typeof 0 != typeof false (0 is a "number" and false is a "boolean")

I stuck with == for my examples because I felt like it would be more familiar to avoid any confusion between the two

[] versus Set

I took a look at using Set to re-write decycle and quickly ran into an issue. You can use Set to detect if there is a cycle, but you can't trivially use it to detect that two cycles are identical. Notice that in my decycle method that I replace a cycle with the string CYCLE! -- originally seen at index X. The reason for this "at index X" is because it tell you which object was referenced. Instead of just having "some object we've seen before", we have "THAT object that we've seen before". Now if two objects reference the same one, we can detect that (because the strings will be equal, having the same index). If two objects reference different ones, we will detect that as well (because the strings will not be equal)

There is, however, a problem with my solution. Consider the following:

var a = {};
a.foo = a;

var b = {};
b.foo = b;

var c = {};
c.foo = a;

In this case my code would claim a and c are equal (because they both reference the same object) but a and b are not (because even though they have the same values, same patterns, and same structures - they reference different objects)

A better solution may be to replace the "index" (a number representing the order in which we found the objects) with "path" (a string representing how to reach the object)

var objectsWeveSeen = []

function nonDestructiveRecursiveDecycle(obj, path) {
    var newObj = {};
    for (var key in obj) {
        var newPath = path + "." + key;
        newObj[key] = obj[key];
        if (typeof obj[key] == "object") {
            for (var i = 0; i < objectsWeveSeen.length; i++) {
                if (objectsWeveSeen[i].obj == obj[key]) {
                    newObj[key] = "$ref:" + objectsWeveSeen[i].path;
                    break;
                }
            }
            if (typeof newObj[key] != "string") {
                objectsWeveSeen.push({obj: obj[key], path: newPath});
                newObj[key] = nonDestructiveRecursiveDecycle(obj[key], newPath);
            }
        }
    }
    return newObj;
}

var decycledValue = nonDestructiveRecursiveDecycle(value, "@root");