The cloneDeep Lodash

Writing in the front

In ECMAScript, there are two types of copy: deep copy and shallow copy, as well as value copy and reference copy. The difference between deep copy and shallow copy is that operations are performed on objects of reference type. The former copies the actual value performed by the reference type (value copy), while the latter copies only the reference (reference copy). In Lodash, both shallow and shallow copies are implemented in a baseClone method, which is based on isDeep values.

This paper mainly explores and appropriately expands the implementation of the more complex deep copy, shallow copy is not discussed

Copying, after all, is copying data. Data types are generally divided into two types: value types and reference types. Let’s first look at copying value types.

Value types

Value types, also called primitive data types in ECMAScript. There are currently several basic data types in ECMAScript.

const undefinedTag = '[object Undefined]'
const nullTag = '[object Null]'

const boolTag = '[object Boolean]'
const numberTag = '[object Number]'
const stringTag = '[object String]'

// es2015
const symbolTag = '[object Symbol]'

// es2019?
const bigIntTag = '[object BigInt]'
Copy the code

Primitive data types are value passed, so any value of the primitive data type can be returned directly to itself

const pVal = [
  undefinedTag, nullTag,
  boolTag, numberTag, stringTag,
  symbolTag, bigIntTag
]
function clone (target) {
  let type = Object.prototype.toString.call(target)
  if (pVal.includes(type)) {
  	return target
  } 
}
Copy the code

Common reference types

All but primitive data types are reference data types. Let’s start with the most common Array and Object.

Implement a ForEach

Before clone can clone arrays and objects, we need to implement a ForEach method.

Why re-implement?

You need a foreach method at clone time for two reasons.

Performance.Array.prototype.forEachThe performance is average.
Object.prototypeThere is no similarforEachA method that can iterate over the value of an objectObject.prototype.keys 和 for... inTo achieve a similar effect, but the latter performance is poor.

/* @param {Array} [Array] / @param {Function} / @returns {Array} Return the original array */
function forEach(array, iteratee) {
  let index = - 1
  const length = array.length

  while (++index < length) {
    // interrupt traversal
    if (iteratee(array[index], index, array) === false) {
      break}}return array
}
Copy the code

You can break the loop

Array.prototype.forEach doesn’t support breaking loops, but our forEach implementation does.

var arr = [1.2.3]

arr.forEach(i= > {
 if (i === 2) {
  return false
 }
 console.log(i)
})
/ / 1
/ / 3
// Only current traversal can be skipped

forEach(arr, i => {
 if (i === 2) {
  return false
 }
 console.log(i)
})
/ / 1
// Just return false in one iteration to break out of the loop
Copy the code

Iterate over an object/array

Because objects have a similar structure to arrays, arrays can be treated as a special key-value, where key is the index of an array item and value is the object of an array item. If we wanted to traverse arrays and objects uniformly, we could write:

const unknownObj = {} || []  
const props = Array.isArray(unknownObj) ? undefined : Object.keys(unknownObj)
forEach(props || unknownObj, (subValue, key) => {
  if (props) {
    key = subValue
    subValue = unknownObj[key]
  }
})
Copy the code

Use of WeakMap

What about circular references?

During clone, objects referenced in a loop will overflow the stack if they are not terminated during recursion. An example of implementing a simple Cloen object:

var cloneObj = function (obj) {
  var target = new obj.constructor()
  forEach(Object.keys(obj), (val, key) => {
   key = val
   val = obj[key]
   if (Object.prototype.toString.call(val) === "[object Object]") {
     target[key] = cloneObj(val)
   } else {
     target[key] = val
   }
  })
  return target
}
Copy the code

Here is an example to prove that this function works:

var a = {
	x: {
    y: 2}}var b = cloneObj(a)
b // { x: { y: 2 } }
b === a // false
b.x === a.x // false
Copy the code

In the following example, you can see a stack overflow:

var a = {
	x: 1
}
a.x = a
cloneObj(a) // Uncaught RangeError: Maximum call stack size exceeded
Copy the code

How to solve this problem? We can see the following:

a.x === a // true
Copy the code

So, just store the value of A, and before the next recursion, if the recursive value of A.x is the same as the stored value, then you can return it without recursion. We can do this:

var cache = []
var cloneObj = function (obj) {
  var target = new obj.constructor()
  if (cache.includes(obj)) {
    return obj
  }
  cache.push(obj)
  forEach(Object.keys(obj), (val, key) => {
   key = val
   val = obj[key]
   if (Object.prototype.toString.call(val) === "[object Object]") {
     target[key] = cloneObj(val)
   } else {
     target[key] = val
   }
  })
  return target
}

var b = cloneObj(a)
a === b // false
Copy the code

Although we ended up preventing recursion, there are drawbacks to this approach. We also need to declare an additional external variable, the cache, to be wrapped as a module, (1) must use closures, the cache holds the value of A, and (2) if the reference persists, a will remain in memory and will not be garbage collected. Also, the ③ includes method iterates through the groups each time, which is very performance consuming.

// Closures must be introduced
var markClone = function () {
	var cache = []
  return function (obj) {
    var target = new obj.constructor()
    if (cache.includes(obj)) {
      return obj
    }
    cache.push(obj)
    forEach(Object.keys(obj), (val, key) => {
     key = val
     val = obj[key]
     if (Object.prototype.toString.call(val) === "[object Object]") {
       target[key] = cloneObj(val)
     } else {
       target[key] = val
     }
    })
    return target
  }
}
var cloneObj = makeClone()
cloneObj({x: 1})
Copy the code

Regarding ①, we can solve it as follows:

var cloneObj = function (obj, cache = []) {
  var target = new obj.constructor()
  if (cache.includes(obj)) {
    return obj
  }
  cache.push(obj)
  forEach(Object.keys(obj), (val, key) => {
   key = val
   val = obj[key]
   if (Object.prototype.toString.call(val) === "[object Object]") {
     target[key] = cloneObj(val, cache)
   } else {
     target[key] = val
   }
  })
  return target
}
cloneObj({x: 1})
Copy the code

Let’s leave the remaining two questions to WeakMap.

Weak reference: WeakMap

Normal objects only support strings as keys, and even if you use other data types, they call their own toString() method:

