双端Diff算法

双端Diff算法

双端Diff算法指的是，在新旧两组子节点的四个端点之间分别进行比较，并试图找到可复用的节点。相比简单Diff算法，双端Diff算法的优势在于，对于同样的更新场景，执行的DOM移动操作次数更少。

1. 简单 Diff 算法（单向 Diff）：

• 工作原理：简单 Diff 算法从一个序列的起始位置开始，逐个比较元素，找出不同之处。

• 特点：

  • 顺序性：仅从一个方向进行比较，一旦发现不同之处，就会停止继续比较。

  • 复杂度：时间复杂度为 O(n)，其中 n 是序列的长度。

  • 结果不唯一：因为只按照一个方向进行比较，可能会忽略一些潜在的更优的匹配方式。

2. 双端 Diff 算法（双向 Diff）：

• 工作原理：双端 Diff 算法同时从两个序列的起始位置开始，向中间移动，逐个比较元素，找出不同之处。
• 特点：
  - 双向性：同时从两个方向进行比较，可以更全面地考虑匹配情况。
  - 优化效率：通过跳过相同的前缀和后缀部分，减少了比较的次数，提高了效率。
  - 复杂度：时间复杂度为 O(n+m)，其中 n 和 m 分别是两个序列的长度。
  - 结果更准确：考虑了更多的匹配可能性，得到更准确的差异结果。

双端Diff算法的比较方式

双端Diff算法是一种同时对新旧两组子节点的两个端点进行比较的算法，因此我们需要四个索引值，分别指向新旧两组节点的端点。

function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    // 封装 patchKeyedChildren 函数处理两组子节点
    patchKeyedChildren(n1, n2, container);
  } else {
    // 省略部分代码
  }
}
function patchKeyedChildren(n1, n2, container) {
  const oldChildren = n1.children;
  const newChildren = n2.children;
  // 四个索引值
  let oldStartIdx = 0;
  let oldEndIdx = oldChildren.length - 1;
  let newStartIdx = 0;
  let newEndIdx = newChildren.length - 1;
  // 四个索引指向的 vnode 节点
  let oldStartVNode = oldChildren[oldStartIdx];
  let oldEndVNode = oldChildren[oldEndIdx];
  let newStartVNode = newChildren[newStartIdx];
  let newEndVNode = newChildren[newEndIdx];
}

上面的代码中，我们将两组子节点的打补丁工程封装到了 patchKeyedChildren 函数中。该函数中，先获取两组新旧子节点 oldChildren 和 newChildren，然后创建四个索引值，分别指向新旧两组子节点的收尾，即 oldStartIdx（简称为旧前）、oldEndIdx（简称为旧后）、newStartIdx（简称为新前）、newEndIdx（简称为新后），以及四个索引值对应的 vnode。其中 oldStartVNode 和 oldEndVNode 是旧的一组子节点的第一个节点和最后一个节点，newStartVNode 和 newEndVNode 则是新的一组子节点的第一个子节点和最后一个子节点。

双端比较，每一轮均分为四个步骤：

1. 比较旧的一组子节点的第一个子节点p-1（简称为旧前）于新的一组子节点的第一个子节点p-4（简称为新前），看看他们是否相同。由于两者的 key 值不同，因此不相同，不可复用，于是什么都不做。
2. 比较旧的一组子节点的最后一个子节点p-4（简称为旧后）于新的一组子节点的最后一个子节点p-3（简称为新后），看看他们是否相同。由于两者的 key 值不同，因此不相同，不可复用，于是什么都不做。
3. 比较旧的一组子节点的第一个子节点p-1（简称为旧前）于新的一组子节点的最后一个子节点p-3（简称为新后），看看他们是否相同。由于两者的 key 值不同，因此不相同，不可复用，于是什么都不做。
4. 比较旧的一组子节点的最后一个子节点p-4（简称为旧后）于新的一组子节点的第一个子节点p-4（简称为新前）。由于他们的 key 相同，因此可以进行DOM复用。

四个步骤命中任何一步均说明命中的节点可以进行DOM复用，因此后续只需要进行DOM移动操作完成更新即可。

