What is deep copy

  • Simple to understand

B is a copy of A. B has no references to objects in A

  • Another way to think about it

B is a copy of A. Changes to B do not affect A

The solution

JSON serialization Deserialization

const cloneTarget = JSON.parse(JSON.stringify(target))
Copy the code

Disadvantages:

  • Functions are not supported (functions are ignored)
  • Undefined is not supported (undefined will be ignored)
  • Circular references are not supported
  • Date not supported (converted to ISO8601 string)
  • No re support (will be converted to empty objects)
  • Symbol not supported (ignored)

2. Recursive cloning

Ideas:

  • recursive

Look at the type of the node. If it is a basic type, copy it directly. If it is Object, discuss separately

  • Object is divided into ordinary objects – array – array initialization function – how to copy? Closure? Date – how to copy the regular expression RegExp – How to copy the regular expression RegExp

implementation

Next we use test-driven development to implement a deep copy

Environment to prepare

  • Create a directory
mkdir deepClone
cd deepClone
yarn init -y
Copy the code
  • Introduce Chai, Sinon, and typescript
yarn add chai mocha sinon sinon-chai 
yarn add @types/chai @types/mocha @types/sinon @types/sinon-chai  ts-node typescript
Copy the code
  • After installation, modify package.json
"scripts": {  "test": "mocha -r ts-node/register test/**/*.ts"},
Copy the code

Start test-driven development

Create two files:

  • SRC /index.ts source code implementation
  • Test /index.ts Test case

To begin test-driven development, let’s start by writing a simple test case

  • Verify that deepClone is a function

test/index.ts

import sinonChai from "sinon-chai" import chai from 'chai' import {describe} from 'mocha' import deepClone from ".. /src"; const assert = chai.assert; chai.use(sinonChai); Describe ('deepClone', () => {it(' is a function ', () => {assert. IsFunction (deepClone)})})Copy the code

Run the yarn test command, and the test environment will report an error because we haven’t started writing the code yet. Next we start writing code to pass the test case SRC /index.ts

function deepClone(){}

export default deepClone
Copy the code

Run yarn test again, and the console prompts the test case to pass. This completes our simple test-driven use case. Next, let’s implement deep-copy code step by step.

  • Ability to copy base types

Add a new test case to test/index.ts

Const n = 1; const n = 1; const n2 = deepClone(n) assert(n === n2) const s = '112' const s2 = deepClone(s) assert(s === s2) const b = true const b2 = deepClone(b) assert(b === b2) const u = undefined const u2 = deepClone(u) assert(u === u2) const empty = null const  empty2 = deepClone(empty) assert(empty === empty2) const sym = Symbol() const sym2 = deepClone(sym) assert(sym === sym2) });Copy the code

When yarn test is run, a message is displayed indicating that the use case does not pass the implementation code SRC /index.ts

