前言

关于 vue 的 diff 算法，大家可能在文章中或多或少都有了解过，我也一样。但是，纸上得来终觉浅，绝知此事要躬行。本文就比对着源码来对 diff 算法进行一个分析。

源码分析

零

首先，对下面可能多次出现的重复代码进行一个提前说明，

// 比较n1, n2新旧节点
patch(n1, n2, container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);
复制代码

// 比较n1, n2是否是相同类型的节点
function isSameVNodeType(n1, n2) {
    return n1.type === n2.type && n1.key === n2.key;
}
复制代码

// 如果新节点经历了挂载的阶段，就克隆一份,否则就创建一个新节点的vnode
const n2 = (c2[e2] = optimized
    ? cloneIfMounted(c2[e2])
    : normalizeVNode(c2[e2]));
复制代码

一 初始化

let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1; // prev ending index
let e2 = l2 - 1; // next ending index
复制代码

首先进行一个初始化，c1 是 vnode 更新前的 children 数组， c2 是 vnode 更新之后的children数组。

二 头部比较

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(n1, n2, container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);
    }
    else {
        break;
    }
    i++;
}
复制代码

从 2 个 children list 的头部开始进行循环比较，如果是相同类型的节点，就进行patch，继续循环，如果不同，则循环终止。

举个例子，比如 oldchildren 是 ['a', 'b', 'c'], newchildren 是 ['a', 'b', 'd']，ab匹配完后，循环就终止了。

三 尾部比较

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, slotScopeIds, optimized);
    }
    else {
        break;
    }
    e1--;
    e2--;
}
复制代码

跟第二步其实是一个意思，从头比较以后，从尾部开始进行循环比较。

四 循环比较完后续处理1

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++;
        }
    }
}
复制代码

i > e1 && i <= e2, 即头尾的指针重叠了，说明 c2 中剩下的没有被指针扫过的元素，即下表介于 [i, e2] 之间的的 child，都是新增的，循环创建挂载就好了。anchor 指的是，元素要挂载到的目标位置，即下一个元素。

举个例子，oldchilren 为 [a, b] , newchildren 为 [a, b, c, d] , 第二步结束以后, i = 2 , 第三步结束以后, 因为 b和d 不是相同类型的 node，所以 e1 = 1, e2 = 3。 index在 [i, e2] 之间为 2, 3 对应的 c, d 就是新增的元素节点。

五 循环比较完后续处理2

else if (i > e2) {
    while (i <= e1) {
        unmount(c1[i], parentComponent, parentSuspense, true);
        i++;
    }
}
复制代码

和第四步一个道理，如果 c2 指针重合了，c1 还没有重合，c1 中剩下的元素都是要被卸载的元素。比如 [a, b, c, d] 和 [a, b]。

六 剩下的中间部分元素的比较

    else {…………}
复制代码

这部分代码就比较长了，也跟上面一样，源码分步进行分析，这一情况的出现是，头部和尾部的双指针都没有完全扫过 c1 和 c2。比如 oldchildren = [a, b, (c, d, e, f,) g, h], newchildren = [a, b, (d, e, f, c,) g, h]，括号中的部分就是剩下需要比较的元素。

一

const s1 = i; // prev starting index
const s2 = i; // next starting index
// 5.1 build key:index map for newChildren
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) {
        keyToNewIndexMap.set(nextChild.key, i);
    }
}
复制代码

生成一个 Map 把新的元素的 key(如果存在) 和它对应的下标保存起来。

二

这段代码比较长，分析就写在注释中了

let j;
let patched = 0; // 已经patch完的数量
const toBePatched = e2 - s2 + 1; // 需要patch的数量,即c2剩下的元素数量
let moved = false; // 是否需要进行移动操作
let maxNewIndexSoFar = 0; // 用来辅助判定moved

// 生成c2中剩下的元素,在c1中的原来的位置的对应数组，初始化都为0
// 数组长度为 toBePatched，即剩下的 c2 中的元素数量
// 比如 oldchildren = [a, b, (c, d, e, f,) g, h], 
// newchildren = [a, b, (d, e, f, c,) g, h]
// d 在 new 中 index 为 2，在 old 中为 3
const newIndexToOldIndexMap = new Array(toBePatched);
for (i = 0; i < toBePatched; i++)
    newIndexToOldIndexMap[i] = 0;

// 循环 c1 中剩余的元素
for (i = s1; i <= e1; i++) {
    const prevChild = c1[i];
    // 如果 patched 数量已经超过了 toBePatched，说明 c2 中的元素已经patch完成了
    // 剩下的都卸载就可以了
    if (patched >= toBePatched) {
        unmount(prevChild, parentComponent, parentSuspense, true);
        continue;
    }
    // 声明一个 index 通过元素的 key 寻找 c1 中的元素在 c2 中的下标
    // 因为之前创建了 c2 中 key 和 index 对应的 Map
    let newIndex;
    
    // 寻找 key 是否存在
    if (prevChild.key != null) {
        newIndex = keyToNewIndexMap.get(prevChild.key);
    }
    else {
        // 如果没有 key 就在 c2 剩下的元素中 寻找同样没有 key 且，还没有配对的元素
        for (j = s2; j <= e2; j++) {
            // 判断是否是相同类型 且没有 key 且没有配对过
            if (newIndexToOldIndexMap[j - s2] === 0 &&
                isSameVNodeType(prevChild, c2[j])) {
                newIndex = j;
                break;
            }
        }
    }
    // 如果 newindex 不存在，说明 child 在 c2 中不存在，卸载就行了
    if (newIndex === undefined) {
        unmount(prevChild, parentComponent, parentSuspense, true);
    }
    else {
        // 如果存在，找到对应的位置
        // 这里 i + 1的原因是，防止 i = 0 的情况出现时，和初始化中的0无法区分
        // 为什么能 i + 1 而不影响结果
        // 因为后续求的是 c2 的元素，在 c1 中的下标的最长上升子序列
        // 只判断下标的大小关系
        // 因此 [1,2,3] 和 [2,3,4]的结果是一样的，不影响
        newIndexToOldIndexMap[newIndex - s2] = i + 1;
        
        // 来判断是不是元素是否移动了
        // 比如 [a,c,d] 和 [b,a,f,c,d]
        // newIndex都是一次增加的，因此中间只需要进行 创建和卸载 操作
        // 像b 和 f 就是直接新增，没有进行过move
        // 在比如 [a,c,d] 和 [b,a,d,c];
        // d 对应的 newIndex 就小于 c 对应的index，就说明c被移到了d后面
        // 我们在后续中就要进行 move 操作了
        if (newIndex >= maxNewIndexSoFar) {
            maxNewIndexSoFar = newIndex;
        }
        else {
            moved = true;
        }
        // 比较新老元素
        patch(prevChild, c2[newIndex], container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);
        
        // patched 数量 + 1
        patched++;
    }
}
复制代码

