[油猴脚本开发指南]简明diff(四)-油猴中文网

李恒道 发表于 2021-10-9 22:05:29

[油猴脚本开发指南]简明diff(四)

# 前文

之前我们已经学习了patchVnode的过程

关于新旧节点的各种判断，但是最核心的情况的函数处理

我们依然还没有研究过，这节课我们研究

```
   if (isDef(oldCh) && isDef(ch)) {
   if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue);
   }
```

里进行处理的updatechildren

这里是精华，也是我们diff部分的终篇。

开干

先说一个diff的算法结论

就是把新旧虚拟dom进行比较

在比较的过程中将真实dom逐步转化为新虚拟dom的状态。

# 开始

直接查代码

代码如下

```javascript
function updateChildren(
parentElm: Node,
oldCh: VNode[],
newCh: VNode[],
insertedVnodeQueue: VNodeQueue
) {
let oldStartIdx = 0;
let newStartIdx = 0;
let oldEndIdx = oldCh.length - 1;
let oldStartVnode = oldCh;
let oldEndVnode = oldCh;
let newEndIdx = newCh.length - 1;
let newStartVnode = newCh;
let newEndVnode = newCh;
let oldKeyToIdx: KeyToIndexMap | undefined;
let idxInOld: number;
let elmToMove: VNode;
let before: any;

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
   if (oldStartVnode == null) {
   oldStartVnode = oldCh[++oldStartIdx]; // Vnode might have been moved left
   } else if (oldEndVnode == null) {
   oldEndVnode = oldCh[--oldEndIdx];
   } else if (newStartVnode == null) {
   newStartVnode = newCh[++newStartIdx];
   } else if (newEndVnode == null) {
   newEndVnode = newCh[--newEndIdx];
   } else if (sameVnode(oldStartVnode, newStartVnode)) {
   patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
   oldStartVnode = oldCh[++oldStartIdx];
   newStartVnode = newCh[++newStartIdx];
   } else if (sameVnode(oldEndVnode, newEndVnode)) {
   patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
   oldEndVnode = oldCh[--oldEndIdx];
   newEndVnode = newCh[--newEndIdx];
   } else if (sameVnode(oldStartVnode, newEndVnode)) {
   // Vnode moved right
   patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
   api.insertBefore(
      parentElm,
      oldStartVnode.elm!,
      api.nextSibling(oldEndVnode.elm!)
   );
   oldStartVnode = oldCh[++oldStartIdx];
   newEndVnode = newCh[--newEndIdx];
   } else if (sameVnode(oldEndVnode, newStartVnode)) {
   // Vnode moved left
   patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
   api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!);
   oldEndVnode = oldCh[--oldEndIdx];
   newStartVnode = newCh[++newStartIdx];
   } else {
   if (oldKeyToIdx === undefined) {
      oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
   }
   idxInOld = oldKeyToIdx;
   if (isUndef(idxInOld)) {
      // New element
      api.insertBefore(
         parentElm,
         createElm(newStartVnode, insertedVnodeQueue),
         oldStartVnode.elm!
      );
   } else {
      elmToMove = oldCh;
      if (elmToMove.sel !== newStartVnode.sel) {
         api.insertBefore(
         parentElm,
         createElm(newStartVnode, insertedVnodeQueue),
         oldStartVnode.elm!
         );
      } else {
         patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
         oldCh = undefined as any;
         api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!);
      }
   }
   newStartVnode = newCh[++newStartIdx];
   }
}
if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
   if (oldStartIdx > oldEndIdx) {
   before = newCh == null ? null : newCh.elm;
   addVnodes(
      parentElm,
      before,
      newCh,
      newStartIdx,
      newEndIdx,
      insertedVnodeQueue
   );
   } else {
   removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
   }
}
}
```

参数

```javascript
parentElm: Node,
oldCh: VNode[],
newCh: VNode[],
insertedVnodeQueue: VNodeQueue
```

传入了父节点，旧虚拟dom的子节点数组，新虚拟dom的子节点数组，insertedVnde数组。

```javascript
let oldStartIdx = 0;
let newStartIdx = 0;
let oldEndIdx = oldCh.length - 1;
let oldStartVnode = oldCh;
let oldEndVnode = oldCh;
let newEndIdx = newCh.length - 1;
let newStartVnode = newCh;
let newEndVnode = newCh;
let oldKeyToIdx: KeyToIndexMap | undefined;
let idxInOld: number;
let elmToMove: VNode;
let before: any;
```

