Vue diff 算法

一、虚拟 DOM （virtual dom）

　　diff 算法首先要明确一个概念就是 diff 的对象是虚拟DOM（virtual dom），更新真实 DOM 是 diff 算法的结果。

　　注：virtual dom 可以看作是一个使用 JavaScript 模拟了 DOM结构的树形结构，这个树结构包含整个DOM结构的信息

二、为什么使用 diff 算法？

　　1、页面结构庞大时，DOM 操作代价太高，可维护性差，因此要减少 DOM 操作；

　　2、虚拟 DOM 很轻量，对虚拟 DOM 操作快；

　　3、diff 算法是找出本次 DOM 需要更新的节点进行更新，其余不更新，对 DOM 进行原地复用，减少 DOM 创建性能耗费，可以减少浏览器页面的重绘。

三、diff 算法原理

　　1、patch 原理

　　源码

　　patch函数接收6个参数：

oldVnode: 旧的虚拟节点或旧的真实dom节点
vnode: 新的虚拟节点
hydrating: 是否要跟真是dom混合
removeOnly: 特殊flag，用于组件
parentElm: 父节点
refElm: 新节点将插入到refElm之前

　　patch的逻辑是：

if vnode不存在但是oldVnode存在，说明意图是要销毁老节点，那么就调用invokeDestroyHook(oldVnode)来进行销
if oldVnode不存在但是vnode存在，说明意图是要创建新节点，那么就调用createElm来创建新节点
else 当vnode和oldVnode都存在时

if oldVnode和vnode是同一个节点，就调用patchVnode来进行patch
当vnode和oldVnode不是同一个节点时，如果oldVnode是真实dom节点或hydrating设置为true，需要用hydrate函数将虚拟dom和真是dom进行映射，然后将oldVnode设置为对应的虚拟dom，找到oldVnode.elm的父节点，根据vnode创建一个真实dom节点并插入到该父节点中oldVnode.elm的位置

　　代码如下：

1function patch (oldVnode, vnode, hydrating, removeOnly, parentElm, refElm) {
2    /*vnode不存在则直接调用销毁钩子*/
3    if (isUndef(vnode)) {
4      if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
5      return
6    }
7
8    let isInitialPatch = false
9    const insertedVnodeQueue = []
10
11    if (isUndef(oldVnode)) {
12      // empty mount (likely as component), create new root element
13      /*oldVnode未定义的时候，其实也就是root节点，创建一个新的节点*/
14      isInitialPatch = true
15      createElm(vnode, insertedVnodeQueue, parentElm, refElm)
16    } else {
17      /*标记旧的VNode是否有nodeType*/
18      const isRealElement = isDef(oldVnode.nodeType)
19      if (!isRealElement && sameVnode(oldVnode, vnode)) {
20        // patch existing root node
21        /*是同一个节点的时候直接修改现有的节点*/
22        patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly)
23      } else {
24        if (isRealElement) {
25          // mounting to a real element
26          // check if this is server-rendered content and if we can perform
27          // a successful hydration.
28          if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
29            /*当旧的VNode是服务端渲染的元素，hydrating记为true*/
30            oldVnode.removeAttribute(SSR_ATTR)
31            hydrating = true
32          }
33          if (isTrue(hydrating)) {
34            /*需要合并到真实Dom上*/
35            if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
36              /*调用insert钩子*/
37              invokeInsertHook(vnode, insertedVnodeQueue, true)
38              return oldVnode
39            } else if (process.env.NODE_ENV !== 'production') {
40              warn(
41                'The client-side rendered virtual DOM tree is not matching ' +
42                'server-rendered content. This is likely caused by incorrect ' +
43                'HTML markup, for example nesting block-level elements inside ' +
44                '<p>, or missing <tbody>. Bailing hydration and performing ' +
45                'full client-side render.'
46              )
47            }
48          }
49          // either not server-rendered, or hydration failed.
50          // create an empty node and replace it
51          /*如果不是服务端渲染或者合并到真实Dom失败，则创建一个空的VNode节点替换它*/
52          oldVnode = emptyNodeAt(oldVnode)
53        }
54        // replacing existing element
55        /*取代现有元素*/
56        const oldElm = oldVnode.elm
57        const parentElm = nodeOps.parentNode(oldElm)
58        createElm(
59          vnode,
60          insertedVnodeQueue,
61          // extremely rare edge case: do not insert if old element is in a
62          // leaving transition. Only happens when combining transition +
63          // keep-alive + HOCs. (#4590)
64          oldElm._leaveCb ? null : parentElm,
65          nodeOps.nextSibling(oldElm)
66        )
67
68        if (isDef(vnode.parent)) {
69          // component root element replaced.
70          // update parent placeholder node element, recursively
71          /*组件根节点被替换，遍历更新父节点element*/
72          let ancestor = vnode.parent
73          while (ancestor) {
74            ancestor.elm = vnode.elm
75            ancestor = ancestor.parent
76          }
77          if (isPatchable(vnode)) {
78            /*调用create回调*/
79            for (let i = 0; i < cbs.create.length; ++i) {
80              cbs.create[i](emptyNode, vnode.parent)
81            }
82          }
83        }
84
85        if (isDef(parentElm)) {
86          /*移除老节点*/
87          removeVnodes(parentElm, [oldVnode], 0, 0)
88        } else if (isDef(oldVnode.tag)) {
89          /*调用destroy钩子*/
90          invokeDestroyHook(oldVnode)
91        }
92      }
93    }
94
95    /*调用insert钩子*/
96    invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
97    return vnode.elm
98  }

