How VNode generates the real Dom is only a small part of what patch rendering does for the first time, but the most important thing it does is make the process of re-rendering pages efficient when triggered in a responsive manner. In fact, the re-rendering of the page could have replaced the old Dom entirely with the newly generated Dom. However, this is not efficient, so the diff comparison algorithm will be used to do this.

What diff algorithm does is to compare VNode and oldVNode, and then make small changes on oldVNode under the condition of VNode as the standard, and complete the Dom rendering corresponding to VNode.

Going back to the previous implementation of the _update method, else logic should be used:

Prototype._update = function(vnode) {const vm = this const prevVnode = vm._vnode._vnode = vnode if(! $el = vm. __Patch__ (vm.$el, vnode)} else {// Render vm.$el = vm. __Patch__ (prevVnode, vnode)}}Copy the code

Since we are tinkering with the existing VNode for the purpose of re-rendering, we can do three things:

Creating a New Node

Deleting an Obsolete Node

Updating an existing node

Next, we will introduce the situations of the above three situations.

Creating a New Node

The new node will be encountered in two cases:

VNodeSome nodes inoldVNodeThere is no

  • VNodeSome nodes inoldVNodeNo, the most obvious scene was first rendered, not at this timeoldVNodeOf, so the wholeVNodeRender as realDomInsert it into the root node.

VNodeandoldVNodeCompletely different

  • whenVNodeandoldVNodeIf the node is not the same, theVNodeMake it realDomIs inserted after the old node, at which point the old node becomes obsolete and removed to complete the replacement process.

To determine whether two nodes are the same node, the internal definition is as follows:

function sameVnode (a, B) {// Check whether the VNode is the same. Return (A.cookie === B.cookie && (// The key (A.cookie === B.cookie && // the key (A.cookie === B.cookie && // the tag is the same IsDef (a.data) === isDef(b.datA) && B) / / the same input type) | | (isTrue (Anderson sAsyncPlaceholder) && / / is asynchronous placeholder fu point a.a syncFactory = = = b.a syncFactory && / / asynchronous factory method isUndef(b.asyncFactory.error) ) ) ) }Copy the code

Deleting an Obsolete Node

If the root node is not the same, render the whole Vnode as a real Dom and insert it after the old node. Finally, delete the old node that has been abandoned.



在patchMethod will be createdDomAfter inserting the abandoned node:

If (isDef(parentElm)) {// Remove old nodes from their parent nodes removeVnodes(parentElm, [oldVnode], 0, 0) } ------------------------------------------------------------- function removeVnodes (parentElm, vnodes, startIdx, endIdx) { for (; startIdx <= endIdx; ++startIdx) {const ch = vnodes[startIdx] if (isDef(ch)) {removeNode(ch. Elm)}}} // Remove content from startIdx to endIdx -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the function removeNode (el) {/ / a single node to remove const parent = nodeOps.parentNode(el) if(isDef(parent)) { nodeOps.removeChild(parent, el) } }Copy the code

Update existing nodes (key)

This is the focus of diff algorithm. When two nodes are the same node, it is necessary to find out their differences and compare them mainly by using the patchVnode method, which mainly deals with several branch cases:

All static nodes

function patchVnode(oldVnode, Vnode) {if(oldVnode === vnode) {// exactly the same return} const elm = vnode.elm = oldvNode. elm if(isTrue(vnode.isstatic) && IsTrue (oldVnode isStatic)) {vnode.com ponentInstance = oldVnode.com ponentInstance return / / are static nodes, skip}... }Copy the code

What is a static node? This is what compile time does. It finds the static nodes in the template and marks them (isStatic is true), for example:

< the template > < div > < h2 > {{title}} < / h2 > < p > fresh food < / p > < / div > < / template >Copy the code

The H2 tag here is not a static node, because it changes by interpolation, and the P tag is a static node, because it doesn’t change. Skip this comparison if both nodes are static, which is also optimized for diff comparison at compile time.

vnodeThe node has no text attribute

function patchVnode(oldVnode, vnode) { const elm = vnode.elm = oldVnode.elm const oldCh = oldVnode.children const ch = vnode.children if (isUndef(vnode.text)) {// vnode has no text attribute if (isDef(oldCh) &&isdef (ch)) {// // has children if (oldCh! UpdateChildren (elm, oldCh, elm) { Ch) // update children}} else if (isDef(ch)) {// Only vnode has children if (isDef(oldvNode.text)) {// oldVnode has text nodes Nodeops. setTextContent(elm, "") // Set oldVnode text to null} addVnodes(elm, null, ch, 0, Ch.length-1) // Insert vnode children's real dom} else if (isDef(oldCh)) {// Only oldVnode has children removeVnodes(elm, oldCh, 0, Else if (isDef(oldvNode.text)) {// oldVnode has a text nodeops.settextContent (elm, ") // Set to null}} else {vnode has text property... }...Copy the code

If a VNode has no text nodes, there are the next four branches:

1. All havechildrenAnd not the same

  • useupdateChildrenMethods compare them in more detailchildren, if updating an existing node ispatchThe core, then update herechildrenIt’s the core of the core, and this is explained in detail later using a flow chart.

Only 2.vnodeThere arechildren

  • That hereoldVnodeEither it’s an empty tag or it’s a text node, if it’s a text node it empties the text node, and then thevnodethechildrenMake it realDomInsert into the empty label.

Only 3.oldVnodeThere arechildren

  • Because isvnodeIs standard, sovnodeWhat you don’t have,oldVnodeInside is the obsolete node and needs to be deleted.

Only 4.oldVnodeA text

  • As long as it isoldVnodeThere are,vnodeIf not, empty or remove it.

vnodeNodes have text attributes

function patchVnode(oldVnode, vnode, insertedVnodeQueue) { const elm = vnode.elm = oldVnode.elm const oldCh = oldVnode.children const ch = vnode.children if (isUndef(vnode.text)) {// vnode has no text attribute... } else if(oldVnode.text ! == vnode.text) {// Vnode has text attributes and different nodeops.settextContent (elm, vnode.text) // Set text}...Copy the code

Again, vNode is the standard, so vnode has a text node, no matter what type of node oldVnode is, directly set to vNode text. At this point, even if the general process of the whole Diff comparison is explained, we still use a flow chart to clarify the idea:

Update the update child of an existing node (key of key)

Example of updating child nodes:  <template> <ul> <li v-for='item in list' :key='item.id'>{{item.name}}</li> </ul> </template> export default { data() { return { list: [{ id: 'a1',name: 'A'}, { id: 'b2',name: 'B'}, { id: 'c3',name: 'C'}, { id: 'd4',name: 'D'} ] } }, mounted() { setTimeout(() => { this.list.sort(() => Math.random() - .5) .unshift({id: 'e5', name: 'E'}) }, 1000) } }Copy the code

Rendering a list, randomly disordering it and adding an item to the top of the list triggers the component to update the child node. There is also some other logic, but let’s just focus on updating the child node and see how it updates the Dom:

function updateChildren(parentElm, oldCh, NewCh) {let oldStartIdx = 0 // old first subscript let oldStartVnode = oldCh[0] // old first node let oldEndIdx = oldch.length-1 // old last subscript Let oldEndVnode = oldCh[oldEndIdx] // old last node let newStartIdx = 0 // new first subscript let newStartVnode = newCh[0] // new first node let NewEndIdx = newch.length-1 // new last subscript let newEndVnode = newCh[newEndIdx] // new last node let oldKeyToIdx // old node key and subscript object set let CheckDuplicateKeys (newCh) // While (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {// Start traversing children if (isUndef(oldStartVnode)) {// omit undefined oldStartVnode = oldCh[++oldStartIdx]} else if (isUndef(oldStartVnode)) { Undefine oldEndVnode = oldCh[--oldEndIdx]} else if(sameVnode(oldStartVnode, NewStartVnode)) {// Compare patchVnode(oldStartVnode, NewStartVnode) // Recursively call oldStartVnode = oldCh[++oldStartIdx] // The old first node and the table below are re-marked after newStartVnode = newCh[++newStartIdx] // Else if (sameVnode(oldEndVnode, newEndVnode)) {patchVnode(oldEndVnode, newEndVnode); NewEndVnode) // Recursively call oldEndVnode = oldCh[--oldEndIdx] // The old last node and the following table are re-marked forward newEndVnode = newCh[--newEndIdx] // Else if (sameVnode(oldStartVnode, newEndVnode)) {// Compare patchVnode(oldStartVnode, InsertBefore (parentElm, oldStartvNode.elm, Nodeops.nextsibling (oldEndVNode.elm)) // Move the old first sibling right to the end, view immediately render oldStartVnode = oldCh[++oldStartIdx] // Old start node is processed, NewEndVnode = newCh[--newEndIdx] // The new last node is processed, Else if (sameVnode(oldEndVnode, newStartVnode)) {// Compare patchVnode(oldEndVnode, newStartVnode, InsertedVnodeQueue) // Recursion nodeops.insertbefore (parentElm, oldEndvNode.elm, oldStartvNode.elm) // Move the old last node left to the front, The view immediately renders oldEndVnode = oldCh[--oldEndIdx] // The old last node is processed, the old last node is the second-to-last node newStartVnode = newCh[++newStartIdx] // The new first node is processed, If (isUndef(oldKeyToIdx)) {oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, OldEndIdx)} idxInOld = isDef(newStartvNode.key) // Get new node key in old node key set? oldKeyToIdx[newStartVnode.key] : FindIdxInOld (newStartVnode, oldCh, oldStartIdx, oldEndIdx) if (isUndef(idxInOld)) {findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx); CreateElm (newStartVnode, insertedVnodeQueue, parentElm, oldStartvNode. elm, false, newCh, NewStartIdx)} else { VnodeToMove = oldCh[idxInOld] // Obtain patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue) oldCh[idxInOld] = undefined nodeOps.insertBefore(parentElm, vnodeToMove.elm, Oldstartvnode.elm)} newStartVnode = newCh[++newStartIdx] // New start subscript and node updated to second node}}... }Copy the code

Function will first define a heap of the let defined variables, these variables are changed by the while loop body of current value, the cycle of exit criteria for as long as there is a new node list processed out, looked at the loop body code is quite complex, but it just did three things, see again see the loop body, which three things will find that in fact is not complicated:

1. Skip the undefined

Why undefined, the flow chart will explain clearly. Just remember, if the old start node is undefined, it moves one bit later; If the old end node is undefined, it moves forward one bit.

2. Quick search

Four quick lookups are tried first, and if they do not match, further processing is done:

  • 2.1 Comparison between new start nodes and old Start nodes

If they match, it means that they are in the right position. Dom does not need to change, just move the index from the beginning of the new node to the later one.

  • 2.2 Comparison between the Old End Node and the new End Node

If they match, it means that they are in the right position. Dom does not need to change, just move the index of the end of the old and new nodes one bit ahead.

  • 2.3 Comparison between the old Start node and the new End node

If the match is not in the right position, the Dom view needs to be updated. Insert the real Dom corresponding to the old start node to the last bit. The index of the old start node moves one bit later, and the index of the new end node moves one bit earlier.

  • 2.4 Comparison between the Old End and new Start Nodes

If the match is not in the right position, the Dom view needs to be updated. Insert the real Dom corresponding to the old end node in front of the real Dom corresponding to the old start node. The index of the old end node is moved one bit earlier, and the index of the new start node is moved one bit later.

3. Search for the key value

  • 3.1 If the value matches the existing key value

That shows that it is an existing node, but the location is wrong, then move the node position can be.

  • 3.2 If the value does not match the existing key value

If it cannot be found in the existing key value set, it indicates that it is a new node. Then create a corresponding real Dom node and insert it in front of the real Dom corresponding to the old start node.

This is not easy to understand, but combined with the previous example, the following flow chart should make a lot of sense:

This is the initial state of the ↑ example, where the subscripts and corresponding nodes defined earlier are the start and end flags.

Write the first to show that the 224 times fast than before, can’t find the key value of the old node through the list after search, and did not find “E” is for the new node, create the corresponding real Dom, inserted into the old start in the front of the corresponding real Dom node, which is A front, has done A, ward A new start position.



↑ then start processing the second, or first for quick lookup, no laterkeyValue list lookup. If it is found that the existing node is in the wrong position, insert the reference nodeANode, will be the original old nodeCSet toundefinedI’m going to skip it here. Another node has been processed. NewstartMove back one.



The new start node corresponds to the old start node.DomIt’s in the right place. NewstartAnd the oldstartAll move back one.



The matching of the old start node and the new end node is satisfied by quick search.DomThe position is incorrect, insert the node to the last position, and the last will be newendMove up one, oldstartMove back one.

↑ processes the last node, which is skipped firstundefined, and then start the quick comparison, matching is the new start node and the old start node, respectivelystartIf I move back one, I’ll break out of the loop. Then take a look at the final code:

function updateChildren(parentElm, oldCh, newCh) { let oldStartIdx = 0 ... while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { ... If (oldStartIdx > oldEndIdx) {refElm = isUndef(newCh[newEndIdx + 1])? null : newCh[newEndIdx + 1].elm addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, InsertedVnodeQueue) // add} else if (newStartIdx > newEndIdx) { RemoveVnodes (parentElm, oldCh, oldStartIdx, oldEndIdx) // Remove obsolete nodes}}Copy the code

In our previous example, the old and new node lists were processed simultaneously to exit the loop. Here is a different processing for the remaining nodes after exiting the loop:

Using the new node list as the standard, if the new node list is processed, the old list still has unused nodes that have not been processed, you can delete them. If the old node is processed first and there are still unused nodes in the new list, create trueDomAnd insert it into the view. That’s the wholediffAlgorithm process.