json - Is there a way to test circular reference in JavaScript?

Question

I'm making a game, and I've come across a problem... When I try to save, JSON fails and reports that circular reference is being made somewhere. I don't think it actually is, I can't see it, so is there an algorithm or anything which could tell me where it is exactly (between which objects and stuff)? Also, is there a JSON alternative that can save circular reference? I'm running a node.js server, I saw this, but I can't get it to work (it's not made as a module i can require() in my code).

Answer 1

If you want to serialize a circular reference so you can save it, you need to make the reference "virtual" in that it can't be serialized as a circular reference, since that would cause serialization to serialize the same circle of objects forever (or at least until the runtime has run out of memory).

So instead of storing the circular reference itself, you just store a pointer to the object. The pointer will just be something like ref : '#path.to.object' that can be resolved when you deserialize so you point the reference back to the actual object. You just need to break the reference on serialization to be able to serialize it.

Discovering a circular reference in JavaScript can be done by recursively iterating through all objects (with for (x in y)), store x in an array and compare each x with the identity operator (a.k.a. strict comparison operator) === for each z in the temporary array. Whenever x === z equals true, replace the reference to x with a placeholder that will be serialized to the above mentioned ref.

An alternative to keeping an array over "visited" objects is to "taint" the objects you iterate through by setting a property on them, like in this very na?ve example:

for (x in y) {
    if (x.visited) {
       continue;
    }

    x.visited = true;
}