likes
comments
collection
share

精读《Vuejs设计与实现》第 10 章（双端 diff 算法）

作者站长头像
站长
· 阅读数 16

10.1 双端比较的原理

简单 Diff 算法的问题在于，它对 DOM 的移动操作并不是最优的，我们举个例子：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）上图如果使用简单 Diff，则会发生两次 DOM 移动操作：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）上述两次移动操作，其实只需要把真实 DOM 节点 p-3 移动到真实 DOM 节点 p-1 之前这一次操作即可：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）上述操作，我们可以通过双端 Diff 算法实现。双端 Diff 算法是同时进行两组子节点的头尾比较的一种算法。首先，我们需要设定四个索引，分别指向新旧子节点的两端：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）

我们在 patchChildren 和 patchKeyedChildren 函数中定义了四个端点：

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
}

在 patchKeyedChildren 函数中，我们首先获取新旧子节点集，然后创建四个索引分别指向新旧子节点的起始和结束位置。然后，我们可以利用这些索引找到对应的虚拟节点：

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]
}

双端比较过程可以分为四步：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）

  • 第一步，我们比较旧子节点集的第一个节点 p-1 和新子节点集的第一个节点 p-4，它们的 key 值不同，则说明它们不可复用。
  • 第二步，我们比较旧子节点集的最后一个节点 p-4 和新子节点集的最后一个节点 p-3，它们的 key 值不同，同样，它们也不可复用。
  • 第三步，我们比较旧子节点集的第一个节点 p-1 和新子节点集的最后一个节点 p-3，它们的 key 值不同，那么它们也不可复用。
  • 第四步，我们比较旧子节点集的最后一个节点 p-4 和新子节点集的第一个节点 p-4，它们的 key 值相同，说明它们可复用。

当我们发现可复用的元素之后，只需将其移动到正确位置即可。上面我们在比较过程中发现旧子节点集的最后一个节点与新子节点集的第一个节点相同，那么我们就应该将这个节点从尾部移动到头部。对应的代码如下：

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]

  if (oldStartVNode.key === newStartVNode.key) {
    // 第一步：oldStartVNode 和 newStartVNode 比较
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 第二步：oldEndVNode 和 newEndVNode 比较
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 第三步：oldStartVNode 和 newEndVNode 比较
  } 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]
  }
}

上述代码，我们使用一系列的 if...else if... 语句比较四个索引指向的虚拟节点。在比较过程的最后一步，我们发现具有相同 key 值的节点，说明它们可以复用。因此，我们只需要将尾部元素移动到头部，即我们只需要以头部元素 oldStartVNode.el 作为锚点，将尾部元素 oldEndVNode.el 移动到锚点前面即可，注意移动之前，我们还需要调用 patch 函数为新旧虚拟节点打补丁。完成 DOM 移动操作之后，接下来的关键步骤是更新索引值，由于第四步中涉及的两个索引分别是 oldEndIdx 和 newStartIdx，所以我们需要更新两者的值，让它们各自朝正确的方向前进一步，并指向下一个节点：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）此时，真实 DOM 节点顺序为 p-4、p-1、p-2、p-3，这与新的一组子节点顺序不一致。这是因为 Diff 算法还没结束，我们还需继续下一轮更新，我们将其封装到一个 while 循环中：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 步骤一：oldStartVNode 和 newStartVNode 比较
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 步骤二：oldEndVNode 和 newEndVNode 比较
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 步骤三：oldStartVNode 和 newEndVNode 比较
  } 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]
  }
}

上述代码，整个 while 循环执行的条件是：头部索引值要小于等于尾部索引值。第一轮更新后循环条件仍然成立，如上图所示，因此需要进行下一轮的比较：

  1. 首先，我们比较旧子节点头部节点 p-1 与新子节点头部节点 p-2。这里的头部节点指向的是由 oldStartIdx 和 newStartIdx 索引标识的节点。由于 p-1 与 p-2 的 key 值不同，它们不能复用，故不进行任何操作。
  2. 接着，我们比较旧子节点尾部节点 p-3 与新子节点尾部节点 p-3。它们的 key 值相同，故可复用。并且，由于都在尾部，无需移动 DOM，只需打补丁即可。代码如下：
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 步骤一：oldStartVNode 和 newStartVNode 比较
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 步骤二：oldEndVNode 和 newEndVNode 比较
    // 节点在新的顺序中仍然处于尾部，不需要移动，但仍需打补丁
    patch(oldEndVNode, newEndVNode, container)
    // 更新索引和头尾部节点变量
    oldEndVNode = oldChildren[--oldEndIdx]
    newEndVNode = newChildren[--newEndIdx]
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 步骤三：oldStartVNode 和 newEndVNode 比较
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 步骤四：oldEndVNode 和 newStartVNode 比较
    patch(oldEndVNode, newStartVNode, container)
    insert(oldEndVNode.el, container, oldStartVNode.el)
    oldEndVNode = oldChildren[--oldEndIdx]
    newStartVNode = newChildren[++newStartIdx]
  }
}

