vue中的diff算法解析

分析的整体思路是从一个简单例子的执行流程去分析演示diff的工作机制。下面先介绍一下几个patch.js中的函数：
1.判断两个vnode是否相同的函数，可以看到首先比较的是两个节点的key值是否相同，注意的是，当不设置key的时候，undefined与undefined是相等的，后面继续比较vnode的标签，注释节点，是否有数据等条件，以及如果是输入框类型会进行类型校验。从这里我们可以分析出，如果虚拟dom的子元素列表只包含文本节点并且dom结构一致的话，其实不设置key的时候更新dom的效率是更高的，不需要进行过多的判断逻辑，只用patchVnode函数去更新vnode的文本就好，这要比设置了key后进行dom的insert操作高效的多。

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

2.对vnode进行patch操作，更新vnode的内容，包括移除oldVnode的子元素，在oldVnode内部添加子元素，更新文本节点，或者新旧vnode都有子元素的时候，去继续调用updateChildren函数进行diff操作。

 function patchVnode (
    oldVnode,
    vnode,
    insertedVnodeQueue,
    ownerArray,
    index,
    removeOnly
  ) {
    //....
  }

3.创建一个key与下标为映射关系的对象，当设置了key时可以通过此对象快速找到对应新旧vnode的对应关系。

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
}

4.当不设置key时候，使用此函数找出新旧vnode匹配的下标

function findIdxInOld (node, oldCh, start, end) {
    for (let i = start; i < end; i++) {
      const c = oldCh[i]
      if (isDef(c) && sameVnode(node, c)) return i
    }
  }

5.diff算法的核心方法

function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
    let oldStartIdx = 0
    let newStartIdx = 0
    let oldEndIdx = oldCh.length - 1
    let oldStartVnode = oldCh[0]
    let oldEndVnode = oldCh[oldEndIdx]
    let newEndIdx = newCh.length - 1
    let newStartVnode = newCh[0]
    let newEndVnode = newCh[newEndIdx]
    let oldKeyToIdx, idxInOld, vnodeToMove, refElm

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
        oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
      } else if (isUndef(oldEndVnode)) {
        oldEndVnode = oldCh[--oldEndIdx]
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        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)) { // Vnode moved right
        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)) { // Vnode moved left
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        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 {
          vnodeToMove = oldCh[idxInOld]
          if (sameVnode(vnodeToMove, newStartVnode)) {
            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
            oldCh[idxInOld] = undefined
            canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
          } else {
            // same key but different element. treat as new element
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
          }
        }
        newStartVnode = newCh[++newStartIdx]
      }
    }
    if (oldStartIdx > oldEndIdx) {
      refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
      addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
    } else if (newStartIdx > newEndIdx) {
      removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
  }

1.不设置key的情况下，具体步骤。

我们假设旧的节点为A,B,C,D，新的节点为C,E,A,B,D。下面通过图示结合文字说明一下执行过程。

image.png

首先确定新旧两个dom的开始于结束节点。对应代码：

image.png

进入while循环后，新旧头头，尾尾，头尾，头尾四种比较，尾尾比较满足条件，进行patch操作，改变新旧Ch尾节点对象。

   else if (sameVnode(oldEndVnode, newEndVnode)) {
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      }

image.png

下次while循环会进入最后的else逻辑。通过findIdxInOld函数可以找到C在oldCh的下标，执行patch与insert操作，oldCh变为下图所示：

image.png

接着E节点无法在oldCh中找到，会执行createElm操作，变为下图：

image.png

下一次循环中会命中头头节点相同的逻辑，进行patch操作以及头节点后移操作。

image.png
继续循环，与上一次一样重复操作，处理过后，newCh中的起始下标大于了结束下标，所以会退出循环。

 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx)

退出循环说明diff操作基本流程执行完毕，最后一步是要进行多余节点的删除或者缺失节点的添加操作。这个例子会将前面置为undefined的节点删除掉，对应代码如下：

  if (oldStartIdx > oldEndIdx) {
      refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
      addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
    } else if (newStartIdx > newEndIdx) {
      removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }

至此，一次不带key的完整diff流程就执行完毕了。

2.设置了key的流程

其实有key无key主要影响两个地方，分别是sameVnode函数与下图两个地方

image.png

设置了key，可以通过key快速的区分出是否是同一vnode，以及可以快速从上面创建的key与下标对象中找出对应的下标。很显然，大多数情况下设置了key可以让dom更新更加迅速高效。而整体diff流程上，有无key的过程并无差别。