[SOLVED] How to detect circular references in JavaScript

How to detect circular references in JavaScript

For example:

$ node
> var x = {}
undefined
> x.x = x
{ x: [Circular] }

Wondering the sort of structures are they using to accomplish this, because it's not encoded directly into what I just did. It seems like they would do something like:

var graph = new Graph(object)
graph.detectCircularReferences()

And then it would get them, but not sure how that works. Hoping to learn how to implement that.

Solution

Taking into an account the ideas from the comments I came to this function. It traverses the passed object (over arrays and object) and returns an array of paths that point to the circular references.

// This function is going to return an array of paths
// that point to the cycles in the object
const getCycles = object => {
    if (!object) {
        return;
    }

    // Save traversed references here
    const traversedProps = new Set();
    const cycles = [];

    // Recursive function to go over objects/arrays
    const traverse = function (currentObj, path) {
        // If we saw a node it's a cycle, no need to travers it's entries
        if (traversedProps.has(currentObj)) {
            cycles.push(path);
            return;
        }

        traversedProps.add(currentObj);

        // Traversing the entries
        for (let key in currentObj) {
            const value = currentObj[key];
            // We don't want to care about the falsy values
            // Only objects and arrays can produce the cycles and they are truthy
            if (currentObj.hasOwnProperty(key) && value) {
                if (value.constructor === Object) {
                    // We'd like to save path as parent[0] in case when parent obj is an array
                    // and parent.prop in case it's an object
                    let parentIsArray = currentObj.constructor === Array;
                    traverse(value, parentIsArray ? `${path}[${key}]` : `${path}.${key}`);

                } else if (value.constructor === Array) {
                    for (let i = 0; i < value.length; i += 1) {
                        traverse(value[i], `${path}.${key}[${i}]`);
                    }
                }

                // We don't care of any other values except Arrays and objects.
            }
        }
    }

    traverse(object, 'root');
    return cycles;
};

Then you can test it like this:

// Making some cycles.
const x = {};
x.cycle = x;
const objWithCycles = {
    prop: {},
    prop2: [1, 2, [{subArray: x}]]
};
objWithCycles.prop.self = objWithCycles;

console.log(getCycles(objWithCycles));

It produces the following output which is a list of cycles in the object:

[ 'root.prop.self', 'root.prop2[2][0].subArray.cycle' ]