JS native method principle exploration (nine) how to achieve shallow copy and deep copy?

This is the ninth article in a series exploring the principles of JavaScript native methods. This article shows you how to implement shallow copy and deep copy by hand.

Implementing a shallow copy

What is a shallow copy?

A shallow copy of the original object generates a new object that is “just like” it. However, this copy only copies the base type properties of the first level of the original object, and the reference type properties are still shared with the original object.

Take a simple example to understand:

let obj1 = {
    a: 'Jack',
    b: {
        c: 1
    }
}
let obj2 = Object.assign({},obj1)
obj1.a = 'Tom'
obj1.b.c = 2
console.log(obj1.a)      // 'Tom'
console.log(obj2.a)      // 'Jack'   
console.log(obj1.b.c)    // 2
console.log(obj2.b.c)    // 2

As you can see, because the new object copies the primitive type property of the first level of the original object, changing the value of obj1.a does not affect the value of obj2.a; Also, because the new object and the original object share the same first-level reference type property, modifying the obj1.b object will affect the obj2.b object as well.

How do I implement shallow copy?

Common shallow copy methods in JS are object.assign (),… The expansion operator and the array’s slice method. But what if we want to implement a shallow copy ourselves?

Because the shallow copy only works at the first level, you simply traverse the original object and add each of its members to the new object. By primitive objects, we mean object literals, arrays, array-like objects, sets, and maps that can be traversed. For other non-traversable objects and values of primitive types, return them directly.

The code is as follows:

Function getType (obj) {return Object. The prototype. ToSrting. Call (obj). Slice (8, 1)} / / can traverse the data type of the let iterableList = ['Object','Array','Arguments','Set','Map'] function shallowCopy(obj){let type = getType(obj) if(! IterableList.Includes (type)) return obj let res = new obj.constructor() type === 'Set' ? res.add(value) : ForEach (key => {res[key] = obj[key]}) return res}

Some key points:

• Initialize the new objectres: Gets the original objectobjCreates an instance of the same type as the original object
• There are three ways to traverse through an object or an array. The first way is to useReflect.ownKeys()Gets all properties of itself (whether enumerable or not), the second is to useThe for... in + hasOwnProperty()Gets all enumerable properties of itself. The third is to useObject.keys()Gets all of its own enumerable properties at once

Implement deep copy of objects

What is Deep Copy?

A deep copy of the original object generates a new object that is “just like” it. Deep copy copies the primitive type attributes and reference type attributes at all levels of the original object. Let me give you an example:

let obj1 = {
    a: 'Jack',
    b: {
        c: 1
    }
}
let obj2 = JSON.parse(JSON.stringify(obj1))
obj1.a = 'Tom'
obj1.b.c = 2
console.log(obj1.a)      // 'Tom'
console.log(obj2.a)      // 'Jack'   
console.log(obj1.b.c)    // 2
console.log(obj2.b.c)    // 1

As you can see, whatever changes you make to obj1 will not affect obj2, and vice versa, and the two are completely independent.

How do I implement deep copy?

A common way to implement deep copy is json.parse (json.stringify ()). It can handle normal deep copy scenarios, but there are a number of problems, most of which occur in the serialization process.

1. Attributes of type Date are deep copied to strings:

   Let obj = {date: new date ()} json.parse (json.stringify (obj)) // {date: "2021-07-04T13:01:35.934z "}

2. Properties of regular and error types are deep copied to become empty objects:

   let obj = {
       reg : /\d+/gi,
       error : new Error()
   }
   JSON.parse(JSON.stringify(obj))       // {reg:{},error:{}}

