vue中的diff算法概念

虽然点进来的大家应该都知道diff算法是什么,不过按照流程还是要简单说一下,按我个人的理解,Vue的diff算法是对新旧两条虚拟DOM进行逐层比较并更新真实DOM

diff算法是平级比较,不考虑跨级的情况,采用深度递归+双指针的方式进行比较

  • 先比较是否是相同节点
  • 如果是相同节点比较属性(key、tag、input->type),并复用老节点
  • 然后比较子节点,以先对比两边,再交叉对比,再乱序对比的方式进行比较(头头、尾尾、头尾、尾头、乱序)

vue中diff算法的实现

工具函数sameVnode

在开始前,需要简单了解下该函数↓↓↓↓↓↓,函数作用是通过tag等内容判断两个vnode是否相同,该函数在diff算法的判断中起重要作用

/**
 * 函数作用:通过tag等内容判断两个vnode是否相同
 * 细节:通过两个值的key进行对比,如果key相同,继续通过标签、isComment、data、input类型等判断是否相同,还会判断异步组件的asyncFactory是否相同
 **/
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)
      )
    )
  )
}

根据节点是否相同初步判断:patch函数

此函数可以说的diff算法的入口函数了,当数据发生改变时,defineProperty => get会调用Depnotify方法调用Watcher进行更新,当每次走get调用_update的时候,都会走patch函数,更新真实DOM

在调用patch函数时,会将新老vnode都传入oldVnodeVnode(不考虑服务器渲染)

无新节点时:代表组件被删除,调用invokeDestroyHook卸载组件
无老节点:代表要创建的是一个新组件,无需算法比较直接createElm创建新组件
有老节点,有新节点:通过sameVnode比对组件

老节点、新节点比对为true:调用patchVnode对比与更新
老节点、新节点比对为false:抛弃旧节点,调用createElm生成新的

function patch(oldVnode, vnode, hydrating, removeOnly) {
    // 如果没有vnode,但有oldVnode,则调用销毁钩子 卸载组件
    if (isUndef(vnode)) {
      if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
      return
    }

    let isInitialPatch = false
    const insertedVnodeQueue = []

    // 如果没有老节点 代表是新组件,直接创建
    if (isUndef(oldVnode)) {
      // empty mount (likely as component), create new root element
      isInitialPatch = true
      createElm(vnode, insertedVnodeQueue)
    } else {
      // isRealElement:
      // nodeType是真实DOM上的一个属性,如果nodeType存在,代表这是一个真实节点
      // 当Vue初次渲染或执行$moudnt(el)时,首次进入该函数的oldVnode就是el
      const isRealElement = isDef(oldVnode.nodeType)
      // 函数sameVnode: 判断新旧节点是否相同
      if (!isRealElement && sameVnode(oldVnode, vnode)) {
        // 新旧节点相同,走patchVnode
        patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
      } else {
          // 服务端渲染相关代码...
          oldVnode = emptyNodeAt(oldVnode)

        /**
         * 此处往下为新旧节点不同(更新)的操作过程
         */
        // 获取旧节点oldVnode对应的父级真实DOM节点
        const oldElm = oldVnode.elm
        const parentElm = nodeOps.parentNode(oldElm)

        // 创建并插入节点
        createElm(
          vnode,
          insertedVnodeQueue,
          // extremely rare edge case: do not insert if old element is in a
          // leaving transition. Only happens when combining transition +
          // keep-alive + HOCs. (#4590)
          oldElm._leaveCb ? null : parentElm,
          nodeOps.nextSibling(oldElm)
        )

        // // 递归 更新父的占位符
        // update parent placeholder node element, recursively
        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
          }
        }

        // 销毁旧节点
        // destroy old node
        if (isDef(parentElm)) {
          removeVnodes([oldVnode], 0, 0)
        } else if (isDef(oldVnode.tag)) {
          invokeDestroyHook(oldVnode)
        }
    }
}

更新+比对子节点 patchVnode

