多图讲解vue3快速diff算法 #41

wuyunqiang · 2024-03-22T06:46:38Z

为什么react需要fiber&时间分片而vue没有？听听尤大怎么说

 多图讲解vue3快速diff算法

 多图讲解Vue3的diff算法最长递增子序列实现原理

 key可以重复嘛？为什么不使用index做key

详解vue nextTick原理

vue3的diff算法名称是快速diff算法。是在vue2双端diff的基础上增加了最长递增子序列的逻辑。下面一起看下是如何实现的

整体核心思路：复用，能不动就不动，能少移动就少移动，直接创建或者直接删除。

变量说明：

c1 旧节点数组

c2 新节点数组

i 两个数组的前指针同步向后移动因此使用一个变量即可标识

e1 旧数组的尾指针依次向前移动

e2 新数组的尾指针依次向前移动

前处理

从前往后依次比较节点直至节点不相等

源码：

    // 1. sync from start
    // (a b) c
    // (a b) d e
    while (i <= e1 && i <= e2) {
      const n1 = c1[i]
      const n2 = (c2[i] = optimized
        ? cloneIfMounted(c2[i] as VNode)
        : normalizeVNode(c2[i]))
      if (isSameVNodeType(n1, n2)) {
        patch(
          n1,
          n2,
          container,
          null,
          parentComponent,
          parentSuspense,
          isSVG,
          slotScopeIds,
          optimized
        )
      } else {
        break
      }
      i++
    }

后处理

从后往前依次比较节点直至节点不相等

源码：

    // 2. sync from end
    // a (b c)
    // d e (b c)
    while (i <= e1 && i <= e2) {
      const n1 = c1[e1]
      const n2 = (c2[e2] = optimized
        ? cloneIfMounted(c2[e2] as VNode)
        : normalizeVNode(c2[e2]))
      if (isSameVNodeType(n1, n2)) {
        patch(
          n1,
          n2,
          container,
          null,
          parentComponent,
          parentSuspense,
          isSVG,
          slotScopeIds,
          optimized
        )
      } else {
        break
      }
      e1--
      e2--
    }

仅新增

假如变化前后的两组节点分别如下：仅需要处理新增即可

当i大于e1说明有新增节点新增[i, e2]的节点内容

源码：

    // 3. common sequence + mount
    // (a b)
    // (a b) c
    // i = 2, e1 = 1, e2 = 2
    // (a b)
    // c (a b)
    // i = 0, e1 = -1, e2 = 0
    if (i > e1) {
      if (i <= e2) {
        const nextPos = e2 + 1
        const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
        while (i <= e2) {
          patch(
            null,
            (c2[i] = optimized
              ? cloneIfMounted(c2[i] as VNode)
              : normalizeVNode(c2[i])),
            container,
            anchor,
            parentComponent,
            parentSuspense,
            isSVG,
            slotScopeIds,
            optimized
          )
          i++
        }
      }
    }

仅删除

假如变化前后的两组节点分别如下：仅需要处理删除即可

当i大于e2说明需要删除节点删除[i, e1]的节点

源码：

    // 4. common sequence + unmount
    // (a b) c
    // (a b)
    // i = 2, e1 = 2, e2 = 1
    // a (b c)
    // (b c)
    // i = 0, e1 = 0, e2 = -1
    else if (i > e2) {
      while (i <= e1) {
        unmount(c1[i], parentComponent, parentSuspense, true)
        i++
      }
    }

其他case(`新增删除移动`)

假如经过前面几轮比较后当前的现状如图所示：

新建一个keyToNewIndexMap用于收集c2列表的key:index 到这个map中

 const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
      for (i = s2; i <= e2; i++) {
        if (nextChild.key != null) {
          keyToNewIndexMap.set(nextChild.key, i)
        }
      }

遍历旧列表c1 在keyToNewIndexMap中找，如果找到了说明可以被复用, 如果没找到说明当前节点在新列表中不存在应该被删除。
在遍历的过程中需要创建一个newIndexToOldIndexMap的数组(叫map其实是一个数组)。数组初始化为0, 0代表节点新增。然后填充这个数组。先用旧的节点在keyToNewIndexMap中找到对应节点在新列表的下标然后使用旧节点所在的位置 + 1 填充到newIndexToOldIndexMap对应的位置。
遍历过旧数组后删除的case 就已经被处理完毕了 ，同时我们得到了newIndexToOldIndexMap数组，记录的是新节点在旧列表中的相对顺序。然后newIndexToOldIndexMap中为 0 的就是需要新增的节点.
接下来就是找到需要移动的节点这里我们需要让节点尽量少移动。所以寻找newIndexToOldIndexMap中的最长递增子序列。在最长子序列中的节点是不需要移动的。