var a = {}
a[{x:2}] = 3
a[234] = 'hello'
Object.keys(a) // ["234", "[object Object]"]
Copy the code

To enable other objects to be used as keys, ECMAScript 6 adds the Map data type to support any data type as a key:

var m = new Map()
m.set(function(){}, 1)
m.set([1.3.5].2)
m.set({x: 'abc'}, 3)
m.forEach((val, key) = > console.log(val, key))
/ 1 / ƒ () {}
// 2 [1, 3, 5]
// 3 {x: "abc"}
Copy the code

The WeakMap type is slightly different in that it only supports types other than raw data types as keys, and these keys cannot be traversed because weak references are stored.

Weak references are not counted in the reference count. If a reference object’s reference count becomes zero, it will be collected in garbage collection. At the same time, weak references are disassociated.

We use WeakMap instead of cache:

var cloneObj = function (obj, cache = new WeakMap()) {
  var target = new obj.constructor()
  if (cache.has(obj)) {
    return cache.get(obj)
  }
  cache.set(obj, target)
  forEach(Object.keys(obj), (val, key) => {
   key = val
   val = obj[key]
   if (Object.prototype.toString.call(val) === "[object Object]") {
     // If the reference is circular, this line looks like a.x = a, because the cloneObj method returns target
     target[key] = cloneObj(val, cache)
   } else {
     target[key] = val
   }
  })
  return target
}
cloneObj({x: 1})
Copy the code

The get and HAS methods are definitely more efficient (O(1)) than include (O(n)), and we have solved the problem ③. Let’s now test whether we have solved the problem ②.

Test garbage collection

First, open the command line.

node --expose-gc
Copy the code

The expose-GC parameter allows manual garbage collection

Then execute:

// Perform a garbage collection manually to ensure accurate memory usage
> global.gc();
undefined

// Define the getUsage method, which can quickly obtain the current heap memory usage in M
> var getUsage = (a)= > process.memoryUsage().heapUsed / 1024 / 1024 + 'M'

// check the initial memory usage. HeapUsed is about 5M
> getUsage();
'5.1407012939453125 M'

> let wm = new WeakMap(a);undefined

// Create a variable key that points to an array of 5*1024*1024
> let key = new Array(5 * 1024 * 1024);
undefined

// Set the key name of the WeakMap instance, which also points to the key array
// In this case, the key array is actually referenced twice,
// The variable key is referenced once, and the key name of WeakMap is referenced twice
// However, WeakMap is a weak reference. For the engine, the reference count is still 1
> wm.set(key, 1);
WeakMap {}

> global.gc();
undefined

// The heapUsed memory has been increased to 45MB
> getUsage();
'45.260292053222656 M'

// Clear the reference to array by variable key,
// But there is no manual clearing of the key name reference to the array of the WeakMap instance
> key = null;
null

// Perform the garbage collection again
> global.gc();
undefined

// The heapUsed memory is changed back to around 5M.
// You can see that WeakMap's key name reference does not prevent GC from collecting memory
> getUsage();
'5.110954284667969 M'
Copy the code

Concise version

Based on the above content, we can summarize a concise version, support value type, Array, Object type copy:

const sampleClone = function (target, cache = new WeakMap()) {
	/ / value types
	const undefinedTag = '[object Undefined]'
	const nullTag = '[object Null]'
	const boolTag = '[object Boolean]'
	const numberTag = '[object Number]'
	const stringTag = '[object String]'
	const symbolTag = '[object Symbol]'
	const bigIntTag = '[object BigInt]'
	// Reference type
	const arrayTag = '[object Array]'
	const objectTag = '[object Object]'

	// The type of the object passed in
	const type = Object.prototype.toString.call(target)

	// All supported types
	const allTypes = [
		undefinedTag, nullTag,boolTag, numberTag, stringTag,symbolTag, bigIntTag, arrayTag, objectTag
	]

	// If it is an unsupported type
	if(! allTypes.includes(type)) {console.warn(` does not support${type}Type, return {}. `)
		return{}}// Array of value types
	const valTypes = [
		undefinedTag, nullTag,boolTag, numberTag, stringTag,symbolTag, bigIntTag
	]

	// The value type returns directly
	if (valTypes.includes(type)) {
		return target
	}

	// forEach
	function forEach(array, iteratee) {
		let index = - 1
		const length = array.length

		while (++index < length) {
			// interrupt traversal
			if (iteratee(array[index], index, array) === false) {
				break}}return array
	}

	// Initialize the clone value
	let cloneTarget = new target.constructor()
	// Prevent circular references
	if (cache.has(target)) {
		return cache.get(target)
	}
	cache.set(target, cloneTarget)

	// Clone Array and Object
	const keys = type === arrayTag ? undefined : Object.keys(target)
	forEach(keys || target, (value, key) => {
		if (keys) {
			key = value
		}
		cloneTarget[key] = sampleClone(target[key], cache)
	})

	return cloneTarget
}
Copy the code

The clone of raw data type and Array and Object realized above can basically meet the daily use, because this is the data format that the front-end will deal with in most cases.

Object of a special Array type

There are several lines of code in Lodash’s Baseclone.js:

