VUE3.0的diff算法原理相比较vue2.X还是有很大改变的；最重要的改变有以下几点：标记静态节点不再全量对比，前置和后置元素预处理，利用"最长递增子序列"移动节点。
问题背景：在VUE2.X中当一个节点数据发生改变时，VUE会全量对比所有子节点，找出差异，进行复用和更新；然而子节点中的一些静态节点，无论如何是不会被改变的， 重新创建 这些静态节点并参与对比，显然造成了不小的性能浪费。
解决方案：VUE3.0引入了一个叫flag静态标记的东西，在生成虚拟节点的时候，会根据以下节点特点，为节点添加一个静态标记
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
const PatchFlagNames = { [1 /* TEXT */]: `TEXT`,(动态文本元素) [2 /* CLASS */]: `CLASS`,(动态绑定class元素) [4 /* STYLE */]: `STYLE`,(动态绑定style元素) [8 /* PROPS */]: `PROPS`,(动态props元素，且不含class和style绑定) [16 /* FULL_PROPS */]: `FULL_PROPS`,(动态绑定props，和有key的元素) [32 /* HYDRATE_EVENTS */]: `HYDRATE_EVENTS`,(事件监听的元素) [64 /* STABLE_FRAGMENT */]: `STABLE_FRAGMENT`,(子元素的订阅不会改变fragment的元素) [128 /* KEYED_FRAGMENT */]: `KEYED_FRAGMENT`,(自己或者资源所带有key的fragment的元素) [256 /* UNKEYED_FRAGMENT */]: `UNKEYED_FRAGMENT`,(没有key的fragment元素) [512 /* NEED_PATCH */]: `NEED_PATCH`,(带有ref的指令元素) [1024 /* DYNAMIC_SLOTS */]: `DYNAMIC_SLOTS`,(动态solt的组件元素) [2048 /* DEV_ROOT_FRAGMENT */]: `DEV_ROOT_FRAGMENT`, [-1 /* HOISTED */]: `HOISTED`,(静态元素) [-2 /* BAIL */]: `BAIL`(不是render生成的元素，eg：renderSlot) }; |
然后利用这些标记，知道哪些节点会改变，哪些节点不会改变；进而做到静态元素只渲染一次，只对比可能会改变的节点。
如何标记节点：只这样说还是难直观的看到VUE是怎样标记节点的，我们可以通过一个测试网址来了解一下。例如我们要生成两个虚拟节点：<span>我是一只小小鸟</span> <div>{{meg}}</div>；VUE是这么添加标记的：
静态节点提升：标记完了节点之后，VUE会把所有不参与更新的静态节点提升起来， 只做一次渲染 ，有用到该节点的地方直接复用不再重复渲染；在测试网址里我们可以勾选options-hostStatic来模拟该操作
事件监听缓存：事件监听被视为动态绑定，所以每次都会追踪它的变化，但是因为是同一个函数，所以不用追踪变化，为了优化性能，VUE会将事件监听缓存起来，用到的时候直接复用就行。我们可以通过测试网站勾选options-cacheHandlers来对比一下开启事件侦听器缓存前后的变化(例如渲染虚拟节点<div @click='sss'></div>)：
从子节点的比较开始说起；patchChildren相当于VUE2.0里的patchVnode，比较子节点的情况：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
const patchChildren = (n1, n2, container, anchor, parentComponent, parentSuspense, isSVG, optimized = false) => { const c1 = n1 && n1.children; const prevShapeFlag = n1 ? n1.shapeFlag : 0; const c2 = n2.children; const { patchFlag, shapeFlag } = n2; //当patchflg>0时，根据有key和没key执行不同的比较函数 if (patchFlag > 0) { if (patchFlag & 128 /* KEYED_FRAGMENT */) {//子节点有key值时，调用patchKeyedChildren函数进行比较子节点 patchKeyedChildren(c1, c2, container, anchor, parentComponent, parentSuspense, isSVG, optimized); return; } else if (patchFlag & 256 /* UNKEYED_FRAGMENT */) {//子节点没有key值时，调用patchUnkeyedChildren函数进行比较子节点 patchUnkeyedChildren(c1, c2, container, anchor, parentComponent, parentSuspense, isSVG, optimized); return; } } //节点不存在patchFlag或者patchFlag <= 0时：子节点情况分三种：文本节点，数组(至少有一个节点)，没节点 if (shapeFlag & 8 /* TEXT_CHILDREN */) {//1.子节点是文本节点时：删除旧节点的文本节点设置为新节点的文本 if (prevShapeFlag & 16 /* ARRAY_CHILDREN */) { unmountChildren(c1, parentComponent, parentSuspense); } if (c2 !== c1) { hostSetElementText(container, c2); } } else { if (prevShapeFlag & 16 /* ARRAY_CHILDREN */) {//2.旧节点至少一个子节点 if (shapeFlag & 16 /* ARRAY_CHILDREN */) {//新节点也至少有一个，直接调用patchKeyedChildren patchKeyedChildren(c1, c2, container, anchor, parentComponent, parentSuspense, isSVG, optimized); } else { //新节点没有子节点，直接删除旧节点的子节点 unmountChildren(c1, parentComponent, parentSuspense, true); } } else { // 旧节点的子节点是文本或者没有，清空文本 if (prevShapeFlag & 8 /* TEXT_CHILDREN */) { hostSetElementText(container, ''); } //新节点有多个子节点，直接新增 if (shapeFlag & 16 /* ARRAY_CHILDREN */) { mountChildren(c2, container, anchor, parentComponent, parentSuspense, isSVG, optimized); } } } }; |
当子节点没有key的时候比较子节点用patchUnkeyedChildren函数；这个函数比较简单，就是遍历新旧子节点最小公共长度部分，然后进行patch，最后把多余子节点卸载，新增的挂载：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
const patchUnkeyedChildren = (c1, c2, container, anchor, parentComponent, parentSuspense, isSVG, optimized) => { 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++) { const nextChild = (c2[i] = optimized ? cloneIfMounted(c2[i]) : normalizeVNode(c2[i]));//如果新节点已经挂载过了(已经过了各种优化处理)，则直接clone一份，否则创建一个新的vnode节点 patch(c1[i], nextChild, container, null, parentComponent, parentSuspense, isSVG, optimized); } //如果旧节点的数量大于新节点数量，直接写在多余节点，否则旧挂载新建节点 if (oldLength > newLength) { unmountChildren(c1, parentComponent, parentSuspense, true, false, commonLength); } else { mountChildren(c2, container, anchor, parentComponent, parentSuspense, isSVG, optimized, commonLength); } }; |
当子节点有key的时候，比较子节点用patchKeyedChildren函数；这个函数算是VUE3.0diff算法的核心了；它首先会进行一个预处理：把相同的前置和后置节点找出来不参与对比，处理只有删除或者添加节点的情况。然后处理剩余的真正需要diff的节点：创建一个map对象存放新节点的key-index映射关系，遍历旧子节点删除多余节点，依次找到新子节点对应旧节点所在的位置，然后存放在一个数组内，最后根据最长递增子序列移动需要移动的数据，并挂载需要新增的节点
VUE3.0的预处理主要做的工作是找出前置和后置相同节点，使他们不参与diff对比，然后在处理只有添加节点和删除节点的情况，这样我们可以极大提高算法速度(当我们只是添加和删除节点的话根本就不用执行向下更复杂的算法步骤)：
前置和后置相同节点预处理：从头部或尾部开始遍历，遇到相同节点执行patch，下标 + 1或 - 1，继续循环，遇到不同节点就跳出循环 ，结束遍历
只有新增或删除节点预处理： 如果旧节点遍历完毕，新节点还有剩余，就新增剩余节点 ； 如果新节点遍历完毕，旧节点还有剩余，就删除剩余节点
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
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) { const n1 = c1[i]; const n2 = (c2[i] = optimized ? cloneIfMounted(c2[i]) : normalizeVNode(c2[i])); if (isSameVNodeType(n1, n2)) {//节点相同执行patch方法 patch(n1, n2, container, null, parentComponent, parentSuspense, isSVG, optimized); } else { break; } i++; } // 2. 进行尾部遍历，遇到相同节点则继续，不同节点则跳出循环 while (i <= e1 && i <= e2) { const n1 = c1[e1]; const n2 = (c2[e2] = optimized ? cloneIfMounted(c2[e2]) : normalizeVNode(c2[e2])); if (isSameVNodeType(n1, n2)) { patch(n1, n2, container, null, parentComponent, parentSuspense, isSVG, optimized); } else { break; } e1--; e2--; } // 3. 如果旧节点已遍历完毕，并且新节点还有剩余，则遍历剩下的进行新增 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); i++; } } } // 4.新节点遍历完毕，旧节点还有剩余，就直接卸载剩余节点 else if (i > e2) { while (i <= e1) { unmount(c1[i], parentComponent, parentSuspense, true); i++; } } |
VUE3.0预处理完了之后就开始真正的diff中间剩余节点了；
创建新节点位置映射表：首先用一个生成一个map对象keyToNewIndexMap，创建一个新子节点的key-index映射表
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
const s1 = i; // prev starting index const s2 = i; // next starting index // 5.1 创建一个map，为剩余的新节点存储键值对，映射关系：key => index const keyToNewIndexMap = new Map(); for (i = s2; i <= e2; i++) { const nextChild = (c2[i] = optimized ? cloneIfMounted(c2[i]) : normalizeVNode(c2[i])); if (nextChild.key != null) { if (keyToNewIndexMap.has(nextChild.key)) { warn(`Duplicate keys found during update:`, JSON.stringify(nextChild.key), `Make sure keys are unique.`); } keyToNewIndexMap.set(nextChild.key, i); } } |
记录新节点在旧节点中的位置：遍历旧子节点，新旧节点对比，找出新子节点在旧子节点中所在的位置，存进一个newIndexToOldIndexMap数组的对应位置里(初始化为[0,0,0...]，对应位置存放对应新节点对应旧节点的位置下标 + 1)，当旧节点在新节点里无法找到，就删除多余的旧节点
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
let j; let patched = 0; const toBePatched = e2 - s2 + 1;//剩余要遍历的节点长度 let moved = false; let maxNewIndexSoFar = 0; //注意：oldIndex = 0代表的是多余的子节点，所以这里的oldIndex需要一个+1的偏移量 const newIndexToOldIndexMap = new Array(toBePatched);//新子节点在旧子节点对应的位置关系;主要用于最长递增子序列 //1.初始化newIndexToOldIndexMap for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 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; } //2.找到新节点对应旧节点的下标 let newIndex; if (prevChild.key != null) {//旧节点存在key，则通过key找到对应的新节点的下标 newIndex = keyToNewIndexMap.get(prevChild.key); } else {//旧节点没有key，就遍历所有的新节点，找到对应新节点下标 for (j = s2; j <= e2; j++) { if (newIndexToOldIndexMap[j - s2] === 0 && isSameVNodeType(prevChild, c2[j])) { newIndex = j; break; } } } if (newIndex === undefined) {//当前旧节点在新节点里没有找到：卸载当前旧节点 unmount(prevChild, parentComponent, parentSuspense, true); } else {//当前旧节点在新节点中找到了，则将旧节点的位置+1，存储在对应的新节点对应位置的newIndexToOldIndexMap里 newIndexToOldIndexMap[newIndex - s2] = i + 1; if (newIndex >= maxNewIndexSoFar) {// maxNewIndexSoFar如果不是逐级递增，则代表有新节点的位置前移了，那么需要进行移动 maxNewIndexSoFar = newIndex; } else { moved = true; } patch(prevChild, c2[newIndex], container, null, parentComponent, parentSuspense, isSVG, optimized); patched++; } } |
记录完节点位置之后就开始移动需要移动的节点了；VUE2.0算法是找到对应节点之后一个个节点进行移动，但是如下图我们知道只需要将移动C到E后边就可以了，再移动D和E就浪费性能了
于是VUE3.0引入了一个叫"最长递增子序列"的概念；那么什么是"最长递增子序列"呢？官方给出的定义是：在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中可以是不连续的；注意最长递增子序列可能不是唯一的
如此一来我们既可以使用这个"最长递增子序列"作为参照序列，即不需要移动的元素序列，移动那些没有在序列中的元素，就可以达到移动最少的节点进行更新节点的要求；如我们上述移动节点的例子中newIndexToOldIndexMap：[4,5,3,0]，这个数组的最长递增子序列是：[4,5] ；也就是说需要操作的节点是[3,0]因为0代表新增，所以我们只需要移动旧节点下标是2(3-1=2)的节点，到对应节点的后边就好(因为是向后移)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// 5.3 拿到最长递增子序列进行move or 新增挂载 const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : EMPTY_ARR;//在需要移动的时候生成最长递增子序列 j = increasingNewIndexSequence.length - 1; // looping backwards so that we can use last patched node as anchor for (i = toBePatched - 1; i >= 0; i--) { const nextIndex = s2 + i; const nextChild = c2[nextIndex]; const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor; if (newIndexToOldIndexMap[i] === 0) {//newIndexToOldIndexMap数组中有0，则新增节点 patch(null, nextChild, container, anchor, parentComponent, parentSuspense, isSVG); } else if (moved) { if (j < 0 || i !== increasingNewIndexSequence[j]) {//当不存在最长递增子序列或者节点不在最长递增子序列中时，移动节点 move(nextChild, container, anchor, 2 /* REORDER */); } else { j--; } } } |
至此VUE3.0的算法算是梳理完毕了；其实也不复杂，最重要的就是前置和后置节点的预处理，然后根据"最长递增子序列"最小程度的移动节点
