Vue进阶 Diff算法详解

前端LeBron

发布于 2021-12-08 16:30:45

5890

发布于 2021-12-08 16:30:45

文章被收录于专栏：前端LeBron

原创不易，未经作者允许禁止转载！！

一、虚拟DOM

什么是虚拟DOM？

虚拟DOM就是把真实DOM树的结构和信息抽象出来，以对象的形式模拟树形结构，如下：

真实DOM:

<div>
    <p>Hello World</p>
</div>

对应的虚拟DOM就是：

let vnode = {
    tag: 'div',
    children:[ {tag:'p', text:'Hello World'}]
}

为什么需要虚拟DOM？

渲染真实DOM会有一定的开销，如果每次修改数据都进行真实DOM渲染，都会引起DOM树的重绘和重排，性能开销很大。那么有没有可能只修改一小部分数据而不渲染整个DOM呢？虚拟DOM和Diff算法可以实现。

怎么实现？

先根据真实DOM生成一颗虚拟DOM树
当某个DOM节点数据发生改变时，生成一个新的Vnode
新的Vnode和旧的oldVnode进行对比
通过patch函数一边比对一边给真实DOM打补丁或者创建Vnode、移除oldVnode等

有什么不一样？

真实DOM操作为一个属性一个属性去修改，开销较大。
虚拟DOM直接修改整个DOM节点再替换真实DOM

还有什么好处？

Vue的虚拟DOM数据更新机制是异步更新队列，并不是数据变更马上更新DOM，而是被推进一个数据更新异步队列统一更新。想要马上拿到DOM更新后DOM信息？有个API叫 Vue.nextTick

二、 Diff算法

传统Diff算法

遍历两棵树中的每一个节点，每两个节点之间都要做一次比较。
比如 a->e 、a->d 、a->b、a->c、a->a

遍历完成的时间复杂度达到了O(n^2)
对比完差异后还要计算最小转换方式，实现后复杂度来到了O(n^3)

img

Vue优化的Diff算法

Vue的diff算法只会比较同层级的元素，不进行跨层级比较

img

三、 Vue中的Diff算法实现

Vnode分类

EmptyVNode: 没有内容的注释节点
TextVNode: 文本节点
ElementVNode: 普通元素节点
ComponentVNode: 组件节点
CloneVNode: 克隆节点，可以是以上任意类型的节点，唯一的区别在于isCloned属性为true

Patch函数

patch函数接收以下参数：

oldVnode：旧的虚拟节点
Vnode：新的虚拟节点
hydrating：是否要和真实DOM混合
removeOnly：特殊的flag，用于 transition-group

处理流程大致分为以下步骤：

vnode不存在，oldVnode存在时，移除oldVnode
vnode存在，oldVnode不存在时，创建vnode
vnode和oldVnode都存在时
1. 如果vnode和oldVnode是同一个节点（通过sameVnode函数对比后续详解），通过patchVnode进行后续比对工作
2. 如果vnode和oldVnode不是同一个节点，那么根据vnode创建新的元素并挂载至oldVnode父元素下。如果组件根节点被替换，遍历更新父节点element。然后移除旧节点。如果oldVnode是服务端渲染元素节点，需要用hydrate函数将虚拟dom和真是dom进行映射

源码如下，已写好注释便于阅读