function initCloneArray(array) {
  const { length } = array
  const result = new array.constructor(length)

  // Add properties assigned by `RegExp#exec`.
  if (length && typeof array[0= = ='string' && hasOwnProperty.call(array, 'index')) {
    result.index = array.index
    result.input = array.input
  }
  return result
}
Copy the code

The initCloneArray method is used to initialize an array object, but if some special conditions are met, it initializes the index and input properties. This is to initialize the special Array returned by the regexp.prototype. exec method. We can take a look:

As you can see, this array object is different from the usual array. To clone an array object of this type, follow Lodash’s instructions. We now add it to sampleClone.

var sampleClone = function (target, cache = new WeakMap()) {... let cloneTargetif (Array.isArray(target)) {
  	cloneTarget = initCloneArray(target)
  } else {
    cloneTarget = new target.constructor()
  }
  ...
}
Copy the code

What is the groups attribute?

A special Object key

In sampleClone above, we used object. keys to iterate over keys on “all” objects. But this is questionable because the method does not take the key of the prototype object, nor does it take the key of type Symbol, nor does it iterate over non-enumerable values.

In my previous article, I listed several methods for retrieving attributes that, in combination with these methods, can be used to retrieve all the values available from the original object. The key is to use several methods to obtain these values based on object. keys. In Lodash’s baseClone method, isFlat indicates whether properties on the prototype object are copied, and isFull indicates whether keys of type Symbol are copied. Note that Lodash only copies enumerable values.

Let’s do this by passing parameters:

// from lodash, use for... In, returns an array of enumerable property keys + prototype keys on an object
function keysIn(object) {
  const result = []
  for (const key in object) {
    result.push(key)
  }
  return result
}

// From lodash, returns an array of enumerable Symbol keys on an object
function getSymbols(object) {
  if (object == null) {
    return []
  }
  object = Object(object)
  return Object
    .getOwnPropertySymbols(object)
    .filter((symbol) = > Object.prototype.propertyIsEnumerable.call(object, symbol))
}

// From lodash, returns an array of enumerable property keys + Symbol keys on the object
function getAllKeys(object) {
  const result = keys(object)
  if (!Array.isArray(object)) { result.push(... getSymbols(object)) }return result
}

// From Lodash, returns an array of enumerable (attribute key + Symbol key) attributes on the prototype chain of objects
function getSymbolsIn(object) {
  const result = []
  while(object) { result.push(... getSymbols(object)) object =Object.getPrototypeOf(Object(object))
  }
  return result
}

// From lodash, returns an array of enumerable property keys + Symbol keys + enumerable property keys + Symbol keys on the prototype chain
function getAllKeysIn(object) {
  const result = []
  for (const key in object) {
    result.push(key)
  }
  if (!Array.isArray(object)) { result.push(... getSymbolsIn(object)) }return result
}

var sampleClone = function (
	target, cache = new WeakMap(), includePrototypeKey.includeSymbolKey
  ) {...// Finally get the method used by the object keys array
	const keysFunc = isFull
    ? (isFlat ? getAllKeysIn : getAllKeys)
    : (isFlat ? keysIn : keys)
  
  ...
  
  const keys = type === arrayTag ? undefined : keysFunc(target)
  

  ...
}
Copy the code

Class Array Like

You can learn about the concept of class arrays in this article. A class array is a special kind of object, which is copied by our custom forEach. Lodash distinguishes it when fetching an array of object keys. In the getAllKeys method, we refer to the keys method, which uses different values depending on whether it is an array of classes:

function keys(object) {
  return isArrayLike(object)
    ? arrayLikeKeys(object)
    : Object.keys(Object(object))
}
Copy the code

The isArrayLike method is used to determine whether it is a class array, as you can see in detail in this article. Let’s take a look at how the arrayLikeKeys method retrieves keys from an array of classes.

// Take all the keys from the class array value and place them in a new array
/ / such as [' a ', 'b', 'c']
function arrayLikeKeys(value, inherited) {
  const isArr = Array.isArray(value)
  constisArg = ! isArr && isArguments(value)constisBuff = ! isArr && ! isArg && isBuffer(value)constisType = ! isArr && ! isArg && ! isBuff && isTypedArray(value)const skipIndexes = isArr || isArg || isBuff || isType
  const length = value.length
  const result = new Array(skipIndexes ? length : 0)
  let index = skipIndexes ? - 1 : length
  while (++index < length) {
    result[index] = `${index}`
  }
  for (const key in value) {
    if ((inherited || Object.prototype.hasOwnProperty.call(value, key)) && ! (skipIndexes && (// Safari 9 has enumerable `arguments.length` in strict mode.
          (key === 'length' ||
           // Skip index properties.
           isIndex(key, length))
        ))) {
      result.push(key)
    }
  }
  return result
}
Copy the code

As we can see, arrayLikeKeys takes two steps to retrieve the key.

The first step

Determine if there is an IndexKey (that is, 0,1,2,3,4…) The key.

// Arrays, parameter arrays, Buff, and Typed arrays are all treated as IndexKey objects
const skipIndexes = isArr || isArg || isBuff || isType

// Insert indexKeys into the array and skip all other types
const length = value.length
const result = new Array(skipIndexes ? length : 0)
let index = skipIndexes ? - 1 : length
while (++index < length) {
  result[index] = `${index}`
}
Copy the code

The second step

Extract all keys except IndexKey

// The inherited key parameter identifies whether the inherited key is inherited from the prototype object.

function arrayLikeKeys(value, inherited) {... (inherited ||Object.prototype.hasOwnProperty.call(value, key))
  ...
}
Copy the code

Inherited = True: when inherited = true: when inherited = True: when inherited = True In, which can take the key inherited from the prototype object;

To false or Undefined, it is to use the Object. The prototype. The hasOwnProperty take key Object itself.

function arrayLikeKeys(value, inherited) {
...
!(skipIndexes && (key === 'length' || isIndex(key, length)))
...
{
  result.push(key)
}
}
Copy the code

SkipIndexes is used to determine whether the array has an IndexKey. If not, the current key is another key. Go to the next step and insert the key into the array to be returned. If so, go ahead and judge.

In Safari 9, the arguments.length property is enumerable, but Lodash does not copy length. Because Lodash only copies enumerable attributes. Then we move on to the isIndex method:

function isIndex(value, length) {
  const type = typeof value
  length = length == null ? MAX_SAFE_INTEGER : length

  return!!!!! length && (type ==='number'|| (type ! = ='symbol' && reIsUint.test(value))) &&
        (value > - 1 && value % 1= =0 && value < length)
}
Copy the code

This method is used to determine whether the current key is an IndexKey of the array. If so, the insert is skipped because it was already inserted in the while loop, if not, insert.

AssignValue?

After processing the object, at the end of the assignment, we see Lodash write:

assignValue(result, key, baseClone(subValue, bitmask, customizer, key, value, stack))
Copy the code

Instead of assigning directly to =, we use a method called assignValue, which we can look at:

function assignValue(object, key, value) {
  const objValue = object[key]

  if(! (hasOwnProperty.call(object, key) && eq(objValue, value))) {if(value ! = =0| | -1 / value) === (1 / objValue)) {
      baseAssignValue(object, key, value)
    }
  } else if (value === undefined && !(key in object)) {
    baseAssignValue(object, key, value)
  }
}

