笔记&收藏&学习

本文由简悦 SimpRead 转码，原文地址 mp.weixin.qq.com

作者：广工小成

来源：SegmentFault 思否

网上看了一些 diff 的算法，但是感觉看完之后，还是那么的一知半解，为什么一个简单的 diff 算法，不能直接画个流程图就简单的明了了呢，说动就动，下面的是本人基于 vue 版本 2.6.11 源码为各位读友进行的解析

Vue 的 diff 流程图

流程前说明

由于 diff 的过程是对 vnode（虚拟 dom）树进行层级比较，所以以同一层级作为例子
下面将旧节点列表的起始和终止节点称为 OS（OldStarVnode）和 OE（OldEndVnode），用 index 标志遍历过程 OS 和 OE 的变化。即 OS 和 OE 的 index 称为 OSIndex 和 OEIndex。同理得新节点的为 NS 和 NE，NSIndex 和 NEIndex，如下图

主流程

如下图:

文字版描述一下就是：

判断是否遍历完，未遍历则开始 2，否则，如果遍历完了旧节点列表，则未遍历的新节点则创建并且增加到节点列表，如果遍历完了新节点列表，则未遍历的旧节点在节点列表里面删除
对旧节点的 OS 和 OE 进行判空，如果为空，则跳过该节点，继续从 1 开始；否则继续 3
对 OS，OE，NS，NE 进行两两比较，如果相等，则更新节点并且指针向下一个移动，继续从 1 开始；否则继续 4
判断 NS 是否有 key，有 key 则判断 NS 是否在旧节点列表里面找到 key 一样的进行更新；否则创建 NS 并且插入节点列表

updateChildren 进行 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

    // 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]
      } 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(oldCh, oldStartIdx, oldEndIdx)
    }
  }

附，源码中部分工具函数的解释：

isUndef 对节点进行判空

function isUndef (v) {
  return v === undefined || v === null
}

sameVnode 对节点进行判断是否相等

判断新旧节点的 key
判断新旧节点的属性（tag,isComment 表示是否是注释节点，isDef 表示是否为非空节点，sameInputType 表示是否同个 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)
      )
    )
  )
}

patchVnode 更新节点

patchVnode 更新节点主要做以下事情，代码比较长就不贴了，影响读者，需要可以直接阅读源码：

判断 vnode 和 oldvnode 是否相等，相等直接返回
处理静态节点的情况
对 vnode 如果是可 patch 的情形进行调用 update
对 vnode 进行判断是否是根节点（即文本节点），如果是，则进行 5，否则则对其子节点进行遍历更新
判断 vnode 和 oldvnode 文本是否一样: 不一样则替换节点文本

最后

欢迎关注【前端瓶子君】✿✿ヽ (°▽°) ノ✿

欢迎关注「前端瓶子君」，回复「算法」，加入前端算法源码编程群，每日一刷（工作日），每题瓶子君都会很认真的解答哟！

作者：广工小成 ​

**Vue 的 diff 流程图 ** ​

流程前说明 ​

主流程 ​

updateChildren 进行 diff 算法源码 ​

附，源码中部分工具函数的解释： ​

isUndef 对节点进行判空 ​

sameVnode 对节点进行判断是否相等 ​

patchVnode 更新节点 ​

最后 ​