这里我们声明了许多变量，有些我们还不知道，但是可以根据名字和作用猜测到大部分的变量作用。

先说一个结论，diff算法是同时获取新旧虚拟dom的头和尾，并逐步向中间逼近，在逼近的过程中将真实dom逐步变为新虚拟dom对应的真实dom的操作。

```javascript
let oldStartIdx = 0;
let newStartIdx = 0;
```

设置新虚拟dom的开始索引以及旧虚拟dom的开始索引为0

```javascript
let oldEndIdx = oldCh.length - 1;
let oldStartVnode = oldCh;
let oldEndVnode = oldCh;
```

获取旧虚拟dom的结束索引

获取开始索引的对应虚拟dom

获取结束索引的对应虚拟dom

```javascript
let newEndIdx = newCh.length - 1;
let newStartVnode = newCh;
let newEndVnode = newCh;
```

获取新虚拟dom的结束索引

获取新虚拟dom的开始索引位置的虚拟dom

获取新虚拟dom的结束索引位置的虚拟dom

```javascript
let oldKeyToIdx: KeyToIndexMap | undefined;
let idxInOld: number;
let elmToMove: VNode;
let before: any;
```

这四个不知道是啥，先不管。

```javascript
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx)
```

因为diff算法是分别从左右设置两个索引逐渐向里逼近，直至新旧虚拟dom一方结束才结束

![图片.png](data/attachment/forum/202110/09/201953xt39sukxwhh7wiia.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "图片.png")

所以这里用了while，比对是否旧虚拟dom的开始结束索引是否相等

比较新虚拟dom的开始结束索引是否相等。

如果都不等的话，证明是可以继续比对的，我们往下看都进行了哪些操作。

```javascript
   if (oldStartVnode == null) {
   oldStartVnode = oldCh[++oldStartIdx]; // Vnode might have been moved left
   } else if (oldEndVnode == null) {
   oldEndVnode = oldCh[--oldEndIdx];
   } else if (newStartVnode == null) {
   newStartVnode = newCh[++newStartIdx];
   } else if (newEndVnode == null) {
   newEndVnode = newCh[--newEndIdx];
   }
```

这里首先判断了是否为null

如果开始索引的节点为null

则开始索引往后移

如果结束索引的节点为null

则结束索引往前移

因为是if else

所以如果前几个判断为null

则会直接跳过判断部分，进入下一轮循环。

那如果四个节点都不为null

我们会怎么进行判断？

```javascript
if (sameVnode(oldStartVnode, newStartVnode)) {
   patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
   oldStartVnode = oldCh[++oldStartIdx];
   newStartVnode = newCh[++newStartIdx];
   }
```

这里对旧开始节点和新开始节点进行比较，如果比较成功，则调用patchVnode来对这两个节点进行处理

然后旧开始节点和新开始节点都往前进一个

这里调用patchVnode相当于一个递归

我们一开始对元素用了patchvnode

然后发现都存在子元素就调用了 updateChildren

这时候updateChildren又会调用patchVnode对其子元素继续处理。

一直到穷尽为止

比较的函数是怎么进行比较的？

```javascript
function sameVnode(vnode1: VNode, vnode2: VNode): boolean {
const isSameKey = vnode1.key === vnode2.key;
const isSameIs = vnode1.data?.is === vnode2.data?.is;
const isSameSel = vnode1.sel === vnode2.sel;

return isSameSel && isSameKey && isSameIs;
}
```

通过比较key，data，sel，然后进行结合判断

这里我们基本懂了，那我们继续

```javascript
if (sameVnode(oldEndVnode, newEndVnode)) {
   patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
   oldEndVnode = oldCh[--oldEndIdx];
   newEndVnode = newCh[--newEndIdx];
   }
```

这里我们比对旧结束节点以及新结束节点

如果相等则调用patchVnode

并把旧结束节点和新结束节点往前推进一个

每一次推进节点，都代表一个元素的真实dom已经排列到了新虚拟dom的响应位置并正确更新了新虚拟dom中对应的数据。

```javascript
if (sameVnode(oldStartVnode, newEndVnode)) {
   // Vnode moved right
   patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
   api.insertBefore(
      parentElm,
      oldStartVnode.elm!,
      api.nextSibling(oldEndVnode.elm!)
   );
   oldStartVnode = oldCh[++oldStartIdx];
   newEndVnode = newCh[--newEndIdx];
   }
```

