前言

我们之前完成过一个 patchChildren 的方法，该方法的主要作用是为了 更新子节点，即：为子节点打补丁。

子节点的类型多种多样，如果两个 ELEMENT 的子节点都是 TEXT_CHILDREN 的话，那么直接通过 setText 附新值即可。

但是如果新旧 ELEMENT 的子节点都为 ARRAY_CHILDREN 的话，那么想要完成一个高效的更新就会比较复杂了。这个时候，我们就需要，比较两组子节点，以达到一个高效的更新功能。这种 比较的算法 就是 diff 算法。

vue 中对 diff 算法的描述在 packages/runtime-core/src/renderer.ts 的 patchKeyedChildren（1759行） 方法中：

观察该方法，可以发现该方法内部被分成了 5 块（ 5 种场景）：

sync from start：自前向后的对比
sync from end：自后向前的对比
common sequence + mount：新节点多于旧节点，需要挂载
common sequence + unmount：旧节点多于新节点，需要卸载
unknown sequence：乱序

这 5 块就是 diff 的核心逻辑。我们本章就是围绕这五种场景进行分析和实现，现在，就让我们开始循序渐进的解开 diff 算法的神秘面纱吧~~~

1. 前置知识：VNode 虚拟节点 key 属性的作用

在学习 diff 算法前，有一个属性我们必须先了解一下，那就是 key。

我们知道在 v-for 循环的时候，我们必须要指定一个 key 值。那么这个 key 值的作用是什么呢？

如果大家有看过我前几篇关于渲染器的文章，应该还记得我们写过一个方法：在 packages/runtime-core/src/vnode.ts 中的 isSameVNodeType 方法：

ts
/**
 * 根据 key || type 判断是否为相同类型节点
 */
export function isSameVNodeType(n1: VNode, n2: VNode): boolean {
    return n1.type === n2.type && n1.key === n2.key
}

type 和 key 都是 vnode 的 props。

可以看出 vue 是通过判断两个 VNode 的 type 和 key 这两个属性是否相同来判断两个 VNode 是否为相同 VNode 的。

这个概念在 diff 中非常重要，它决定了 ELEMENT 的复用逻辑。因为我们目前的代码并没有 key 这个属性，现在就来把 key 加一下。

在 packages/runtime-core/src/vnode.ts 的 createBaseVNode 中，增加 key 属性：

ts
 const vnode = {
    __v_isVNode: true,
    type,
    props,
    shapeFlag,
 +  key: props?.key || null
 } as VNode

这样，我们的 vnode 就可以具备 key 属性了。

2. 场景一：自前向后的 diff 对比

我们创建如下测试实例：

html
<script>
  const { h, render } = Vue

  const vnode = h('ul', [
    h('li', { key: 1 }, 'a'),
    h('li', { key: 2 }, 'b'),
    h('li', { key: 3 }, 'c')
  ])
  // 挂载
  render(vnode, document.querySelector('#app'))

  // 延迟两秒，生成新的 vnode，进行更新操作
  setTimeout(() => {
    const vnode2 = h('ul', [
      h('li', { key: 1 }, 'a'),
      h('li', { key: 2 }, 'b'),
      h('li', { key: 3 }, 'd')
    ])
    render(vnode2, document.querySelector('#app'))
  }, 2000)
</script>

在上面的测试实例中，我们利用 vnode2 更新 vnode 节点。

它们的子节点都是一个 ARRAY_CHILDREN ，需要注意的是它们的 子节点具备相同顺序下的相同 vnode (type、key 相等)。唯一不同的地方在于 第三个 li 标签显示的内容不同

那么我们来看一下这种情况下 vue 是如何来处理对应的 diff 的。

2.1 源码阅读

在 patchKeyedChildren 中，进行 debugger，等待两秒，进入 debugger：

