Vue3之Diff算法学习
| 文档创建人 | 创建日期 | 文档内容 | 更新时间 |
|---|---|---|---|
| adsionli | 2022-07-13 | Vue3 Diff算法学习 | 2022-07-14 |
Vue3中最重要的模块之一就是Diff算法了，它保证了虚拟Dom的快速更新，为对比新旧Virtual DOM来找出真正的Dom变化之处提供了高效的查询。所以就需要来学习一下实现。
引流：Vue3之快速Diff算法学习
本章主要是通过学习<<vue.js设计与实现>>这本书来进行总结
首先对于拥有子集且子集是一个数组的时候，我们才会在组件更新的时候，去使用diff算法。这一点需要明确。
简单Diff
简单Diff的实现是真的比较简单，但是理解了简单Diff之后，就可以为之后学习双端Diff和快速Diff打下一个好的基础，知道我们的目标是什么。
这里使用到的一些函数和参数，都是在Node这个对象下的
我们需要在Diff算法中实现什么?
- 找到需要更新的节点
- 节点内容未改变，但节点顺序发生改变后，调整真实dom顺序
- 有新增节点内容时，进行挂载与Dom的调整
- 旧节点被移除后，卸载节点
也就是需要实现上面四个目标，然后我们就一步一步来实现。
1.1 节点更新判断
既然要知道节点是否被更新，那么我们首先需要为每一个节点加上一个唯一标识符，这样有利于让我们可以快速的在旧节点内容与新节点内容中找到对应的关系，来判断节点是否被更新。
/**
* @method simpleDiff 简单Diff
* @param {*} newChildren 新节点数据
* @param {*} oldChildren 旧节点数据
* @param {Node} container 容器
*/
const simpleDiff = function(newChildren: any[], oldChildren: any[], container: Node) {
//README: lastIndex就是用来记录newChildren元素的位置是否发生改变的关键
let lastIndex = 0;
for(let i = 0; i < newChildren.length; i++) {
for(let j = 0; j < oldChildren.length; j++) {
if(newChildren[i].key === oldChildren[j].key) {
//NOTE: 首先会先对节点进行更新，这里会进行一个el的真实映射，是newChildren的节点也会获得真实dom，具体代码下面截图放出
patch(oldChildren[j], newChildren[i], container);
if(j < lastIndex) {
......
}else {
lastIndex = j;
}
}
}
}
}
patch更新函数中也是最后会调用到patchElement这个函数，所以我们看一下patchElement函数实现：function patchElement(n1: VNode, n2: VNode) { //README: 这里就是进行DOM复用，在复用了DOM元素之后，新节点将持有对真实DOM的引用 const el = n2.el = n1.el; const newProps = n2.props; const oldProps = n1.props; for (const key in newProps) { if (newProps[key] !== oldProps[key]) { options.patchProps(el, key, oldProps[key], newProps[key]) } } for (const key in oldProps) { if (!(key in newProps)) { options.patchProps(el, key, oldProps[key], null); } } //NOTE: 更新子节点 patchChildren(n1, n2, el); }上面备注中也已经标出了，会进行
el赋予。
上面这段代码中出现了一个lastIndex的变量，这个变量是用来记录节点位置是否发生改变的一个判断依据，我们可以通过遍历newChildren时，判断新的位置和oldChilren中的位置，进行判断是否发生改变。比如说下图的这种情况
上图我们可以看到之前的p-3所在的index是2，但是在newChildren中，他的位置变成了0，这时候我们发现老的位置下标是要比新的位置下标来的大的，所以我们需要去更新一下lastIndex，让lastIndex = j，也就是赋予老的位置index。为什么这么做呢，因为这里和之后的更新dom有很大的关系。这里更新真实dom和我们会很容易想到的改变parentNode的childNode中的位置不同，它是采用尾插移动的，如下图
有了上面这个图，就很明确了。所以我们可以通过lastIndex赋予老的且大的index，来判断newChildren中的node是否顺序发生改变的判断依据。
1.2 节点位置改变
在1.1中，我们已经可以知晓位置是否改变，且知道了他的位置改变时采用尾插法进行改变的，不是通过调整childNode中的原有顺序调整的，因此通过lastIndex的改变与比较，就可以知道位置是否改变了，那么为了调整位置的话，用代码实现比较简单了，如下所示
/**
* @method simpleDiff 简单Diff
* @param {*} newChildren 新节点数据
* @param {*} oldChildren 旧节点数据
* @param {Node} container 容器
*/
const simpleDiff = function(newChildren: any[], oldChildren: any[], container: Node) {
//README: lastIndex就是用来记录newChildren元素的位置是否发生改变的关键
let lastIndex = 0;
for(let i = 0; i < newChildren.length; i++) {
for(let j = 0; j < oldChildren.length; j++) {
if(newChildren[i].key === oldChildren[j].key) {
patch(oldChildren[j], newChildren[i], container);
if(j < lastIndex) {
//README: 这里我们可以知道，新的节点顺序一定是真实dom最终的顺序，所以我们可以通过获取前置节点来作为锚点。
//README: 因为新的节点数据中el对应的还是老的节点数据的真实Dom数据的，所以我们可以获取到
let preVNode = newChildren[i - 1];
if(anchor) {
//获取锚点，通过Node的nextSibling属性
let anchor = preVNode.el.nextSibling;
insert(oldChildren[j].el, container, anchor);
}
}else {
lastIndex = j;
}
}
}
}
}
我们通过获取newChildren上一节点的数据，来获取到它的前置节点的VNode，又因为它的el中保存的就是真实dom数据，那么我们就可以获取它的锚点anchor啦，然后再通过Node对象中的nextSibling属性可以获取到当前锚点的紧邻的后一位的child对象，然后在进行添加即可(这里需要先判断当前位是不是第一位，如果是第一位，那么anchor就为undefined，就不同设置了)。insert函数的代码如下
const insert = (el, parent, anchor: Node | null = null) => {
//insertBefore是Node的内置函数，用于添加到childrenNode中
parent.insertBefore(el, anchor);
}
insertBefore也是Node对象本身具有的内置函数，直接调用就可以进行设置添加了。
1.3 新增节点
除了本身的节点位置及内容更新，也会存在新增的节点的进入，如果需要加入新增的接点的话，也是非常的简单的，我们只需要稍微修改一下1.2中的simpleDiff代码的实现即可
/**
* @method simpleDiff 简单Diff
* @param {*} newChildren 新节点数据
* @param {*} oldChildren 旧节点数据
* @param {Node} container 容器
*/
const simpleDiff = function(newChildren: any[], oldChildren: any[], container: Node) {
let lastIndex = 0;
for(let i = 0; i < newChildren.length; i++) {
//FIXME: 新增一个find协助判断是否是新增节点
let find = false;
for(let j = 0; j < oldChildren.length; j++) {
if(newChildren[i].key === oldChildren[j].key) {
find = true;
patch(oldChildren[j], newChildren[i], container);
if(j < lastIndex) {
let preVNode = newChildren[i - 1];
if(anchor) {
let anchor = preVNode.el.nextSibling;
insert(oldChildren[j].el, container, anchor);
}
}else {
lastIndex = j;
}
}
}
//如果在上面没有找的话，find依然是false,说明是新增节点
if(!find) {
let preVNode = newChildren[i - 1];
let anchor = null;
//FIXME: 如果新增节点在首位，那么就额外处理一下，否则取前置节点作为锚点
if(preVNode) {
anchor = preVNode.el.nextSibling;
}else {
//这里依然是调用了Node对象的属性firstChild,来设置锚点
anchor = container.firstChild;
}
patch(null, newChildren[i], container,anchor);
}
}
}
新增了一个属性find用来协助判断是否是新增节点，如果是新增节点的话，就将新增节点添加入对应的位置，也就是下面的处理，这里稍微有点不一样，因为新增节点可能是首位，所以会调用Node对象的firstChild作为锚点进行新增。那么具体的工作原理可以看下图:
1.4 节点删除
那么有了节点更新，添加之后，也就会存在节点删除的情况，对于节点删除来说，我们只需要判断newChildren与oldChildren是否一样就可以了，所以还是需要在1.3的基础上继续完善代码，添加newChildren与oldChildren进行对比的代码即可。
/**
* @method simpleDiff 简单Diff
* @param {*} newChildren 新节点数据
* @param {*} oldChildren 旧节点数据
* @param {Node} container 容器
*/
const simpleDiff = function(newChildren: any[], oldChildren: any[], container: Node) {
let lastIndex = 0;
for(let i = 0; i < newChildren.length; i++) {
let find = false;
for(let j = 0; j < oldChildren.length; j++) {
if(newChildren[i].key === oldChildren[j].key) {
find = true;
patch(oldChildren[j], newChildren[i], container);
if(j < lastIndex) {
let preVNode = newChildren[i - 1];
if(anchor) {
let anchor = preVNode.el.nextSibling;
insert(oldChildren[j].el, container, anchor);
}
}else {
lastIndex = j;
}
}
}
if(!find) {
let preVNode = newChildren[i - 1];
let anchor = null;
if(preVNode) {
anchor = preVNode.el.nextSibling;
}else {
anchor = container.firstChild;
}
patch(null, newChildren[i], container,anchor);
}
}
//NOTE: 通过遍历oldChildren与newChildren进行对比，如果newChildren中不存在，就执行unmounted卸载操作
for(let i = 0; i < oldChildren.length; i++) {
let has = newChildren.find(vnode => vnode.key === oldChildren[i].key)
if(!has) {
unmount(oldChildren[i]);
}
}
}
通过在最后添加一次对比操作，来判断节点是否需要被卸载，如果oldChildren中的节点在newChildren无法找到的话，就进行卸载unmount操作。
这里最后的卸载在书上写的方法确实有点啰嗦了，有很多好的方法来实现，但是这只是作者给我们的一种思路参考的实现，所以无需深究这点。
好了，上面的4个步骤，我们就可以完成简单Diff的实现了，我想大家可以发现，这样子的时间复杂度也实在是有点高，有很多可以优化的地方，所以下面就是优化的内容，也就是双端Diff以及快速Diff了。
双端Diff
开始说双端Diff之前，可以先看一张对比图，然后从这个对比图开始我们的双端Diff实现原理的学习
可以看到再SimpleDiff中我们需要移动2次才能完成节点的更新，分别移动p1,p2。但是在右边这块中，我们只需要移动一次p3的位置，就可以完成更新，这就是我们需要在双端Diff中优化的效果，优化时间复杂度，减少节点更新次数。通过对比可以很直观地看到双端Diff的优势。简单Diff需要移动两次，而双端Diff只需要移动一次即可。
2.1 一般实现
我们通过下图，来一窥一般实现双端Diff的思路，很简单。
通过上图我们可以知道，双端Diff的实现是依靠的多指针来实现的，实际就是双指针的Double版，旧节点集合和新节点集合均有一对双指针来进行遍历比较。
这个比较的顺序在图上也已经清楚地标出了，分别是：
-
newChildrenStart compare oldChildrenStart新节点集合的头部节点与旧节点集合的头部节点进行比较。如果相同就进行节点更新，更新
newChildren的头指针与oldChildren的头指针；不同向下执行。 -
newChildrenEnd compare oldChildrenEnd
新节点集合的尾部节点与旧节点集合的头部尾点进行比较。如果相同就进行节点更新，更新newChildren的尾指针与oldChildren的尾指针；不同向下执行。
-
newChildrenEnd compare oldChildrenStart新节点集合的尾部节点与旧节点集合的头部尾点进行比较。如果相同就进行节点更新并进行真实的dom移动，更新
newChildren的尾指针与oldChildren的头指针；不同向下执行。 -
newChildrenStart compare oldChildrenEnd新节点集合的尾部节点与旧节点集合的头部尾点进行比较。如果相同就进行节点更新并进行真实的dom移动，更新
newChildren的尾指针与oldChildren的头指针；不同向下执行。
1,2的判断与3,4判断后的处理不同，3,4还需要对应真实dom移动，而1,2实际还是在原位置，所以无需移动
所以我们可以先把我们需要使用到的变量设置出来
type NodePointer = {
index: number,
node: VNode
}
let newStart: NodePointer = {
index: 0,
node: newChildren[this.index]
}
let newEnd: NodePointer = {
index: newChildren.length - 1,
node: newChildren[this.index]
}
let oldStart: NodePointer = {
index: 0,
node: oldChildren[this.index]
}
let oldEnd: NodePointer = {
index: oldChildren.length - 1,
node: oldChildren[this.index]
}
这里我们就是需要维护四个指针，也就是newChildren的头尾指针，oldChildren的头尾指针。
那么在理想情况下一定会有一对节点存在对应关系，且不存在节点卸载与新增，因此我们可以在上述四种情况中的任意一种都可以进行命中，那么就可以来进行代码编写了。
type NodePointer = {
index: number,
node: VNode
}
const DoubleDiff = function(newChildren: VNode[], oldChildren: VNode[], container: Node) {
let newStart: NodePointer = {
index: 0,
node: newChildren[this.index]
}
let newEnd: NodePointer = {
index: newChildren.length - 1,
node: newChildren[this.index]
}
let oldStart: NodePointer = {
index: 0,
node: oldChildren[this.index]
}
let oldEnd: NodePointer = {
index: oldChildren.length - 1,
node: oldChildren[this.index]
}
//README: 因为我们需要遍历newChildren与oldChildren所有修改后的节点，所以这里要使用while并引入对应终止判断
//判断条件很好理解，如果最终两边的双指针同时指向最后一个节点时，说明已经到最后一个了，然后就可以跳出循环了
while(newStart.index <= newEnd.index && oldStart.index <= oldEnd.index ) {
//NOTE: 下面就是对上诉四种情况的判断
if(newStart.node.key === oldStart.node.key) {
patch(oldStart.node, newStart.node, container);
//首部指针判断完成，均向下移动
newStart.node = newChildren[++newStart.index];
oldStart.node = newChildren[++oldStart.index];
}else if(newEnd.node.key === oldEnd.node.key) {
patch(oldEnd.node, newEnd.node, container);
//尾部指针判断完成，均向上移动
newEnd.node = newChildren[--newEnd.index];
oldEnd.node = oldChildren[--oldEnd.index];
}else if(newEnd.node.key === oldStart.node.key){
patch(oldStart.node, newEnd.node, container);
//这里因为位置不同，需要更新真实Dom位置，锚点选中为oldEnd的位置的紧邻下一位
insert(oldStart.node.el,container, oldEnd.node.el.nextSibling);
//newEnd指针判断完成，向上移动；oldStart指针判断完成，向下移动
newEnd.node = newChildren[--newEnd.index];
oldStart.node = oldChildren[++oldStart.index];
}else if(newStart.node.key === oldEnd.node.key) {
patch(oldEnd.node, newStart.node, container);
//这里因为位置不同，需要更新真实Dom位置，锚点选中为olStart的位置
insert(oldEnd.node.el,container, olStart.node.el);
//newStart指针判断完成，向下移动；oldEnd指针判断完成，向上移动
newStart.node = newChildren[++newStart.index];
oldEnd.node = oldChildren[--oldEnd.index];
}
}
}
好啦，这样就完成了，看着挺多，实际很简单的嘞，所以这一块看完一遍立刻就记住了