对比旧开始节点与新结束节点是否相等

如果相等，则调用patchVnode函数

并将其插入到旧结束节点之后

然后将旧开始节点往前推进一个，新结束节点往后推进一个

这里之所以插入旧结束节点之后

是因为diff是在不断的比对的过程中移动开始和结束的元素的位置

并且排列元素

代表除了开始和结束的元素位置以外的元素都已经排序完成了

我们来大概模拟一下

![图片.png](data/attachment/forum/202110/09/211443dxwgnq8lk53x3gsk.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "图片.png")

匹配成功~

![图片.png](data/attachment/forum/202110/09/211524ydtczc22d2ki2gcf.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "图片.png")

然后把元素挪过来

![图片.png](data/attachment/forum/202110/09/211624qrnpnbemznf2rbls.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "图片.png")

接下来挪动旧的开始坐标和新的结束坐标，缩小范围

![图片.png](data/attachment/forum/202110/09/211759fvpsxamppy0ipsz0.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "图片.png")

这个时候新旧的结尾范围外的元素，完全是相等的

![图片.png](data/attachment/forum/202110/09/211909eddr8kd5zkkiogc8.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "图片.png")

注意，这里的修改位置不是指修改虚拟的dom

而是指根据新旧虚拟dom进行对比，操控真实dom

从而使真实dom最后与新虚拟dom所有信息一致。

如果你了解了这里，那么接下来就基本一路通畅了

如果前三种情况都不符合呢？

```javascript
if (sameVnode(oldEndVnode, newStartVnode)) {
   // Vnode moved left
   patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
   api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!);
   oldEndVnode = oldCh[--oldEndIdx];
   newStartVnode = newCh[++newStartIdx];
   }
```

接下来对比旧虚拟dom的结尾以及新虚拟dom的开头节点

如果相等

则使用patchVnode函数

然后插入到旧开始节点之前

然后将旧结束节点向前提前一位

将新开始节点向后一位。

如果这四种情况都不符合呢？

```javascript
   if (oldKeyToIdx === undefined) {
      oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
   }
   idxInOld = oldKeyToIdx;
```

首先判断oldkeytoidx是否为undefined

如果为undefined则设置oldkeytoidx

我们看看createKeyToOldIdx

```javascript
function createKeyToOldIdx(
children: VNode[],
beginIdx: number,
endIdx: number
): KeyToIndexMap {
const map: KeyToIndexMap = {};
for (let i = beginIdx; i <= endIdx; ++i) {
const key = children?.key;
if (key !== undefined) {
   map = i;
}
}
return map;
}
```

以旧开始节点和旧结束节点为范围

设置了一个对象

属性是每个节点的key

值则是整个数组的节点索引的位置

```javascript
idxInOld = oldKeyToIdx;
```

获取到了oldKeyToIdx之后，则输入新虚拟dom索引位置的节点的key值，得到index

```javascript
   if (isUndef(idxInOld)) {
      // New element
      api.insertBefore(
         parentElm,
         createElm(newStartVnode, insertedVnodeQueue),
         oldStartVnode.elm!
      );
   } else {
      elmToMove = oldCh;
      if (elmToMove.sel !== newStartVnode.sel) {
         api.insertBefore(
         parentElm,
         createElm(newStartVnode, insertedVnodeQueue),
         oldStartVnode.elm!
         );
      } else {
         patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
         oldCh = undefined as any;
         api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!);
      }
   }
```

首先判断index是否为未定义，如果为未定义，直接在旧虚拟dom开始索引前插入新创建的元素。

如果存在定义

```javascript
elmToMove = oldCh;
```

则获取相应的元素

```javascript
      if (elmToMove.sel !== newStartVnode.sel) {
         api.insertBefore(
         parentElm,
         createElm(newStartVnode, insertedVnodeQueue),
         oldStartVnode.elm!
         );
      }
```

如果获取到的元素的sel是否相等，sel相当于css选择器如span#app这样

如果不相等，则证明不是一个元素，直接在旧开始节点前插入一个新元素。

如果相等，则进行以下处理

```javascript
      patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
         oldCh = undefined as any;
         api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!);
```

通过patchVnode来比对差异并修改

然后设置相应的节点为undefined

并插入到旧开始节点前。

在以上操作都结束后

会执行

