Vue2.x源码解析系列十：Patch和Diff 算法

[lihongxun945]

diff 原则

让我们回顾下，当 vm 上有更新发生时，会触发这一段代码：

vm._update(vm._render(), hydrating)

在上一章我们知道了Vue是如何生成 vnode 的，也就是 _render() 函数的工作原理。这一章我们来看看 Vue 是如何把 vnode 渲染为真实DOM的，这一过程，我们称之为 patch(补丁).

_update函数的定义如下：

core/instance/lifecycle.js

Vue.prototype._update = function (vnode: VNode, hydrating?: boolean) {
    const vm: Component = this
    const prevEl = vm.$el
    const prevVnode = vm._vnode
    const prevActiveInstance = activeInstance
    activeInstance = vm
    vm._vnode = vnode
    // Vue.prototype.__patch__ is injected in entry points
    // based on the rendering backend used.
    if (!prevVnode) {
      // initial render
      vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */)
    } else {
      // updates
      vm.$el = vm.__patch__(prevVnode, vnode)
    }
    // 省略
  }

这里除了对 prevVnode 以及 prevEl 的定义外，我们这里重点关心的是这两段：

    if (!prevVnode) {
      // initial render
      vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */)
    } else {
      // updates
      vm.$el = vm.__patch__(prevVnode, vnode)
    }

他们的主要区别是 prevVnode 是否存在，显然，如果是第一次渲染，那么是不存在的，从第二次开始就存在了。由于我们每次patch的时候，入口肯定是根节点，因此第一次渲染的时候，prevVnode 就变成了我们要挂载的那个DOM元素，一般是 <div id="app"></div>。

在我们看 patch 算法之前，这里必须提到react对Diff算法的说明：https://reactjs.org/docs/reconciliation.html 。由于对一颗树进行完整的diff需要的时间复杂度是 O(n^3)，所以我们必须有一些妥协来加快速度。React中提到了两个假设，在Vue中同样适用：

1. 两个不同类型的元素将产生不同的树。
2. 通过渲染器附带key属性，开发者可以示意哪些子元素可能是稳定的。

这个假设有点难以理解，通俗点说就是：

• 如果是不同类型的元素，则认为是创建了新的元素，而不会递归比较他们的孩子
• 只进行统一层级的比较，如果夸层级的移动则视为创建/删除操作
• 如果是列表元素等比较相似的内容，可以通过key来唯一确定。
  而所有的修改类型总结起来无非是这么几种：
• 替换：用新元素替换旧元素，比如用 p 替换 span 则会删除 span 并重新创建一个 p
• 移动：移动元素
• 删除：删除元素
• 增加：创建元素
• 修改属性：直接修改修行
• 修改文本：直接修改元素的 textContent 即可

patch 算法

弄清楚了这些原则，让我们进入 patch 的代码看看：
core/vdom/patch.js

  return function patch (oldVnode, vnode, hydrating, removeOnly, parentElm, refElm) {
    if (isUndef(vnode)) {
      if (isDef(oldVnode)) { invokeDestroyHook(oldVnode); }
      return
    }

    var isInitialPatch = false;
    var insertedVnodeQueue = [];

    if (isUndef(oldVnode)) {
      // empty mount (likely as component), create new root element
      isInitialPatch = true;
      createElm(vnode, insertedVnodeQueue, parentElm, refElm);
    } else {
      var isRealElement = isDef(oldVnode.nodeType);
      if (!isRealElement && sameVnode(oldVnode, vnode)) { //比较元素类型
        // patch existing root node
        patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly); //相同则比较元素
      } else {
          // 省略
          oldVnode = emptyNodeAt(oldVnode);
        }

        // replacing existing element
        var oldElm = oldVnode.elm;
        var parentElm$1 = nodeOps.parentNode(oldElm);

        // create new node
        // 不同则直接创建新的
        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$1,
          nodeOps.nextSibling(oldElm)
        );

        // 省略 parent相关内容
      }
    }

    invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch);
    return vnode.elm
  }

省略了一些代码之后，patch 函数的代码依然还是比较长的。眼见的童鞋可能注意到了，这里怎么没有 flow 呢？因为这是引入了一个第三方的库，它本来就没用、
那么让我们一段段来看：

 var isRealElement = isDef(oldVnode.nodeType);
      if (!isRealElement && sameVnode(oldVnode, vnode)) {
        // patch existing root node
        patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly);
      }

这里面的 isRealElement 其实就是根据有没有 nodeType 来判断是不是真实DOM，vnode 是不存在这个字段的。如果不是真实DOM元素，并且这两个节点是相同的，那就就会进入这个 if 内部，进行 patchVnode ，这个函数其实主要就是对children进行diff以决定该如何更新。那么什么叫相同节点呢?我们看看 sameVnode 的代码：

