An oyster met an oyster and they were oysters two. Two oysters met two oysters and they were oysters too. Four oysters met Chef Boyardee, who thinking they appeared healthy and hearty, invited them to a party. The hot tub was just right, warm and not too salty. Too late they realized that Chef Boyardee was very very naughty.
Meouzer
This excerpt from Meouzer's critically acclaimed treatise, The Oyster Dimension, is available to the public under poetic license.
Full code is at deepCopy.js, which depends on ValueCopy.js, which depends on typing.js.
Listing 7 gives the deepCopy() function after its its predecessors, each of which covers one technical complexity.
If a deep copy algorithm is applied to x to produce y, then x is a source and y is its target. This terminology continues as follows. If p1.p2...pn. is a dotted chain of properties then x.p1.p2...pn is a source and y.p1.p2...pn is its target. Of course, during a deep copy algorithm the target of a source won't be completely filled in untill the algorithm completes.
We start with deep copying JSON Literal Objects, and add complexity in pieces to build up to general deep copying.
function deepCopy_JSON_Literal(source) { // Rather than use a recursive function, a stack is used. What would be // pushed onto the call stack in a recursive function is instead pushed onto // a data stack. if(isPrimitive(source)) return source; const target = isArray(source)? []:{} // the target starts off //as a value copy of the source. const stack = [{source:source, target:target}]; while(stack.length > 0) // while still processing sources in preorder { const top = stack.pop(); const source = top.source; // get source const target = top.target; // get currently unfilled target (the valueCopy) // process nodes of the object tree in preorder for(const p of Object.getOwnPropertyNames(source)) { if(isPrimitive(source[p])) { // fill in target property target[p] = source[p]; } else { // push source and its valueCopy onto stack target[p] = isArray(source[p])? []:{} stack.push({source:source[p], target:target[p]}); } } } return target; }Complexities not accounted for
To go beyond JSON object literals and deep copy most anything, simply modify lines 3 and 13 of code listing 1 by setting the target to a value copy of the source. WeakSets and WeakMaps are copy primitives, which explains lines 4 and 15.
function deepCopy_1(source) { if(isPrimitive(source)) return source; // targets start off as value copies of sources const target = valueCopy(source); // if target is source then source is a copy primitive (a WeakSet or WeakMap) if(target === source) return source; const stack = [{source:source, target:target}]; while(stack.length > 0) { const top = stack.pop(); const source = top.source; // get source const target = top.target; // get its unfilled value copy // process nodes of the object tree in preorder for(const p of Object.getOwnPropertyNames(source)) { if(isPrimitive(source[p])) { // fill in target primitive property target[p] = source[p]; } else { // push source and its valueCopy onto stack target[p] = valueCopy(source[p]); if(target[p] !== source[p]) // but disallow copy primitives { stack.push({source:source[p], target:target[p]}); } } } } return target; }Complexities Remaining
To handle circular and duplicate references, a weak map is used to record sources and their targets. If a source is copied to a target and if the source is found again, then it is copied to the same target on line 16.
function deepCopy_2(source) { if(isPrimitive(source)) return source; const target = valueCopy(source); if(target === source) return source; const wm = new WeakMap(); wm.set(source, target); const stack = [{source:source, target:target}]; while(stack.length > 0) { const top = stack.pop(); const source = top.source; const target = top.target; // process nodes of the object tree in preorder for(const p of Object.getOwnPropertyNames(source)) { if(isPrimitive(source[p])) { target[p] = source[p]; } else if(wm.has(source[p])) { target[p] = wm.get(source[p]); } else { target[p] = valueCopy(source[p]); if(target[p] !== source[p]) { stack.push({source:source[p], target:target[p]}); wm.set(source[p], target[p]); } } } } return target; }Complexities Remaining
Post order processing of a node occurs after it and all its descendents have been processed in preorder. The technique for doing so involves pushing null markers onto the stack. The first time a node is visited on the stack, it's in preorder. Then a null marker is pushed onto the stack. The second time the node is visited on the stack, the null marker indicates it's in post order.
function deepCopy_3(source) { if(isPrimitive(source)) return source; const target = valueCopy(source); if(target === source) return source; const wm = new WeakMap(); wm.set(source, target); const stack = [{source:source, target:target}]; while(stack.length > 0) { const top = stack.pop(); if(top === null) { // Post order processing. // Freezing, sealing, and preventing extensions // can only be done post order. const top1 = stack.pop(); if(Object.isFrozen(top1.source)) { Object.freeze(top1.target) } else if (Object.isSealed(top1.source)) { Object.seal(top1.target); } else if(!Object.isExtensible(top1.source)) { Object.preventExtensions(top1.target); } continue; } else { stack.push(top); stack.push(null); } const source = top.source; const target = top.target; // process nodes of the object tree in preorder for(const p of Object.getOwnPropertyNames(source)) { if(isPrimitive(source[p])) { target[p] = source[p]; } else if(wm.has(source[p])) { target[p] = wm.get(source[p]); } else { target[p] = valueCopy(source[p]); if(target[p] !== source[p]) { stack.push({source:source[p], target:target[p]}); wm.set(source[p], target[p]); } } } } return target; }Complexities Remaining
To make sure that nodes which are functions are copied, simply add an evaluator parameter to the deep copy function on line 1, and also to the calls to valueCopy() on lines 3 and 30. Then functions are copied into the evaluator's context. If no evaluator is specified, the global evaluator is used as the default, which works well if the function nodes don't depend on an outer context.
function deepCopy_4(source, evaluator) { if(isPrimitive(source)) return source; const target = valueCopy(source, evaluator); if(target === source) return source; const wm = new WeakMap(); wm.set(source, target); const stack = [{source:source, target:target}]; while(stack.length > 0) { const top = stack.pop(); if(top === null) { // Post order processing. // Freezing, sealing, and preventing extensions // can only be done post order. const top1 = stack.pop(); if(Object.isFrozen(top1.source)) { Object.freeze(top1.target) } else if (Object.isSealed(top1.source)) { Object.seal(top1.target); } else if(!Object.isExtensible(top1.source)) { Object.preventExtensions(top1.target); } continue; } else { stack.push(top); stack.push(null); } const source = top.source; const target = top.target; // process nodes of the object tree in preorder for(const p of Object.getOwnPropertyNames(source)) { const pd = Object.getOwnPropertyDescriptor(source, p); if(isPrimitive(source[p])) { Object.defineProperty(target, pd); } else if(wm.has(source[p])) { pd.value = wm.get(source[p]); Object.defineProperty(target, pd); } else { pd.value = valueCopy(source[p], evaluator); Object.defineProperty(target, pd); if(target[p] !== source[p]) { stack.push({source:source[p], target:target[p]}); wm.set(source[p], target[p]); } } } } return target; }
Complexities Remaining
Gets and Sets can only be copied with property descriptors. As functions they must also be evaluated with an evaluator: They must be copied into the evaluators context. See lines 26-30.
function deepCopy_5(source, evaluator) { if(isPrimitive(source)) return source; const target = valueCopy(source, evaluator); if(target === source) return source; const wm = new WeakMap(); wm.set(source, target); const stack = [{source:source, target:target}]; while(stack.length > 0) { const top = stack.pop(); if(top === null) { // Post order processing. // Freezing, sealing, and preventing extensions // can only be done post order. const top1 = stack.pop(); if(Object.isFrozen(top1.source)) { Object.freeze(top1.target) } else if (Object.isSealed(top1.source)) { Object.seal(top1.target); } else if(!Object.isExtensible(top1.source)) { Object.preventExtensions(top1.target); } continue; } else { stack.push(top); stack.push(null); } const source = top.source; const target = top.target; // process nodes of the object tree in preorder for(const p of Object.getOwnPropertyNames(source)) { const pd = Object.getOwnPropertyDescriptor(source, p); if(pd.get || pd.set) { if(!hasOwnProperty(target, p) ) { if(pd.get) pd.get = evaluateGetterSetter(pd.get, evaluator); if(pd.set) pd.set = evaluateGetterSetter(pd.set, evaluator); Object.defineProperty(target, p, pd); } } else if(isPrimitive(source[p])) { Object.defineProperty(target, p, pd); } else if(wm.has(source[p])) { pd.value = wm.get(source[p]); Object.defineProperty(target, p, pd); } else { pd.value = valueCopy(source[p], evaluator); Object.defineProperty(target, p, pd); if(target[p] !== source[p]) { stack.push({source:source[p], target:target[p]}); wm.set(source[p], target[p]); } } } } return target; } \numbersRestartA literal get is not defined with a property descriptor and looks like get(){...}. The programmer can't use that form at all. We need to make it look like function(){...} so we can use it as the get in a property descriptor. Similarly for literal sets. Line 7 makes sure the get/set is evaluated into the evaluator's context.
if(!isNativeCode(func)) { // change any "get" or "set" to "function" and // copy it into the evaluators context on line 7 evaluator = evaluator || globalEvaluator; let s = func.toString(); if(s[0] == 'g' || s[0] == 's') { s = "function" + s.substring(3); } return evaluator(s); } else { // can't evaluate native code. return func; } }Complexities Remaining
function getTarget(obj, evaluator) { // Set and Map targets should initially be completely empty. // So calling getTarget(obj, evaluator) below is a substitute // for calling valueCopy(obj, evaluator) in previous listings if(isSet(obj)) return new Set(); if(isMap(obj)) return new Map(); return valueCopy(obj, evaluator); } function deepCopy(source, evaluator) { if(isPrimitive(source)) return source; const target = getTarget(source, evaluator); if(target === source) return source; const wm = new WeakMap(); wm.set(source, target); const stack = [{source:source, target:target}]; while(stack.length > 0) { const top = stack.pop(); if(top === null) { // Post order processing. // Freezing, sealing, and preventing extensions // can only be done post order. const top1 = stack.pop(); if(Object.isFrozen(top1.source)) { Object.freeze(top1.target) } else if (Object.isSealed(top1.source)) { Object.seal(top1.target); } else if(!Object.isExtensible(top1.source)) { Object.preventExtensions(top1.target); } continue; } else { stack.push(top); stack.push(null); } const source = top.source; const target = top.target; // process nodes of the object tree in preorder for(const p of Object.getOwnPropertyNames(source)) { const pd = Object.getOwnPropertyDescriptor(source, p); if(pd.get || pd.set) { if(!hasOwnProperty(target, p) ) { if(pd.get) pd.get = evaluateGetterSetter(pd.get, evaluator); if(pd.set) pd.set = evaluateGetterSetter(pd.set, evaluator); Object.defineProperty(target, p, pd); } } else if(isPrimitive(source[p])) { Object.defineProperty(target, p, pd); } else if(wm.has(source[p])) { pd.value = wm.get(source[p]); Object.defineProperty(target, p, pd); } else { pd.value = getTarget(source[p], evaluator); Object.defineProperty(target, p, pd); if(target[p] !== source[p]) { // if source[p] not a copy primitive push onto stack stack.push({source:source[p], target:target[p]}); wm.set(source[p], target[p]); } } } if(isSet(source)) { for(const value of source.values()) // loop through members of Set { // value is a member of the set and is also a source if(wm.has(value)) { // value as a source already has a target, // which is wm.get(value) // add the target of value to the target Set target.add(wm.get(value)); } else { const targetValue = getTarget(value); target.add(targetValue); if(value !== targetValue) { stack.push({source:value, target:targetValue}); wm.set(value, targetValue); } } } } else if(isMap(source)) { for(const key of source.keys()) { const value = source.get(key); // key and value are sources let targetKey; // target of key let targetValue; // target of value if(wm.has(key)) { // key as a source already has a target, // which is wm.get(key) targetKey = wm.get(key); } else { targetKey = getTarget(key); if(key !== targetKey) { stack.push({source:key, target:targetKey}); wm.set(key, targetKey); } } if(wm.has(value)) { // value as a source already has a target, // which is wm.get(value) targetValue = wm.get(value); } else { targetValue = getTarget(value); if(value!== targetValue) { stack.push({source:value, target:targetValue}); wm.set(value, targetValue); } } // In the target Map, set the key and value. target.set(targetKey, targetValue); } } } return target; }