3. If the key’s value is of function type, undefined type, and Symbol type, it will be lost after deep copy:

   Let obj = {fn: function(){}, name: undefined, sym: Symbol(), age: Parse (json.stringify (obj)) // {age:12} Let arr = [function(){}, undefined, Symbol(), 12 ] JSON.parse(JSON.stringify(arr)) // ["null","null","null"12]

4. If the key is of type Symbol, it will be lost after a deep copy:

   let obj = {a:1}
   obj[Symbol()] = 2
   JSON.parse(JSON.stringify(obj))      // {a:1}

5. NaN, Infinity, -infinity are null after deep copy

   let obj = {
       a:NaN,
       b:Infinity,
       c:-Infinity
   }
   JSON.parse(JSON.stringify(obj))     // {a:null,b:null,c:null}

6. May cause constructor pointing to miss:

   function Super(){}
   let obj1 = new Super()
   let obj2 = JSON.parse(JSON.stringify(obj1))
   
   console.log(obj1.constructor)       // Super
   console.log(obj2.constructor)       // Object   

JSON.stringify() can only serialize enumerable properties of the object itself. This constructor is not a property of the instance itself, but of the instance’s prototype object. Therefore, when serializing the instance Object obj1, we do not actually handle the constructor’s point, so that the constructor’s point becomes the default Object.

7. There is a circular reference problem

   let obj = {}
   obj.a = obj
   JSON.parse(JSON.stringify(obj1))

The obj object above has a circular reference, that is, it is a circular structure (not a tree), such an object cannot be converted to JSON, so the error is issued: Can’t convert circular structure to JSON.

Alternatively, we might consider using the deep copy method provided by Lodash. But what if you want to implement a deep copy yourself? Let’s take it step by step.

Basic version

The core of deep copy is == shallow copy + recursion ==. No matter how deep the nesting level is, we can always recurse to the innermost level of the object to copy the attributes of the basic type and the attributes of the reference type that cannot be traversed.

Here is the most basic deep copy version:

function deepClone(target){
    if(typeof target === 'object'){
        let cloneTarget = Array.isArray(target) ? []:{}
        Reflect.ownKeys(target).forEach(key => {
            cloneTarget[key] = deepClone(target[key])
        })
        return cloneTarget
    } else {
        return target
    }
}

We’re only considering arrays and object literals here. Depending on whether the initial target is an object literal or an array, the final cloneTarget returned is an object or an array. It then iterates through each of the target’s own attributes, recursively calling deepClone and returning directly if the attribute is already a primitive type. If it is an object or an array, it is treated the same way as the original target. Finally, the processed results are added to cloneTarget one by one.

Resolve the issue of stack bursting caused by circular references

However, there is a circular reference problem.

Suppose the target of a deep copy is something like this:

let obj = {}
obj.a = obj

For such an object, there is a loop in the structure, i.e. a circular reference: obj refers to itself through property a, and A must also have a property a that refers to itself again… So it’s going to end up with obj nested indefinitely. In deep copy, because recursion is used, infinitely nested objects will result in infinitely recursion, which will eventually lead to stack overflows.

How do you solve the stack explosion problem caused by circular references? It’s as simple as creating an exit for the recursion. For the object or array that is passed in for the first time, a WeakMap will be used to record the mapping relationship between the current target and the copied results. When the same target is passed in again, repeated copying will not be carried out, but the corresponding copy results will be taken out directly from the WeakMap and returned.

The “return” in this case creates an exit for recursion, so it doesn’t recurse indefinitely, so it doesn’t break the stack.

So the improved code is as follows:

function deepClone(target,map = new WeakMap()){ if(typeof target === 'object'){ let cloneTarget = Array.isArray(target) ? If (map.has(target)) return map.get(target) map.set(target,cloneTarget) Reflect.ownKeys(target).forEach(key => { cloneTarget[key] = deepClone(target[key],map) }) return cloneTarget } else { return target } }

Handle other data types

Always remember that we are dealing with three types of goals:

• Basic data type: return directly
• Reference data types you can continue traversing: In addition to the object literals and arrays you’ve already dealt with, there are class array objects, sets, and maps. They all belong to potentially nested reference types that can be iterated over, so recursion is required when processing them
• Reference data types that cannot continue traversal: These include functions, error objects, date objects, regular objects, wrapper objects of primitive types (String, Boolean, Symbol, Number), and so on. They are not traversable, or “non-nested”, so a copy of the same will be returned for reprocessing

1) Type determination function

To better determine whether to refer to a datatype or a primitive datatype, we can use an isObject function:

function isObject(o){ return o ! == null && (typeof o === 'object' || typeof o === 'function') }

To determine exactly what the data type is, we can use a getType function:

function getType(o){
    return Object.prototype.toString.call(o).slice(8,-1)
}
// getType(1)      "Number"
// getType(null)   "Null"

2) Initialize the function

When we deep copy object literals or arrays, we first initialize the final result cloneTarget to either [] or {}. Similarly, you need to do the same for sets, maps, and array-like objects, so it’s best to use a single function to initialize cloneTarget.

function initCloneTarget(target){
    return new target.constructor()
}

Target. Constructor gets the constructor of the incoming instance and uses that constructor to create a new instance of the same type and returns.