由上图所示，在 patchKeyedChildren 方法中程序会进入 while(i < e1 && i <= e2) 这个循环，而在 第一次循环 中，因为 n1 和 n2 的 key 和 type 都相同，所以会进入 if 执行 patch 方法，进行打补丁。最后 i++ 变为 1。因为此时仍然满足 i <= e1 && i <= e2 ，所以会 第二次进入循环：

因为第二次的 n1 和 n2 的 type 和 key 仍然相同，所以仍然会进入 if 和第一步执行相同操作，接着 i++ 变为 2，此时会 第三次进入循环 ，而因为第三次的 n1 和 n2 的也是相同 VNode，所以与前两次相同执行 patch
三次循环全部完成，此时，我们查看浏览器，可以发现 children 的更新操作 已经完成。
后续的代码无需关心。

总结：

由以上代码可知：

diff 所面临的的第一个场景就是：自前向后的 diff 比对
在这样的一个比对中，会 依次获取相同下标的 oldChild 和 newChild ：
如果 oldChild 和 newChild 为 相同的 VNode，则直接通过 patch 进行打补丁即可
如果 oldChild 和 newChild 为 不相同的 VNode，则会跳出循环
每次处理成功，则会自增 i 标记，表示：自前向后已处理过的节点数量

2.1 代码实现

根据我们上一小节的源码阅读，下面我们可以直接实现对应逻辑。

首先我们先让我们的代码支持 ARRAY_CHILDREN 的渲染。创建 mountChildren 方法:

ts
const mountChildren = (children, container, anchor) => {
  for (let i = 0; i < children.length; i++) {
    patch(null, children[i], container, anchor)
  }
}

在 packages/runtime-core/src/renderer.ts 中触发 mountElement 方法：

ts
else if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
    // 设置 Array 子节点
    mountChildren(vnode.children, el, anchor)
}

接下来我们来处理 diff，在 packages/runtime-core/src/renderer.ts 中，创建 patchKeyedChildren 方法：

ts
/**
 * diff
 */
const patchKeyedChildren = (
  oldChildren,
  newChildren,
  container,
  parentAnchor
) => {
  /**
   * 索引
   */
  let i = 0
  /**
   * 新的子节点的长度
   */
  const newChildrenLength = newChildren.length
  /**
   * 旧的子节点最大（最后一个）下标
   */
  let oldChildrenEnd = oldChildren.length - 1
  /**
   * 新的子节点最大（最后一个）下标
   */
  let newChildrenEnd = newChildrenLength - 1

  // 1. 自前向后的 diff 对比。经过该循环之后，从前开始的相同 vnode 将被处理
  while (i <= oldChildrenEnd && i <= newChildrenEnd) {
    const oldVNode = oldChildren[i]
    const newVNode = normalizeVNode(newChildren[i])
    // 如果 oldVNode 和 newVNode 被认为是同一个 vnode，则直接 patch 即可
    if (isSameVNodeType(oldVNode, newVNode)) {
      patch(oldVNode, newVNode, container, null)
    }
    // 如果不被认为是同一个 vnode，则直接跳出循环
    else {
      break
    }
    // 下标自增
    i++
  }
}

在 patchChildren 方法中，触发 patchKeyedChildren 方法：

ts
if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
  //  这里要进行 diff 运算
  patchKeyedChildren(c1, c2, container, anchor)
}

最后，创建对应测试实例 packages/vue/examples/runtime/render-element-diff.html：

html
<script>
  const { h, render } = Vue

  const vnode = h('ul', [
    h('li', { key: 1 }, 'a'),
    h('li', { key: 2 }, 'b'),
    h('li', { key: 3 }, 'c')
  ])
  // 挂载
  render(vnode, document.querySelector('#app'))

  // 延迟两秒，生成新的 vnode，进行更新操作
  setTimeout(() => {
    const vnode2 = h('ul', [
      h('li', { key: 1 }, 'a'),
      h('li', { key: 2 }, 'b'),
      h('li', { key: 3 }, 'd')
    ])
    render(vnode2, document.querySelector('#app'))
  }, 2000)
