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

# diff 原则
让我们回顾下，当 `vm` 上有更新发生时，会触发这一段代码：
```js
vm._update(vm._render(), hydrating)
```

在上一章我们知道了Vue是如何生成 `vnode` 的，也就是 `_render()` 函数的工作原理。这一章我们来看看 `Vue` 是如何把 `vnode` 渲染为真实DOM的，这一过程，我们称之为 `patch`(补丁).

`_update`函数的定义如下：

**core/instance/lifecycle.js**
```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` 的定义外，我们这里重点关心的是这两段：

```js
    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**
```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` 呢？因为这是引入了一个第三方的库，它本来就没用、
那么让我们一段段来看：

```js
 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**
```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**
```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)
    }
  }
```

这里我们一段一段来看代码，首先是：

```js
 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` 定义如下：

```js
const hooks = ['create', 'activate', 'update', 'remove', 'destroy']
```

从名字可以看出他们是在 vnode 更新的各个阶段进行相应的操作。这里，`cbs.update` 包含如下几个回调：

* updateAttributes
* updateClass
* updateDOMListeners
* updateDOMProps
* updateStyle
* update
* updateDirectives

可以看到都是对当前元素本身的一些更新操作。至于这些函数内部都做了什么，这里暂且不去深究，其实从名字已经基本可以看出他们的操作内容了。

那么在更新完当前 vnode 节点之后，对于它的孩子们显然也要更新。我们看看对孩子的更新代码：
**core/vdom/patch.js**
```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**
```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`，起始状态如下图所示：

![](https://raw.githubusercontent.com/lihongxun945/myblog/master/images/vue2/patch/diff1.png)

现在我们进行第一次循环，我们的代码会进入这一个条件：

```js
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` 都会向前移动一步，变成这样：
![](https://raw.githubusercontent.com/lihongxun945/myblog/master/images/vue2/patch/diff2.png)

此时再进行比较，会发现旧孩子的第一个和新孩子的最后一个相同，那么说明这两个被交换了，进入这段代码：

```js
 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` 交换下位置，这样我们旧的孩子就摇身一变，成了新的孩子相同的结构了：

![](https://raw.githubusercontent.com/lihongxun945/myblog/master/images/vue2/patch/diff3.png)

这样我们再次移动只针的时候，会发现 `oldStartIdx`已经移动到 `oldEndIdx` 右边了。

上面这个例子我们可以理解`更新节点`和`移动节点`两中情况，那么如果增加了节点和删除了节点呢？

先看增加节点的请款，如下图所示，假设我们增加了一个D节点：
![](https://raw.githubusercontent.com/lihongxun945/myblog/master/images/vue2/patch/diff4.png)

第一次循环的时候，显然开始的两个节点都是相同的，也就是会进入如下代码：

```js
 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
        // 省略
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      }
}
```

那么指针将会向右移动，变成这样：
![](https://raw.githubusercontent.com/lihongxun945/myblog/master/images/vue2/patch/diff5.png)

此时会发现和前面的情况差不多，B节点依然是相同的节点，因此会再次向右移动指针，就变成了这样：
![](https://raw.githubusercontent.com/lihongxun945/myblog/master/images/vue2/patch/diff6.png)

旧孩子的两个指针已经重叠了，此时显然 `oldStart` 和 `newStart` 不同，而是 `oldEnd` 和 `newEnd` 相同。因此我们这时候会向左移动指针，变成这样：
![](https://raw.githubusercontent.com/lihongxun945/myblog/master/images/vue2/patch/diff7.png)

此时已经完成了比较，因为 `oldEndIdx` 已经移动到 `oldStartIdx` 左边了，不满足循环条件。不是说好了处理新增节点的吗？怎么就退出循环了？别担心，对新增节点和删除节点的处理，都是在循环外面完成的，也就是如下代码：

```js
    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` 的代码：

```js
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)
    }
  }
```

最关键的地方是这里：
```js
 if (createComponent(vnode, insertedVnodeQueue, parentElm, refElm)) {
```

如果是一个组价，那么 `createComponent` 会返回 `true`，因此不会进行接下来的操作，如果不是组件，会进行节点创建工作，并会递归对孩子创建节点。
而 `createComponent` 其实会调用 `$mount` 来挂载组件，又回到了我们流程的最开始处。

`createElm` 代码很容易理解，这里不做过多的讲解，在阅读代码的时候主要注意 `createComponent` 启动了一个新的组件挂载流程即可。

# 完整流程图

综合前面讲过的内容，我画了一个组件挂载和更新的完整的流程图如下，希望可以帮助大家理解和记忆：
![](https://raw.githubusercontent.com/lihongxun945/myblog/master/images/vue2/patch/pipline.png)

到此我们弄懂了神秘的 `patch` 算法，以及他是如何进行Diff的。

下一章，让我们看看指令是如何工作的。

下一章 [Vue2.x源码解析系列十一：指令](https://github.com/lihongxun945/myblog/issues/34)

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

diff 原则

patch 算法

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

createElm 创建真实DOM元素

完整流程图

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development