笔记VueDiff算法分析

1次阅读

共计 3958 个字符，预计需要花费 10 分钟才能阅读完成。

为什么要应用 Virtual DOM？

将失去的变更告诉生成新的 Virtual DOM 树。将新的和旧的进行 diff patch 操作，缩小了间接通过 DOM API 去增删改查 DOM 的操作，进步开发效率。
All problem in computer science can be resolved by another level of indirection 软件开发中的所有问题都能够通过减少一层形象来解决。（关注点拆散）

Virtual DOM 是分层思维的一种体现

框架将 DOM 形象成 Virtual DOM 后能够利用在各个终端

1、按 tree 层级 diff（level by level）

在 Web UI 中很少会呈现 DOM 层级会因为交互而产生更新
在新旧节点之间按层级进行 diff

2、按类型进行 diff

不同类型的节点之间往往差别很大，为了晋升效率，只会对雷同类型节点进行 diff
不同类型会间接创立新类型节点，替换旧类型节点
下图中，由上一层图形变为下一层图形。同层比拟，第二列五角星和三角形不同，尽管子节点的两个五角星雷同，然而也会间接将三个五角星间接销毁，替换为新的节点。

3、列表 Diff

给列表元素设置 key，能够晋升效率

参考文章：详解 Vue 的 Diff 算法

  updateChildren(parentElm, oldCh, newCh) {
    let oldStartIdx = 0, newStartIdx = 0
    let oldEndIdx = oldCh.length - 1
    let oldStartVnode = oldCh[0]
    let oldEndVnode = oldCh[oldEndIdx]
    let newEndIdx = newCh.length - 1
    let newStartVnode = newCh[0]
    let newEndVnode = newCh[newEndIdx]
    let oldKeyToIdx
    let idxInOld
    let elmToMove
    let before
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {if (oldStartVnode == null) {   // 对于 vnode.key 的比拟，会把 oldVnode = null
        oldStartVnode = oldCh[++oldStartIdx]
      } else if (oldEndVnode == null) {oldEndVnode = oldCh[--oldEndIdx]
      } else if (newStartVnode == null) {newStartVnode = newCh[++newStartIdx]
      } else if (newEndVnode == null) {newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newStartVnode)) {patchVnode(oldStartVnode, newStartVnode)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) {patchVnode(oldEndVnode, newEndVnode)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) {patchVnode(oldStartVnode, newEndVnode)
        api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
        oldStartVnode = oldCh[++oldStartIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldEndVnode, newStartVnode)) {patchVnode(oldEndVnode, newStartVnode)
        api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        // 应用 key 时的比拟
        if (oldKeyToIdx === undefined) {oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // 有 key 生成 index 表
        }
        idxInOld = oldKeyToIdx[newStartVnode.key]
        if (!idxInOld) {api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
          newStartVnode = newCh[++newStartIdx]
        }
        else {elmToMove = oldCh[idxInOld]
          if (elmToMove.sel !== newStartVnode.sel) {api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
          } else {patchVnode(elmToMove, newStartVnode)
            oldCh[idxInOld] = null
            api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)
          }
          newStartVnode = newCh[++newStartIdx]
        }
      }
    }
    if (oldStartIdx > oldEndIdx) {before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
      addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
    } else if (newStartIdx > newEndIdx) {removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
  }

updateChildren 代码剖析

循环成立条件：OldStart 小于等于 OldEnd && NewStart 小于等于 NewEnd 时
判断 VNode 是否为 null，是指针指向下一个节点

不是则依照 OS 和 NS（S|）、OE 和 NE（E|）、OS 和 NE（\）、OE 和 NS（/）的程序进行比拟判断
若雷同

 S| 节点地位不变，指针 +1
 E| 节点地位不变，指针 -1
 \  OldStart 挪动到 OldEnd 之后，OldStart +1，NewEnd -1
 /  OldEnd 挪动到 OldStart 之前，NewStart +1，OldEnd -1

若不同，依据 key 生成 OldStart 和 OldEnd 之间的 index 表，查找元素是否在 OldStart 和 OldEnd 之间

 若有，间接挪动到 OldStart 前
 若没有，创立后，挪动到 OldStart 前

判断如果 NewStart > NewEnd，阐明新节点曾经遍历完，删除 OldStart 和 OldEnd 之间的 DOM
如果 OldStart > OldEnd，阐明旧节点曾经遍历完，将多的新节点依据 index 增加到 DOM 中去

例：如图，灰色示意 Virtual DOM 深色示意实在的 DOM

四个指针
- OldStartIdx 旧开始节点
- OldEndIdx 和旧完结节点
- NewStartIdx 新开始节点
- NewEndIdx 新完结节点

判断 OldStartIdx 和 NewStartIdx 是否雷同。1 和 1 雷同，两个 Start 指针都往右挪动一位（+1）
持续比拟 OldStartIdx 和 NewStartIdx 是否雷同。2 和 5 不同，改为比拟 OldEndIdx 和 NewEndIdx
6 和 6 雷同，两个 End 指针都往左挪动一位（-1）。5 和 2 不统一，改为比拟 OldStartIdx 和 NewStartIdx
2 和 5 不同，改为比拟 OldEndIdx 和 NewEndIdx，也不同。改为比拟 OldStartIdx 和 NewEndIdx（方向）。2 和 2 雷同，将 OldStartIdx 对应的实在 DOM 挪动到 OldEndIdx 之后，同时 OldStartIdx 右移一位，NewEndIdx 左移一位。
持续比拟 Start，不同，比拟 End，也不同。比拟 OldStart 和 NewEnd，不同。比拟 OldEnd 和 NewStart（/ 方向），雷同。挪动 OldEnd 对应的实在 DOM 到 OldStart 之前。同时 OldEnd 左移，NewStart 右移。
持续循环，Start| End| / 四个方向，都不同。依据 key 生成 OldStart 和 OldEnd 之间的 index 表，查找 7 是否在 OldStart 和 OldEnd 之间。如果找到，间接挪到 OldStart 之前。找不到，则阐明是新节点，将 7 由 VirtualDOM 生成实在 DOM 后挪到 OldStart 之前。
NewEnd 左移，此时 NewEnd 小于 NewStart，完结循环
删除 OldStart 和 OldEnd 之间的局部
新 Virtual DOM 已存在，DOM 节点也已生成，销毁旧 Virtual DOM 列表
设置 key 之后，就不要遍历了。算法复杂度为 O(n)，否则最坏状况为 $O(n^2)$