前言
学完了React、Vue2的diff算法，又到了学Vue3的时候了，Vue3出来了一段时间，不了解一下说不过去~
这篇文章主要分为两部分：
一、diff算法大体的流程和实现思路
二、深入源码，看看具体的实现
核心diff思路
我们都知道，通常我们对比时只有当是相同的父元素时，只有当父元素是相同的节点时，才会往下遍历。那我们假设他们的父节点是相同的，直接开始进行子节点们的比较。为了区分不同的场景下的思路，每一个部分都会举的不同的例子。
预处理优化
我们先来看一下下面这两组简单的节点对比，在Vue3中首先会进行头尾的遍历，进行预处理优化。
1、从头开始遍历
首先会遍历开始节点，判断新老的第一个节点是否一致，一致的话，执行patch方法更新差异，然后往下继续比较，否则break跳出。可以看到下图中，A vs A 是一样的，然后去比较B，B也是一样的，然后去比较C vs D，发现不一样了，于是跳出当前循环。
2、尾部开始
接着我们开始从后往前遍历，也是找相同的元素，G vs G，一致，那么执行patch后往前对比，F vs F一致，继续往前diff，直到E和C不一致，跳出循环。
3、一方已经处理完毕
目前新节点还剩下一个新增节点，那么我们就会去判断是否老节点遍历完毕，然后新增它。下图的C节点则是要新增。
如果是老节点还剩下一个多余节点，则会去判断新节点是否遍历完毕，然后卸载它。下图的I节点则是要卸载。
到了这一步，肯定有人想问，为什么要这么做呢？
但其实大家直觉都知道是为什么，平时我们在修改列表的时候，有一些比较常见场景，比如说列表中间节点的增加、删除、修改等，如果使用了这样的方式查找，可以减少diff的时间，甚至可以不用diff来达到我们想要的结果，并且还可以减少后续diff的复杂度。这个预处理优化策略，是Neil Fraser提出的。
这里应该都有了一些了解，那么接下来还没有走到的场景是新老节点都还剩余有多个子节点存在的情况。那我们再想一想，如果是我们去做这样的一个需求，我们会怎么做呢？
我第一时间想到了Vue2的方式，新老节点去遍历查找然后进行移动。但是如果这样的话，好像跟Vue2相比好像不一定更好。在Vue2遍历时，我们使用的是交叉遍历的方式。那这种方式解决的主要是什么问题呢？举个简单的例子：
这个例子如果在我们刚刚的流程里，是不会做任何操作的，但是Vue2去遍历的时候会进行交叉首尾遍历，然后一个个的匹配到，并且在第一次匹配到G节点的时候，就会把G节点移动到A节点前面，后续匹配ABF节点的时候，只需要去patch，但是不需要move了，因为将G节点移动到A前面后，真实DOM节点的顺序就已经与新节点一致了。
按照前面我去遍历的思路，需要移动四次，如图：
那么问题来了，接下来该怎么做能够在之前优化的基础上继续优化呢？
好像我们找到持续递增的那列节点，就知道哪些节点是可以稳定不变的。
这里引入一个概念，叫最长递增子序列。
官方解释：在一个给定的数组中，找到一组递增的数值，并且长度尽可能的大。
有点比较难理解，那来看具体例子：
const arr = [10, 9, 2, 5, 3, 7, 101, 18]
=> [2, 3, 7, 18, 30]
这一列数组就是arr的最长递增子序列想更深入了解它可以看一下这道题：最长增长子序列
所以如果我们能够找到，老节点在新节点序列中顺序不变的节点们，就知道，哪一些节点不需要移动，然后只需要把不在这里的节点插入进来就可以了。在此之前，我们先把所有节点都找到，在找到对应的序列。
4、找到新节点对应的老节点坐标
最后一个新例子，要diff这两组节点，上面是老节点，下面是新节点~通过上面的铺垫，我们得知了，要找到这样一个数组[2, 3, 新增, 0]，不过因为数组的初始值是0，代表的是新增的意思，所以我们将这个坐标+1，新增的变为0，也就是[3, 4, 0, 1]，我们可以看成第1位，第2位，第3位的意思。
找到这个数组就很简单了，我们先遍历老节点，找到对应的新节点，然后加入到新节点对应的坐标上。我们开始遍历了，在遍历过程中，会执行patch和卸载操作，如下图表格：
| 当前老坐标下标 | 当前找到的新节点坐标 | 新节点坐标下所对应的旧节点数组(初始值为0，代表新增，加进来坐标+1) |
|---|---|---|
| 0 | 3 | [0, 0, 0, 1] |
| 1 | 无 | 卸载 |
| 2 | 0 | [3, 0, 0, 1] |
| 3 | 1 | [3, 4, 0, 1] |
遍历完数组后，最后得到的数组为[3, 4, 0, 1]，然后我们会找到它的最长增长子序列为3, 4，它所对应的是第一个节点D和第二个节点E，所以这两个节点是不需要动的。
最后我们再遍历新节点，如果我们当前的节点与在最长增长子序列中，则不移动，为0则直接新增，剩下的则移动到当前位置。
到这里大致的流程就已经结束了，我们在跟着源码进行一次深入的了解吧~
源码
源码文件路径：packages/runtime-core/src/renderer.ts
源码仓库地址：vue-next
patchChildren
我们从patchChildren方法开始，进行子节点之间的比较。
const patchChildren: PatchChildrenFn = () => {
// 获得当前新旧节点下的子节点们
const c1 = n1 && n1.children
const prevShapeFlag = n1 ? n1.shapeFlag : 0
const c2 = n2.children
const { patchFlag, shapeFlag } = n2
// fragment有两种类型的静态标记：子节点有key、子节点无key
if (patchFlag > 0) {
if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
// 子节点全部或者部分有key
patchKeyedChildren()
return
} else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
// 子节点没有key
patchUnkeyedChildren()
return
}
}
// 子节点有三种可能：文本节点、数组（至少一个子节点）、没有子节点
if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {
// 匹配到当前是文本节点：卸载之前的节点，为其设置文本节点
unmountChildren()
hostSetElementText()
} else {
// old子节点是数组
if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
// 现在(new)也是数组（至少一个子节点），直接full diff（调用patchKeyedChildren()）
} else {
// 否则当前没有子节点，直接卸载当前所有的子节点
unmountChildren()
}
} else {
// old的子节点是文本或者没有
if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
// 清空文本
hostSetElementText(container, '')
}
// 现在(new)的节点是多个子节点，直接新增
if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
// 新建子节点
mountChildren()
}
}
}
}我们可以直接用文本描述一下这段代码：
1、获得当前新旧节点下的子节点们(c1、c2)
2、使用patchFlag进行按位与判断fragment的子节点是否有key（patchFlag是什么稍后下面说）
3、不管有没有key，只要匹配成功一定是数组，有key/部分有key则调用patchKeyedChildren方法进行diff计算，无key则调用patchUnkeyedChildren方法
4、不是fragment节点，那么子节点有三种可能：文本节点、数组(至少一个子节点)、没有子节点
5、如果new的子节点是文本节点：old有子节点的话则直接进行卸载，并为其设置文本节点
6、否则new的子节点是数组 or 无节点，在这个基础上：
7、如果old的子节点为数组，那么new的子节点也是数组的话，调用patchKeyedChildren方法，直接full diff，否则new没有子节点，直接进行卸载
8、最后old的子节点为文本节点 or 没有节点（此时新节点可能为数组，也可能没有节点），所以当old的子节点为文本节点，那么则清空文本，new节点如果是数组的话，直接新增
9、此时所有的情况已经处理完毕了，不过真正的diff还没开始，那我们来看一下没有key的情况下，是否进行diff的
patchUnkeyedChildren
没有key的处理比较简单，直接上删减版源码
const patchUnkeyedChildren = () => {
c1 = c1 || EMPTY_ARR
c2 = c2 || EMPTY_ARR
const oldLength = c1.length
const newLength = c2.length
// 拿到新旧节点的最小长度
const commonLength = Math.min(oldLength, newLength)
let i
// 遍历新旧节点，进行patch
for (i = 0; i < commonLength; i++) {
// 如果新节点已经挂载过了(已经过了各种处理)，则直接clone一份，否则创建一个新的vnode节点
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
patch()
}
// 如果旧节点的数量大于新节点数量
if (oldLength > newLength) {
// 直接卸载多余的节点
unmountChildren( )
} else {
// old length < new length => 直接进行创建
mountChildren()
}
}我们继续文本描述一下逻辑：
1、首先会拿到新旧节点的最短公共长度
2、然后遍历公共部分，直接进行patch
3、如果旧节点的数量大于新节点数量，直接卸载多余的节点，否则新建节点
patchKeyedChildren
到了Diff算法比较核心的部分，我们先看一个大概预览，了解一下流程~再把patchKeyedChildren源码内部拆分一下，逐步来看。
const patchKeyedChildren = () => {
let i = 0
const l2 = c2.length
let e1 = c1.length - 1 // prev ending index
let e2 = l2 - 1 // next ending index
// 1. 进行头部遍历，遇到相同节点则继续，不同节点则跳出循环
while (i <= e1 && i <= e2) {}
// 2. 进行尾部遍历，遇到相同节点则继续，不同节点则跳出循环
while (i <= e1 && i <= e2) {}
// 3. 如果旧节点已遍历完毕，并且新节点还有剩余，则遍历剩下的进行新增
if (i > e1) {
if (i <= e2) {}
}
// 4. 如果新节点已遍历完毕，并且旧节点还有剩余，则直接卸载
else if (i > e2) {
while (i <= e1) {}
}
// 5. 新旧节点都存在未遍历完的情况
else {
// 5.1 创建一个map，为剩余的新节点存储键值对，映射关系：key => index
// 5.2 遍历剩下的旧节点，新旧数据对比，移除不使用的旧节点
// 5.3 拿到最长递增子序列进行move or 新增挂载
}
}1、第一步是进行头部遍历，遇到相同节点则继续，下标 + 1，不同节点则跳出循环
// 1. sync from start
// (a b) c
// (a b) d e
while (i <= e1 && i <= e2) {
const n1 = c1[i]
// 如果新节点已经挂载过了(已经经历了各种处理)，则直接clone一份，否则创建一个新的vnode节点
const n2 = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
// 相同节点，则继续执行patch方法
if (isSameVNodeType(n1, n2)) {
patch()
} else {
break
}
i++
}
此时i = 2, e1 = 6, e2 = 7, 旧节点剩下C、D、E、F、G，新节点剩下D、E、I、C、F、G
这里判断是否为相同节点的方法isSameVNodeType，是通过类型和key来进行判断，在Vue2中是通过key和sel(属性选择器)来判断是否是相同元素。这里的类型指的是ShapeFlag，也是一个标志位，是对元素的类型进行不同的分类，比如：元素、组件、fragment、插槽等等
export function isSameVNodeType(n1: VNode, n2: VNode): boolean {
return n1.type === n2.type && n1.key === n2.key
}2、第二步是进行尾部遍历，遇到相同节点则继续，length - 1，不同节点则跳出循环
// 2. sync from end
// a (b c)
// d e (b c)
// 进行尾部遍历，遇到相同节点则继续，不同节点则跳出循环
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = (c2[e2] = optimized
? cloneIfMounted(c2[e2] as VNode)
: normalizeVNode(c2[e2]))
if (isSameVNodeType(n1, n2)) {
patch()
} else {
break
}
e1--
e2--
}
此时i = 2, e1 = 4, e2 = 5, 旧节点剩下C、D、E，新节点剩下D、E、I、C
3、如果旧节点已遍历完毕，并且新节点还有剩余，则遍历剩下的进行新增
// 3.common sequence + mount
// (a b)
// (a b) c
// i = 2, e1 = 1, e2 = 2
// (a b)
// c (a b)
// i = 0, e1 = -1, e2 = 0
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1
const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
while (i <= e2) {
patch(null, c2[i]) // 节点新增(伪代码)
i++
}
}
}因为我们上面的图例(i < e1)走不到这段逻辑，所以我们可以直接看一下代码注释(注释真的写得非常详细了，patchKeyedChildren里面的原注释我都保留了)。如果旧节点遍历完毕，开头或者尾部还剩下了新节点，则进行节点新增(通过传参，patch内部会处理)。
4、如果新节点已经遍历完毕，则说明多余的节点需要卸载
// 4.common sequence + unmount
// (a b) c
// (a b)
// i = 2, e1 = 2, e2 = 1
// a (b c)
// (b c)
// i = 0, e1 = 0, e2 = -1
else if (i > e2) {
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true)
i++
}
}因为我们上面的图例(i < e2)依然走不到这段逻辑，所以我们可以继续看一下原注释。i > e2意味着新节点遍历完毕，如果新节点遍历完毕，开头或者尾部还剩下了旧节点，则进行节点卸载unmount。
5、新旧节点都没有遍历完成的情况
// 5. unknown sequence
// [i ... e1 + 1]: a b [c d e] f g
// [i ... e2 + 1]: a b [e d c h] f g
// i = 2, e1 = 4, e2 = 5
else {
const s1 = i // prev starting index
const s2 = i // next starting index
...
}按照上面图的例子来看，s1 = 2, s2 = 2，旧节点剩下C、D、E，新节点剩下D、E、I、C需要继续进行diff
5.1、生成map对象，通过键值对的方式存储新节点的key => index
// 5.1 build key:index map for newChildren
// 创建一个空的map对象
const keyToNewIndexMap = new Map()
// 遍历剩下没有patch的新节点，也就是D、E、I、H
for (i = s2; i <= e2; i++) {
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
// 如果剩余的新节点有key的话，则将其存储起来，key对应index
if (nextChild.key != null) {
keyToNewIndexMap.set(nextChild.key, i)
}
}执行完上面的方法，得到keyToNewIndexMap = {D => 2, E => 3, I => 4, C => 5},keyToNewIndexMap主要用来干嘛呢~请继续往下看
5.2、遍历剩下的旧节点，新旧数据对比，移除不使用的旧节点
// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
let j
// 记录即将被patch过的新节点数量
let patched = 0
// 拿到剩下要遍历的新节点的长度，按照上面的图示toBePatched = 4
const toBePatched = e2 - s2 + 1
// 是否发生过移动
let moved = false
// 用于跟踪是否有任何节点移动
let maxNewIndexSoFar = 0
// works as Map<newIndex, oldIndex>
// 注意：旧节点 oldIndex偏移量 + 1
// 并且oldIndex = 0是一个特殊值，代表新节点没有对应的旧节点
// newIndexToOldIndexMap主要作用于最长增长子序列
// newIndexToOldIndexMap从变量名可以看出，它代表的是新旧节点的对应关系
const newIndexToOldIndexMap = new Array(toBePatched)
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
// 此时newIndexToOldIndexMap = [0, 0, 0, 0]
// 遍历剩余旧节点的长度
for (i = s1; i <= e1; i++) {
const prevChild = c1[i]
if (patched >= toBePatched) {
// patched大于剩余新节点的长度时，代表当前所有新节点已经patch了，因此剩下的节点只能卸载
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
let newIndex
if (prevChild.key != null) {
// 旧节点的key存在的话，则通过旧节点的key找到对应的新节点的index位置下标
newIndex = keyToNewIndexMap.get(prevChild.key)
} else {
// 旧节点没有key的话，则遍历所有的新节点
for (j = s2; j <= e2; j++) {
// newIndexToOldIndexMap[j - s2]如果等于0的话
// 代表当前新节点还没有被patch，因为在下面的运算中
// 如果找到新节点对应的旧节点位置，newIndexToOldIndexMap[j - s2]则会等于旧节点的下标 + 1
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j] as VNode)
) {
// 当前新节点还没有被找到，并新旧节点相同，则将新节点的位置赋予newIndex
newIndex = j
break
}
}
}
if (newIndex === undefined) {
// 当前旧节点没有找到对应的新节点，则进行卸载
unmount(prevChild, parentComponent, parentSuspense, true)
} else {
// 找到了对应的新节点，则将旧节点的位置存储在对应的新节点下标
newIndexToOldIndexMap[newIndex - s2] = i + 1
// maxNewIndexSoFar如果不是逐级递增，则代表有新节点的位置前移了，那么需要进行移动
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
// 更新节点差异
patch()
// 找到一个对应的新节点，+1
patched++
}
}这段代码比较长，但是总的来说做了下面几件事：
1、拿到新节点对应的旧节点下标newIndexToOldIndexMap(下标+1,因为0代表的是新节点没有对应的旧节点，直接创建新节点)，在我们的图例中newIndexToOldIndexMap = [4, 5, 0, 3]。
2、存在在遍历的过程中，如果老节点找到对应的新节点，则进行打补丁，更新节点差异，找不到则删除该老节点
3️、通过新节点下标的顺序是否递增来判断，是否有节点发生过移动
5.3、对剩下没有找到的新节点进行挂载，对需要移动的节点进行移动
// 5.3 move and mount
// 仅在有节点需要移动的时候才生成最长递增子序列
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
j = increasingNewIndexSequence.length - 1
// 此时图示中的increasingNewIndexSequence = [4, 5]
// 从后面开始遍历，将最后一个patch的节点用作锚点
for (i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i
const nextChild = c2[nextIndex] as VNode
const anchor =
nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
// 代表新增
if (newIndexToOldIndexMap[i] === 0) {
// mount new
patch( )
} else if (moved) {
// 移动的条件：当前最长子序列的length小于0(没有稳定的子序列)，或者当前的节点不在稳定的序列中
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, MoveType.REORDER)
} else {
j--
}
}
}最后这段源码用到了一个优化方法，最长上升子序列，这段大致的流程就是：
1、通过moved来判断当前是否有节点进行了移动，如果有的话则通过getSequence(newIndexToOldIndexMap)拿到最长上升子序列，我们的图示中拿到的是increasingNewIndexSequence = [4, 5]
2、遍历剩余新节点的长度，从后面开始遍历，判断newIndexToOldIndexMap[i] === 0，当前的新节点是否有对应的老节点，如果等于0，就是没有，直接新增。
3、否则通过moved判断是否有移动，有移动的话，如果当前最长子序列的length小于0，或者当前的节点不在稳定的序列中，则意味着现在没有稳定的子序列，每个节点需要进行移动，或者，最后一个新节点，不在末尾的子序列中，子序列的末尾另有他人，那当前也需要进行移动。若是不符合移动的条件，则说明当前新节点在最长上升子序列中，不需要进行移动，只用等待别的节点去移动。
到这里，diff算法的核心流程就了解得差不多了~有机会再把最长子序列求解补上。
参考资料：查看原文
源码：https://github.com/vuejs/vue-...
diff优化策略：https://neil.fraser.name/writ...
inforno：https://github.com/infernojs/inferno
https://blog.csdn.net/u014125...
https://zhuanlan.zhihu.com/p/...
https://hustyichi.github.io/2...
https://www.cnblogs.com/Windr...
通过上述流程，小程序的
