Vue 2.x 源码解析(十):Patch 和 Diff 算法

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(组件第一次挂载的时候),或者发现元素的标签不相同了(比如 divp 了),那么直接 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

弄懂了这部分,那么下面让我们看看 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节点之后, oldEndIdxnewEndIdx 都会向前移动一步,变成这样:

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

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

那么除了更新 oldStartVnodenewEndVnode 之外,最重要的操作是要把 oldStartIdxoldEndIdx 交换下位置,这样我们旧的孩子就摇身一变,成了新的孩子相同的结构了:

这样我们再次移动只针的时候,会发现 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节点依然是相同的节点,因此会再次向右移动指针,就变成了这样:

旧孩子的两个指针已经重叠了,此时显然 oldStartnewStart 不同,而是 oldEndnewEnd 相同。因此我们这时候会向左移动指针,变成这样:

此时已经完成了比较,因为 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的。

下一章,让我们看看插件是如何工作的。

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章