该函数是递归调用updateChildren的入口,除了比对子节点以外,还会将老节点上的东西更新到新节点中,在updateChildren函数中,更新节点调用的就是该方法

该方法中比对子节点的逻辑:

新节点是文本节点:走setTextContent,更新文本内容
新节点有子节点

新节点和老节点都有子节点:如果子集完全一致不更新,不一致走updateChildren比较
只有新节点有子节点:不需要比较,直接将新节点插入到elm(父dom)下addVnodes
只有老节点有子节点:不需要比较,删除所有子节点removeVnodes
老节点是文本节点:走setTextContent清空文本

function patchVnode(
    oldVnode,
    vnode,
    insertedVnodeQueue,
    ownerArray,
    index,
    removeOnly
  ) {
    if (oldVnode === vnode) {
      return
    }
    if (isDef(vnode.elm) && isDef(ownerArray)) {
      // clone reused vnode
      vnode = ownerArray[index] = cloneVNode(vnode)
    }

    // 让新的vnode绑定老vnode所绑定的真实dom(elm)
    const elm = vnode.elm = oldVnode.elm

    // 异步处理
    if (isTrue(oldVnode.isAsyncPlaceholder)) {
      if (isDef(vnode.asyncFactory.resolved)) {
        hydrate(oldVnode.elm, vnode, insertedVnodeQueue)
      } else {
        vnode.isAsyncPlaceholder = true
      }
      return
    }

    // reuse element for static trees.
    // note we only do this if the vnode is cloned - if the new node is not cloned it means the render functions have been reset by the hot-reload-api and we need to do a proper re-render.
    // 注意,我们只在vnode被克隆时才这样做——如果新节点没有被克隆,这意味着渲染函数已经被热重新加载api重置,我们需要进行适当的重新渲染。
    // 静态节点或者once的话,不执行
    if (isTrue(vnode.isStatic) &&
      isTrue(oldVnode.isStatic) &&
      vnode.key === oldVnode.key &&
      (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
    ) {
      vnode.componentInstance = oldVnode.componentInstance
      return
    }

    /**
     * 此处调用了prepatch函数
     * 只有组件才会有该函数
     * prepatch函数创建位置:create-component.js
     * prepatch函数内部调用了updateChildComponent方法(lifecycle.js)
     * 最终更新了组件实例(oldVnode.componentInstance)中的一系列属性,并将其放在vnode.componentInstance上
     * (在内部会调用$forceUpdate())
     */
    let i
    const data = vnode.data
    if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
      i(oldVnode, vnode)
    }

    const oldCh = oldVnode.children
    const ch = vnode.children

    // 调用update 钩子函数更新
    if (isDef(data) && isPatchable(vnode)) {
      for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
      if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)
    }

    // 如果新节点不是文本或注释节点
    if (isUndef(vnode.text)) {
      if (isDef(oldCh) && isDef(ch)) { // 新老节点都有子节点
        // 新老节点的子节点不完全一直,调用updateChildren(diff算法)
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
      } else if (isDef(ch)) { // 只有新节点有子节点
        // 如果老节点是文本节点、清空文本
        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
        // addVnodes:将ch批量插入到elm下
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
      } else if (isDef(oldCh)) { // 只有老节点有子节点
        // 删除所有子节点
        removeVnodes(oldCh, 0, oldCh.length - 1)
      } else if (isDef(oldVnode.text)) { // 新老节点都没有子节点,但老节点是文本节点时
        nodeOps.setTextContent(elm, '') // => elm.text = ''
      }
    } else if (oldVnode.text !== vnode.text) { // 新节点是文本节点 && (新老节点文本不同||老节点不是文本节点)
      nodeOps.setTextContent(elm, vnode.text) // => elm.text = vnode.text
    }
    // 如果有postpatch,执行postpatch钩子函数,组件自定义钩子函数
    if (isDef(data)) {
      if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
    }
}

diff算法

核心方法 updateChildren

