How to implement a deep copy

Update: Thank you for your support. Recently, I have made a blog official website come out to facilitate your systematic reading. There will be more content and more optimization in the follow-up

—— The following is the text ——

The introduction

The previous article introduced the shallow copy of Object.assign in detail and simulated its implementation. During the implementation process, a lot of basic knowledge was introduced. In today’s article we look at a must-see question, how to implement a deep copy. This article describes deep copy practices in detail for objects, arrays, circular references, lost references, Symbol, and recursive stack bursting.

Step 1: Simple implementation

In fact, deep copy can be split into two steps, shallow copy + recursion, shallow copy to determine whether the attribute value is an object, if it is an object, recursive operation, a combination of the two to achieve a deep copy.

Based on the previous article, we can write the following simple shallow copy code.

/ / wooden Yi Yang
function cloneShallow(source) {
    var target = {};
    for (var key in source) {
        if (Object.prototype.hasOwnProperty.call(source, key)) { target[key] = source[key]; }}return target;
}

// Test case
var a = {
    name: "muyiy".book: {
        title: "You Don't Know JS".price: "45"
    },
    a1: undefined.a2: null.a3: 123
}
var b = cloneShallow(a);

a.name = "Advanced front-end advanced";
a.book.price = "55";

console.log(b);
/ / {
// name: 'muyiy',
// book: { title: 'You Don\'t Know JS', price: '55' },
// a1: undefined,
// a2: null,
// a3: 123
// }
Copy the code

The above code is a shallow copy implementation, which can be implemented with a small change, a determination of whether it is an object or not, and a recursion where appropriate.

/ / wooden Yi Yang
function cloneDeep1(source) {
    var target = {};
    for(var key in source) {
        if (Object.prototype.hasOwnProperty.call(source, key)) {
            if (typeof source[key] === 'object') {
                target[key] = cloneDeep1(source[key]); // Notice here
            } else{ target[key] = source[key]; }}}return target;
}

// Use the above test cases
var b = cloneDeep1(a);
console.log(b);
/ / {
// name: 'muyiy',
// book: { title: 'You Don\'t Know JS', price: '45' },
// a1: undefined,
// a2: {},
// a3: 123
// }
Copy the code

A simple deep copy is done, but there are many problems with this implementation.

1. Null should be returned instead of {}
Typeof null === ‘object’; typeof null === ‘object’;
3. No consideration for array compatibility

Step 2: Copy the array

Let’s take a look at the judgment of the object, which was introduced in [Advanced 3-3] before. The judgment scheme is as follows.

/ / wooden Yi Yang
function isObject(obj) {
    return Object.prototype.toString.call(obj) === '[object Object]';
}
Copy the code

But it’s not appropriate here, because we want to keep the array case, so we use Typeof.

/ / wooden Yi Yang
typeof null //"object"
typeof {} //"object"
typeof [] //"object"
typeof function foo(){} //"function" (special case)
Copy the code

After the change, the isObject judgment logic is as follows.

/ / wooden Yi Yang
function isObject(obj) {
	return typeof obj === 'object'&& obj ! =null;
}
Copy the code

So the compatible array is written as follows.

/ / wooden Yi Yang
function cloneDeep2(source) {

    if(! isObject(source))return source; // Non-objects return themselves
      
    var target = Array.isArray(source) ? [] : {};
    for(var key in source) {
        if (Object.prototype.hasOwnProperty.call(source, key)) {
            if (isObject(source[key])) {
                target[key] = cloneDeep2(source[key]); // Notice here
            } else{ target[key] = source[key]; }}}return target;
}

// Use the above test cases
var b = cloneDeep2(a);
console.log(b);
/ / {
// name: 'muyiy',
// book: { title: 'You Don\'t Know JS', price: '45' },
// a1: undefined,
// a2: null,
// a3: 123
// }
Copy the code

Step 3: Circular references

We know that JSON cannot deep copy circular references, and that an exception will be thrown if it does.

/ / wooden Yi Yang
// Here a is the test case at the beginning of this article
a.circleRef = a;

JSON.parse(JSON.stringify(a));
// TypeError: Converting circular structure to JSON
Copy the code

1. Use hash tables

The solution is simply loop detection. We set an array or hash table to store the copied objects. When we detect that the current object already exists in the hash table, we fetch the value and return it.

/ / wooden Yi Yang
function cloneDeep3(source, hash = new WeakMap()) {

    if(! isObject(source))return source; 
    if (hash.has(source)) return hash.get(source); // Add code to check the hash table
      
    var target = Array.isArray(source) ? [] : {};
    hash.set(source, target); // Add code, hash table set value
    
    for(var key in source) {
        if (Object.prototype.hasOwnProperty.call(source, key)) {
            if (isObject(source[key])) {
                target[key] = cloneDeep3(source[key], hash); // Add the code and pass in the hash table
            } else{ target[key] = source[key]; }}}return target;
}
Copy the code

Test it out and see how it works.

/ / wooden Yi Yang
// Here a is the test case at the beginning of this article
a.circleRef = a;

var b = cloneDeep3(a);
console.log(b);
/ / {
// name: "muyiy",
// a1: undefined,
//	a2: null,
// a3: 123,
// book: {title: "You Don't Know JS", price: "45"},
// circleRef: {name: "muyiy", book: {... }, a1: undefined, a2: null, a3: 123,... }
// }
Copy the code

Perfect!

2. Use arrays

Here uses ES6 WeakMap to deal with, that should be handled in ES5?

It’s very simple, just use an array, so here’s the code.

/ / wooden Yi Yang
function cloneDeep3(source, uniqueList) {

    if(! isObject(source))return source; 
    if(! uniqueList) uniqueList = [];// Add code to initialize the array
      
    var target = Array.isArray(source) ? [] : {};
    
    // ============= add code
    // The data already exists, return the saved data
    var uniqueData = find(uniqueList, source);
    if (uniqueData) {
        return uniqueData.target;
    };
        
    // The data does not exist, save the source data, and the corresponding reference
    uniqueList.push({
        source: source,
        target: target
    });
    / / = = = = = = = = = = = = =

    for(var key in source) {
        if (Object.prototype.hasOwnProperty.call(source, key)) {
            if (isObject(source[key])) {
                target[key] = cloneDeep3(source[key], uniqueList); // Add the code and pass in the array
            } else{ target[key] = source[key]; }}}return target;
}

// Add a new method for finding
function find(arr, item) {
    for(var i = 0; i < arr.length; i++) {
        if (arr[i].source === item) {
            returnarr[i]; }}return null;
}

// The above test case has passed
Copy the code

Now that we’ve solved the circular reference situation perfectly, which is actually a situation where the reference is missing, let’s look at the following example.

/ / wooden Yi Yang
var obj1 = {};
var obj2 = {a: obj1, b: obj1};

obj2.a === obj2.b; 
// true

var obj3 = cloneDeep2(obj2);
obj3.a === obj3.b; 
// false
Copy the code

Missing references can be problematic in some cases, such as obj2 above, where the keys a and b of obj2 both refer to the same object, obj1. After a deep copy with cloneDeep2, the reference relationship is lost and the two objects become different.

In fact, if you notice, our cloneDeep3 solves this problem because we only need to store the copied objects.

/ / wooden Yi Yang
var obj3 = cloneDeep3(obj2);
obj3.a === obj3.b; 
// true
Copy the code

Perfect!

Step 4: Copy`Symbol`

This is where things are going to get messy, so can we copy the Symol type?

Sure, but Symbol is available under ES6. We need some way to detect the Symble type.

Method one: Object. GetOwnPropertySymbols (…).

Reflect.ownkeys (…)

So method one can look for a symbolic property of a given object and return one, right? An array of type symbol. Note that each initialized object does not have its own symbol property, so the array may be empty unless you have set a symbol property on the object. (From MDN)

var obj = {};
var a = Symbol("a"); // Create a new symbol type
var b = Symbol.for("b"); // Register from the global symbol. Table setting and getting symbol

obj[a] = "localSymbol";
obj[b] = "globalSymbol";

var objectSymbols = Object.getOwnPropertySymbols(obj);

console.log(objectSymbols.length); / / 2
console.log(objectSymbols)         // [Symbol(a), Symbol(b)]
console.log(objectSymbols[0])      // Symbol(a)
Copy the code

For method 2, return an array of the target object’s own property keys. The return value is equal to the Object. GetOwnPropertyNames (target). The concat (Object. GetOwnPropertySymbols (target). (MDN)

Reflect.ownKeys({z: 3.y: 2.x: 1}); // [ "z", "y", "x" ]
Reflect.ownKeys([]); // ["length"]

var sym = Symbol.for("comet");
var sym2 = Symbol.for("meteor");
var obj = {[sym]: 0."str": 0."773": 0."0": 0,
           [sym2]: 0."1": 0."8": 0."second str": 0};
Reflect.ownKeys(obj);
// [ "0", "8", "773", "str", "-1", "second str", Symbol(comet), Symbol(meteor) ]
// Pay attention to the order
// Indexes in numeric order, 
// strings in insertion order, 
// symbols in insertion order
Copy the code

Methods a

The idea is to look for a Symbol attribute, and if so, iterate through the Symbol case first, and then handle the normal case. The extra logic is the new code below.

/ / wooden Yi Yang
function cloneDeep4(source, hash = new WeakMap()) {

    if(! isObject(source))return source; 
    if (hash.has(source)) return hash.get(source); 
      
    let target = Array.isArray(source) ? [] : {};
    hash.set(source, target);
    
    // ============= add code
    let symKeys = Object.getOwnPropertySymbols(source); / / to find
    if (symKeys.length) { // The search succeeded
        symKeys.forEach(symKey= > {
            if (isObject(source[symKey])) {
                target[symKey] = cloneDeep4(source[symKey], hash); 
            } else{ target[symKey] = source[symKey]; }}); }/ / = = = = = = = = = = = = =
    
    for(let key in source) {
        if (Object.prototype.hasOwnProperty.call(source, key)) {
            if (isObject(source[key])) {
                target[key] = cloneDeep4(source[key], hash); 
            } else{ target[key] = source[key]; }}}return target;
}
Copy the code

To test the effect.

/ / wooden Yi Yang
// Here a is the test case at the beginning of this article
var sym1 = Symbol("a"); // Create a new symbol type
var sym2 = Symbol.for("b"); // Register from the global symbol. Table setting and getting symbol

a[sym1] = "localSymbol";
a[sym2] = "globalSymbol";

var b = cloneDeep4(a);
console.log(b);
/ / {
// name: "muyiy",
// a1: undefined,
//	a2: null,
// a3: 123,
// book: {title: "You Don't Know JS", price: "45"},
// circleRef: {name: "muyiy", book: {... }, a1: undefined, a2: null, a3: 123,... },
// [Symbol(a)]: 'localSymbol',
// [Symbol(b)]: 'globalSymbol'
// }
Copy the code

Perfect!

Method 2

/ / wooden Yi Yang
function cloneDeep4(source, hash = new WeakMap()) {

    if(! isObject(source))return source; 
    if (hash.has(source)) return hash.get(source); 
      
    let target = Array.isArray(source) ? [] : {};
    hash.set(source, target);
    
  	Reflect.ownKeys(source).forEach(key= > { / / change
        if (isObject(source[key])) {
            target[key] = cloneDeep4(source[key], hash); 
        } else{ target[key] = source[key]; }});return target;
}

// Test passed
Copy the code

We use reflect.ownkeys () to get all the key values, including Symbol, and assign to the source traversal.

I’m almost done here, so let’s go ahead and write target a different way, and I’ll change it to the following.

/ / wooden Yi Yang
function cloneDeep4(source, hash = new WeakMap()) {

    if(! isObject(source))return source; 
    if (hash.has(source)) return hash.get(source); 
      
    let target = Array.isArray(source) ? [...source] : { ... source };/ / 1
    hash.set(source, target);
    
  	Reflect.ownKeys(target).forEach(key= > { / / 2
        if (isObject(source[key])) {
            target[key] = cloneDeep4(source[key], hash); 
        } else{ target[key] = source[key]; }});return target;
}

// Test passed
Copy the code

In change 1, return a new array or object, and once you get the source object, pass in the target traversal assignment as shown in change 2.

The problem with reflect.ownkeys () is that it doesn’t deep copy the data on the prototype chain because it returns an array of the target object’s own property keys. If you want to deep copy the data on the prototype chain, use for.. In will do.

Let’s look at the use of expansion syntax when constructing arrays of literals and when constructing objects of literals. (The following code examples are from MDN)

1. Expand the syntax literal array

This is an ES2015 (ES6) syntax that allows you to construct new arrays in a literal way, instead of combining push, splice, concat, etc.

var parts = ['shoulders'.'knees']; 
var lyrics = ['head'. parts,'and'.'toes']; 
// ["head", "shoulders", "knees", "and", "toes"]
Copy the code

This is used in a similar way to the argument list expansion.

function myFunction(v, w, x, y, z) {}var args = [0.1];
myFunction(- 1. args,2. [3]);
Copy the code

The new array is returned, and changes to the new array do not affect the old array, similar to arr.slice().

var arr = [1.2.3];
var arr2 = [...arr]; // like arr.slice()
arr2.push(4); 

// arR2 = [1, 2, 3, 4]
// ArR is not affected
Copy the code

The expansion syntax behaves the same as object.assign (), executing a shallow copy (that is, traversing only one layer).

var a = [[1], [2], [3]].var b = [...a];
b.shift().shift(); / / 1
/ / [[], [2], [3]]
Copy the code

Here a is a multilayer array, b only copies the first layer, and for the second layer it still holds the same address as A, so any change to B will affect A.

2. Expand the syntax literal object

This is an ES2018 syntax that copies all enumerable properties of an existing Object into a newly constructed Object, similar to the object.assign () method.

var obj1 = { foo: 'bar'.x: 42 };
var obj2 = { foo: 'baz'.y: 13 };

varclonedObj = { ... obj1 };// { foo: "bar", x: 42 }

varmergedObj = { ... obj1, ... obj2 };// { foo: "baz", x: 42, y: 13 }
Copy the code

The object.assign () function fires setters; the expansion syntax does not. Sometimes you can’t replace or emulate the object.assign () function because you get unexpected results, as shown below.

var obj1 = { foo: 'bar'.x: 42 };
var obj2 = { foo: 'baz'.y: 13 };
const merge = (. objects) = >({... objects } );var mergedObj = merge ( obj1, obj2);
// { 0: { foo: 'bar', x: 42 }, 1: { foo: 'baz', y: 13 } }

var mergedObj = merge ( {}, obj1, obj2);
// { 0: {}, 1: { foo: 'bar', x: 42 }, 2: { foo: 'baz', y: 13 } }
Copy the code

What you’re actually doing here is deconstructing multiple parameters into rest and then expanding the remaining parameters into literal objects.

Step 5: Crack the recursion stack

The above four steps use recursive methods, but there is a problem with the stack bursting. The error message is as follows.

// RangeError: Maximum call stack size exceeded
Copy the code

So how do you solve it? In fact, we can use the loop, the code is as follows.

function cloneDeep5(x) {
    const root = {};

    / / stack
    const loopList = [
        {
            parent: root,
            key: undefined.data: x,
        }
    ];

    while(loopList.length) {
        // Breadth first
        const node = loopList.pop();
        const parent = node.parent;
        const key = node.key;
        const data = node.data;

        // Initialize the assignment target. If key is undefined, copy to the parent element, otherwise copy to the child element
        let res = parent;
        if (typeofkey ! = ='undefined') {
            res = parent[key] = {};
        }

        for(let k in data) {
            if (data.hasOwnProperty(k)) {
                if (typeof data[k] === 'object') {
                    // Next loop
                    loopList.push({
                        parent: res,
                        key: k,
                        data: data[k],
                    });
                } else{ res[k] = data[k]; }}}}return root;
}
Copy the code

Due to the problem of space to introduce more, please refer to the following article for details.

The ultimate search for deep copy (unknown to 99% of the population)

Question for this issue

How to implement json.parse with JS?

reference

Delve into deep copying of JavaScript

The ultimate search for deep copy (unknown to 99% of the population)

Deep copy objects in JS

MDN expansion syntax

The Symbol of MDN

Advanced series directory

【 advanced phase 1 】 Call stack
[Advanced phase 2] Scoped closures
【高级 3期】 This is the most important thing
【 advanced 4期】 The principle of deep and shallow copy
【 advanced step 5期刊
【 advanced 6期】 Higher order function
[advanced 7] Event mechanics
【高级 8期】 The Event Loop principle
【高级 9期】 Promise principle
【高级 10期】Async/Await principle
[Advanced phase 11] Anti-shaking/throttling principle
【 advanced 12期】 Modular detailed explanation
【高级 13期】ES6
【高级 14期】 Overview of computer networks
【 advanced 15期】 Browser rendering principles
[advanced 16] WebPack configuration
【 advanced 17 issue 】 Webpack principles
[advanced 18] Front-end monitoring
【 advanced 19期】 Cross-domain and Security
[Advanced 20] Performance optimization
【真题 21期】 The principle of VirtualDom
【 advanced 22期】Diff algorithm
MVVM bidirectional binding
【 advanced 24期】Vuex principle
【 advanced 25期】Redux principle
[advanced 26] Routing principle
【高级 27期】VueRouter source code analysis
【 advanced 28期】ReactRouter source code parsing

communication

Advanced series of articles summarized as follows, there are high quality front-end data, feel good point a star.

Github.com/yygmind/blo…

I am Mu Yiyang, the author of the public number “advanced front-end advanced”, follow me to focus on solving a front-end interview difficult points every week. Next let me take you into the advanced front end of the world, on the way to advance, we encourage!

The introduction

Step 1: Simple implementation

Step 2: Copy the array

Step 3: Circular references

1. Use hash tables

2. Use arrays

Step 4: CopySymbol

Methods a

Method 2

1. Expand the syntax literal array

2. Expand the syntax literal object

Step 5: Crack the recursion stack

Question for this issue

reference

Advanced series directory

communication

Related Posts

🔧 An example learn to use GitLab Runner to implement automatic deployment of pit logging

Timestamp conversion

What will Web 3.0 look like? The guide piece

Step 4: Copy`Symbol`