The origin of the virtual Dom and diff algorithm

As we all know, there is no virtual Dom and DIff algorithm in Vue1.0. For details, you can check my previous article on the analysis and implementation of the principle of Vue1.0. Then why does Vue2.0 introduce virtual Dom and DIff algorithm? Memory leaks result, so introducing virtual Dom and diff algorithms becomes a hurdle to overcome.

Virtual Dom (VNode)

Suppose our real DOM is:

<ul id="container">
    <li class="box" :key="user1">Zhang SAN</li>
    <li class="box" :key="user2">Li si</li>
</ul>
Copy the code

Then its corresponding VNode is:

<script>
let oldVNode = {
  tag: "ul".data: {
    staticClass: "container",},text: undefined.children: [{tag: "li".data: { staticClass: "box".key: "user1" },
      text: undefined.children: [{tag: undefined.data: undefined.text: "Zhang".children: undefined},],}, {tag: "li".data: { staticClass: "box".key: "user2" },
      text: undefined.children: [{tag: undefined.data: undefined.text: "Bill".children: undefined},],},],}; </script>Copy the code

Modify the contents of a LI tag

<ul id="container">
    <li class="box" :key="user1">Zhang SAN's 123123123</li>
    <li class="box" :key="user2">Li si</li>
</ul>
Copy the code

The corresponding virtual DOM becomes

let oldVNode = {
  tag: "ul".data: {
    staticClass: "container",},text: undefined.children: [{tag: "li".data: { staticClass: "box".key: "user1" },
      text: undefined.children: [{tag: undefined.data: undefined.text: "Zhang SAN's 123123123".children: undefined},],}, {tag: "li".data: { staticClass: "box".key: "user2" },
      text: undefined.children: [{tag: undefined.data: undefined.text: "Bill".children: undefined},],},],};Copy the code

diff

A simple introduction

In a word to summarize is: the same layer comparison, depth first

  • Peer comparison?

    If the comparison process is not in the same level, then the time complexity will go up and will no longer be On

  • Depth first?

    When you compare two nodes in a tree, it’s a recursive process

Implementation process

When we this.key = XXX, we fire the setter for the current key and notify all watcher via internal dep.notify() to update it. When we update, we call the patch method.

patch

The sameVnode() function checks whether oldVnode and newVnode are the same node type.

  • Is that callpatchVnode()Diff algorithm
  • If no, replace it directly

When will it go else? For example, when a component is initialized without an oldVnode, Vue will pass in a real DOM (isRealElement is defined for initialization). Obviously sameVnode(a,b) will return false and they are not of the same type.

Core code of Patch:

function patch(oldVnode, newVnode) {
    const isRealElement = isDef(oldVnode.nodeType) // Check whether oldVnode is a real node
    if(! isRealElement && sameVnode(oldVnode, vnode)) {// The update cycle goes here, where diff occurs
        patchVnode(oldVnode, vnode, insertedVnodeQueue, null.null, removeOnly) 
    } else {
        // If it is a real DOM, convert to Vnode and assign to oldVnode
        if (isRealElement) {
            oldVnode = emptyNodeAt(oldVnode) 
        }

        // replacing existing element
        const oldElm = oldVnode.elm
        const parentElm = nodeOps.parentNode(oldElm) // Get the parent of the real DOM

        // Convert oldVnode to real DOM and insert
        createElm(
            vnode,
            insertedVnodeQueue,
            oldElm._leaveCb ? null : parentElm,
            nodeOps.nextSibling(oldElm)
        )


        if (isDef(parentElm)) {
            removeVnodes([oldVnode], 0.0) // Delete the old node
        } else if (isDef(oldVnode.tag)) {
            invokeDestroyHook(oldVnode)
        }
    }
}

Copy the code

sameVnode

This method is used to compare whether two vNodes passed in are the same node. The judging conditions are shown in the following code:

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

patchVnode

Main function: Compares two VNodes, including three types of operations: attribute update, text update, child node update

The specific rules are as follows:

  1. The new and old nodeAll have children nodes, diff operation is performed on the child node and is calledupdateChildren.
  2. If the new node has children and the old node does not, clear the text of the old node and add children to it.
  3. If the new node has no children and the old node has children, all children of the node are removed.
  4. When both old and new nodes have no children, it is simply a text replacement.

