vue中的diff算法

朴灿烈づ我的快乐病毒、 2023-01-07 07:06 265阅读 0赞

一、是什么diff算法

先来一句概念：

diff算法就是进行虚拟节点对比，并返回一个patch对象，用来存储两个节点不同的地方，最后用patch记录的消息去局部更新Dom。

换句人话

diff的过程就是调用名为patch的函数，比较新旧节点，一边比较一边给真实的DOM打补丁

其有两个特点：

  • 比较只会在同层级进行, 不会跨层级比较
  • 在diff比较的过程中，循环从两边向中间比较

diff 算法的在很多场景下都有应用，在 vue 中，作用于虚拟 dom 渲染成真实 dom 的新旧 VNode 节点比较

废话说了很多，上图
　　在这里插入图片描述
　多说无益，再来一张图
　在这里插入图片描述
这个Diff的过程不展开说了，有兴趣的童鞋可以走起，如果还没懂，再走起

Diff算法的步骤：

  • 用 JavaScript 对象结构表示 DOM 树的结构；然后用这个树构建一个真正的 DOM 树，插到文 档当中
  • 当状态变更的时候，重新构造一棵新的对象树。然后用新的树和旧的树进行比较(diff)，记录两棵树差异
  • 把第二棵树所记录的差异应用到第一棵树所构建的真正的DOM树上(patch)，视图就更新了

二、比较方式

diff整体策略为：深度优先，同层比较

  1. 比较只会在同层级进行, 不会跨层级比较
    在这里插入图片描述
  2. 比较的过程中，循环从两边向中间收拢
    在这里插入图片描述
    下面举个vue通过diff算法更新的例子：

新旧VNode节点如下图所示：
在这里插入图片描述
第一次循环后，发现旧节点D与新节点D相同，直接复用旧节点D作为diff后的第一个真实节点，同时旧节点endIndex移动到C，新节点的 startIndex 移动到了 C
在这里插入图片描述
第二次循环后，同样是旧节点的末尾和新节点的开头(都是 C)相同，同理，diff 后创建了 C 的真实节点插入到第一次创建的 B 节点后面。同时旧节点的 endIndex 移动到了 B，新节点的 startIndex 移动到了 E
在这里插入图片描述
第三次循环中，发现E没有找到，这时候只能直接创建新的真实节点 E，插入到第二次创建的 C 节点之后。同时新节点的 startIndex 移动到了 A。旧节点的 startIndex 和 endIndex 都保持不动

在这里插入图片描述
第四次循环中，发现了新旧节点的开头(都是 A)相同，于是 diff 后创建了 A 的真实节点，插入到前一次创建的 E 节点后面。同时旧节点的 startIndex 移动到了 B，新节点的startIndex 移动到了 B
在这里插入图片描述
第五次循环中，情形同第四次循环一样，因此 diff 后创建了 B 真实节点 插入到前一次创建的 A 节点后面。同时旧节点的 startIndex移动到了 C，新节点的 startIndex 移动到了 F
在这里插入图片描述
新节点的 startIndex 已经大于 endIndex 了，需要创建 newStartIdx 和 newEndIdx 之间的所有节点，也就是节点F，直接创建 F 节点对应的真实节点放到 B 节点后面
在这里插入图片描述
三、原理分析
当数据发生改变时，set方法会调用Dep.notify通知所有订阅者Watcher，订阅者就会调用patch给真实的DOM打补丁，更新相应的视图

