The diff algorithm is an efficient algorithm that compares tree nodes at the same level, avoiding the need to search and traverse the tree layer by layer. So how much do you know about the diff algorithm? The following article will give you an in-depth analysis of the diff algorithm of vue2. I hope it will be helpful to you!

I have been looking at the source code of Vue 2 for a long time. From using flow to now using TypeScript, I will open its source code and take a look every time, but every time I only saw the data initialization part, which is the stage of beforeMount, about how to generate VNode (Visual Dom Node, which can also be directly called vdom) and how to compare VNode (diff) when updating components ) has never been carefully studied. I only know that the double-ended diff algorithm is used. As for how this double-ended starts and ends, I have never seen it, so I took the opportunity to write an article to study it carefully this time. If the content is wrong, I hope you can help me point it out. Thank you very much~

What is diff?

In my understanding, diff refers to differences, that is, calculating the difference between old and new content; the diff algorithm in Vue quickly compares the old and new content through a simple and efficient method The difference between VNode node arrays is to update page content with minimal dom operations. [Related recommendations: vuejs video tutorial, web front-end development]

There are two necessary prerequisites here:

• The comparison is the VNode array

• There are two sets of old and new VNode arrays at the same time

So it generally only occurs when data updates Execute when the page content needs to be updated, that is, renderWatcher.run().

Why VNode?

As mentioned above, what is compared in diff is VNode, not the real dom node. I believe that why VNode is used? Most people compare It’s clear, let me just briefly explain it, right?~

There are roughly two reasons for using VNode in Vue:

• VNode is designed as a framework designer according to the framework requirements. The JavaScript object itself has simpler properties than the real DOM node, and there is no need to perform DOM query during operation, which can greatly optimize the performance consumption during calculation

• This link from VNode to the real DOM The rendering process can be processed differently according to different platforms (web, WeChat applet) to generate real dom elements adapted to each platform

During the diff process, the old and new node data will be traversed. In comparison, using VNode can bring great performance improvements.

Process sorting

In the web page, the real dom nodes exist in the form of tree, and the root nodes are all , in order to ensure that the virtual node is consistent with the real dom node, VNode also uses a tree structure.

If all VNode nodes need to be compared when the component is updated, both the old and new sets of nodes need to be deeply traversed and compared, which will cause a lot of performance overhead; therefore, by default in Vue Comparison of nodes at the same level, that is, if the levels of the old and new VNode trees are different, the content of the extra levels will be directly created or discarded, and only the diff operation will be performed at the same level.

Generally speaking, diff operations generally occur in v-for loops or v-if/v-else, component and the like. Dynamically generate node objects (static nodes generally do not change, and comparison is very fast), and this process is to update the dom, so in the source code, the method name corresponding to this process is updateChildren , located in src/core/vdom/patch.ts. As shown below:

Here is a review of the creation and update process of Vue component instances:

• First of all beforeCreate to the created stage, mainly processing data and status as well as some basic events and methods

• Then, $mount(vm .$options.el) method enters the creation and mounting phase of Vnode and dom, that is, between beforeMount and mounted (when the component is updated Similar to here)

• The $mount on the prototype will be rewritten in platforms/web/runtime-with-compiler.ts, and the original implementation is in platforms/web/runtime/index.ts; in the original implementation method, it actually calls the mountComponent method to execute render; and in web The runtime-with-compiler below adds the template string compilation module, which will perform the template in options Once parsed and compiled, converted into a function bound to options.render

