Vue diff算法核心

前言：个人对算法和原理比较感兴趣，以此文做一个diff算法的研究记录

目录大纲：

  1. 作为一个算法，时间复杂度如何？
    1. 首先弄清楚算法处理的对象是什么？
    2. 为什么不直接diff真实dom树？
    3. 想达到什么结果？（diff核心用处）
    4. 为什么不直接把整个newVnode都更新到页面上，而要保留原来的相同的vnode？
  2. 算法在哪些情况下时间复杂度是O（n），哪些情况下是O（n平方）？
  3. diff提高性能的关键
  4. 算法解析

1. 作为一个算法，时间复杂度如何？

  1. 首先弄清楚算法处理的对象是什么？
    处理对象是：2棵树（虚拟dom树），oldVnode和newVnode，是js的对象，和真实的dom树是一一映射的
    • 实际就是对比2个js对象，对象是树结构，子元素在children里面。子元素的子元素 在 子元素的children里面(ÒܫÓױ)
      vnode如图：
      vnode如图：
      vnode.png

树结构
tree.pmg.png

  1. 为什么不直接diff真实dom树？
    1. 真实的dom树很大很重，遍历起来很慢（对比遍历js对象）
    2. 操作dom的api是jsdom api，速度很慢，比js本身的方法要慢很多
  2. 想达到什么结果？（diff核心用处）
    高效的对比oldVnode和newVnode，得到diff差异，然后update到页面上
    • 顺带高效的解决一些table的行排序性能问题（可以确保都是最优化的解决dom元素变更的代码书写）
  3. 为什么不直接把整个newVnode都更新到页面上，而要保留原来的相同的vnode？
    因为dom是很重很大的，能不动就不动，能update最好update。如果直接删掉原来的，在create一个新的dom比update或不动要慢很多

2. 算法在哪些情况下时间复杂度是O（n），哪些情况下是O（n平方）？

  1. 首先2棵树（有N层），对比差异，最优的是时间复杂度是O（n），就是层层对比（比如第一层和第一层比、第二层和第二层比、第n层和第n层比），diff算法是这么写的吗？
    diff算法就是层层对比的，因为dom结构一般来说，不会有大改，这样遍历效率最高
  2. 新旧树之间同层是怎么对比的？（比如第三层和第三层比）
    首先肯定也是“层层对比”最快，比如第一个和第一个比，第二个和第二个比，这样 时间复杂度是O（n），但这样一旦第一个和第一个不同，这样容易全乱了。
    所以：diff算法对同层对比还做了优化，用了双指针，会从4个方向去遍历！
    • 分别是：前前对比，前后对比，后前对比，后后对比 （前指的是第一个元素 index === 0, 后指的最后一个元素 index === array.length - 1）

新旧树之间同层 前前对比，前后对比，后前对比，后后对比 对应场景：

  • 假设 旧vnode的第二层是 [1, 2, 3]
  • 适合前前对比的场景（尾部元素被操作了）：新vnode是 [1, 2, 3, 4] 或 [1, 2] 的情况
  • 适合后后对比的场景（前部元素被操作了）：新vnode是 [2, 3] 或 [0, 1, 2, 3] 的情况
  • 适合前后对比的场景（元素被逆序了）：新vnode是 [2, 1] 或 [3, 2, 1] 的情况
  • 适合后前对比的场景（元素被逆序了）：新vnode是 [2, 1] 或 [3, 2, 1] 的情况
    1. 如果当前层 前前，前后，后前，后后 都没有相同的情况，diff算法会怎么处理？
      比如oldVnode是[1, 2, 3]，newVnode是[7, 8, 9]
  • 会遍历当前层的旧vnode，然后生成一个map，map里面保存的是key（v-for处的:key，所以:key对性能提升很明显）
  • 如果没有key，那就性能就不好了，会去遍历旧vnode。（此时 时间复杂度是n平方）
    • if 找到了sameVnode，就不动或者update一些内容（比如class，domListerner，text内容，属性等）。（重新创建dom是比较重的，能update，就update。）
    • else 没找到，就会createElm