源码位置：patch.js

  1. function patch(oldVnode, vnode, hydrating, removeOnly) { 
  2.     if (isUndef(vnode)) {  // 没有新节点，直接执行destory钩子函数
  3.         if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
  4.         return
  5.     }
  7.     let isInitialPatch = false
  8.     const insertedVnodeQueue = []
  10.     if (isUndef(oldVnode)) { 
  11.         isInitialPatch = true
  12.         createElm(vnode, insertedVnodeQueue) // 没有旧节点，直接用新节点生成dom元素
  13.     } else { 
  14.         const isRealElement = isDef(oldVnode.nodeType)
  15.         if (!isRealElement && sameVnode(oldVnode, vnode)) { 
  16.             // 判断旧节点和新节点自身一样，一致执行patchVnode
  17.             patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
  18.         } else { 
  19.             // 否则直接销毁及旧节点，根据新节点生成dom元素
  20.             if (isRealElement) { 
  22.                 if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) { 
  23.                     oldVnode.removeAttribute(SSR_ATTR)
  24.                     hydrating = true
  25.                 }
  26.                 if (isTrue(hydrating)) { 
  27.                     if (hydrate(oldVnode, vnode, insertedVnodeQueue)) { 
  28.                         invokeInsertHook(vnode, insertedVnodeQueue, true)
  29.                         return oldVnode
  30.                     }
  31.                 }
  32.                 oldVnode = emptyNodeAt(oldVnode)
  33.             }
  34.             return vnode.elm
  35.         }
  36.     }
  37. }

patch函数前两个参数位为oldVnode 和 Vnode ，分别代表新的节点和之前的旧节点，主要做了四个判断：

  • 没有新节点，直接触发旧节点的destory钩子
  • 没有旧节点，说明是页面刚开始初始化的时候，此时，根本不需要比较了，直接全是新建，所以只调用 createElm
  • 旧节点和新节点自身一样，通过 sameVnode 判断节点是否一样，一样时，直接调用 patchVnode去处理这两个节点
  • 旧节点和新节点自身不一样，当两个节点不一样的时候，直接创建新节点，删除旧节点

下面主要讲的是patchVnode部分

  1. function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) { 
  2.     // 如果新旧节点一致，什么都不做
  3.     if (oldVnode === vnode) { 
  4.       return
  5.     }
  7.     // 让vnode.el引用到现在的真实dom，当el修改时，vnode.el会同步变化
  8.     const elm = vnode.elm = oldVnode.elm
  10.     // 异步占位符
  11.     if (isTrue(oldVnode.isAsyncPlaceholder)) { 
  12.       if (isDef(vnode.asyncFactory.resolved)) { 
  13.         hydrate(oldVnode.elm, vnode, insertedVnodeQueue)
  14.       } else { 
  15.         vnode.isAsyncPlaceholder = true
  16.       }
  17.       return
  18.     }
  19.     // 如果新旧都是静态节点，并且具有相同的key
  20.     // 当vnode是克隆节点或是v-once指令控制的节点时，只需要把oldVnode.elm和oldVnode.child都复制到vnode上
  21.     // 也不用再有其他操作
  22.     if (isTrue(vnode.isStatic) &&
  23.       isTrue(oldVnode.isStatic) &&
  24.       vnode.key === oldVnode.key &&
  25.       (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
  26.     ) { 
  27.       vnode.componentInstance = oldVnode.componentInstance
  28.       return
  29.     }
  31.     let i
  32.     const data = vnode.data
  33.     if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) { 
  34.       i(oldVnode, vnode)
  35.     }
  37.     const oldCh = oldVnode.children
  38.     const ch = vnode.children
  39.     if (isDef(data) && isPatchable(vnode)) { 
  40.       for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
  41.       if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)
  42.     }
  43.     // 如果vnode不是文本节点或者注释节点
  44.     if (isUndef(vnode.text)) { 
  45.       // 并且都有子节点
  46.       if (isDef(oldCh) && isDef(ch)) { 
  47.         // 并且子节点不完全一致，则调用updateChildren
  48.         if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
  50.         // 如果只有新的vnode有子节点
  51.       } else if (isDef(ch)) { 
  52.         if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
  53.         // elm已经引用了老的dom节点，在老的dom节点上添加子节点
  54.         addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
  56.         // 如果新vnode没有子节点，而vnode有子节点，直接删除老的oldCh
  57.       } else if (isDef(oldCh)) { 
  58.         removeVnodes(elm, oldCh, 0, oldCh.length - 1)
  60.         // 如果老节点是文本节点
  61.       } else if (isDef(oldVnode.text)) { 
  62.         nodeOps.setTextContent(elm, '')
  63.       }
  65.       // 如果新vnode和老vnode是文本节点或注释节点
  66.       // 但是vnode.text != oldVnode.text时，只需要更新vnode.elm的文本内容就可以
  67.     } else if (oldVnode.text !== vnode.text) { 
  68.       nodeOps.setTextContent(elm, vnode.text)
  69.     }
  70.     if (isDef(data)) { 
  71.       if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
  72.     }
  73.   }