• mountComponent inside the function defines rendering Method updateComponent = () => (vm._update(vm._render()), instantiates a watcher instance with before configuration (i.e. renderWatcher), by defining the watch observation object as the just-defined updateComponent method to perform the first component rendering and trigger dependency collection , where before The configuration only configures the method to trigger the beforeMount/beforeUpdate hook function; this is why the real dom node cannot be obtained in the beforeMount stage and the beforeUpdate stage The reason is that the old dom node

• _update method is defined in the same file as mountComponent, and its core is reading The $el (old dom node) and _vnode (old VNode) in the component instance are compared with the vnode generated by the _render() function. patch Operation

• patch The function first compares to see if it has an old node. If not, it must be a new one. Component, create and render directly; if there is an old node, compare the old and new nodes through patchVnode, And if the old and new nodes are consistent and both have children child nodes, Then enter the core logic of diff - updateChildren Child node comparison update, this method is also what we often call the diff algorithm

Preface content

Since we are comparing the old and new VNode arrays, there must first be a comparison judgment method: sameNode (a, b), method of adding nodesaddVnodes, method of removing nodesremoveVnodes, of course, even after sameNode determines that the VNode is consistent , patchVnode will still be used to deeply compare the contents of a single new and old VNode to confirm whether the internal data needs to be updated.

sameNode(a, b)

This method has one purpose: Compare whether the old and new nodes are the same.

In this method, the first thing to compare is whether the key of a and b are the same. This is why Vue notes v-for, v-if, Dynamic nodes such as v-else must set key to identify the uniqueness of the node. If key exists and is the same, you only need to compare whether the internal changes have occurred. Under normal circumstances It can reduce a lot of DOM operations; if it is not set, the corresponding node elements will be directly destroyed and rebuilt.

Then it will compare whether it is an asynchronous component, and here it will compare whether their constructors are consistent.

Then you will enter two different situations for comparison:

• Non-asynchronous component: the label is the same, both are not comment nodes, both have data, and the same type of text input box
• Asynchronous component: The error prompts of the old node placeholder and the new node are both undefined

The overall process of the function is as follows

addVnodes

As the name suggests, add new VNode nodes.

This function receives 6 parameters: parentElm The parent element of the current node array, refElm The element at the specified position, vnodes New Virtual node array, startIdx The starting position of the inserted element of the new node array, endIdx The end index of the inserted element of the new node array, insertedVnodeQueue The virtual node that needs to be inserted Node queue.

The internal function will traverse the vnodes array starting from startIdx until the endIdx position , and then call createElm Create and insert the elements corresponding to vnodes[idx] before refElm in turn.

Of course, there may be Component components in this vnodes[idx], and createComponent will also be called to create the corresponding Component instance.

Because the entire VNode and dom are both a tree structure, so after comparison at the same level, it is necessary to process the deeper VNode under the current level. and dom processing.

removeVnodes

Contrary to addVnodes, this method is used to remove VNode nodes.

Since this method only removes, it only requires three parameters: vnodes Old virtual node array, startIdx Start index, endIdx End index.

The internal function will traverse the vnodes array starting from startIdx until the endIdx position , if vnodes[idx ] If it is not undefined, it will be processed according to the tag attribute:

• exists, indicating that it is An element or component needs to recursively process the contents of vnodes[idx], trigger remove hooks and destroy hooks does not exist tag
, indicating that it is a
• plain text node, you can directly remove the node from the dom
patchVnode

The actual complete comparison and dom update

method of node comparison.

In this method, it mainly contains nine

main parameter judgments, and corresponds to different processing logic:

The old and new VNodes are congruent, It means there is no change,

Exit directly

• If the new VNode has real dom binding, and the node set that needs to be updated is an array, copy the current The VNode goes to the specified position of the collection

• If the old node is an
asynchronous component and has not finished loading, exit
• directly, otherwise pass

  hydrate The function converts the new VNode into a real dom for rendering; in both cases, exits the function

  If the old and new nodes are both
static nodes
• and

  key are equal, or if the node is not updated if isOnce is specified, the component instance of the old node will be directly reused and exit the function

  If the new VNode node has the
data
• attribute and is configured with the

  prepatch hook function, execute prepatch(oldVnode, vnode) Notifies the node to enter the comparison phase. Generally, this step will configure performance optimization

  If the new VNode has the
data
• attribute and recursively changes the node's child If the vnode of the component instance is still available with labels, the

  update hook function configured in the cbs callback function object and the update## configured in data #Hook function

  If the new VNode is not a text node, it will enter the core comparison phase
:

• If there are both old and new nodes children

  child node, enter the
  updateChildren
  • method to compare child nodesIf the old node has no child nodes, directly create a new child node corresponding to the VNode If the new node has no child nodes, remove the old VNode child nodes
  • If there are no child nodes and the old node has text content configuration, clear the previous one
  text
  • Text
  If the new VNode has
  text
text (it is a text node), compare the text content of the old and new nodes to see if they are consistent, otherwise proceed with the text content The update

• finally calls the

  postpatch
hook function configured in the
• data

  of the new node to notify the node that the update is completeSimply put,

  patchVnode
is to compare the new content with the old content in the

same node update phase. If there is a change, the corresponding content will be updated; if there are child nodes, then "Recursively" performs comparison and update of each child node

. And The comparison and update of child node arrays is the core logic of diff, and it is also one of the questions often mentioned during interviews.

Next, let’s enter the analysis of the updateChildren method~

##updateChildren diff core analysis

First, let's think about itComparing the difference in elements of two object arrays based on the new arrayWhat are the methods?

Generally speaking, we can directly traverse two arrays

through violent means to find the order and difference of each element in the array, which is simple diff algorithm

.

That is, traverses the new node array, traverses the old node array again in each cycle to compare whether the two nodes are consistent, and determines whether the new node is added, removed or moved by comparing the results , The entire process requires m*n comparisons, so the default time complexity is On.

This comparison method is very performance consuming during a large number of node updates, so Vue 2 has optimized it and changed it to Double-ended comparison algorithm, which is Double-ended diff.

Double-ended diff algorithm

As the name suggests, Double-ended is starting from both ends and traversing to the middle for comparison algorithm.

In double-ended diff, there are five comparison situations:

• The old and new headers are equal

• The old and new tails are equal

• The old head is equal to the new tail

• The old tail is equal to the new head

• The four are not equal to each other

Among them, the first four are ideal situations, while the fifth is The most complex comparison situation.

Judge equality, that is, sameVnode(a, b) is equal to true

Below we use a preset situation to Perform analysis.

1. Preset new and old node states

In order to try to demonstrate the above five situations at the same time, I preset the following new and old node arrays:

• As the old node array in initial node orderoldChildren, including a total of 7 nodes from 1 to 7
• As the new node array after disordernewChildren, There are also 7 nodes, but compared to the old node, there is one less vnode 3 and one more vnode 8

Before comparing, you first need toDefine the double-ended index of two sets of nodes :

let oldStartIdx = 0
let oldEndIdx = oldCh.length - 1
let oldStartVnode = oldCh[0]
let oldEndVnode = oldCh[oldEndIdx]

let newStartIdx = 0
let newEndIdx = newCh.length - 1
let newStartVnode = newCh[0]
let newEndVnode = newCh[newEndIdx]

Copied source code, where oldCh is oldChildren in the figure,newCh is newChildren

Then, we define the stop condition for the traversal comparison operation:

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx)

