Detecting and fixing circular references in JavaScript

Solution 1:

Pulled from http://blog.vjeux.com/2011/javascript/cyclic-object-detection.html. One line added to detect where the cycle is. Paste this into the Chrome dev tools:

function isCyclic (obj) {
  var seenObjects = [];

  function detect (obj) {
    if (obj && typeof obj === 'object') {
      if (seenObjects.indexOf(obj) !== -1) {
        return true;
      }
      seenObjects.push(obj);
      for (var key in obj) {
        if (obj.hasOwnProperty(key) && detect(obj[key])) {
          console.log(obj, 'cycle at ' + key);
          return true;
        }
      }
    }
    return false;
  }

  return detect(obj);
}

Here's the test:

> a = {}
> b = {}
> a.b = b; b.a = a;
> isCyclic(a)
  Object {a: Object}
   "cycle at a"
  Object {b: Object}
   "cycle at b"
  true

Solution 2:

@tmack's answer is definitely what I was looking for when I found this question!

Unfortunately it returns many false positives - it returns true if an object is replicated in the JSON, which isn't the same as circularity. Circularity means that an object is its own child, e.g.

obj.key1.key2.[...].keyX === obj

I modified the original answer, and this is working for me:

function isCyclic(obj) {
  var keys = [];
  var stack = [];
  var stackSet = new Set();
  var detected = false;

  function detect(obj, key) {
    if (obj && typeof obj != 'object') { return; }

    if (stackSet.has(obj)) { // it's cyclic! Print the object and its locations.
      var oldindex = stack.indexOf(obj);
      var l1 = keys.join('.') + '.' + key;
      var l2 = keys.slice(0, oldindex + 1).join('.');
      console.log('CIRCULAR: ' + l1 + ' = ' + l2 + ' = ' + obj);
      console.log(obj);
      detected = true;
      return;
    }

    keys.push(key);
    stack.push(obj);
    stackSet.add(obj);
    for (var k in obj) { //dive on the object's children
      if (Object.prototype.hasOwnProperty.call(obj, k)) { detect(obj[k], k); }
    }

    keys.pop();
    stack.pop();
    stackSet.delete(obj);
    return;
  }

  detect(obj, 'obj');
  return detected;
}

Here are a few very simple tests:

var root = {}
var leaf = {'isleaf':true};
var cycle2 = {l:leaf};
var cycle1 = {c2: cycle2, l:leaf};
cycle2.c1 = cycle1
root.leaf = leaf

isCyclic(cycle1); // returns true, logs "CIRCULAR: obj.c2.c1 = obj"
isCyclic(cycle2); // returns true, logs "CIRCULAR: obj.c1.c2 = obj"
isCyclic(leaf); // returns false
isCyclic(root); // returns false

Solution 3:

Here is MDN's approach to detecting and fixing circular references when using JSON.stringify() on circular objects: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Errors/Cyclic_object_value :

In a circular structure like the following

var circularReference = {otherData: 123};
circularReference.myself = circularReference;

JSON.stringify() will fail:

JSON.stringify(circularReference);
// TypeError: cyclic object value

To serialize circular references you can use a library that supports them (e.g. cycle.js) or implement a solution by yourself, which will require finding and replacing (or removing) the cyclic references by serializable values.

The snippet below illustrates how to find and filter (thus causing data loss) a cyclic reference by using the replacer parameter of JSON.stringify():

const getCircularReplacer = () => {
      const seen = new WeakSet();
      return (key, value) => {
        if (typeof value === "object" && value !== null) {
          if (seen.has(value)) {
            return;
          }
          seen.add(value);
        }
        return value;
      };
    };

JSON.stringify(circularReference, getCircularReplacer());
// {"otherData":123}

Solution 4:

This is a fix for both @Trey Mack and @Freddie Nfbnm answers on the typeof obj != 'object' condition. Instead it should test if the obj value is not instance of object, so that it can also work when checking values with object familiarity (for example, functions and symbols (symbols aren't instance of object, but still addressed, btw.)).

I'm posting this as an answer since I can't comment in this StackExchange account yet.

PS.: feel free to request me to delete this answer.

function isCyclic(obj) {
  var keys = [];
  var stack = [];
  var stackSet = new Set();
  var detected = false;

  function detect(obj, key) {
    if (!(obj instanceof Object)) { return; } // Now works with other
                                              // kinds of object.

    if (stackSet.has(obj)) { // it's cyclic! Print the object and its locations.
      var oldindex = stack.indexOf(obj);
      var l1 = keys.join('.') + '.' + key;
      var l2 = keys.slice(0, oldindex + 1).join('.');
      console.log('CIRCULAR: ' + l1 + ' = ' + l2 + ' = ' + obj);
      console.log(obj);
      detected = true;
      return;
    }

    keys.push(key);
    stack.push(obj);
    stackSet.add(obj);
    for (var k in obj) { //dive on the object's children
      if (obj.hasOwnProperty(k)) { detect(obj[k], k); }
    }

    keys.pop();
    stack.pop();
    stackSet.delete(obj);
    return;
  }

  detect(obj, 'obj');
  return detected;
}