vue diff 双端比较算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了vue diff 双端比较算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

双端指针

vue diff 双端比较算法,Vue源码,vue.js,算法,前端,javascript

使用四个变量 oldStartIdx、oldEndIdx、newStartIdx 以及 newEndIdx 分别存储旧 children 和新 children 的两个端点的位置索引

let oldStartIdx = 0
let oldEndIdx = prevChildren.length - 1
let newStartIdx = 0
let newEndIdx = nextChildren.length - 1

除了位置索引之外，还需要拿到四个位置索引所指向的 VNode

let oldStartVNode = prevChildren[oldStartIdx]
let oldEndVNode = prevChildren[oldEndIdx]
let newStartVNode = nextChildren[newStartIdx]
let newEndVNode = nextChildren[newEndIdx]

比较策略

使用旧 children 的头一个 VNode 与新 children 的头一个 VNode 比对，即 oldStartVNode 和 newStartVNode 比较对。
使用旧 children 的最后一个 VNode 与新 children 的最后一个 VNode 比对，即 oldEndVNode 和 newEndVNode 比对。
使用旧 children 的头一个 VNode 与新 children 的最后一个 VNode 比对，即 oldStartVNode 和 newEndVNode 比对。
使用旧 children 的最后一个 VNode 与新 children 的头一个 VNode 比对，即 oldEndVNode 和 newStartVNode 比对。

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 比对
  }
}

命中策略四

第一步：拿旧 children 中的 li-a 和新 children 中的 li-d 进行比对，由于二者 key 值不同，所以不可复用，什么都不做。
第二步：拿旧 children 中的 li-d 和新 children 中的 li-c 进行比对，同样不可复用，什么都不做。
第三步：拿旧 children 中的 li-a 和新 children 中的 li-c 进行比对，什么都不做。
第四步：拿旧 children 中的 li-d 和新 children 中的 li-d 进行比对，由于这两个节点拥有相同的 key 值，所以我们在这次比对的过程中找到了可复用的节点。
- li-d 节点所对应的真实 DOM 原本是最后一个子节点，并且更新之后它应该变成第一个子节点。所以我们需要把 li-d 所对应的真实 DOM 移动到最前方即可：

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)
	  // 更新完成后，将容器中最后一个子节点移动到最前面，使其成为第一个子节点
	  container.insertBefore(oldEndVNode.el, oldStartVNode.el)
	  // 更新索引，指向下一个位置
	  oldEndVNode = prevChildren[--oldEndIdx]
	  newStartVNode = nextChildren[++newStartIdx]
	}
}

命中策略二

上一步更新完成之后，新的索引关系可以用下图来表示：
第一步：拿旧 children 中的 li-a 和新 children 中的 li-b 进行比对，由于二者 key 值不同，所以不可复用，什么都不做。
第二步：拿旧 children 中的 li-c 和新 children 中的 li-c 进行比对，此时，由于二者拥有相同的 key，所以是可复用的节点，但是由于二者在新旧 children 中都是最末尾的一个节点，所以是不需要进行移动操作的，只需要调用 patch 函数更新即可，同时将相应的索引前移一位

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 步骤一：oldStartVNode 和 newStartVNode 比对
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 步骤二：oldEndVNode 和 newEndVNode 比对

    // 调用 patch 函数更新
    patch(oldEndVNode, newEndVNode, container)
    // 更新索引，指向下一个位置
    oldEndVNode = prevChildren[--oldEndIdx]
    newEndVNode = nextChildren[--newEndIdx]
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 步骤三：oldStartVNode 和 newEndVNode 比对
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 步骤四：oldEndVNode 和 newStartVNode 比对

    // 先调用 patch 函数完成更新
    patch(oldEndVNode, newStartVNode, container)
    // 更新完成后，将容器中最后一个子节点移动到最前面，使其成为第一个子节点
    container.insertBefore(oldEndVNode.el, oldStartVNode.el)
    // 更新索引，指向下一个位置
    oldEndVNode = prevChildren[--oldEndIdx]
    newStartVNode = nextChildren[++newStartIdx]
  }
}

命中策略三