return function patch(oldVnode, vnode, hydrating, removeOnly) {
    // 如果vnode不存在，但是oldVnode存在，移除oldVnode
    if (isUndef(vnode)) {
      if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
      return
    }

    let isInitialPatch = false
    const insertedVnodeQueue = []

    // 如果oldVnode不存在，但是vnode存在时，创建vnode
    if (isUndef(oldVnode)) {
      isInitialPatch = true
      createElm(vnode, insertedVnodeQueue)
    } else {
      // 剩余情况为vnode和oldVnode都存在

      // 判断是否为真实DOM元素
      const isRealElement = isDef(oldVnode.nodeType)
      if (!isRealElement && sameVnode(oldVnode, vnode)) {
        // 如果vnode和oldVnode是同一个（通过sameVnode函数进行比对  后续详解）
        // 受用patchVnode函数进行后续比对工作 （函数后续详解）
        patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly)
      } else {
        // vnode和oldVnode不是同一个的情况
        if (isRealElement) {
          // 如果存在真实的节点，存在data-server-render属性
          if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
            // 当旧的Vnode是服务端渲染元素，hydrating记为true
            oldVnode.removeAttribute(SSR_ATTR)
            hydrating = true
          }
          // 需要用hydrate函数将虚拟DOM和真实DOM进行映射
          if (isTrue(hydrating)) {
            // 需要合并到真实DOM上
            if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
              // 调用insert钩子
              invokeInsertHook(vnode, insertedVnodeQueue, true)
              return oldVnode
            } else if (process.env.NODE_ENV !== 'production') {
              warn(
                'The client-side rendered virtual DOM tree is not matching ' +
                'server-rendered content. This is likely caused by incorrect ' +
                'HTML markup, for example nesting block-level elements inside ' +
                '<p>, or missing <tbody>. Bailing hydration and performing ' +
                'full client-side render.'
              )
            }
          }
          // 如果不是服务端渲染元素或者合并到真实DOM失败，则创建一个空的Vnode节点去替换它
          oldVnode = emptyNodeAt(oldVnode)
        }

        // 获取oldVnode父节点
        const oldElm = oldVnode.elm
        const parentElm = nodeOps.parentNode(oldElm)

        // 根据vnode创建一个真实DOM节点并挂载至oldVnode的父节点下
        createElm(
          vnode,
          insertedVnodeQueue,
          oldElm._leaveCb ? null : parentElm,
          nodeOps.nextSibling(oldElm)
        )

        // 如果组件根节点被替换，遍历更新父节点Element
        if (isDef(vnode.parent)) {
          let ancestor = vnode.parent
          const patchable = isPatchable(vnode)
          while (ancestor) {
            for (let i = 0; i < cbs.destroy.length; ++i) {
              cbs.destroy[i](ancestor)
            }
            ancestor.elm = vnode.elm
            if (patchable) {
              for (let i = 0; i < cbs.create.length; ++i) {
                cbs.create[i](emptyNode, ancestor)
              }
              // #6513
              // invoke insert hooks that may have been merged by create hooks.
              // e.g. for directives that uses the "inserted" hook.
              const insert = ancestor.data.hook.insert
              if (insert.merged) {
                // start at index 1 to avoid re-invoking component mounted hook
                for (let i = 1; i < insert.fns.length; i++) {
                  insert.fns[i]()
                }
              }
            } else {
              registerRef(ancestor)
            }
            ancestor = ancestor.parent
          }
        }

        // 销毁旧节点
        if (isDef(parentElm)) {
          // 移除老节点
          removeVnodes(parentElm, [oldVnode], 0, 0)
        } else if (isDef(oldVnode.tag)) {
          // 调用destroy钩子
          invokeDestroyHook(oldVnode)
        }
      }
    }
    // 调用insert钩子并返回节点
    invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
    return vnode.elm
  }

sameVnode函数

Vue怎么判断是不是同一个节点？流程如下：

判断Key值是否一样
tag的值是否一样
isComment，这个不用太关注。
数据一样
sameInputType()，专门对表单输入项进行判断的：input一样但是里面的type不一样算不同的inputType

从这里可以看出key对diff算法的辅助作用，可以快速定位是否为同一个元素，必须保证唯一性。
如果你用的是index作为key，每次打乱顺序key都会改变，导致这种判断失效，降低了Diff的效率。
因此，用好key也是Vue性能优化的一种方式。

源码如下：

function sameVnode(a, b) {
  return (
    a.key === b.key && (
      (
        a.tag === b.tag &&
        a.isComment === b.isComment &&
        isDef(a.data) === isDef(b.data) &&
        sameInputType(a, b)
      ) || (
        isTrue(a.isAsyncPlaceholder) &&
        a.asyncFactory === b.asyncFactory &&
        isUndef(b.asyncFactory.error)
      )
    )
  )
}