</script>

3. 场景二：自后向前的 diff 对比

现在，我们的代码已经处理 自前向后完全相同的 vnode 了，但也仅仅如此。

接下来我们看另一个例子：

html
<script>
  const { h, render } = Vue

  const vnode = h('ul', [
    h('li', { key: 1 }, 'a'),
    h('li', { key: 2 }, 'b'),
    h('li', { key: 3 }, 'c')
  ])
  // 挂载
  render(vnode, document.querySelector('#app'))

  // 延迟两秒，生成新的 vnode，进行更新操作
  setTimeout(() => {
    const vnode2 = h('ul', [
      h('li', { key: 4 }, 'a'),
      h('li', { key: 2 }, 'b'),
      h('li', { key: 3 }, 'd')
    ])
    render(vnode2, document.querySelector('#app'))
  }, 2000)
</script>

在上面的例子中， vnode2 的第一个子节点的 key = 4，这就会导致一个情况：**如果我们从前往后进行 diff 比对，那么第一个 child 无法满足 isSameVNodeType ，就会直接跳出 **

我们继续去调试看看源码是怎么处理的

3.1 源码阅读

进入 patchKeyedChildren 方法，因为前面的赋值都是一样的我们直接来到第一个 while 循环：

当进入第一个 while 的第一次循环时，此时 n1 的 key 为 1 ,n2 的 key 为 4，所以 isSameVNodeType(n1,n2) 为 false，会执行 else 中的 break 跳出当前 while。第一个 while 结束，来到第二个 while开始 第一次循环：

由上图可知，第二个 while 是从后往前遍历的，且第一次进入循环会比较两个列表的最后一个 vnode 节点，因为此时两个节点不相同所以会进行 patch 打补丁，完成第三个节点的更新后，e1-- e2--，e1 和 e2 此时都为 1，所以会 第二次进入循环：

由于第二次进入循环 n1 和 n2 的 type 和 key 还是相同的，所以会再次执行 patch 操作，此时 e1 和 e2 都为 0，满足 i <= e1 && i <= e2 所以 第三次进入循环：

此时 n1.key = 1 n2.key = 4 所以会执行 break 跳出循环。
此时，各变量的值为：e1 = 0 e2 = 0 i = 0 l2 = 3
三次循环全部完成，此时，我们查看浏览器，可以发现 children 的更新操作已经完成。后续的代码无需关心。

总结：

由以上代码可知：

vue 的 diff 首先会 自前向后 和 自后向前，处理所有的 相同的 VNode 节点
每次处理成功之后，会自减 e1 和 e2 ，表示：新、旧节点中已经处理完成节点（自后向前）

3.2 代码实现

明确好了自后向前的 diff 对比之后，接下来我们就可以直接进行对应的实现了：

在 patchKeyedChildren 方法中，处理自后向前的场景：

ts
// 2. 自后向前的 diff 对比。经过该循环之后，从后开始的相同 vnode 将被处理
while (i <= oldChildrenEnd && i <= newChildrenEnd) {
  const oldVNode = oldChildren[oldChildrenEnd]
  const newVNode = normalizeVNode(newChildren[newChildrenEnd])
  if (isSameVNodeType(oldVNode, newVNode)) {
    patch(oldVNode, newVNode, container, null)
  } else {
    break
  }
  oldChildrenEnd--
  newChildrenEnd--
}

创建测试实例 packages/vue/examples/runtime/render-element-diff-2.html：

html
<script>
  const { h, render } = Vue

  const vnode = h('ul', [
    h('li', { key: 1 }, 'a'),
    h('li', { key: 2 }, 'b'),
    h('li', { key: 3 }, 'c')
  ])
  // 挂载
  render(vnode, document.querySelector('#app'))

  // 延迟两秒，生成新的 vnode，进行更新操作
  setTimeout(() => {
    const vnode2 = h('ul', [
      h('li', { key: 4 }, 'a'),
      h('li', { key: 2 }, 'b'),
      h('li', { key: 3 }, 'd')
    ])
    render(vnode2, document.querySelector('#app'))
  }, 2000)
