本文主要內(nèi)容是vue3中的patchKeyedChildren函數(shù)，該函數(shù)為vue3diff最核心的方法，它的作用是將有key的children列表進(jìn)行diff比較，最終以老children 為模版，通過patch move unmounted 完成diff

 // can be all-keyed or mixed
  const patchKeyedChildren = (
    c1: VNode[],
    c2: VNodeArrayChildren,
    container: RendererElement,
    parentAnchor: RendererNode | null,
    parentComponent: ComponentInternalInstance | null,
    parentSuspense: SuspenseBoundary | null,
    isSVG: boolean,
    slotScopeIds: string[] | null,
    optimized: boolean
  ) => {
    let i = 0
    const l2 = c2.length
    let e1 = c1.length - 1 // prev ending index
    let e2 = l2 - 1 // next ending index

    // 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]))
        // 比較c1[i] c2[i] 是否值得比較，也就是是不是同一個(gè)元素 如果不是直接跳出循環(huán)
      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]))
      // 比較c1[i] c2[i] 是否值得比較，也就是是不是同一個(gè)元素 如果不是直接跳出循環(huán)
      if (isSameVNodeType(n1, n2)) {
        patch(
          n1,
          n2,
          container,
          null,
          parentComponent,
          parentSuspense,
          isSVG,
          slotScopeIds,
          optimized
        )
      } else {
        break
      }
      e1--
      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
    // 如果雙端比較完后，新節(jié)點(diǎn)還有多，老節(jié)點(diǎn)沒了即i > e1，那么，C2多出來的節(jié)點(diǎn)直接新增操作也就是執(zhí)行patch：
    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++
        }
      }
    }

    // 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
    // 如果雙端比較完后，新節(jié)點(diǎn)沒有了，老節(jié)點(diǎn)有多余的，那么，C1多出來的節(jié)點(diǎn)直接刪除即可也就是執(zhí)行unmount：
    else if (i > e2) {
      while (i <= e1) {
        unmount(c1[i], parentComponent, parentSuspense, true)
        i++
      }
    }

    // 5. unknown sequence
    // [i ... e1 + 1]: a b [c d e] f g
    // [i ... e2 + 1]: a b [e d c h] f g
    // i = 2, e1 = 4, e2 = 5
    // 兩端的節(jié)點(diǎn)比較完，剩下中間的節(jié)點(diǎn)是亂序的即剩余的節(jié)點(diǎn)的兩頭兩尾都不相同是亂序的
    else {
      const s1 = i // prev starting index
      const s2 = i // next starting index

      // 5.1 build key:index map for newChildren
      // 構(gòu)建一個(gè)以新節(jié)點(diǎn)的key為map的key,在數(shù)組中的索引位置為值的map，使用空間換時(shí)間的做法，在遍歷一個(gè)數(shù)組的時(shí)候，直接在map中查詢，降低時(shí)間復(fù)雜度。
      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)
        }
      }

      // 5.2 loop through old children left to be patched and try to patch
      // matching nodes & remove nodes that are no longer present
      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
      // 創(chuàng)建一個(gè)新數(shù)組亂序部分為長(zhǎng)度的數(shù)組
      const newIndexToOldIndexMap = new Array(toBePatched)
      for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
      // 遍歷老數(shù)組在新數(shù)組中查找是否有key值相同的節(jié)點(diǎn)
      for (i = s1; i <= e1; i++) {
        const prevChild = c1[i]
        // patched為值得比較的次數(shù),如果大于toBePatched(新數(shù)組亂序部分的長(zhǎng)度)說明新節(jié)點(diǎn)已經(jīng)比較完畢，那么剩下的老節(jié)點(diǎn)都需要?jiǎng)h除
        if (patched >= toBePatched) {
          // all new children have been patched so this can only be a removal
          unmount(prevChild, parentComponent, parentSuspense, true)
          continue
        }
        let newIndex
        // 如果新節(jié)點(diǎn)有key值，那么就在map中查找是否有相同的key值，newIndex為在新數(shù)組中的索引
        if (prevChild.key != null) {
          newIndex = keyToNewIndexMap.get(prevChild.key)
        } else {
          // key-less node, try to locate a key-less node of the same type
          // 如果新節(jié)點(diǎn)沒有key值，那么就遍歷新數(shù)組，尋找和老節(jié)點(diǎn)類型相同的節(jié)點(diǎn)
          for (j = s2; j <= e2; j++) {
            if (
              newIndexToOldIndexMap[j - s2] === 0 // newIndexToOldIndexMap[j - s2] === 0，說明沒有進(jìn)行過patch
              &&
              isSameVNodeType(prevChild, c2[j] as VNode)
            ) {
              newIndex = j
              break
            }
          }
        }
        // 在新數(shù)組中沒有老節(jié)點(diǎn)類型相同的節(jié)點(diǎn)，那么就直接刪除老節(jié)點(diǎn)
        if (newIndex === undefined) {
          unmount(prevChild, parentComponent, parentSuspense, true)
        } else {
          // 保存下所有（值得比較也就是是相同的節(jié)點(diǎn)）的老節(jié)點(diǎn)的索引
          newIndexToOldIndexMap[newIndex - s2] = i + 1
          // 得到的索引newIndex是新節(jié)點(diǎn)在新數(shù)組中的索引，應(yīng)該是一直增大的，如果newIndex < maxNewIndexSoFar說明需要移動(dòng)
          if (newIndex >= maxNewIndexSoFar) {
            maxNewIndexSoFar = newIndex
          } else {
            moved = true
          }
          patch(
            prevChild,
            c2[newIndex] as VNode,
            container,
            null,
            parentComponent,
            parentSuspense,
            isSVG,
            slotScopeIds,
            optimized
          )
          patched++
        }
      }

      // 5.3 move and mount
      // generate longest stable subsequence only when nodes have moved
      // 如果新節(jié)點(diǎn)有移動(dòng)，那么就需要生成最長(zhǎng)的遞增子序列 [1,8,6,3,4,5]=>(最長(zhǎng)的遞增子序列)[1,3,4,5]=>(最長(zhǎng)的遞增子序列在原數(shù)組中的索引)[0,3,4,5]
      const increasingNewIndexSequence = moved
        ? getSequence(newIndexToOldIndexMap)
        : EMPTY_ARR
      j = increasingNewIndexSequence.length - 1
      // looping backwards so that we can use last patched node as anchor
      // 遍歷新數(shù)組亂序部分，以老數(shù)組為模版，將新節(jié)點(diǎn)通過移動(dòng)變?yōu)樾聰?shù)組中的順序
      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 || //j<0有兩種情況：1.最長(zhǎng)遞增子序列的長(zhǎng)度為0，2.最長(zhǎng)遞增子序列的元素已經(jīng)遍歷完畢
            i !== increasingNewIndexSequence[j]  // 判斷不為同一個(gè)元素 
            ) {
            move(nextChild, container, anchor, MoveType.REORDER)
          } else {
            // 不需要移動(dòng)
            j--
          }
        }
      }
    }
  }