function patchKeyedChildren(n1, n2, container) {
  const oldChildren = n1.children;
  const newChildren = n2.children;
  // 四个索引值
  let oldStartIdx = 0;
  let oldEndIdx = oldChildren.length - 1;
  let newStartIdx = 0;
  let newEndIdx = newChildren.length - 1;
  // 四个索引指向的 vnode 节点
  let oldStartVNode = oldChildren[oldStartIdx];
  let oldEndVNode = oldChildren[oldEndIdx];
  let newStartVNode = newChildren[newStartIdx];
  let newEndVNode = newChildren[newEndIdx];
  while(oldEndIdx >= oldStartIdx && newEndIdx >= newStartIdx) {
    if (oldStartVNode.key === newStartVNode.key) {
      // 步骤一：oldStartVNode 和 newStartVNode 比较
      // 调用 patch 函数在 oldStartIdx 和 newStartIdx 之间打补丁
      patch(oldStartVNode, newStartVNode, container);
      // 更新相关索引到下一个位置
      oldStartVNode = oldChildren[++oldStartIdx];
      newStartVNode = newEndVNode[++newEndIdx];
    } else if(oldEndVNode.key === newEndVNode.key) {
      // 步骤二：oldEndVNode 和 newEndVNode 比较
      // 节点在新的顺序中仍然处于尾部，不需要移动，但仍需打补丁
      patch(oldEndVNode, newEndVNode, container);
      // 更新索引和头尾部节点变量
      newEndVNode = newChildren[--newEndIdx];
      oldEndVNode = oldChildren[--oldEndIdx];
    } else if(oldStartVNode.key === newEndVNode.key) {
      // 步骤三：oldStartVNode 和 newEndVNode 比较
      // 调用 patch 函数在 oldStartIdx 和 newEndIdx之间打补丁
      patch(oldStartVNode, newEndVNode, container);
      // 将旧的一组子节点的头部节点对应的真是节点 DOM 节点 oldStartVNode.el 移动
      // 到旧一组子节点的尾部节点对应的真实 DOM 节点后面
      insert(oldStartVNode.el, container, oldEndVNode.el.nextSibiling);
      // 更新相关索引到下一个位置
      oldStartVNode = oldChildren[++oldStartIdx];
      newEndVNode = newChildren[--newEndIdx];
    } else if(oldEndVNode.key === newStartVNode.key) {
      // 步骤四：oldEndVNode 和 newStartVNode 比较
      // 仍然需要调用 patch 函数进行打补丁
      patch(oldEndVNode, newStartVNode, container);
      // 移动 DOM 操作
      // oldEndVNode.el 移动到 oldStartVNode.el 前面
      insert(oldEndVNode.el, container, oldStartVNode.el);
      // 移动 DOM 完成后，更新索引值，并指向下一个位置
      oldEndVNode = oldChildren[--oldEndIdx];
      newStartVNode = newChildren[++newStartIdx];
    }
  }
}

上述代码：

• 步骤四中找到了具有相同key值的节点，说明原来处于尾部的节点在新的顺序周中应该处于头部。因此我们只需要以头部元素 oldStartVNode.el 作为锚点，将尾部元素 oldEndVNode.el 移动到锚点前面即可，移动前仍然需要调用 patch 函数在新旧虚拟节点之间打补丁。然后还需要更新索引，oldEndIdx 向上移动，newStartIdx 向下移动，同时更新 oldEndVNode 和 newStartVNode。
• 步骤三中找到了具有相同key值的节点，说明原来处于头部的节点在新的顺序中应该处于尾部。因此我们需要以 oldEndVNode.el.nextSibiling（旧一组节点的尾部节点对应的真实 DOM 节点的兄弟节点） 作为锚点，将头部元素 oldStartVNode.el 移动到锚点之前即可，移动前需要调用 patch 函数对新旧虚拟节点进行打补丁，然后更新相关的索引，oldStartIdx 向下移动，newEndIdx 向上移动，同时更新 oldStartVNode 和 newEndVNode。
• 步骤二中找到了具有相同key值的节点，说明原来处于尾部的节点在新的顺序中仍然处于尾部，因此不需要进行移动，调用 patch 函数进行新旧虚拟节点打补丁，然后更新相关索引，newEndIdx 和 oldEndIdx 均向上移动，同时更新 newEndVNode 和 oldEndVNode。
• 步骤一中找到了具有相同key值的节点，说明原来处于头部的节点在新的顺序中仍然处于头部，因此不需要进行移动，调用 patch 函数进行新旧虚拟节点打补丁，然后更新相关索引，oldStartIdx 和 newEndIdx 均向下移动，同时更新 oldStartVNode 和 newStartVNode。

