In Javascript, when performing a deep copy, how do I avoid a cycle, due to a property being “this”?

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

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.

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

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 4

Here's a simple recursive clone method. Like many others solutions, most non-basic properties will share a reference with the original object (such as functions).

It handles infinite loops by keeping a map of referenced objects so subsequent references can share the same clone.

const georgeCloney = (originalObject, __references__ = new Map()) => {
  if(typeof originalObject !== "object" || originalObject === null) {
    return originalObject;
  }

  // If an object has already been cloned then return a
  // reference to that clone to avoid an infinite loop
  if(__references__.has(originalObject) === true) {
    return __references__.get(originalObject);
  }

  let clonedObject = originalObject instanceof Array ? [] : {};

  __references__.set(originalObject, clonedObject);

  for(let key in originalObject) {
    if(originalObject.hasOwnProperty(key) === false) {
      continue;
    }

    clonedObject[key] = georgeCloney(originalObject[key], __references__);
  }

  return clonedObject;
};

Example usage...

let foo = {};
foo.foo = foo;

let bar = georgeCloney(foo);
bar.bar = "Jello World!";

// foo output
// {
//   foo: {
//     foo: {...}
//   }
// }
// 
// bar output
// { 
//   foo: { 
//     foo: {...},
//     bar: "Jello World!"
//   }, 
//   bar: "Jello World!"
// }

Answer 5

I had to do this for an interview and this is what I got:

Object.defineProperty(Object.prototype, 'deepclone', { enumerable :false, configurable :true, value :function(){
  let map /*for replacement*/ =new Map(), rep ={} ;map.set(this, rep)
  let output = (function medclone(_, map){  let output ={..._}
    for(let k in _){  let v =_[k]
      let v2 ;if(!(v instanceof Object)) v2 =v ;else {
        if(map.has(v)) v2 =map.get(v) ;else {
          let rep ={}
          map.set(v, rep), v2 =medclone(v, map)
          Replace(rep, v2), map.set(v, v2)
        }
      }
      output[k] =v2
    }    return output
  })(this, map)
  Replace(rep, output)
  return output
  /*[*/ function Replace(rep/*resentative*/, proper, branch =proper, seens =new Set()){
    for(let k in branch){  let v =branch[k]
      if(v ===rep) branch[k] =proper
      else if(v instanceof Object &&!seens.has(v)) seens.add(v), Replace(rep, proper, v, seens)
    }
  }/*]*/
} })
                                                                                                                                  // Code is freely available for use for academia/scrutiny. As for development, contact author. 

The methodology is "hack and slash" instead of "plan with ample time before coding", so the result can't be all that great but it works. could iterate on it to remove the WET in the recursion entry point, for one.