An overview of the

Diff algorithm can be said to be a more core content of Vue. Before, I will only use Vue to carry out some development. The specific core content is actually not much

Virtual Dom (virtual Dom)

Virtual DOM is to extract the data of the real DOM and simulate the tree structure in the form of objects. For example, the following is our real DOM

<div>
   <p>1234</p>
   <div>
       <span>1111</span>
   </div>
</div>
Copy the code

The virtual DOM generated based on the real DOM is as follows

var Vnode = { tag: 'div', children: [ { tag: 'p', text: '1234' }, { tag: 'div', children:[ { tag: 'span', text: '1111'}]}]}Copy the code

The principle of

The principle of DIff is that the current real DOM generates a virtual DOM, which is also called the virtual DOM. When the data of a node in the virtual DOM changes, a new Vnode is generated. Then, the Vnode is compared with the old oldVnode, and the difference is found, and the Vnode is directly modified on the real DOM

The implementation process

The core of the implementation process of diff algorithm is patch, among which patchVnode, sameVnode and updateChildren methods are worth our attention, which are explained in the following sequence

Patch method

The core logic of Patch is to compare two Vnode nodes, and then update the differences to the view. The way of comparison is peer comparison, rather than cyclic traversal of each level. If the differences are obtained after comparison, the differences will be updated to the view

SameVnode function

SameVnode is used to determine whether two nodes are identical based on key, tag, isCommit, input type, etc. This method is a bit of a flaw. It may also be judged to be a reusable node. Do not use index as the key value.

PatchVnode function

// Pass several parameters, oldVnode for the old node, vnode for the new node, ReadOnly Indicates whether the node is read-only. Function patchVnode (oldVnode, vNode, insertedVnodeQueue, ownerArray, index, RemoveOnly) {if (oldVnode === vnode) { Return} if (isDef resused (vnode.elm) && isDef(ownerArray)) {// Clone port vNode vNode = ownerArray[index] = cloneVNode(vnode) } const elm = vnode.elm = oldVnode.elm if (isTrue(oldVnode.isAsyncPlaceholder)) { if (isDef(vnode.asyncFactory.resolved)) { hydrate(oldVnode.elm, vnode, {vnode.isAsyncplaceholder = true} return {vnode.isAsyncplaceholder = true} return {vnode.isAsyncplaceholder = true}} // The rendering function has been cloned via hot-reload-API, and we need to do a proper re-render. if (isTrue(vnode.isStatic) && isTrue(oldVnode.isStatic) && vnode.key === oldVnode.key && (isTrue(vnode.isCloned) || isTrue(vnode.isOnce)) ) { vnode.componentInstance = oldVnode.componentInstance return } let i const data = vnode.data if  (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) { i(oldVnode, vnode) } const oldCh = oldVnode.children const ch = vnode.children if (isDef(data) && isPatchable(vnode)) { for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode) if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode) } if (isUndef(vnode.text)) { if (isDef(oldCh) && isDef(ch)) { if (oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) } else if (isDef(ch)) { if (process.env.NODE_ENV ! == 'production') { checkDuplicateKeys(ch) } if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '') addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue) } else if (isDef(oldCh)) { removeVnodes(oldCh, 0, oldCh.length - 1) } else if (isDef(oldVnode.text)) { nodeOps.setTextContent(elm, '') } } else if (oldVnode.text ! == vnode.text) { nodeOps.setTextContent(elm, vnode.text) } if (isDef(data)) { if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode) } }Copy the code

The specific implementation logic is:

  1. If the new node is the same as the new node, you don’t need to change it
  2. Oldvnode. elm and oldvNode. child are copied to vnode when vnode is a clone or v-once command
  3. Determine whether the Vnode is a comment node or a text node and do the following
    1. When vnode is a text or comment node, when vnode.text! == oldvNode. text, only the vnode text needs to be updated;
    2. OldVnode and vndoe both have children. If the children are different, the updateChildren method is called
    3. If only vnode has child nodes, check the environment. If not, call checkDuplicateKeys to check whether the key value is repeated. The current CH is then added to the oldVnode
    4. If only oldVnode has child nodes, then the method is called to remove the current node

UpdateChildren function

As the name implies, updateChildren is a method to update child nodes. It can be seen from the above methods of patchVnode that this method is implemented when both the new and old nodes have child nodes. So let’s look at the implementation logic, and there are some examples that you might have seen, but let’s look at the code