</script>

4. 场景三：新节点多余旧节点时的 diff 比对

以上两种场景，新节点数量和旧节点数量都是完全一致的。

但是我们也知道一旦产生更新，那么新旧节点的数量是可能会存在不一致的情况，具体的不一致情况会分为两种：

新节点的数量多于旧节点的数量
旧节点的数量多于新节点的数量

本小节我们先来研究一下 新节点的数量多于旧节点的数量 的情况

新节点的数量多于旧节点的数量的场景下，依然可以被细分为两种具体的场景：

多出的新节点位于尾部
多出的新节点位于头部

明确好了以上内容之后，我们来看如下测试实例

html
<script>
  const { h, render } = Vue

  const vnode = h('ul', [h('li', { key: 1 }, 'a'), h('li', { key: 2 }, 'b')])
  // 挂载
  render(vnode, document.querySelector('#app'))

  // 延迟两秒，生成新的 vnode，进行更新操作
  setTimeout(() => {
    const vnode2 = h('ul', [
      h('li', { key: 1 }, 'a'),
      h('li', { key: 2 }, 'b'),
      h('li', { key: 3 }, 'c')
    ])
    render(vnode2, document.querySelector('#app'))
  }, 2000)
</script>

4.1 源码阅读

根据以上代码进入 debugger，忽略掉前两种场景，直接从第三种场景开始：

代码进入场景三 3. common sequence + mount：

以上逻辑为：多出的新节点位于尾部的场景。

那么接下来我们来看：多出的新节点位于头部的场景：

html
<script>
  const { h, render } = Vue

  const vnode = h('ul', [h('li', { key: 1 }, 'a'), h('li', { key: 2 }, 'b')])
  // 挂载
  render(vnode, document.querySelector('#app'))

  // 延迟两秒，生成新的 vnode，进行更新操作
  setTimeout(() => {
    const vnode2 = h('ul', [
      h('li', { key: 3 }, 'c'),
      h('li', { key: 1 }, 'a'),
      h('li', { key: 2 }, 'b')
    ])
    render(vnode2, document.querySelector('#app'))
  }, 2000)
</script>

根据以上代码，再次进入情景三：

代码进入场景三 3. common sequence + mount：

总结：

由以上代码可知：

对于新节点多余旧节点的场景具体可以在细分为两种情况：
1. 多出的新节点位于尾部
2. 多出的新节点位于头部
这两种情况下的区别在于：插入的位置不同
明确好插入的位置之后，直接通过 patch 进行打补丁即可。

4.1 代码实现

根据上一小节的分析，我们可以直接在 packages/runtime-core/src/renderer.ts 中的 patchKeyedChildren 方法下，实现如下代码：

ts
// 3. 新节点多余旧节点时的 diff 比对。
if (i > oldChildrenEnd) {
  if (i <= newChildrenEnd) {
    const nextPos = newChildrenEnd + 1
    const anchor =
      nextPos < newChildrenLength ? newChildren[nextPos].el : parentAnchor
    while (i <= newChildrenEnd) {
      patch(null, normalizeVNode(newChildren[i]), container, anchor)
      i++
    }
  }
}

创建对应测试实例 packages/vue/examples/runtime/render-element-diff-3.html：

html
<script>
  const { h, render } = Vue

  const vnode = h('ul', [h('li', { key: 1 }, 'a'), h('li', { key: 2 }, 'b')])
  // 挂载
  render(vnode, document.querySelector('#app'))

  // 延迟两秒，生成新的 vnode，进行更新操作
  setTimeout(() => {
    const vnode2 = h('ul', [
      h('li', { key: 1 }, 'a'),
      h('li', { key: 2 }, 'b'),
      h('li', { key: 3 }, 'c')
    ])
    render(vnode2, document.querySelector('#app'))
  }, 2000)