三 最后一步

代码还是有些长，分析还是一起写注释里

// 获取最长上升子序列，目的是为了移动的次数最小
// 比如中间剩下的元素为 [a,b,c] 和 [b,c,a],
// 对应的下标数组 newIndexToOldIndexMap [1,2,0] (这里没有算 i + 1);
// 那 [1,2] 就是最长上升子序列，对应bc，那操作时bc保持不动，移动a就行了
// 算法在后续进行讲解
// 如果 moved = false 说明不用移动。
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];
    // 找到元素要移动的位置节点
    const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor;
    // 新元素没有在 c1 中匹配到index 新建就行了
    if (newIndexToOldIndexMap[i] === 0) {
        // mount new
        patch(null, nextChild, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);
    }
    else if (moved) {
        // move if:
        // There is no stable subsequence (e.g. a reverse)
        // OR current node is not among the stable sequence
        
        // 最大子序列下标中 对应的元素不需要移动，其他的元素要进行move
        // 如果 i 对应的不是最长子序列中的下标 进行move移动元素
        if (j < 0 || i !== increasingNewIndexSequence[j]) {
            move(nextChild, container, anchor, 2 /* REORDER */);
        }
        else {
            j--;
        }
    }
}
复制代码

getSequence(最长上升子序列)算法分析

在看算法代码前，可以先来看个图，大致了解一下，操作流程的解析。

by Shuyu.Ji en.wikipedia.org/wiki/Longes…

function getSequence(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];
    if (arrI !== 0) {
      // 获取到result中的最后一个值j，比较arr[j]和arr[i]
      // 因为是求最长递增子列，所以最后一项 arr[j] 永远是 result 中最大的，
      // 只要 arr[i] 比 arr[j] 大，就把 i 插入result
      // p[i] 作用的话，后面一起分析
      j = result[result.length - 1];
      if (arr[j] < arrI) {
        p[i] = j;
        result.push(i);
        continue;
      }

      // 因为 result 是一个递增的数组，
      // 可以通过二分法找到 arrI 对应的 i 应该处在 result 中的位置
      u = 0;
      v = result.length - 1;
      while (u < v) {
        c = ((u + v) / 2) | 0;
        if (arr[result[c]] < arrI) {
          u = c + 1;
        }
        else {
          v = c;
        }
      }

      // 与现处于这个位置的数 arr[result[u]] 进行比较，只有可能是小于或者等于
      // 小于的话，就把 result[u] 的值 替换成 i
      // 这里又出现了p[i]，来分析下p[i]的作用，p[i] 的作用实际就是记录对应的前一个数字的 index
      // 举个例子, 比如 参数数组是 [2, 4, 5, 3]。
      // 当 5 运行完以后， result 中的 index 数组应该是 [0, 1, 2], 对应的值为 [2, 4, 5];
      // 这时候 新来的 arrI 是 3，在二分查找以后，3 应该现在 4 的这个位置；
      // 之前 4 插入的时候，因为大于 2 ,对应第一段代码， 
      // 4 对应的 p[i] 就是当时 result 的最后一项0,也就是 2 对应的 index;
      // 现在 3 替代了 4 的 index 在，result 中的位置，所以 3 对应的p[i] 也是 2 的 index 0;
      // p的作用简单来说 就是把一个递增子列的 index 串联起来，p[i] 对应的就是 前一个数字的 index 值
      // 运行结束后 p 的值应该为, [2, 0, 1, 0];
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1];
        }
        result[u] = i;
      }
    }
  }

  // 修正 result，先取到 result 中的最后一个 index，
  // 然后依次从 p 中获取他之前的那个 index, 直到 u 等于 0 为止；
  // 这么做的原因是为什么呢,还是举上面那个例子,
  // 当最后一个值 3 进入循环以后，取代了 4 的位置，
  // result 就变成了 [0, 3, 2]， 对应 [2, 3, 5]
  // 但是 3 明显是在 5 后面的，不能算一个子序列，因此要修正它，
  // 刚好在上一段代码中，5 结束时，对应的 p[i] 记录了 4 对应的 index，
  // 因此，只要通过 p 数组，就能获得真实的子列对应的 index。
  
  u = result.length;
  v = result[u - 1];
  while (u-- > 0) {
    result[u] = v;
    v = p[v];
  }
  return result;
}
复制代码

结语

其实就像文章开始说的，大家对 diff 的概念或多或少都有了解，比如怎么运行，怎么实现。但是其中的细节，可能了解的不是很清楚，希望这篇文章能对你有所帮助。如果有写错的地方也希望大家能够指正，探讨。