function baseAssignValue(object, key, value) {
  if (key == '__proto__') {
    Object.defineProperty(object, key, {
      'configurable': true.'enumerable': true.'value': value,
      'writable': true})}else {
    object[key] = value
  }
}
Copy the code

BaseAssignValue is essentially an assignment, but two conditions need to be met to get to this point. Let’s look at the first one:

! (hasOwnProperty.call(object, key) && eq(objValue, value))Copy the code

This is only true if the key is on the prototype chain, but we may not need to deal with prototype object properties, as discussed later.

Let’s move on to the second condition:

value === undefined && !(key in object)
Copy the code

The property must not be on the object. This condition should be for other function calls in Lodash, which we can skip.

So we don’t need the assign method at the end, we just use =.

Began to transform

We are now modifying our simple version for the special objects covered above.

A special array object

Reged-generated special array objects need to be compatible. As shown earlier, the special properties are copied directly when the array is initialized.

A special Key

Lodash supports two parameters in the baseClone method: whether to copy properties on the prototype object and whether to copy values of type Symbol. Let’s go through them one by one.

Properties on the stereotype object

Let’s forget about how to “copy the properties of the prototype object” and start thinking about “do we need to copy the properties of the prototype object?” I don’t think so. There are two reasons.

Every object is an instance of a class, and the instance properties of the class are the prototype object properties of the object. In actual scenarios, if we need such an instance, we can simply use the class to generate a new and identical instance, and it seems that there is no scenario to copy an identical instance.
LodashSuch a parameter is provided, but never used. I’ve already mentioned it to the developersIssue.

`Symbol`type

Symbol is a basic data type that is naturally supported. You can expose a parameter and let the user decide whether to copy it or not.

Therefore, in our next enhanced version, this parameter will not be added, nor will the object’s prototype object properties be copied.

An array of class

Class arrays also need to be compatible, as shown in the previous section, when fetching the object’s key, use the corresponding method. In addition, the binary array is not going to be dealt with for the moment, but will be added separately later.

Enhanced version

const hasOwnProperty = Object.prototype.hasOwnProperty
const getType = Object.prototype.toString