</script>

测试成功

5. 场景四：旧节点多于新节点时的 diff 比对

接下来我们来看场景四 旧节点多于新节点时，根据场景三的经验，其实我们也可以明确，对于旧节点多于新节点时，对应的场景也可以细分为两种：

多出的旧节点位于尾部
多出的旧节点位于头部

html
<script>
  const { h, render } = Vue

  const vnode = h('ul', [
    h('li', { key: 1 }, 'a'),
    h('li', { key: 2 }, 'b'),
    h('li', { key: 3 }, 'c')
  ])
  // 挂载
  render(vnode, document.querySelector('#app'))

  // 延迟两秒，生成新的 vnode，进行更新操作
  setTimeout(() => {
    const vnode2 = h('ul', [
      h('li', { key: 1 }, 'a'),
      h('li', { key: 2 }, 'b')
    ])
    render(vnode2, document.querySelector('#app'))
  }, 2000)
</script>

5.1 源码阅读

跟踪代码，直接进入场景四即可：

因为 i = 2,e1 = 0,e2 = 1，所以最后会执行 unmount 方法卸载多余出来的第三个 vnode
以上代码比较简单，对于多出的旧节点位于头部的场景，同样执行该逻辑。

总结：

由以上代码可知：

旧节点多于新节点时，整体的处理比较简单，只需要 卸载旧节点即可

5.2 代码实现

根据上一小节的分析，我们可以直接在 packages/runtime-core/src/renderer.ts 中的 patchKeyedChildren 方法下，实现如下代码：

ts
// 4. 旧节点多与新节点时的 diff 比对。
else if (i > newChildrenEnd) {
  while (i <= oldChildrenEnd) {
    unmount(oldChildren[i])
    i++
  }
}

创建如下测试实例 packages/vue/examples/runtime/render-element-diff-4.html：

html
<script>
  const { h, render } = Vue

  const vnode = h('ul', [
    h('li', { key: 1 }, 'a'),
    h('li', { key: 2 }, 'b'),
    h('li', { key: 3 }, 'c')
  ])
  // 挂载
  render(vnode, document.querySelector('#app'))

  // 延迟两秒，生成新的 vnode，进行更新操作
  setTimeout(() => {
    const vnode2 = h('ul', [
      h('li', { key: 1 }, 'a'),
      h('li', { key: 2 }, 'b')
    ])
    render(vnode2, document.querySelector('#app'))
  }, 2000)
</script>

测试成功

6. 最长递增子序列

在场景五的 diff 中，vue 使用了 最长递增子序列 这样的一个概念，所以想要更好地理解场景五，那么我们需要先搞明白，两个问题：

什么是最长递增子序列？
最长递增子序列在 diff 中的作用是什么？

什么是最长递增子序列？

维基百科 - 最长递增子序列在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。

前置知识：最长递增子序列在 diff 中的作用是什么？

根据我们之前的四种场景可知，所谓的 diff，其实说白了就是对 一组节点 进行添加、删除、打补丁 的对应操作。但是除了以上三种操作之外，其实还有最后一种操作方式，那就是移动。

我们来看下面这个例子：


旧节点：1、2、3、4、5、6
新节点：1、3、2、4、6、5

我们可以根据新节点生成递增子序列，其结果为：

1、3、6
1、2、4、6
......

那么接下来，我们来分析一下移动的策略，整个移动根据递增子序列的不同，将拥有两种移动策略：

1、3、6 递增序列下：
1. 因为 1、3、6 的递增已确认，所以它们三个是不需要移动的，那么我们所需要移动的节点无非就是三个 2、4、5 。
2. 所以我们需要经过三次移动
1、2、4、6 递增序列下：
1. 因为 1、2、4、6 的递增已确认，所以它们四个是不需要移动的，那么我们所需要移动的节点无非就是两个 3、5 。
2. 所以我们需要经过两次移动

