vue源码阅读（六）：数据更新算法--patch算法

vue 源码 patch算法

数据更新的过程回顾

在组件实例初始化的过程中，Watcher实例与updateComponent创建了关联。

let updateComponent = () => {
      //更新 Component的定义，主要做了两个事情：render(生成vdom)、update(转换vdom为dom)
      vm._update(vm._render(), hydrating)
  }

重点关注vm._update()。查看/core/instance/lifecycle.js:

Vue.prototype._update = function (vnode: VNode, hydrating?: boolean) {
    ...//省略
    if (!prevVnode) {
      //初始化渲染
      vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */)
    } else {
      // updates
      vm.$el = vm.__patch__(prevVnode, vnode)
    }
    ...//省略
  }

此处的vm.__patch__()是在源码入口阶段的platforms/web/runtime/index.js中定义：

import { patch } from './patch'
//定义补丁函数,这是将虚拟DOM转换为真实DOM的操作，非常重要
Vue.prototype.__patch__ = inBrowser ? patch : noop

进入到platforms/web/runtime/patch.js:

import * as nodeOps from 'web/runtime/node-ops'
import { createPatchFunction } from 'core/vdom/patch'
import baseModules from 'core/vdom/modules/index'
import platformModules from 'web/runtime/modules/index'
const modules = platformModules.concat(baseModules)
//引入平台特有代码，其中： nodeOps是节点操作，modules是属性操作
export const patch: Function = createPatchFunction({ nodeOps, modules })

createPatchFunction({nodeOps, modules})中的两个参数nodeOps与modules都是和特定平台相关的代码。其中：

nodeOps是节点操作，定义各种原生dom基础操作方法。
modules 是属性操作，定义属性更新实现。

createPatchFunction在文件core/vdom/patch.js中。该文件是整个Vue项目中最大的文件，详细记录了patch的过程。下面我们来详细看看patch算法的原理与实现。

patch算法

patch算法通过新老VNode树的对比，根据比较结果进行最小单位地修改视图（打补丁的由来），而不是将整个视图根据新的VNode重绘。patch的核心在于diff算法。

diff算法使用同层的树节点进行比较（而非对整棵树进行逐层搜索遍历），时间复杂度只有O(n)，是一种相当高效的算法。示意如下图：两棵树之间，相同颜色的方块代表互相进行比较的VNode节点。

patch()

看看patch算法的源码：

return function patch (oldVnode, vnode, hydrating, removeOnly) {
    //新节点不存在，老节点存在，直接移除老节点
    if (isUndef(vnode)) {
      if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
      return
    }
    let isInitialPatch = false
    const insertedVnodeQueue = []
    if (isUndef(oldVnode)) {
      // empty mount (likely as component), create new root element
      isInitialPatch = true
      //新节点存在，老节点不存在，新增该节点
      createElm(vnode, insertedVnodeQueue)
    } else {
      //判断是否是真实DOM，用于区分是否是初始化逻辑
      const isRealElement = isDef(oldVnode.nodeType)
      //不是真实DOM，并且是相同的VNode元素
      if (!isRealElement && sameVnode(oldVnode, vnode)) {
        //更新操作
        patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
      } else {
        //真实DOM，即初始化逻辑
        if (isRealElement) {
          if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
            //当旧的VNode是服务端渲染的元素，hydrating记为true
            oldVnode.removeAttribute(SSR_ATTR)
            hydrating = true
          }
          if (isTrue(hydrating)) {
            //需要合并服务端渲染的页面到真实DOM上
            if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
              invokeInsertHook(vnode, insertedVnodeQueue, true)
              return oldVnode
            } 
          }
          // 不是服务端渲染节点，或者服务端渲染合并到真实DOM失败，返回一个空节点
          oldVnode = emptyNodeAt(oldVnode)
        }
        // 取代现有元素
        const oldElm = oldVnode.elm
        const parentElm = nodeOps.parentNode(oldElm)
        //生成真实DOM
        createElm(
          vnode,
          insertedVnodeQueue,
          oldElm._leaveCb ? null : parentElm, //指定父节点
          nodeOps.nextSibling(oldElm) //指定插入位置：现有元素的旁边
        )
        ...//省略
        // 移除老节点
        if (isDef(parentElm)) {
          removeVnodes([oldVnode], 0, 0)
        } else if (isDef(oldVnode.tag)) {
          invokeDestroyHook(oldVnode)
        }
      }
    }
    invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
    return vnode.elm
  }

上面代码的逻辑不算难，主要进行的是同层的树节点进行比较。其中包含的操作分别是：增加新节点、删除旧节点、更新节点。

查看源码发现，只有当判定新旧节点是同一个节点的时候，才会执行patchVnode()更新操作。怎样才算同一个节点呢？我们来看sameVnode()：