// Initialize an array object, including the special array returned by the re
function initCloneArray(array) {
	const { length } = array
	const result = new array.constructor(length)

	// Add properties assigned by `RegExp#exec`.
	if (length && typeof array[0= = ='string' && hasOwnProperty.call(array, 'index')) {
		result.index = array.index
		result.input = array.input
	}
	return result
}

// Get the key method
function getKeysFunc(isFull) {
	// Returns an array of enumerable Symbol keys on an object
	function getSymbols(object) {
		if (object == null) {
			return []
		}
		object = Object(object)
		return Object
			.getOwnPropertySymbols(object)
			.filter((symbol) = > Object.prototype.propertyIsEnumerable.call(object, symbol))
	}
	// Check whether the length property of the class array is valid
	function isLength(value) {
		return typeof value === 'number' &&
			value > - 1 && value % 1= = =0 && value <= Number.MAX_SAFE_INTEGER
	}
	// Check if it is a class array
	function isArrayLike(value) {
		returnvalue ! =null && typeofvalue ! = ='function' && isLength(value.length)
	}
	// Check whether the index of the class array is valid
	function isIndex(value, length) {
		const reIsUint = / ^ (? :0|[1-9]\d*)$/
		const type = typeof value
		length = length == null ? Number.MAX_SAFE_INTEGER : length

		return!!!!! length && (type ==='number'|| (type ! = ='symbol' && reIsUint.test(value))) &&
			(value > - 1 && value % 1= = =0 && value < length)
	}
	// Arguments
	function isArguments(value) {
		return typeof value === 'object'&& value ! = =null && getType.call(value) === '[object Arguments]'
	}
	// Returns an array of keys from the class array
	function arrayLikeKeys(value, inherited) {
		const isArr = Array.isArray(value)
		constisArg = ! isArr && isArguments(value)const skipIndexes = isArr || isArg
		const length = value.length
		const result = new Array(skipIndexes ? length : 0)
		let index = skipIndexes ? - 1 : length
		while (++index < length) {
			result[index] = `${index}`
		}
		for (const key in value) {
			if((inherited || hasOwnProperty.call(value, key)) && ! (skipIndexes && (// Safari 9 has enumerable `arguments.length` in strict mode.
					(key === 'length' ||
						// Skip index properties.
						isIndex(key, length))
				))) {
				result.push(key)
			}
		}
		return result
	}


	// Returns the enumerable property key on the object
	function keys(object) {
		return isArrayLike(object)
			? arrayLikeKeys(object)
			: Object.keys(Object(object))
	}

	// Returns an array of enumerable property keys + Symbol keys on the object
	function getAllKeys(object) {
		const result = keys(object)
		if (!Array.isArray(object)) { result.push(... getSymbols(object)) }return result
	}


	return isFull
		? getAllKeys
		: keys
}

const enhanceClone = function (target, cache = new WeakMap(), isFull = true) {
	/ / value types
	const undefinedTag = '[object Undefined]'
	const nullTag = '[object Null]'
	const boolTag = '[object Boolean]'
	const numberTag = '[object Number]'
	const stringTag = '[object String]'
	const symbolTag = '[object Symbol]'
	const bigIntTag = '[object BigInt]'
	// Reference type
	const arrayTag = '[object Array]'
	const objectTag = '[object Object]'

	// The type of the object passed in
	const type = getType.call(target)

	// All supported types
	const allTypes = [
		undefinedTag, nullTag,boolTag, numberTag, stringTag, symbolTag, bigIntTag, arrayTag, objectTag
	]

	// If it is an unsupported type
	if(! allTypes.includes(type)) {console.warn(` does not support${type}Type, return {}. `)
		return{}}// Array of value types
	const valTypes = [
		undefinedTag, nullTag,boolTag, numberTag, stringTag,symbolTag, bigIntTag
	]

	// The value type returns directly
	if (valTypes.includes(type)) {
		return target
	}

	// forEach
	function forEach(array, iteratee) {
		let index = - 1
		const length = array.length

		while (++index < length) {
			// interrupt traversal
			if (iteratee(array[index], index, array) === false) {
				break}}return array
	}

	// Initialize the clone value
	let cloneTarget
	if (Array.isArray(target)) {
		cloneTarget = initCloneArray(target)
	} else {
		cloneTarget = new target.constructor()
	}
	// Prevent circular references
	if (cache.has(target)) {
		return cache.get(target)
	}
	cache.set(target, cloneTarget)

	// Determine the method to obtain the key
	const keysFunc = getKeysFunc(isFull)

	// Clone Array and Object
	const keys = type === arrayTag ? undefined : keysFunc(target)
	forEach(keys || target, (value, key) => {
		if (keys) {
			key = value
		}
		cloneTarget[key] = enhanceClone(target[key], cache, isFull)
	})

	return cloneTarget
}
Copy the code

At this point, we’ve added a few special types of objects and arrays, which we’ll call the enhanced version.

The Set and Map

Both Set and Map provide forEach methods to traverse itself, and WeakMap can be used for processing cycles. We continue with sampleCloen by adding:

var cloneDeep = function (target, cache = new WeakMap()) {... const setTag ='[object Set]'
  const mapTag = '[object Map]'.// Array of reference types
	const refTypes = [
		arrayTag, objectTag, setTag, mapTag, argTag
	]
	// If the reference type is not specified, an empty object is returned, indicating that it cannot be copied
	if(! refTypes.includes(type)) {console.warn(` does not support${type}Type, return {}. `)
		return{}}/ / clone set
  if (type === setTag) {
  	target.forEach(value= > {
      cloneTarget.add(cloneDeep(value, cache))
    })
    return cloneTarget
  }
  / / clone map
  if (type === mapTag) {
    target.forEach((value, key) = > {
      cloneTarget.set(key, cloneDeep(value, cache))
    })
    return cloneTarget
  }
  ...
  return target
}
Copy the code

WeakMap and WeakSet

WeakMap and WeakSet store some “temporary” values, as long as the number of references is 0, it will be automatically recovered by garbage collection mechanism, this timing is unpredictable, so how many members there are in a WeakMap and WeakSet is also unpredictable. ECMAScript also states that WeakMap and WeakSet are not traversal.

Therefore, WeakMap and WeakSet cannot be copied.

WeakMap encountered in Lodash returns the original object or {}.

. const weakMapTag ='[object WeakMap]'. const cloneableTags = {} ... cloneableTags[errorTag] = cloneableTags[weakMapTag] =false.// Return the original object if the parent of the original object is passed, otherwise return {}
if(isFunc || ! cloneableTags[tag]) {return object ? value : {}
}
Copy the code

That is, if you copy a WeakMap object directly, it returns {}; However, if you just copy a pointer to the object’s memory, you can still do it, and the difference between a pointer and an object depends on whether the parent object was passed in. Therefore, to properly handle these non-copiable objects, we need to add the parent object’s arguments to the function’s argument list. Modified as follows:

const cloneDeep = function (target, cache = new WeakMap(), isFull = true.parent) {...// Array of reference types
	const refTypes = [
		arrayTag, objectTag, setTag, mapTag, argTag
	]
	// Cannot copy the array
	const unableTypes = [
		weakMapTag, weakSetTag
	]

	// Returns an empty object if it is not of the specified reference type and is not an object that cannot be copied
	if(! refTypes.includes(type)) {// If the parent object is passed in, a reference is returned; Otherwise, an empty object is returned
		if (unableTypes.includes(type)) {
			return parent ? target : {}
		} else {
			console.warn(` does not support${type}Type, return {}. `)
			return{}}}... forEach(keys || target, (value, key) => {if (keys) {
			key = value
		}
		cloneTarget[key] = cloneDeep(target[key], cache, isFull, target)
	})
  ...
}  
Copy the code

Why Lodash only treats WeakMap and does not consider WeakSet?

Arguments

Arguments are also special array-like objects. It has no prototype method for array instances, and its prototype Object points to the prototype of Object. Let’s look at its properties:

let tryArgu = function (a, b) {
	console.log(Object.prototype.toString.call(arguments))
  console.log(Object.getPrototypeOf(arguments) = = =Object.prototype)
  console.log(arguments)
}
tryArgu(1.2)
// [object Arguments]
// true
Copy the code

We see a lot more callee properties than normal array objects. This property is a non-enumerable property with the value of the current function.

arguments.callee === tryArgu // true
Object.getOwnPropertyDescriptor(arguments.'callee')
Copy the code

With that in mind, cloning objects of this type is straightforward. Let’s take a look at how Lodash works:

. if (tag == objectTag || tag == argsTag || (isFunc && ! object)) { result = (isFlat || isFunc) ? {} : initCloneObject(value) ... }... function initCloneObject(object) {return (typeof object.constructor === 'function' && !isPrototype(object))
    ? Object.create(Object.getPrototypeOf(object))
    : {}
}
...
Copy the code

As you can see, it initializes Arguments as an object. Let’s try:

var tryArgu = function (a, b) {
	return _.cloneDeep(arguments)
}
tryArgu(1.2)
// {0: 1, 1: 2}
Copy the code

This is done to ensure that argumens[n] is identical to cloneTarget[n]. What do we do if we want to be real?

Since we don’t have arguments constructors, we can only initialize a clone by returning a real arguments object and modifying its properties with a function.

const cloneDeep = function (target, cache = new WeakMap(), isFull = true.parent) {... let cloneTargetif (Array.isArray(target)) {
		cloneTarget = initCloneArray(target)
	} else {
		if (type === argTag) {
			cloneTarget = (function(){return arguments})()
			cloneTarget.callee = target.callee
			cloneTarget.length = target.length
		} else {
			cloneTarget = new target.constructor()
		}
	}
  ...
}
Copy the code

Note that the length attribute refers to the number of arguments, and can also be modified, we keep the same as the original object.

RegExp

We may be used to declaring regular expressions in literal form, but each regular expression is an instance of a RegExp, with properties and methods. We can also instantiate a RegExp object using the new keyword.

/ / literal
var reg = /abc/gi
// new
var reg2 = new RegExp('abc'.'gi')
Copy the code

A regular expression consists of two parts: **source ** and flags.

reg.source // 'abc'
reg.flags // 'gi'
Copy the code

The characters in **source ** can be roughly divided into six categories. As shown in the

The name of the class	English name of category	For example,
Character classes	Character Classes	`\d`
Matches any Arabic numeral. Equivalent to [0-9]
Character set	Character Sets	`[xyz]`
Matches any character in the collection. Match the ‘x’ in ‘sex’
The border	Boundaries	`$`
Match the end. Such as`/t$/`Does not match the ‘t’ in ‘tea’, but matches the ‘t’ in ‘eat’
Grouping and backreferencing	Grouping & Back References	`(x)`
Matches ‘x’ and captures the match. Such as matching two ‘x’ in ‘xyzxyz’.
quantifiers	Quantifiers	`x*`
Matches the previous pattern ‘x’0 or more times.
assertions	Assertions	`x(? =y)`
Matches only x followed by y, such as ‘xy abcx ayx’ matches only the first x

Flags contains six characters and can be used in combination. As shown in the

character	Corresponding properties	use
g	global	Global matching; Find all matches instead of stopping after the first match
i	ignoreCase	Ignore case
m	multiline	Multiple lines; Treat the start and end characters (^ and $) as if they work on multiple lines (that is, match the start and end of each line respectively (split by \n or \r), rather than just the beginning and end of the entire input string.
u	unicode	Unicode; A sequence that treats a pattern as a Unicode sequence point
y	sticky	Viscous matching; Matches only the indexes indicated by the lastIndex attribute of this regular expression in the target string (and does not attempt to match from any subsequent indexes).
s	dotAll	DotAll mode,. Can match any character (including terminator ‘\n’).

To find out if the current regular expression contains a flag, you can get it directly from the attribute. Note that these properties can only be obtained, not set, because once the regular expression instance is built, it cannot be changed, and once changed, it is another regular expression.

let reg = /abc/uys
reg.global // false
reg.ignoreCase // false
reg.multiline // false
reg.unicode // true
reg.sticky // true
reg.dotAll // true
Copy the code

In addition to this, regular expressions have one more notable property: lastIndex. The value of this property is where the regular expression starts matching, using the test and exec methods of the regular object, and it is possible to change the value of lastIndex when the modifier is G or Y. Of course, you can also set its value.

var reg = /ab/g
var str = 'abababababab'
reg.lastIndex / / 0
reg.test(str) // true
reg.lastIndex / / 2
reg.test(str) // true
reg.lastIndex / / 4
Copy the code

Now that we have regular expressions pretty much figured out, let’s take a look at how Lodash copies regular objects.

const reFlags = /\w*$/
function cloneRegExp(regexp) {
  const result = new regexp.constructor(regexp.source, reFlags.exec(regexp))
  result.lastIndex = regexp.lastIndex
  return result
}
Copy the code

In /\w*$/, \w is the same as [a-za-z0-9_], * means zero or more matches, and $means match from the end. So, the re means to match from the end, find characters that are not [A-za-z0-9_], and return those in the middle. Let’s try:

/\w*$/.exec('abc/def') 
// [0: 'def', groups: undefined, index: 4, input: 'abc/def', length: 1]
/\w*$/.exec('abcdef')
// [0: 'abcdef', groups: undefined, index: 0, input: 'abcdef', length: 1]
Copy the code

The second argument to RegExp should be of type String; if not, the object’s toString method is called. Therefore, the result returned above is implicitly converted to String when building the instance.

/\w*$/.exec('abc/def').toString() // 'def'
Copy the code

I don’t know why Lodash has gone around so much, why not just use regexp. Flags instead? If it is for backward compatibility, there will probably be new flags that [a-za-z] should be enough, no need to use \w? I can’t find the answer right now, and some of the other implementations on the web don’t use this regex match, so let’s improve this as well.

function cloneRegExp(regexp) {
  const result = new regexp.constructor(regexp.source, regexp.flags)
  result.lastIndex = regexp.lastIndex
  return result
}
Copy the code

Add it to our deep copy

const cloneDeep = function (target, cache = new WeakMap(), isFull = true.parent) {... const regexpTag ='[object RegExp]'. if (Array.isArray(target)) {
		cloneTarget = initCloneArray(target)
	} else {
		if (type === argTag) {
			cloneTarget = (function(){return arguments})()
			cloneTarget.callee = target.callee
			cloneTarget.length = target.length
		} else if(type === regexpTag) {
			cloneTarget = cloneRegExp(target)
		} else {
			cloneTarget = new target.constructor()
		}
	}	
...
}
Copy the code

Date

An instance object of time is actually composed of some time value + some time handlers. So it is easy to copy, just use the time value as a parameter, to generate a new instance.

// When an instance is built, no arguments are passed, and the value is the time when the instance was created
var now = new Date(a)Object.prototype.toString.call(now) // "[object Date]"

now + ' ' "Thu Dec 26 2019 15:08:50 GMT+0800"

+now / / 1577344130208
Copy the code

Let’s take a look at how Lodash gets the time value:

function initCloneByTag(object, tag, isDeep) {
  const Ctor = object.constructor
	...
  case dateTag:
  	return new Ctor(+object)
	...
}
Copy the code

It’s exactly what we thought it would be.

const cloneDeep = function (target, cache = new WeakMap(), isFull = true.parent) {... elseif(type === dateTag) {
			cloneTarget = new target.constructor(+target)
		} else {
			cloneTarget = new target.constructor()
		}
	}	
...
}
Copy the code

The Function and the Error

Function does not need to be copied, and Error does not need to be copied. Functions, which store abstract logic, are themselves independent of external state. For example, you can copy the 1 or 2 of 1+2, which are the exact values that occupy memory, but the function is function add(x, y) {return x + y}. Copying this logic doesn’t make much sense. Let’s take a look at what Lodash does:

const isFunc = typeof value === 'function'. if (tag == objectTag || tag == argsTag || (isFunc && ! object)) { result = (isFlat || isFunc) ? {} : initCloneObject(value) ... }else {
  if(isFunc || ! cloneableTags[tag]) {return object ? value : {}
  }
  ...
}
Copy the code

We can see that if the parent object is passed, the original function is returned; otherwise, the empty object is returned. It doesn’t copy functions. There are some articles on the web that actually copy functions, using commands and syntax that the eval and new Function standards don’t encourage.

Let’s just do what we did in Lodash.

const cloneDeep = function (target, cache = new WeakMap(), isFull = true.parent) {... elseif(type === functionTag) {
			cloneTarget = parent ? target : {}
		} else {
			cloneTarget = new target.constructor()
		}
	}	
...
}
Copy the code