在调用函数updateChildren的传参,其中两个参数是新老元素的children

oldCh
newCh

创建变量

然后分别获取两个数组的开头、结尾的元素和索引

// 老元素 children list 相关
let oldStartIdx = 0 // 索引-头
let oldEndIdx = oldCh.length - 1 // 索引-尾
let oldStartVnode = oldCh[0] // 元素-头
let oldEndVnode = oldCh[oldEndIdx] // 元素-尾

// 新元素 children list 相关
let newStartIdx = 0 // 索引-头
let newEndIdx = newCh.length - 1 // 索引-尾
let newStartVnode = newCh[0] // 元素-头
let newEndVnode = newCh[newEndIdx] // 元素-尾

进入循环

然后通过while语句,循环计算:

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {...}
// while (老元素开头索引 <= 老元素结尾索引 && 新元素开头索引 <= 新元素结尾索引) {...}

在循环中,采用了双指针的方式同时处理新节点和老节点,有一方的循环完成,就结束循环

空数据跳过

首先,碰到空数据跳过,用于兼容后边说的乱序对比

while (...) {
    if (isUndef(oldStartVnode)) {
        oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
    } else if (isUndef(oldEndVnode)) {
        oldEndVnode = oldCh[--oldEndIdx]
    } else if (...){
        ...
    }
}

顺序对比

然后,通过上边说的sameVnode函数对比新老节点是否相同,如果相同

  1. 执行patchVnode函数(上边说过的函数)进行递归处理的同时更新新节点
  2. 更新对比的两个节点的vnode和索引

在下图这块代码中,vue使用了4种不同的方式进行对比,分别是

新老节点的头部与头部对比
新老节点的尾部与尾部对比
老节点的头部与新节点的尾部对比
老节点的尾部与新节点的头部对比

先看代码,下边会说明四种对比的方式

// 接上边代码块
while (...) {
    ...
    else if (sameVnode(oldStartVnode, newStartVnode)) { // 新老节点相同 --- 头头比较:老头<->新头
        // 走patchVnode(递归),进行新老节点更替
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
        } else if (sameVnode(oldEndVnode, newEndVnode)) { // 新老节点相同 --- 尾尾比较:老尾<->新尾
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldStartVnode, newEndVnode)) { // 新老节点相同 --- 头尾比较:老头<->新尾
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
        oldStartVnode = oldCh[++oldStartIdx]
        newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldEndVnode, newStartVnode)) { // 新老节点相同 --- 尾头比较:老尾<->新头
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
    } else {
        ...
    }
}

新老节点的头部与头部对比

改变前例1
newStartIdx:0newEndIdx:3
ABCD
ABCD
oldStartIdx:0oldEndIdx:3

首次进入循环,新老节点的头部与头部对比是根据newStartIdxoldStartIdx进行对比,如果二者相同,调用patchVnode后将newStartIdxoldStartIdx分别设置成1,并更新oldStartVnode,newStartVnode

改变后例1
oldStartIdx:1oldEndIdx:3
ABCD
ABCD
newStartIdx:1newEndIdx:3

新老节点的尾部与尾部对比

改变前例2
oldStartIdx:0oldEndIdx:3
ABCD
ABCD
newStartIdx:0newEndIdx:3

和头部对比思路相同,将newEndIdxoldEndIdx进行对比,如果二者相同,调用patchVnode后将newEndIdxoldEndIdx分别设置成2,并更新oldEndVnode,newEndVnode

改变后例2
oldStartIdx:0oldEndIdx:2
ABCD
ABCD
newStartIdx:0newEndIdx:2

老节点的头部与新节点的尾部对比

改变前例3
oldStartIdx:0oldEndIdx:3
DABC
ABCD
newStartIdx:0newEndIdx:3

在本次对比中,会将oldStartIdxnewEndIdx进行对比,如果二者相同,调用patchVnode,然后调用DOM原生方法insertBeforeoldStartVnode对应的真实节点放在oldEndVnode对应的真实节点后边

canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
// ↓↓↓↓↓上边那句话实际做的操作↓↓↓↓↓↓
// parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)

目前真实节点+对应虚拟DOM中xxxIdx的样子:

真实dom例3
oldStartIdx:0oldEndIdx:3
ABCD
newStartIdx:0newEndIdx:3

在例子中,insertBefore只是将真实DOM"D"向后移位,而在循环中的虚拟dom中的索引不会受到影响

最后将oldStartIdx设置成1,将newEndIdx分别设置成2,并更新oldStartVnode,newEndVnode

改变后例3
oldStartIdx:1oldEndIdx:3
DABC
ABCD
newStartIdx:0newEndIdx:2

老节点的尾部与新节点的头部对比

改变前例4
oldStartIdx:0oldEndIdx:3
ABCD
DABC
newStartIdx:0newEndIdx:3

和老节点的头部与新节点的尾部对比思路相同,会将newStartIdxoldEndIdx进行对比,如果二者相同,调用patchVnode,然后调用DOM原生方法insertBeforenewStartVnode对应的真实节点放在newEndVnode对应的真实节点后边

canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, nodeOps.nextSibling(oldStartVnode.elm))
// ↓↓↓↓↓上边那句话实际做的操作↓↓↓↓↓↓
// parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm.nextSibling)

目前真实节点+对应虚拟DOM中xxxIdx的样子:

真实dom例4
oldStartIdx:0oldEndIdx:3
DABC
newStartIdx:0newEndIdx:3

在例子中,insertBefore只是将真实DOM"D"向前移位,而在循环中的虚拟dom中的索引不会受到影响

最后将oldEndIdx设置成2,将newStartIdx分别设置成1,并更新oldEndVnode,newStartVnode

改变后例4
oldStartIdx:0oldEndIdx:2
ABCD
DABC
newStartIdx:1newEndIdx:3

乱序对比

当上方的几种顺序对比都没有进入if的情况下,会走else中的乱序对比逻辑,下边会逐行解析最为核心的乱序对比部分:

乱序对比中的思路是:以newCh中正序的下一个要处理的节点(newStartVnode)为基础,去oldCh中找是否有可以复用的数据,有的话和上边顺序对比一样,走patchVnode更新,没有的话走createElm创建新节点

  1. 确定oldCh中有没有可复用的老节点
    首次走进else判断时,将oldCh数组中未处理的数据转化成{[oldCh.key]:[oldCh的index]}的形式,并存入oldKeyToIdx属性中,在第二次进入else判断时直接拿出来使用
    然后通过oldKeyToIdx[newStartVnode.key]的方式就可以判断oldCh中是否有和当前循环中newStartVnode.key相同key的老节点,并可以根据oldCh[oldKeyToIdx[newStartVnode.key]]找到该节点
    如果没有找到可复用的节点,还会通过findIdxInOld方法重新在oldCh中查找一遍
// 将oldCh数组中未处理的数据转化并存入oldKeyToIdx属性中
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
// 如果有key,可以通过key拿到oldKeyToIdx列表中对应的index,如果没有key,则遍历查找index
idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)


// 下方为上边代码中用到的方法:

// 返回一个{key: index}的对象
function createKeyToOldIdx(children, beginIdx, endIdx) {
    let i, key
    const map = {}
    for (i = beginIdx; i <= endIdx; ++i) {
        key = children[i].key
        if (isDef(key)) map[key] = i
    }
    return map
}
// 查找node在oldCh中的index
function findIdxInOld (node, oldCh, start, end) {
    for (let i = start; i < end; i++) {
        const c = oldCh[i]
        // sameVnode 方法在上边有说过,作用是通过tag等内容判断两个vnode是否相同
        if (isDef(c) && sameVnode(node, c)) return i
    }
}
  1. 判断在第一步中获取的idxInOld是否有值,如果没有值,代表该vnode(newStartVnode)是一个新节点,走createElm创建