上一步更新完成之后，新的索引关系可以用下图来表示：
第一步：拿旧 children 中的 li-a 和新 children 中的 li-b 进行比对，由于二者 key 值不同，所以不可复用，什么都不做。
第二步：拿旧 children 中的 li-b 和新 children 中的 li-a 进行比对，不可复用，什么都不做。
第三步：拿旧 children 中的 li-a 和新 children 中的 li-a 进行比对，此时，我们找到了可复用的节点。
- 这一次满足的条件是：oldStartVNode.key === newEndVNode.key，这说明：li-a 节点所对应的真实 DOM 原本是第一个子节点，但现在变成了“最后”一个子节点，这里的“最后”并不是指真正意义上的最后一个节点，而是指当前索引范围内的最后一个节点。所以移动操作也是比较明显的，我们将 oldStartVNode 对应的真实 DOM 移动到 oldEndVNode 所对应真实 DOM 的后面即可

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 步骤一：oldStartVNode 和 newStartVNode 比对
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 步骤二：oldEndVNode 和 newEndVNode 比对

    // 调用 patch 函数更新
    patch(oldEndVNode, newEndVNode, container)
    // 更新索引，指向下一个位置
    oldEndVNode = prevChildren[--oldEndIdx]
    newEndVNode = newEndVNode[--newEndIdx]
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 步骤三：oldStartVNode 和 newEndVNode 比对

    // 调用 patch 函数更新
    patch(oldStartVNode, newEndVNode, container)
    // 将 oldStartVNode.el 移动到 oldEndVNode.el 的后面，也就是 oldEndVNode.el.nextSibling 的前面
    container.insertBefore(
      oldStartVNode.el,
      oldEndVNode.el.nextSibling
    )
    // 更新索引，指向下一个位置
    oldStartVNode = prevChildren[++oldStartIdx]
    newEndVNode = nextChildren[--newEndIdx]
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 步骤四：oldEndVNode 和 newStartVNode 比对

    // 先调用 patch 函数完成更新
    patch(oldEndVNode, newStartVNode, container)
    // 更新完成后，将容器中最后一个子节点移动到最前面，使其成为第一个子节点
    container.insertBefore(oldEndVNode.el, oldStartVNode.el)
    // 更新索引，指向下一个位置
    oldEndVNode = prevChildren[--oldEndIdx]
    newStartVNode = nextChildren[++newStartIdx]
  }
}

命中策略一

上一步更新完成之后，新的索引关系可以用下图来表示：
第一步：拿旧 children 中的 li-b 和新 children 中的 li-b 进行比对，二者拥有相同的 key，可复用

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 步骤一：oldStartVNode 和 newStartVNode 比对

    // 调用 patch 函数更新
    patch(oldStartVNode, newStartVNode, container)
    // 更新索引，指向下一个位置
    oldStartVNode = prevChildren[++oldStartIdx]
    newStartVNode = nextChildren[++newStartIdx]
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 省略...
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 省略...
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 省略...
  }
}

未命中四种策略，遍历旧节点列表

vue diff 双端比较算法,Vue源码,vue.js,算法,前端,javascript

上图中 ①、②、③、④ 这四步中的每一步比对，都无法找到可复用的节点
策略为：拿新 children 中的第一个节点尝试去旧 children 中寻找，试图找到拥有相同 key 值的节点
如果在旧的 children 中找到了与新 children 中第一个节点拥有相同 key 值的节点，这意味着：旧 children 中的这个节点所对应的真实 DOM 在新 children 的顺序中，已经变成了第一个节点。所以我们需要把该节点所对应的真实 DOM 移动到最前头

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 = prevChildren.findIndex(
      node => node.key === newStartVNode.key
    )
    if (idxInOld >= 0) {
      // vnodeToMove 就是在旧 children 中找到的节点，该节点所对应的真实 DOM 应该被移动到最前面
      const vnodeToMove = prevChildren[idxInOld]
      // 调用 patch 函数完成更新
      patch(vnodeToMove, newStartVNode, container)
      // 把 vnodeToMove.el 移动到最前面，即 oldStartVNode.el 的前面
      container.insertBefore(vnodeToMove.el, oldStartVNode.el)
      // 由于旧 children 中该位置的节点所对应的真实 DOM 已经被移动，所以将其设置为 undefined
      prevChildren[idxInOld] = undefined
    }
    // 将 newStartIdx 下移一位
    newStartVNode = nextChildren[++newStartIdx]
  }
}

因为旧节点已经找到并处理过了，所以后续的双端比较需要跳过处理过的节点
将旧 children 中的 li-b 节点变成 undefined，然后旧节点指针遇到时跳过

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // undefined 跳过
  if (!oldStartVNode) {
    oldStartVNode = prevChildren[++oldStartIdx]
  } else if (!oldEndVNode) { // undefined 跳过
    oldEndVNode = prevChildren[--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 = prevChildren.findIndex(
      node => node.key === newStartVNode.key
    )
    if (idxInOld >= 0) {
      const vnodeToMove = prevChildren[idxInOld]
      patch(vnodeToMove, newStartVNode, container)
      prevChildren[idxInOld] = undefined
      container.insertBefore(vnodeToMove.el, oldStartVNode.el)
    }
    newStartVNode = nextChildren[++newStartIdx]
  }
}

