Writing in the front

As a deep copy of the old growth story on the front end, I’m sure many front-end developers scoff at it.

“In the 21st century, you’re still talking about this old stuff? !”

Don’t worry about pulling out the knife 😅, the article stands in a qualified interviewer’s perspective to talk about a basic qualified deep copy needs to consider what boundary cases:

  • Copy date format processing.
  • Re object processing in copy.
  • A circular object reference in a copy.
  • Processing of the same reference object in the copy.
  • The original object prototype cannot be lost in the copy.
  • Property modifier of the original object in the copy.

The basic implementation of a full-fledged deep copy must include the above six points, so you can think about whether deep copy covers all the points in your mind.

After all, every seemingly simple thing actually hides a lot of things worth thinking about.

Shallow copy

I’m not going to talk too much about shallow copy, because all of the JS apis for copying are shallow copy.

  • Object.assign
  • Es6Extended operator
  • Array.prototype.slice.call/concat
  • .

Shallow copy method too many, this part of the API is not clear students need to refuel to supplement their basic knowledge.

Deep copy

Let’s forget about what we need to do at the beginning of the article and start with the easiest way to do it step by step.

JSON.stringify

Json.stringify is a familiar feature that converts javascript values to strings, making it very easy for me to implement deep copy:

Parse converts the string to Object using json.parse.

JSON.stringifyExisting problems

We use json.stringify to convert a slightly more complex object:

We can find that the original OBj object is converted by JSON apis, eat and key is Symbol[‘name’], the two attributes are lost, NaN is converted to NULL, the value of the re is changed to {}, and the value of date was originally of date type… This becomes a string.

Notice that the properties children1 and Children2 on the original OBj object refer to the same object, and before cloning they pointed to the same reference object address. CloneObj. Children1 === cloneObj. Children2 returns false on cloned cloneObj.

It seems that the JSON API is really buggy for deep copy

Performance problems

Let’s briefly summarize the current problems with json.stringify with deep copy:

  • After the copyDateThe type will become a stringstring.
  • After the copyRegExpThe type becomes an empty object.
  • Contained in the copy objectvalueforNaNThe value of delta will be zeronull.
  • The copied object will lose its contentsSymbolType property.
  • The copied object will be lostvalueforundefinedProperties.
  • The same reference in the copied object will become two completely different references, which just look the same.

There’s also Infinity and -infinity, which we don’t use very often. Those who are interested can try it on themselves.

We’ve covered most of the current problems with deep copy implementation of json.stringify in terms of performance.

Now let’s get to the deeper point, which requires you to think back to the first 6 points of the article.

Deeper problems

Json.stringify essentially implements a method of converting an object to a JSON string and then converting the string to a brand new object using json.parse.

There are two additional problems with the json.stringfiy procedure:

  • The inheritance relationship of the original object is not inherited
  • The property descriptor of the original object is missing

When a string is reconverted to an object, json.stringify’s regenerated object loses the inheritance and property descriptors of the original object, which is obviously the opposite of what we intended when we implemented deep copy.

Circular reference problem

Let’s talk about the so-called circular reference problem, which some of you probably don’t think much about when implementing deep copy.

Let’s start with a simple example of so-called circular references:

A circular reference simply means that an object has a property that points to an object that already exists in the object.

Here’s what happens when we use json. stringify to try cloning the obj object:

For reference type calls, json.stringify throws an error directly and cannot convert a looping reference object.

Deep copy over from a simple version

Let’s start by looking at the idea of implementing a simple version of deep copy.

I’m sure most of you are familiar with the deep-copy implementation of the so-called easy version:

// Simple deep copy
const isReferenceType = (value) = > typeof value === 'object'&& value ! = =null;

    function cloneDeep(obj) {
      if(! isReferenceType(obj)) {return obj
      }
      const cloneObj = Array.isArray(obj) ? [] : {}
      Object.keys(obj).forEach(key= > {
        const value = obj[key]
        // If the deep layer is still object recursive call
        const cloneValue = isReferenceType(value) ? cloneDeep(value) : value
        cloneObj[key] = cloneValue
      })
      return cloneObj
    }

    const object1 = {
      name: '19Qingfeng'.yellow: false.release: {
        custom: true.github: '19Qingfeng'}}const cloneValue = cloneDeep(object1)
    console.log(cloneValue, 'Cloned object')
    console.log(cloneValue === object1)
