用大白话让你明白虚拟DOM的DIFF算法

const vdom = {
  type: "div",
  attr: {
    id: "app",
  },
  children: [
    {
      type: "div",
      attr: {},
      children: "1",
    },
    {
      type: "div",
      attr: {},
      children: "2",
    },
  ],
};

function render(vdom) {
  const el = document.createElement(vdom.type);
  for (const key in vdom.attr) {
    el.setAttribute(key, vdom.attr[key]);
  }
  if (typeof vdom.children === "string") {
    el.textContent = vdom.children;
  } else {
    vdom.children.forEach((child) => {
      el.appendChild(render(child));
    });
  }
  return el;
}

let i = 0
const l2 = c2.length
let e1 = c1.length - 1
let e2 = l2 - 1

while (i <= e1 && i <= e2) {
  const n1 = c1[i]
  const n2 = c2[i] 
  if (isSameVNodeType(n1, n2)) {
    patch(
      n1,
      n2,
      container,
      null,
      parentComponent
    )
  } else {
    break
  }
  i++
}

while (i <= e1 && i <= e2) {
  const n1 = c1[e1]
  const n2 =c2[e2]
  if (isSameVNodeType(n1, n2)) {
    patch(
      n1,
      n2,
      container,
      null,
      parentComponent
    )
  } else {
    break
  }
  e1--
  e2--
}

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],
        container,
        anchor,
        parentComponent
      )
      i++
    }
  }
}

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

else {
  const s1 = i // 旧列表开始索引
  const s2 = i // 新列表开始索引

  // 构建一个新的索引表，用于记录新节点的key和索引的对应关系
  const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
  for (i = s2; i <= e2; i++) {
    const nextChild = c2[i]
    if (nextChild.key != null) {
      keyToNewIndexMap.set(nextChild.key, i)
    }
  }

  let j
  // 用于记录已经被patch的节点的数量
  let patched = 0
  // 用于记录新节点中需要处理的数量,这里其实就是新节点的数量
  const toBePatched = e2 - s2 + 1
  // 这个主要是用来检测旧节点可复用时,在新节点列表中索引是否是升序,如果是升序说明不需要移动
  let maxNewIndexSoFar = 0
  // 用于记录是否有节点被移动过
  let moved = false

  // 构建一个新的索引表,用于记录可复用新旧节点的索引的对应关系
  const newIndexToOldIndexMap = new Array(toBePatched)
  for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0

  // 遍历旧节点
  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去新节点中查找对应的索引
    if (prevChild.key != null) {
      newIndex = keyToNewIndexMap.get(prevChild.key)
    } else {
      // 如果旧节点不存在key，那么就从新节点的最左侧开始查找与旧节点相同的节点
      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 {
      // 如果找到了相同的节点，那么就将新节点的索引记录到索引表中,这里+1是避开索引为0的情况,因为我们初始值是0嘛
      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++
    }
  }

  // 构建一个最长递增子序列的索引表,如果列表没有被移动过,那么说明根本不需要进行计算
  // 构建这个列表的目的是尽可能多的找出不需要移动的节点,反之也就是说尽可能最少的移动节点来完成更新操作
  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

    // 如果索引表中的索引为0,说明这个节点在旧节点中不存在,那么我们就执行创建挂载操作
    if (newIndexToOldIndexMap[i] === 0) {
      patch(
        null,
        nextChild,
        container,
        anchor,
        parentComponent,
        parentSuspense,
        isSVG,
        slotScopeIds,
        optimized
      )
    } else if (moved) {
      // 然后是移动操作
      // 判断一:如果j小于0,说明最长递增子序列已经遍历完了,那么剩下的都是需要移动的节点,可以不用判断这个,但这是个优化点
      // 判断二:看一下当前索引是否能匹配到最长递增子序列中的索引,如果能匹配上,说明这个节点不需要移动,否则就需要移动
      if (j < 0 || i !== increasingNewIndexSequence[j]) {
        move(nextChild, container, anchor, MoveType.REORDER)
      } else {
        // 如果能匹配上,说明我们就不需要进行移动操作了,直接跳过即可,由于我们是倒序,而且j初始值是最长递增子序列的长度-1,所以每次匹配上索引时j都会减1,直到小于0时,说明最长递增子序列已经遍历完了
        j--
      }
    }
  }
}