sameVnode()

/*
判断两个VNode节点是否是同一个节点，需要满足以下条件:
key相同
tag（当前节点的标签名）相同
isComment（是否为注释节点）相同
是否data（当前节点对应的对象，包含了具体的一些数据信息，是一个VNodeData类型，可以参考VNodeData类型中的数据信息）都有定义
当标签是<input>的时候，type必须相同
*/
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)
      )
    )
  )
}
/*
判断当标签是<input>的时候，type是否相同
某些浏览器不支持动态修改<input>类型，所以他们被视为不同类型
*/
function sameInputType (a, b) {
  if (a.tag !== 'input') return true
  let i
  const typeA = isDef(i = a.data) && isDef(i = i.attrs) && i.type
  const typeB = isDef(i = b.data) && isDef(i = i.attrs) && i.type
  return typeA === typeB || isTextInputType(typeA) && isTextInputType(typeB)
}

当两个VNode的tag、key、isComment都相同，并且同时定义或未定义data的时候，且如果标签为input则type必须相同。这时候这两个VNode则算sameVnode，可以直接进行patchVnode操作。

patchVnode()

  function patchVnode (
    oldVnode,
    vnode,
    insertedVnodeQueue,
    ownerArray,
    index,
    removeOnly
  ) {
    //两个VNode节点相同则直接返回
    if (oldVnode === vnode) {
      return
    }
    const elm = vnode.elm = oldVnode.elm
    ...//省略
    /*
    如果新旧VNode都是静态的，同时它们的key相同（代表同一节点），
    并且新的VNode是clone或者是标记了once（标记v-once属性，只渲染一次），
    那么只需要替换componentInstance即可。
    */
    if (isTrue(vnode.isStatic) &&
      isTrue(oldVnode.isStatic) &&
      vnode.key === oldVnode.key &&
      (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
    ) {
      vnode.componentInstance = oldVnode.componentInstance
      return
    }
    let i
    const data = vnode.data
    if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
      //i = data.hook.prepatch，如果存在，见"./create-component componentVNodeHooks"
      i(oldVnode, vnode)
    }
    const oldCh = oldVnode.children
    const ch = vnode.children
    if (isDef(data) && isPatchable(vnode)) {
        //调用update回调以及update钩子
      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)
    }
    //vnode的text属性与children属性是互斥关系，若没有text属性，必有children
    if (isUndef(vnode.text)) {
      if (isDef(oldCh) && isDef(ch)) {
        //老的有子节点，新的也有子节点，对子节点进行diff操作
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
      } else if (isDef(ch)) {
        //新的有子节点，老的没有子节点，先清空老节点的text内容
        if (process.env.NODE_ENV !== 'production') {
          checkDuplicateKeys(ch)
        }
        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) {
      //两个都没有子节点，那么替换文本内容
      nodeOps.setTextContent(elm, vnode.text)
    }
    if (isDef(data)) {
      //i = data.hook.postpatch，如果存在，见"./create-component componentVNodeHooks"
      if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
    }
  }

代码不难理解。整个patchVnode的规则是这样的：

1.如果新旧VNode都是静态的，同时它们的key相同（代表同一节点），并且新的VNode是clone或者是标记了once（标记v-once属性，只渲染一次），那么只需要替换elm以及componentInstance即可。

2.新老节点均有children子节点，则对子节点进行diff操作，调用updateChildren，这个updateChildren也是diff的核心。

3.如果老节点没有子节点而新节点存在子节点，先清空老节点DOM的文本内容，然后为当前DOM节点加入子节点。

4.当新节点没有子节点而老节点有子节点的时候，则移除该DOM节点的所有子节点。

5.当新老节点都无子节点的时候，只是文本的替换。

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
    // 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]
      /*
      前四种情况其实是指定key的时候，判定为同一个VNode，则直接patchVnode即可
      分别比较oldCh以及newCh的两头节点2*2=4种情况
      */
      } 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)) {   //头尾相同
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        //挪动oldStartVnode到oldEndVnode前面
        canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
        oldStartVnode = oldCh[++oldStartIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldEndVnode, newStartVnode)) {   //尾头相同
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        //挪动oldEndVnode到oldStartVnode前面
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        //在OldCh中，创建一张key<==>idx对应的map表，可加快查找newStartVnode是否在OldCh中
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
        if (isUndef(idxInOld)) { //如果不存在OldCh中，那么认定newStartVnode是新元素，创建
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        } else {
          vnodeToMove = oldCh[idxInOld]
          /*
          对比OldCh中找到的【相同key】的Vnode与newStartVnode，是否是相同的节点
          判断是否是相同节点，除了key相同外，还有：
            tag（当前节点的标签名）相同
            isComment（是否为注释节点）相同
            是否data都有定义
            当标签是<input>的时候，type必须相同
          */
          if (sameVnode(vnodeToMove, newStartVnode)) {
            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
            oldCh[idxInOld] = undefined
            canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
          } else {
            // 如果key相同，但是其他不同，那么认为这是新元素，创建
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
          }
        }
        newStartVnode = newCh[++newStartIdx]
      }
    }
    if (oldStartIdx > oldEndIdx) {
      //如果oldCh数组已经遍历完，newCh数组还有元素，那么将剩余元素都创建
      refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
      addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
    } else if (newStartIdx > newEndIdx) {
      //如果newCh数组已经遍历完，oldCh数组还有元素，那么将剩余元素都删除
      removeVnodes(oldCh, oldStartIdx, oldEndIdx)
    }
  }

