Diff 算法

diff的执行策略

同一个虚拟节点，才进行精细化Diff比较；
如何定义同一个虚拟节点呢？就是选择器相同且key相同。
Vue3源码：

function isSameVNodeType(n1, n2) {
  // ...
  return n1.type === n2.type && n1.key === n2.key
}

示例：

<ul key="list">
    <li>我是li<li>  
<ul>

如果上面的代码突然改成：ul变成ol ，但是key不变，里面的内容不变。
那抱歉这里全部需要重新渲染一遍，那为什么会这样设计呢？因为这种场景实际开发中太少见了。

只进行同层比较，不会进行跨层比较；

<ul key="list">
    <li>阿猫<li> 
  <li>阿狗<li>
  <li><div>Box</div> <li>
<ul>

上面代码中，如果li发送变动，只会进行li同层的diff比较，不会进行li子元素divDiff，
这个策略基于：DOM 节点跨层的移动操作少到可以忽略不计。

patchChildren

上一篇我们讲到这个方法是更新子节点，我们来看看里面到底是怎样的：

const patchChildren = (
  n1,
  n2,
  container,
  ...
) => {
  const c1 = n1 && n1.children
  const prevShapeFlag = n1 ? n1.shapeFlag : 0 
  const c2 = n2.children
  const { patchFlag, shapeFlag } = n2
  if (patchFlag > 0) {
    if (patchFlag & 128 /* KEYED_FRAGMENT */) {
      patchKeyedChildren(
        c1,
        c2,
        container,
        ...
      )
      return
    } else if (patchFlag & 256 /* UNKEYED_FRAGMENT */) {
      patchUnkeyedChildren(
        c1,
        c2,
        container,
        ...
      )
      return
    }
  }

其实这个方法就两个处理：

1. 处理有key的节点 patchKeyedChildren
2. 处理没有key的节点 patchUnkeyedChildren

patchKeyedChildren

patchKeyedChildren处理有key的节点，是正式开启Vue diff的流程的方法。
因为代码较长，就不全部列出来了，主要是分为 5 个步骤：

写之前，先看看函数里面的变量声明用法：

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

1. 头头比较，发现不同就跳出

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

上面代码中：旧节点 a b c， 新节点 a b d e
从头向尾diff，到 c 和 d 比较后发现节点有变动，跳出循环。
isSameVNodeType方法上面有讲过。

2. 尾尾比较，发现不同就跳出

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

步骤1完成后，继续步骤2。
上面代码中：旧节点 a b c， 新节点 d e b c
从尾向头diff，到 a 和 e 比较后发现节点有变动，跳出循环。

3. 老节点全部patch，还有新节点

// (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) {    // 并且新节点e2指针还没有走完，表示需要新增节点
    const nextPos = e2 + 1
    const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor
    while (i <= e2) {
      patch(
        null,
        (c2[i] = optimized ? cloneIfMounted(c2[i]) : normalizeVNode(c2[i])),
        container,
        anchor,
        parentComponent,
        parentSuspense,
        isSVG
      )
      i++
    }
  }
}

头头比较和尾尾比较结束后，新节点数大于老节点数，并且新节点e2的指针还没有走完，表示需要新增节点。
旧节点 a b 新节点 a b c
多余节点 c，是新增节点。

4. 新节点全部patch，还有老节点

// (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) {   // 新节点e2指针全部patch完
  while (i <= e1) {  // 新节点数小于老节点数，需要卸载节点
    unmount(c1[i], parentComponent, parentSuspense, true)
    i++
  }
}

步骤4紧接着步骤3，是个 else if ，当前新节点 e2 指针全部patch完成后，旧节点 e1 还有没完成的，需要卸载旧节点。
旧节点 a b c 新节点 a b
多余节点 c，卸载节点。

5. 剩余不确定元素

在执行完前面4步之后，我们发现，咦，只是处理了挂载和卸载，实际开发中有很多移动和插入啊。
嗯，是的这第 5 步才是 diff 的核心。

// [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

旧节点： a b [c d e] f g
新节点： a b [e d c h] f g
待处理的节点： [e d c h]
在待处理的节点中，有很多的可能性： 新增、删除、移动