PatchVnode core code:

function patchVnode (oldVnode, vnode,) {
    if (oldVnode === vnode) {
      return
    } Return if the new node equals the old node

    const elm = vnode.elm = oldVnode.elm // Assign the real DOM node of oldVnode to Vnode

    // Get an array of children of the old and new nodes
    const oldCh = oldVnode.children
    const ch = vnode.children

    // If the new node has no text, it is most likely to have child elements
    if (isUndef(vnode.text)) {

      // If both sides have child elements
      if (isDef(oldCh) && isDef(ch)) {
        if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) }// If the new node has child elements
      else if (isDef(ch)) {
        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, ' ')
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
      }
          
      // If the old node has child elements, the new node has no child elements.
      else if (isDef(oldCh)) {
        removeVnodes(oldCh, 0, oldCh.length - 1)}// If the old node has text (this step means the new node has no text)
      else if (isDef(oldVnode.text)) {
        nodeOps.setTextContent(elm, ' ')}}// If old node text! = the text of the new node
    else if(oldVnode.text ! == vnode.text) { nodeOps.setTextContent(elm, vnode.text) } }Copy the code

The code above validates the four rules we mentioned above, the most important of which is the comparison between new and old nodes when they both have child elements, namely updateChildren.

updateChildren

This method is an important method in patchVnode, which is also called rearrangement operation. It mainly compares the child nodes of the old and new virtual nodes, and recursively calls patchVnode when the same node is found through sameVnode().

The comparison process

  1. The old song= >The new song
  2. Old end= >A new tail
  3. The old song= >A new tail
  4. Old end= >The new song
  5. If none of the above matches, use a new onevnodePass through the old nodes until the same node is found, and then callpatchVnode

Remark: Process 1~4 can be considered as a means of Vue optimization. Think of the Vue scenario you usually use, either inserting at the beginning or end, or simply modifying a value (this.key = XXX). Considering the high frequency of this scenario,Vue simply makes this optimization to avoid repeated traversal. This is a big performance boost.

So let’s do this with a real examplediffprocess

Description: The real DOM and the oldVnode are divs with contents of A, B and C respectively. The new virtual DOM only changes the content of the original node and adds a new DIV with content of D, nothing else. It is important to note that each comparison follows the rules above.

The initial value:

  • OSIdx (starting subscript of oldVnode) = 0

  • OEIdx (end subscript of oldVnode) = 2

  • NSIdx (newVnode starting subscript) = 0

  • NEIdx (end subscript of newVnode) = 3

  • The first step
oldVnode[oSIdx] === newVnode[nSIdx]
Copy the code

SameVnode (a,b) => sameVnode(a,b); sameVnode(a,b) => sameVnode(a,b); All you need to do is call patchVnode(oldVnode,vNode) to update the content of the node, then oSIdx++, nSIdx++.

  • The second step
oldVnode[oSIdx] === newVnode[nSIdx]// Note that oSIdx is 1 and nSIdx is 1
Copy the code

Description: => sameVnode(a,b) => sameVnode(a,b); Therefore, patchVnode(oldVnode,vNode) is still called to update the node content. And then oSIdx++, nSIdx++.

  • The third step
oldVnode[oSIdx] === newVnode[nSIdx]// Note that oSIdx is 2 and nSIdx is 2
Copy the code

Description: This step is the same as the previous two. And then oSIdx++, nSIdx++.

  • The fourth step
oSIdx = 3  oEIdx = 2
nSIdx = 3  nEIdx = 3
Copy the code

OSIdx >oEIdx, nSIdx===nEIdx (terminate the while loop according to the source logic), indicating that oldCh completes first, so there are more newCh than oldCh, indicating that it is a new operation. Execute addVnodes() to insert the new node into the DOM.