所以由以上分析，我们可知：最长递增子序列的确定，可以帮助我们减少移动的次数

所以，当我们需要进行节点移动时，移动需要事先构建出最长递增子序列，以保证我们的移动方案。

7. 源码逻辑：求解最长递增子序列

vue 中关于求 求解最长递增子序列 的代码在 packages/runtime-core/src/renderer.ts 中的 2410 行代码，可以看到存在一个 getSequence 的函数。

这个解法的原理就是通过 贪心 + 二分查找，有兴趣的同学可以去 Leetcode 上做些相关的算法题，这里就不详细展开了。。。

8. 场景五：乱序下的 diff 比对

那么到目前为止，我们已经明确了：

diff 指的就是：添加、删除、打补丁、移动 这四个行为
最长递增子序列 是什么，以及在 diff 中的作用
场景五的乱序，是最复杂的场景，将会涉及到 添加、删除、打补丁、移动 这些所有场景。

那么明确好了以上内容之后，我们先来看对应场景五的测试实例

html
<script>
  const { h, render } = Vue

  const vnode = h('ul', [
    h('li', { key: 1 }, 'a'),
    h('li', { key: 2 }, 'b'),
    h('li', { key: 3 }, 'c'),
    h('li', { key: 4 }, 'd'),
    h('li', { key: 5 }, 'e')
  ])
  // 挂载
  render(vnode, document.querySelector('#app'))

  // 延迟两秒，生成新的 vnode，进行更新操作
  setTimeout(() => {
    const vnode2 = h('ul', [
      h('li', { key: 1 }, 'new-a'),
      h('li', { key: 3 }, 'new-c'),
      h('li', { key: 2 }, 'new-b'),
      h('li', { key: 6 }, 'new-f'),
      h('li', { key: 5 }, 'new-e')
    ])
    render(vnode2, document.querySelector('#app'))
  }, 2000)
</script>

该测试实例经过前四个 while 的过程为：

初始状：索引 i= 0。旧节点结束索引 e1 = 4。新节点索引 e2 = 4
自前向后的对比：索引 i = 1。旧节点结束索引 e1 = 4。新节点索引 e2 = 4
自后到钱的对比：索引 i = 4。旧节点结束索引 e1 = 3。新节点索引 e2 = 3
增加新节点：无任何变化
删除旧节点：无任何变化

8.1 源码阅读

运行该测试实例，我们来跟踪场景五的逻辑：

在 5.1 中创建一个 <key（新节点的 key）:index（新节点的位置）> 的 Map 对象 keyToNewIndexMap。通过该对象可知：新的 child（根据 key 判断指定 child）更新后的位置（根据对应的 index 判断）在哪里。接下来来到 5.2：

2. 5.2 主要做的就是循环 oldChildren ，并尝试进行 patch（打补丁）或 unmount（删除）旧节点。接下来来到 5.3：

如上图 5.3 主要针对移动和挂载做处理

8.2 代码实现

复制 vue 中的源码，然后修改一下变量名 即可。在 patchKeyedChildren 中，添加场景五乱序逻辑：