Function deepClone(target){return target // Export default deepCloneCopy the code

If you run YARN test again, a message is displayed indicating that the use case has passed

  • Can copy ordinary objects

Add a new test case to test copying the plain object test/index.ts

Describe (' objects' () = > {it (' can copy the ordinary objects' () = > {const a = {name: 'LZB, address: {the zipCode: '000000'}} const a2 = deepClone(a) assert(a ! == a2) // Objects are not equal Assert (A.name === a2.name) // Common attribute equality assert(A.dress! == a2.address) // Assert (a.dress.zipcode === a2.address.zipcode)})Copy the code

The code implements SRC /index.ts

Type Dictionary = {[key:string]:any} function deepClone(target:any){if(typeof target==='object'){let CloneTarget :Dictionary = {} for(let key in target){cloneTarget[key] = deepClone(target[key])} return CloneTarget} return target // Export default deepCloneCopy the code
  • Can copy array objects

test/index.ts

It (' Can copy array objects ', () => {const a = [[11, 12], [21, 22], [31, 32]] const a2 = deepClone(a) assert(A2! == a) assert(a2[0] ! == a[0]) assert(a2[1] ! == a[1]) assert(a2[2] ! == a[2]) assert.deepEqual(a, a2)})Copy the code

src/index.ts

. If (target instanceof Object){let cloneTarget:Dictionary if(target instanceof Array){cloneTarget = [] Else {cloneTarget = {} // Otherwise, initialize an empty object} for(let key in target){// iterate over each property and return the copied value cloneTarget[key] = deepClone(target[key]) } return cloneTarget } ...Copy the code
  • Can copy function

Add the test case test/index.ts

. It (' can copy function ', ()=>{const a = function (a:number,b:number){return a+b} const a2 = deepClone(a) assert(a! = = a2) assert (a (1, 2) = = = a2 (1, 2))})...Copy the code

runyarn test src/index.ts

If (target instanceof Array){cloneTarget = [] Else if(target instanceof Function){cloneTarget = Function (this:any){return target.apply(this, Arguments)}}else{cloneTarget = {} // Otherwise initialize to null object}...Copy the code

Run yarn test again. The console displays yes

  • Can copy the ring

Add test cases

type Dictionary = { [key: string]: any } ... It (' can copy rings ', ()=>{const a:Dictionary = {x:{y:111}} a. elf = a const a2 = deepClone(a) assert(a! == a2) assert(a.x! ==a2.x) assert(a.x.y===a2.x.y)})Copy the code

Write code to make the test case pass

Type Dictionary = {[key:string]:any} // Use map to cache accessed objects const map = new map () function deepClone(target:any){// Check whether the object is of type If (target instanceof Object){if(map.has(target)){// If (map.has(target)){return map.get(target)}else{let CloneTarget :Dictionary if(target instanceof Array){cloneTarget = [] Else if(target instanceof Function){cloneTarget = Function (this:any){return target.apply(this, Arguments)}}else{cloneTarget = {} // Otherwise initialize to empty object} // Need to cache map.set(target,cloneTarget) for(let key in target){// CloneTarget [key] = deepClone(target[key])} return cloneTarget}} return target // Common types only return the value} export  default deepCloneCopy the code
  • Copy regular expressions

test/index.ts

It (' Copy regular expressions ', () => {const a = new RegExp('hi\d+', 'ig') const a2 = deepClone(a) assert(a! == a2) assert(a.source === a2.source) assert(a.flags === a2.flags) })Copy the code

src/index.ts

. }else if(target instanceof RegExp){// The regular expression object has two properties, source and flags, CloneTarget = new RegExp(target.source, target.flags)}...Copy the code
  • Copy the date

test/index.ts

It (' Copy Date ', ()=>{const a = new Date() const a2:Date = deepClone(a) assert(a! ==a2) assert(a.getTime()===a2.getTime()) })Copy the code

src/index.ts

. else if(target instanceof Date){ cloneTarget = new Date(target) } ...Copy the code
  • Automatically skips stereotype properties

test/index.ts

It (' skip prototype attribute ', ()=>{const a = object.create ({name:'a'}) a.x = {yyy:1} const a2 = deepClone(a) assert(a! ==a2) assert.isFalse('name' in a2) assert(a.x! ==a2.x) assert(a.x.y===a2.x.y) })Copy the code

src/index.ts

For (let key in target){// Filter prototype property if(target.hasownProperty (key)) {// iterate over each property and return the copied value cloneTarget[key] = deepClone(target[key]) } }Copy the code
  • Copy very complex objects

test/index.ts

> {const a = {n: NaN, n2: Infinity, s: "", bool: false, null: null, u: undefined, sym: Symbol(), o: { n: NaN, n2: Infinity, s: "", bool: false, null: null, u: undefined, sym: Symbol() }, array: [ { n: NaN, n2: Infinity, s: "", bool: false, null: null, u: undefined, sym: Symbol() } ] }; const a2 = deepClone(a); assert(a ! == a2); assert.isNaN(a2.n); assert(a.n2 === a2.n2); assert(a.s === a2.s); assert(a.bool === a2.bool); assert(a.null === a2.null); assert(a.u === a2.u); assert(a.sym === a2.sym); assert(a.o ! == a2.o); assert.isNaN(a2.o.n); assert(a.o.n2 === a2.o.n2); assert(a.o.s === a2.o.s); assert(a.o.bool === a2.o.bool); assert(a.o.null === a2.o.null); assert(a.o.u === a2.o.u); assert(a.o.sym === a2.o.sym); assert(a.array ! == a2.array); assert(a.array[0] ! == a2.array[0]); assert.isNaN(a2.array[0].n); assert(a.array[0].n2 === a2.array[0].n2); assert(a.array[0].s === a2.array[0].s); assert(a.array[0].bool === a2.array[0].bool); assert(a.array[0].null === a2.array[0].null); assert(a.array[0].u === a2.array[0].u); assert(a.array[0].sym === a2.array[0].sym); });Copy the code
  • Don’t burst stack
Const a = {child: null}; let b:Dictionary = a; for (let i = 0; i < 10000; i++) { b.child = { child: null }; b = b.child; } const a2 = deepClone(a); assert(a ! == a2); assert(a.child ! == a2.child); });Copy the code

src/index.ts

Type Dictionary = {[key: string]: any} const map = new map () function deepClone(target: Any) {const stack: any = [] if (target instanceof Object) {const root = {parent: null, key: null, value: target} stack.push(root) let current = stack.pop() let cloneTarget while (current) { const nodeValue = current.value // Const temp; const temp; Set (nodeValue, temp) // For (let k in nodeValue) {if (! Nodevalue.hasownproperty (k)) continue If (map.has(nodeValue[k])) {temp[k] = map.get(nodeValue[k])} else if (nodeValue[k] instanceof Object) {// If the attribute value is an object, stack. Push ({parent: temp, key: k, value: Temp [k] = nodeValue[k]} else {temp[k] = nodeValue[k]} else {temp[k] = nodeValue[k]}} If yes, assign the temporary variable to the parent's key current. Parent? (current.parent[current.key] = temp) : Current = stack.pop()} return cloneTarget} return target} const createObject = (target: Object) => { let obj: Dictionary if (target instanceof Array) {obj = [] Else if (target instanceof Function) {obj = Function (this: Any) {return target.apply(this, arguments)}} else if (target instanceof RegExp) {// Regular expression objects will have two properties, source and flags, Obj = new RegExp(target.source, Target. Flags)} else if (target instanceof Date) {obj = new Date(target)} else {obj = {} // otherwise initialize to empty object} return obj} export default deepCloneCopy the code

1. The root node is pushed onto the stack first. 2. The stack is then traversed, and if there is data in the stack, the top of the stack is fetched. 3. First create a temporary object, and then iterate over the attributes of the object at the top of the stack. If the attribute value is an object, create a new node based on the attributes and attributes, and add it to the stack. If the attribute value is of a normal type, it is assigned directly. 4. Continue processing stack data until the stack is empty.

The source address