vue3 diff算法具体流程【源码+图文】

前言

本文只分析有多个子节点的情况，即节点类型为：ShapeFlags = ARRAY_CHILDREN 的情况,也是最复杂的一种情况，其他情况的处理都很简单

• vue3节点类型

export const enum ShapeFlags {
  ELEMENT = 1, // element
  FUNCTIONAL_COMPONENT = 1 << 1, // 函数式组件
  STATEFUL_COMPONENT = 1 << 2, // 有状态节点
  TEXT_CHILDREN = 1 << 3, //  字节点是文本
  ARRAY_CHILDREN = 1 << 4, // 子节点是数组/有多个子节点
  SLOTS_CHILDREN = 1 << 5, // 子节点是slot
  TELEPORT = 1 << 6, 
  SUSPENSE = 1 << 7,
  COMPONENT_SHOULD_KEEP_ALIVE = 1 << 8,
  COMPONENT_KEPT_ALIVE = 1 << 9,
  COMPONENT = ShapeFlags.STATEFUL_COMPONENT | ShapeFlags.FUNCTIONAL_COMPONENT // 有状态组件或者函数组件
}

• diff过程中相关变量解释

    c1: VNode[], // 老虚拟dom
    c2: VNodeArrayChildren, // 新虚拟dom

同层对比

1. 从队头开始对比， （指针i=0），依次对比新旧虚拟dom节点,如果是相同的节点，则调用path方法进行更新，同时指针向后移动一位：i++如果新旧节点不相同，则停止对比，跳出循环，从尾部开始对比虚拟dom节点

    // 先从头部开始对比
    let i = 0
    let e1 = c1.length - 1 // prev ending index （旧dom尾部指针）
    let e2 = l2 - 1 // next ending index （新dom尾部指针）
    // 1. sync from start
    // (a b) c
    // (a b) d e
    // 先定义一个指针i从头部开始向尾部移动比较新旧dom
    // 碰到不相同的节点，或者头尾指针相遇就停止比较
    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)) { // 节点类型一样&&key一样就是相同的节点
        patch(
          n1,
          n2,
          container,
          null,
          parentComponent,
          parentSuspense,
          isSVG,
          slotScopeIds,
          optimized
        )
      } else { // 新旧节点类型不一致，结束对比
        break
      }
      i++
    }

1. 尾部对比，如果新旧节点相同，指针分别向前移动一位：e1--、e2--，开始比较下一个二个；如果新旧节点不相同，或者和头部指针i相遇则停止比较

    const l2 = c2.length
    while (i <= e1 && i <= e2) { // 新旧dom任何一个如果头尾指针相遇就停止
      const n1 = c1[e1]
      const n2 = (c2[e2] = optimized
        ? cloneIfMounted(c2[e2] as VNode)
        : normalizeVNode(c2[e2]))
      if (isSameVNodeType(n1, n2)) { // 如果是相同的节点，则调用path方法复用并更新该节点
        patch(
          n1, // 这个参数为null会做新增操作，有值时会做更新操作
          n2,
          container,
          null,
          parentComponent,
          parentSuspense,
          isSVG,
          slotScopeIds,
          optimized
        )
      } else { // 新旧节点不一致，停止循环
        break
      }
      // 尾部指针分布向前移动一位，比较下一个节点
      e1--
      e2--
    }

图解比较过程

中间剩余部分处理

老虚拟dom比较完了，新虚拟dom还有多余

• 新虚拟dom（c2）有剩余，旧虚拟dom（c1）没有剩余，说明需要新增c2（新虚拟dom）剩余的节点:i（头部指针）到e2（新虚拟dom尾部指针）之间的节点，则调用path方法新增

    // 老节点比较完了，新节点还有多余，就新增i-e2之间的节点
    if (i > e1) {
      if (i <= e2) { // 新增i-e2之间的节点
        const nextPos = e2 + 1
        const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
        while (i <= e2) {
          patch(
            null, // 这个参数为null会做新增操作，有值时会做更新操作
            (c2[i] = optimized
              ? cloneIfMounted(c2[i] as VNode)
              : normalizeVNode(c2[i])),
            container,
            anchor,
            parentComponent,
            parentSuspense,
            isSVG,
            slotScopeIds,
            optimized
          )
          i++
        }
      }
    }

新虚拟dom比较完了, 老虚拟dom还有多余

• 旧虚拟dom（c1）有剩余，新虚拟dom（c2）没有剩余，说明需要删除c1(旧虚拟dom)剩余的节点:i（头部指针）到e1（旧虚拟dom尾部指针）之间的节点，则调用path方法删除

    // 新节点已经比较完了，老节点还有剩余，就将剩余的删除(i-e1之间)
    else if (i > e2) {
      while (i <= e1) { // 移除i-e1之间的节点
        unmount(c1[i], parentComponent, parentSuspense, true)
        i++
      }
    }  

新旧虚拟dom都有剩余（最复杂的情况）

1. 以中间剩余新虚拟dom的key作为key，索引作为值，创建key和索引的映射map：keyToNewIndexMap，（便于后续快速查找）

      // i: 即是前面提到的队头部指针
      // e2：即是前面提到新虚拟dom的队尾指针
      const s1 = i // prev starting index 
      const s2 = i // next starting index

      // 5.1 build key:index map for newChildren
      // 以新节点的key作为key,索引作为值生成一个map
      const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
      for (i = s2; i <= e2; i++) {
        const nextChild = (c2[i] = optimized
          ? cloneIfMounted(c2[i] as VNode)
          : normalizeVNode(c2[i]))
        if (nextChild.key != null) {
          if (__DEV__ && keyToNewIndexMap.has(nextChild.key)) {
            warn(
              `Duplicate keys found during update:`,
              JSON.stringify(nextChild.key),
              `Make sure keys are unique.`
            )
          }
          keyToNewIndexMap.set(nextChild.key, i)
        }
      }

