Vue principle analysis (eight) : work out the headache diff algorithm

Vue principle analysis (seven) : a comprehensive and in-depth understanding of the principle of response (below)- array advanced chapter

The previous section explained how VNode generates the real Dom. This is only the first rendering in Patch, and it does a small part of the job. The most important thing it does is to efficiently re-render the page 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:

Vue.prototype._update = function(vnode) {const vm = this const prevVnode = vm._vnode vm._vnode = vnodeif(! PrevVnode) {// Render vm for first time.$el = vm.__patch__(vm.$el, vnode)
  } else{// re-render the 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 into the root node, as detailed in the previous section.

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:

functionSameVnode (a, b) {// whether it is the sameVnodereturn(a.k ey = = = b.k ey && (/ / written as usual v - for key (a.t ag = = = b.t ag && / / tag same Anderson sComment = = = b.i sComment && / / comment node SameInputType (a, sameInputType) === isDef(b.ata) && 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.

patch
Dom

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 the contents from startIdx to endIdx ------------------------------------------------------------functionConst parent = nodeops.parentNode (el) {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) {// Identicalreturn
  }

  const elm = vnode.elm = oldVnode.elm
  if(isTrue(vnode.isStatic) && isTrue(oldVnode.isStatic)) {  
    vnode.componentInstance = oldVnode.componentInstance
    return// all 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 attributeif(isDef(oldCh) &&isdef (ch)) {// // both have childrenif(oldCh ! UpdateChildren (elm, oldCh, ch) {else if(isDef(ch)) {// Only vnodes have childrenif(isDef(oldvNode.text)) {// oldVnode has a text node nodeops.settextContent (elm,' '} addVnodes(ELM, null, ch, 0, ch.length-1) // Insert the children's real DOM of vNode into the empty tag of oldVnode}else if(isDef(oldCh)) {children removeVnodes(elm, oldCh, 0, oldch.length-1)}else if(isDef(oldvNode.text)) {// oldVnode has a text node nodeops.settextContent (elm,' ') // Set to null}}else{vnode has a text attribute... }...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 for 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) {
  letOldStartIdx = 0 // old first indexletOldStartVnode = oldCh[0] // Old first nodeletOldEndIdx = oldch.length - 1 // old last subscriptletOldEndVnode = oldCh[oldEndIdx] // Old last nodeletNewStartIdx = 0 // New first indexletNewStartVnode = newCh[0] // New first nodeletNewEndIdx = newch.length - 1 // New last subscriptletNewEndVnode = newCh[newEndIdx] // New last nodeletOldKeyToIdx // An object collection of old node keys and subscriptsletIdxInOld // Index of the new node key in the old node key setletVnodeToMove // idxInOld nodeletRefElm // checkDuplicateKeys(newCh) // Check whether newVnode has duplicate keyswhile(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {// Start traversing childrenif(isUndef(oldStartVnode)) {// skip undefined oldStartVnode = oldCh[++ oldStarttidx]}else if(isUndef(oldEndVnode)) {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] // The new first node and the following table are re-marked later}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] // New last node and the following table re-mark forward}else if(sameVnode(oldStartVnode, newEndVnode)) {// patchVnode(oldStartVnode, newEndVnode) 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, the new last node is the penultimate}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, New first node is second}else{// The above four quick comparison methods are not includedif(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)) {// If no subscript is found, the new node is added. Create dom createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartvNode. elm,false, 
          newCh, 
          newStartIdx
        )
      }
      
      else{// Can find the corresponding subscript, indicating that is the existing node, 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:

start
end

key
E
Dom
start
Dom
A
start

key
A
C
undefined
start

Dom
start
start

Dom
end
start

undefined
start

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)else ifRemoveVnodes (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:

Dom
diff

We end this chapter with the usual interview question that Vue will be asked

The interviewer smiled politely and asked,

whyv-forLi recommends binding for each itemkeyAnd preferably unique and not recommendedindex?

Dui back:

indiffThe child nodes are updated according to the internal comparisonoldVnodeThe node that is not processed inside gets onekeyValues and subscripts correspond to a collection of objects that are processed whenvnodeEach node can quickly find whether the node is an existing node, thus improving the wholediffComparison performance. If it’s a dynamic list,keyValues are best kept unique, but are used for lists that do not change, such as a rotation chartindexThat’s ok.

(9) To understand the principles of computed and Watch, and to reduce the time to think about using scenarios

Easy to click a like or follow bai, also easy to find ~

Reference:

Vue. Js source code comprehensive in-depth analysis

Vue.js is easy to understand

Share a component library for everyone, may use up ~ ↓

A library of vUE functional components that you might want to use.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Vue principle analysis (eight) : work out the headache diff algorithm

Creating a New Node

`VNode`Some nodes in`oldVNode`There is no

`VNode`and`oldVNode`Completely different

Deleting an Obsolete Node

Update existing nodes (key)

All static nodes

`vnode`The node has no text attribute

`vnode`Nodes have text attributes

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

1. Skip the undefined

2. Quick search

3. Search for the key value

The interviewer smiled politely and asked,

Dui back:

Reference:

Share a component library for everyone, may use up ~ ↓

Vue principle analysis (eight) : work out the headache diff algorithm

Creating a New Node

VNodeSome nodes inoldVNodeThere is no

VNodeandoldVNodeCompletely different

Deleting an Obsolete Node

Update existing nodes (key)

All static nodes

vnodeThe node has no text attribute

vnodeNodes have text attributes

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

1. Skip the undefined

2. Quick search

3. Search for the key value

The interviewer smiled politely and asked,

Dui back:

Reference:

Share a component library for everyone, may use up ~ ↓

Related Posts

Vscode failed to commit Git

JS Basic series – 💣 exception handling

Review the computer composition of the series

`VNode`Some nodes in`oldVNode`There is no

`VNode`and`oldVNode`Completely different

`vnode`The node has no text attribute

`vnode`Nodes have text attributes