5.1 build key，记录新的节点

先看看代码中声明的变量：

const s1 = i  // 第一步遍历到的index
const s2 = i 
const keyToNewIndexMap = new Map()   // 把没有比较过的新的vnode节点,通过map保存
for (i = s2; i <= e2; i++) {
  if (nextChild.key != null) {
    keyToNewIndexMap.set(nextChild.key, i)
  }
}

let j // 新指针j
let patched = 0 
const toBePatched = e2 - s2 + 1 // 没有经过 path 的 新的节点的数量
let moved = false               // 是否需要移动
let maxNewIndexSoFar = 0 

const newIndexToOldIndexMap = new Array(toBePatched)
// 建立一个数组，每个子元素都是0 [ 0, 0, 0, 0, 0, 0 ]
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0;

在 keyToNewIndexMap变量中，我们得到的结果是：（假设节点 e 的key是 e）。

keyToNewIndexMap = {"e" => 2, "d" => 3, "c" => 4, "h" => 5}

用新指针 j 来记录剩下的新的节点的索引。
newIndexToOldIndexMap 用来存放新节点索引，和旧节点索引。

5.2 匹配节点，删除不存在的节点

for (i = s1; i <= e1; i++) {   /* 开始遍历老节点 */
  const prevChild = c1[i]      // c1是老节点
  if (patched >= toBePatched) {  
    /* 已经patch数量大于等于剩余节点数量，卸载老的节点 */
    unmount(prevChild, parentComponent, parentSuspense, true)
    continue
  }
  let newIndex   // 目标新节点的索引

  /* 如果,老节点的key存在 ，通过key找到对应的新节点的index */
  if (prevChild.key != null) {
    newIndex = keyToNewIndexMap.get(prevChild.key)
  } else {
    /* 
        如果,老节点的key不存在，遍历剩下的所有新节点
      按我们上面的节点来讲，就是遍历 [e d c h]，代码中s2=2  e2=5，
    */
    for (j = s2; j <= e2; j++) {
      if (
        newIndexToOldIndexMap[j - s2] === 0 &&
        isSameVNodeType(prevChild, c2[j])
      ) {
        /* 如果找到与当前老节点对应的新节点那么 ，将新节点的索引，赋值给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],
      container,
      null,
      parentComponent,
      parentSuspense,
      isSVG,
      optimized
    )
    patched++   // 记录已经在新节点中找到了了多少个老节点了
  } 
}

总结下来主要执行了2步操作：
第一步：
通过老节点的key，找到新节点的 index，这里有两种情况：

1. 老节点没有key，遍历剩下的所有新节点，尝试找到索引
2. 老节点有key，在keyToNewIndexMap中找到索引

第二步：

1. 如果第一步依旧没有找到 Index，则表示没有和新节点对应的老节点，删除当前旧节点。
2. 如果找到了Index，则表示老节点中有对应的节点，赋值新节点索引到newIndex。再把老节点索引，记录到新节点的数组newIndexToOldIndexMap中，这里索引+1，是因为初始值就0，如果直接存放索引，从第一个开始就发生变化那么存入的索引会是0，则会直接被当作没有老节点匹配。

解释判断： newIndex >= maxNewIndexSoFar
因为遍历老数组是从前往后遍历，那么假如说在遍历的时候，就记录该节点在新节点数组中的位置，假如发生倒转，那么就是 maxNewIndexSoFar > newIndex ， 就代表说新老节点的某节点已经发生了调换，在 diff 过程中肯定会涉及元素的移动。

示例:
旧节点 a b c f
新节点 a f b c
遍历老节点时：
当指针到 b 时，newIndex = 2 maxNewIndexSoFar = 0
当指针到 c 时，newIndex = 3 maxNewIndexSoFar = 2
当指针到 f 时，newIndex = 1 maxNewIndexSoFar = 3，结果 moved = true

5.2 流程示例：
旧节点： a b [c d e] f g
新节点： a b [e d c h] f g
待处理的节点： [e d c h]
按上面的逻辑我们先遍历旧节点 [c d e]，在这里我们假设 c的key是c，d和e没有key
当指针到 c，newIndex = 4 s2 = 2 newIndexToOldIndexMap = [0,0,3,0]，执行 patch
当制作到 d，newIndex = undefined 删除 d
当制作到 e，newIndex = undefined 删除 e

5.3 移动和挂载

获取最长递增子序列。

/* 移动老节点、创建新节点*/
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
// 用于节点移动判断
j = increasingNewIndexSequence.length - 1

 // 倒序带处理节点，因为插入节点时使用 insertBefore 即向前插，倒序遍历可以使用上一个更新的节点作为锚点
for (i = toBePatched - 1; i >= 0; i--) {
  // 当前在整个新数组中，带处理节点的索引，s2 是头部相同节点的偏移量
  const nextIndex = s2 + i
  const nextChild = c2[nextIndex]
  const anchor =
        nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor

   // 如果仍然是默认值 0， 证明是一个全新的节点
  if (newIndexToOldIndexMap[i] === 0) {
    patch(
      null,
      nextChild,
      container,
      anchor,
      parentComponent,
      parentSuspense,
      isSVG
    )
  } else if (moved) {
     // 当前索引不是最长递增子序列里的值，需要移动
    if (j < 0 || i !== increasingNewIndexSequence[j]) {
      move(nextChild, container, anchor, 2 /* REORDER */)
    } else {
      // 是最长递增子序列里的值，则指向下一个
      j--
    }
  }
}

在得到最长递增子序列索引后，设置一个变量j，它的初始值是最长递增子序列索引的length - 1，即指向其末尾，主要是用来判断节点是否需要移动。

流程示例1：
旧节点： a b [c d e] f g
新节点： a b [e d c h] f g
待处理的节点： [e d c h]
toBePatched 带处理的节点数为4
moved 为 false
newIndexToOldIndexMap = [0,0,3,0]
按上面的逻辑倒序遍历待处理的节点：
当指针到 h，i = 3 newIndexToOldIndexMap[i] = 0，执行 patch，挂载 h
当指针到 c，i = 2 newIndexToOldIndexMap[i] = 3
当指针到 d，i = 1 newIndexToOldIndexMap[i] = 0，执行 patch，挂载 d
当指针到 e，i = 0 newIndexToOldIndexMap[i] = 0，执行 patch，挂载 e

流程示例2：
旧节点： a [b c f]
新节点： a [f b c]
待处理的节点： [f b c]
toBePatched 带处理的节点数 == 3
moved == true
newIndexToOldIndexMap = [4, 2, 3]
increasingNewIndexSequence 获取最长递增子序列 = [1, 2]
j = 1
按上面的逻辑倒序遍历待处理的节点：
当指针到 f， j = 1， i = 2， increasingNewIndexSequence[j] = 2（是最长序列的值），j—
当指针到 b，j = 0， i = 1， increasingNewIndexSequence[j] = 1（是最长序列的值），j—
当指针到 c，j = -1，i = 0， increasingNewIndexSequence[j] = null（不是最长序列的值）执行move

patchUnkeyedChildren

patchUnkeyedChildren处理没有key的节点。

const patchUnkeyedChildren = (
  c1,
  c2,
  container,
  anchor,
  parentComponent,
  parentSuspense,
  isSVG,
  optimized
) => {
  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++) {
    const nextChild = (c2[i] = optimized
                       ? cloneIfMounted(c2[i])
                       : normalizeVNode(c2[i]))
    patch(
      c1[i],
      nextChild,
      container,
      null,
      parentComponent,
      parentSuspense,
      isSVG,
      optimized
    )
  }
  if (oldLength > newLength) {
    // remove old
    unmountChildren(
      c1,
      parentComponent,
      parentSuspense,
      true,
      false,
      commonLength
    )
  } else {
    // mount new
    mountChildren(
      c2,
      container,
      anchor,
      parentComponent,
      parentSuspense,
      isSVG,
      optimized,
      commonLength
    )
  }
}

对于没有key，的节点，就显得很简单粗暴，。

总结：

1. 比较新老children的length获取最小长度作为公共长度，然后以这个长度进行新旧节点的 patch；
2. 如果老节点数量大于新的节点数量 ，移除多出来的节点；
3. 如果新的节点数量大于老节点的数量， mountChildren 挂载子节点；