在这一轮更新完成之后，新旧两组子节点与真实 DOM 节点的状态，如图所示：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）DOM 的顺序无变化，因为此轮比较未移动任何 DOM，仅对节点 p-3 打补丁。现在，让我们进入下轮比较：

  1. 首先，我们比较旧子节点组中的头部节点 p-1 和新子节点组中的头部节点 p-2。由于它们的 key 值不同，它们是不可复用的，所以我们不做任何操作。
  2. 其次，我们比较旧子节点组中的尾部节点 p-2 和新子节点组中的尾部节点 p-1。同样，由于它们的 key 值不同，它们也是不可复用的，所以我们不做任何操作。
  3. 然后，我们比较旧子节点组中的头部节点 p-1 和新子节点组中的尾部节点 p-1。由于它们的 key 值相同，它们是可复用的。在这个比较过程中，我们发现了相同的节点。这说明 p-1 节点在新的顺序中从头部节点变为了尾部节点。因此，我们需要将 p-1 节点对应的真实 DOM 移动到旧子节点组的尾部节点 p-2 所对应的真实 DOM 后面，并更新相关索引到下一个位置。如下图所示：

精读《Vuejs设计与实现》第 10 章（双端 diff 算法）实现如下：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
  } else if (oldEndVNode.key === newEndVNode.key) {
    patch(oldEndVNode, newEndVNode, container)
    oldEndVNode = oldChildren[--oldEndIdx]
    newEndVNode = newChildren[--newEndIdx]
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 调用 patch 函数在 oldStartVNode 和 newEndVNode 之间打补丁
    patch(oldStartVNode, newEndVNode, container)
    // 将旧的一组子节点的头部节点对应的真实 DOM 节点 oldStartVNode.el 移动到
    // 旧的一组子节点的尾部节点对应的真实 DOM 节点后面
    insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)
    // 更新相关索引到下一个位置
    oldStartVNode = oldChildren[++oldStartIdx]
    newEndVNode = newChildren[--newEndIdx]
  } else if (oldEndVNode.key === newStartVNode.key) {
    patch(oldEndVNode, newStartVNode, container)
    insert(oldEndVNode.el, container, oldStartVNode.el)

    oldEndVNode = oldChildren[--oldEndIdx]
    newStartVNode = newChildren[++newStartIdx]
  }
}

上述代码，如果旧子节点组的头部节点与新子节点组的尾部节点匹配，则旧节点对应的真实 DOM 节点需要移动到尾部。我们获取当前尾部节点的下一个兄弟节点作为锚点，即oldEndVNode.el.nextSibling，并更新相关索引到下一个位置。此时，新旧两组子节点的头部索引和尾部索引发生重合，但仍然满足循环的条件，所以还会进行下一轮的更新。

  1. 然后我们比较旧子节点组中的头部节点 p-2 与新子节点组中的头部节点 p-2。发现它们的 key 值相同，是可复用的，但无需移动，只需调用 patch 函数进行打补丁即可。整体代码实现如下：
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 调用 patch 函数在 oldStartVNode 与 newStartVNode 之间打补丁
    patch(oldStartVNode, newStartVNode, container)
    // 更新相关索引，指向下一个位置
    oldStartVNode = oldChildren[++oldStartIdx]
    newStartVNode = newChildren[++newStartIdx]
  } else if (oldEndVNode.key === newEndVNode.key) {
    patch(oldEndVNode, newEndVNode, container)
    oldEndVNode = oldChildren[--oldEndIdx]
    newEndVNode = newChildren[--newEndIdx]
  } else if (oldStartVNode.key === newEndVNode.key) {
    patch(oldStartVNode, newEndVNode, container)
    insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)

    oldStartVNode = oldChildren[++oldStartIdx]
    newEndVNode = newChildren[--newEndIdx]
  } else if (oldEndVNode.key === newStartVNode.key) {
    patch(oldEndVNode, newStartVNode, container)
    insert(oldEndVNode.el, container, oldStartVNode.el)

    oldEndVNode = oldChildren[--oldEndIdx]
    newStartVNode = newChildren[++newStartIdx]
  }
}