```javascript
newStartVnode = newCh[++newStartIdx];
```

将新虚拟dom节点索引+1

因为如果不存在，会插入，可以+1

如果存在，不相等，会新建并插入，可以+1

如果存在，相等，插入到新位置，然后将旧虚拟dom相应位置设置为undefined，所以旧的不需要+1了。新的位置+1就可以了。

那么这里我们已经学习完所有的比对了。

我们总结一下

即

旧开头与新开头对比

旧结尾与新结尾对比

旧开头与新结尾对比

旧结尾与新开头对比

如果都不符合

则对开始都结尾的map进行查询，是否有对应key的节点

如果不存在，新建并插入

如果存在，不相等，新建并插入

如果存在，相等，旧虚拟dom相应节点索引位置设置为undefined，并插入。

那么到这里我们已经学习完了核心内容，接下来有一点收尾工作。

```javascript
if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
   if (oldStartIdx > oldEndIdx) {
   before = newCh == null ? null : newCh.elm;
   addVnodes(
      parentElm,
      before,
      newCh,
      newStartIdx,
      newEndIdx,
      insertedVnodeQueue
   );
   } else {
   removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
   }
}
```

判断新开头和新结尾或旧开头旧结尾之间，是否存在剩余

如果最后处理只剩两个元素

![图片.png](data/attachment/forum/202110/09/215918xwactgrw7tm2cr3m.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "图片.png")

我们处理完第一个元素，开头和结尾应该重叠了

![图片.png](data/attachment/forum/202110/09/215954b925iph39panf8tp.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "图片.png")

这时候如果再处理最后一个元素，也就是第二个元素，尾元素会向前走一个

也就是说处理完成的特征就是头>尾

![图片.png](data/attachment/forum/202110/09/220033t78s55l6h5611ehr.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "图片.png")

```javascript
oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx
```

这里首先判断了新和旧是否有任意一个头小于等于尾，代表有剩余元素

```javascript
if (oldStartIdx > oldEndIdx) {
   before = newCh == null ? null : newCh.elm;
   addVnodes(
      parentElm,
      before,
      newCh,
      newStartIdx,
      newEndIdx,
      insertedVnodeQueue
   );
   } else {
   removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
   }
```

判断旧头是否大于旧尾，如果大于，代表是新虚拟dom剩余了元素，这时候把剩余元素全部插入到旧尾节点后就好了

如果是新节点没有剩余，代表我们本次diff已经完成了，删除旧虚拟剩余dom的对应真实dom即可

![图片.png](data/attachment/forum/202110/09/220351z8xbm9kjubj2lzgg.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "图片.png")

这里相当于新虚拟dom剩余了元素

无论新旧

前三个节点一定相等，后两个节点一定相等

同时尾节点在第三个节点上

这时候插入剩余节点一定会在相应的位置上

因为左右遍历的时候，会确定出剩余元素应该插入到哪个位置上。

那么到这里我们的diff章节正式结束

我几乎把全程每个细节和代码以及理论都讲出来了

唉

累死了

# 结语

撒花~

李恒道 发表于 2021-10-9 22:08:59

代码太他妈长了

王一之 发表于 2021-10-9 22:20:17

哥哥太硬核了。。。。不过这和油猴有关系么

李恒道 发表于 2021-10-9 22:27:41

王一之发表于 2021-10-9 22:20
哥哥太硬核了。。。。不过这和油猴有关系么
对后期注入Vue有帮助...
如果连Vue原理都不懂，根本没法找点注入....
想一边介绍vue基础
一边渗透vue原理
不然到时候webpack源码+nodejs环境+vue原理凑一起太爆炸了

王一之 发表于 2021-10-9 22:30:39

李恒道发表于 2021-10-9 22:27
对后期注入Vue有帮助...
如果连Vue原理都不懂，根本没法找点注入....
想一边介绍vue基础

哥哥tql。。。

李恒道 发表于 2021-10-9 23:48:06

王一之发表于 2021-10-9 22:30
哥哥tql。。。

哥哥太穷了？
呜呜呜
哥哥别骂了别骂了
我学就是了

懒男孩 发表于 2021-10-10 10:34:57

李恒道发表于 2021-10-9 23:48
哥哥太穷了？
呜呜呜
哥哥别骂了别骂了

哈哈哈哈。穷鬼

页: [1]

油猴中文网's Archiver

[油猴脚本开发指南]简明diff(四)