🖼

Vue3 - Diff

Jul 2

简单梳理

Diff

新旧虚拟节点子节点都为一组节点时，需要对比两组子节点并完成高效的更新，这一过程就为 Diff

⚽️目标：移动最少节点完成更新

实现

  • 处理新旧两组子节点中相同的前置和后置节点
  • 对留下的中间部分依据索引关系进行增删更新换位置

前置准备

判断两个虚拟节点是否同一个

function isSameVNodeValue(n1: VNODE, n2: VNODE) {
  return n1.type === n2.type && n1.key === n2.key;
}

function patchChildren(c1: VNODE[], c2: VNODE[], container) { 
  // 后续步骤填充在此
  // ... 
}

找到头尾相同的节点

  • 两个数组头尾各有一个指针，都向中间压缩
  • XABCDY vs XCADEFY => ABCD vs CADEF（过滤 X Y）
  • X Y 自身还是会更新，但不参与后续流程
const l1 = c1.length
const l2 = c2.length

let i = 0
let e1 = l1 - 1 // end 指针
let e2 = l2 - 1 // end 指针

// 左侧
while (i <= e1 && i <= e2) {
  const n1 = c1[i]
  const n2 = c2[i]
  
  if (isSameVNodeValue(n1, n2)) {
    patch(n1, n2, container)
  } else {
    break
  }
  
  i ++
}

// 右侧
while (i <= e1 && i <= e2) {
  const n1 = c1[i]
  const n2 = c2[i]
  
  if (isSameVNodeValue(n1, n2)) {
    patch(n1, n2, container)
  } else {
    break
  }
  
  e1 --
  e2 --
}

根据 i e1 e2 大小关系做进一步处理

  • i > e1 (AB vs ABCD) 纯增
  • i > e2 (ABCD vs AB) 纯减
  • 否则：非纯增删 (ABCD vs CADEF)
if (i > e1) {
  // 新增 新节点在原节点基础上有新增
  while (i <= e2) {
    const nextPos = e2 + 1;
    const anchor = nextPos < l2 ? c2[nextPos].el : null;
    patch(null, c2[i], container);
    i++;
  }
} else if (i > e2) {
  // 删除 新节点在原节点基础上有删除
  while (i <= e1) {
    remove(c1[i].el);
    i++;
  }
} else {
  // ...
}

处理非纯增删情况

  • 删除多余的节点（即 c2 无，c1 有）
  • 更新两者都有的节点（c2，c1 重合部分）
  • 调整重合节点的顺序 同时 创建新增的点
分析 ABCD vs CADEF

目标：

  • AD 不动
  • 删 B
  • 移 C
  • 增 EF

步骤：

  • 获取 c2 相对于 c1 映射的数组下标

    • 初始化存储下标的数组 indexMap = [-1, -1, -1, -1, -1]
    • ABCD -> [0, 1, 2, 3]
    • CADEF -> [2, 0, 3, -1, -1]

  • 找出最长递增子序列下标： [2, 0, 3, -1, -1] -> 值 [0, 3] -> 下标 [1, 2]

  • 从右向左循环待处理的子节点

    • 遇到 -1 新建插入
    • 遇到子序列下标 不动
    • 其它直接插入
const s1 = i
const s2 = i
const toBePatched = e2 - s2

// 存储映射后的 c2 数组下标
const newIndexToOldIndexMap = Array(toBePatched).fill(-1)

// 获取 c2 的 元素对应下标，优化后续查找流程
const keyToIndexMap = new Map()

for (let i = s2; i <= e2; i ++) {
  keyToIndexMap.set(c2[i].key, i);
}

let newIndex
// 根据 c1 顺序来填充 newIndexToOldIndexMap
for (let i = s1; i <= e1; i ++) {
  const c1Child = c1[i]
  
  // 设置 newIndex，判断 c2 中是否有当前 c1 的元素
  if (c1Child.key) {
    // map 查询
    newIndex = keyToIndexMap.get(c1Child)
  } else {
    // 循环查询
    for (let j = s2; j <= e2; j ++) {
      if (isSameVNodeValue(c1Child, c2[j])) {
        newIndex = j;
        break;
      }
    }
  }

 if (newIndex  === undefined) {
    remove(c1Child)
  } else {
    newIndexToOldIndexMap[newIndex - s2] = i
    patch(c1Child, c2[newIndex], container)
  }
  // ↑ 至此，相同元素的更新，不同元素的删除已经处理完  接下来需要调换元素的位置，插入新增元素
  
  // 获取最长递增子序列的下标，说明这些元素的相对位置是不变的，也就是不需要动
  const increasingNewIndexSequence = getSequence(newIndexToOldIndexMap) // => [1, 2]
  // 循环待调整的 c2 进行插入新建操作
  let j = increasingNewIndexSequence.length - 1;
  for (let i = toBePatched - 1; i >= 0; i -= 1) {
      const nextIndex = i + s2;
      const nextChild = c2[nextIndex]!;
      const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : null;

      // 若该点没有则新建，然后插入
    if (newIndexToOldIndexMap[i] === -1) {
        patch(null, nextChild, container);
    } else {
      if (j < 0 || i !== increasingNewIndexSequence[j]) {
        insert(nextChild.el!, container, anchor);
      } else {
        j--;
      }
    }
  }
}