在这轮更新完成后，真实 DOM 节点的顺序与新子节点组的顺序相同了：p-4, p-2, p-1, p-3。精读《Vuejs设计与实现》第 10 章（双端 diff 算法）同时，因为 newStartIdx 和 oldStartIdx 的值都小于 newEndIdx 和 oldEndIdx，所以循环终止，双端 Diff 算法执行完毕。

10.2 双端比较的优势

我们使用双端 Diff 算法演示下优势，下面例子使用简单 diff 会发生两次 DOM 移动操作：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）我们按照双端比较的步骤执行更新：

  1. 比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-3，两者 key 值不同，不可复用
  2. 比较旧的一组子节点中的尾部节点 p-3 与新的一组子节点中的尾部节点 p-2，两者 key 值不同，不可复用
  3. 比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的尾部节点 p-2，两者 key 值不同，不可复用
  4. 比较旧的一组子节点中的尾部节点 p-3 与新的一组子节 点中的头部节点 p-3，发现可以进行复用

在第四步我们找到了位于尾部的，可复用的节点 p-3，但它在新的一组子节点中处于头部。因此，只需要让节点 p-3 对应的真实 DOM 变成新的头部节点即可：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）此时其实真实 DOM 节点的顺序已经与新的一组子节点的顺序一致了。但双端比较依然会继续下一轮比较：比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-1，两者的 key 值相同，可以复用。但由于两者都处于头部，因此不需要移动，只需要打补丁即可。在这一轮比较过后，新旧两组子节点与真实 DOM 节点的状态如图：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）此时，双端 Diff 算法仍然没有停止，开始新一轮的比较：比较旧的一组子节点中的头部节点 p-2 与新的一组 子节点中的头部节点 p-2，两者的 key 值相同，可以复用。但由于两者都处于头部，因此不需要移动，只需要打补丁即可：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）此时，索引 newStartIdx 比 newEndIdx 大，oldStartIdx 比 oldEndIdx 大，循环结束，于是更新结束。同样例子简单 Diff 两次完成 DOM 移动操作，双端 Diff 算法只需要一次 DOM 移动操作即可完成更新。

10.3 非理想状况的处理方式

在双端 Diff 算法中，有时我们会遇到一种情况，即旧子节点和新子节点的头尾均无法匹配。在这种情况下，我们需要采取额外的步骤来处理。下面以一个例子来具体说明：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）旧的子节点组：p-1、p-2、p-3、p-4。 新的子节点组：p-2、p-4、p-1、p-3。在尝试使用双端 Diff 算法进行比较时，我们会发现无法找到匹配的节点。

这时，我们用新的一组子节点的头部节点去旧的一组节点寻找：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  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(node => node.key === newStartVNode.key)
  }
}