function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) { let oldStartIdx = 0 let newStartIdx = 0 let oldEndIdx = oldCh.length - 1 let oldStartVnode = oldCh[0] let oldEndVnode = oldCh[oldEndIdx] let newEndIdx = newCh.length - 1 let newStartVnode = newCh[0] let newEndVnode = newCh[newEndIdx] let oldKeyToIdx, idxInOld, vnodeToMove, refElm // removeOnly is a special flag used only by <transition-group> // to ensure removed elements stay in correct relative positions // during leaving transitions const canMove = ! removeOnly if (process.env.NODE_ENV ! == 'production') { checkDuplicateKeys(newCh) } while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { if (isUndef(oldStartVnode)) { oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left } else if (isUndef(oldEndVnode)) { oldEndVnode = oldCh[--oldEndIdx] } else if (sameVnode(oldStartVnode, newStartVnode)) { patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx) oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx] } else if (sameVnode(oldEndVnode,  newEndVnode)) { patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx) oldEndVnode = oldCh[--oldEndIdx] newEndVnode = newCh[--newEndIdx] } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right 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)) { // Vnode moved left patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx) canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm) oldEndVnode = oldCh[--oldEndIdx] newStartVnode = newCh[++newStartIdx] } else { 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] } } 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

OldStartIdx, oldEndIdx, oldStartVnode, oldEndVnode; oldStartVnode, oldEndVnode; oldStartVnode, oldEndVnode; Similarly, newStartIdx and other four items are the first index of the new node.

After determining that it is the same node, the node also needs to continue the patchVnode method

  1. If the old first element and the new first element are the same node, the old first index and the new first index are both moved right

  2. If the old and new tailed elements are the same node, the old and new tailed indexes are moved to the left at the same time

  3. If the old leading element is the same node as the new trailing element, then the new trailing element is shifted to the right and the new trailing index is shifted to the left, based on the readonly value uploaded by the method. If false, the old leading element is moved to the right and the new trailing index to the left

  4. If the old trailing element is the same node as the new leading element, then the method uploads readonly (if false) to move the old trailing element to one bit before the first index of the old node, while moving the old trailing index to the left and the new leading index to the right

  5. If newStartVnode and oldCh have the same key as newStartVnode, it is a new node, create a new node and insert it

    If you find a Vnode that has the same key as newStartVnode, name it vnodeToMove. Then compare vnodeToMove to newStartVnode. If removeOnly is false, remove the Vnode that has the same key as newStartVnode, called vnodeTomove.elm, and move it before oldStartVNode.elm

    If the key values are the same, but the nodes are different, a new node is created

After going through the While loop, if there are still nodes in the new or old node array, delete them or add them as the case may be

When oldStartIdx > oldEndIdx, it means oldCh finished first, which means there are more nodes than needed, so add new nodes

When newStartIdx > newEndIdx, the new node is traversed first, the old node is left, and the remaining nodes are deleted

Let’s look at a sample diagram

  1. Original node (oldVnode is the old node, Vnode is the new node, diff is the node array generated after the diff algorithm)

! [image. PNG] (p3-juejin.byteimg.com/tos-cn-i-k3…

  1. For the first time in the loop, we find that the old trailing element is the same as the new leading element, so the old trailing element D moves to the front of the old leading index, which is in front of A, and the old trailing index moves to the left and the new leading index moves to the right

3. Loop the second time, the new first element is the same as the old first element. This time, the two elements remain unchanged, and the new and old first indexes move to the right at the same time

  1. On the third loop, we find that there is no node in the old element that is the same as the current element, so we add a new element, put F before the old first element. Similarly, on the fourth loop, we generate a new sample graph after two loops

  1. Cycle the fifth time, as if the second cycle

  1. The sixth time, newStartIdx moves to the right again

NewStartIdx > newEndIdx, newStartIdx > newEndIdx, newStartIdx > newEndIdx, newStartIdx > newEndIdx, newStartIdx > newEndIdx

Above is a few diFF algorithm related functions, and diFF algorithm implementation process

conclusion

Diff algorithm is a core part of the virtual DOM. By comparing new and old nodes at the same layer, it updates the changed places to the real DOM.

The specific implementation methods are Patch, patchVnode and updateChildren

The core of Patch is: If the new node has one, the old node does not, the new node is added. Old node yes, new node no, delete; If both exist, check whether they are the same. If they are the same, call patchVnode for further comparison

The core of patchVnode is as follows: If the new node is not a comment or text node and the new node has a child node, and the old node does not have a child node, a new child node is added. If the new node has no child nodes, and the old node has child nodes, the child nodes under the old node are deleted. If both have children, the updateChildren method is called

The core of updateChildren is to compare old and new nodes and add, delete, or update them.

This is just a preliminary explanation of the diff algorithm of Vue2.0 version, and the deeper principle of the diff algorithm of Vue3.0 remains to be learned.