Vue3 Diff算法可视化

function diff(oldChildren, newChildren) {
  // 1. 双端对比（跳过相同的前置和后置节点）
  let oldStartIdx = 0, oldEndIdx = oldChildren.length - 1;
  let newStartIdx = 0, newEndIdx = newChildren.length - 1;
  
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 跳过已处理节点
    if (!oldChildren[oldStartIdx]) { oldStartIdx++; continue; }
    if (!oldChildren[oldEndIdx]) { oldEndIdx--; continue; }
    
    // 头头比较
    if (isSameNode(oldChildren[oldStartIdx], newChildren[newStartIdx])) {
      patchNode(oldChildren[oldStartIdx], newChildren[newStartIdx]);
      oldStartIdx++;
      newStartIdx++;
    } 
    // 尾尾比较
    else if (isSameNode(oldChildren[oldEndIdx], newChildren[newEndIdx])) {
      patchNode(oldChildren[oldEndIdx], newChildren[newEndIdx]);
      oldEndIdx--;
      newEndIdx--;
    } 
    // 头尾比较
    else if (isSameNode(oldChildren[oldStartIdx], newChildren[newEndIdx])) {
      patchNode(oldChildren[oldStartIdx], newChildren[newEndIdx]);
      moveNode(oldChildren[oldStartIdx], oldChildren[oldEndIdx].el.nextSibling);
      oldStartIdx++;
      newEndIdx--;
    } 
    // 尾头比较
    else if (isSameNode(oldChildren[oldEndIdx], newChildren[newStartIdx])) {
      patchNode(oldChildren[oldEndIdx], newChildren[newStartIdx]);
      moveNode(oldChildren[oldEndIdx], oldChildren[oldStartIdx].el);
      oldEndIdx--;
      newStartIdx++;
    } 
    else {
      break;
    }
  }
  
  // 2. 处理新增或删除的节点
  if (oldStartIdx > oldEndIdx && newStartIdx <= newEndIdx) {
    // 新增节点
    for (let i = newStartIdx; i <= newEndIdx; i++) {
      createEl(newChildren[i]);
    }
  } else if (newStartIdx > newEndIdx && oldStartIdx <= oldEndIdx) {
    // 删除节点
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      removeNode(oldChildren[i]);
    }
  }
  
  // 3. 处理未知子序列（通过key映射）
  const oldStart = oldStartIdx;
  const newStart = newStartIdx;
  const keyToNewIndexMap = new Map();
  
  // 构建新节点key的索引映射
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    keyToNewIndexMap.set(newChildren[i].key, i);
  }
  
  // 遍历旧节点，尝试复用
  const newIndexToOldIndexMap = new Array(newEndIdx - newStartIdx + 1).fill(-1);
  
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {
    const oldNode = oldChildren[i];
    const newIndex = keyToNewIndexMap.get(oldNode.key);
    
    if (newIndex === undefined) {
      // 没有对应的新节点，移除
      removeNode(oldNode);
    } else {
      newIndexToOldIndexMap[newIndex - newStart] = i;
      patchNode(oldNode, newChildren[newIndex]);
    }
  }
  
  // 4. 使用最长递增子序列(LIS)优化移动操作
  const lis = getSequence(newIndexToOldIndexMap);
  let j = lis.length - 1;
  
  for (let i = newIndexToOldIndexMap.length - 1; i >= 0; i--) {
    if (newIndexToOldIndexMap[i] === -1) {
      // 新增节点
      createEl(newChildren[newStart + i]);
    } else if (i !== lis[j]) {
      // 需要移动的节点
      moveNode(oldChildren[newIndexToOldIndexMap[i]], ...);
    } else {
      // 在LIS中，不需要移动
      j--;
    }
  }
}

// 计算最长递增子序列（贪心+二分）
function getSequence(arr) {
  // ... 实现略 ...
}