关于前端:我让虚拟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。

关于前端:我让虚拟DOM的diff算法过程动起来了

评论

发表回复取消回复

更多文章

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

深入解析：基于Delta的线性数据结构模型，打造高效富文本编辑器

轻松管理社交媒体：使用Automa插件实现一键拉黑功能

关于前端:我让虚拟DOM的diff算法过程动起来了

评论

发表回复 取消回复

更多文章

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

深入解析：基于Delta的线性数据结构模型，打造高效富文本编辑器

轻松管理社交媒体：使用Automa插件实现一键拉黑功能

发表回复取消回复