© 2019 Meouzer Consortium

Deep Copies with Circular References

Meouzer The Curiously Deep Copy Cat meouzer@gmail.com
loading
In deep copyying, handling circlular refences is the easy part. Meouzer

Meouzer is biting his tail, which somehow just seems relevant.

Full code at Deep-Copy-Literals.js, which has no dependencies.

In an object tree, if two nodes are equal they are circular references if one is an ancestor of the other, but otherwise they are duplicate references. Circular references tend to cause infinite recursion in naive algorithms, while duplicate references do not.

Introduction

Our goal is to show how to break circular references, so we take it easy and stick to copying literals.

The following is probably the simplest way to process a tree of nodes in preorder, with upper most node topNode.

function processInPreOrder(topNode) { var stack = [topNode]; while(stack.length > 0) { var node = stack.pop(); // process node here // push children onto stack for further processing for(var length = node.children.length, k = length - 1; k ≥ 0; k--) { stack.push(node.children[k]); } } }

However, it adequate for only the most basic tasks. One problem is that once a node is on the stack, it's ancestors have already been popped off. You can in fact transverse in preorder while keeping ancestors on the stack and doing so makes dealing with circular references a one liner, with some supporting code of course. Also the stack consists of nodes when it's possible that it should contain additional information for processing needs. So a member of the stack should roughly resemble something like {node:x, otherInfo:info, ...}.

In deep copying, stack members may be like {node:x, children:x.children, index:3} where index points to the child node currently being processed. When index passes its max = x.children.length - 1, all children of the node x have been processed, and x can then be popped off the stack. So a child while processing will always have its parent on the stack.

Power Preorder Transversals

unavailable

This tree can be "represented" in literal notation as var tree = {a:{b:{e:{},f:{}},c:{g:{}, h:{}},d:{i:{}, k:{}}}}. Let's process the "nodes" of this tree in a preorder transversal.

The Basic and Powerful Preorder Transversal
var tree = { a: { b:{e:{},f:{}}, c:{g:{}, h:{}, i:{}}, d:{j:{}, k:{}} } } function aPreorderTransversal(tree) { var stack = []; stack.push({node:tree, childKeys:Object.getOwnPropertyNames(tree), index:0}); while(stack.length > 0) { var T = stack[stack.length - 1]; // top of stack var node = T.node; // node at top of stack var childKeys = T.childKeys; // its child keys to access children if(T.index < childKeys.length ) { // process child of node at current index here console.log(childKeys[T.index]); // log key of child var child = node[childKeys[T.index]]; // child of node // push child node onto the stack stack.push({node:child, childKeys:Object.getOwnPropertyNames(child), index:0}); T.index++; // process next child of node } else { stack.pop(); } } } aPreorderTransversal(tree); // The nodes are logged in preorder a, b, e, f, c, g, h, i, d, j, k.

The above is the preorder transversal framework that can accomplish major things: stringification of objects, deep copying, and in part helps with breaking circular references in deep copying. Of course members of the stack may become more complicated with other information for the need.

We will next show how to deep copy literal objects with circular references with help from a cheater stack.

Deep Copying Literals with Circular References

The object to be copied is called a source and its deep copy is called the target. Each node source.X, where X is a dotted chain of attributes, is also called a source and its target is target.X, the corresponding node in the target tree. When the deep copy algorithm is complete, each target will be a deep copy of its source.

The code below produces the tree on the left. We want to do a deep copy. Notice that x and y refer to each other through their attributes a and b. In the left tree, the two circular references are shown. We want to make sure the deep copy contains the same circular references, and that once a circular reference is obtained copying should stop for the node in question.

unavailable

The following table depicts a stack algorithm in preorder transversal.

Stack
depthSourceTargetKeys in Preorder
1zcz = { }
2z.M = xcz.M = { }M
3z.M.a = ycz.M.a = { }a
4 z.M.a.b = z.M cz.M.a.b = cz.M b
4z.M.a.g = 2cz.M.a.g = 2g
3z.M.f = 1cz.M.f = 1f
Intermission. Popcorn is ready!
2z.N = ycz.N = { }N
3z.N.b = xcz.N.b = { }b
4 z.N.b.a = z.N cz.N.b.a = cz.N a
4z.N.b.f = 1cz.N.b.f = 1f
3z.N.g = 2cz.N.g = 2g

OK! The target is the deep copy of the source, but not originally. The target gets filled in as the algorithm progresses.

Original thoughts were that there's no way we are going to search through the stack in preorder transversal code to find circular references, so we are going to let the stack itself do the work. (1) The stack will keep a fast record, say a WeakSet of all sources on the stack and so infinite recursion is avoided since a source will not be pushed onto the stack if it already is on the stack.

(2) To check and close circular references the stack will maintain a WeakMap. Every time a source, and target are pushed onto the stack, the source will be weakly mapped to the target. Once we reach a particular source source.X that is already on the stack, we look up its target T in the WeakMap. The value of target.X in the target tree is set to T to close the circular reference and maintain consistency.

The WeakSet is redundant since the WeakMap is also a fast record of sources (in addition to their targets)

For example, when we see z.M.a.b = x is already a source on the stack, we lookup its target which is cx. We then know to set cz.M.a.b to that target cx to duplicate the circular reference.

Cheater Stack Customized for Deep Copying
Literals with Possible Circular References
function CheaterStack() { var wm = new WeakMap(); // record of sources and their targets var l = 0; // length of stack this.push = function(x) { this[l++] = x; // push onto stack wm.set(x.source, x.target); // record source and its target } this.pop = function() { var x = this[--l]; // pop the stack // record of source and target no longer needed //wm.delete(x.source); // The above line is commented out since we want to handle // duplicate references. If you know for sure there are // going to be no duplicate references, you can gain some // efficiency by uncommenting the above line. return x; } this.peek = function() { return this[l - 1]; } this.inSource = function(source) { // return true if source is on the stack return wm.has(source); } this.getTarget = function(source) // get target of source { return wm.get(source); } Object.defineProperty(this, 'length', { get:function(){return l;} }); }

You should now be able to make headway on the grand finale: The deep copy algorithm of literals that can deal with circular references.

Deep Copying Literals with Possible Circular References
function deepCopyLiteral(source) { var stack = new CheaterStack(); var target = {}; stack.push({source:source, target:target, keys:Object.getOwnPropertyNames(source), index:0}); while(stack.length > 0) { var T = stack.peek(); if(T.index < T.keys.length ) // process next key of source at current index { var key = T.keys[T.index]; // key at current index let source = T.source[key]; // source to copy // dont process if source already on stack if(!stack.inSource(source)) { if(isPrimitive(source)) { T.target[key] = source; // fill in target } else { T.target[key] = {}; // empty copy target of source stack.push({source:source, target:T.target[key] , keys:Object.getOwnPropertyNames(T.source[key]), index:0}); } // alert(stringify(target)); // Watch target filled in preorder. } else // source already on stack, so copy circular reference { // add circular reference to deep copy. T.target[key] = stack.getTarget(source); } T.index++; } else { stack.pop(); } } return target; } function isPrimitive(x) { return (x == null || typeof(x) != 'object') && typeof(x) != 'function'; }
Test deepCopyLiteral with Circular References
(uses type2.js and Stringification.js)
function TestDeepCopyLiteral() { var x = {}, y = {} x.a = y; y.b = x; x.f = 1; y.g = 2; var z = {M:x, N:y}; var cz = deepCopyLiteral(z); console.log(stringify(z) == stringify(cz)); // stringification will indicate circular references with the @ symbol. console.log(stringify(cz)); }

The reader can create more extensive examples.

Appendices

A Better Way to Deep Copying Literals

In addition to circular references, which cause infinite recursion unless you specifically code for that possibility, there may be duplicate references that themselves should really be taken care of. To do that in the CheaterStack pop code delete the line wm.delete(x.source);. You can even do better. In deepCopyLiteral code, start with [] as the stack, i.e., no cheater stack, then deepCopyLiteral will itself use a weak map to take care of circular references and duplicate references.

However, cheater stacks are still important and you got to see a simple example of one.