关于前端:Vue进阶-Diff算法详解

写作不易，未经作者容许禁止以任何模式转载！
如果感觉文章不错，欢送关注、点赞和分享！
博客原文链接：Vue 进阶 Diff 算法详解

什么是虚构 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

遍历两棵树中的每一个节点，每两个节点之间都要做一次比拟。

比方 a->e、a->d、a->b、a->c、a->a

遍历实现的工夫复杂度达到了 O(n^2)
比照完差别后还要计算最小转换形式，实现后复杂度来到了 O(n^3)

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

EmptyVNode: 没有内容的正文节点
TextVNode: 文本节点
ElementVNode: 一般元素节点
ComponentVNode: 组件节点
CloneVNode: 克隆节点，能够是以上任意类型的节点，惟一的区别在于 isCloned 属性为 true

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
  }

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)
      )
    )
  )
}

前置条件 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)
    }
  }

重点！！！

前置条件：vnode 和 oldVnode 的 children 不相等

整体的执行思路如下：

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

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

能够疾速检测出 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。

原文链接：Vue 进阶 Diff 算法详解 | 学习笔记

掘金：前端 LeBron

知乎：前端 LeBron

继续分享技术博文，关注微信公众号👇🏻

关于前端:Vue进阶-Diff算法详解

一、虚构 DOM

二、Diff 算法

传统 Diff 算法

Vue 优化的 Diff 算法

三、Vue 中的 Diff 算法实现

Vnode 分类

Patch 函数

sameVnode 函数

patchVnode 函数

updateChildren 函数

四、总结