URLON.stringify() suffer from a problem, when passed an object that contains a cycle, it will never stop. This article shows 3 techniques in order to detect if an object is cyclical.

Edit the object: Mark

In order to detect a cycle in an object, the method we learn at school is to mark each visited node. When doing a traversal, if we encounter an already marked node, then it is cyclic.

This method alters an object we don't own. It is a dangerous practice and has many side effects.

  • How do we find a unique mark key? I chose to use Math.random but it has a slight chance of giving the wrong result and removing this key from the object!
  • Adding a new key then deleting it makes the object memory size change. Therefore there are great chances of introducing memory copy and at the end of the process, memory holes because of the attribute deletion.
  • It does not work with Sealed objects and Proxies.
function isCyclic (obj) {
  var seenObjects = [];
  var mark = String(Math.random());
 
  function detect (obj) {
    if (typeof obj === 'object') {
      if (mark in obj) {
        return false;
      }
      obj[mark] = true;
      seenObjects.push(obj);
      for (var key in obj) {
        if (obj.hasOwnProperty(key) && !detect(obj[key])) {
          return false;
        }
      }
    }
    return true;
  }
 
  var result = detect(obj);
 
  for (var i = 0; i < seenObjects.length; ++i) {
    delete seenObjects[i][mark];
  }
 
  return result;
}

Keep the mark in a separate data structure

Obviously, we want to avoid editing the object, but what solutions do we have? The only one I found is keeping the visited nodes in an array. Then using indexOf, we can detect if we already visited the node.

However, this is a O(n²) process where the previous one was O(n).

function isCyclic (obj) {
  var seenObjects = [];
 
  function detect (obj) {
    if (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])) {
          return true;
        }
      }
    }
    return false;
  }
 
  return detect(obj);
}

Use native JSON.stringify

The last technique is a bit hacky. When implemented by the browser, JSON.stringify will throw an error if the object happens to be cyclic. It requires a recent browser and feels wrong.

function isCyclic (obj) {
  var isNativeJSON = typeof JSON !== 'undefined' && JSON.stringify.toString().match(/\{ \[native code\] \}$/);
  if (!isNativeJSON) {
    throw 'Native JSON.stringify is not available, can\'t use this technique.';
  }
  try {
    JSON.stringify(obj);
    return true;
  } catch (e) {
    return false;
  }
}

Conclusion

The conclusion is a bit sad, none of the techniques above are satisfying. In order to make a pure-Javascript and efficient version of cycle detection, it would require an Object hash-map, which we don't currently have.

If you are interested, the code source is on github and there's a jsperf that compares the 3 techniques.

Related Work

If you need to store and load circular structures, use Douglas Crockford decycle & retrocycle functions.

If you liked this article, you might be interested in my Twitter feed as well.
 
  • http://twitter.com/EsaMatti Esa-Matti Suuronen

    Underscore.js seems to do cyclic structure detection now. Check it out:

    https://github.com/documentcloud/underscore/blob/9fcaac97b6d4d5e243c5fc9eab27979f8f5fbf59/underscore.js#L708

  • http://blog.vjeux.com/ Vjeux

    They are using the second technique I present.

        var length = stack.length;
        while (length--) {
          if (stack[length] == a) return true;
        }

    Is an equivalent way of writing

          if (seenObjects.indexOf(obj) !== -1) {
            return true;
          }
  • Pingback: [译]JavaScrip:循环对象检测 | 编程·早晨()

  • andres
  • Joel

    Old post now, but worth noting that this find more than just cycles, it just finds if there are two equal objects contained in an object. That is not usually what you want, i.e.,

    var a = { 'foo': 4 };
    var b = { 'keyA': a, 'keyB': a }

    That isn't a cycle, since it is fine as long as 'a' does not re-reference 'b' but your implementation would claim it to be.

  • http://tony.brix.ninja Tony Brix

    you could add `seenObjects.pop()` after the for loop

  • Davide Mannone

    Look for this one: [R-SON][1]

    The files in this collection implement JSON encoders/decoders in JavaScript with this features:

    1. serializes any kind of JavaScript cyclic object, including arrays

    2. deseriliazes any standard JSON and any Reflection decycled object by retrocycling, including arrays

    3. serializes/deserializes JavaScript standard Date and RegExp

    4. Retypes/Reprototypes any user defined JavaScript object

    5. use of standard JSON.stringify and JSON.parse and works with any

    6. written in strong typed TypeScript

    [1]: https://github.com/davidemannone/R-SON/

  • John Doe

    Why not using an object instead of an array and put the keys as Objects straightly and so stop O(n2) ?

    Like so:
    seenObjects = {};

    in the for loop:
    if (seenObject[obj] === true) {return true}
    seenObjects[obj] = true;

  • http://tony.brix.ninja Tony Brix

    objects can only have strings as keys so if obj was an object then it would be converted into seenObjects["[object Object]"] = true

  • Hannan Ali

    @vjeux:disqus Doesn't implementing it using `WeakMap` solve the problem of O(n^2) for the second approach?

 

Related Posts

  • August 29, 2011 Javascript: Improve Cache Performance: Reduce Lookups (2)
    In my Binary Decision Diagram Library, the performance bottleneck was the uniqueness cache. By reducing the number of cache lookup, it is possible to greatly improve the performances. Common pattern In order to test if the key is already in the cache, the usual pattern is to use key […]
  • September 25, 2011 Javascript Object Difference (5)
    This article is about a difference algorithm. It extracts changes from one version of an object to another. It helps storing a smaller amount of information. Template In a project, I have a template object with all the default settings for a widget. var template = { […]
  • August 23, 2011 Javascript – Hook Technique (5)
    Let's go back 5 years ago during the World of Warcraft beta. I was working on Cosmos UI, a projects that aimed to improve the World of Warcraft interface. As interface modification was not officially supported by Blizzard, we went ahead and directly modify the game files written in […]
  • December 7, 2011 C++: Fuzzy Search with Trie (0)
    For a school project, I had to make a part of a spell-check program. Given a dictionnary of words, you have to determine all the words that are within K mistakes of the original word. Trie As input, we've got a list of words along with their frequency. For example, with the following […]
  • August 14, 2012 Image Layout Algorithm – Facebook – Reordering (2)
    In this article, we are going to see how to support dynamic updates to Facebook Image Layout Algorithm. Beware, this is not an easy task and there are many special cases to handle :) Making images bigger To make images bigger we just run the algorithm all over again with the new […]