In Javascript, when performing a deep copy, how do

Question

I have some library code that is cycling endlessly on me.

I'm not clear on how to best perform cycle detection and avoidance in javascript. i.e. there's no programmatic way of inspecting whether an object came from a "this" reference, is there?

Here's the code. Thanks!

setAttrs: function(config) {
    var go = Kinetic.GlobalObject;
    var that = this;

    // set properties from config
    if(config !== undefined) {
        function setAttrs(obj, c) {
            for(var key in c) {
                var val = c[key];

                /*
                 * if property is an object, then add an empty object
                 * to the node and then traverse
                 */
                if(go._isObject(val) && !go._isArray(val) && !go._isElement(val)) {
                    if(obj[key] === undefined) {
                        obj[key] = {};
                    }
                    setAttrs(obj[key], val);  // <--- offending code; 
                                              // one of my "val"s is a "this" reference
                                              // to an enclosing object
                }

Answer 1

Not unless you want to keep track of every property copied.

But if you're sure that every property is either null, a string, a number, an array or a simple object, you can catch JSON.stringify exceptions to see if there are back references, like this:

try {
    JSON.stringify(obj);
    // It's ok to make a deep copy of obj
} catch (e) {
    // obj has back references and a deep copy would generate an infinite loop
    // Or finite, i.e. until the stack space is full.
}

It's just an idea and I have no idea of the performances. I fear it may be quite slow on large objects.

Answer 2

OK, I've got interested in how that "visited" property @pst mentioned could look like, so I've coded this:

Object.copyCircular = function deepCircularCopy(o) {
    const gdcc = "__getDeepCircularCopy__";
    if (o !== Object(o))
        return o; // primitive value
    var set = gdcc in o,
        cache = o[gdcc],
        result;
    if (set && typeof cache == "function")
        return cache();
    // else
    o[gdcc] = function() { return result; }; // overwrite
    if (o instanceof Array) {
        result = [];
        for (var i=0; i<o.length; i++) {
            result[i] = deepCircularCopy(o[i]);
    } else {
        result = {};
        for (var prop in o)
            if (prop != gdcc)
                result[prop] = deepCircularCopy(o[prop]);
            else if (set)
                result[prop] = deepCircularCopy(cache);
    }
    if (set)
        o[gdcc] = cache; // reset
    else
        delete o[gdcc]; // unset again
    return result;
};

Note, this is only an example. It does not support:

• non-plain objects. Everything with a prototype (except arrays) will not be cloned but copied to a new Object! This includes functions!
• cross-global-scope objects: it uses instanceof Array.
• property descriptors like setters/getters, unwritable and nonenumerable properties

Goodies:

• it does not use a big array which it needs to search each time it encounters an object.

Drawbacks:

• does not work on objects which have a __getDeepCircularCopy__ method that does not what it claims. Although methods (properties with a function as value) are not supported anyway in this lightweight version.

This solution will work on objects with circular references, copying the circular structure, without ending in an infinite loop. Note that "circular" means by here that a property references one of its "parents" in the "tree":

   [Object]_            [Object]_
     /    |\              /    |\
   prop     |           prop    |
     \_____/             |      |
                        \|/     |
                      [Object]  |
                          \     |
                         prop   |
                            \___/

The structure of trees that share a leaf won't be copied, they will become two independent leafes:

            [Object]                     [Object]
             /    \                       /    \
            /      \                     /      \
          |/_      _\|                 |/_      _\|  
      [Object]    [Object]   ===>  [Object]    [Object]
           \        /                 |           |
            \      /                  |           |
            _\|  |/_                 \|/         \|/
            [Object]               [Object]    [Object]

Answer 3

The "reliable and clean" way I know of to deal with this situation is to use a collection of "visited" objects and then react -- terminate, insert symbolic reference, etc -- based on if the current object has already been "visited" or not.

Mr. Crockford uses this approach in cycle.js and he uses an Array for the collection. Excerpt:

// If the value is an object or array, look to see if we have already
// encountered it. If so, return a $ref/path object. This is a hard way,
// linear search that will get slower as the number of unique objects grows.

for (i = 0; i < objects.length; i += 1) {
    if (objects[i] === value) {
        return {$ref: paths[i]};
    }
}

It is unfortunately not possible to use a primitive "Hash" approach for this in JavaScript because it lacks an Identity-Map. While the Array-collection bounds are O(n^2) this is not as bad as it sounds:

This is because, if the "visited" collection is just a guard then the value of n is just the depth of the stack: only cycles are of importance while copying the same object multiple times is not. That is, the objects in the "visited" collection can be pruned on stack-unwind.

In the cycle.js code the "visited" collection cannot be pruned because it must ensure the same symbolic name for a given object is always used which allows the serialization to "maintain the references" when it is restored. However, even in this case, n is only the number of unique non-primitive values traversed.

The only other method I can think of would require adding a "visited property" directly to the objects being traversed, which I would consider a generally undesirable feature. (However, see Bergi's comment about this artifact being [relatively] easily cleaned up.)

Happy coding.