我让虚拟DOM的diff算法过程动起来了

去年写了一篇文章手写一个虚拟DOM库，彻底让你理解diff算法介绍虚拟DOM的patch过程和diff算法过程，当时使用的是双端diff算法，今年看到了Vue3使用的已经是快速diff算法，所以也想写一篇来记录一下，但是肯定已经有人写过了，所以就在想能不能有点不一样的，上次的文章主要是通过画图来一步步展示diff算法的每一种情况和过程，所以就在想能不能改成动画的形式，于是就有了这篇文章。当然目前的实现还是基于双端diff算法的，后续会补充上快速diff算法。

传送门：双端Diff算法动画演示。

界面就是这样的，左侧可以输入要比较的新旧VNode列表，然后点击启动按钮就会以动画的形式来展示从头到尾的过程，右侧是水平的三个列表，分别代表的是新旧的VNode列表，以及当前的真实DOM列表，DOM列表初始和旧的VNode列表一致，算法结束后会和新的VNode列表一致。

需要说明的是这个动画只包含diff算法的过程，不包含patch过程。

先来回顾一下双端diff算法的函数：

const diff = (el, oldChildren, newChildren) => {// 指针let oldStartIdx = 0let oldEndIdx = oldChildren.length - 1let newStartIdx = 0let newEndIdx = newChildren.length - 1// 节点let oldStartVNode = oldChildren[oldStartIdx]let oldEndVNode = oldChildren[oldEndIdx]let newStartVNode = newChildren[newStartIdx]let newEndVNode = newChildren[newEndIdx]while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {if (oldStartVNode === null) {oldStartVNode = oldChildren[++oldStartIdx]} else if (oldEndVNode === null) {oldEndVNode = oldChildren[--oldEndIdx]} else if (newStartVNode === null) {newStartVNode = oldChildren[++newStartIdx]} else if (newEndVNode === null) {newEndVNode = oldChildren[--newEndIdx]} else if (isSameNode(oldStartVNode, newStartVNode)) { // 头-头patchVNode(oldStartVNode, newStartVNode)// 更新指针oldStartVNode = oldChildren[++oldStartIdx]newStartVNode = newChildren[++newStartIdx]} else if (isSameNode(oldStartVNode, newEndVNode)) { // 头-尾patchVNode(oldStartVNode, newEndVNode)// 把oldStartVNode节点移动到最后el.insertBefore(oldStartVNode.el, oldEndVNode.el.nextSibling)// 更新指针oldStartVNode = oldChildren[++oldStartIdx]newEndVNode = newChildren[--newEndIdx]} else if (isSameNode(oldEndVNode, newStartVNode)) { // 尾-头patchVNode(oldEndVNode, newStartVNode)// 把oldEndVNode节点移动到oldStartVNode前el.insertBefore(oldEndVNode.el, oldStartVNode.el)// 更新指针oldEndVNode = oldChildren[--oldEndIdx]newStartVNode = newChildren[++newStartIdx]} else if (isSameNode(oldEndVNode, newEndVNode)) { // 尾-尾patchVNode(oldEndVNode, newEndVNode)// 更新指针oldEndVNode = oldChildren[--oldEndIdx]newEndVNode = newChildren[--newEndIdx]} else {let findIndex = findSameNode(oldChildren, newStartVNode)// newStartVNode在旧列表里不存在，那么是新节点，创建插入if (findIndex === -1) {el.insertBefore(createEl(newStartVNode), oldStartVNode.el)} else { // 在旧列表里存在，那么进行patch，并且移动到oldStartVNode前let oldVNode = oldChildren[findIndex]patchVNode(oldVNode, newStartVNode)el.insertBefore(oldVNode.el, oldStartVNode.el)// 将该VNode置为空oldChildren[findIndex] = nullnewStartVNode = newChildren[++newStartIdx]// 旧列表里存在新列表里没有的节点，需要删除if (oldStartIdx <= oldEndIdx) {for (let i = oldStartIdx; i <= oldEndIdx; i++) {removeEvent(oldChildren[i])oldChildren[i] && el.removeChild(oldChildren[i].el)} else if (newStartIdx <= newEndIdx) {let before = newChildren[newEndIdx + 1] ? newChildren[newEndIdx + 1].el : nullfor (let i = newStartIdx; i <= newEndIdx; i++) {el.insertBefore(createEl(newChildren[i]), before)

该函数具体的实现步骤可以参考之前的文章，本文就不再赘述。

我们想让这个diff过程动起来，首先要找到动画的对象都有哪些，从函数的参数开始看，首先oldChildren和 newChildren两个VNode列表是必不可少的，可以通过两个水平的列表表示，然后是四个指针，这是双端diff算法的关键，我们通过四个箭头来表示，指向当前所比较的节点，然后就开启循环了，循环中新旧VNode列表其实基本上是没啥变化的，我们实际操作的是VNode对应的真实DOM元素，包括patch打补丁、移动、删除、新增等等操作，所以我们再来个水平的列表表示当前的真实DOM列表，最开始肯定是和旧的VNode列表是对应的，通过diff算法一步步会变成和新的VNode列表对应。

再来回顾一下创建VNode对象的h函数：

export const h = (tag, data = {}, children) => {let text = ''let ellet key// 文本节点if (typeof children === 'string' || typeof children === 'number') {text = childrenchildren = undefined} else if (!Array.isArray(children)) {children = undefinedif (data && data.key) {key = data.keyreturn {tag, // 元素标签children, // 子元素text, // 文本节点的文本el, // 真实domkey,data

我们输入的VNode列表数据会使用h函数来创建成VNode对象，所以可以输入的最简单的结构如下：

tag: 'div',children: '文本节点的内容',data: {key: 'a'

输入的新旧VNode列表数据会保存在store中，可以通过如下方式获取到：

// 输入的旧VNode列表store.oldVNode// 输入的新VNode列表store.newVNode

接下来定义相关的变量：

// 指针列表const oldPointerList = ref([])const newPointerList = ref([])// 真实DOM节点列表const actNodeList = ref([])// 新旧节点列表const oldVNodeList = ref([])const newVNodeList = ref([])// 提示信息const info = ref('')

指针的移动动画可以使用css的transition属性来实现，只要修改指针元素的left值即可，真实DOM列表的移动动画可以使用Vue的列表过渡组件TransitionGroup来轻松实现，模板如下：

{{ item.name }}

{{ item.value }}

旧的VNode列表

{{ item ? item.children : '空' }}

新的VNode列表

{{ item.children }}

{{ info }}

{{ item.value }}

{{ item.name }}

真实DOM列表

{{ item.children }}

双端diff算法过程中是不会修改新的VNode列表的，但是旧的VNode列表是有可能被修改的，也就是当首尾比较没有找到可以复用的节点，但是通过直接在旧的VNode列表中搜索找到了，那么会移动该VNode对应的真实DOM，移动后该VNode其实就相当于已经被处理过了，但是该VNode的位置又是在当前指针的中间，不能直接被删除，所以只好置为空null，所以可以看到模板中有处理这种情况。

另外我们还创建了一个info元素用来展示提示的文字信息，作为动画的描述。

但是这样还是不够的，因为每个旧的VNode是有对应的真实DOM元素的，但是我们输入的只是一个普通的json数据，所以模板还需要新增一个列表，作为旧的VNode列表的关联节点，这个列表只要提供节点引用即可，不需要可见，所以把它的display设为none：

// 根据输入的旧VNode列表创建元素const _oldVNodeList = computed(() => {return JSON.parse(store.oldVNode)// 引用DOM元素const oldNode = ref(null)const oldNodeList = ref([])

{{ item.children }}

然后当我们点击启动按钮，就可以给我们的三个列表变量赋值了，并使用h函数创建新旧VNode对象，然后传递给打补丁的patch函数就可以开始进行比较更新实际的DOM元素了：

const start = () => {nextTick(() => {// 表示当前真实的DOM列表actNodeList.value = JSON.parse(store.oldVNode)// 表示旧的VNode列表oldVNodeList.value = JSON.parse(store.oldVNode)// 表示新的VNode列表newVNodeList.value = JSON.parse(store.newVNode)nextTick(() => {let oldVNode = h('div',{ key: 1 },JSON.parse(store.oldVNode).map((item, index) => {// 创建VNode对象let vnode = h(item.tag, item.data, item.children)// 关联真实的DOM元素vnode.el = oldNodeList.value[index]return vnode// 列表的父节点也需要关联真实的DOM元素oldVNode.el = oldNode.valuelet newVNode = h('div',{ key: 1 },JSON.parse(store.newVNode).map(item => {return h(item.tag, item.data, item.children)// 调用patch函数进行打补丁patch(oldVNode, newVNode)

可以看到我们输入的新旧VNode列表是作为一个节点的子节点的，这是因为只有当比较的两个节点都存在非文本节点的子节点时才需要使用diff算法来高效的更新他们的子节点，当patch函数运行完后你可以打开控制台查看隐藏的DOM列表，会发现是和新的VNode列表保持一致的，那么你可能要问，为什么不直接用这个列表来作为真实DOM列表呢，还要自己额外创建一个actNodeList列表，其实是可以，但是diff算法过程中是使用insertBefore等方法来移动真实DOM节点的，所以不好加过渡动画，只会看到节点瞬间换位置，不符合我们的动画需求。

到这里效果如下：

接下来我们先把指针搞出来，我们创建一个处理函数对象，这个对象上会挂载一些方法，用于在diff算法过程中调用，在函数中更新相应的变量。

const handles = {// 更新指针updatePointers(oldStartIdx, oldEndIdx, newStartIdx, newEndIdx) {oldPointerList.value = [name: 'oldStartIdx',value: oldStartIdx},name: 'oldEndIdx',value: oldEndIdxnewPointerList.value = [name: 'newStartIdx',value: newStartIdx},name: 'newEndIdx',value: newEndIdx},

然后我们就可以在diff函数中通过handles.updatePointers()更新指针了：

const diff = (el, oldChildren, newChildren) => {// 指针handles.updatePointers(oldStartIdx, oldEndIdx, newStartIdx, newEndIdx)

这样指针就出来了：

然后在while循环中会不断改变这四个指针，所以在循环中也需要更新：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {handles.updatePointers(oldStartIdx, oldEndIdx, newStartIdx, newEndIdx)

但是这样显然是不行的，为啥呢，因为循环也就一瞬间就结束了，而我们希望每次都能停留一段时间，很简单，我们写个等待函数：

const wAIt = t => {return new Promise(resolve => {setTimeout(resolve()},t || 3000

然后我们使用async/await语法，就可以轻松在循环中实现等待了：

const diff = async (el, oldChildren, newChildren) => {while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {handles.updatePointers(oldStartIdx, oldEndIdx, newStartIdx, newEndIdx)await wait()

接下来我们新增两个变量，来突出表示当前正在比较的两个VNode：

// 当前比较中的节点索引const currentCompareOldNodeIndex = ref(-1)const currentCompareNewNodeIndex = ref(-1)const handles = {// 更新当前比较节点updateCompareNodes(a, b) {currentCompareOldNodeIndex.value = acurrentCompareNewNodeIndex.value = b

{{ item ? item.children : '空' }}

{{ item.children }}

给当前比较中的节点添加一个类名，用来突出显示，接下来还是一样，需要在diff函数中调用该函数，但是，该怎么加呢：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {if // ...} else if (isSameNode(oldStartVNode, newStartVNode)) {oldStartVNode = oldChildren[++oldStartIdx]newStartVNode = newChildren[++newStartIdx]} else if (isSameNode(oldStartVNode, newEndVNode)) {oldStartVNode = oldChildren[++oldStartIdx]newEndVNode = newChildren[--newEndIdx]} else if (isSameNode(oldEndVNode, newStartVNode)) {oldEndVNode = oldChildren[--oldEndIdx]newStartVNode = newChildren[++newStartIdx]} else if (isSameNode(oldEndVNode, newEndVNode)) {oldEndVNode = oldChildren[--oldEndIdx]newEndVNode = newChildren[--newEndIdx]} else {newStartVNode = newChildren[++newStartIdx]

我们想表现出头尾比较的过程，其实就在这些if条件中，也就是要在每个if条件中停留一段时间，那么可以直接这样吗：

const isSameNode = async () => {handles.updateCompareNodes()await wait()if (await isSameNode(oldStartVNode, newStartVNode))

很遗憾，我尝试了不行，那么只能改写成其他形式了：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {let stop = falselet _isSameNode = falseif (oldStartVNode === null) {callbacks.updateInfo('')oldStartVNode = oldChildren[++oldStartIdx]stop = trueif (!stop) {callbacks.updateInfo('头-头比较')callbacks.updateCompareNodes(oldStartIdx, newStartIdx)_isSameNode = isSameNode(oldStartVNode, newStartVNode)if (_isSameNode) {callbacks.updateInfo('key值相同，可以复用，进行patch打补丁操作。新旧节点位置相同，不需要移动对应的真实DOM节点'await wait()if (!stop && _isSameNode) {oldStartVNode = oldChildren[++oldStartIdx]newStartVNode = newChildren[++newStartIdx]stop = true

我们使用一个变量来表示是否进入到了某个分支，然后把检查节点是否能复用的结果也保存到一个变量上，这样就可以通过不断检查这两个变量的值来判断是否需要进入到后续的比较分支中，这样比较的逻辑就不在if条件中了，就可以使用await了，同时我们还使用updateInfo增加了提示语：

const handles = {// 更新提示信息updateInfo(tip) {info.value = tip

接下来看一下节点的移动操作，当头（oldStartIdx对应的oldStartVNode节点）尾（newEndIdx对应的newEndVNode节点）比较发现可以复用时，在打完补丁后需要将oldStartVNode对应的真实DOM元素移动到oldEndVNode对应的真实DOM元素的位置，也就是插入到oldEndVNode对应的真实DOM的后面一个节点的前面：

if (!stop && _isSameNode) {// 头-尾patchVNode(oldStartVNode, newEndVNode)// 把oldStartVNode节点移动到最后el.insertBefore(oldStartVNode.el, oldEndVNode.el.nextSibling)// 更新指针oldStartVNode = oldChildren[++oldStartIdx]newEndVNode = newChildren[--newEndIdx]stop = true

那么我们可以在insertBefore方法移动完真实的DOM元素后紧接着调用一下我们模拟列表的移动节点的方法：

if (!stop && _isSameNode) {el.insertBefore(oldStartVNode.el, oldEndVNode.el.nextSibling)callbacks.moveNode(oldStartIdx, oldEndIdx + 1)

我们要操作的实际上是代表真实DOM节点的actNodeList列表，那么关键是要找到具体是哪个，首先头尾的四个节点指针它们表示的是在新旧VNode列表中的位置，所以我们可以根据oldStartIdx和oldEndIdx获取到oldVNodeList中对应位置的VNode，然后通过key值在actNodeList列表中找到对应的节点，进行移动、删除、插入等操作：

const handles = {// 移动节点moveNode(oldIndex, newIndex) {let oldVNode = oldVNodeList.value[oldIndex]let newVNode = oldVNodeList.value[newIndex]let fromIndex = findIndex(oldVNode)let toIndex = findIndex(newVNode)actNodeList.value[fromIndex] = '#'actNodeList.value.splice(toIndex, 0, oldVNode)actNodeList.value = actNodeList.value.filter(item => {return item !== '#'const findIndex = (vnode) => {return !vnode: actNodeList.value.findIndex(item => {return item && item.data.key === vnode.data.key

其他的插入节点和删除节点也是类似的：

插入节点：

const handles = {// 插入节点insertNode(newVNode, index, inNewVNode) {let node = {data: newVNode.data,children: newVNode.textlet targetIndex = 0if (index === -1) {actNodeList.value.push(node)} else {if (inNewVNode) {let vNode = newVNodeList.value[index]targetIndex = findIndex(vNode)} else {let vNode = oldVNodeList.value[index]targetIndex = findIndex(vNode)actNodeList.value.splice(targetIndex, 0, node)

删除节点：

const handles = {// 删除节点removeChild(index) {let vNode = oldVNodeList.value[index]let targetIndex = findIndex(vNode)actNodeList.value.splice(targetIndex, 1)

这些方法在diff函数中的执行位置其实就是执行insertBefore、removeChild方法的地方，具体可以本文源码，这里就不在具体介绍了。

另外还可以凸显一下已经结束比较的元素、即将被添加的元素、即将被删除的元素等等，最终效果：

时间原因，目前只实现了双端diff算法的效果，后续会增加上快速diff算法的动画过程，有兴趣的可以点个关注哟~

仓库：https://Github.com/wanglin2/VNode_visualization。