Copy the code

Above is a basic version of the deep copy implementation, which I believe is what most people call a deep copy implementation.

But before we mention the above mature deep copy should be considered to start, in fact he andJSON.stingifyIt’s just as simple.

Use Tyoe of to determine if it is a reference type and implement deep copy by iterating recursive calls using object. keys.

If your usual deep copy implementation isn’t that far off, I hope you stop sliding at this point and think about what needs to be implemented. You will find that he still can’t solve the “problems” I mentioned. Try to see if you have a solution to the problems mentioned above.

Implement deep copy from “problem”

Let’s start from the problems and sort out what solutions can be used to solve the problems raised at the beginning of the article:

Date/re formatting processing

  • Copy date format processing.
  • Re object processing in copy.

For the processing of dates and re objects in data formats, we can additionally determine whether the value passed in is of date/re type.

If so, return a new type of the corresponding regular/date type. We can use the constructor attribute on the prototype object to determine if this is a specific regular/date type:

We can use the constructor of js’s prototype object to determine if it is of the same type.

Of course you can also through the Object. The prototype. ToString. To determine the results of the call.

Missing stereotype/attribute modifiers

  • A copy ofObject.keysUnable to traverse thekeyforsymboltype
  • The original object prototype cannot be lost in the copy.
  • Property modifier of the original object in the copy.

For these two problems let’s take a look at the basic API of several JS

Reflect.ownKeys()

You can check out Reflect’s official profile here.

We use reflect.ownkeys () instead of object.keys () because reflect.ownkeys () has the following advantages:

  • It supports traversing non-enumerable objectsenumerable:falseProperties, andObject.keys()In no other.
  • It supports traversal of objectsSymbolType, andObject.keys()In no other.
  • He and the sameObject.keys()It only iterates through its own properties, and does not return properties on the prototype.

Object.getPrototypeOf()

The object.getProtoTypeof () method returns the Prototype of the specified Object (the value of the internal [[Prototype]] property).

We can use it to obtain the original prototype Object of the Object, which can be combined with the Object. Create method to easily achieve the corresponding, easy to realize the inheritance relationship in the deep copy.

Object.getOwnPropertyDescriptors()

Object. GetOwnPropertyDescriptors () method returns the specified Object on a has its own corresponding attribute descriptor. (Owned properties are those that are given to the object directly, without the need to look it up on the stereotype chain.)

Let’s take a look at the API return value, pay attention to distinguish between him and the Object. The getOwnPropertyDescriptors ().

Object. The create (proto, [propertiesObject])

Object.create supports passing in two arguments to return a brand new Object.

The first argument supports passing in an object and pointing to it as the __proto__ of the newly created object, which is the prototype object of the newly created object.

The second argument supports passing in an object, this object

As mentioned above, we have been able to pass:

  • getPrototypeOf()Gets the prototype object of the original object.
  • getOwnPropertyDescriptors()Gets the property descriptor for all properties of the original object.

We can implement the deep copy effect of inheritance and property characters by simply passing the return values of the two methods through object.create.

Solve the circular reference problem

We can store an additional variable in the deepClone method, which is a hash table that holds every object we recursively copy.

Therefore, the next time we encounter the same reference address object, we can directly retrieve the same reference address from the saved hash table and assign the value without recursing the same object again.

In this way, the stack burst caused by circular references can be avoided, and the same reference problem can be solved.

But there is a little tip that should be noted here. In JS, we usually use object to store corresponding key and value structures. But the key that we need to store here needs to be the old reference object, which is an object.

It’s not hard to imagine that supporting the Map structure in ES6 would be our best choice, but one thing to consider at this point is that reference types to maps actually cause reference counting. The effect we want is that the hash object should not cause reference calculations to affect the garbage collection mechanism, and the reference values in the hash will also be cleared when we erase the saved object.