patchVnode函数

前置条件vnode和oldVnode是同一个节点执行流程：

如果oldVnode和vnode引用一致，可以认为没有变化，return
如果oldVnode的isAsyncPlaceholder属性为true，跳过检查异步组件，return
如果oldVnode跟vnode都是静态节点，且具有相同的key，同时vnode是克隆节点或者v-once指令控制的节点时，只需要把oldVnode.elm和oldVnode.child都复制到vnode上，也不用再有其他操作，return
如果vnode不是文本节或注释节点
1. 如果vnode和oldVnode都有子节点并且两者子节点不一致时，就调用updateChildren更新子节点
2. 如果只有vnode有自子节点，则调用addVnodes创建子节点
3. 如果只有oldVnode有子节点，则调用removeVnodes把这些子节点都删除
4. 如果vnode文本为undefined，则清空vnode.elm文本
如果vnode是文本节点但是和oldVnode文本内容不同，只需更新文本。

源代码如下，已写好注释便于阅读

function patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly) {

    // 如果新老节点引用一致，直接返回。
    if (oldVnode === vnode) {
      return
    }

    const elm = vnode.elm = oldVnode.elm

    // 如果oldVnode的isAsyncPlaceholder属性为true，跳过检查异步组件
    if (isTrue(oldVnode.isAsyncPlaceholder)) {
      if (isDef(vnode.asyncFactory.resolved)) {
        hydrate(oldVnode.elm, vnode, insertedVnodeQueue)
      } else {
        vnode.isAsyncPlaceholder = true
      }
      return
    }

    // 如果新旧都是静态节点，vnode的key也相同
    // 新vnode是克隆所得或新vnode有 v-once属性
    // 则进行赋值，然后返回。vnode的componentInstance 保持不变
    if (isTrue(vnode.isStatic) &&
      isTrue(oldVnode.isStatic) &&
      vnode.key === oldVnode.key &&
      (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
    ) {
      vnode.componentInstance = oldVnode.componentInstance
      return
    }

    let i
    const data = vnode.data
    // 执行data.hook.prepatch 钩子
    if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
      i(oldVnode, vnode)
    }

    // 获取子元素列表
    const oldCh = oldVnode.children
    const ch = vnode.children

    if (isDef(data) && isPatchable(vnode)) {
      // 遍历调用 cbs.update 钩子函数，更新oldVnode所有属性
      // 包括attrs、class、domProps、events、style、ref、directives
      for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
      // 执行data.hook.update 钩子
      if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)
    }
    // Vnode 的 text选项为undefined
    if (isUndef(vnode.text)) {
      if (isDef(oldCh) && isDef(ch)) {
        //新老节点的children不同，执行updateChildren方法
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
      } else if (isDef(ch)) {
        // oldVnode children不存在 执行 addVnodes方法
        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
      } else if (isDef(oldCh)) {
        // vnode不存在执行removeVnodes方法
        removeVnodes(elm, oldCh, 0, oldCh.length - 1)
      } else if (isDef(oldVnode.text)) {
        // 新旧节点都是undefined，且老节点存在text，清空文本。
        nodeOps.setTextContent(elm, '')
      }
    } else if (oldVnode.text !== vnode.text) {
      // 新老节点文本内容不同，更新文本
      nodeOps.setTextContent(elm, vnode.text)
    }
    if (isDef(data)) {
      // 执行data.hook.postpatch钩子，至此 patch完成
      if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
    }
  }

updateChildren函数

重点！！！前置条件：vnode和oldVnode的children不相等整体的执行思路如下：

vnode头对比oldVnode头
vnode尾对比oldVnode尾
vnode头对比oldVnode尾
vnode尾对比oldVnode头
- 只要符合一种情况就进行patch，移动节点，移动下标等操作
都不对再在oldChild中找一个key和newStart相同的节点
- 如果是相同节点，进行patch 然后将这个节点插入到oldStart之前，newStart下标继续移动
- 如果不是相同节点，需要执行createElm创建新元素
- 找不到，新建一个。
- 找到，获取这个节点，判断它和newStartVnode是不是同一个节点