非理想状况的处理方式

在四个步骤的比较过程中，都无法找到可复用的节点，此时我们通过增加额外的处理步骤（盘外招）来处理这种情况：拿新的一组子节点中的头部节点去旧的一组子节点中寻找，如下代码所示：

while(oldEndIdx >= oldStartIdx && newEndIdx >= newStartIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 省略部分代码
  } else if(oldEndVNode.key === newEndVNode.key) {
    // 省略部分代码
  } else if(oldStartVNode.key === newEndVNode.key) {
    // 省略部分代码
  } else if(oldEndVNode.key === newStartVNode.key) {
    // 省略部分代码
  } else {
    // 遍历旧的一组节点，试图寻找与 newStartVNode 拥有相同 key 值的节点
    // idxInOld 就是新的一组子节点的头部节点在旧的一组节点中的索引
    const idxInOld = oldChildren.findIndex(ele => ele.key === newStartVNode.key);
  }
}

上图中我们拿新的一组子节点的头部节点p-2去旧的一组子节点中查找，在索引为1的位置找到了可复用的节点。然后将节点p-2对应的真实 DOM 节点移动到当前旧的一组子节点的头部节点p-1所对应的真实 DOM 节点之前。

while(oldEndIdx >= oldStartIdx && newEndIdx >= newStartIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 省略部分代码
  } else if(oldEndVNode.key === newEndVNode.key) {
    // 省略部分代码
  } else if(oldStartVNode.key === newEndVNode.key) {
    // 省略部分代码
  } else if(oldEndVNode.key === newStartVNode.key) {
    // 省略部分代码
  } else {
    // 遍历旧的一组节点，试图寻找与 newStartVNode 拥有相同 key 值的节点
    // idxInOld 就是新的一组子节点的头部节点在旧的一组节点中的索引
    const idxInOld = oldChildren.findIndex(ele => ele.key === newStartVNode.key);
    // idxInOld > 0，说明找了可复用的节点，并且需要将其对应的真实 DOM 移动到头部
    if (idxInOld) {
      // idxInOld 位置对应的 vnode 就是需要移动的节点
      const vnodeToMove = oldChildren[idxInOld];
      // 不要忘记除移动操作之外还应该打补丁
      patch(vnodeToMove, newStartVNode, container);
      // 将 vnodeToMove.el 移动到头部节点 oldStartVNode.el 之前，因此将后者作为锚点
      insert(vnodeToMove.el, container, oldStartVNode.el);
      // 由于位置 idxInOld 处的节点所对应的真实 DOM 已经移动了别处，因此将其设置为 undefined
      oldChildren[idxInOld] = undefined;
      // 最后更新 newStartIdx 到下一个位置
      newStartVNode = newChildren[++newStartIdx];
    }
  }
}

上面代码中，首先判断 idxInOld是否大于0，条件成立，说明找到了可复用的节点，然后将该节点进行移动。先获取需要移动的节点（oldChildren[idxInOld]），移动前进行打补丁，然后找到锚点（oldStartVNode.el），调用 insert 函数完成节点移动。移动完成后，需要将 oldChildren[idxInOld] 设置为undefined，同时更新 newStartIdx （向下移动）。

然后再进行双端Diff的四个步骤，进行节点移动和更新操作。由于旧的一组子节点中存在 undefined（说明该节点已经被处理过，直接跳过即可）因此我们需要对代码进行补充。