3) Handle reference types that can continue to traverse: class array objects, Set, Map

Array-like objects are actually the same form as arrays and object literals, so you can work with them together; The process for dealing with sets and maps is basically the same, but instead of assigning values directly, you have to use add or Set methods, so it’s a little bit better.

The code is as follows:

Function deepClone(target,map = new WeakMap()){ Let type = getType(target) let cloneTarget = initClonetarget (target) // If (map.has(target)) return map.get(target) map.set(target,cloneTarget) return map.get(target) map.set(target,cloneTarget); Target.foreach (value = bb0 {DeepClone (value,map))})} Target.foreach ((value,key) => {clonetarget. set(key,deepClone(value,map))})} else if(type === = 'Object' || type === 'Array' || type === 'Arguments'){ Reflect.ownKeys(target).forEach(key => { cloneTarget[key] = deepClone(target[key],map) }) } return cloneTarget }

4) Handle reference types that cannot continue to traverse

Now deal with reference types that cannot continue to be traversed. For such targets, we cannot return them directly as we would for primitive data types, because they are also objects in nature, and returning them directly will return the same reference, without the purpose of copying. The correct approach, should be a copy of a copy of the return.

How do you copy it? There are two cases. String, Boolean, Number, error, and date can all return a copy of an instance by new; Copies of Symbol, functions, and regular objects cannot pass through a simple new copy and need to be handled separately.

Copies of the Symbol

The function cloneSymbol (target) {return Object (target. The valueOf ()) / / or return the Object (Symbol. The prototype. The valueOf. Call (target)) // return Object(Symbol(target.description))}

PS: Target is the wrapper type of the basic type of Symbol. Call ValueOf to get its corresponding unboxing result. Then pass this unboxing result to Object to construct a copy of the original wrapper type. To be on the safe side, we can call valueOf through Symbol’s prototype; You can obtain the Symbol’s descriptor from.description, based on which you can also construct a copy of the original wrapper type.

Copy regular objects (see Lodash’s example)

function cloneReg(target) {
    const reFlags = /\w*$/;
    const result = new RegExp(target.source, reFlags.exec(target));
    result.lastIndex = target.lastIndex;
    return result;
}

Copy the function (there is no need to copy the function)

Function clonefwseofunction (target){return eval(' (${target}) ') // or return new function (' return (${target})() ')}

PS: The arguments passed to new Function declare the body of the newly created Function instance

Next, use a DirectCloneTarget function to handle all of the above cases:

function directCloneTarget(target,type){ let _constructor = target.constructor switch(type): case 'String': case 'Boolean': case 'Number': case 'Error': case 'Date': Return new _constructor (target. The valueOf ()) / / or return the new Object (_constructor. Prototype. The valueOf. Call (target) case 'RegExp': return cloneReg(target) case 'Symbol': return cloneSymbol(target) case 'Function': return cloneFunction(target) default: return null }

PS: Notice that there are some pits here.

• Why Use Itreturn new _constructor(target.valueOf())Rather thanreturn new _constructor(target)? Because if it comes intarget 是 new Boolean(false), so the final return is actuallynew Boolean(new Boolean(false))Since the parameter is not an empty object, its value does not correspond to the expected false, but to true. So, it’s best to usevalueOfGets the real value corresponding to the wrapper type.
• It is also possible not to use a constructor corresponding to the base type_constructor, but directlynew Object(target.valueOf())Wrap the base type
• To allow for the possibility that valueOf could be overridden, it is safe to use the constructor corresponding to the base type_constructorTo call the valueOf method

The final version

The final code looks like this:

let objectToInit = ['Object','Array','Set','Map','Arguments'] function deepClone(target,map = new WeakMap()){ if(! IsObject (target)) return target // let type = getType(target) let cloneTarget if(ObjectToInit.Includes (type)){ } else {return directClonetarget (target,type)} if(map.has(target)) Return map.get(target) map.set(target,cloneTarget) // copy set if(type === 'set '){target.foreach (value =>){return map.get(target) map.set(target,cloneTarget); Clonetarget. add(DeepClone (value,map))})} else if(type === 'map '){target.foreach ((value,key) => { CloneTarget. Set (key, deepClone (value, map))})} / / copy the Object literal, Array, Array Object else if (type = = = 'Object' | | type = = = 'Array' | | type  === 'Arguments'){ Reflect.ownKeys(target).forEach(key => { cloneTarget[key] = deepClone(target[key],map) }) } return cloneTarget }