In-depth analysis of Vue source code - to implement diff algorithm with me!

This section, is still an in-depth analysis of Vue source code series, the last few sections introduced Virtual DOM is Vue in the rendering mechanism to do optimization, and the core of rendering lies in data changes, how to update nodes efficiently, this is the DIFF algorithm. Because the source code on the DIFF algorithm part of the process is complex, directly analyze each process is not easy to understand, so this section we change a way of thinking, reference source code to manually achieve a simple version of the DIFF algorithm.

As mentioned before, Vue introduces the concept of Virtual DOM in the optimization of rendering mechanism, and uses Virtual DOM to describe a real DOM. Essentially, it sets up a buffer layer between JS and the real DOM. When we render through a large number of JS operations and reflect the final results to the browser, Virtual DOM can combine multiple changes into a batch operation, so as to reduce the number of DOM rearrangement, and thus shorten the time spent in generating rendering trees and rendering nodes, so as to achieve the purpose of rendering optimization. In the previous section, we briefly introduced the concept of Vnode in Vue, and the process from creating a Vnode to rendering a Vnode to the actual DOM. If you forget the process, refer to the previous section for analysis.

** The process from the Render function to creating the virtual DOM to rendering real nodes is complete and easy to understand. However, the core of introducing the virtual DOM is not here, but how to optimize the process of data changes to view updates when data changes. This process, also known as the DIff algorithm, is at the heart of Vnode’s updated view. ** Now follow me to implement a simple version of the DIff algorithm

8.1 Creating a Basic Class

There are a lot of basic types of decisions to make during code writing, and the first step is to encapsulate these methods.

class Util {
  constructor() {}
  // Check the base type
  _isPrimitive(value) {
    return (typeof value === 'string' || typeof value === 'number' || typeof value === 'symbol' || typeof value === 'boolean')}// Check that the value is not null
  _isDef(v) {
    returnv ! = =undefined&& v ! = =null}}// The use of utility classes
const util = new Util()
Copy the code

8.2 create Vnode

Vnode this class in the previous chapter has analyzed the source code, essentially is to use an object to describe a real DOM element, a simple version of the focus is on the element tag tag, element attribute set data, children of the element,text is the text node of the element, the simple description class is as follows:

class VNode {
  constructor(tag, data, children) {
    this.tag = tag;
    this.data = data;
    this.children = children;
    this.elm = ' '
    // The text attribute is used to indicate that a Vnode has no other children and only plain text
    this.text = util._isPrimitive(this.children) ? this.children : ' '}}Copy the code

8.3 Simulate the rendering process

Next we need to create another class that simulates converting the Render function to a Vnode and rendering the Vnode as a real DOM, We define this class as Vn, which has two basic methods, createVnode and createElement, to create a virtual Vnode and a real DOM, respectively.

8.3.1 createVnode

CreateVnode simulates the Render function in Vue to convert data into a virtual Vnode.

// index.html

<script src="diff.js">
<script>

/ / create a Vnode

let createVnode = function() {
  let _c = vn.createVnode;
  return _c('div', { attrs: { id: 'test' } }, arr.map(a= > _c(a.tag, {}, a.text)))
}

// Element content structure
let arr = 
  [{
    tag: 'i'.text: 2
  }, {
    tag: 'span'.text: 3
  }, {
    tag: 'strong'.text: 4
  }]
</script>



// diff.js
(function(global) {
  class Vn {
    constructor() {}
    // Create a virtual Vnode
    createVnode(tag, data, children) {
      return new VNode(tag, data, children)
    }
  }
  global.vn = new Vn()
}(this))

Copy the code

This is a complete Vnode object that can be used to simply describe a DOM node, and createElement is the process of mapping this object to the actual node. In the end, this is what we want.

The Vnode object

The renderings

8.3.2 createElement method

The process of rendering the real DOM is to iterate over the Vnode object and recursively create the real node. This is not the focus of this article, so we can implement it roughly.

class Vn {
  createElement(vnode, options) {
      let el = options.el;
      if(! el || !document.querySelector(el)) return console.error('Root node cannot be found')
      let _createElement = vnode= > {
        const { tag, data, children } = vnode;
        const ele = document.createElement(tag);
        // Add attributes
        this.setAttr(ele, data);
        // Simple text node, just create a text node
        if (util._isPrimitive(children)) {
          const testEle = document.createTextNode(children);
          ele.appendChild(testEle)
        } else {
        // Complex children need to iterate over the children to create the node recursively.
          children.map(c= > ele.appendChild(_createElement(c)))
        }
        return ele
      }
      document.querySelector(el).appendChild(_createElement(vnode))
    }
}
Copy the code