Going back to Error, why would a copy of it make no sense? This is simply not possible…. But can the error object be copied? We could give it a try. Take a look at the following example:

Var err1 = new Error(' Error 1') object.keys (err1) // [] for(let x in err1) {console.log(x)} // undefined Object. GetOwnPropertyNames (err1) / / / 'stack', 'message' err1. Message / / '1' wrong err1. The stack / / 'Error: Error 1 at <anonymous>:1:12'Copy the code

We see that the err1 object has two non-enumerable properties, message is the argument passed in when it was created, and stack is the location of the heap where the error was created. What follows at is the error thrown at **< file name >: line number: column number **.

So, how do you copy? The Error constructor actually takes three arguments: message, file name, and line number. However, the latter two parameters are non-standard and are not currently supported by browsers, but even if they are supported, the information is incomplete without column numbers.

We can also create a new error object and pass the value of Message as an argument, overriding the stack property of the new object with the stack of the original object. This is actually feasible. That is, we throw an error, and both objects can jump to where the first object reported an error. However, they are different in themselves: they have different call chains.

At the very top of their call chain, they hold the location where the object was created, and this cannot be changed. So, this method appears to copy common properties and methods, but because they are created in different places (and can’t be the same).

It’s a little tricky to list the examples here, but you can experiment on your own if you’re interested.