while(oldEndIdx >= oldStartIdx && newEndIdx >= newStartIdx) {
  // 增加两个判断分支，如果头部节点为undefined，说明该节点被处理过，直接跳到下一个位置
  if (!oldStartVNode) {
    oldStartVNode = oldChildren[++oldStartIdx];
  } else if (!oldEndVNode) {
    oldEndVNode = oldChildren[--endStartIdx];
  } else if (oldStartVNode.key === newStartVNode.key) {
    // 省略部分代码
  } else if(oldEndVNode.key === newEndVNode.key) {
    // 省略部分代码
  } else if(oldStartVNode.key === newEndVNode.key) {
    // 省略部分代码
  } else if(oldEndVNode.key === newStartVNode.key) {
    // 省略部分代码
  } else {
    // 遍历旧的一组节点，试图寻找与 newStartVNode 拥有相同 key 值的节点
    // idxInOld 就是新的一组子节点的头部节点在旧的一组节点中的索引
    const idxInOld = oldChildren.findIndex(ele => ele.key === newStartVNode.key);
    // idxInOld > 0，说明找了可复用的节点，并且需要将其对应的真实 DOM 移动到头部
    if (idxInOld) {
      // idxInOld 位置对应的 vnode 就是需要移动的节点
      const vnodeToMove = oldChildren[idxInOld];
      // 不要忘记除移动操作之外还应该打补丁
      patch(vnodeToMove, newStartVNode, container);
      // 将 vnodeToMove.el 移动到头部节点 oldStartVNode.el 之前，因此将后者作为锚点
      insert(vnodeToMove.el, container, oldStartVNode.el);
      // 由于位置 idxInOld 处的节点所对应的真实 DOM 已经移动了别处，因此将其设置为 undefined
      oldChildren[idxInOld] = undefined;
      // 最后更新 newStartIdx 到下一个位置
      newStartVNode = newChildren[++newStartIdx];
    }
  }
}

添加新元素

前面说了非理想情况的处理，即在一轮比较过程中，不会命中四个步骤中的任何一步。这时我们会拿新的一组子节点中的头部节点去旧的一组子节点中寻找可复用的节点，然而并非总能找到。如下所示：

我们发现经过四个步骤，均没有命中且p-4节点在旧的一组也没有相同的 key 值对应的节点，因此可得p-4节点是一个新增节点，我们应该将该节点挂载到正确的位置上。因为p-4节点是新的一组子节点中的头部节点，所以需要将它挂载到当前头部节点（旧的一组子节点的头部节点p-1）的前面即可。

while(oldEndIdx >= oldStartIdx && newEndIdx >= newStartIdx) {
  // 增加两个判断分支，如果头部节点为undefined，说明该节点被处理过，直接跳到下一个位置
  if (!oldStartVNode) {
    oldStartVNode = oldChildren[++oldStartIdx];
  } else if (!oldEndVNode) {
    oldEndVNode = oldChildren[--endStartIdx];
  } else if (oldStartVNode.key === newStartVNode.key) {
    // 省略部分代码
  } else if(oldEndVNode.key === newEndVNode.key) {
    // 省略部分代码
  } else if(oldStartVNode.key === newEndVNode.key) {
    // 省略部分代码
  } else if(oldEndVNode.key === newStartVNode.key) {
    // 省略部分代码
  } else {
    // 遍历旧的一组节点，试图寻找与 newStartVNode 拥有相同 key 值的节点
    // idxInOld 就是新的一组子节点的头部节点在旧的一组节点中的索引
    const idxInOld = oldChildren.findIndex(ele => ele.key === newStartVNode.key);
    // idxInOld > 0，说明找了可复用的节点，并且需要将其对应的真实 DOM 移动到头部
    if (idxInOld) {
      // idxInOld 位置对应的 vnode 就是需要移动的节点
      const vnodeToMove = oldChildren[idxInOld];
      // 不要忘记除移动操作之外还应该打补丁
      patch(vnodeToMove, newStartVNode, container);
      // 将 vnodeToMove.el 移动到头部节点 oldStartVNode.el 之前，因此将后者作为锚点
      insert(vnodeToMove.el, container, oldStartVNode.el);
      // 由于位置 idxInOld 处的节点所对应的真实 DOM 已经移动了别处，因此将其设置为 undefined
      oldChildren[idxInOld] = undefined;
      // 最后更新 newStartIdx 到下一个位置
      newStartVNode = newChildren[++newStartIdx];
    } else {
      // 将 newStartVNode 作为新的节点挂载到头部，使用当前头部节点 oldStartVNode.el 作为锚点
      patch(null, newStartVNode, container, oldStartVNode.el);
    }
    newStartVNode = newChildren[++newStartIdx];
  }
}