p2 最终移动如下图：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）当我们拿新的一组子节点的头部节点 p-2 去旧的一组子节点中查找时，会在索引为 1 的位置找到可复用的节点。节点 p-2 原本不是头部节点，但在更新之后，它应该变成头部节点。

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 省略部分代码
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 省略部分代码
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 省略部分代码
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 省略部分代码
  } else {
    // 遍历旧 children，试图寻找与 newStartVNode 拥有相同 key 值的元素
    const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key)
    // idxInOld 大于 0，说明找到了可复用的节点，并且需要将其对应的真实 DOM 移动到头部
    if (idxInOld > 0) {
      // 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 中。查看 idxInOld 是否大于 0。如果找到了匹配的节点（即idxInOld > 0），我们将该节点对应的真实 DOM 移动到当前的头部节点前，并更新相关索引到下一个位置。注意在移动节点之前，我们需要调用 patch 函数进行更新。由于处于 idxInOld 处的节点已经处理过了（对应的真实 DOM 移到了别处），因此我们应该 oldChildren[idxInOld] 设置为 undefined。新的一组子节点中的头部节点已经处理完毕，因此将 newStartIdx 前进到下一个位置代码最终执行后如下图：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）此时，真实 DOM 的顺序为：p-2、p-1、p-3、p-4。接着，双端 Diff 算法会继续进行：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）

  1. 比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-4，两者 key 值不同，不可复用。
  2. 比较旧的一组子节点中的尾部节点 p-4 与新的一组子节点中的尾部节点 p-3，两者 key 值不同，不可复用。
  3. 比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的尾部节点 p-3，两者 key 值不同，不可复用。
  4. 比较旧的一组子节点中的尾部节点 p-4 与新的一组子节点中的头部节点 p-4，两者的 key 值相同，可以复用。

在这一轮第四步我们找到可复用的节点，因此，按照双端 Diff 算法的逻辑移动真实 DOM，即把节点 p-4 对应的真实 DOM 移动到旧的一组子节点中头部节点 p-1 所对应的真实 DOM 前面：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）此时，真实 DOM 节点的顺序是：p-2、p-4、p-1、p-3。接着，开始下一轮的比较：

  1. 比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-1，两者的 key 值相同，可以复用。

这一轮比较中，第一步就找到了可复用的节点。由于两者都处 于头部，所以不需要对真实 DOM 进行移动，只需要打补丁即可：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）此时，真实 DOM 节点的顺序是：p-2、p-4、p-1、p-3。接着，进行下一轮的比较。值得注意的是，旧子节点组的首节点现在是 undefined，意味着该节点已被处理，我们可以直接跳过。为此，我们需要补充这部分逻辑的代码：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // 增加两个判断分支，如果头尾部节点为 undefined，则说明该节点已经被处理过了，直接跳到下一个位置
  if (!oldStartVNode) {
    oldStartVNode = oldChildren[++oldStartIdx]
  } else if (!oldEndVNode) {
    oldEndVNode = oldChildren[--oldEndIdx]
  } 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 {
    const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key)
    if (idxInOld > 0) {
      const vnodeToMove = oldChildren[idxInOld]
      patch(vnodeToMove, newStartVNode, container)
      insert(vnodeToMove.el, container, oldStartVNode.el)
      oldChildren[idxInOld] = undefined
      newStartVNode = newChildren[++newStartIdx]
    }
  }
}

在这一轮比较过后，新旧两组子节点与真实 DOM 节点的状态：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）接着进行最后一轮的比较：

  1. 比较旧的一组子节点中的头部节点 p-3 与新的一组子节点中的头部节点 p-3，两者的 key 值相同，可以复用

在第一步中找到了可复用的节点。由于两者都是头部节点，因此 不需要进行 DOM 移动操作，直接打补丁即可。在这一轮比较过后，最终状态如图：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）这时，满足循环停止的条件，于是更新完成。最终，真实 DOM 节点的顺序与新的一组子节点的顺序一致，都是：p-2、p-4、p-1、p-3。

10.4 添加新元素

在前一节，我们讨论了如何处理不理想情况，即在一轮比较中，都无法匹配上我们的四个步骤。在这种情况下，我们会尝试用新子节点集合的头节点去旧子节点集合中寻找可复用的节点，但并非总能找到匹配的节点，如图所示：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）考虑这样一个例子：旧子节点集合为 p-1、p-2、p-3，新的子节点集合为 p-4、p-1、p-3、p-2。在初次比较时，我们无法找到可复用的节点。我们尝试用新的头节点 p-4 去旧节点集合中寻找相同 key 的节点，但旧集合中并没有 p-4 节点这表明 p-4 是一个新增的节点，我们应将它插入到正确的位置。由于 p-4 是新子节点集合的头节点，我们可以直接将其插入到当前头节点之前。这里的"当前"头节点指的是旧子节点集合中的头节点对应的真实 DOM 节点 p-1。下面的代码展示了如何实现这个挂载操作：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // 增加两个判断分支，如果头尾部节点为 undefined，则说明该节点已经被处理过了，直接跳到下一个位置
  if (!oldStartVNode) {
    oldStartVNode = oldChildren[++oldStartIdx]
  } else if (!oldEndVNode) {
    oldEndVNode = newChildren[--oldEndIdx]
  } 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 {
    const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key)
    if (idxInOld > 0) {
      const vnodeToMove = oldChildren[idxInOld]
      patch(vnodeToMove, newStartVNode, container)
      insert(vnodeToMove.el, container, oldStartVNode.el)
      oldChildren[idxInOld] = undefined
    } else {
      // 将 newStartVNode 作为新节点挂载到头部，使用当前头部节点 oldStartVNode.el 作为锚点
      patch(null, newStartVNode, container, oldStartVNode.el)
    }
    newStartVNode = newChildren[++newStartIdx]
  }
}