新增情况一

节点所在的双端不满足四种策略，也不满足能找到旧节点

vue diff 双端比较算法,Vue源码,vue.js,算法,前端,javascript

在新 children 中，节点 li-d 是一个全新的节点。在这个例子中 ①、②、③、④ 这四步的比对仍然无法找到可复用节点，所以我们会尝试拿着新 children 中的 li-d 节点去旧的 children 寻找与之拥有相同 key 值的节点，结果很显然，我们无法找到这样的节点。这时说明该节点是一个全新的节点，我们应该将其挂载到容器中，由于 li-d 节点的位置索引是 newStartIdx，这说明 li-d 节点是当前这一轮比较中的“第一个”节点，所以只要把它挂载到位于 oldStartIdx 位置的节点所对应的真实 DOM 前面就可以了，即 oldStartVNode.el

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (!oldStartVNode) {
    oldStartVNode = prevChildren[++oldStartIdx]
  } else if (!oldEndVNode) {
    oldEndVNode = prevChildren[--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 = prevChildren.findIndex(
      node => node.key === newStartVNode.key
    )
    if (idxInOld >= 0) {
      const vnodeToMove = prevChildren[idxInOld]
      patch(vnodeToMove, newStartVNode, container)
      prevChildren[idxInOld] = undefined
      container.insertBefore(vnodeToMove.el, oldStartVNode.el)
    } else {
      // 使用 mount 函数挂载新节点，如果传入了最后一个参数，内部也是使用 insertBefore
      mount(newStartVNode, container, false, oldStartVNode.el)
    }
    newStartVNode = nextChildren[++newStartIdx]
  }
}

新增情况二

节点所在的双端优先满足了四种策略

vue diff 双端比较算法,Vue源码,vue.js,算法,前端,javascript

最终双端比较完成后结果
oldEndIdx 将比 oldStartIdx 的值要小，对 oldEndIdx 和 oldStartIdx 的值进行检查，如果在循环结束之后 oldEndIdx 的值小于 oldStartIdx 的值则说明新的 children 中存在还没有被处理的全新节点，这时我们应该调用 mount 函数将其挂载到容器元素中，观察上图可知，我们只需要把这些全新的节点添加到 oldStartIdx 索引所指向的节点之前即可

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // 省略...
}
if (oldEndIdx < oldStartIdx) {
  // 添加新节点
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    mount(nextChildren[i], container, false, oldStartVNode.el)
  }
}

删除节点

vue diff 双端比较算法,Vue源码,vue.js,算法,前端,javascript

在进行双端比较后
此时 newEndIdx 的值小于 newStartIdx 的值，所以循环将终止，但是通过上图可以发现，旧 children 中的 li-b 节点没有得到被处理的机会，我们应该将其移除才行，循环结束后，一旦满足条件 newEndIdx < newStartId 则说明有元素需要被移除

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // 省略...
}
if (oldEndIdx < oldStartIdx) {
  // 添加新节点
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    mount(nextChildren[i], container, false, oldStartVNode.el)
  }
} else if (newEndIdx < newStartIdx) {
  // 移除操作
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {
    container.removeChild(prevChildren[i].el)
  }
}

双端比较的优势

对于如下节点情况

vue diff 双端比较算法,Vue源码,vue.js,算法,前端,javascript

如果采用 React 根据相对位置的diff 方式来对上例进行更新，则会执行两次移动操作
- 首先会把 li-a 节点对应的真实 DOM 移动到 li-c 节点对应的真实 DOM 的后面
- 接着再把 li-b 节点所对应的真实 DOM 移动到 li-a 节点所对应真实 DOM 的后面，即：
如果采用 vue 的双端比较 diff
- 第一步：拿旧 children 中的 li-a 和新 children 中的 li-c 进行比对，由于二者 key 值不同，所以不可复用，什么都不做。
- 第二步：拿旧 children 中的 li-c 和新 children 中的 li-b 进行比对，不可复用，什么都不做。
- 第三步：拿旧 children 中的 li-a 和新 children 中的 li-b 进行比对，不可复用，什么都不做。
- 第四步：拿旧 children 中的 li-c 和新 children 中的 li-c 进行比对，此时，两个节点拥有相同的 key 值，可复用。