Let’s take a look at how Lodash handles error objects:

. cloneableTags[errorTag] = cloneableTags[weakMapTag] =false. if (isFunc || ! cloneableTags[tag]) {return object ? value : {}
}
...
Copy the code

Same as with functions and WeakMaps. We just add it to the non-copiable array type we defined earlier.

const unableTypes = [
		weakMapTag, weakSetTag, errorTag
]
Copy the code

Promise

Copying a Promise instance is simpler because it stores the current state, and if nothing is done with the current state in the THEN method, it returns a new instance object that holds the current state. So just copy the Promise, call its then method, and do nothing.


const cloneDeep = function (target, cache = new WeakMap(), isFull = true.parent) {... elseif(type === promiseTag) {
			cloneTarget = target.then()
		} else {
			cloneTarget = new target.constructor()
		}
	}	
...
}
Copy the code

ArrayBuffer

TODO

Full version

Based on the various types mentioned above, we can put together a more comprehensive version that deals with clones of all the data types in ECMAScript.

Some common objects such as Window (‘[Object Window]’) and Document (‘[Object HTMLDocument]’) are built-in objects of the browser. They belong to BOM and DOM and are not built-in objects of ECMAScript. It is beyond the scope of this paper.

const hasOwnProperty = Object.prototype.hasOwnProperty
const getType = Object.prototype.toString