Appendix: updateChildren core source code, with notes

 function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
    let oldStartIdx = 0 // oldVnode starts subscript
    let oldEndIdx = oldCh.length - 1 // oldVnode end subscript
    let oldStartVnode = oldCh[0] // oldVnode first node
    let oldEndVnode = oldCh[oldEndIdx] // oldVnode last node
    
    let newStartIdx = 0 // newVnode start subscript
    let newEndIdx = newCh.length - 1 // newVnode end subscript
    let newStartVnode = newCh[0] // newVnode specifies the first node
    let newEndVnode = newCh[newEndIdx] // newVnode specifies the last node
    let oldKeyToIdx, idxInOld, vnodeToMove, refElm

   
    constcanMove = ! removeOnlyif(process.env.NODE_ENV ! = ='production') {
      checkDuplicateKeys(newCh)
    }

    // Pay attention to the loop condition, only if the start node of oldVnode and newVnode is less than or equal to
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
        oldStartVnode = oldCh[++oldStartIdx] // This step is an extra operation. If oldStartVnode does not get the element, it moves back
      } else if (isUndef(oldEndVnode)) {
        oldEndVnode = oldCh[--oldEndIdx] // This step is an extra operation, if oldEndVnode can't get the element, it moves back
      } 
      // Actually start diff
      else if (sameVnode(oldStartVnode, newStartVnode)) {
        // Compare old and new
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // Old tail new tail comparison
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) { 
        // Compare the old head with the new tail
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
        oldStartVnode = oldCh[++oldStartIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldEndVnode, newStartVnode)) { 
        // Compare the old tail with the new head
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        // None of the above matches execute the following logic
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
        if (isUndef(idxInOld)) { // New element
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        } else {
          vnodeToMove = oldCh[idxInOld]
          if (sameVnode(vnodeToMove, newStartVnode)) {
            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
            oldCh[idxInOld] = undefined
            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]
      }
    }
    
    // When the loop ends, determine whether there is more oldCh or newCh
    // If oldCh is more than newCh, it is deleted
    // If oldCh is less, newCh is more
    if (oldStartIdx > oldEndIdx) {
      refElm = isUndef(newCh[newEndIdx + 1])?null : newCh[newEndIdx + 1].elm
      addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
    } else if (newStartIdx > newEndIdx) {
      removeVnodes(oldCh, oldStartIdx, oldEndIdx)
    }
  }
Copy the code

Why can’t index be used as key?

Why don’t we use index as the key in our for loop?

Here are two examples of what matters, what doesn’t, and how the correct key should be set.

/ / / / new old
<ul>                                    <ul>  
                                           <li :key="0"> user3 </li> 
    <li :key="0"> user1 </li>              <li :key="1"> user1 </li>
    <li :key="1"> user2 </li>              <li :key="2"> user2 </li>                               
</ul>                                   </ul>
                                
Copy the code

In the example above, we inserted only one entry at the beginning of the list, leaving everything else unchanged. In normal thinking, user1 and user2 can be reused and user3 can be created. But now our key is index, and when we insert the button, what does the browser do?

The index for the key

<ul class="container">
  <li v-for="(item, index) in list" :key="index" class="box">{{ item }}</li>
</ul>
<button @click="addUser">add</button>


<script>
export default {
  data() {
    return {
      list: ["user1"."user2"."user3"]}; },methods: {
    addUser() {
      this.list.unshift("user5"); ,}}};</script>
Copy the code

He will directly update all nodes corresponding to Li! Why is that? At this point you need to go back to the sameVnode(a,b) method. The nodes to be compared have the same key and tag, so if sameVnode() is true, patchVnode() will be called directly to update the text of the two identical nodes

In our example, 4 DOM manipulations (3 updates, 1 creation) were performed, user4 should have been created, and user3 was created without reuse at all!!

The key item do

If we use item as the key, how does the browser update it? (There is an ID in the list of normal services. Generally, ids are used as keys.)

<ul class="container">
  <li v-for="item in list" :key="item" class="box">{{ item }}</li>
</ul>
<button @click="addUser">add</button>
Copy the code

Is there only one DOM operation (one creation), thus realizing the concept of reuse and updating with less cost?

Best line

If I button with push instead of unshift, then whether we use index as the key or item as the key, it’s the same thing, we just create a new node and do a DOM operation.

addUser() {
  this.list.push("user5");
},
Copy the code

That’s because diff’s rules are:

  1. The old song= >The new song
  2. Old end= >A new tail
  3. The old song= >A new tail
  4. Old end= >The new song
  5. If none of the above matches, use a new onevnodePass through the old nodes until the same node is found, and then callpatchVnode

See here, do you have a deeper understanding of Diff’s rules.