8.3.3 are included setAttr

SetAttr is a method of setting attributes for nodes, using the DOM native setAttribute to setAttribute values for each node.

class Vn {
  setAttr(el, data) {
    if(! el)return
    const attrs = data.attrs;
    if(! attrs)return;
    Object.keys(attrs).forEach(a= >{ el.setAttribute(a, attrs[a]); }}})Copy the code

So far a simple ** data -> Virtual DOM => real DOM** model has been built successfully, which is also the basis for data change, comparison and update.

8.4 Implementation of diFF algorithm

The process of updating components begins with responsive data changes. Frequent changes of data rendered directly to the real DOM will result in the redrawing and rearrangement of the entire DOM tree, which is extremely performance consuming. How to optimize the rendering process, the Vue source is given in the two concrete train of thought, one of which is mentioned in the reactive system is introduced in this paper to push several revisions to a queue, the next tick to execute the view update, another is next to the diff algorithm is introduced, will need to modify the data comparison, and only render necessary DOM.

The change of data will eventually lead to the change of nodes, so the core of diff algorithm is to find the nodes that need to be updated under the premise of as little change as possible, and directly call the native DOM method to modify the view. Both the real DOM and the Virtual DOM created above can be understood as a DOM tree. When the algorithm compares different nodes, it only compares nodes of the same layer rather than across layers, which greatly reduces the complexity of the algorithm.

8.4.1 diffVnode

Based on the previous example, we implement an idea, and after 1 second the data changes.

// index.html
setTimeout(function() {
  arr = [{
    tag: 'span'.text: 1}, {tag: 'strong'.text: 2}, {tag: 'i'.text: 3}, {tag: 'i'.text: 4
  }]
  // newVnode indicates the newVnode tree after the change
  const newVnode = createVnode();
  // diffVnode compares the old and new Vnode trees and completes the view update
  vn.diffVnode(newVnode, preVnode);
})
Copy the code

The diffVnode logic compares the difference between the old and new nodes and completes the view rendering update

class Vn ··· diffVnode(nVnode, oVnode) {if (!this._sameVnode(nVnode, oVnode)) {
      // Update the root node and all its children directly
      return* * *}this.generateElm(vonde);
    this.patchVnode(nVnode, oVnode); }}Copy the code

8.4.2 _sameVnode

The comparison between the old and new nodes is the first step of the algorithm. If the root node of the old and new nodes is not the same node, the node is directly replaced. This follows the principle mentioned above and only compares nodes of the same layer. If nodes are inconsistent, the old node is replaced directly with the new node and its children. For the sake of understanding, we assume that the determination of identical nodes is whether the tag tag is consistent (the actual source code is more complicated).

class Vn {
  _sameVnode(n, o) {
    returnn.tag === o.tag; }}Copy the code

8.4.3 generateElm

The purpose of generateElm is to track the actual real nodes of each node, so that real DOM nodes can be updated in real time after virtual nodes are compared. The Vue source code does this differently, but that is not the point of analyzing diff.

class Vn {
  generateElm(vnode) {
    const traverseTree = (v, parentEl) = > {
      let children = v.children;
      if(Array.isArray(children)) {
        children.forEach((c, i) = > {
          c.elm = parentEl.childNodes[i];
          traverseTree(c, c.elm)
        })
      }
    }
    traverseTree(vnode, this.el); }}Copy the code

After executing the generateElm method, we can trace the actual node information of each Virtual DOM in the Vnode of the old node.

8.4.4 patchVnode

PatchVnode is the core method to compare old and new VNodes. The logic of comparison is as follows.

The nodes are the same, and the node has no child nodes except the text node. In this case, replace the text content directly.
If the new node has no children and the old node has children, delete all children of the old node.
If the old node has no children and the new node has children, the old node is updated with all the new children.
Both old and new have child nodes. Compares the content of child nodes to perform operations.

The code logic is as follows:

class Vn {
  patchVnode(nVnode, oVnode) {
    
    if(nVnode.text && nVnode.text ! == oVnode) {// The current real DOM element
      let ele = oVnode.elm
      // The child nodes are text nodes
      ele.textContent = nVnode.text;
    } else {
      const oldCh = oVnode.children;
      const newCh = nVnode.children;
      // Both old and new nodes exist. Contrast child node
      if (util._isDef(oldCh) && util._isDef(newCh)) {
        this.updateChildren(ele, newCh, oldCh)
      } else if (util._isDef(oldCh)) {
        // The new node has no children
      } else {
        // The old node has no children}}}}Copy the code

In the example above, in the patchVnode process, both the old and new child nodes exist, so the updateChildren branch is used.

8.4.5 updateChildren

We can clearly see the subtlety of diff algorithm by analyzing the comparison of child nodes in the form of text and drawings.

The general logic is:

The starting position of the old node isoldStartIndexAnd the ending position isoldEndIndex, the starting position of the new node isnewStartIndexAnd the ending position isnewEndIndex.
The old and newchildrenCompare the elements at the starting position ofnewStartVnode, oldStartVnode; newEndVnode, oldEndVnode;newEndVnode, oldStartVnode;newStartIndex, oldEndIndex
newStartVnode, oldStartVnodeIf the nodes are the same, perform this operation oncepatchVnodeThe process of recursively comparing the corresponding child nodes and replacing the nodes.OldStartIndex, newStartIndexIt’s like moving one to the right.
newEndVnode, oldEndVnodeIf the nodes are the same, perform this operation oncepatchVnodeProcedure, recursively compare the corresponding child nodes, and replace nodes.OldEndIndex, newEndIndexIt’s like moving one to the left.
newEndVnode, oldStartVnodeIf the nodes are the same, perform this operation oncepatchVnodeProcess and will the oldoldStartVnodeMove to the tail,oldStartIndexMove one to the right,newEndIndexMove one to the left.
newStartIndex, oldEndIndexIf the nodes are the same, perform this operation oncepatchVnodeProcess and will the oldoldEndVnodeMove to the head,oldEndIndexOne to the left,newStartIndexMove one to the right.
If the four combinations are different, all the children of the old node will be searched and the old node will be foundnewStartVnodeperformpatchVnodeProcess.
The process of constant comparison makesoldStartIndexThe loomingoldEndIndex.newStartIndexThe loomingnewEndIndex. whenoldEndIndex <= oldStartIndexNote The existing nodes have been traversed. In this case, you only need to add new nodes in batches. whennewEndIndex <= newStartIndexNote Old nodes still exist. You only need to delete them in batches.

Combined with the previous example:

The first step:

The second step:

Step 3:

Step 3:

Step 4:

Following these steps, the code is implemented as follows:

class Vn {
  updateChildren(el, newCh, oldCh) {
    // New children start flag
    let newStartIndex = 0;
    // The old children start flag
    let oldStartIndex = 0;
    // New children end flag
    let newEndIndex = newCh.length - 1;
    // Old children end flag
    let oldEndIndex = oldCh.length - 1;
    let oldKeyToId;
    let idxInOld;
    let newStartVnode = newCh[newStartIndex];
    let oldStartVnode = oldCh[oldStartIndex];
    let newEndVnode = newCh[newEndIndex];
    let oldEndVnode = oldCh[oldEndIndex];
    // Iterate over the end condition
    while (newStartIndex <= newEndIndex && oldStartIndex <= oldEndIndex) {
      // The new children start node is the same as the old one
      if (this._sameVnode(newStartVnode, oldStartVnode)) {
        this.patchVnode(newCh[newStartIndex], oldCh[oldStartIndex]);
        newStartVnode = newCh[++newStartIndex];
        oldStartVnode = oldCh[++oldStartIndex]
      } else if (this._sameVnode(newEndVnode, oldEndVnode)) {
      // The new childre end node is the same as the old one
        this.patchVnode(newCh[newEndIndex], oldCh[oldEndIndex])
        oldEndVnode = oldCh[--oldEndIndex];
        newEndVnode = newCh[--newEndIndex]
      } else if (this._sameVnode(newEndVnode, oldStartVnode)) {
      // The new childre end node is the same as the old start node
        this.patchVnode(newCh[newEndIndex], oldCh[oldStartIndex])
        // The old oldStartVnode is moved to the end
        el.insertBefore(oldCh[oldStartIndex].elm, null);
        oldStartVnode = oldCh[++oldStartIndex];
        newEndVnode = newCh[--newEndIndex];
      } else if (this._sameVnode(newStartVnode, oldEndVnode)) {
        // The new children start node is the same as the old end node
        this.patchVnode(newCh[newStartIndex], oldCh[oldEndIndex]);
        el.insertBefore(oldCh[oldEndIndex].elm, oldCh[oldStartIndex].elm);
        oldEndVnode = oldCh[--oldEndIndex];
        newStartVnode = newCh[++newStartIndex];
      } else {
        // Find the same vNode in the new node as in the old node
        this.findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx); }}// There are more new nodes than old nodes
    if(oldEndIndex <= oldStartIndex) {
      for (let i = newStartIndex; i <= newEndIndex; i++) {
        // Add nodes in batches
        this.createElm(oldCh[oldEndIndex].elm, newCh[i])
      }
    }
  }

  createElm(el, vnode) {
    let tag = vnode.tag;
    const ele = document.createElement(tag);
    this._setAttrs(ele, vnode.data);
    const testEle = document.createTextNode(vnode.children);
    ele.appendChild(testEle)
    el.parentNode.insertBefore(ele, el.nextSibling)
  }

  // Find the matching value
  findIdxInOld(newStartVnode, oldCh, start, end) {
    for (var i = start; i < end; i++) {
      var c = oldCh[i];
      if (util.isDef(c) && this.sameVnode(newStartVnode, c)) { return i }
    }
  }
}
Copy the code

8.5 Diff algorithm optimization

There is a branch in front, and when none of the four comparison nodes can find a match, findIdxInOld is called to find the node that matches the old node and the new comparison node. Node search is slow at large orders of magnitude. Look at the source code of Vue, found that it has been optimized in this link, that is, we are often asked to add the unique attribute key when compiling the list, with this unique flag bit, we can establish a simple dictionary query of the old node, as long as there is a key value can be convenient to search to meet the requirements of the old node. Modify code:

class Vn {updateChildren() {···}else {
      // Find the same vNode in the new node as in the old node
      if(! oldKeyToId) oldKeyToId =this.createKeyMap(oldCh, oldStartIndex, oldEndIndex);
      idxInOld = util._isDef(newStartVnode.key) ? oldKeyToId[newStartVnode.key] : this.findIdxInOld(newStartVnode, oldCh, oldStartIndex, oldEndIndex);
      // Subsequent operations}}// Create a dictionary
  createKeyMap(oldCh, start, old) {
    const map = {};
    for(let i = start; i < old; i++) {
      if(oldCh.key) map[key] = i;
    }
    returnmap; }}Copy the code

8.6 Problem Thinking

Finally, we asked ourselves if Virtual DOM’s redraw performance is really better than innerHTML alone. It’s not, the authors explained

innerHTML: render html string O(template size) +Recreate allDOMThe elementO(DOM size)

Virtual DOM: render Virtual DOM + diff O(template size) +The necessaryDOMupdateO(DOM change)

Virtual DOM render + diffObviously slower than rendering HTML strings, but! It is still pure JS level computation, compared to laterDOMOperationally, it’s still much cheaper. As you can see,innerHTMLStudent: The total amount of computation is whateverjsCalculation orDOMIt all depends on the size of the whole interface, butVirtual DOMOf the number of calculations, onlyjsCalculations are related to interface size, and DOM manipulation is related to how much data changes.

An in-depth analysis of Vue source code – option merge (1)
An in-depth analysis of Vue source code – option merge (2)
In-depth analysis of Vue source code – data agents, associated child and parent components
In-depth analysis of Vue source code – instance mount, compile process
In-depth analysis of Vue source code – complete rendering process
In-depth analysis of Vue source code – component foundation
In-depth analysis of Vue source code – components advanced
An in-depth analysis of Vue source code – Responsive System Building (PART 1)
In – Depth Analysis of Vue source code – Responsive System Building (Middle)
An in-depth analysis of Vue source code – Responsive System Building (Part 2)
In-depth analysis of Vue source code – to implement diff algorithm with me!
In-depth analysis of Vue source code – reveal Vue event mechanism
In-depth analysis of Vue source code – Vue slot, you want to know all here!
In-depth analysis of Vue source code – Do you understand the SYNTAX of V-Model sugar?
In-depth analysis of Vue source – Vue dynamic component concept, you will be confused?
Thoroughly understand the keep-alive magic in Vue (part 1)
Thoroughly understand the keep-alive magic in Vue (2)

In-depth analysis of Vue source code – to implement diff algorithm with me!