View Code

　　patchVnode的逻辑是：

如果oldVnode跟vnode完全一致，那么不需要做任何事情
如果oldVnode跟vnode都是静态节点，且具有相同的key，当vnode是克隆节点或是v-once指令控制的节点时，只需要把oldVnode.elm和oldVnode.child都复制到vnode上，也不用再有其他操作
否则，如果vnode不是文本节点或注释节点
- 如果oldVnode和vnode都有子节点，且2方的子节点不完全一致，就执行updateChildren
- 如果只有oldVnode有子节点，那就把这些节点都删除
- 如果只有vnode有子节点，那就创建这些子节点
- 如果oldVnode和vnode都没有子节点，但是oldVnode是文本节点或注释节点，就把vnode.elm的文本设置为空字符串
如果vnode是文本节点或注释节点，但是vnode.text != oldVnode.text时，只需要更新vnode.elm的文本内容就可以

1/*patch VNode节点*/
2  function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
3    /*两个VNode节点相同则直接返回*/
4    if (oldVnode === vnode) {
5      return
6    }
7    // reuse element for static trees.
8    // note we only do this if the vnode is cloned -
9    // if the new node is not cloned it means the render functions have been
10    // reset by the hot-reload-api and we need to do a proper re-render.
11    /*
12      如果新旧VNode都是静态的，同时它们的key相同（代表同一节点），
13      并且新的VNode是clone或者是标记了once（标记v-once属性，只渲染一次），
14      那么只需要替换elm以及componentInstance即可。
15    */
16    if (isTrue(vnode.isStatic) &&
17        isTrue(oldVnode.isStatic) &&
18        vnode.key === oldVnode.key &&
19        (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))) {
20      vnode.elm = oldVnode.elm
21      vnode.componentInstance = oldVnode.componentInstance
22      return
23    }
24    let i
25    const data = vnode.data
26    if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
27      /*i = data.hook.prepatch，如果存在的话，见"./create-component componentVNodeHooks"。*/
28      i(oldVnode, vnode)
29    }
30    const elm = vnode.elm = oldVnode.elm
31    const oldCh = oldVnode.children
32    const ch = vnode.children
33    if (isDef(data) && isPatchable(vnode)) {
34      /*调用update回调以及update钩子*/
35      for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
36      if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)
37    }
38    /*如果这个VNode节点没有text文本时*/
39    if (isUndef(vnode.text)) {
40      if (isDef(oldCh) && isDef(ch)) {
41        /*新老节点均有children子节点，则对子节点进行diff操作，调用updateChildren*/
42        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
43      } else if (isDef(ch)) {
44        /*如果老节点没有子节点而新节点存在子节点，先清空elm的文本内容，然后为当前节点加入子节点*/
45        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
46        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
47      } else if (isDef(oldCh)) {
48        /*当新节点没有子节点而老节点有子节点的时候，则移除所有ele的子节点*/
49        removeVnodes(elm, oldCh, 0, oldCh.length - 1)
50      } else if (isDef(oldVnode.text)) {
51        /*当新老节点都无子节点的时候，只是文本的替换，因为这个逻辑中新节点text不存在，所以直接去除ele的文本*/
52        nodeOps.setTextContent(elm, '')
53      }
54    } else if (oldVnode.text !== vnode.text) {
55      /*当新老节点text不一样时，直接替换这段文本*/
56      nodeOps.setTextContent(elm, vnode.text)
57    }
58    /*调用postpatch钩子*/
59    if (isDef(data)) {
60      if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
61    }
62  }

View Code

　　updataChildren原理：