上面的代码所示，当条件 idxInOld > 0 不成立时，说明 newStartVNode 节点是全新的节点。又由于

newStartVNode 节点是头部节点，因此我们应该将其作为新的头部节点进行挂载。因此我们在调用 patch 函数挂载节点时，我们使用 oldStartVNode.el 作为锚点。这步操作完成之后，新旧两组子节点以及真实 DOM 节点如下图所示。

除了上述新增节点的方式，还有另外一种情况，如下所示：

在经历三轮更新之后，新旧两组子节点以及真实 DOM 节点的状态如下图所示：

可以发现，由于变量 oldStartIdx 的值大于 oldEndIdx 的值，满足更新停止的条件，因此更新停止。但是观察发现，节点p-4在整个更新过程中被遗漏了，因此我们添加额外的代码，代码如下：

while(oldEndIdx >= oldStartIdx && newEndIdx >= newStartIdx) {
  // 省略部分代码
}
// 循环结束后检查索引值的情况
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
  // 如果满足条件，则说明有新的节点遗留，需要挂载他们
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    const anchor = newChildren[newEndIdx + 1] ? newChildren[newEndIdx + 1].el : null;
    patch(null, newChildren[i], container, anchor);
  }
}

我们在while循环之后，增加了一个if条件语句，检查四个索引值的情况。如果满足oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx条件，说明有新的一组子节点中有遗留的节点需要作为新节点挂载。其中索引值位于 newStartIdx 和 newEndIdx 之间的节点都是新节点。于是我们开启一个for循环遍历这个区间的节点，并逐一进行挂载。挂载时的锚点仍然使用当前的头部节点 oldStartVNode.el。

移除不存在的元素

解决了新增节点的问题后，我们来讨论关于移除元素的情况，如下所示：

经过两轮更新后，如下所示：

我们可以发现：此时变量 newStartIdx 的值大于变量 newEndIdx 的值，满足更新停止的条件，于是更新结束。但是旧的一组子节点中存在未被处理的节点，应该将其移除，我们新增额外的代码处理，代码如下：

while(oldEndIdx >= oldStartIdx && newEndIdx >= newStartIdx) {
  // 省略部分代码
}
if (oldEndIdx < oldStartIdx && newStart <= newEndIdx) {
  // 添加新节点
  // 省略部分代码
} else if (oldEndIdx >= oldStartIdx && newStart > newEndIdx) {
  // 移除操作
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {
    unmount(oldChildren[i]);
  }
}

与处理新增节点类似，我们在while循环结束后又增加了一个 else…if 分支，用于卸载已经不存在的节点。索引值位于 oldStartIdx 和 oldEndIdx 区间的节点都应该被卸载，于是我们开启一个 for 循环将他们逐一卸载。

完整的代码如下：