为什么会有头对尾、尾对头的操作？

可以快速检测出reverse操作，加快diff效率。

源码如下已写好注释便于阅读：

 function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {

    // 定义变量
    let oldStartIdx = 0  // 老节点Child头下标
    let newStartIdx = 0  // 新节点Child头下标
    let oldEndIdx = oldCh.length - 1  // 老节点Child尾下标
    let oldStartVnode = oldCh[0]      // 老节点Child头结点
    let oldEndVnode = oldCh[oldEndIdx] // 老节点Child尾结点
    let newEndIdx = newCh.length - 1   // 新节点Child尾下标
    let newStartVnode = newCh[0]       // 新节点Child头结点
    let newEndVnode = newCh[newEndIdx]  // 新节点Child尾结点
    let oldKeyToIdx, idxInOld, vnodeToMove, refElm  

    // removeOnly is a special flag used only by <transition-group>
    // to ensure removed elements stay in correct relative positions
    // during leaving transitions
    const canMove = !removeOnly

    if (process.env.NODE_ENV !== 'production') {
      checkDuplicateKeys(newCh)
    }

    // 定义循环
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      // 存在检测
      if (isUndef(oldStartVnode)) {
        oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
      } else if (isUndef(oldEndVnode)) {
        oldEndVnode = oldCh[--oldEndIdx]

      // 如果老结点Child头和新节点Child头是同一个节点
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        // patch差异
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
        // patch完成  移动节点位置  继续比对下一个节点
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]

      // 如果老结点Child尾和新节点Child尾是同一个节点
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // patch差异
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
        // patch完成  移动节点位置 继续比对下一个节点
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]

      // 如果老结点Child头和新节点Child尾是同一个节点
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
         // patch差异
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
        // 把oldStart节点放到oldEnd节点后面
        canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
        // patch完成  移动节点位置 继续比对下一个节点
        oldStartVnode = oldCh[++oldStartIdx]
        newEndVnode = newCh[--newEndIdx]
      // 如果老结点Child尾和新节点Child头是同一个节点
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
         // patch差异
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
        // 把oldEnd节点放到oldStart节点前面
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        // patch完成  移动节点位置 继续比对下一个节点
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        // 如果没有相同的Key，执行createElm方法创建元素
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        idxInOld = isDef(newStartVnode.key) ?
          oldKeyToIdx[newStartVnode.key] :
          findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
        if (isUndef(idxInOld)) { // New element
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        } else {
          // 有相同的Key，判断这两个节点是否为sameNode
          vnodeToMove = oldCh[idxInOld]
          if (sameVnode(vnodeToMove, newStartVnode)) {
            // 如果是相同节点，进行patch  然后举将oldStart插入到oldStart之前，newStart下标继续移动
            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)
            oldCh[idxInOld] = undefined
            canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
          } else {
            // 如果不是相同节点，需要执行createElm创建新元素
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
          }
        }
        newStartVnode = newCh[++newStartIdx]
      }
    }

    // oldStartIdx > oldEndIdx说明oldChild先遍历完，使用addVnode方法添加newStartIdx指向的节点到newEndIdx的节点
    if (oldStartIdx > oldEndIdx) {
      refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
      addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
    } else if (newStartIdx > newEndIdx) {
      // 如果newStartIdx > newEndIdx说明newChild先遍历完，remove掉oldChild未遍历完的节点
      removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
  }

四、总结

正确使用key，可以快速执行sameVnode比对，加速Diff效率，可以作为性能优化的一个点。
DIff只做同级比较，使用sameVnode函数比对，文本节点直接替换文本内容。
子元素列表的Diff，进行头对头、尾对尾、头对尾等系列比较，直到遍历完两个元素的子元素列表。
- 或一个列表先遍历完了，直接addVnode / removeVnode。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-05-12，如有侵权请联系 cloudcommunity@tencent.com 删除

node.js