1function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
2    let oldStartIdx = 0 // 旧头索引
3    let newStartIdx = 0 // 新头索引
4    let oldEndIdx = oldCh.length - 1 // 旧尾索引
5    let newEndIdx = newCh.length - 1 // 新尾索引
6    let oldStartVnode = oldCh[0] // oldVnode的第一个child
7    let oldEndVnode = oldCh[oldEndIdx] // oldVnode的最后一个child
8    let newStartVnode = newCh[0] // newVnode的第一个child
9    let newEndVnode = newCh[newEndIdx] // newVnode的最后一个child
10    let oldKeyToIdx, idxInOld, vnodeToMove, refElm
11
12    // removeOnly is a special flag used only by <transition-group>
13    // to ensure removed elements stay in correct relative positions
14    // during leaving transitions
15    const canMove = !removeOnly
16
17    // 如果oldStartVnode和oldEndVnode重合，并且新的也都重合了，证明diff完了，循环结束
18    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
19      // 如果oldVnode的第一个child不存在
20      if (isUndef(oldStartVnode)) {
21        // oldStart索引右移
22        oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
23
24      // 如果oldVnode的最后一个child不存在
25      } else if (isUndef(oldEndVnode)) {
26        // oldEnd索引左移
27        oldEndVnode = oldCh[--oldEndIdx]
28
29      // oldStartVnode和newStartVnode是同一个节点
30      } else if (sameVnode(oldStartVnode, newStartVnode)) {
31        // patch oldStartVnode和newStartVnode， 索引左移，继续循环
32        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
33        oldStartVnode = oldCh[++oldStartIdx]
34        newStartVnode = newCh[++newStartIdx]
35
36      // oldEndVnode和newEndVnode是同一个节点
37      } else if (sameVnode(oldEndVnode, newEndVnode)) {
38        // patch oldEndVnode和newEndVnode，索引右移，继续循环
39        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
40        oldEndVnode = oldCh[--oldEndIdx]
41        newEndVnode = newCh[--newEndIdx]
42
43      // oldStartVnode和newEndVnode是同一个节点
44      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
45        // patch oldStartVnode和newEndVnode
46        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
47        // 如果removeOnly是false，则将oldStartVnode.eml移动到oldEndVnode.elm之后
48        canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
49        // oldStart索引右移，newEnd索引左移
50        oldStartVnode = oldCh[++oldStartIdx]
51        newEndVnode = newCh[--newEndIdx]
52
53      // 如果oldEndVnode和newStartVnode是同一个节点
54      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
55        // patch oldEndVnode和newStartVnode
56        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
57        // 如果removeOnly是false，则将oldEndVnode.elm移动到oldStartVnode.elm之前
58        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
59        // oldEnd索引左移，newStart索引右移
60        oldEndVnode = oldCh[--oldEndIdx]
61        newStartVnode = newCh[++newStartIdx]
62
63      // 如果都不匹配
64      } else {
65        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
66
67        // 尝试在oldChildren中寻找和newStartVnode的具有相同的key的Vnode
68        idxInOld = isDef(newStartVnode.key)
69          ? oldKeyToIdx[newStartVnode.key]
70          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
71
72        // 如果未找到，说明newStartVnode是一个新的节点
73        if (isUndef(idxInOld)) { // New element
74          // 创建一个新Vnode
75          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
76
77        // 如果找到了和newStartVnodej具有相同的key的Vnode，叫vnodeToMove
78        } else {
79          vnodeToMove = oldCh[idxInOld]
80          /* istanbul ignore if */
81          if (process.env.NODE_ENV !== 'production' && !vnodeToMove) {
82            warn(
83              'It seems there are duplicate keys that is causing an update error. ' +
84              'Make sure each v-for item has a unique key.'
85            )
86          }
87
88          // 比较两个具有相同的key的新节点是否是同一个节点
89          //不设key，newCh和oldCh只会进行头尾两端的相互比较，设key后，除了头尾两端的比较外，还会从用key生成的对象oldKeyToIdx中查找匹配的节点，所以为节点设置key可以更高效的利用dom。
90          if (sameVnode(vnodeToMove, newStartVnode)) {
91            // patch vnodeToMove和newStartVnode
92            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)
93            // 清除
94            oldCh[idxInOld] = undefined
95            // 如果removeOnly是false，则将找到的和newStartVnodej具有相同的key的Vnode，叫vnodeToMove.elm
96            // 移动到oldStartVnode.elm之前
97            canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
98
99          // 如果key相同，但是节点不相同，则创建一个新的节点
100          } else {
101            // same key but different element. treat as new element
102            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
103          }
104        }
105
106        // 右移
107        newStartVnode = newCh[++newStartIdx]
108      }
109    }

View Code

一、虚拟 DOM （virtual dom）

二、为什么使用 diff 算法？

三、diff 算法原理

1、patch 原理

源码

patch函数接收6个参数：

patch的逻辑是：

patchVnode的逻辑是：

updataChildren原理：

随笔整理自

https://www.jianshu.com/p/bf9a8b4773ee

https://segmentfault.com/a/1190000008782928

https://www.cnblogs.com/isLiu/p/7909889.html

https://www.cnblogs.com/answershuto/p/7545143.html

感谢博主分享！

评论区

相关推荐