vue源码阅读六：diff 算法

[yangrenmu]

前言

在vue中，首先是将模板编译成虚拟DOM，然后再将虚拟DOM转为真实的DOM。当我们的页面有更新时，仅仅是改变了很小的一部分，要去替换整体旧的DOM的话，势必会影响性能和用户体验的。所以vue中使用diff算法来优化DOM的更新渲染。

createPatchFunction

在将虚拟DOM转为真实DOM中，有一个很重要的函数，就是createPatchFunction。其中又有一段很重要的代码。

  return function patch(oldVnode, vnode, hydrating, removeOnly) {
    ...
    // 没有旧节点，直接生成新节点
    if (isUndef(oldVnode)) {
      createElm(vnode, insertedVnodeQueue)
    } else {
      const isRealElement = isDef(oldVnode.nodeType)
      // 先用 sameVnode 判断新旧节点是否一样，一样的话，
      // 就用 patchVnode 找不一样的地方，比如说子节点之类的
      if (!isRealElement && sameVnode(oldVnode, vnode)) {
        patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
      } else {
        // 创建新节点
        createElm(
          vnode,
          insertedVnodeQueue,
          oldElm._leaveCb ? null : parentElm,
          nodeOps.nextSibling(oldElm)
        )
        // 销毁旧节点
        if (isDef(parentElm)) {
          removeVnodes([oldVnode], 0, 0)
        } else if (isDef(oldVnode.tag)) {
          invokeDestroyHook(oldVnode)
        }
      }
    }
    ...
    return vnode.elm
  }

这里分为三种情况，

• 1、没有旧节点：直接创建新节点
• 2、有旧节点，但是和新节点不一样：创建新节点，删除旧节点
• 3、有旧节点，但是和新节点一样：进入patchVnode

前两种情况，之前的文章中，已经讲过。接下来，我们就详细看看patchVnode

patchVnode

  function patchVnode(
    oldVnode,
    vnode,
    insertedVnodeQueue,
    ownerArray,
    index,
    removeOnly
  ) {
    // ...
    // 新旧节点完全一致，直接返回
    if (oldVnode === vnode) {
      return
    }
    // 将旧节点上的 DOM，添加到新节点上。之后新旧节点若有不一致，直接修改 elm 即可
    const elm = vnode.elm = oldVnode.elm

    const oldCh = oldVnode.children
    const ch = vnode.children
    // 新节点不是文本节点
    if (isUndef(vnode.text)) {
      if (isDef(oldCh) && isDef(ch)) {
        // 新旧节点都存在子元素
        if (oldCh !== ch) 
        updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
      } else if (isDef(ch)) {
        // 只有新节点存在子元素，先清空节点上的文本，然后将子元素创建为真实 DOM 插入
        if (isDef(oldVnode.text)) nodeOps.setTextContent(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, '')
      }
    } else if (oldVnode.text !== vnode.text) {
      // 新旧节点上的文本节点不一致，更新新节点上的 DOM
      nodeOps.setTextContent(elm, vnode.text)
    }
    //...
  }

patchVnode主要做了两件事，

• 1、判断新节点是否是文本节点，如果是文本节点，就需要判断与旧节点上的文本节点是否一致。不一致的时候，就需要更新节点上的文本。

• 2、是当新节点不是文本节点时候，就需要对新旧节点的子元素进行判断了。这里有四种情况：

  • 新旧节点都有children：使用updateChildren比较两个children。
  • 只有新节点有children：清空旧节点上的文本，然后将新节点创建为真实DOM后，插入到父节点。
  • 只有旧节点有children：删除节点上的children。
  • 当只有旧节点上有文本时：新节点上没有，直接清空即可。

updateChildren