stop here The condition is As soon as either the traversal of the old or new node array ends, the traversal will stop immediately.

The node status at this time is as follows:

2. Confirm that vnode exists before comparing

In order to ensure the old and new The node array will not perform invalid comparison during comparison, and will first exclude the data where the beginning part and end part of the old node array are continuous and the value is Undefined.

if (isUndef(oldStartVnode)) {
  oldStartVnode = oldCh[++oldStartIdx]
} else if (isUndef(oldEndVnode)) {
  oldEndVnode = oldCh[--oldEndIdx]

Of course this is not the case in our example and can be ignored.

3. The old head is equal to the new head

At this time, it is equivalent to the two starting indexes of the old and new node arrays. The node pointed to isBasically consistent, then patchVnode will be called at this time to perform deep comparison and dom update of the two vnodes, and the two starting indexes will be moved backward . That is:

if (sameVnode(oldStartVnode, newStartVnode)) {
  patchVnode(
    oldStartVnode,
    newStartVnode,
    insertedVnodeQueue,
    newCh,
    newStartIdx
  )
  oldStartVnode = oldCh[++oldStartIdx]
  newStartVnode = newCh[++newStartIdx]
}

The node and index changes at this time are as shown in the figure:

##4. The old tail is equal to the new tail

is similar to head node equality. This situation means that

the last node of the old and new node arrays are basically the same

. At this time, patchVnode is also called to compare the sum of the two tail nodes. Update the dom and move the two end indices forward .

if (sameVnode(oldEndVnode, newEndVnode)) {
  patchVnode(
    oldEndVnode,
    newEndVnode,
    insertedVnodeQueue,
    newCh,
    newEndIdx
  )
  oldEndVnode = oldCh[--oldEndIdx]
  newEndVnode = newCh[--newEndIdx]
}

The node and index changes at this time are as shown in the figure:

5. The old head is equal to the new tail

What this means is that

The vnode pointed by the current starting index of the old node array is basically the same as the vnode pointed by the current end index of the new node array

. Call patchVnode to perform the same on the two nodes. deal with. But the difference from the above two is that in this case, the

node will be moved

, so it will end at patchVnode Then reinsert the old head node through nodeOps.insertBefore to after the current old tail node . Then,

the starting index of the old node will be moved backward and the end index of the new node will be moved

forward.

You may have a question when you see this, why is the

old node array

moved here? This is because there is an attribute elm in the vnode node. , will point to the actual dom node corresponding to the vnode, so moving the old node array here is actually moving the actual dom node sequence on the side; and note that this is the current tail node, when the index changes Afterwards, this is not necessarily the end of the old node array.

即：

if (sameVnode(oldStartVnode, newEndVnode)) {
  patchVnode(
    oldStartVnode,
    newEndVnode,
    insertedVnodeQueue,
    newCh,
    newEndIdx
  )
  canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
  oldStartVnode = oldCh[++oldStartIdx]
  newEndVnode = newCh[--newEndIdx]
}

此時狀態(tài)如下：

6. 舊尾等于新頭

這里與上面的 舊頭等于新尾 類似，一樣要涉及到節(jié)點對比和移動，只是調(diào)整的索引不同。此時 舊節(jié)點的 末尾索引 前移、新節(jié)點的 起始索引 后移，當(dāng)然了，這里的 dom 移動對應(yīng)的 vnode 操作是 將舊節(jié)點數(shù)組的末尾索引對應(yīng)的 vnode 插入到舊節(jié)點數(shù)組 起始索引對應(yīng)的 vnode 之前。

if (sameVnode(oldEndVnode, newStartVnode)) {
  patchVnode(
    oldEndVnode,
    newStartVnode,
    insertedVnodeQueue,
    newCh,
    newStartIdx
  )
  canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
  oldEndVnode = oldCh[--oldEndIdx]
  newStartVnode = newCh[++newStartIdx]
}

此時狀態(tài)如下：

7. 四者均不相等

在以上情況都處理之后，就來到了四個節(jié)點互相都不相等的情況，這種情況也是 最復(fù)雜的情況。

當(dāng)經(jīng)過了上面幾種處理之后，此時的 索引與對應(yīng)的 vnode 狀態(tài)如下：

可以看到四個索引對應(yīng)的 vnode 分別是：vnode 3、vnode 5、 vnode 4、vnode 8，這幾個肯定是不一樣的。

此時也就意味著 雙端對比結(jié)束。

后面的節(jié)點對比則是 將舊節(jié)點數(shù)組剩余的 vnode （oldStartIdx 到 oldEndIdx 之間的節(jié)點）進(jìn)行一次遍歷，生成由 vnode.key 作為鍵，idx 索引作為值的對象 oldKeyToIdx，然后 遍歷新節(jié)點數(shù)組的剩余 vnode（newStartIdx 到 newEndIdx 之間的節(jié)點），根據(jù)新的節(jié)點的 key 在 oldKeyToIdx 進(jìn)行查找。此時的每個新節(jié)點的查找結(jié)果只有兩種情況：

• 找到了對應(yīng)的索引，那么會通過 sameVNode 對兩個節(jié)點進(jìn)行對比：

  • 相同節(jié)點，調(diào)用 patchVnode 進(jìn)行深層對比和 dom 更新，將 oldKeyToIdx 中對應(yīng)的索引 idxInOld 對應(yīng)的節(jié)點插入到 oldStartIdx 對應(yīng)的 vnode 之前；并且，這里會將 舊節(jié)點數(shù)組中 idxInOld 對應(yīng)的元素設(shè)置為 undefined
  • 不同節(jié)點，則調(diào)用 createElm 重新創(chuàng)建一個新的 dom 節(jié)點并將 新的 vnode 插入到對應(yīng)的位置

• 沒有找到對應(yīng)的索引，則直接 createElm 創(chuàng)建新的 dom 節(jié)點并將新的 vnode 插入到對應(yīng)位置

注：這里 只有找到了舊節(jié)點并且新舊節(jié)點一樣才會將舊節(jié)點數(shù)組中 idxInOld 中的元素置為 undefined。

最后，會將 新節(jié)點數(shù)組的 起始索引 向后移動。

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]
}