1. 以中间剩余的新节点个数：toBePatched为长度，初始化一个初始值为0的数组，用来进行新旧节点的索引映射，即新旧节点索引映射数组:newIndexToOldIndexMap（为了后面更高效的创建和移动节点）

      let j
      let patched = 0
      const toBePatched = e2 - s2 + 1 // 新节点中间剩余的节点数目
      let moved = false
      // used to track whether any node has moved
      let maxNewIndexSoFar = 0
      // works as Map<newIndex, oldIndex>
      // Note that oldIndex is offset by +1
      // and oldIndex = 0 is a special value indicating the new node has
      // no corresponding old node.
      // used for determining longest stable subsequence
      // 根据新节点中间剩余的节点数目初始化一个数组，数组的每一个元素都是0
      const newIndexToOldIndexMap = new Array(toBePatched)
      for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0

1. 创建中间剩余部分的新旧虚拟dom索引映射关系：遍历中间剩余旧虚拟dom，通过上面创建的keyToNewIndexMap，判断旧的虚拟节点是否可以复用，不能复用，直接调用unmount删除；可以复用则调用patch更新，同时在新旧节点索引映射数组:newIndexToOldIndexMap对应位置记录旧节点索引

      // 遍历老节虚拟节点
      for (i = s1; i <= e1; i++) {
        const prevChild = c1[i]
        if (patched >= toBePatched) { // 新节点已经比完了，则删除剩余老节点
          // all new children have been patched so this can only be a removal
          unmount(prevChild, parentComponent, parentSuspense, true)
          continue
        }
        let newIndex
        // 节点存在key，通过key在keyToNewIndexMap快速索引，判断在新节点中是否存在
        // 时间复杂度为o(1)
        if (prevChild.key != null) {
          newIndex = keyToNewIndexMap.get(prevChild.key)
        } else {
          // 如果key不存在，需要遍历新节点查找当前节点是否存在
          // 时间复杂度为o(n)
          // key-less node, try to locate a key-less node of the same type
          for (j = s2; j <= e2; j++) {
            if (
              newIndexToOldIndexMap[j - s2] === 0 &&
              isSameVNodeType(prevChild, c2[j] as VNode)
            ) {
              newIndex = j
              break
            }
          }
        }

        
        if (newIndex === undefined) { // 当前老节点在新节点中找不到，说明不能复用，则删除
          unmount(prevChild, parentComponent, parentSuspense, true)
        } else {
          // 在新节点中找到了相同的节点，说明该老节点可以复用
          // 将新老节点索引建立联系 
          newIndexToOldIndexMap[newIndex - s2] = i + 1 
          if (newIndex >= maxNewIndexSoFar) { // 判断是否是升序
            maxNewIndexSoFar = newIndex
          } else { // 如果不是升序，说明需要移动
            moved = true
          }
          patch(
            prevChild,
            c2[newIndex] as VNode,
            container,
            null,
            parentComponent,
            parentSuspense,
            isSVG,
            slotScopeIds,
            optimized
          )
          patched++
        }
      }

至此 newIndexToOldIndexMap记录了新旧节点的索引关系，不为0则记录了对应可复用的旧节点索引，为0则表示，没有可复用的节点，需要重新创建

1. 计算最长递增子序列的索引数组:increasingNewIndexSequence（最长递增子序列中保存着不需要移动的节点的索引）

      const increasingNewIndexSequence = moved
        ? getSequence(newIndexToOldIndexMap)
        : EMPTY_ARR

1. 倒叙遍历中间剩余的新虚拟dom，和新旧节点索引映射关系数组newIndexToOldIndexMap比较，如果newIndexToOldIndexMap对应位置的值是0,则说明该节点需要创建,调用patch创建;如果对应位置值不为零，说明是可以复用的节点，则将此时新节点的索引和最长递增子序列最后一个值increasingNewIndexSequence[j]做对比，判断是否需要移动，两个值不相等，说明需要移动调用move方法移动，相等则说明无需移动，最长递增子序列指针向前移动一位j--

      j = increasingNewIndexSequence.length - 1 // 最长递增子序列指针
      // looping backwards so that we can use last patched node as anchor
      // 倒叙遍历中间剩余的新节点，
      for (i = toBePatched - 1; i >= 0; i--) {
        const nextIndex = s2 + i
        const nextChild = c2[nextIndex] as VNode
        const anchor =
          nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
        if (newIndexToOldIndexMap[i] === 0) {
          // mount new
          patch(
            null,
            nextChild,
            container,
            anchor,
            parentComponent,
            parentSuspense,
            isSVG,
            slotScopeIds,
            optimized
          )
        } else if (moved) {
          // move if:
          // There is no stable subsequence (e.g. a reverse)
          // OR current node is not among the stable sequence
          // 如果当前的索引和最长递增子序列中之后一个值不相等，则说明需要移动
          if (j < 0 || i !== increasingNewIndexSequence[j]) {
            debugger
            move(nextChild, container, anchor, MoveType.REORDER)
          } else { // 不相等，说明不需要移动，指针向后移动一位
            j--
          }
        }
      }

完成流程图