ts
  // 5. 乱序的 diff 比对
  else {
  const oldStartIndex = i
  const newStartIndex = i
  const keyToNewIndexMap = new Map()
  for (i = newStartIndex; i <= newChildrenEnd; i++) {
    const nextChild = normalizeVNode(newChildren[i])
    if (nextChild.key != null) {
      keyToNewIndexMap.set(nextChild.key, i)
    }
  }

  let j
  let patched = 0
  const toBePatched = newChildrenEnd - newStartIndex + 1
  let moved = false
  let maxNewIndexSoFar = 0
  const newIndexToOldIndexMap = new Array(toBePatched)
  for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
  for (i = oldStartIndex; i <= oldChildrenEnd; i++) {
    const prevChild = oldChildren[i]
    if (patched >= toBePatched) {
      unmount(prevChild)
      continue
    }
    let newIndex
    if (prevChild.key != null) {
      newIndex = keyToNewIndexMap.get(prevChild.key)
    }

    if (newIndex === undefined) {
      unmount(prevChild)
    }
    else {
      newIndexToOldIndexMap[newIndex - newStartIndex] = i + 1
      if (newIndex >= maxNewIndexSoFar) {
        maxNewIndexSoFar = newIndex
      } else {
        moved = true
      }
      patch(prevChild, newChildren[newIndex], container, null)
      patched++
    }
  }

  const increasingNewIndexSequence = moved
    ? getSequence(newIndexToOldIndexMap)
    : []
  j = increasingNewIndexSequence.length - 1
  for (i = toBePatched - 1; i >= 0; i--) {
    const nextIndex = newStartIndex + i
    const nextChild = newChildren[nextIndex]
    const anchor =
      nextIndex + 1 < newChildrenLength
        ? newChildren[nextIndex + 1].el
        : parentAnchor
    if (newIndexToOldIndexMap[i] === 0) {
      patch(null, nextChild, container, anchor)
    } else if (moved) {
      if (j < 0 || i !== increasingNewIndexSequence[j]) {
        move(nextChild, container, anchor)
      } else {
        j--
      }
    }
  }
}

新增 move 方法：

ts
/**
* 移动节点到指定位置
*/
const move = (vnode, container, anchor) => {
    const { el } = vnode
    hostInsert(el!, container, anchor)
}

新增 getSequence 方法

ts
/**
 * 获取最长递增子序列下标
 * 维基百科：https://en.wikipedia.org/wiki/Longest_increasing_subsequence
 * 百度百科：https://baike.baidu.com/item/%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97/22828111
 */
function getSequence(arr) {
  // 获取一个数组浅拷贝。注意 p 的元素改变并不会影响 arr
  // p 是一个最终的回溯数组，它会在最终的 result 回溯中被使用
  // 它会在每次 result 发生变化时，记录 result 更新前最后一个索引的值
  const p = arr.slice()
  // 定义返回值（最长递增子序列下标），因为下标从 0 开始，所以它的初始值为 0
  const result = [0]
  let i, j, u, v, c
  // 当前数组的长度
  const len = arr.length
  // 对数组中所有的元素进行 for 循环处理，i = 下标
  for (i = 0; i < len; i++) {
    // 根据下标获取当前对应元素
    const arrI = arr[i]
    //
    if (arrI !== 0) {
      // 获取 result 中的最后一个元素，即：当前 result 中保存的最大值的下标
      j = result[result.length - 1]
      // arr[j] = 当前 result 中所保存的最大值
      // arrI = 当前值
      // 如果 arr[j] < arrI 。那么就证明，当前存在更大的序列，那么该下标就需要被放入到 result 的最后位置
      if (arr[j] < arrI) {
        p[i] = j
        // 把当前的下标 i 放入到 result 的最后位置
        result.push(i)
        continue
      }
      // 不满足 arr[j] < arrI 的条件，就证明目前 result 中的最后位置保存着更大的数值的下标。
      // 但是这个下标并不一定是一个递增的序列，比如： [1, 3] 和 [1, 2]
      // 所以我们还需要确定当前的序列是递增的。
      // 计算方式就是通过：二分查找来进行的

      // 初始下标
      u = 0
      // 最终下标
      v = result.length - 1
      // 只有初始下标 < 最终下标时才需要计算
      while (u < v) {
        // (u + v) 转化为 32 位 2 进制，右移 1 位 === 取中间位置（向下取整）例如：8 >> 1 = 4;  9 >> 1 = 4; 5 >> 1 = 2
        // https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Operators/Right_shift
        // c 表示中间位。即：初始下标 + 最终下标 / 2 （向下取整）
        c = (u + v) >> 1
        // 从 result 中根据 c（中间位），取出中间位的下标。
        // 然后利用中间位的下标，从 arr 中取出对应的值。
        // 即：arr[result[c]] = result 中间位的值
        // 如果：result 中间位的值 < arrI，则 u（初始下标）= 中间位 + 1。即：从中间向右移动一位，作为初始下标。 （下次直接从中间开始，往后计算即可）
        if (arr[result[c]] < arrI) {
          u = c + 1
        } else {
          // 否则，则 v（最终下标） = 中间位。即：下次直接从 0 开始，计算到中间位置 即可。
          v = c
        }
      }
      // 最终，经过 while 的二分运算可以计算出：目标下标位 u
      // 利用 u 从 result 中获取下标，然后拿到 arr 中对应的值：arr[result[u]]
      // 如果：arr[result[u]] > arrI 的，则证明当前  result 中存在的下标 《不是》 递增序列，则需要进行替换
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]
        }
        // 进行替换，替换为递增序列
        result[u] = i
      }
    }
  }
  // 重新定义 u。此时：u = result 的长度
  u = result.length
  // 重新定义 v。此时 v = result 的最后一个元素
  v = result[u - 1]
  // 自后向前处理 result，利用 p 中所保存的索引值，进行最后的一次回溯
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