大致邏輯如下圖：

剩余未比較元素處理

經(jīng)過上面的處理之后，根據(jù)判斷條件也不難看出，遍歷結(jié)束之后 新舊節(jié)點數(shù)組都剛好沒有剩余元素 是很難出現(xiàn)的，當(dāng)且僅當(dāng)遍歷過程中每次新頭尾節(jié)點總能和舊頭尾節(jié)點中總能有兩個新舊節(jié)點相同時才會發(fā)生，只要有一個節(jié)點發(fā)生改變或者順序發(fā)生大幅調(diào)整，最后 都會有一個節(jié)點數(shù)組起始索引和末尾索引無法閉合。

那么此時就需要對剩余元素進(jìn)行處理：

• 舊節(jié)點數(shù)組遍歷結(jié)束、新節(jié)點數(shù)組仍有剩余，則遍歷新節(jié)點數(shù)組剩余數(shù)據(jù)，分別創(chuàng)建節(jié)點并插入到舊末尾索引對應(yīng)節(jié)點之前
• 新節(jié)點數(shù)組遍歷結(jié)束、舊節(jié)點數(shù)組仍有剩余，則遍歷舊節(jié)點數(shù)組剩余數(shù)據(jù)，分別從節(jié)點數(shù)組和 dom 樹中移除

即：

小結(jié)

Vue 2 的 diff 算法相對于簡單 diff 算法來說，通過 雙端對比與生成索引 map 兩種方式 減少了簡單算法中的多次循環(huán)操作，新舊數(shù)組均只需要進(jìn)行一次遍歷即可將所有節(jié)點進(jìn)行對比。

The double-end comparison will perform four comparisons and moves respectively, and the performance is not the optimal solution, so Vue 3 introduced the Longest Increasing Subsequence method to replace the double-end comparison. , while the rest still uses space expansion to reduce time complexity by converting it into an index map, thereby further improving computing performance.

Of course, the real dom node of elm corresponding to vnode is not given in the figure of this article. The mobile relationship between the two may cause misunderstandings. It is recommended to read it together with "Vue.js Design and Implementation".

The overall process is as follows:

(Learning video sharing: vuejs introductory tutorial, Programming Basic video)

The above is the detailed content of Quickly understand the Vue2 diff algorithm (detailed graphic explanation). For more information, please follow other related articles on the PHP Chinese website!