if (isUndef(idxInOld)) {
    createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
} else {...
  1. 如果idxInOld有值
    通过idxInOld获取旧节点中可复用的那个节点vnodeToMovevnodeToMove = oldCh[idxInOld]
    判断当前处理的节点newStartVnodevnodeToMove是否相同
    如果相同的话
    patchVnode更新节点,将oldCh旧节点列表中对应的这个值(oldCh[idxInOld])设置为undefined,用于标识该节点已经被处理过了。(因为这个节点并不是通过oldStartIdx或者oldEndIdx拿到的,所以没办法像顺序对比时更新这两个oldxxxIdx值来做到标识节点已经被处理过,在这里设置为undefined后,当while循环走到通过oldxxxIdx获取到该节点时,就可以通过上边说的空数据跳过处的代码跳过该节点操作了)
    最后将vnodeToMove的真实DOM通过insertBefore方法插入到下一个需要判断的节点(oldStartVnode)的前边就可以了
    如果不相同的话
    在这里如果判断出newStartVnodevnodeToMove不同,代表两个vnode只有key相同,无法复用,走createElm创建
} else {
    // 获取oldCh中可复用的那个节点
    vnodeToMove = oldCh[idxInOld]
    // 判断当前处理的节点是否相同  
    if (sameVnode(vnodeToMove, newStartVnode)) {
        // 和顺序对比思路相同,走patchVnode更新
        patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        // 把旧节点置为undefined
        oldCh[idxInOld] = undefined
        // 把要移动的真实DOM插入到下一个需要判断的节点
        canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
    } else {
        // 无法复用,走`createElm`创建
        createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
    }
}
  1. 最后++newStartIdx,并更新newStartVnode
// 更新newStartVnode并++newStartIdx
newStartVnode = newCh[++newStartIdx]

乱序对比的完整代码

while (...) {
    if (isUndef(oldStartVnode)) {
        ...
    } else if (...) {
        ...
    } else {
        // 将oldCh数组中未处理的数据转化并存入oldKeyToIdx属性中
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        // 如果有key,可以通过key拿到oldKeyToIdx列表中对应的index,如果没有key,则遍历查找index
        idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
        if (isUndef(idxInOld)) {
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        } else {
            // 获取oldCh中可复用的那个节点
            vnodeToMove = oldCh[idxInOld]
            // 判断当前处理的节点是否相同  
            if (sameVnode(vnodeToMove, newStartVnode)) {
                // 和顺序对比思路相同,走patchVnode更新
                patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
                // 把旧节点置为undefined
                oldCh[idxInOld] = undefined
                // 把要移动的真实DOM插入到下一个需要判断的节点
                canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
            } else {
                // 无法复用,走createElm创建
                createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
            }
        }
        // 更新newStartVnode并++newStartIdx
        newStartVnode = newCh[++newStartIdx]
    }
}

跳出循环后

因为循环的判断是oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx,当跳出循环后,可能会存在新节点列表或老节点列表中有没有处理完毕的节点,这里要对这些节点进行处理
**新节点列表中有未处理的数据:**老节点中已经没有可以拿出来判断的内容了,代表着剩下的新节点都是需要重新创建DOM的节点,所以直接循环调用createElm就可以了
**老节点列表中有未处理的数据:**新节点处理完毕后,老节点列表中如果有没有处理的数据,就代表剩下的数据是要删除掉的了,调用removeVnodes将剩余的节点删除

if (oldStartIdx > oldEndIdx) { // 老节点列表已经处理完毕
    refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm // 获取真实节点中要插入的节点位置后的第一个元素(用于Dom.insertBefore的传参)
    // 创建所有newCh中还未处理的节点(循环调用createElm)
    addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
} else if (newStartIdx > newEndIdx) { // 新节点列表已经处理完毕
    removeVnodes(oldCh, oldStartIdx, oldEndIdx) // 删除所有oldCh中还未处理的节点
}

------------end------------

Logo

前往低代码交流专区

更多推荐