// Initialize an array object, including the special array returned by the re
function initCloneArray(array) {
	const { length } = array
	const result = new array.constructor(length)

	// Add properties assigned by `RegExp#exec`.
	if (length && typeof array[0= = ='string' && hasOwnProperty.call(array, 'index')) {
		result.index = array.index
		result.input = array.input
	}
	return result
}

// Get the key method
function getKeysFunc(isFull) {
	// Returns an array of enumerable Symbol keys on an object
	function getSymbols(object) {
		if (object == null) {
			return []
		}
		object = Object(object)
		return Object
			.getOwnPropertySymbols(object)
			.filter((symbol) = > Object.prototype.propertyIsEnumerable.call(object, symbol))
	}
	// Check whether the length property of the class array is valid
	function isLength(value) {
		return typeof value === 'number' &&
			value > - 1 && value % 1= = =0 && value <= Number.MAX_SAFE_INTEGER
	}
	// Check if it is a class array
	function isArrayLike(value) {
		returnvalue ! =null && typeofvalue ! = ='function' && isLength(value.length)
	}
	// Check whether the index of the class array is valid
	function isIndex(value, length) {
		const reIsUint = / ^ (? :0|[1-9]\d*)$/
		const type = typeof value
		length = length == null ? Number.MAX_SAFE_INTEGER : length

		return!!!!! length && (type ==='number'|| (type ! = ='symbol' && reIsUint.test(value))) &&
			(value > - 1 && value % 1= = =0 && value < length)
	}
	// Arguments
	function isArguments(value) {
		return typeof value === 'object'&& value ! = =null && getType.call(value) === '[object Arguments]'
	}
	// Returns an array of keys from the class array
	function arrayLikeKeys(value, inherited) {
		const isArr = Array.isArray(value)
		constisArg = ! isArr && isArguments(value)const skipIndexes = isArr || isArg
		const length = value.length
		const result = new Array(skipIndexes ? length : 0)
		let index = skipIndexes ? - 1 : length
		while (++index < length) {
			result[index] = `${index}`
		}
		for (const key in value) {
			if((inherited || hasOwnProperty.call(value, key)) && ! (skipIndexes && (// Safari 9 has enumerable `arguments.length` in strict mode.
					(key === 'length' ||
						// Skip index properties.
						isIndex(key, length))
				))) {
				result.push(key)
			}
		}
		return result
	}

	// Returns the enumerable property key on the object
	function keys(object) {
		return isArrayLike(object)
			? arrayLikeKeys(object)
			: Object.keys(Object(object))
	}

	// Returns an array of enumerable property keys + Symbol keys on the object
	function getAllKeys(object) {
		const result = keys(object)
		if (!Array.isArray(object)) { result.push(... getSymbols(object)) }return result
	}

	return isFull
		? getAllKeys
		: keys
}

// Copy the re object
function cloneRegExp(regexp) {
	const result = new regexp.constructor(regexp.source, regexp.flags)
	result.lastIndex = regexp.lastIndex
	return result
}

// Copy arguments objects

function cloneArguments(args) {
	const result = (function(){return arguments})()
	result.callee = args.callee
	result.length = args.length
	return result
}

const cloneDeep = function (target, isFull = true, cache = new WeakMap(), parent) {
	/ / value types
	const undefinedTag = '[object Undefined]'
	const nullTag = '[object Null]'
	const boolTag = '[object Boolean]'
	const numberTag = '[object Number]'
	const stringTag = '[object String]'
	const symbolTag = '[object Symbol]'
	const bigIntTag = '[object BigInt]'
	// Reference type
	const arrayTag = '[object Array]'
	const objectTag = '[object Object]'
	const setTag = '[object Set]'
	const mapTag = '[object Map]'
	const argTag = '[object Arguments]'
	const regexpTag = '[object RegExp]'
	const dateTag = '[object Date]'
	const funcTag = '[object Function]'
	const promiseTag = '[object Promise]'
	// Cannot copy the reference type
	const weakMapTag = '[object WeakMap]'
	const weakSetTag = '[object WeakSet]'
	const errorTag = '[object Error]'

	// The type of the object passed in
	const type = getType.call(target)

	// All supported types
	const allTypes = [
		undefinedTag, nullTag,boolTag, numberTag, stringTag, symbolTag, bigIntTag, arrayTag, objectTag,
		setTag, mapTag, argTag, regexpTag, dateTag, funcTag, promiseTag,
		weakMapTag, weakSetTag, errorTag
	]

	// If it is an unsupported type
	if(! allTypes.includes(type)) {console.warn(` does not support${type}Type, return {}. `)
		return{}}// Array of value types
	const valTypes = [
		undefinedTag, nullTag,boolTag, numberTag, stringTag,symbolTag, bigIntTag
	]
	// The value type returns directly
	if (valTypes.includes(type)) {
		return target
	}

	// forEach
	function forEach(array, iteratee) {
		let index = - 1
		const length = array.length

		while (++index < length) {
			// interrupt traversal
			if (iteratee(array[index], index, array) === false) {
				break}}return array
	}

	// Initialize the clone value
	let cloneTarget
	if (Array.isArray(target)) {
		cloneTarget = initCloneArray(target)
	} else {
		switch (type) {
			case argTag:
				cloneTarget = cloneArguments(target)
				break
			case regexpTag:
				cloneTarget = cloneRegExp(target)
				break
			case dateTag:
				cloneTarget = new target.constructor(+target)
				break
			case funcTag:
				cloneTarget = parent ? target : {}
				break
			case promiseTag:
				cloneTarget = target.then()
				break
			case weakMapTag:
			case weakSetTag:
			caseerrorTag: ! parent &&console.warn(`${type}Type cannot be copied, return {}. `)
				cloneTarget = parent ? target : {}
				break
			default:
				cloneTarget = new target.constructor()
		}
	}
	// Prevent circular references
	if (cache.has(target)) {
		return cache.get(target)
	}
	cache.set(target, cloneTarget)

	/ / clone set
	if (type === setTag) {
		target.forEach(value= > {
			cloneTarget.add(cloneDeep(value, cache))
		})
		return cloneTarget
	}
	/ / clone map
	if (type === mapTag) {
		target.forEach((value, key) = > {
			cloneTarget.set(key, cloneDeep(value, cache))
		})
		return cloneTarget
	}

	// Determine the method to obtain the key
	const keysFunc = getKeysFunc(isFull)

	// Clone Array and Object
	const keys = type === arrayTag ? undefined : keysFunc(target)
	forEach(keys || target, (value, key) => {
		if (keys) {
			key = value
		}
		cloneTarget[key] = cloneDeep(target[key], isFull, cache, target)
	})

	return cloneTarget
}
Copy the code

There may be some performance or writing problems in the above code that need to be optimized, which is enough for the implementation process of clone demonstration. If ECMAScript later adds new data types, you can extend this method.

Use of bitmasks

Bit arithmetic is rarely involved in daily development work and is highly discouraged ** due to its poor readability. But it is often used in very low-level frameworks because it is much more efficient than ordinary computing. In addition to computation, there are other uses, such as in LoDash, where bitmasks are used in several places. Imagine that you want to design a permission system. The distribution of permissions for a user can be expressed in simple JSON:

{
	"id": 1."RightA": true."RightB": false."RightC": false."RightD": true
}
Copy the code

As the system expands and has more and more permissions, the object will become larger and larger, which will reduce the efficiency of network transmission and memory usage. We can try to optimize this problem with bitmasks.

Let’s look at the table below, the binary representation of some decimal numbers:

The decimal system	binary
0	00000000
1	00000001
2	00000010
3	00000011
4	00000100
5	000000101
6	00000110
7	00000111
8	00001000
9	00001001

If we use 1 for true, 0 for false, and the binary position for permission, the previous JSON object can be simplified as follows:

{
	"id": 1."right": 9
}
Copy the code

This is the equivalent of storing information in a single number, and we’re now trying to extract information from that number:

const Right = 9
const RightA = 1
const RightB = 2
const RightC = 4
const RightD = 8hasRightA = !! (Right & RightA)// truehasRightB = !! (Right & RightB)// falsehasRightC = !! (Right & RightC)// falsehasRightD = !! (Right & RightD)// true
Copy the code

If we reset the permissions again, we need to piece together the information and return:

// Modified information
var change = {
	"id": 1."RightA": true."RightB": false."RightC": true."RightD": false
}

right = parseInt(1010.2) / / 10
Copy the code

In Lodash, bitmasks are used to pass multiple parameters:

/** Used to compose bitmasks for cloning. */
const CLONE_DEEP_FLAG = 1
const CLONE_FLAT_FLAG = 2
const CLONE_SYMBOLS_FLAG = 4

function baseClone(value, bitmask, customizer, key, object, stack) {
  let result
  const isDeep = bitmask & CLONE_DEEP_FLAG
  const isFlat = bitmask & CLONE_FLAT_FLAG
  const isFull = bitmask & CLONE_SYMBOLS_FLAG
  ...  
}  
Copy the code

reference

Github.com/lodash/loda…
Developer.mozilla.org/zh-CN/docs/…
es6.ruanyifeng.com/