Is there a way to test circular reference in JavaS

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;
}

Answer 2

This is a small extension to Andris' answer that tells you where the first circular element is so you can deal with it accordingly.

function findCircularObject(node, parents, tree){
    parents = parents || [];
    tree = tree || [];

    if (!node || typeof node != "object")
        return false;

    var keys = Object.keys(node), i, value;

    parents.push(node); // add self to current path
    for (i = keys.length - 1; i >= 0; i--){
        value = node[keys[i]];
        if (value && typeof value == "object") {
            tree.push(keys[i]);
            if (parents.indexOf(value) >= 0)
                return true;
            // check child nodes
            if (arguments.callee(value, parents, tree))
                return tree.join('.');
            tree.pop();
        }
    }
    parents.pop();
    return false;
}

If you don't want a string, the tree array is unnecessary. Just change the original function to

return value;

for the circular object itself or

return parents.pop();

for its parent.

Answer 3

I was thinking about what you're trying to accomplish based off the initial code from your other question. Why not do something like this.

Player = function()
{
    this.UnitTypeXpower = 2
    this.UnitTypeYpower = 7

}

UnitTypeXAdd = function(owner)
{
    owner.UnitTypeXpower++;   
}

That way you don't have to use a circular reference and it accomplishes the same thing.

Answer 4

There is no good way to detect circularity in objects but it is possible though by walking the object tree and checking references. I baked up a node-walking function that tries to detect if a node has been already used as its parent

function isCircularObject(node, parents){
    parents = parents || [];

    if(!node || typeof node != "object"){
        return false;
    }

    var keys = Object.keys(node), i, value;

    parents.push(node); // add self to current path      
    for(i = keys.length-1; i>=0; i--){
        value = node[keys[i]];
        if(value && typeof value == "object"){
            if(parents.indexOf(value)>=0){
                // circularity detected!
                return true;
            }
            // check child nodes
            if(arguments.callee(value, parents)){
                return true;
            }

        }
    }
    parents.pop(node);
    return false;
}

And the usage would be isCircularObject(obj_value) where the function returns true if circularity exists and false if not.

// setup test object
var testObj = {
    property_a:1, 
    property_b: {
        porperty_c: 2
        },
    property_d: {
        property_e: {
            property_f: 3
            } 
        }
    }

console.log(isCircularObject(testObj)); // false

// add reference to another node in the same object
testObj.property_d.property_e.property_g = testObj.property_b;
console.log(isCircularObject(testObj)); // false

// add circular node
testObj.property_b.property_c = testObj.property_b;
console.log(isCircularObject(testObj));  // true

The key point being that an object value is equal with an other value only if it is the same object reference and not when it's another object (even if completely similar).

Answer 5

Here is the code that I am using to detect circular references, it uses the technique that was suggested in the accepted answer by asbjornu, whereby each value is walked through and its reference is maintained in an array so that the next value can be compared with those previously walked.

function isCircular(obj, arr) {
    "use strict";

    var type = typeof obj,
        propName,
        //keys,
        thisVal,
        //iterKeys,
        iterArr,
        lastArr;

    if (type !== "object" && type !== "function") {
        return false;
    }

    if (Object.prototype.toString.call(arr) !== '[object Array]') {
    //if (!Array.isArray(arr)) {
        type = typeof arr; // jslint sake
        if (!(type === "undefined" || arr === null)) {
            throw new TypeError("Expected attribute to be an array");
        }

        arr = [];
    }

    arr.push(obj);
    lastArr = arr.length - 1;

    for (propName in obj) {
    //keys = Object.keys(obj);
    //propName = keys[iterKeys];
    //for (iterKeys = keys.length - 1; iterKeys >= 0; iterKeys -= 1) {
        thisVal = obj[propName];
        //thisVal = obj[keys[iterKeys]];
        type = typeof thisVal;

        if (type === "object" || type === "function") {
            for (iterArr = lastArr; iterArr >= 0; iterArr -= 1) {
                if (thisVal === arr[iterArr]) {
                    return true;
                }
            }

            // alternative to the above for loop
            /*
            if (arr.indexOf(obj[propName]) >= 0) {
                return true;
            }
            */

            if (isCircular(thisVal, arr)) {
                return true;
            }

        }
    }

    arr.pop();

    return false;
}

This code is available on jsfiddle, where you can test it for yourself. I have also run some performance tests on jsperf.

Array.indexOf was only introduced as of Javascript 1.6, see MDN page

Array.isArray was only introduced as of Javascript 1.8.5, see MDN page

Object.keys was only introduced as of Javascript 1.8.5, see MDN page

It is also worth noting that arguments.callee is deprecated and forbidden in strict mode in preference to using named functions