这个过程不算复杂。通过画图的方式会更加清晰一些。

4种简单比较

在新老两个VNode节点的左右头尾两侧都有一个变量标记，在遍历过程中这几个变量都会向中间靠拢。当oldStartIdx <= oldEndIdx或者newStartIdx <= newEndIdx时结束循环。
首先，oldStartVnode、oldEndVnode与newStartVnode、newEndVnode两两比较一共有2*2=4种比较方法。

头头相等或者尾尾相等

当新老VNode节点的start或者end满足sameVnode()时，直接将对应VNode节点进行patchVnode即可。

头尾相等

如果oldStartVnode与newEndVnode满足sameVnode()，即sameVnode(oldStartVnode, newEndVnode)。这时候说明oldStartVnode已经跑到oldEndVnode后面了。进行patchVnode的同时，还需要将oldStartVnode移动到oldEndVnode的后面。

尾头相等

如果oldEndVnode与newStartVnode满足sameVnode()，即sameVnode(oldEndVnode, newStartVnode)。这说明oldEndVnode跑到了oldStartVnode的前面。进行patchVnode()的同时，还需要将oldEndVnode移动到oldStartVnode的前面。

非简单比较

如果不符合以上4种简单情况，那么在OldCh中，创建一张key<==>idx对应的map表，可加快查找newStartVnode是否在OldCh中。从这个map表中可以找到是否有与newStartVnode一致key的旧的VNode节点。如果满足sameVnode()，patchVnode()的同时会将这个真实DOM（elmToMove）移动到oldStartVnode对应的真实DOM的前面。

当然，满足相同节点的情况是美好的，更多的情况是不满足相同节点的时候：key不相同，或者key相同但依然不满足sameVnode()。这时，需要创建新节点：

当然，还有一些终止条件的判断。

如果oldCh数组已经遍历完，newCh数组还有元素，那么将剩余元素都创建。

如果newCh数组已经遍历完，oldCh数组还有元素，那么将剩余元素都删除

patch算法回顾

整个patch算法很长。整体一遍理下来，会对其实现过程有一个更加深刻的理解。

接下来想要问一个问题：updateChildren()的时候，为什么会产生头尾交叉的4种比较的方式呢？它有什么好处么？

结合实际日常网页操作的习惯：我们可能会是只拖拖拽拽一个DOM元素，其他元素都不改变；或者点击一个让展示元素逆向排序的按钮；或者清除了一个DOM元素。

这些操作，都只是简单的改变DOM树的同层结构而已。头尾交叉的比较方式，完全能够高效应对这些日常操作。

这也可以作为一个面向工程化的算法优化案例了~

MORE

关于DOM的操作更新，patch算法已经向我们展示了全部过程。不过依然还有细节没有处理完：patch的过程只是将虚拟DOM映射成了真实的DOM。那如何给这些DOM加入attr、class、style等DOM属性呢？

实际上，源码中已经有答案，只是还不够明细。它的实现依赖于VDOM的生命周期函数。在createPatchFunction()中，有这么一段：

//VDOM生命周期钩子函数
const hooks = ['create', 'activate', 'update', 'remove', 'destroy']
  //引入DOM属性相关的生命周期钩子函数
  for (i = 0; i < hooks.length; ++i) {
    cbs[hooks[i]] = []
    //modules包含[attrs,klass,events,domProps,style,transition,ref,directives]等DOM属性
    for (j = 0; j < modules.length; ++j) {
      if (isDef(modules[j][hooks[i]])) {
        cbs[hooks[i]].push(modules[j][hooks[i]])
      }
    }
  }

这个cbs数组中的函数在哪里被调用了呢？来看patchVNode()中容易被忽视的一行代码：

    if (isDef(data) && isPatchable(vnode)) {
      //调用各个DOM属性相关的update钩子函数
      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)
    }

此处正式更新对应DOM属性的所在。实际上，也就意味着，在patchVNode()过程中，DOM属性对应的更新也已经悄悄做完了。