diff算法
为什么要用diff？
Vue是基于依赖收集完成的响应式，当一个节点发生改变时，它相关的节点都会被更新。如果对所有的组件都进行更新，那么对性能的影响是很大的，如果可以找出其中不需要更新的地方，只更新需要更改的部分，那么性能也会得到较大的提升，这就是diff算法存在的必要性。通过新旧 vnode 比对，从而找到实际需要更新的结点，再进行更新，这个过程称为 patch。
diff算法实现
简单的实现diff算法，分三种情况：
- tag不同的比较：直接替换
- props不同的比较：新props在老props中没有或更改，直接添加和替换成新props，老props中有而新props中没有则删除
- children不同的比较：
如果新的children是string，与旧children不相等的话则直接替换；
如果新的children是array，旧的children是string，则去掉旧children，将新children依次渲染；
如果新的children是array，旧的children也是array，简化考虑二者位置不变，取二者的最小长度length，对这部分每一个node做diff算法，再判断新children长度是否大于length，如果大于就添加，而老children长度大于length则删除
export function diff(n1, n2) {const el = n2.el = n1.el;if (n1.tag !== n2.tag) {n1.el.replaceWith(createElement(n2.tag))} else {const newProps = n2.props;const oldProps = n1.props;if (newProps) {for (const key in newProps) {if (newProps[key] !== oldProps[key]) {patchProps(el, key, oldProps[key], newProps[key]);}}}if (oldProps) {for (const key in oldProps) {if (!(key in newProps)) {patchProps(el, key, oldProps[key], null);}}}const newChildren = n2.children;const oldChildren = n1.children;if (typeof newChildren === 'string') {if (newChildren !== oldChildren) {el.innerText = newChildren}} else if(Array.isArray(newChildren)) {if (typeof oldChildren === 'string') {el.innerText = '';newChildren.forEach((v) => {mountElement(v, el)})} else if (Array.isArray(oldChildren)) {const length = Math.min(newChildren.length, oldChildren.length);for (let i = 0; i < length; i++) {const newVnode = newChildren[i];const oldVnode = oldChildren[i];diff(oldVnode, newVnode);}if (newChildren.length > length) {for (let i = length; i < newChildren.length; i++) {mountElement(newChildren[i], el);}}if (oldChildren.length > length) {for (let i = length; i < oldChildren.length; i++) {el.removeChild(oldChildren[i].el);}}}}}
}
新旧children都是array的情况
新旧的children都是array的情况，利用双边对比算法。具体为：
- 先从左边查找，比较new[i]和old[i]，如果节点可以复用，那么复用本节点并继续往后比较，即i++重复本步骤。如果不能复用，则中止本循环（0<= i <old.length, i<new.length）
- 从右边查找，比较new[e1]和old[e2]，如果节点可以复用，那么复用本节点并继续往后比较，即e1–; e2–; 重复本步骤。如果不能复用，则中止本循环（0<= e1 <old.length, 0<= e1 <new.length）。
经过以上两步骤之后，只剩下了中间有点乱的序列。
从左边向右边查找
从左边往右查找，如果节点可以复用，则继续往右，不能就停止循环。注意下面while循环的终止条件包括两个：1. 数组越界 2. 节点不能再复用。
// *1. 从左边往右查找，如果节点可以复用，则继续往右，不能就停止循环while (i <= e1 && i <= e2) {const n1 = c1[i];const n2 = c2[i]; if (isSameVnodeType(n1, n2)) { patch(n1.key); } else { break; } i++;}
从右边向左边查找
从右边往左边查找，如果节点可以复用，则继续往左，不能就停止循环。和上一步一样，下面while循环的终止条件包括两个：1. 数组越界 2. 节点不能再复用。
// *2. 从右边往左边查找，如果节点可以复用，则继续往左，不能就停止循环
while (i <= e1 && i <= e2) {const n1 = c1[e1];const n2 = c2[e2];if (isSameVnodeType(n1, n2)) {patch(n1.key);} else {break;}e1--;e2--;
}
old或者new已经遍历完成
经过以上两步，可能会出现以下两种情况：
old没了，而new还有
如下面的例子：
// old (a b)
// new (a b) c
那么这个时候，只需要把new剩下的元素逐个新增。实现代码如下：
if (i > e1) {if (i <= e2) {while (i <= e2) {const n2 = c2[i];mountElement(n2.key);i++;}}
}
new没了，而old还有
如下面的例子：
// old (a b) c
// new (a b)
那么这个时候，只需要把old剩下的元素逐个删除就行了，实现代码如下：
// 这里的else if承接上段代码的if
else if (i > e2) {while (i <= e1) {const n1 = c1[i];unmount(n1.key);i++;}
}
凌乱的中间
经过了上面的左右夹击，old和new都还有，这个时候我们就要想办法复用了这”凌乱的“的中间部分节点了。参考例子如下：
// old [i ... e1 + 1]: a b [c d e] f g
// new [i ... e2 + 1]: a b [e c d h] f g
经过第1步，patch了ab，经过第2步，patch了fg，接下来我们只剩下了凌乱的c d e和e c d h。肉眼可见，cde是要patch的，h是mountElement的，并且原先的cde要变成新顺序的ecd是要move的。
问题来了，鉴于中间顺序的凌乱，如果我们先遍历old，我们该如何高效地从new中对应的节点呢？当然你可以选择暴力找，但是如果new中的每个节点都通过for循环去old中暴力找，效率太低了。而且等会儿我们还要根据检查old和new的相对顺序变化来判断是否要移动节点呢，所以怎么办？
把new做成Map图
鉴于单纯地通过key去old数组中找节点不好找，我们就把new数组的元素做成key:value的Map不就行了，代码如下：
const s1 = i;
const s2 = i;
const keyToNewIndexMap = new Map();
for (i = s2; i <= e2; i++) {const nextChild = c2[i];keyToNewIndexMap.set(nextChild.key, i);
}
学过React VDOM DIFF的可以再来思考一个问题，React中也用到了Map，只不过是把old拼了个Map，但是React中Map的value取值的是vnode，而我们这里却用的下标i，为什么？
这里就涉及到数据结构了，react中的old是fiber单链表结构，无法快速找到节点，所以想通过key快速找节点的话，只能存vnode。而vue的old是数组，也就意味着通过下标就能快速找到节点，既然如此，那value就存下标i就可以了，还可以记录位置，方便又省事儿~
记录节点位置
这一步主要是记录位置，可以先只看toBePatched和patched这两个值。
// 注意这里的命名patch不是指复用哈，而是包括了复用和新增
// 前面文章中我用绿色字体说过了，Vue3源码中的patch包括了复用和新增
// 本文中代码为了方便TDD，patch我只代表复用，而mountElement代表新增
const toBePatched = e2 - s2 + 1;
// 还剩下多少个新节点没处理
// 计数值，就是算一算新增已经复用或者新增了多少个新节点了，每复用或者新增一个新节点，patched就加1
// 如果patched >= toBePatched，那么证明new处理完成。剩下的老节点就unmount就行啦
let patched = 0;const newIndexToOldIndexMap = new Array(toBePatched);
// 下标是新元素的相对下标，初始值是0，
// 在4.3中如果检查到节点能复用的话，值会更新为老元素的下标+1，那么最小值就是1
// 也就是说4.4中会根据newIndexToOldIndexMap[i]的值判断点是否有被复用过，如果是0，则证明没有被复用过。
for (i = 0; i < toBePatched; i++) {newIndexToOldIndexMap[i] = 0;
}
遍历old，patch节点
刚刚已经有了new的Map，那么我们接下来就可以遍历old了，然后把能复用的节点patch了，先看简版：
// *4.3 先遍历老元素 检查老元素是否要被复用，如果能复用就patch，如果不能复用就删除
for (i = s1; i <= e1; i++) {const prevChild = c1[i];if (patched >= toBePatched) {unmount(prevChild.key);continue;}const newIndex = keyToNewIndexMap.get(prevChild.key);// 根据老节点的key去新节点的字段中找值，找到了就证明节点有复用，找不到就不复用呗if (newIndex === undefined) {// 节点没法复用unmount(prevChild.key);} else { // 参考4.3中代码的注释，这里对理解4.4很重要 newIndexToOldIndexMap[newIndex - s2] = i + 1;patch(prevChild.key); patched++; }
}
遍历新元素 mount move
在4.3中我们已经遍历完了old，把能复用的节点和要删除的节点都处理完了，相当于这个例子中我们已经处理完了cde的复用，但是cde除了要执行patch函数，还要移动节点才能变成ecd呀，而且新增h我们也还没处理呢。
// old [i ... e1 + 1]: a b [c d e] f g
// new [i ... e2 + 1]: a b [e c d h] f g
接下来我们还需要再来遍历new，从而执行move和mountElement。
遍历new很简单，但是问个小问题，这个遍历应该从前往后还是应该从后往前遍历呢？
先想下我们要做的事情，move或者mountElement对吧，而这两个函数其实用原生函数的方法都是通过appendChild或者insertBefore来实现的。appendChild是在容器内末尾插入元素，insertBefore则是在某个元素前面插入。如果我们从前向后遍历，例如先创建e，然后插到c前面，但是此时c还没有处理，无法保证c是否为稳定元素，是否还需要移动，所以接下来我们最好先去创建这个后面的元素。也就是遍历new可以从后面往前遍历。例如先处理h节点，将他插到f前面，而f一定是一个稳定节点。
另外注意，这里遍历的时候用的不是原先的数组下标，而是相对下标，用相对下标主要是为了判断节点是否需要移动的考虑~
// 相对下标
for (i = toBePatched - 1; i >= 0; i--) { const nextChildIndex = s2 + i; const nextChild = c2[nextChildIndex];// 判断nextChild是mount还是move// 在老元素中出现的元素可能要move，没有出现过的要mount if (newIndexToOldIndexMap[i] === 0) { mountElement(nextChild.key); } else { // 可能move }
}
最长递增子序列
如果old节点是cde，而new节点是ecdh，那么对于c和d而言，他们的相对位置其实没有改变，重新去append或insert的效率也可以做一下提升。所以可以在old中先找到一个位置稳定的序列，再将位置不稳定的节点插入这个稳定序列中，可以减少元素的移动次数从而提升效率。
使用最长递增子序列算法得到递增的索引，再将其他值insert到这个子序列中。
// 利用最长递增子序列来优化移动逻辑// 因为元素是升序的话，那么这些元素就是不需要移动的// 而我们就可以通过最长递增子序列来获取到升序的列表// 在移动的时候我们去对比这个列表，如果对比上的话，就说明当前元素不需要移动// 通过 moved 来进行优化，如果没有移动过的话 那么就不需要执行算法// getSequence 返回的是 newIndexToOldIndexMap 的索引值// 所以后面我们可以直接遍历索引值来处理，也就是直接使用 toBePatched 即可const increasingNewIndexSequence = getSequence(newIndexToOldIndexMap)let j = increasingNewIndexSequence.length - 1;// 遍历新节点// 1. 需要找出老节点没有，而新节点有的 -> 需要把这个节点创建// 2. 最后需要移动一下位置，比如 [c,d,e] -> [e,c,d]// 这里倒循环是因为在 insert 的时候，需要保证锚点是处理完的节点（也就是已经确定位置了）// 因为 insert 逻辑是使用的 insertBefore()for (let i = toBePatched - 1; i >= 0; i--) {// 确定当前要处理的节点索引const nextChildIndex = s2 + i;const nextChild = c2[nextChildIndex];if (newIndexToOldIndexMap[i] === 0) {// 说明新节点在老的里面不存在// 需要创建mountElement(nextChild.key); } else {// 需要移动// 1. j 已经没有了 说明剩下的都需要移动了// 2. 最长子序列里面的值和当前的值匹配不上， 说明当前元素需要移动if (j < 0 || increasingNewIndexSequence[j] !== i) {// 移动的话使用 insert 即可hostInsert(nextChild.el);} else {// 这里就是命中了 index 和 最长递增子序列的值// 当前元素不需要移动，所以可以移动指针了j--;}}}