至此，场景五的逻辑完成。

创建对应测试实例 packages/vue/examples/runtime/render-element-diff-5.html：

html
<script>
  const { h, render } = Vue

  const vnode = h('ul', [
    h('li', { key: 1 }, 'a'),
    h('li', { key: 2 }, 'b'),
    h('li', { key: 3 }, 'c'),
    h('li', { key: 4 }, 'd'),
    h('li', { key: 5 }, 'e')
  ])
  // 挂载
  render(vnode, document.querySelector('#app'))

  // 延迟两秒，生成新的 vnode，进行更新操作
  setTimeout(() => {
    const vnode2 = h('ul', [
      h('li', { key: 1 }, 'new-a'),
      h('li', { key: 3 }, 'new-c'),
      h('li', { key: 2 }, 'new-b'),
      h('li', { key: 6 }, 'new-f'),
      h('li', { key: 5 }, 'new-e')
    ])
    render(vnode2, document.querySelector('#app'))
  }, 2000)
</script>

测试成功

9. 总结

总结 diff

整个的 diff 就分成 5 种场景，前四种场景相对而言，还比较简单。最复杂的就是第五种，乱序的场景。

整个 diff 中，涉及到了很多的算法。比如：最长递增子序列。

总结 runtime 模块，对于 runtime 而言：

我们首先是了解了 dom、节点、节点树和 虚拟 DOM，虚拟节点之间的概念
然后知道了render 函数和 h 函数各自的作用。h 函数可以得到一个 vnode，而 render 函数可以渲染一个 vnode
接着就是挂载、更新、卸载这三组概念。知道了针对于不同的 vnode 节点，他们的挂载、更新、卸载方式也都是不同的。
之后又深入了解组件，我们知道组件本质上是一个对象（或函数），组件的挂载本质上是 render 函数的挂载。
组件内部维护了一个 effect 对象，以达到响应性渲染的效果。
针对于 setup 函数而言，它在实现上反而更加简单，因为不需要改变 this 指向了。
最后的 diff 分为 5 种场景，最后一种场景还是比较复杂的。

目录

前言

1. 前置知识：VNode 虚拟节点 key 属性的作用

2. 场景一：自前向后的 diff 对比

2.1 源码阅读

2.1 代码实现

3. 场景二：自后向前的 diff 对比

3.1 源码阅读

3.2 代码实现

4. 场景三：新节点多余旧节点时的 diff 比对

4.1 源码阅读

4.1 代码实现

5. 场景四：旧节点多于新节点时的 diff 比对

5.1 源码阅读

5.2 代码实现

6. 最长递增子序列

7. 源码逻辑：求解最长递增子序列

8. 场景五：乱序下的 diff 比对

8.1 源码阅读

8.2 代码实现

9. 总结