渲染器——双端Diff算法

简单 Diff 算法利用虚拟节点的 key 属性，尽可能地复用 DOM 元素，并通过移动 DOM 的方式来完成更新，从而减少不断地创建和销毁DOM 元素带来的性能开销。但是，简单 Diff 算法仍然存在很多缺陷，这些缺陷可以通过双端 Diff 算法解决。

1、双端比较的原理

简单 Diff 算法的问题在于，它对 DOM 的移动操作并不是最优的。我们拿上一章的例子来看，如下图所示：

在这个例子中，如果使用简单 Diff 算法来更新它，则会发生两次 DOM 移动操作，如下图所示：

第一次 DOM 移动操作会将真实 DOM 节点 p-1 移动到真实DOM 节点 p-3 后面。第二次移动操作会将真实 DOM 节点 p-2 移动到真实 DOM 节点 p-1 后面。最终，真实 DOM 节点的顺序与新的一组子节点顺序一致：p-3、p-1、p-2。

然而，上述更新过程并非最优解。在这个例子中，其实只需要通过一步 DOM 节点的移动操作即可完成更新，即只需要把真实 DOM 节点 p-3 移动到真实 DOM 节点 p-1 前面，如下图所示：

可以看到，理论上只需要一次 DOM 移动操作即可完成更新。但简单 Diff 算法做不到这一点，不过双端Diff 算法可以做到。接下来，我们就来讨论双端 Diff 算法的原理。

顾名思义，双端 Diff 算法是一种同时对新旧两组子节点的两个端点进行比较的算法。因此，我们需要四个索引值，分别指向新旧两组子节点的端点，如下图所示：

用代码来表达四个端点，如下面 patchChildren 和patchKeyedChildren 函数的代码所示：

01 function patchChildren(n1, n2, container) {
02   if (typeof n2.children === 'string') {
03     // 省略部分代码
04   } else if (Array.isArray(n2.children)) {
05     // 封装 patchKeyedChildren 函数处理两组子节点
06     patchKeyedChildren(n1, n2, container)
07   } else {
08     // 省略部分代码
09   }
10 }
11
12 function patchKeyedChildren(n1, n2, container) {
13   const oldChildren = n1.children
14   const newChildren = n2.children
15   // 四个索引值
16   let oldStartIdx = 0
17   let oldEndIdx = oldChildren.length - 1
18   let newStartIdx = 0
19   let newEndIdx = newChildren.length - 1
20 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

在上面这段代码中，我们将两组子节点的打补丁工作封装到了patchKeyedChildren 函数中。在该函数内，首先获取新旧两组子节点 oldChildren 和 newChildren，接着创建四个索引值，分别指向新旧两组子节点的头和尾，即 oldStartIdx、oldEndIdx、newStartIdx 和 newEndIdx。有了索引后，就可以找到它所指向的虚拟节点了，如下面的代码所示：

01 function patchKeyedChildren(n1, n2, container) {
02   const oldChildren = n1.children
03   const newChildren = n2.children
04   // 四个索引值
05   let oldStartIdx = 0
06   let oldEndIdx = oldChildren.length - 1
07   let newStartIdx = 0
08   let newEndIdx = newChildren.length - 1
09   // 四个索引指向的 vnode 节点
10   let oldStartVNode = oldChildren[oldStartIdx]
11   let oldEndVNode = oldChildren[oldEndIdx]
12   let newStartVNode = newChildren[newStartIdx]
13   let newEndVNode = newChildren[newEndIdx]
14 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

其中，oldStartVNode 和 oldEndVNode 是旧的一组子节点中的第一个节点和最后一个节点，newStartVNode 和newEndVNode 则是新的一组子节点的第一个节点和最后一个节点。有了这些信息之后，我们就可以开始进行双端比较了。怎么比较呢？如下图所示：

在双端比较中，每一轮比较都分为四个步骤，如上图中的连线所示：

• 第一步：比较旧的一组子节点中的第一个子节点 p-1 与新的一组子节点中的第一个子节点 p-4，看看它们是否相同。由于两者的 key 值不同，因此不相同，不可复用，于是什么都不做。