【源码&库】 Vue3 的组件更新核心算法
接着上一篇的节奏，上一篇我们过了一遍普通dom元素的一个简单的更新过程，也大致的知道了更新的过程是什么样的，但是没有接触核心；
那么核心是什么呢？通常我们说的核心指代的就是Vue的组件更新核心算法；
首先我们还是编写一下demo，然后再来分析一下Vue的组件更新核心算法；
const {h, render} = Vue;
const app = document.createElement("div");
document.body.appendChild(app);
const component = h('ul',
[
h('li', '1'),
h('li', '2'),
h('li', '3'),
h('li', '4'),
h('li', '5'),
]
);
render(component, app);
const component2 = h('ul',
[
h('li', '2'),
h('li', '3'),
h('li', '4'),
h('li', '5'),
h('li', '1'),
]
);
debugger
render(component2, app);
根据官方文档可得h函数是重载过的函数，这里只需要传入两个参数即可，第一个参数是tag，第二个参数是children，这里就不多说了，可以去看官方文档；
在我们第二次使用h函数的时候，我将第一个li放到了最后，然后在render的时候打了一个断点，开始这次的源码分析；
patchChildren 函数
在上一章中我们知道了dom更新会调用到patchChildren函数，上一章只有文本节点的情况，文本节点是最简单的，只需要替换文本内容即可；
而这一章我们的children是一个数组，将会进入不同的分支，我们先来看一下简化后的patchChildren函数源码；
/**
* @param n1 旧的 VNode
* @param n2 新的 VNode
* @param container 真实 DOM
*/
const patchChildren = (n1, n2, container) => {
// 获取新旧 VNode 的 children，这里是 Hellow! 和 world! 文本内容
const c1 = n1 && n1.children;
const prevShapeFlag = n1 ? n1.shapeFlag : 0;
const c2 = n2.children;
const {shapeFlag, patchFlag} = n2;
// TODO 这里开始是上一章的内容
// shapeFlag 指代的是 VNode 的类型，这里是文本类型，目前还没完全摸清楚
if (shapeFlag & 8) {
// 两个文本节点不相等，那么就直接更新文本内容
if (c2 !== c1) {
hostSetElementText(container, c2);
}
}
// TODO 这里开始是这一章的内容
else {
// 旧的 VNode 是数组类型
if (prevShapeFlag & 16) {
// 新的 VNode 也是数组类型
if (shapeFlag & 16) {
// 进入 patchKeyedChildren 函数
patchKeyedChildren(
c1,
c2,
container
);
}
}
}
};
这里暂时不用太在意 shapeFlag 的含义是什么，根据目前的情况可以很明显的看出来代表的是
vnode的类型，后面会详细分析；
patchKeyedChildren 函数
这里我们就进入了核心，在patchKeyedChildren函数中，我们可以看到这个函数的作用是对比新旧children，然后进行更新；
patchKeyedChildren函数的内容很长，这里因为我们没有使用key也没有改变dom的标签类型，所以只会走一部分的逻辑；
这里我将这部分的逻辑抽离出来，方便大家阅读：
/**
* @param c1 - 原始子节点
* @param c2 - 新子节点
* @param container - 父容器
*/
const patchKeyedChildren = (c1, c2, container) => {
let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1;
let e2 = l2 - 1;
// 遍历新旧子节点, 对比节点是否发生变化
while (i <= e1 && i <= e2) {
const n1 = c1[i];
const n2 = c2[i];
// 如果新旧子节点相同, 则进行 patch
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container
);
} else {
break;
}
i++;
}
};
/**
* @param n1 - 原始节点
* @param n2 - 新节点
*/
function isSameVNodeType(n1, n2) {
// 两个节点的 type 和 key 都相同, 则认为是相同节点
return n1.type === n2.type && n1.key === n2.key;
}
这里我们可以看到的最开始就直接遍历了新旧子节点，然后对比节点是否发生变化，如果没有发生变化则直接进行patch，如果发生了变化则直接跳出循环；
patch函数很熟了，组件的任何变化都会调用到patch函数，之前也都介绍过，忘记了的可以回头看看之前的文章；
到这一步，我们上面写的示例demo就已经更新完成了，同时我们了解到了一个很关键的信息，dom是否发生变化是通过key和type来判断的；
而这里的patch的执行过程就是我们上一章的内容，到这里我们已经学习到了一个小阶段；
核心算法掐头去尾
上面我们看到的代码是俗称掐头去尾中的掐头，可以看到上面的代码如果发现子节点不同就会直接break跳出循环，跳出循环之后就完成了掐头的操作；
那么去尾是什么呢？我们先修改一下demo，再在后面加上这样的代码：
const component3 = h('ul',
[
h('li', '1'),
h('li', '2'),
h('li', '3'), // 这里将li改成了span
h('li', '4'),
h('li', '5'),
]
);
render(component3, app);
我们将第三个li改成了span，然后再次调用render函数，这个时候patchKeyedChildren函数就会进入去尾的操作；
const patchKeyedChildren = (c1, c2, container) => {
let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1;
let e2 = l2 - 1;
// 掐头
while (i <= e1 && i <= e2) {
// ...
}
// 去尾
while (i <= e1 && i <= e2) {
// 这里的逻辑和上面的一样
const n1 = c1[e1];
const n2 = c2[e2];
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container
);
} else {
break;
}
// 去尾操作 i 的指针不变，e1 和 e2 的指针向前移动
e1--;
e2--;
}
};
这里的去尾操作就是将e1和e2的指针向前移动，然后再次进行对比，如果相同则进行patch，如果不同则跳出循环；
去尾操作和掐头操作是一样的，不同的是移动的指针不同，掐头操作是移动i指针，去尾操作是移动e1和e2指针；
如果全都是相同节点，那么就不会有
去尾操作，这个时候如果是有新增的节点，意思是e2(新节点的数量)大于i(这个时候i是旧节点数量)那么会进入patch函数进行添加；如果有删除的节点，那么
e2(新节点的数量)小于i(这个时候i是旧节点数量)，那么会进入unmount函数进行删除；由于这一块相对来说简单很多，所以不单独做演示代码和讲解，下面是源码：
if (i > e1) { if (i <= e2) { const nextPos = e2 + 1; const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor; while (i <= e2) { patch( null, c2[i] = optimized ? cloneIfMounted(c2[i]) : normalizeVNode(c2[i]), container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized ); i++; } } } else if (i > e2) { while (i <= e1) { unmount(c1[i], parentComponent, parentSuspense, true); i++; } } else { // 这里是核心的 diff 算法 }
核心算法
上面我们已经了解了掐头去尾的操作，核心算法就是处理剩下不规则的情况，这里的代码量有点大，需要大家耐心看完；
先还是来编写一下demo：
const component3 = h('ul',
[
h('span', '1'),
h('li', '2'),
h('p', '3'),
h('div', '4'),
h('h1', '5'),
]
);
render(component3, app);
const component4 = h('ul',
[
h('h1', '5'),
h('div', '4'),
h('li', '2'),
h('p', '3'),
h('span', '1'),
]
);
render(component4, app);
下面是简化后的源码：
if (i > e1) {
// ...
} else if (i > e2) {
// ...
} else {
// 两个指针，都指向的是未处理的节点的起始位置
const s1 = i;
const s2 = i;
let j;
let patched = 0; // 已经处理了多少个节点
// e2 是新节点的结束位置
// s2 是处理到什么地方了
// e2 - s2 + 1 表示需要打补丁的节点有多少个
const toBePatched = e2 - s2 + 1;
let moved = false; // 复用节点的标识
let maxNewIndexSoFar = 0; // 到目前为止，新节点中最大的索引值，这里指的是复用节点的索引值
// 用来存储新节点的索引值到旧节点索引值的映射
const newIndexToOldIndexMap = new Array(toBePatched);
// 这里先初始化为 0，表示都没有复用
for (i = 0; i < toBePatched; i++)
newIndexToOldIndexMap[i] = 0;
// e1 是旧节点的结束位置
for (i = s1; i <= e1; i++) {
// 遍历旧节点，拿到每一个节点
const prevChild = c1[i];
// 如果已经处理的节点的数量大于等于需要处理的节点的数量
// 说明新节点中所有的节点都已经处理完毕了，这个时候只需要卸载剩余的旧节点即可
if (patched >= toBePatched) {
unmount(prevChild, parentComponent, parentSuspense, true);
continue;
}
// 拿到新节点的索引值
let newIndex;
// 这里的 j 是新节点的索引值，遍历新节点
for (j = s2; j <= e2; j++) {
// j - s2 表示缓存新旧节点的索引表中的索引值
// === 0 表示这个节点还没有被处理过
// isSameVNodeType 上面介绍过，判断两个节点是否相同
if (newIndexToOldIndexMap[j - s2] === 0 && isSameVNodeType(prevChild, c2[j])) {
// 找到了相同的节点，记录一下索引值
newIndex = j;
break;
}
}
// void 0 是 undefined 的简写
// 没有找到相同的节点，说明这个节点是不需要复用的，直接卸载即可
if (newIndex === void 0) {
unmount(prevChild, parentComponent, parentSuspense, true);
} else {
// 找到了相同的节点，记录一下旧节点的索引值
newIndexToOldIndexMap[newIndex - s2] = i + 1;
// 如果新节点的索引值大于之前记录的最大索引值，就记录一下
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex;
} else {
// 否则，说明新节点的顺序被打乱了，需要移动节点
moved = true;
}
// 调用 patch 方法，将新旧节点传递进去
// 这里的 patch 方法只是更新复用的节点，能够复用的节点都已经处理完毕了
patch(
prevChild,
c2[newIndex],
container,
null
);
// 已处理的节点数量 + 1
patched++;
}
}
// 如果是乱序的节点，需要移动节点
// newIndexToOldIndexMap 存储的是新节点的索引值到旧节点索引值的映射
// getSequence 会返回一个递增的索引值数组，稍后说这个
const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : EMPTY_ARR;
j = increasingNewIndexSequence.length - 1;
// 所以这里遍历的其实是新节点中需要打补丁的节点，而不是需要移动的节点
for (i = toBePatched - 1; i >= 0; i--) {
// 拿到新节点的索引值
const nextIndex = s2 + i;
// 拿到新节点
const nextChild = c2[nextIndex];
// 插入的位置，anchor 是下一个节点的位置
// 如果是最后一个节点，anchor 就是父容器的结束位置
const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor;
// 如果这个节点没有被处理过，说明是新节点，直接使用 patch 方法即可
if (newIndexToOldIndexMap[i] === 0) {
patch(
null,
nextChild,
container,
anchor
);
} else if (moved) {
// 如果是乱序的节点，需要移动节点
// j < 0 说明没有需要移动的节点了
// i !== increasingNewIndexSequence[j] 表示当前节点已经是在正确的位置了，不需要移动
// 这里的 i 表示当前节点的索引值
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, 2);
} else {
j--;
}
}
}
}
稍微剥离一下代码，咱一步一步的来，首先是新旧索引节点的映射:
// 用来存储新节点的索引值到旧节点索引值的映射
const newIndexToOldIndexMap = new Array(toBePatched);
// 这里先初始化为 0，表示都没有复用
for (i = 0; i < toBePatched; i++)
newIndexToOldIndexMap[i] = 0;
这里的newIndexToOldIndexMap的索引就是新节点的索引值，值就是旧节点的索引值，这里的值初始化为0，表示没有旧节点可以复用；
然后就是寻找可以复用的节点，拿到复用节点的新节点的索引值：
// 拿到新节点的索引值
let newIndex;
// 这里的 j 是新节点的索引值，遍历新节点
for (j = s2; j <= e2; j++) {
// j - s2 表示缓存新旧节点的索引表中的索引值
// === 0 表示这个节点还没有被处理过
// isSameVNodeType 上面介绍过，判断两个节点是否相同
if (newIndexToOldIndexMap[j - s2] === 0 && isSameVNodeType(prevChild, c2[j])) {
// 找到了相同的节点，记录一下索引值
newIndex = j;
break;
}
}
接下来就是打补丁的操作，没有可以复用的节点就直接卸载，有可以复用的节点就调用patch函数进行更新，并记录一下索引值：
// 没有找到相同的节点，说明这个节点是不需要复用的，直接卸载即可
if (newIndex === void 0) {
unmount(prevChild, parentComponent, parentSuspense, true);
} else {
// 找到了相同的节点，记录一下旧节点的索引值
newIndexToOldIndexMap[newIndex - s2] = i + 1;
// 如果新节点的索引值大于之前记录的最大索引值，就记录一下
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex;
} else {
// 否则，说明新节点的顺序被打乱了，需要移动节点
moved = true;
}
// 调用 patch 方法，将新旧节点传递进去
// 这里的 patch 方法只是更新复用的节点，能够复用的节点都已经处理完毕了
patch(
prevChild,
c2[newIndex],
container,
null
);
// 已处理的节点数量 + 1
patched++;
}
上面的代码由于最外层循环的就是旧节点，所以这里的i就是旧节点的索引值，newIndex就是新节点的索引值，这里的newIndexToOldIndexMap的索引就是新节点的索引值，值就是旧节点的索引值；
对于是否移动节点的判断可以说是非常巧妙了，这里的maxNewIndexSoFar就是记录的最大的索引值，仔细一看其实没有什么卵用；
因为通常情况下newIndex是递增的，不会出现小于maxNewIndexSoFar的情况，但是如果出现了这种情况，说明新节点的顺序被打乱了，这个时候就需要移动节点了；
后面就是处理乱序节点的逻辑，乱序节点存在两种情况，一种是新节点中存在旧节点中没有的节点，这个时候就需要插入节点；
还有一种就是复用旧节点，这个时候就需要移动节点；
// newIndexToOldIndexMap[i] === 0 表示这个节点是新节点，需要插入
if (newIndexToOldIndexMap[i] === 0) {
patch(
null,
nextChild,
container,
anchor
);
} else if (moved) {
// 如果是乱序的节点，需要移动节点
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, 2);
} else {
j--;
}
}
这里的i就是当前节点的索引值，这里的i是从后往前遍历的，j同样也是从后往前遍历的；
increasingNewIndexSequence[j]如果等于i，说明当前节点已经在正确的位置了，不需要移动；
通常情况下所有的节点都需要移动，但是有了increasingNewIndexSequence可以确定哪些节点不需要移动，这样就可以减少移动的次数；
而j < 0说明不需要移动的节点已经处理完毕了，这个时候当前的节点还不在正确的位置，需要移动；
getSequence 函数
上面的代码中有一个getSequence函数，这个函数就是我们常听到的返回最长递增子序列的函数，这个函数的作用就是返回一个递增的索引值数组；
意思就是给定一个数组，返回这个数组内递增的索引值数组，用来确定那些节点不需要移动；
function getSequence(arr) {
// 对 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];
// 过滤掉 0
if (arrI !== 0) {
// 拿到结果数组的最后一个值
j = result[result.length - 1];
// 最后一个值小于当前值，直接 push 进去，是递增的，然后继续下一次循环
if (arr[j] < arrI) {
p[i] = j;
result.push(i);
continue;
}
// 二分查找，找到第一个大于等于当前值的索引值
u = 0;
v = result.length - 1;
while (u < v) {
c = u + v >> 1;
if (arr[result[c]] < arrI) {
u = c + 1;
} else {
v = c;
}
}
// 如果找到的索引值大于 0，说明找到了第一个大于等于当前值的索引值
// 这个时候需要更新结果数组，同时更新 p 数组回溯最长递增子序列的索引顺序
// 这个时候更新 p 的目的是用
if (arrI < arr[result[u]]) {
if (u > 0) {
p[i] = result[u - 1];
}
result[u] = i;
}
}
}
// 回溯最长递增子序列的索引顺序
// 通过反向向 p 数组查找，找到最长递增子序列的索引值
u = result.length;
v = result[u - 1];
while (u-- > 0) {
result[u] = v;
v = p[v];
}
// 返回最长递增子序列的索引值
return result;
}
代码还是有点小复杂的，需要花时间去理解，本身我也是一个算法渣渣，所以这里就不做过多的解释了，有兴趣的可以去刷刷算法题，提升一下自己的能力；
总结
到这里我们就学习完了Vue的组件更新核心算法，这里的核心算法就是diff算法，diff算法的核心就是掐头去尾，然后处理剩下的不规则情况；
不规则的情况分很多种，有可能是在列表中插入或删除节点，有可能是节点的顺序发生了变化，而最复杂的就是顺序发生了变化，这个时候就需要移动节点了；
vue为了尽可能的高效复用节点，所以在处理乱序节点的时候，使用了getSequence函数，这个函数的作用就是返回一个递增的索引值数组，用来确定哪些节点不需要移动；
到这里我们就学习完了Vue的组件更新核心算法，真的有点烧脑；