What is the virtual DOM

Simply put, the virtual DOM refers to the use of JS objects to describe a DOM node.

<div class="a" id="b"> I am content </div> {tag:'div'.// Element tag
  attrs: {/ / property
    class:'a'.id:'b'
  },
  text:'I am content'.// Text content
  children: []/ / child elements
}
Copy the code

Why use the virtual DOM?

Due to browser standards, real DOM objects themselves are designed to be very complex, and since the JS engine, DOM engine, and layout engine share a single main thread of the browser, using THE DOM multiple times with JS can cause frequent context switches, leading to a dramatic performance degradation (in some tests). So the real problem with the virtual DOM is to reduce unnecessary DOM API calls and use dom-diff to compare the state of the data before and after changes to figure out where updates need to be made.

It is not necessarily more efficient to use the virtual DOM for a single DOM API operation, but the framework provides a general solution with acceptable performance. Evan You

Vue’s virtual DOM

Through the VNode class in Vue, we can instantiate different types of virtual DOM nodes, and a virtual DOM tree is composed of vNodes.

The implementation of Vue virtual DOM is based on a virtual DOM librarysnabbdom

// Source: SRC /core/vdom/vnode.js

export default class VNode {
  constructor (tag? : string, data? : VNodeData, children? :?Array<VNode>, text? : string, elm? : Node, context? : Component, componentOptions? : VNodeComponentOptions, asyncFactory? :Function
  ) {
    this.tag = tag                                /* Label name of the current node */
    this.data = data        /* The object corresponding to the current node, which contains specific data information, is a VNodeData type, you can refer to the VNodeData type data information */
    this.children = children  /* The child of the current node is an array */
    this.text = text     /* The text of the current node */
    this.elm = elm       /* The actual DOM node corresponding to the current virtual node */
    this.ns = undefined            /* Namespace of the current node */
    this.context = context          /* Vue instance corresponding to the current component node */
    this.fnContext = undefined       /* The Vue instance of the functional component */
    this.fnOptions = undefined
    this.fnScopeId = undefined
    this.key = data && data.key           /* The key attribute of the node, which is used as the node's identifier, is used to optimize */
    this.componentOptions = componentOptions   /* The component's option */
    this.componentInstance = undefined       /* The instance of the component corresponding to the current node */
    this.parent = undefined           /* The parent of the current node */
    this.raw = false         InnerHTML is true, and textContent is false*/
    this.isStatic = false         /* Static node flag */
    this.isRootInsert = true      /* Whether to insert as the heel node */
    this.isComment = false             /* Is a comment node */
    this.isCloned = false           /* Whether the node is a clone */
    this.isOnce = false                /* Whether there is a v-once instruction */
    this.asyncFactory = asyncFactory
    this.asyncMeta = undefined
    this.isAsyncPlaceholder = false
  }

  get child (): Component | void {
    return this.componentInstance
  }
}
Copy the code

The VNode class contains the necessary attributes to describe a node, such as tag, text, children, elm, and elm.

Before rendering the view, we compile the written Template template into VNode and cache it. When the page needs to be rendered again after data changes, we compare the VNode generated after data changes with the VNode cached before to find out the difference. Then the real DOM nodes corresponding to the different VNodes are the nodes that need to be re-rendered. Finally, the real DOM nodes are created according to the different Vnodes and then inserted into the view to finally complete a view update.

The next part of the discussion, of course, is how to find the difference between NewVNode after the data change and OldVnode before the change.

DOM-Diff

The DOM-diff in Vue is called the patch process. From the perspective of semantics, patch means to patch the real DOM by comparing the changes of the old and new VNodes and comparing the old and new Ones with the new newVNode as the benchmark to update the real DOM and make it become the real DOM mapped by newVNode. Through the patch function as the entry point, there are no more than three actions to be performed: creating nodes, deleting nodes, and updating nodes.

Create a node

There are three types of nodes that can be inserted into the DOM: element nodes, text nodes, and comment nodes, for which Vue also encapsulates different creation methods.