core/vdom/patch.js

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

这里的判断条件其实主要是两个：

• key 必须相同（都是 undefined 则也是相同的），
• DOM 元素的标签必须相同。比如都是 div
  如果满足以上条件，那么就认为是相同的vnode，因此就可以进行 patchVnode 操作。那么如果不是呢？就认为是完全新的一个 vnode，因此会进入下面的 createElm。让我们梳理下逻辑：当进入 patch 之后有两种分支可以走：
• 如果是第一次patch（组件第一次挂载的时候），或者发现元素的标签不相同了（比如div 变p了），那么直接 createElm 创建新的DOM元素
• 否则，就是对已存在的DOM元素进行更新，那么通过 patchVnode 进行diff，有条件的更新以提升性能

这样其实就实现了 React 中原则的第一条，即：两个不同类型的元素将产生不同的树。只要发现两个元素的类型不同，我们直接删除旧的并创建一个新的，而不是去递归比较。
那么如果发现他们相同呢？这时候就需要做两件事：

• 比较并更新当前元素的差异
• 递归比较children
  因此patchVnode显然实现了这两部分，那么让我们来看看 patchVnode的代码：

core/vdom/patch.js

function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
    if (oldVnode === vnode) {
      return
    }

    const elm = vnode.elm = oldVnode.elm

    //省略

    const oldCh = oldVnode.children
    const ch = vnode.children
    // 这里的 cbs.update 就是更新attributes的
    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)) { // 非Text元素
      if (isDef(oldCh) && isDef(ch)) {
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
      } else if (isDef(ch)) {
        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
      } else if (isDef(oldCh)) {
        removeVnodes(elm, oldCh, 0, oldCh.length - 1)
      } else if (isDef(oldVnode.text)) {
        nodeOps.setTextContent(elm, '')
      }
    } else if (oldVnode.text !== vnode.text) { // text元素直接更新text
      nodeOps.setTextContent(elm, vnode.text)
    }
    if (isDef(data)) {
      if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
    }
  }

这里我们一段一段来看代码，首先是：

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

这里的 cbs 其实是从 hooks中来的，hooks 定义如下：

const hooks = ['create', 'activate', 'update', 'remove', 'destroy']

从名字可以看出他们是在 vnode 更新的各个阶段进行相应的操作。这里，cbs.update 包含如下几个回调：

• updateAttributes
• updateClass
• updateDOMListeners
• updateDOMProps
• updateStyle
• update
• updateDirectives

可以看到都是对当前元素本身的一些更新操作。至于这些函数内部都做了什么，这里暂且不去深究，其实从名字已经基本可以看出他们的操作内容了。

那么在更新完当前 vnode 节点之后，对于它的孩子们显然也要更新。我们看看对孩子的更新代码：
core/vdom/patch.js

 if (isUndef(vnode.text)) { // 非Text元素
      if (isDef(oldCh) && isDef(ch)) {
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
      } else if (isDef(ch)) {
        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
      } else if (isDef(oldCh)) {
        removeVnodes(elm, oldCh, 0, oldCh.length - 1)
      } else if (isDef(oldVnode.text)) {
        nodeOps.setTextContent(elm, '')
      }
    } else if (oldVnode.text !== vnode.text) { // text元素直接更新text
      nodeOps.setTextContent(elm, vnode.text)
    }

这时候分两种情况：

• 如果孩子不是textNode，那么需要再分三种情况处理
• 如果当前孩子是 textNode 那么直接更新 text即可

对孩子是vnode的三种情况：

• 有新孩子无旧孩子，直接创建新的
• 有旧孩子无新孩子，直接删除旧的
• 新旧孩子都有，那么调用 updateChildren 比较他们的差异，而这一部分就是diff算法的精髓所在

弄懂了这部分，那么下面让我们看看 updateChildren 是如何对孩子们的差异进行比较的

updateChildren 孩子差异比较算法，diff算法的核心

当新旧节点都有孩子的时候，我们就需要进行孩子的比较。对于每一个孩子节点，我们依然有这么几种可能：

• 更新了节点
• 删除了节点
• 增加了节点
• 移动了节点

Vue对新旧两个children数组分别在首位各用了一个指针，总共四个指针，由于指针仅仅对数组进行了一次遍历，因此时间复杂度是 O(n)，这是非常小的开销。下面我们举个例子来说明如何进行diff的。

updateChildren完整代码如下：
core/vdom/patch.js

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)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
        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)
        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)
            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)
    }
  }

假设我们有三个节点 A,B,C，我们更新之后把 A,B位置调换了，变成了 B,A,C，起始状态如下图所示：

现在我们进行第一次循环，我们的代码会进入这一个条件：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
      //省略
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      }
}

