Vue2、Vue3的diff对比

let oldStartIdx = 0 // 老vnode遍历的开始下标let newStartIdx = 0 // 新vnode遍历的开始下标let oldEndIdx = oldCh.length - 1 // 老vnode 列表长度let oldStartVnode = oldCh[0] // 老vnode列表第一个子元素let oldEndVnode = oldCh[oldEndIdx] // 老vnode列表最后一个子元素let newEndIdx = newCh.length - 1 // 新vnode列表长度let newStartVnode = newCh[0] // 新vnode列表第一个子元素let newEndVnode = newCh[newEndIdx] // 新vnode列表最后一个子元素

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

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

else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved rightpatchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))oldStartVnode = oldCh[++oldStartIdx]newEndVnode = newCh[--newEndIdx]}

else if (sameVnode(oldEndVnode, newStartVnode)) {  // Vnode moved leftpatchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);oldEndVnode = oldCh[--oldEndIdx];newStartVnode = newCh[++newStartIdx];}

else { // 创建一个 { key: oldVnode } 的映射表 if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // 查找这个表，如果 newStartVnode 中有 key，则直接去映射表中查；否则通过 findIdxInOld 查 idxInOld = isDef(newStartVnode.key)   ? oldKeyToIdx[newStartVnode.key]   : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) if (isUndef(idxInOld)) {   // 如果没找到，那么新建节点   createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)} else {   vnodeToMove = oldCh[idxInOld]   // 相同节点的话   if (sameVnode(vnodeToMove, newStartVnode)) {     // 进行patch     patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)     // 因为该位置对应的节点处理完毕，因此，将该位置设置为 undefined，后续指针遍历进来后可以直接跳过遍历下一个     oldCh[idxInOld] = undefined     // 后移动对应的真实DOM     canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)   } else {     // 不是相同节点的话，那么需要新建节点     createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)   }} newStartVnode = newCh[++newStartIdx]}

// oldStartIdx > oldEndIdx 说明老的 vnode 先遍历完  if (oldStartIdx > oldEndIdx) {// 就添加从 newStartIdx 到 newEndIdx 之间的节点refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elmaddVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)// 否则就说明新的 vnode 先遍历完} else if (newStartIdx > newEndIdx) {// 就删除掉老的 vnode 里没有遍历的节点removeVnodes(oldCh, oldStartIdx, oldEndIdx)}}

let i = 0; // 新老vnode遍历的开始下标const l2 = c2.length; // 新vnode的遍历长度let e1 = c1.length - 1; // 老vnode的末尾下标let e2 = l2 - 1; // 新vnode的末尾下标

// 1. sync from start// (a b) c// (a b) d ewhile (i <= e1 && i <= e2) {const prevChild = c1[i];const nextChild = c2[i];// 如果不是相同节点，遍历终止if (!isSameVNodeType(prevChild, nextChild)) {break;}// 是相同节点，继续往后遍历，新老节点末尾索引加一patch(prevChild, nextChild, container, parentAnchor, parentComponent);i++;}

// 2. sync from end// a (b c)// d e (b c)while (i <= e1 && i <= e2) {// 从右向左取值const prevChild = c1[e1];const nextChild = c2[e2];// 如果不是相同节点，遍历终止if (!isSameVNodeType(prevChild, nextChild)) {break;}// 是相同节点，继续往后遍历，新老节点末尾索引减一patch(prevChild, nextChild, container, parentAnchor, parentComponent);e1--;e2--;}

// 老节点先遍历完，新节点还剩余// (a b)// (a b) c// i = 2, e1 = 1, e2 = 2// (a b)// c (a b)// i = 0, e1 = -1, e2 = 0if (i > e1 && i <= e2) {// 如果是这种情况的话就说明 e2 也就是新节点的数量大于旧节点的数量// 也就是说新增了 vnode// 应该循环 c2// 锚点的计算：新的节点有可能需要添加到尾部，也可能添加到头部，所以需要指定添加的问题// 要添加的位置是当前的位置(e2 开始)+1// 因为对于往左侧添加的话，应该获取到 c2 的第一个元素// 所以我们需要从 e2 + 1 取到锚点的位置const nextPos = e2 + 1;const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor;while (i <= e2) {patch(null, c2[i], container, anchor, parentComponent);i++;}}

// 新节点先遍历完，老节点还剩余// (a b) c// (a b)// i = 2, e1 = 2, e2 = 1// a (b c)// (b c)// i = 0, e1 = 0, e2 = -1else if (i > e2 && i <= e1) {// 这种情况的话说明新节点的数量是小于旧节点的数量的// 那么我们就需要把多余的while (i <= e1) {hostRemove(c1[i].el);i++;}}

// 左右两边都比对完了，然后剩下的就是中间部位顺序变动的// 例如下面的情况// a,b,[c,d,e,f],g// a,b,[f,c,d,e,h],glet s1 = i; // 2let s2 = i; // 2const keyToNewIndexMap = new Map(); // 新节点剩余节点映射哈希表let moved = false; // 移动标识let maxNewIndexSoFar = 0; // 判断是否需要移动// 先把 key 和 newIndex 绑定好，方便后续基于 key 找到 newIndex// 时间复杂度是 O(1)for (let i = s2; i <= e2; i++) { // i= 2-6const nextChild = c2[i];keyToNewIndexMap.set(nextChild.key, i);}// keyToNewIndexMap = { f: 2, c: 3, d: 4, e: 5, h: 6 }

// 需要处理新节点的数量const toBePatched = e2 - s2 + 1; // 6 - 2 + 1 = 5let patched = 0; // 记录新老节点都有的数量// 初始化 从新的index映射为老的index// 创建数组的时候给定数组的长度，这个是性能最快的写法const newIndexToOldIndexMap = new Array(toBePatched);// 初始化为 0 , 后面处理的时候 如果发现是 0 的话，那么就说明新值在老的里面不存在for (let i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0;// [0, 0, 0, 0, 0]

// 遍历老节点// 1. 需要找出老节点有，而新节点没有的 -> 需要把这个节点删除掉// 2. 新老节点都有的，—> 需要 patch// 老节点 => [c,d,e,f]// 新节点剩余索引 keyToNewIndexMap = { f: 2, c: 3, d: 4, e: 5, h: 6 }for (i = s1; i <= e1; i++) {const prevChild = c1[i];// 如果新老节点都有的数量大于新节点的数量的话，那么这里在处理老节点的时候就直接删除即可if (patched >= toBePatched) {hostRemove(prevChild.el);continue;}let newIndex; // 老节点在新节点的索引if (prevChild.key != null) {// 这里就可以通过key快速的查找了， 看看在新的里面这个节点存在不存在// 时间复杂度O(1)newIndex = keyToNewIndexMap.get(prevChild.key);} else {// 如果没key 的话，那么只能是遍历所有的新节点来确定当前节点存在不存在了// 时间复杂度O(n)for (let j = s2; j <= e2; j++) {if (isSameVNodeType(prevChild, c2[j])) {newIndex = j;break;}}}// 因为有可能 nextIndex 的值为0（0也是正常值）// 所以需要通过值是不是 undefined 或者 null 来判断if (newIndex === undefined) {// 当前节点的key 不存在于 newChildren 中，需要把当前节点给删除掉hostRemove(prevChild.el);} else {// 老节点 => [c,d,e,f]// 新节点剩余索引 keyToNewIndexMap = { f: 2, c: 3, d: 4, e: 5, h: 6 }// 老节点在新节点中的索引newIndex: [3,4,5,2]// i + 1 是因为 i 有可能是0 (0 的话会被认为新节点在老的节点中不存在)newIndexToOldIndexMap[newIndex - s2] = i + 1;// newIndexToOldIndexMap = [6, 3, 4, 5, 0]// 来确定中间的节点是不是需要移动// 新的 newIndex 如果一直是升序的话，那么就说明没有移动// 所以我们可以记录最后一个节点在新的里面的索引，然后看看是不是升序// 不是升序的话，我们就可以确定节点移动过了if (newIndex >= maxNewIndexSoFar) {maxNewIndexSoFar = newIndex;} else {moved = true;}patch(prevChild, c2[newIndex], container, null, parentComponent); // 继续递归diffpatched++; // 记录新老节点都有的数量}}

// 利用最长递增子序列来优化移动逻辑// 因为元素是升序的话，那么这些元素就是不需要移动的// 而我们就可以通过最长递增子序列来获取到升序的列表// 在移动的时候我们去对比这个列表，如果对比上的话，就说明当前元素不需要移动// 通过 moved 来进行优化，如果没有移动过的话 那么就不需要执行算法// getSequence 返回的是 newIndexToOldIndexMap 的索引值// 所以后面我们可以直接遍历索引值来处理，也就是直接使用 toBePatched 即可const increasingNewIndexSequence = moved? getSequence(newIndexToOldIndexMap): [];// increasingNewIndexSequence = [1,2,3]/*最长增长子序列方法贪心加二分获取最长序列根据前驱序列得到正确索引序列*/function getSequence(arr) {const preIndex = new Array(arr.length), indexResult = [0];let resultLastIndex, left, right, mid;const len = arr.length;for (let i = 0; i < len; i++) {const arrI = arr[i];if (arrI !== 0) {resultLastIndex = indexResult[indexResult.length - 1];// 当前项大于最后一项，直接加入结果resif (arr[resultLastIndex] < arrI) {preIndex[i] = resultLastIndex;indexResult.push(i);continue;}// 当前项小于最后一项，二分查找+替换，找到并替换比当前项大的那项left = 0, right = indexResult.length - 1;while (left < right) { // 重合就说明找到了 对应的值,时间复杂度O(logn)mid = (left + right) >> 1;// mid的值比当前项小，所以不包括mid的值if (arr[indexResult[mid]] < arrI) {left = mid + 1;} else {right = mid;}}// 只替换比当前项大的那一项，如果相同、比当前项的还小就不换了if (arrI < arr[indexResult[left]]) {if (left > 0) {preIndex[i] = indexResult[left - 1];}indexResult[left] = i;}}}// 利用前驱节点重新计算resultlet length = indexResult.length; //总长度let prev = indexResult[length - 1]; // 最后一项while (length-- > 0) { // 根据前驱节点一个个向前查找indexResult[length] = prev;prev = preIndex[prev];}return indexResult;}

let j = increasingNewIndexSequence.length - 1; // 2// 遍历新节点，用toBePatched，是之前记录的新节点个数// 1. 需要找出老节点没有，而新节点有的(如节点h) -> 需要把这个节点创建// 2. 最后需要移动一下位置，比如 [c,d,e,f] -> [f,c,d,e]// 这里倒循环是因为在 insert 的时候，需要保证锚点是处理完的节点（也就是已经确定位置了）// 因为 insert 逻辑是使用的 insertBefore()// [ 0:a, 1:b, 2:f, 3:c, 4:d, 5:e, 6:h, 7:g ], s2 = 2for (let i = toBePatched - 1; i >= 0; i--) { // 4, 3, 2, 1, 0与increasingNewIndexSequence下标相同// 确定当前要处理的节点索引，拿到正确的下标const nextIndex = s2 + i; // 6 -> 'h'const nextChild = c2[nextIndex]; // 'h'节点// 锚点等于当前节点索引+1// 也就是当前节点的后面一个节点(又因为是倒遍历，所以锚点是位置确定的节点)const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor;// newIndexToOldIndexMap = [6, 3, 4, 5, 0]if (newIndexToOldIndexMap[i] === 0) {// 说明新节点在老的里面不存在，需要创建patch(null, nextChild, container, anchor, parentComponent);} else if (moved) {// 需要移动// 1. j 已经没有了 说明剩下的都需要移动了// 2. 最长子序列里面的值和当前的值匹配不上， 说明当前元素需要移动if (j < 0 || increasingNewIndexSequence[j] !== i) {// 移动的话使用 insert 即可hostInsert(nextChild.el, container, anchor);} else {// 这里就是命中了  index 和 最长递增子序列的值// 所以可以移动指针了j--;}}}