Diff算法深度剖析 - Vue.js的DOM更新魔法

// 四个指针：旧列表的头尾、新列表的头尾。它们向中间收，碰头就结束。
// 真实源码里它是 createPatchFunction 闭包中的一个函数，不属于任何类。
function updateChildren(parentElm, oldCh, newCh) {
  let oldStartIdx = 0;
9 collapsed lines
  let newStartIdx = 0;
  let oldEndIdx = oldCh.length - 1;
  let newEndIdx = newCh.length - 1;
  let oldStartVnode = oldCh[0];
  let oldEndVnode = oldCh[oldEndIdx];
  let newStartVnode = newCh[0];
  let newEndVnode = newCh[newEndIdx];
  let oldKeyToIdx, idxInOld, vnodeToMove;

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 省略：跳过被置空的旧节点 —— 情况 5 会把用过的槽位标成 undefined
    if (sameVnode(oldStartVnode, newStartVnode)) {
      // ① 头头相同：原地更新，两个 start 指针右移
      patchVnode(oldStartVnode, newStartVnode);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      // ② 尾尾相同：原地更新，两个 end 指针左移
      patchVnode(oldEndVnode, newEndVnode);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      // ③ 头尾相同：这个节点跑到末尾去了，把它的 DOM 移过去
      patchVnode(oldStartVnode, newEndVnode);
      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      // ④ 尾头相同：这个节点跑到开头去了
      patchVnode(oldEndVnode, newStartVnode);
      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      // ⑤ 四种都不命中：建一次 key → 旧索引的映射表，直接查
      if (!oldKeyToIdx) {
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
      }
      idxInOld = oldKeyToIdx[newStartVnode.key];

      if (idxInOld === undefined) {
        createElm(newStartVnode, parentElm, oldStartVnode.elm);
      } else {
        vnodeToMove = oldCh[idxInOld];
        patchVnode(vnodeToMove, newStartVnode);
        oldCh[idxInOld] = undefined;          // 标记这个槽位已经用掉
        parentElm.insertBefore(vnodeToMove.elm, oldStartVnode.elm);
      }
      newStartVnode = newCh[++newStartIdx];
    }
  }

  // 一侧先走完：剩下的要么全是新增，要么全是删除
  if (oldStartIdx > oldEndIdx) {
    const refElm = newCh[newEndIdx + 1] ? newCh[newEndIdx + 1].elm : null;
    addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx);
  } else if (newStartIdx > newEndIdx) {
    removeVnodes(oldCh, oldStartIdx, oldEndIdx);
  }
}

18 collapsed lines
// key → 旧列表下标。只在情况 5 第一次发生时建一次，之后复用。
function createKeyToOldIdx(children, beginIdx, endIdx) {
const map = {};
for (let i = beginIdx; i <= endIdx; i++) {
  const key = children[i].key;
  if (key !== undefined) map[key] = i;
}
return map;
}

// 「同一个节点」的判据：key 相同，且标签、注释、data 有无、input type 都一致
function sameVnode(a, b) {
return a.key === b.key
  && a.tag === b.tag
  && a.isComment === b.isComment
  && isDef(a.data) === isDef(b.data)
  && sameInputType(a, b);
}

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) {
      j = result[result.length - 1];
      if (arr[j] < arrI) {
        // 当前值大于结果数组最后一个值，直接追加
        p[i] = j;
        result.push(i);
        continue;
      }

      // 二分查找，找到第一个大于arrI的位置
      u = 0;
      v = result.length - 1;
      while (u < v) {
        c = (u + v) >> 1; // 位运算，相当于Math.floor((u + v) / 2)
        if (arr[result[c]] < arrI) {
          u = c + 1;
        } else {
          v = c;
        }
      }

      // 如果找到的值大于arrI，则替换
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1];
        }
        result[u] = i;
      }
    }
  }
13 collapsed lines

  // 回溯，生成正确的LIS
  u = result.length;
  v = result[u - 1];
  while (u-- > 0) {
    result[u] = v;
    v = p[v];
  }

  return result;
}

// 演示LIS在Diff中的应用

function patchKeyedChildren(c1, c2, container) {
  let i = 0;
  let e1 = c1.length - 1;
  let e2 = c2.length - 1;

  // 1. 从头开始，相同的先 patch 掉
  while (i <= e1 && i <= e2 && isSameVNodeType(c1[i], c2[i])) {
    patch(c1[i], c2[i], container);
    i++;
  }

9 collapsed lines
  // 2. 从尾开始，同理
  while (i <= e1 && i <= e2 && isSameVNodeType(c1[e1], c2[e2])) {
    patch(c1[e1], c2[e2], container);
    e1--;
    e2--;
  }

  // 3. 中间剩下的乱序段：建 key 映射，求最长递增子序列，
  //    序列里的节点保持不动，其余的按新顺序插入。
  const increasingNewIndexSequence = getSequence(newIndexToOldIndexMap);
}