Diff算法的实现

1. Vue Diff算法的策略

Vue 2 的 Diff 算法基于 双端比较 策略，即通过四个指针（旧头、旧尾、新头、新尾）来比较新旧节点列表，尽可能复用 DOM 节点。

2. 实现步骤

2.1 定义节点结构

我们用一个简单的对象来表示虚拟 DOM 节点：

class VNode {
  constructor(tag, key, children) {
    this.tag = tag;       // 节点标签
    this.key = key;       // 节点唯一标识
    this.children = children || []; // 子节点列表
  }
}

2.2 定义 Diff 函数

Diff 函数接收新旧子节点列表，并返回需要更新的操作。

function diff(oldChildren, newChildren) {
  let oldStartIdx = 0;                  // 旧节点列表的起始索引
  let oldEndIdx = oldChildren.length - 1; // 旧节点列表的结束索引
  let newStartIdx = 0;                  // 新节点列表的起始索引
  let newEndIdx = newChildren.length - 1; // 新节点列表的结束索引

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    const oldStartNode = oldChildren[oldStartIdx];
    const oldEndNode = oldChildren[oldEndIdx];
    const newStartNode = newChildren[newStartIdx];
    const newEndNode = newChildren[newEndIdx];

    // 1. 旧头 vs 新头
    if (isSameNode(oldStartNode, newStartNode)) {
      patch(oldStartNode, newStartNode); // 更新节点
      oldStartIdx++;
      newStartIdx++;
    }
    // 2. 旧尾 vs 新尾
    else if (isSameNode(oldEndNode, newEndNode)) {
      patch(oldEndNode, newEndNode); // 更新节点
      oldEndIdx--;
      newEndIdx--;
    }
    // 3. 旧头 vs 新尾
    else if (isSameNode(oldStartNode, newEndNode)) {
      patch(oldStartNode, newEndNode); // 更新节点
      move(oldStartNode, oldEndNode);  // 移动节点到旧尾之后
      oldStartIdx++;
      newEndIdx--;
    }
    // 4. 旧尾 vs 新头
    else if (isSameNode(oldEndNode, newStartNode)) {
      patch(oldEndNode, newStartNode); // 更新节点
      move(oldEndNode, oldStartNode);  // 移动节点到旧头之前
      oldEndIdx--;
      newStartIdx++;
    }
    // 5. 查找新头节点在旧节点列表中的位置
    else {
      const idxInOld = findIdxInOld(newStartNode, oldChildren, oldStartIdx, oldEndIdx);
      if (idxInOld !== -1) {
        const nodeToMove = oldChildren[idxInOld];
        patch(nodeToMove, newStartNode); // 更新节点
        move(nodeToMove, oldStartNode);  // 移动节点到旧头之前
        oldChildren[idxInOld] = undefined; // 标记节点已处理
      } else {
        insert(newStartNode, oldStartNode); // 插入新节点
      }
      newStartIdx++;
    }
  }

  // 处理剩余节点
  if (oldStartIdx > oldEndIdx) {
    // 插入新节点
    for (let i = newStartIdx; i <= newEndIdx; i++) {
      insert(newChildren[i], oldChildren[oldStartIdx]);
    }
  } else if (newStartIdx > newEndIdx) {
    // 删除旧节点
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      remove(oldChildren[i]);
    }
  }
}

---

3. 辅助函数

3.1 判断节点是否相同

function isSameNode(oldNode, newNode) {
  return oldNode && newNode && oldNode.key === newNode.key && oldNode.tag === newNode.tag;
}

3.2 查找节点在旧列表中的位置

function findIdxInOld(node, oldChildren, start, end) {
  for (let i = start; i <= end; i++) {
    if (oldChildren[i] && isSameNode(oldChildren[i], node)) {
      return i;
    }
  }
  return -1;
}

3.3 更新节点

function patch(oldNode, newNode) {
  console.log(`更新节点: ${oldNode.key} -> ${newNode.key}`);
  // 这里可以执行具体的 DOM 更新操作
}

3.4 移动节点

function move(node, referenceNode) {
  console.log(`移动节点: ${node.key} 到 ${referenceNode.key} 附近`);
  // 这里可以执行具体的 DOM 移动操作
}

3.5 插入节点

function insert(node, referenceNode) {
  console.log(`插入节点: ${node.key} 到 ${referenceNode ? referenceNode.key : '开头'}`);
  // 这里可以执行具体的 DOM 插入操作
}

3.6 删除节点

function remove(node) {
  console.log(`删除节点: ${node.key}`);
  // 这里可以执行具体的 DOM 删除操作
}

---

4. 示例

4.1 定义新旧节点列表

const oldChildren = [
  new VNode('div', 'A'),
  new VNode('div', 'B'),
  new VNode('div', 'C'),
  new VNode('div', 'D')
];

const newChildren = [
  new VNode('div', 'D'),
  new VNode('div', 'A'),
  new VNode('div', 'B'),
  new VNode('div', 'C')
];

4.2 执行 Diff 算法

diff(oldChildren, newChildren);

4.3 输出结果

移动节点: D 到 A 附近
更新节点: A -> A
更新节点: B -> B
更新节点: C -> C

---

5. 总结

通过这个简单版的diff算法，我们模拟了双端比较策略，并实现了节点的更新、移动、插入和删除操作。虽然这是一个简化版本，但并不妨碍理解Vue 的diff 算法的核心思想。