当 idxInOld > 0 不成立时，说明 newStartVNode 是一个全新的节点。因为它是头节点，我们应将其作为新的头节点进行挂载。因此，我们在调用 patch 函数挂载节点时，使用 oldStartVNode.el 作为锚点。执行结果如下图所示：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）

然而，这个算法并不完美。例如，看下面例子精读《Vuejs设计与实现》第 10 章（双端 diff 算法）新子节点集合的顺序为 p-4、p-1、p-2、p-3 时，我们按照双端 Diff 算法的思路来执行更新下：

  1. 比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-4，两者的 key 值不同，不可以复用。
  2. 比较旧的一组子节点中的尾部节点 p-3 与新的一组子节点中的尾部节点 p-3，两者的 key 值相同，可以复用。

在第二步中找到了可复用的节点，因此进行更新，结果如图：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）接着进行下一轮更新：

  1. 比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-4，两者的 key 值不同，不可以复用。
  2. 比较旧的一组子节点中的尾部节点 p-2 与新的一组子节点中的尾部节点 p-2，两者的 key 值相同，可以复用。

在第二步中找到了可复用的节点，因此再次进行更新，结果如图：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）接着，进行下一轮的更新：

  1. 比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-4，两者的 key 值不同，不可以复用。
  2. 比较旧的一组子节点中的尾部节点 p-1 与新的一组子节 点中的尾部节点 p-1，两者的 key 值相同，可以复用。

在第二步中找到了可复用的节点，因此再次进行更新，结果如图：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）当这一轮更新完毕后，由于变量 oldStartIdx 的值大于 oldEndIdx 的值，满足更新停止的条件，因此更新停止。但通过观察可知，节点 p-4 在整个更新过程中被遗漏了，没有得到任何处理，这说明我们的算法是有缺陷的。为了弥补这个缺陷，我们需要添加额外的处理代码：

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

在这个改进后的版本中，如果 oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx 成立，这意味着新子节点集合中有未处理的节点需要作为新节点挂载。这些新节点的索引值在 newStartIdx 和 newEndIdx 这个区间内。因此，我们使用一个 for 循环来遍历这个区间内的节点并逐一挂载。挂载时的锚点仍然使用当前的头节点 oldStartVNode.el，这样我们就完成了对新增元素的处理。

10.5 移除不存在的元素

在解决了节点添加的问题之后，让我们进一步探讨元素移除的场景，如图所示：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）

  • 旧子节点集合：p-1、p-2、p-3
  • 新子节点集合：p-1、p-3

显然，新节点组中已经没有 p-2。我们依然采用双端 Diff 算法流程更新：

  1. 比较旧的一组子节点中的头部节点 p-1 与新的一组 子节点中的头部节点 p-1，两者的 key 值相同，可以复用。

在第一步的比较中找到了可复用的节点，于是执行更新。在这一轮比较过后状态如图：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）接着，执行下一轮更新：

  1. 比较旧的一组子节点中的头部节点 p-2 与新的一组子节点中的头部节点 p-3，两者的 key 值不同，不可以复用。
  2. 比较旧的一组子节点中的尾部节点 p-3 与新的一组子节点中的尾部节点 p-3，两者的 key 值相同，可以复用。

在第二步中找到了可复用的节点，于是进行更新。更新后状态如图：精读《Vuejs设计与实现》第 10 章（双端 diff 算法）此时变量 newStartIdx 的值大于变量 newEndIdx 的值，满足更新停止的条件，于是更新结束。但旧的一组子节点中存在未被处理的节点，应该将其移除，我们需要添加额外的代码来处理这些节点，如下：

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

在这段代码中，我们增加了一个 else if 分支来处理需要被卸载的节点。如果新的子节点集合已经处理完，但旧的子节点集合中还有未处理的节点，我们就会遍历这些剩余的节点并逐一卸载。

10.6 总结

在本章中，我们介绍了双端 Diff 算法的原理及其优势。双端 Diff 算法在新旧两组子节点的四个端点间进行比较，试图找到可复用的节点。相比简单 Diff 算法，双端 Diff 算法更高效，因为对于同样的更新场景，它需要进行的 DOM 移动操作更少。

转载自:https://juejin.cn/post/7270047564102680612
评论
请登录