Vivien's Notebook

11.快速Diff算法

2024/9/11 Vue

1、预处理：首先，对新旧虚拟 DOM 树进行预处理，包括：标记所有静态节点、标记所有拥有 key的节点。

2、根节点比较：比较新旧虚拟 DOM 树的根节点，如果相同则跳过，否则进行深度比较。

3、深度比较：深度比较的流程如下: ①比较两个节点的类型，如果不同则直接生成更新操作。②如果两个节点的类型相同，则比较两个节点的属性，如果不同则生成更新操作。③如果两个节点的类型和属性都相同，则比较两个节点的子节点。

4.生成更新操作 根据两个节点之间的差异，生成更新真实 DOM 所需的最小操作集。

​ 快速 Diff 算法：正如其名，该算法的实测速度非常快。该算法最早应用于 ivi 和 inferno 这两个框架，Vue.js 3 借鉴并扩展了它。下图比较了 ivi、inferno 以及 Vue.js 2 的性能：

性能比较

从中可以看出，在 DOM 操作的各个方面，ivi 和 inferno 所采用的快速 Diff 算法的性能都要稍优于 Vue.js 2 所采用的双端 Diff 算法。既然快速 Diff 算法如此高效，我们有必要了解它的思路。

# 相同的前置元素和后置元素

截取可复用的部分，不可复用的部分再进行 Diff。

​ 不同于简单 Diff 算法和双端 Diff 算法，快速 Diff 算法包含预处理步骤，这其实是借鉴了纯文本 Diff 算法的思路。在纯文本 Diff 算法中，存在对两段文本进行预处理的过程。例如，在对两段文本进行 Diff 之前，可以先对它们进行全等比较：

 if (text1 === text2) return
1

​ 这也称为快捷路径。如果两段文本全等，那么就无须进入核心 Diff 算法的步骤了。除此之外，预处理过程还会处理两段文本相同的前缀和后缀。假设有如下两段文本：

 TEXT1: I use vue for app development
 TEXT2: I use react for app development
1
2

​ 通过肉眼可以很容易发现，这两段文本的头部和尾部分别有一段相同的内容：

文本预处理

​ 对于内容相同的问题，是不需要进行核心 Diff 操作的。因此，对于 TEXT1 和 TEXT2 来说，真正需要进行 Diff 操作的部分是：

 TEXT1: vue
 TEXT2: react
1
2

​ 这实际上是简化问题的一种方式。这么做的好处是，在特定情况下我们能够轻松地判断文本的插入和删除，例如：

 TEXT1: I like you
 TEXT2: I like you too
1
2

​ 经过预处理，去掉这两段文本中相同的前缀内容和后缀内容之后，它将变成：

 TEXT1:
 TEXT2: too
1
2

​ 可以看到，经过预处理后，TEXT1 的内容为空。这说明 TEXT2 在 TEXT1 的基础上增加了字符串 too。相反，我们还可以将这两段文本的位置互换：

 TEXT1: I like you too
 TEXT2: I like you
1
2

​ 这两段文本经过预处理后将变成：

 TEXT1: too
 TEXT2:
1
2

​ 由此可知，TEXT2 是在 TEXT1 的基础上删除了字符串 too。

​ 快速 Diff 算法借鉴了纯文本 Diff 算法中预处理的步骤。例如：

新旧两组子节点

这两组子节点的顺序如下：

  • 旧的一组子节点：p-1、p-2、p-3。
  • 新的一组子节点：p-1、p-4、p-2、p-3。

​ 通过观察可以发现，两组子节点具有相同的前置节点 p-1，以及相同的后置节点 p-2 和 p-3：

相同的前置节点和后置节点

​ 对于相同的前置节点和后置节点，由于它们在新旧两组子节点中的相对位置不变，所以我们无须移动它们，但仍然需要在它们之间打补丁。

# 前置节点

​ 对于前置节点，我们可以建立索引 j，其初始值为 0，用来指向两组子节点的开头：

建立索引j，指向两组子节点的开头

​ 然后开启一个 while 循环，让索引 j 递增，直到遇到不相同的节点为止：

 function patchKeyedChildren(n1, n2, container) {
   const newChildren = n2.children
   const oldChildren = n1.children
   // 处理相同的前置节点
   // 索引 j 指向新旧两组子节点的开头
   let j = 0
   let oldVNode = oldChildren[j]
   let newVNode = newChildren[j]
   // while 循环向后遍历，直到遇到拥有不同 key 值的节点为止
   while (oldVNode.key === newVNode.key) {
     // 调用 patch 函数进行更新
     patch(oldVNode, newVNode, container)
     // 更新索引 j，让其递增
     j++
     oldVNode = oldChildren[j]
     newVNode = newChildren[j]
   }
 } // 就是从左往右遍历打补丁，直到遇到 key 不相等的 VNode 即停下来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