所以对于开发者来说，如果有dom会频繁变更，那么一定要加上:key，性能就会很好

3. diff提高性能的关键

  1. 用js对象形成vnode表示真实dom，操作js比操作dom快太多
  2. v-for生成的table或list。对old vnode 做了一层缓存，然后用:key去匹配新旧vnode，大大节省了对比新旧dom节点的时间
  3. 由于创建dom是很重的，可以的话 最好能利用原来的dom。 比如 insertBefore或update 肯定比 replaceChild + createElement 要快
  4. 新旧树之间一层一层对比，大多数情况时间复杂度是n，最差的情况是n平方，写了:key的话就是一定是n。（n表示时间复杂度）
    • 因为dom层级结构一般不会大变（大多数情况时间复杂度是n）
    • 如果是table各种筛选排序的这种 dom位置变换的很多情况，写v-for的时候 必须要带:key，然后diff算法会匹配key，且有key的map缓存，速度很快

4. 算法解析

  1. 递归
    • 先对比当前vnode，然后存在children的话，递归在对比children vnode
  2. 新旧树之间一层一层对比，时间复杂度n。
    • 因为dom层级结构一般不会大变
    • 如果是table各种筛选排序的这种 dom位置变换的很多情况，写v-for的时候 必须要带:key，然后diff算法会匹配key，且有key的map缓存，速度很快
  3. while循环
    1. 先各种顺序遍历，看看新旧vnode是否是sameVnode:
      1. oldStartVnode, newStartVnode 旧前新前
      2. oldEndVnode, newEndVnode 旧后新后
      3. oldStartVnode, newEndVnode 旧前新后
      4. oldEndVnode, newStartVnode 旧后新前
    2. 以上各种顺序都不是sameVnode的话，
      • 会遍历当前层的旧vnode，然后生成一个map，map里面保存的是key（v-for处的:key，所以:key对性能提升很明显）
      • 如果没有key，那就性能就不好了，会去遍历旧vnode。（此时 时间复杂度是n平方）
        • if 找到了sameVnode，就不动或者update一些内容（比如class，domListerner，text内容，属性等）。（重新创建dom是比较重的，能update，就update。）
        • else 没找到，就会createElm
  4. 出了while循环（已经一层一层的遍历对比完新旧的vnode后），还有2种情况
    1. if (oldStartIdx > oldEndIdx) 说明 newVnode 比 oldVnode 多. 存在没遍历到的new vnode, 后面就直接addVnode（createElement）
    2. else if (newStartIdx > newEndIdx) 此处情况是: newVnode 比 oldVnode 少的情况, 删除原页面上的一些old vnode。（removeChild）
  5. 以下是diff算法核心源码，附带详细注释 
  1. /* 传参：
  2.     parentElm：父元素的dom。
  3.     oldCh 旧的vnode（虚拟dom，用js对象标示的dom树）。
  4.     newCh：新的vnode
  5.     insertedVnodeQueue（此处不用关心这个）：作用：延迟为组件根节点插入钩子，在元素真正插入后调用它们
  6.     removeOnly（此处不用太关心这个）：是一个特殊标志，仅由 <transition-group> 使用，以确保移除的元素在离开过渡期间保持在正确的相对位置
  7. */
  8. function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
  9.   var oldStartIdx = 0; // oldCh 起点 index
  10.   var newStartIdx = 0; // newCh 起点 index
  11.   var oldEndIdx = oldCh.length - 1; // oldCh 终点 index
  12.   var oldStartVnode = oldCh[0];
  13.   var oldEndVnode = oldCh[oldEndIdx];
  14.   var newEndIdx = newCh.length - 1; // newCh 终点 index
  15.   var newStartVnode = newCh[0];
  16.   var newEndVnode = newCh[newEndIdx];
  17.   var oldKeyToIdx, idxInOld, vnodeToMove, refElm;
  19.   // removeOnly is a special flag used only by <transition-group>
  20.   // to ensure removed elements stay in correct relative positions
  21.   // during leaving transitions
  22.   var canMove = !removeOnly;
  24.   if (process.env.NODE_ENV !== 'production') {
  25.     checkDuplicateKeys(newCh) // dev环境会的一个报错，:key的值 不能重复
  26.   }
  28.   // 开始进入diff算法核心部分，里面是递归
  29.   while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  30.     if (isUndef(oldStartVnode)) { // 判断oldVnode是否存在(这个函数是处理child的（递归进来的）) 作为后续的退出while循环的操作
  31.       oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
  32.     } else if (isUndef(oldEndVnode)) { // 同上（下面不止 有顺序 还有逆序）
  33.       oldEndVnode = oldCh[--oldEndIdx];
  34.     } else if (sameVnode(oldStartVnode, newStartVnode)) { // (旧前新前 对比) sameVnode() 判断Vnode是否相等。（规则: 1. 主要是判断key是否相等（:key）） 2. ...下面有写这个方法 ）
  35.       // 里面还是会递归回到 updateChildren
  36.       // 执行patchVnode最终还是回到updateChildren去递归（下一轮是匹配children的diff）（往下看，有写这个方法）
  37.       patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx); // 跑完一个child, 就跑下一个child
  38.       oldStartVnode = oldCh[++oldStartIdx];
  39.       newStartVnode = newCh[++newStartIdx];
  40.     } else if (sameVnode(oldEndVnode, newEndVnode)) { // (旧后新后 对比)
  41.       // 注解同上
  42.       patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);
  43.       oldEndVnode = oldCh[--oldEndIdx];
  44.       newEndVnode = newCh[--newEndIdx];
  45.     } else if (sameVnode(oldStartVnode, newEndVnode)) { // (旧前新后 对比) (倒序对比, 场景table根据索引 倒序 重排序) Vnode moved right
  46.       // 注解同上
  47.       patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);
  48.       canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm)); // 直接把oldNode的dom插入到新的elm去就行, 因为sameNode
  49.       oldStartVnode = oldCh[++oldStartIdx];
  50.       newEndVnode = newCh[--newEndIdx];
  51.     } else if (sameVnode(oldEndVnode, newStartVnode)) { // (旧后新前 对比) (倒序对比, 场景table根据索引 倒序 重排序) Vnode moved left
  52.       // 注解同上
  53.       patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
  54.       canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm); // 直接把oldNode的dom插入到新的elm去就行, 因为sameNode
  55.       oldEndVnode = oldCh[--oldEndIdx];
  56.       newStartVnode = newCh[++newStartIdx];
  57.     } else { // 前前，前后，后前，后后 都没有相同的情况
  58.       // 缓存old vnode, 以key为键的map映射,
  59.       if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
  60.       idxInOld = isDef(newStartVnode.key) // 判断new vnode的key是否在old vnode的缓存map内
  61.         ? oldKeyToIdx[newStartVnode.key]
  62.         : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) // 没有key的话，就只能遍历oldVnode，看看是否是sameVnode
  63.       if (isUndef(idxInOld)) { //new vnode 和 old vnode 不是 sameVnode, 创建 New element
  64.         createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
  65.       } else { // 此时 new vnode 和 old vnode 是 sameVnode
  66.         vnodeToMove = oldCh[idxInOld]
  67.         if (sameVnode(vnodeToMove, newStartVnode)) { // 相同的vnode, 不用做删除和新增，只需做update（比如update：class，domListerner，text内容，属性等）, 然后递归对比children
  68.           patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
  69.           oldCh[idxInOld] = undefined
  70.           canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
  71.         } else { // key相同, 但不是sameVnode. 作为new element对待
  72.           createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
  73.         }
  74.       }
  75.       newStartVnode = newCh[++newStartIdx] // 顺序往一下
  76.     }
  77.   }
  78.   // 遍历对比完新旧的vnode后
  79.   if (oldStartIdx > oldEndIdx) { // 如果oldStartIdx > oldEndIdx, 说明 newVnode 比 oldVnode 多. 存在没遍历到的new vnode, 以下直接addVnode
  80.     refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm;
  81.     addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
  82.   } else if (newStartIdx > newEndIdx) { // 此处情况是: newVnode 比 oldVnode 少的情况, 删除原页面上的一些old vnode
  83.     removeVnodes(oldCh, oldStartIdx, oldEndIdx);
  84.   }
  85. }
  87. function checkDuplicateKeys (children) {
  88.   var seenKeys = {};
  89.   for (var i = 0; i < children.length; i++) {
  90.     var vnode = children[i];
  91.     var key = vnode.key;
  92.     if (isDef(key)) {
  93.       if (seenKeys[key]) {
  94.         warn(
  95.           ("Duplicate keys detected: '" + key + "'. This may cause an update error."),
  96.           vnode.context
  97.         );
  98.       } else {
  99.         seenKeys[key] = true;
  100.       }
  101.     }
  102.   }
  103. }
  104. function sameVnode (a, b) { // 判断规则: 1. key相等  2. ...  判断2个vnode是否相等
  105.   return (
  106.     a.key === b.key && (
  107.       (
  108.         a.tag === b.tag &&
  109.         a.isComment === b.isComment &&
  110.         isDef(a.data) === isDef(b.data) &&
  111.         sameInputType(a, b)
  112.       ) || (
  113.         isTrue(a.isAsyncPlaceholder) &&
  114.         a.asyncFactory === b.asyncFactory &&
  115.         isUndef(b.asyncFactory.error)
  116.       )
  117.     )
  118.   )
  119. }
  120. function patchVnode (oldVnode, vnode, insertedVnodeQueue, ownerArray, index, removeOnly) {
  121.   if (oldVnode === vnode) {
  122.     return
  123.   }
  124.   // 此中间删除了一些代码，简化思路
  125.   const elm = vnode.elm = oldVnode.elm
  126.   const oldCh = oldVnode.children
  127.   const ch = vnode.children
  128.   if (isUndef(vnode.text)) {
  129.     if (isDef(oldCh) && isDef(ch)) { // 最终还是回到updateChildren去递归（把判断children）
  130.       if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
  131.     } else if (isDef(ch)) {
  132.       if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
  133.       addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
  134.     } else if (isDef(oldCh)) {
  135.       removeVnodes(oldCh, 0, oldCh.length - 1)
  136.     } else if (isDef(oldVnode.text)) {
  137.       nodeOps.setTextContent(elm, '')
  138.     }
  139.   } else if (oldVnode.text !== vnode.text) {
  140.     nodeOps.setTextContent(elm, vnode.text)
  141.   }
  142. }
  144. function createKeyToOldIdx (children, beginIdx, endIdx) {
  145.   let i, key
  146.   const map = {}
  147.   for (i = beginIdx; i <= endIdx; ++i) {
  148.     key = children[i].key
  149.     if (isDef(key)) map[key] = i
  150.   }
  151.   return map
  152. }
  154. // 根据index判定, 如果新增node  则createElm
  155. function addVnodes (parentElm, refElm, vnodes, startIdx, endIdx, insertedVnodeQueue) {
  156.   for (; startIdx <= endIdx; ++startIdx) {
  157.     createElm(vnodes[startIdx], insertedVnodeQueue, parentElm, refElm, false, vnodes, startIdx);
  158.   }
  159. }
  160. function removeVnodes (vnodes, startIdx, endIdx) {
  161.   for (; startIdx <= endIdx; ++startIdx) {
  162.     var ch = vnodes[startIdx];
  163.     if (isDef(ch)) {
  164.       if (isDef(ch.tag)) {
  165.         removeAndInvokeRemoveHook(ch);
  166.         invokeDestroyHook(ch);
  167.       } else { // Text node
  168.         removeNode(ch.elm);
  169.       }
  170.     }
  171.   }
  172. }
  173. function removeNode (el) {
  174.   var parent = nodeOps.parentNode(el);
  175.   // element may have already been removed due to v-html / v-text
  176.   if (isDef(parent)) {
  177.     nodeOps.removeChild(parent, el);
  178.   }
  179. }

Vue diff算法核心 - 图3