function patchKeyedChildren(n1, n2, container) {
  const oldChildren = n1.children;
  const newChildren = n2.children;
  // 四个索引值
  let oldStartIdx = 0;
  let oldEndIdx = oldChildren.length - 1;
  let newStartIdx = 0;
  let newEndIdx = newChildren.length - 1;
  // 四个索引指向的 vnode 节点
  let oldStartVNode = oldChildren[oldStartIdx];
  let oldEndVNode = oldChildren[oldEndIdx];
  let newStartVNode = newChildren[newStartIdx];
  let newEndVNode = newChildren[newEndIdx];
  
  while(oldEndIdx >= oldStartIdx && newEndIdx >= newStartIdx) {
    // 增加两个判断分支，如果头部节点为undefined，说明该节点被处理过，直接跳到下一个位置
    if (!oldStartVNode) {
      oldStartVNode = oldChildren[++oldStartIdx];
    } else if (!oldEndVNode) {
      oldEndVNode = oldChildren[--endStartIdx];
    } else if (oldStartVNode.key === newStartVNode.key) {
      // 第一步：oldStartVNode 和 newStartVNode 比较
      // 调用 patch 函数在 oldStartIdx 和 newStartIdx 之间打补丁
      patch(oldStartVNode, newStartVNode, container);
      // 更新相关索引到下一个位置
      oldStartVNode = oldChildren[++oldStartIdx];
      newStartVNode = newEndVNode[++newEndIdx];
    } else if(oldEndVNode.key === newEndVNode.key) {
      // 第二步：oldEndVNode 和 newEndVNode 比较
      // 节点在新的顺序中仍然处于尾部，不需要移动，但仍需打补丁
      patch(oldEndVNode, newEndVNode, container);
      // 更新索引和头尾部节点变量
      newEndVNode = newChildren[--newEndIdx];
      oldEndVNode = oldChildren[--oldEndVNode];
    } else if(oldStartVNode.key === newEndVNode.key) {
      // 第三步：oldStartVNode 和 newEndVNode 比较
      // 调用 patch 函数在 oldStartIdx 和 newEndIdx之间打补丁
      patch(oldStartVNode, newEndVNode, container);
      // 将旧的一组子节点的头部节点对应的真是节点 DOM 节点 oldStartVNode.el 移动
      // 到旧一组子节点的尾部节点对应的真实 DOM 节点后面
      insert(oldStartVNode.el, container, oldEndVNode.el.nextSibiling);
      // 更新相关索引到下一个位置
      oldStartVNode = oldChildren[++oldStartIdx];
      newEndVNode = newChildren[--newEndIdx];
    } else if(oldEndVNode.key === newStartVNode.key) {
      // 第四步：oldEndVNode 和 newStartVNode 比较
      // 仍然需要调用 patch 函数进行打补丁
      patch(oldEndVNode, newStartVNode, container);
      // 移动 DOM 操作
      // oldEndVNode.el 移动到 oldStartVNode.el 前面
      insert(oldEndVNode.el, container, oldStartVNode.el);
      // 移动 DOM 完成后，更新索引值，并指向下一个位置
      oldEndVNode = oldChildren[--oldEndIdx];
      newStartVNode = newChildren[++newStartIdx];
    } else {
      // 遍历旧的一组节点，试图寻找与 newStartVNode 拥有相同 key 值的节点
      // idxInOld 就是新的一组子节点的头部节点在旧的一组节点中的索引
      const idxInOld = oldChildren.findIndex(ele => ele.key === newStartVNode.key);
      // idxInOld > 0，说明找了可复用的节点，并且需要将其对应的真实 DOM 移动到头部
      if (idxInOld) {
        // idxInOld 位置对应的 vnode 就是需要移动的节点
        const vnodeToMove = oldChildren[idxInOld];
        // 不要忘记除移动操作之外还应该打补丁
        patch(vnodeToMove, newStartVNode, container);
        // 将 vnodeToMove.el 移动到头部节点 oldStartVNode.el 之前，因此将后者作为锚点
        insert(vnodeToMove.el, container, oldStartVNode.el);
        // 由于位置 idxInOld 处的节点所对应的真实 DOM 已经移动了别处，因此将其设置为 undefined
        oldChildren[idxInOld] = undefined;
        // 最后更新 newStartIdx 到下一个位置
        newStartVNode = newChildren[++newStartIdx];
      } else {
        // 将 newStartVNode 作为新的节点挂载到头部，使用当前头部节点 oldStartVNode.el 作为锚点
        patch(null, newStartVNode, container, oldStartVNode.el);
      }
      newStartVNode = newChildren[++newStartIdx];
    }
  	// 循环结束后检查索引值的情况
  	if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
      // 如果满足条件，则说明有新的节点遗留，需要挂载他们
      for (let i = newStartIdx; i <= newEndIdx; i++) {
        const anchor = newChildren[newEndIdx + 1] ? newChildren[newEndIdx + 1].el : null;
        patch(null, newChildren[i], container, anchor);
      }
    }
}