我们使用 while 循环查找所有相同的前置节点，并调用 patch 函数进行打补丁，直到遇到 key 值不同的节点为止。这样，我们就完成了对前置节点的更新。

​ 在这一步更新操作过后，新旧两组子节点的状态如下：

处理完前置节点后的状态

注意，当 while 循环终止时，索引 j 的值为 1。

# 后置节点

​ 接下来，我们需要处理相同的后置节点。由于新旧两组子节点的数量可能不同，所以我们需要两个索引 newEnd 和 oldEnd，分别指向新旧两组子节点中的最后一个节点：

建立索引，指向两组子节点的最后一个节点

​ 然后，再开启一个 while 循环，并从后向前遍历这两组子节点，直到遇到 key 值不同的节点为止：

 function patchKeyedChildren(n1, n2, container) {
   const newChildren = n2.children
   const oldChildren = n1.children
   // 更新相同的前置节点
   let j = 0
   let oldVNode = oldChildren[j]
   let newVNode = newChildren[j]
   while (oldVNode.key === newVNode.key) {
     patch(oldVNode, newVNode, container)
     j++
     oldVNode = oldChildren[j]
     newVNode = newChildren[j]
   }

   // 更新相同的后置节点
   // 索引 oldEnd 指向旧的一组子节点的最后一个节点
   let oldEnd = oldChildren.length - 1
   // 索引 newEnd 指向新的一组子节点的最后一个节点
   let newEnd = newChildren.length - 1

   oldVNode = oldChildren[oldEnd]
   newVNode = newChildren[newEnd]

   // while 循环从后向前遍历，直到遇到拥有不同 key 值的节点为止
   while (oldVNode.key === newVNode.key) {
     // 调用 patch 函数进行更新
     patch(oldVNode, newVNode, container)
     // 递减 oldEnd 和 nextEnd
     oldEnd--
     newEnd--
     oldVNode = oldChildren[oldEnd]
     newVNode = newChildren[newEnd]
   }

 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

与处理相同的前置节点一样，在 while 循环内，需要调用 patch 函数进行打补丁，然后递减两个索引 oldEnd、newEnd 的值。

  1. 从左往右遍历，找到新旧节点 key 不同时即跳出循环，此时 j 指针就是新旧 VNode 不一致的位置索引。
  2. 开启另一个循环，从右向左遍历，此时新旧节点集合因为数量可能不一样多，所以需要分别定一个结束索引（即节点集合的长度 -1），然后从右往左遍历。
  3. 如果遇到相同 key 的节点则 path 对比内容是否需要更新，然后尾指针各自递减，继续下个循环。
  4. 往前找到新旧虚拟节点不同的，则退出循环，此时的新旧节点集合的尾指针指向的就是 key 不同的虚拟节点。

​ 在这一步更新操作过后，新旧两组子节点的状态如下：

处理完后置节点后的状态

​ 当相同的前置节点和后置节点被处理完毕后，旧的一组子节点已经全部被处理了，而在新的一组子节点中，还遗留了一个未被处理的节点 p-4。

# 新增节点

​ 其实不难发现，节点 p-4 是一个新增节点。那么，如何用程序得出“节点 p-4 是新增节点”这个结论呢？这需要我们观察三个索引 j、newEnd 和 oldEnd 之间的关系。

  • 条件一 oldEnd < j 成立：说明在预处理过程中，所有旧子节点都处理完毕了。
  • 条件二 newEnd >= j 成立：说明在预处理过后，在新的一组子节点中，仍然有未被处理的节点，而这些遗留的节点将被视作新增节点。

​ 如果条件一和条件二同时成立，说明在新的一组子节点中，存在遗留节点，且这些节点都是新增节点。因此我们需要将它们挂载到正确的位置：

新增节点的情况

​ 在新的一组子节点中，索引值处于 j 和 newEnd 之间的任何节点都需要作为新的子节点进行挂载。为了将这些节点挂载到正确位置，我们必须找到正确的锚点元素。

​ 观察上图中新的一组子节点可知，新增节点应该挂载到节点 p-2 所对应的真实 DOM 前面。所以，节点 p-2 对应的真实 DOM 节点就是挂载操作的锚点元素：

 function patchKeyedChildren(n1, n2, container) {
   const newChildren = n2.children
   const oldChildren = n1.children
   // 更新相同的前置节点
   // 省略部分代码

   // 更新相同的后置节点
   // 省略部分代码

   // 预处理完毕后，如果满足如下条件，则说明从 j --> newEnd 之间的节点应作为新节点插入
   if (j > oldEnd && j <= newEnd) {
     // 锚点的索引
     const anchorIndex = newEnd + 1
     // 锚点元素
     const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null
     // 采用 while 循环，调用 patch 函数逐个挂载新增节点
     while (j <= newEnd) {
       patch(null, newChildren[j++], container, anchor)
     }
   }

 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

​ 首先计算锚点的索引值（即 anchorIndex）为 newEnd + 1。如果小于新的一组子节点的数量，则说明锚点元素在新的一组子节点中，所以直接使用newChildren[anchorIndex].el 作为锚点元素；否则说明索引 newEnd 对应的节点已经是尾部节点了，这时无须提供锚点元素。有了锚点元素之后，我们开启了一个 while循环，用来遍历索引 j 和索引 newEnd 之间的节点，并调用 patch 函数挂载它们。

由于插入都是用的 inserBefore，而且后面节点的顺序都确定了，所以可以参照当前节点的下个节点的 el 进行插入。

newEnd 是新元素数组中，从尾开始往前比对，直到不匹配，这里需要注意不要将其跟 j 搞混了。

# 删除节点

​ 上面的案例展示了新增节点的情况，我们再来看看删除节点的情况：

删除节点的情况

在这个例子中，新旧两组子节点的顺序如下。

  • 旧的一组子节点：p-1、p-2、p-3。
  • 新的一组子节点：p-1、p-3。

我们同样使用索引 j、oldEnd 和 newEnd 进行标记：

在删除节点的情况下，各个索引的关系

​ 接着，对相同的前置节点进行预处理，处理后的状态如下：

处理完前置节点后，各个索引的关系

​ 然后，对相同的后置节点进行预处理，处理后的状态如下：

处理完后置节点后，各个索引的关系

​ 当相同的前置节点和后置节点全部被处理完毕后，新的一组子节点已经全部被处理完毕了，而旧的一组子节点中遗留了一个节点 p-2。这说明，应该卸载节点 p-2。实际上，遗留的节点可能有多个：

遗留的节点可能有多个

​ 索引 j 和索引 oldEnd 之间的任何节点都应该被卸载，具体实现如下：

 function patchKeyedChildren(n1, n2, container) {
   const newChildren = n2.children
   const oldChildren = n1.children
   // 更新相同的前置节点
   // 省略部分代码

   // 更新相同的后置节点
   // 省略部分代码

   if (j > oldEnd && j <= newEnd) {
     // 省略部分代码
   } else if (j > newEnd && j <= oldEnd) {
     // j -> oldEnd 之间的节点应该被卸载
     while (j <= oldEnd) {
       unmount(oldChildren[j++])
     }
   }

 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

新增了一个 else...if 分支。当满足条件 j > newEnd && j <=oldEnd 时，则开启一个 while 循环，并调用 unmount 函数逐个卸载这些遗留节点。

# 判断是否需要进行 DOM 移动操作

预处理的本质是找到相同的前置节点和后置节点理想情况下，预处理之后只需要增加或删除节点即可。非理想情况下就是还要处理节点的移动。

​ 快速 Diff 算法的预处理过程，即处理相同的前置节点和后置节点。但是，前面给出的例子比较理想化，当处理完相同的前置节点或后置节点后，新旧两组子节点中总会有一组子节点全部被处理完毕。在这种情况下，只需要简单地挂载、卸载节点即可。但有时情况会比较复杂：

复杂情况下的新旧两组子节点

在这个例子中，新旧两组子节点的顺序如下：

  • 旧的一组子节点：p-1、p-2、p-3、p-4、p-6、p-5。
  • 新的一组子节点：p-1、p-3、p-4、p-2、p-7、p-5。

​ 可以看到，与旧的一组子节点相比，新的一组子节点多出了一个新节点 p-7，少了一个节点 p-6。这个例子并不像前面的例子那样理想化，我们无法简单地通过预处理过程完成更新。在这个例子中，相同的前置节点只有 p-1，而相同的后置节点只有 p-5：

复杂情况下仅有少量相同的前置节点和后置节点

​ 经过预处理后两组子节点的状态如下：

处理完前置节点和后置节点后的状态

可以看到，经过预处理后，无论是新的一组子节点，还是旧的一组子节点，都有部分节点未经处理。这时就需要我们进一步处理。

​ 怎么处理呢？其实无论是简单 Diff 算法，还是双端 Diff 算法，抑或快速 Diff 算法，它们都遵循同样的处理规则：

  • 判断是否有节点需要移动，以及应该如何移动；
  • 找出那些需要被添加或移除的节点。

​ 所以接下来我们的任务就是，判断哪些节点需要移动，以及应该如何移动。观察上图可知，在这种非理想的情况下，当相同的前置节点和后置节点被处理完毕后，索引 j、newEnd 和 oldEnd 不满足下面两个条件中的任何一个：

  • j > oldEnd && j <= newEnd
  • j > newEnd && j <= oldEnd

​ 因此，我们需要增加新的 else 分支来处理上图所示的情况：

 function patchKeyedChildren(n1, n2, container) {
   const newChildren = n2.children
   const oldChildren = n1.children
   // 更新相同的前置节点
   // 省略部分代码

   // 更新相同的后置节点
   // 省略部分代码

   if (j > oldEnd && j <= newEnd) {
     // 省略部分代码
   } else if (j > newEnd && j <= oldEnd) {
     // 省略部分代码
   } else {
     // 增加 else 分支来处理非理想情况
   }

 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

后续的处理逻辑将会编写在这个 else 分支内。

​ 知道了在哪里编写处理代码，接下来我们学习具体的处理思路。

​ 首先，我们需要构造一个数组 source，它的长度等于新的一组子节点在经过预处理之后剩余未处理节点的数量，并且 source 中每个元素的初始值都是 -1：

构造source数组

​ 我们可以通过下面的代码完成 source 数组的构造：

 if (j > oldEnd && j <= newEnd) {
   // 省略部分代码
 } else if (j > newEnd && j <= oldEnd) {
   // 省略部分代码
 } else {
   // 构造 source 数组
   // 新的一组子节点中剩余未处理节点的数量
   const count = newEnd - j + 1
   const source = new Array(count)
   source.fill(-1)
 }
1
2
3
4
5
6
7
8
9
10
11

首先，我们需要计算新的一组子节点中剩余未处理节点的数量，即 newEnd - j + 1，然后创建一个长度与之相同的数组 source，最后使用 fill 函数完成数组的填充。

数组 source 的作用：观察上图可以发现，数组 source 中的每一个元素分别与新的一组子节点中剩余未处理节点对应。

​ 实际上，source 数组将用来存储新的一组子节点中的节点在旧的一组子节点中的位置索引，后面将会使用它计算出一个最长递增子序列，并用于辅助完成 DOM 移动的操作：

填充source数组

上图 展示了填充 source 数组的过程。由于 source 数组存储的是新子节点在旧的一组子节点中的位置索引，所以有：

  • 新的一组子节点中的节点 p-3 在旧的一组子节点中的索引为 2，因此 source 数组的第一个元素值为 2；
  • 新的一组子节点中的节点 p-4 在旧的一组子节点中的索引为 3，因此 source 数组的第二个元素值为 3；
  • 新的一组子节点中的节点 p-2 在旧的一组子节点中的索引为 1，因此 source 数组的第三个元素值为 1；
  • 新的一组子节点中的节点 p-7 比较特殊，因为在旧的一组子节点中没有与其 key 值相等的节点，所以 source 数组的第四个元素值保留原来的 -1。

核心思路就是尽可能找到能复用的节点进行 patch 操作。

source 存储的是中间部分新虚拟节点在旧虚拟节点集合中对应的索引，如果没有找到则保留初始值 -1，-1的就是最终需要新增的。

​ 我们可以通过两层 for 循环来完成 source 数组的填充工作，外层循环用于遍历旧的一组子节点，内层循环用于遍历新的一组子节点：

 if (j > oldEnd && j <= newEnd) {
   // 省略部分代码
 } else if (j > newEnd && j <= oldEnd) {
   // 省略部分代码
 } else {
   const count = newEnd - j + 1
   const source = new Array(count)
   source.fill(-1)

   // oldStart 和 newStart 分别为起始索引，即 j
   const oldStart = j
   const newStart = j
   // 遍历旧的一组子节点
   for (let i = oldStart; i <= oldEnd; i++) {
     const oldVNode = oldChildren[i]
     // 遍历新的一组子节点
     for (let k = newStart; k <= newEnd; k++) {
       const newVNode = newChildren[k]
       // 找到拥有相同 key 值的可复用节点
       if (oldVNode.key === newVNode.key) {
         // 调用 patch 进行更新
         patch(oldVNode, newVNode, container)
         // 最后填充 source 数组
         source[k - newStart] = i
       }
     }
   }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

注意，由于数组 source 的索引是从 0 开始的，而未处理节点的索引未必从 0 开始，所以在填充数组时需要使用表达式 k - newStart 的值作为数组的索引值。外层循环的变量 i 就是当前节点在旧的一组子节点中的位置索引，因此直接将变量 i 的值赋给 source[k - newStart] 即可。

未处理节点即为 newStart，不一定是 0，所以不能直接用 k，需要 k-newStart 获取当前在未处理新节点数组中实际的 index。

​ 现在，source 数组已经填充完毕，我们后面会用到它。不过在进一步学习之前，我们需要回头思考一下上面那段用于填充 source 数组的代码存在怎样的问题。这段代码中我们采用了两层嵌套的循环，其时间复杂度为 O(n1 * n2)，其中 n1 和 n2 为新旧两组子节点的数量，我们也可以使用 O(n^2) 来表示。

​ 当新旧两组子节点的数量较多时，两层嵌套的循环会带来性能问题。出于优化的目的，我们可以为新的一组子节点构建一张索引表，用来存储节点的 key 和节点位置索引之间的映射：

使用索引表填充source数组

​ 有了索引表，我们就可以利用它快速地填充 source 数组：

 if (j > oldEnd && j <= newEnd) {
   // 省略部分代码
 } else if (j > newEnd && j <= oldEnd) {
   // 省略部分代码
 } else {
   const count = newEnd - j + 1
   const source = new Array(count)
   source.fill(-1)

   // oldStart 和 newStart 分别为起始索引，即 j
   const oldStart = j
   const newStart = j
   // 构建索引表
   const keyIndex = {}
   for(let i = newStart; i <= newEnd; i++) {
     keyIndex[newChildren[i].key] = i
   }
   // 遍历旧的一组子节点中剩余未处理的节点
   for(let i = oldStart; i <= oldEnd; i++) {
     oldVNode = oldChildren[i]
     // 通过索引表快速找到新的一组子节点中具有相同 key 值的节点位置
     const k = keyIndex[oldVNode.key]

     if (typeof k !== 'undefined') {
       newVNode = newChildren[k]
       // 调用 patch 函数完成更新
       patch(oldVNode, newVNode, container)
       // 填充 source 数组
       source[k - newStart] = i
     } else {
       // 没找到
       unmount(oldVNode)
     }
   }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

同样使用了两个 for 循环，不过它们不再是嵌套的关系，所以能够将代码的时间复杂度降至 O(n)。

其中，第一个 for 循环用来构建索引表，索引表存储的是节点的 key 值与节点在新的一组子节点中位置索引之间的映射，第二个 for 循环用来遍历旧的一组子节点。

可以看到，我们拿旧子节点的 key 值去索引表 keyIndex 中查找该节点在新的一组子节点中的位置，并将查找结果存储到变量 k 中。

如果 k 存在，说明该节点是可复用的，所以我们调用 patch 函数进行打补丁，并填充 source 数组；否则说明该节点已经不存在于新的一组子节点中了，这时我们需要调用 unmount函数卸载它。

​ 上述流程执行完毕后，source 数组已经填充完毕了。

​ 接下来我们应该思考的是，如何判断节点是否需要移动。实际上，快速 Diff 算法判断节点是否需要移动的方法与简单 Diff 算法类似：

 if (j > oldEnd && j <= newEnd) {
   // 省略部分代码
 } else if (j > newEnd && j <= oldEnd) {
   // 省略部分代码
 } else {
   // 构造 source 数组
   const count = newEnd - j + 1  // 新的一组子节点中剩余未处理节点的数量
   const source = new Array(count)
   source.fill(-1)

   const oldStart = j
   const newStart = j
   // 新增两个变量，moved 和 pos
   let moved = false
   let pos = 0

   const keyIndex = {}
   for(let i = newStart; i <= newEnd; i++) {
     keyIndex[newChildren[i].key] = i
   }
   for(let i = oldStart; i <= oldEnd; i++) {
     oldVNode = oldChildren[i]
     const k = keyIndex[oldVNode.key]

     if (typeof k !== 'undefined') {
       newVNode = newChildren[k]
       patch(oldVNode, newVNode, container)
       source[k - newStart] = i
       // 判断节点是否需要移动
       if (k < pos) {
         moved = true
       } else {
         pos = k
       }
     } else {
       unmount(oldVNode)
     }
   }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

新增了两个变量 moved 和 pos。前者的初始值为 false，代表是否需要移动节点，后者的初始值为 0，代表遍历旧的一组子节点的过程中遇到的最大索引值 k。

我们在学习简单 Diff 算法时曾提到，如果在遍历过程中遇到的索引值呈现递增趋势，则说明不需要移动节点，反之则需要。所以在第二个 for 循环内，我们通过比较变量 k 与变量 pos 的值来判断是否需要移动节点。

**解析：**pos 相当于普通 Diff 算法中的 lastIndex，即 oldChildren 按序遍历，正常来说索引序列应该是递增的，如果出现某个节点在 newChildren 中的索引打破了这个递增序列，说明该节点在 newChildren 中应该被移动了。

​ 除此之外，我们还需要一个数量标识，代表已经更新过的节点数量。我们知道，已经更新过的节点数量应该小于新的一组子节点中需要更新的节点数量。一旦前者超过后者，则说明有多余的节点，我们应该将它们卸载：

 if (j > oldEnd && j <= newEnd) {
   // 省略部分代码
 } else if (j > newEnd && j <= oldEnd) {
   // 省略部分代码
 } else {
   // 构造 source 数组
   const count = newEnd - j + 1
   const source = new Array(count)
   source.fill(-1)

   const oldStart = j
   const newStart = j
   let moved = false
   let pos = 0
   const keyIndex = {}
   for(let i = newStart; i <= newEnd; i++) {
     keyIndex[newChildren[i].key] = i
   }
   // 新增 patched 变量，代表更新过的节点数量
   let patched = 0
   for(let i = oldStart; i <= oldEnd; i++) {
     oldVNode = oldChildren[i]
     // 如果更新过的节点数量小于等于需要更新的节点数量，则执行更新
     if (patched <= count) {
       const k = keyIndex[oldVNode.key]
       if (typeof k !== 'undefined') {
         newVNode = newChildren[k]
         patch(oldVNode, newVNode, container)
         // 每更新一个节点，都将 patched 变量 +1
         patched++
         source[k - newStart] = i
         if (k < pos) {
           moved = true
         } else {
           pos = k
         }
       } else {
         // 没找到
         unmount(oldVNode)
       }
     } else {
       // 如果更新过的节点数量大于需要更新的节点数量，则卸载多余的节点
       unmount(oldVNode)
     }
   }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

增加了 patched 变量，其初始值为 0，代表更新过的节点数量。

接着，在第二个 for 循环中增加了判断 patched <= count，如果此条件成立，则正常执行更新，并且每次更新后都让变量 patched 自增；否则说明剩余的节点都是多余的，于是调用 unmount 函数将它们卸载。

​ 现在，我们通过判断变量 moved 的值，已经能够知道是否需要移动节点，同时也处理了很多边界条件。

# 如何移动元素

​ 前面，我们实现了两个目标：

  • 判断是否需要进行 DOM 移动操作。我们创建了变量 moved 作为标识（是否需要移动），当它的值为true 时，说明需要进行 DOM 移动操作。
  • 构建 source 数组。该数组的长度等于新的一组子节点去掉相同的前置/后置节点后，剩余未处理节点的数量。source 数组中存储着新的一组子节点中的节点在旧的一组子节点中的位置，后面我们会根据 source 数组计算出一个最长递增子序列，用于 DOM 移动操作。

​ 接下来，我们学习如何进行 DOM 移动操作：

 if (j > oldEnd && j <= newEnd) {
   // 省略部分代码
 } else if (j > newEnd && j <= oldEnd) {
   // 省略部分代码
 } else {
   // 省略部分代码
   for(let i = oldStart; i <= oldEnd; i++) {
     // 省略部分代码
   }
   if (moved) {
     // 如果 moved 为真，则需要进行 DOM 移动操作
   }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13

在 for 循环后增加了一个 if 判断分支。如果变量 moved 的值为 true，则说明需要进行 DOM 移动操作，所以用于 DOM 移动操作的逻辑将编写在该 if 语句块内。

​ 为了进行 DOM 移动操作，我们首先要根据 source 数组计算出它的最长递增子序列。source 数组仍然取用在前面例子：

用于计算source数组的递增子序列的例子

在这个例子中，我们计算出 source 数组为 [2, 3, 1, -1]。

​ 那么，该数组的最长递增子序列是什么呢？这就需要我们了解最长递增子序列的概念。

什么是一个序列的递增子序列

​ 简单来说，给定一个数值序列，找到它的一个子序列，并且该子序列中的值是递增的，子序列中的元素在原序列中不一定连续。一个序列可能有很多个递增子序列，其中最长的那一个就称为最长递增子序列。

举个例子，假设给定数值序列 [ 0, 8, 4, 12 ]，那么它的最长递增子序列就是 [0, 8, 12]。

当然，对于同一个数值序列来说，它的最长递增子序列可能有多个，例如 [0, 4, 12] 也是本例的答案之一。

​ 理解了什么是最长递增子序列，接下来我们就可以求解 source 数组的最长递增子序列了:

 if (moved) {
   // 计算最长递增子序列
   const seq = lis(sources) // [ 0, 1 ]
 }
1
2
3
4

使用 lis 函数计算一个数组的最长递增子序列。lis 函数接收source 数组作为参数，并返回 source 数组的最长递增子序列之一。

​ 在上例中，你可能疑惑为什么通过 lis 函数计算得到的是 [0, 1]？实际上，source 数组 [2, 3, 1, -1] 的最长递增子序列应该是 [2, 3]，但我们得到的结果是 [0, 1]，这是为什么呢？这是因为 lis 函数的返回结果是最长递增子序列中的元素在 source 数组中的位置索引:

递增子序列中存储的是source数组内元素的位置索引

因为 source 数组的最长递增子序列为 [2, 3]，其中元素 2 在该数组中的索引为 0，而数组 3 在该数组中的索引为 1，所以最终结果为 [0, 1]。

​ 有了最长递增子序列的索引信息后，下一步要重新对节点进行编号:

重新对节点进行编号后的状态

注意，在编号时，我们忽略了经过预处理的节点 p-1 和 p-5。所以，索引为 0 的节点是 p-2，而索引为 1 节点是 p-3，以此类推。

重新编号是为了让子序列 seq 与新的索引值产生对应关系。其实，最长递增子序列 seq 拥有一个非常重要的意义。

以上例来说，子序列 seq 的值为 [0, 1]，它的含义是：**在新的一组子节点中，重新编号后索引值为 0 和 1 的这两个节点在更新前后顺序没有发生变化。**换句话说，重新编号后，索引值为 0 和 1 的节点不需要移动（因为递增，位置不用动）。在新的一组子节点中，节点 p-3 的索引为0，节点 p-4 的索引为 1，所以节点 p-3 和 p-4 所对应的真实 DOM 不需要移动。换句话说，只有节点 p-2 和 p-7 可能需要移动。

​ 为了完成节点的移动，我们还需要创建两个索引值 i 和 s：

  • 用索引 i 指向新的一组子节点中的最后一个节点；
  • 用索引 s 指向最长递增子序列中的最后一个元素。

​ 为了简化图示，我们在去掉了旧的一组子节点以及无关的线条和变量：

建立索引s和i，分别指向子序列和索引的最后一个位置

​ 接下来，我们将开启一个 for 循环，让变量 i 和 s 按照上图中箭头的方向移动：

 if (moved) {
   const seq = lis(sources)

   // s 指向最长递增子序列的最后一个元素
   let s = seq.length - 1
   // i 指向新的一组子节点的最后一个元素
   let i = count - 1
   // for 循环使得 i 递减，即按照图 11-24 中箭头的方向移动
   for (i; i >= 0; i--) {
     if (i !== seq[s]) {
       // 如果节点的索引 i 不等于 seq[s] 的值，说明该节点需要移动
     } else {
       // 当 i === seq[s] 时，说明该位置的节点不需要移动
       // 只需要让 s 指向下一个位置
       s--
     }
   }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

其中，for 循环的目的是让变量 i 按照上图中箭头的方向移动，以便能够逐个访问新的一组子节点中的节点，这里的变量 i 就是节点的索引。

在 for 循环内，判断条件 i!== seq[s]，如果节点的索引 i 不等于 seq[s] 的值，则说明该节点对应的真实 DOM需要移动，否则说明当前访问的节点不需要移动，但这时变量 s 需要按照上图中箭头的方向移动，即让变量 s 递减。

​ 接下来我们就按照上述思路执行更新。初始时索引 i 指向节点 p-7。由于节点 p-7 对 应的 source 数组中相同位置的元素值为 -1，所以我们应该将节点 p-7 作为全新的节点进行挂载：

 if (moved) {
   const seq = lis(sources)

   // s 指向最长递增子序列的最后一个元素
   let s = seq.length - 1
   // i 指向新的一组子节点的最后一个元素
   let i = count - 1
   // for 循环使得 i 递减，即按照图 11-24 中箭头的方向移动
   for (i; i >= 0; i--) {
     if (source[i] === -1) {
       // 说明索引为 i 的节点是全新的节点，应该将其挂载
       // 该节点在新 children 中的真实位置索引
       const pos = i + newStart
       const newVNode = newChildren[pos]
       // 该节点的下一个节点的位置索引
       const nextPos = pos + 1
       // 锚点
       const anchor = nextPos < newChildren.length
         ? newChildren[nextPos].el
         : null
       // 挂载
       patch(null, newVNode, container, anchor)
     } else if (i !== seq[s]) {
       // 如果节点的索引 i 不等于 seq[s] 的值，说明该节点需要移动
     } else {
       // 当 i === seq[s] 时，说明该位置的节点不需要移动
       // 只需要让 s 指向下一个位置
       s--
     }
   }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

如果 source[i] 的值为 -1，则说明索引为 i 的节点是全新的节点，于是我们调用 patch函数将其挂载到容器中。

注意，由于索引 i 是重新编号后的，因此为了得到真实索引值，我们需要计算表达式 i + newStart 的值。

​ 新节点创建完毕后，for 循环已经执行了一次，此时索引 i 向上移动一步，指向了节点p-2：

节点以及索引的当前状态

​ 接着，进行下一轮 for 循环：

1、source[i] 是否等于 -1？很明显，此时索引 i 的值为 2，source[2] 的值等于 1，因此节点 p-2 不是全新的节点，不需要挂载它，进行下一步的判断。

2、i !== seq[s] 是否成立？此时索引 i 的值为 2，索引 s 的值为 1。因此 2 !== seq[1] 成立，节点 p-2 所对应的真实 DOM 需要移动。

​ 在第二步中，我们知道了节点 p-2 所对应的真实 DOM 应该移动：

 if (moved) {
   const seq = lis(sources)

   // s 指向最长递增子序列的最后一个元素
   let s = seq.length - 1
   let i = count - 1
   for (i; i >= 0; i--) {
     if (source[i] === -1) {
       // 省略部分代码
     } else if (i !== seq[s]) {
       // 说明该节点需要移动
       // 该节点在新的一组子节点中的真实位置索引
       const pos = i + newStart
       const newVNode = newChildren[pos]
       // 该节点的下一个节点的位置索引
       const nextPos = pos + 1
       // 锚点
       const anchor = nextPos < newChildren.length
         ? newChildren[nextPos].el
         : null
       // 移动
       insert(newVNode.el, container, anchor)
     } else {
       // 当 i === seq[s] 时，说明该位置的节点不需要移动
       // 并让 s 指向下一个位置
       s--
     }
   }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

移动节点的实现思路类似于挂载全新的节点。不同点在于，移动节点是通过 insert 函数来完成的。

​ 接着，进行下一轮的循环。此时索引 i 指向节点 p-4：

节点以及索引的当前状态

​ 更新过程仍然分为三个步骤：

1、判断表达式 source[i] 的值是否等于 -1？很明显，此时索引 i 的值为 1，表达式 source[1] 的值等于 3，条件不成立。所以节点 p-4 不是全新的节点，不需要挂载它。接着进行下一步判断。

2、判断表达式 i !== seq[s] 是否成立？此时索引 i 的值为 1，索引 s 的值为1。这时表达式 1 === seq[1] 为真，所以条件 i !== seq[s] 也不成立。

3、由于第一步和第二步中的条件都不成立，所以代码会执行最终的 else 分支。这意味着，节点 p-4 所对应的真实 DOM 不需要移动，但我们仍然需要让索引 s的值递减，即 s--。

​ 经过三步判断之后，我们得出结论：节点 p-4 不需要移动。

​ 于是进行下一轮循环，此时的状态如下：

节点以及索引的当前状态

​ 此时索引 i 指向节点 p-3。我们继续进行三个步骤的判断：

1、判断表达式 source[i] 的值是否等于 -1？很明显，此时索引 i 的值为 0，表 达式 source[0] 的值等于 2，所以节点 p-3 不是全新的节点，不需要挂载它，接着进行下一步判断。

2、第二步：判断表达式 i !== seq[s] 是否成立？此时索引 i 的值为 0，索引 s 的值也为0。这时表达式 0 === seq[0] 为真，因此条件也不成立，最终将执行 else 分支的代码，也就是第三步。

3、到了这里，意味着节点 p-3 所对应的真实 DOM 也不需要移动。

​ 在这一轮更新完成之后，循环将会停止，更新完成。

# 求解给定序列的最长递增子序列

​ 如下是用于求解给定序列的最长递增子序列的代码，取自 Vue.js 3：

 function getSequence(arr) {
   const p = arr.slice()
   const result = [0]
   let i, j, u, v, c
   const len = arr.length
   for (i = 0; i < len; i++) {
     const arrI = arr[i]
     if (arrI !== 0) {
       j = result[result.length - 1]
       if (arr[j] < arrI) {
         p[i] = j
         result.push(i)
         continue
       }
       u = 0
       v = result.length - 1
       while (u < v) {
         c = ((u + v) / 2) | 0
         if (arr[result[c]] < arrI) {
           u = c + 1
         } else {
           v = c
         }
       }
       if (arrI < arr[result[u]]) {
         if (u > 0) {
           p[i] = result[u - 1]
         }
         result[u] = i
       }
     }
   }
   u = result.length
   v = result[u - 1]
   while (u-- > 0) {
     result[u] = v
     v = p[v]
   }
   return result
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

注意,源码中 0 表示新增节点，所以上面代码是 !==0 表示跳过。前面的示例中是用 -1 表示新增节点。

# 总结

  • 快速 Diff 算法在实测中性能最优。它借鉴了文本 Diff 中的预处理思路，先处理新旧两组子节点中相同的前置节点和相同的后置节点。
  • 当前置节点和后置节点全部处理完毕后，如果无法简单地通过挂载新节点或者卸载已经不存在的节点来完成更新，则需要根据节点的索引关系，构造出一个最长递增子序列。
  • 最长递增子序列所指向的节点即为不需要移动的节点。
算法 描述
简单 Diff 算法 当索引大于最大索引值，说明需要移动
双端 Diff 算法 两端指针双双比较，key 相同时需要移动，或者 patch
快速 Diff 算法 在简单 Diff 的基础上，先处理相同的前置和后置节点，对于中间的节点得到最长递增子序列，子序列指向的节点即为不需要移动的节点。

核心概念都是，先找到需要移动的节点，再解决怎样移动的问题，最后再处理新增删除，或其他边界情况。

Vue2：双端 Diff 算法，新旧虚拟 DOM 进行头头、尾尾、旧头新尾、新头旧尾循环对比。

Vue3：快速 Diff 算法，先预处理相同头尾，再计算中间部分的最长递增子序列用于 DOM 移动与修改。

上次更新: 2024/9/11 06:21:35

12.组件的实现原理