详解vue3.0 diff算法的使用(超详细)

<div>
  <span> 苹果🍎 </span> 
  <span> 香蕉🍌 </span>
  <span> 鸭梨🍐 </span>
</div>

<template>
  <span> 苹果🍎 </span> 
  <span> 香蕉🍌 </span>
  <span> 鸭梨🍐 </span>
</template>

 <Fragment>
  <span> 苹果🍎 </span> 
  <span> 香蕉🍌 </span>
  <span> 鸭梨🍐 </span>
</Fragment>

if (patchFlag > 0) {
   if (patchFlag & PatchFlags.KEYED_FRAGMENT) { 
     /* 对于存在key的情况用于diff算法 */
    patchKeyedChildren(
     c1 as VNode[],
     c2 as VNodeArrayChildren,
     container,
     anchor,
     parentComponent,
     parentSuspense,
     isSVG,
     optimized
    )
    return
   } else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
     /* 对于不存在key的情况,直接patch */
    patchUnkeyedChildren( 
     c1 as VNode[],
     c2 as VNodeArrayChildren,
     container,
     anchor,
     parentComponent,
     parentSuspense,
     isSVG,
     optimized
    )
    return
   }
  }

c1 = c1 || EMPTY_ARR
  c2 = c2 || EMPTY_ARR
  const oldLength = c1.length
  const newLength = c2.length
  const commonLength = Math.min(oldLength, newLength)
  let i
  for (i = 0; i < commonLength; i++) { /* 依次遍历新老vnode进行patch */
   const nextChild = (c2[i] = optimized
    ? cloneIfMounted(c2[i] as VNode)
    : normalizeVNode(c2[i]))
   patch(
    c1[i],
    nextChild,
    container,
    null,
    parentComponent,
    parentSuspense,
    isSVG,
    optimized
   )
  }
  if (oldLength > newLength) { /* 老vnode 数量大于新的vnode，删除多余的节点 */
   unmountChildren(c1, parentComponent, parentSuspense, true, commonLength)
  } else { /* /* 老vnode 数量小于于新的vnode，创造新的即诶安 */
   mountChildren(
    c2,
    container,
    anchor,
    parentComponent,
    parentSuspense,
    isSVG,
    optimized,
    commonLength
   )
  }

  /* c1 老的vnode c2 新的vnode */
  let i = 0       /* 记录索引 */
  const l2 = c2.length  /* 新vnode的数量 */
  let e1 = c1.length - 1 /* 老vnode 最后一个节点的索引 */
  let e2 = l2 - 1    /* 新节点最后一个节点的索引 */

 /* 从头对比找到有相同的节点 patch ，发现不同，立即跳出*/
  while (i <= e1 && i <= e2) {
   const n1 = c1[i]
   const n2 = (c2[i] = optimized
    ? cloneIfMounted(c2[i] as VNode)
    : normalizeVNode(c2[i]))
    /* 判断key ，type是否相等 */
   if (isSameVNodeType(n1, n2)) {
    patch(
     n1,
     n2,
     container, 
     parentAnchor,
     parentComponent,
     parentSuspense,
     isSVG,
     optimized
    )
   } else {
    break
   }
   i++
  }

export function isSameVNodeType(n1: VNode, n2: VNode): boolean {
 return n1.type === n2.type && n1.key === n2.key
}

/* 如果第一步没有patch完，立即，从后往前开始patch ,如果发现不同立即跳出循环 */
  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,
     parentAnchor,
     parentComponent,
     parentSuspense,
     isSVG,
     optimized
    )
   } else {
    break
   }
   e1--
   e2--
  }

/* 如果新的节点大于老的节点数 ，对于剩下的节点全部以新的vnode处理（ 这种情况说明已经patch完相同的vnode ） */
  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
     )
     i++
    }
   }
  }

else if (i > e2) {
  while (i <= e1) {
   unmount(c1[i], parentComponent, parentSuspense, true)
   i++
  }
}

 const s1 = i //第一步遍历到的index
   const s2 = i 
   const keyToNewIndexMap: Map<string | number, number> = new Map()
   /* 把没有比较过的新的vnode节点,通过map保存 */
   for (i = s2; i <= e2; i++) {
    if (nextChild.key != null) {
     keyToNewIndexMap.set(nextChild.key, i)
    }
   }
   let j
   let patched = 0 
   const toBePatched = e2 - s2 + 1 /* 没有经过 path 新的节点的数量 */
   let moved = false /* 证明是否 */
   let maxNewIndexSoFar = 0 
   const newIndexToOldIndexMap = new Array(toBePatched)
    for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
   /* 建立一个数组，每个子元素都是0 [ 0, 0, 0, 0, 0, 0, ] */ 

 for (i = s1; i <= e1; i++) { /* 开始遍历老节点 */
    const prevChild = c1[i]
    if (patched >= toBePatched) { /* 已经patch数量大于等于， */
     /* ① 如果 toBePatched新的节点数量为0 ，那么统一卸载老的节点 */
     unmount(prevChild, parentComponent, parentSuspense, true)
     continue
    }
    let newIndex
     /* ② 如果,老节点的key存在 ，通过key找到对应的index */
    if (prevChild.key != null) {
     newIndex = keyToNewIndexMap.get(prevChild.key)
    } else { /* ③ 如果,老节点的key不存在 */
     for (j = s2; j <= e2; j++) { /* 遍历剩下的所有新节点 */
      if (
       newIndexToOldIndexMap[j - s2] === 0 && /* newIndexToOldIndexMap[j - s2] === 0 新节点没有被patch */
       isSameVNodeType(prevChild, c2[j] as VNode)
      ) { /* 如果找到与当前老节点对应的新节点那么 ，将新节点的索引，赋值给newIndex */
       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节点 */
     patch(
      prevChild,
      c2[newIndex] as VNode,
      container,
      null,
      parentComponent,
      parentSuspense,
      isSVG,
      optimized
     )
     patched++
    }
 }

  /*移动老节点创建新节点*/
   /* 根据最长稳定序列移动相对应的节点 */
   const increasingNewIndexSequence = moved
    ? getSequence(newIndexToOldIndexMap)
    : EMPTY_ARR
   j = increasingNewIndexSequence.length - 1
   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) { /* 没有老的节点与新的节点对应，则创建一个新的vnode */
     patch(
      null,
      nextChild,
      container,
      anchor,
      parentComponent,
      parentSuspense,
      isSVG
     )
    } else if (moved) {
     if (j < 0 || i !== increasingNewIndexSequence[j]) { /*如果没有在长*/
      /* 需要移动的vnode */
      move(nextChild, container, anchor, MoveType.REORDER)
     } else {
      j--
     }