At this point, the best choice for this hash object must be to use a WeakMap object for storage.

You can check out the description of WeakMap here.

In contrast, the native WeakMap holds a “weak reference” to each key object, meaning garbage collection works correctly when no other reference exists. The structure of the native WeakMap is special and efficient, and the key it uses for mapping is valid only if it is not reclaimed.

If you use maps alone, it is very easy to leak memory and lose unnecessary performance when copying large amounts of data in a loop/same reference.

With that said, let’s look at the implementation of the final version:

Final deep copy

/* Implement deep copy 1. Judge circular reference 2. Judge regular object 3. Judge date object 4. 6. Consider the property modifier */
function cloneDeep(value, map = new WeakMap(a)) {
  if (value.constructor === Date) {
    return new RegExp(value)
  }
  if (value.constructor === RegExp) {
    return new RegExp(value)
  }
  // If value is a common type
  if (typeofvalue ! = ='object' || value === null) {
    return value
  }
  // Create a new object that inherits the object's prototype
  const prototype = Object.getPrototypeOf(value)
  // The property descriptor of the original object cannot be lost when considering copying
  const description = Object.getOwnPropertyDescriptors(value)
  // Create a new empty object that inherits the original object prototype and has the corresponding descriptor
  const object = Object.create(prototype, description)
  // Reflect. OwnKeys iterate to get its own non-enumerable and Symbol properties
  map.set(value, object)
  Reflect.ownKeys(value).forEach(key= > {
    // Key is a common type
    if (typeofkey ! == object || key ===null) {
      // Overwrite directly
      object[key] = value[key]
    } else {
      // The key to solving the circular reference is to store every object in weakMap because weakMap is a weak reference
      // Every time you enter an object, put the object in weakMap first. After that, if there is any reference to the object, you can directly take it out of WeakMap without going through again to cause stack explosion
      // Similarly, if the same reference is used, in order to ensure the same reference address, weakMap can be directly taken out to ensure the same reference
      // If the same reference exists, return the reference directly
      const mapValue = map.get(value)
      mapValue ? (object[key] = map.get(value)) : (object[key] = cloneDeep(value[key]))
    }
  })
  return object
}
Copy the code

There are detailed comments for each step in the code, and implementing a deep copy itself is not that difficult, but there are many boundary cases to be aware of.

Let’s write a Demo to verify the results of this method:

let obj = {
  age: 23.name: '19Qingfeng'.boolean: true.empty: undefined.nul: null.customObj: { name: '19Qingfeng'.github:'https://github.com/19Qingfeng' },
  customArr: [0.1.2].customFn: () = > console.log('19Qingfeng'),
  date: new Date(100),
  reg: new RegExp('/19Qingfeng/ig'),Symbol('hello')]: 'Welcome follow my github! '};// Define non-enumerable attributes
Object.defineProperty(obj, 'innumerable', {
  enumerable: false.value: 'Non-enumerable properties'}); obj =Object.create(obj, Object.getOwnPropertyDescriptors(obj))
obj.loop = obj    // Set loop to a property referenced in a loop
let cloneObj = cloneDeep(obj)
cloneObj.customArr.push(4)


console.log(cloneDeep(obj))

console.log(cloneDeep(obj) === obj)
// Note that enumerating properties cannot be printed. We can verify this with reflect.ownkeys
Reflect.ownKeys(cloneDeep(obj)).forEach(key= > console.log(key))
Copy the code

You’re done, and a basic deep copy is now fully implemented!

Write in the last

There are many ways to write deep copy, but the principles are pretty much the same.

Just to give you an idea, true deep copy is compatible with too many boundary cases. For example, if we copy the code in the Map/Set type article, it will not be compatible, but for learning, I think the final deep copy is enough for the interviewer to examine your knowledge system and breadth of thinking.

If you are interested, you can improve the code in private. Don’t ask about deep copy and tell others that you only know the cloneDeep method in LoDash