patchVnode主要做了几个判断：

  • 新节点是否是文本节点，如果是，则直接更新dom的文本内容为新节点的文本内容
  • 新节点和旧节点如果都有子节点，则处理比较更新子节点
  • 只有新节点有子节点，旧节点没有，那么不用比较了，所有节点都是全新的，所以直接全部新建就好了，新建是指创建出所有新DOM，并且添加进父节点

  • 只有旧节点有子节点而新节点没有，说明更新后的页面，旧节点全部都不见了，那么要做的，就是把所有的旧节点删除，也就是直接把DOM 删除
    子节点不完全一致，则调用updateChildren

    function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) { 

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

while循环主要处理了以下五种情景：

  • 当新老 VNode 节点的 start 相同时，直接 patchVnode ，同时新老 VNode 节点的开始索引都加 1
  • 当新老 VNode 节点的 end相同时，同样直接 patchVnode ，同时新老 VNode 节点的结束索引都减 1
  • 当老 VNode 节点的 start 和新 VNode 节点的 end 相同时，这时候在 patchVnode 后，还需要将当前真实 dom 节点移动到 oldEndVnode 的后面，同时老 VNode 节点开始索引加 1，新 VNode 节点的结束索引减 1
  • 当老 VNode 节点的 end 和新 VNode 节点的 start 相同时，这时候在 patchVnode 后，还需要将当前真实 dom 节点移动到 oldStartVnode 的前面，同时老 VNode 节点结束索引减 1，新 VNode 节点的开始索引加 1
  • 如果都不满足以上四种情形，那说明没有相同的节点可以复用，则会分为以下两种情况：
  • 从旧的 VNode 为 key 值，对应 index 序列为 value 值的哈希表中找到与 newStartVnode 一致 key 的旧的 VNode 节点，再进行patchVnode，同时 将这个真实 dom移动到 oldStartVnode 对应的真实 dom 的前面
  • 调用 createElm 创建一个新的 dom 节点放到当前 newStartIdx 的位置

小结

  • 当数据发生改变时，订阅者watcher就会调用patch给真实的DOM打补丁
  • 通过isSameVnode进行判断，相同则调用patchVnode方法

  • patchVnode做了以下操作：

    • 找到对应的真实dom，称为el
    • 如果都有都有文本节点且不相等，将el文本节点设置为Vnode的文本节点
    • 如果oldVnode有子节点而VNode没有，则删除el子节点
    • 如果oldVnode没有子节点而VNode有，则将VNode的子节点真实化后添加到el
    • 如果两者都有子节点，则执行updateChildren函数比较子节点

  • updateChildren主要做了以下操作：

    • 设置新旧VNode的头尾指针
    • 新旧头尾指针进行比较，循环向中间靠拢，根据情况调用patchVnode进行patch重复流程、调用createElem创建一个新节点，从哈希表寻找 key一致的VNode 节点再分情况操作

发表评论

表情：
评论列表 （有 0 条评论，265人围观）

还没有评论，来说两句吧...

相关阅读

    相关 介绍一下Vue中的Diff算法？

    在新老虚拟DOM对比时 首先，对比节点本身，判断是否为同一节点，如果不为相同节点，则删除该节点重新创建节点进行替换 如果为相同节点，进行patchVnode，判断如何对...

    朱雀朱雀/ 0 赞/ 549 阅读