因为我们此时发现，只有最后两个节点 C 是相同的，因此进入对C节点的递归比较，如果此节点有更新，会按照我们前面所讲的内容在 patchVnode 中对其进行更新。

那么更新C节点之后，oldEndIdx 和 newEndIdx 都会向前移动一步，变成这样：

此时再进行比较，会发现旧孩子的第一个和新孩子的最后一个相同，那么说明这两个被交换了，进入这段代码：

 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
        //省略
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
        canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
        oldStartVnode = oldCh[++oldStartIdx]
        newEndVnode = newCh[--newEndIdx]
      }
}

那么除了更新 oldStartVnode 和 newEndVnode之外，最重要的操作是要把 oldStartIdx 和 oldEndIdx 交换下位置，这样我们旧的孩子就摇身一变，成了新的孩子相同的结构了：

这样我们再次移动只针的时候，会发现 oldStartIdx已经移动到 oldEndIdx 右边了。

上面这个例子我们可以理解更新节点和移动节点两中情况，那么如果增加了节点和删除了节点呢？

先看增加节点的请款，如下图所示，假设我们增加了一个D节点：

第一次循环的时候，显然开始的两个节点都是相同的，也就是会进入如下代码：

 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
        // 省略
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      }
}

那么指针将会向右移动，变成这样：

此时会发现和前面的情况差不多，B节点依然是相同的节点，因此会再次向右移动指针，就变成了这样：

旧孩子的两个指针已经重叠了，此时显然 oldStart 和 newStart 不同，而是 oldEnd 和 newEnd 相同。因此我们这时候会向左移动指针，变成这样：

此时已经完成了比较，因为 oldEndIdx 已经移动到 oldStartIdx 左边了，不满足循环条件。不是说好了处理新增节点的吗？怎么就退出循环了？别担心，对新增节点和删除节点的处理，都是在循环外面完成的，也就是如下代码：

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

当循环结束的时候，如果oldStartIdx > oldEndIdx 也就是我们这里的情况，旧孩子的循环先结束，如果新孩子的未遍历完，那么肯定是增加节点了。在 addVnodes 中会判断指针情况决定是否增加孩子。
同理，如果 newStartIdx > newEndIdx 那么有可能是因为删除了节点，才导致新孩子遍历完了，旧孩子可能还没完的情况，因此调用 removeVnodes 来删除节点。

当然，如果你定义了 key，Vue可以直接根据key找到 index进行比较。

以上就是 diff 算法的核心内容。

createElm 创建真实DOM元素

最后我们说到，无论怎么比较，最终都是调用 createElm 来根据 vnode 创建真实的DOM的。当然createElm 并不是简单的创建DOM，让我们再来看 createElm 的代码：

function createElm (
    vnode,
    insertedVnodeQueue,
    parentElm,
    refElm,
    nested,
    ownerArray,
    index
  ) {
    // 省略
    if (createComponent(vnode, insertedVnodeQueue, parentElm, refElm)) {
      return
    }

    const data = vnode.data
    const children = vnode.children
    const tag = vnode.tag
    if (isDef(tag)) {

      vnode.elm = vnode.ns
        ? nodeOps.createElementNS(vnode.ns, tag)
        : nodeOps.createElement(tag, vnode)
      setScope(vnode)

      /* istanbul ignore if */
      if (__WEEX__) {
        //省略weex
      } else {
        createChildren(vnode, children, insertedVnodeQueue)
        if (isDef(data)) {
          invokeCreateHooks(vnode, insertedVnodeQueue)
        }
        insert(parentElm, vnode.elm, refElm)
      }

      if (process.env.NODE_ENV !== 'production' && data && data.pre) {
        creatingElmInVPre--
      }
    } else if (isTrue(vnode.isComment)) {
      vnode.elm = nodeOps.createComment(vnode.text)
      insert(parentElm, vnode.elm, refElm)
    } else {
      vnode.elm = nodeOps.createTextNode(vnode.text)
      insert(parentElm, vnode.elm, refElm)
    }
  }

最关键的地方是这里：

 if (createComponent(vnode, insertedVnodeQueue, parentElm, refElm)) {

如果是一个组价，那么 createComponent 会返回 true，因此不会进行接下来的操作，如果不是组件，会进行节点创建工作，并会递归对孩子创建节点。
而 createComponent 其实会调用 $mount 来挂载组件，又回到了我们流程的最开始处。

createElm 代码很容易理解，这里不做过多的讲解，在阅读代码的时候主要注意 createComponent 启动了一个新的组件挂载流程即可。

完整流程图

综合前面讲过的内容，我画了一个组件挂载和更新的完整的流程图如下，希望可以帮助大家理解和记忆：

到此我们弄懂了神秘的 patch 算法，以及他是如何进行Diff的。

下一章，让我们看看指令是如何工作的。

下一章 Vue2.x源码解析系列十一：指令