关于前端:我让虚拟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 = 0
  let oldEndIdx = oldChildren.length - 1
  let newStartIdx = 0
  let 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] = null
      }
      newStartVNode = 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 : null
    for (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 el
  let key
  // 文本节点
  if (typeof children === 'string' || typeof children === 'number') {
    text = children
    children = undefined
  } else if (!Array.isArray(children)) {children = undefined}
  if (data && data.key) {key = data.key}
  return {
    tag, // 元素标签
    children, // 子元素
    text, // 文本节点的文本
    el, // 实在 dom
    key,
    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 来轻松实现，模板如下：

<div class="playground">
  <!-- 指针 -->
  <div class="pointer">
    <div
         class="pointerItem"
         v-for="item in oldPointerList"
         :key="item.name"
         :style="{left: item.value * 120 +'px'}"
         >
      <div class="pointerItemName">{{item.name}}</div>
      <div class="pointerItemValue">{{item.value}}</div>
      <img src="../assets/ 箭头_向下.svg" alt="" />
    </div>
  </div>
  <div class="nodeListBox">
    <!-- 旧节点列表 -->
    <div class="nodeList">
      <div class="name" v-if="oldVNodeList.length > 0"> 旧的 VNode 列表 </div>
      <div class="nodes">
        <TransitionGroup name="list">
          <div
               class="nodeWrap"
               v-for="(item, index) in oldVNodeList"
               :key="item ? item.data.key : index"
               >
            <div class="node">{{item ? item.children : '空'}}</div>
          </div>
        </TransitionGroup>
      </div>
    </div>
    <!-- 新节点列表 -->
    <div class="nodeList">
      <div class="name" v-if="newVNodeList.length > 0"> 新的 VNode 列表 </div>
      <div class="nodes">
        <TransitionGroup name="list">
          <div
               class="nodeWrap"
               v-for="(item, index) in newVNodeList"
               :key="item.data.key"
               >
            <div class="node">{{item.children}}</div>
          </div>
        </TransitionGroup>
      </div>
    </div>
    <!-- 提示信息 -->
    <div class="info">{{info}}</div>
  </div>
  <!-- 指针 -->
  <div class="pointer">
    <div
         class="pointerItem"
         v-for="item in newPointerList"
         :key="item.name"
         :style="{left: item.value * 120 +'px'}"
         >
      <img src="../assets/ 箭头_向上.svg" alt="" />
      <div class="pointerItemValue">{{item.value}}</div>
      <div class="pointerItemName">{{item.name}}</div>
    </div>
  </div>
  <!-- 实在 DOM 列表 -->
  <div class="nodeList act" v-if="actNodeList.length > 0">
    <div class="name"> 实在 DOM 列表 </div>
    <div class="nodes">
      <TransitionGroup name="list">
        <div
             class="nodeWrap"
             v-for="item in actNodeList"
             :key="item.data.key"
             >
          <div class="node">{{item.children}}</div>
        </div>
      </TransitionGroup>
    </div>
  </div>
</div>

双端 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([])

<!-- 暗藏 -->
<div class="hide">
  <div class="nodes" ref="oldNode">
    <div
         v-for="(item, index) in _oldVNodeList"
         :key="index"
         ref="oldNodeList"
         >
      {{item.children}}
    </div>
  </div>
</div>

而后当咱们点击启动按钮，就能够给咱们的三个列表变量赋值了，并应用 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.value
      let 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: oldEndIdx
      }
    ]
    newPointerList.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 = a
    currentCompareNewNodeIndex.value = b
  }
}

<div
     class="nodeWrap"
     v-for="(item, index) in oldVNodeList"
     :key="item ? item.data.key : index"
     :class="{current: currentCompareOldNodeIndex === index,}"
     >
  <div class="node">{{item ? item.children : '空'}}</div>
</div>
<div
     class="nodeWrap"
     v-for="(item, index) in newVNodeList"
     :key="item.data.key"
     :class="{current: currentCompareNewNodeIndex === index,}"
     >
  <div class="node">{{item.children}}</div>
</div>

给以后比拟中的节点增加一个类名，用来突出显示，接下来还是一样，须要在 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 = false
  let _isSameNode = false
  if (oldStartVNode === null) {callbacks.updateInfo('')
    oldStartVNode = oldChildren[++oldStartIdx]
    stop = true
  }
  // ...
  if (!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
    ? -1
    : 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.text
    }
    let targetIndex = 0
    if (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。