重点看下updateChildren这个函数，

  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) {
      // 如果旧节点中开始的节点是 undefined，开始节点下标就后移一位
      if (isUndef(oldStartVnode)) {
        oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
      } else if (isUndef(oldEndVnode)) {
        // 如果旧节点结束节点是 undefined，结束节点下标就迁移一位
        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 {
        // 否则，将每个旧节点的 key 值组成一个对应的 map 表，然后判断新节点的 key 是否在 map 表中
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        // idxInOld 是在旧节点列表中，与新节点相同的旧节点位置
        idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key] // key 值比较
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) // sameVnode 进行比较
        if (isUndef(idxInOld)) { // New element
          // 如果 key 不在 map 表中，则创建新节点
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        } else {
          // 若在，则判断该 key 值对应的旧节点与新节点是否是相同的节点
          vnodeToMove = oldCh[idxInOld]
          if (sameVnode(vnodeToMove, newStartVnode)) {
            // 若该 key 值对应的旧节点与新节点是相同的节点，则比较他们的子节点
            // 同时将该 key 值对应的节点插入到旧开始节点之前
            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)
          }
        }
        // key 值判断之后，新开始节点后移一位
        newStartVnode = newCh[++newStartIdx]
      }
    }
    if (oldStartIdx > oldEndIdx) {
      // 如果旧节点列表先处理完，则将剩余的新节点创建为真实 DOM 插入
      refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
      addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
    } else if (newStartIdx > newEndIdx) {
      // 如果新节点列表先处理完，则删除剩余的旧节点
      removeVnodes(oldCh, oldStartIdx, oldEndIdx)
    }
  }

可以看出updateChildren主要的作用是比较新旧子节点，分为5种情况：

• 1、旧开始节点 == 新开始节点
  若旧开始节点与新开始节点相等时，说明旧开始节点的位置是对的，不需要更新该节点。之后是将旧开始节点和新开始节点的下标后移一位。

• 2、旧结束节点 == 新结束节点
  若旧结束节点与新结束节点相等，说明旧节点的位置是对的，不需要更新该节点。之后是将旧结束节点和新结束节点的下标前移一位。

• 3、旧开始节点 == 新结束节点
  若旧开始节点与新结束节点相等，说明旧开始节点的位置不对了，需要移动到oldEndVnode后面。然后将旧开始节点的下标后移一位，新结束节点的下标前移一位。

• 4、旧结束节点 == 新开始节点
  若旧结束节点与新开始节点相等，说明旧结束节点需要移动到oldStartVnode前面。然后将旧结束节点前移一位，新开始节点位置后移一位。

• 5、key 值查找

  当前面四种比较都不行的时候，则会去通过key值进行查找。查找时候是当前的新节点，去遍历旧节点数组，找到相同的旧节点，然后将其移到 oldStartVnode 前面。大致流程是：

处理剩余节点

接着就是处理余下的新旧节点。有两种情况：

• 1、新节处理完了，旧节点还有剩余
  将剩余的旧节点，逐个删除即可。

  // 删除剩余的旧节点
  removeVnodes(oldCh, oldStartIdx, oldEndIdx)
  
  function removeVnodes(vnodes, startIdx, endIdx) {
    for (; startIdx <= endIdx; ++startIdx) {
      const ch = vnodes[startIdx]
      if (isDef(ch)) {
        if (isDef(ch.tag)) {
          removeAndInvokeRemoveHook(ch)
          invokeDestroyHook(ch)
        } else { // Text node
          removeNode(ch.elm)
        }
      }
    }
  }

• 2、新节点有剩余，旧节点处理完了
  逐个创建剩余的新节点。有个问题是，将剩余的新节点创建好后，插入到哪里呢？

  // 将剩余的新节点创建为真实的 DOM 插入
  refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
  addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
  function addVnodes(parentElm, refElm, vnodes, startIdx, endIdx, insertedVnodeQueue) {
    for (; startIdx <= endIdx; ++startIdx) {
      createElm(vnodes[startIdx], insertedVnodeQueue, parentElm, refElm, false, vnodes, startIdx)
    }
  }

我们可以看到，refElm 是获取新节点最后一个节点。
如果refElm存在的话，说明最后一个节点之前被处理过，那么剩余的新节点插入到refElm前面即可。
如果refElm不存在，则将剩余的新节点插入到父节点孩子的末尾。

本文到此也就结束了，相信大家也对 vue 中 diff 算法有一定了解。结束的结束，有个小问题，大家觉得 v-for 中 key 值的作用是什么呢？