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
                }

Cathode

Keep track of the collection of "visited" objects and don't re-visit an object in that collection. An array will work but doesn't have a good bounds... and arbitrary objects do not make good keys in objects. – Tenorrhaphy

I thought of this... but it seems, for lack of a better word, heavyweight? i.e. there isn't a better solution? – Cathode

I think it's a very common approach when traversing object-graphs. Granted it's more awkward in this case because there is no identity-map in JavaScript. Another (icky) alternative would be to modify the traversed objects with a "visited property". – Tenorrhaphy

This is how Mr. Crockford did it in cycle.js – Tenorrhaphy

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.

Tenorrhaphy

I don't think the "visisited" property is such a bad idea - if you remove it afterwards... – Gileadite

@Gileadite Fair enough. I still feel dirty modify objects in a "copy" operation, though. – Tenorrhaphy

Yes, me too. Also, the "visited"-property-method with a recursive depth-first algorithm doesn't work on any cross-referenced structure, it just detects circles. See my answer :) – Gileadite

Great answer...I'm a bit confused by "only cycles are of importance while copying the same object multiple times is not". Wouldn't it be best to have only one cloned object for each original object? i.e. if there were multiple references to the single object in the original, all those references would still be pointing to a single object in the result. That's probably what the user would expect, and use less memory, would it not? – Shredding

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]

Gileadite

Nice diagrams and explanation. However, I think that if the property contained the "symbolic reference name" (e.g. as used in cycle.js) that could also be wired up to a lookup to maintain the relations (a symbolic lookup is required for text serialization). Alternatively, the property stored, if present, could evaluate to the newly [first] cloned object and just return that on detection... – Tenorrhaphy

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.

Martguerita

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!"
// }

Navigator

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.

Kinder