// SRC /core/vdom/patch.js
function createElm (vnode, parentElm, refElm) {
    const data = vnode.data
    const children = vnode.children
    const tag = vnode.tag
    if (isDef(tag)) {
      	vnode.elm = nodeOps.createElement(tag, vnode)   // Create the element node
        createChildren(vnode, children, insertedVnodeQueue) // Create a child node of the element node
        insert(parentElm, vnode.elm, refElm)       // Insert into the DOM
    } else if (isTrue(vnode.isComment)) {
      vnode.elm = nodeOps.createComment(vnode.text)  // Create a comment node
      insert(parentElm, vnode.elm, refElm)           // Insert into the DOM
    } else {
      vnode.elm = nodeOps.createTextNode(vnode.text)  // Create a text node
      insert(parentElm, vnode.elm, refElm)           // Insert into the DOM}}Copy the code

In the codenodeOpsVue encapsulates all node operations for cross-platform compatibility, for examplenodeOps.createTextNode()Equivalent on the browser sidedocument.createTextNode()

Remove nodes

function removeNode (el) {
    const parent = nodeOps.parentNode(el)  // Get the parent node
    if (isDef(parent)) {
      nodeOps.removeChild(parent, el)  // Call the removeChild method on the parent node}}Copy the code

Update the node

function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
  // Are vNodes exactly the same as oldvNodes? If so, exit the program
  if (oldVnode === vnode) {
    return
  }
  /** * VNode's ELM attributes, oldVnode's ELM attributes, and ELM all point to the same memory address * so changing elm will change all */
  const elm = vnode.elm = oldVnode.elm

  // Are both vNodes and oldvNodes static? If so, exit the program
  if (isTrue(vnode.isStatic) &&
    isTrue(oldVnode.isStatic) &&
    vnode.key === oldVnode.key &&
    (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
  ) {
    return
  }

  const oldCh = oldVnode.children
  const ch = vnode.children
  // VNode has a text attribute? If no:
  if (isUndef(vnode.text)) {
    // Do the children of vNode and oldVnode exist?
    if (isDef(oldCh) && isDef(ch)) {
      // If they both exist, check whether the child nodes are the same. If they are different, update the child nodes
      if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) }// If only vNode child nodes exist
    else if (isDef(ch)) {
      /** * Does oldVnode have text? * If not, add vNode's children to the real DOM * if not, empty the text in the DOM and add vNode's children to the real DOM */
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, ' ')
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
    }
    // If only children of oldNode exist
    else if (isDef(oldCh)) {
      // Clear the child nodes in the DOM
      removeVnodes(elm, oldCh, 0, oldCh.length - 1)}// If both vnode and oldNode have no child nodes, oldNode has text
    else if (isDef(oldVnode.text)) {
      // Empty the oldNode text
      nodeOps.setTextContent(elm, ' ')}// If a vNode has neither text nor child nodes, empty whatever is in the corresponding oldNode
  }
  // If yes, is the text attribute of vNode the same as the text attribute of oldVnode?
  else if(oldVnode.text ! == vnode.text) {// If not: replace the real DOM text with the vNode text
    nodeOps.setTextContent(elm, vnode.text)
  }
}
Copy the code

A static node is a node whose content is fixed and independent of Vue Data, for example

<p>I am the words that will not change</p>
Copy the code

The following sections focus on the updateChildren method for updating child nodes.

Update child nodes

// Update the child node recursively if the old and new nodes are the same...
  function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
    // oldChildren starts indexing
    let oldStartIdx = 0
    // oldChildren end the index
    let oldEndIdx = oldCh.length - 1
    // Record the current oldChildren of all unprocessed first ones
    let oldStartVnode = oldCh[0] 
    // Records the last of the current oldChildren that was not processed
    let oldEndVnode = oldCh[oldEndIdx]   
    
    // newChildren starts indexing
    let newStartIdx = 0
    // newChildren ends the index
    let newEndIdx = newCh.length - 1
    // Record all unprocessed first entries of the current newChildren
    let newStartVnode = newCh[0]
    // Records the last unprocessed newChildren
    let newEndVnode = newCh[newEndIdx]  

    let oldKeyToIdx, idxInOld, vnodeToMove, refElm

    // Related to transition, can be ignored
    constcanMove = ! removeOnly// Non-production environments check newCh for duplicate keys
    if(process.env.NODE_ENV ! = ='production') {
      checkDuplicateKeys(newCh)
    }
    // Note that the end index is already determined, so subsequent changes to the oldCh array do not affect pointer traversal
    // Start the node comparison with "head", "tail", "head to tail", "tail to head"
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
        oldStartVnode = oldCh[++oldStartIdx] 
      } else if (isUndef(oldEndVnode)) {
        oldEndVnode = oldCh[--oldEndIdx]
        // The oldVnode is undefined. Why undefined? It will be explained below
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        // If the new node is the same as the old node, the patchVnode is recursively called to update the child nodes of both nodes
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // Similar to above
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) {
        // If the new node is the same as the old node, patch the two nodes first, and then move the old node to after all unprocessed nodes in oldChilren, i.e. before the next node of the current oldEndVnode
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
        canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
        oldStartVnode = oldCh[++oldStartIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldEndVnode, newStartVnode)) {
        // If the new node is the same as the old node, patch the two nodes first, and then move the old node to the front of all unprocessed nodes in oldChilren
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        OldKeyToIdx :{key:index} oldKeyToIdx:{key:index} oldKeyToIdx:{key:index} oldKeyToIdx:{key:index} You have to loop violence to find the index in oldCh */
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
        // If the child of the current loop in newChildren cannot be found in oldChildren
        if (isUndef(idxInOld)) { // New element
          // Add the node and insert it into the appropriate position
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        } else {
          // If a child node in newChildren of the current loop is found in oldChildren
          vnodeToMove = oldCh[idxInOld]
          // If two nodes are the same
          if (sameVnode(vnodeToMove, newStartVnode)) {
            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)
            /** * set oldCh[idxInOld] to undefined * because this non-special update will only move newStartIdx * so in subsequent loops with possible oldIdx moves, The oldCh node may also be traversed * when traversed, it will enter the judgment at the beginning of the code because it is marked as moved, i.e. undefined
            oldCh[idxInOld] = undefined
            // canmove indicates whether the node needs to be moved. If true, the node needs to be moved. If false, the node does not need to be moved
            canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
          } else {
            // same key but different element. treat as new element
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
          }
        }
        newStartVnode = newCh[++newStartIdx]
      }
    }
    if (oldStartIdx > oldEndIdx) {
      /** * If oldChildren completes before newChildren, * then the remaining nodes in newChildren are new nodes. */ Insert all nodes between [newStartIdx, newEndIdx] into the DOM
      refElm = isUndef(newCh[newEndIdx + 1])?null : newCh[newEndIdx + 1].elm
      addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
    } else if (newStartIdx > newEndIdx) {
      /** * If newChildren completes before oldChildren, then the remaining nodes in oldChildren are the ones that need to be deleted. */ Delete all nodes between [oldStartIdx, oldEndIdx]
      removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
  }
Copy the code

The sameVnode function is also attached:

function sameVnode (a, b) {
  return (
    a.key === b.key && (
      (
        a.tag === b.tag &&
        a.isComment === b.isComment &&
        isDef(a.data) === isDef(b.data) &&
        sameInputType(a, b)
      ) || (
        isTrue(a.isAsyncPlaceholder) &&
        a.asyncFactory === b.asyncFactory &&
        isUndef(b.asyncFactory.error)
      )
    )
  )
}
Copy the code

The main problem to be solved is how to quickly locate the old node which is the same as the new node (or make sure there is no such old node). If it is a double cycle of violence every time, the average time complexity is O(n^2) order of magnitude. But according to the actual frequent operation of front end changes the DOM, increased the end combination, through the time complexity of O (1) rapid locking changes related to the head to tail, and constantly update the index by means of double needle clamp force, records need mobile node is moving position and in an array traversal is completed, obtain pure need to delete or the new child node. When the head-to-tail comparison cannot solve the problem, the bottom-saving strategy is to use key to help lock the position of the new child node with someKey and the old word child node with the same key in the parent node, then compare sameVnode, and set the current position to undefined after the parent node needs to be moved to avoid the second search. If the new node does not have a key or the old node does not have a key, the final bottom-of-the-pocket strategy is triggered, that is, the oldCh violence is traversed to see if the same node exists. NewCh did not change in the whole process. Instead, the nodes of newCh were constantly searched for the same nodes in oldCh, updated and moved to achieve the effect of patch.

A few examples

Characteristics of Vue2 Diff algorithm

The DOM-Diff algorithm of Vue2 (snabbDOM algorithm) and the Diff algorithm of React have the same thing in that they both think that there is very little movement across layers, so they only compare things at the same level without taking the changes across layers into account. In this tricky way, The problem of O(n^3) tree edit distance (a brief introduction of edit distance will be mentioned at the end) is changed to O(n) time complexity of the list update problem, and both of them use the list key to speed up the update and node reuse; The difference is that React only uses lastIndex when comparing lists to record the maximum position of the same element in the old list. If a new same element appears in a smaller position than lastIndex, move it. Vue2 introduces the double-end comparison algorithm. By using two Pointers to point to the head and tail of the old and new lists, it compares the Pointers of the old and new lists four times each time to determine whether there is node overuse, thus avoiding the inefficient problem of moving tail elements to the head of the list in React algorithm.

Edit distance problem

The problem of editing distance is a classic dynamic programming problem. The problem is roughly how many operations are needed to convert word1 into word2 given two strings word1 and word2, including adding, deleting and replacing (leetcode#72). To solve this problem, a two-dimensional DP table is required. Each position (I, j) represents the minimum number of operations for word1. Substr (0, I) to be converted to word2.substr(0, j).

Note that dp table (I,j) is a substring length, so use word1[i-1], word2[J-1] to get the last character of this length.

dp[i][j] = dp[i-1][j-1]  (if word1[i-1] === word2[j-1])
           min(dp[i-1][j-1] +1, dp[i-1][j]+1, dp[i][j-1] +1) (else)
Copy the code

If at the new (I,j) position of the dp table, the last bit of the word1 substring in the last bit of the word2 substring is equal, then nothing needs to be done, and the minimum number of operations is the same as dp [i-1][J-1]. When the last digit is not equal, you need to do something from another state to get to the desired state. Remember we have three operations: add, delete, and replace, from dp[I][J-1] to add, from DP [i-1][j] to delete, from DP [i-1][J-1] to replace, The minimum value of each of the three +1 is the minimum number of operations corresponding to dp[I][j]. Until the dp table is completed, dp[word1.length][word2.length] is the editing distance of the two strings, and the time complexity is O(n^2) level.

// dp[I][j] *** indicates the edit distance of word1. Substr (0, I) and word2.substr[0,j] ***
// dp[i][j] = dp[i-1][j-1] (if word1[i-1] === word2[j-1])
// min(dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1) (else)
var minDistance = function(word1, word2) {
    const dp = new Array(word1.length + 1).fill(0).map(_= >new Array(word2.length + 1).fill(0))
    for(let i = 1; i <= word1.length; i++) { dp[i][0] = i
    }
    for(let j = 1; j <= word2.length; j++) { dp[0][j] = j
    }
    for (let i = 1; i <= word1.length; i++) {
        for (let j = 1; j <= word2.length; j++){
            if(word1[i-1] === word2[j-1]){
                dp[i][j] = dp[i-1][j-1]}else {
                dp[i][j] = Math.min(dp[i-1][j-1] +1, dp[i-1][j]+1, dp[i][j-1] +1)}}}return dp[word1.length][word2.length]
Copy the code

zhuanlan.zhihu.com/p/91667128

Therefore, in fact, DOM Diff is the problem of editing distance between two virtual DOM trees in the traditional sense, but obviously this problem is more complex and the time complexity is O(n^3) order of magnitude. For details, you can read this paper, but I will not repeat it here.

References:

Vue-js.com/learn-vue/v…

Hustyichi. Making. IO / 2020/09/16 /…

Ustbhuangyi. Making. IO/vue – analysi…