Vue源码拆解（二）：说说虚拟DOM补丁算法

[luoway]

前言

Virtual DOM patching algorithm（虚拟DOM补丁算法）是Vue能够称为“超快虚拟 DOM”的原因。

DOM操作慢，是前端开发者的共识，有多慢？

正好笔者很久以前fork别人的项目改改，挖了个DOM操作的坑，可以稍微感受下：PwLXXP是一个不断操作DOM实现文字动画的页面，随着操作的DOM内容越来越多，页面越来越卡，安静的电脑风扇也躁动了起来。

虚拟DOM代理了开发者直接JS操作DOM的行为，其使用JS对象树来描述DOM树，开发者只需要操作这棵JS对象树，由虚拟DOM补丁算法来决定和执行JS操作DOM。

不仅如此，在没有DOM的非浏览器环境，虚拟DOM也可以通过改写JS操作DOM的逻辑部分，来适配到这些环境。

VNode

虚拟DOM树上的每个对象节点，包括根节点，都是VNode实例对象。它在运行时存储了节点的状态信息。

完整内容见源码，本文会提到VNode的以下属性：

class VNode {
  constructor (
    tag,
    data,
    children,
    text,
    elm,
  ) {
    this.tag = tag
    this.data = data
    this.children = children
    this.text = text
    this.elm = elm
    this.componentInstance = undefined
    this.isStatic = false
    this.isComment = false
    this.isCloned = false
    this.isOnce = false
  }
}

VNode由Vue选项render函数参数createElement创建，render函数返回结果就是创建好的VNode实例对象。

createElement = ()=>VNode

Vue开发者很少手写render函数，vue-loader会在构建时帮我们将SFC（单文件组件）的template编译为组件的render函数。

patch()

Vue组件在视图更新时，总是会执行render()方法，得到一个新的VNode实例对象。见源码

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

_update源码

Vue.prototype._update = function (vnode, hydrating) {
  const vm = this
  const prevEl = vm.$el
  const prevVnode = vm._vnode
  vm._vnode = vnode
  
  if (!prevVnode) {
    vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */)
  } else {
    vm.$el = vm.__patch__(prevVnode, vnode)
  }
  //...
}

vm.__patch__是Vue内部patch()函数的别名，见源码

Vue.prototype.__patch__ = inBrowser ? patch : noop

vm._vnode是直接替换成新的VNode对象了，但DOM是不受影响的。

对比新旧VNode对象，更新DOM，是patch()函数的逻辑。

patch()函数是与环境相关的，浏览器和非浏览器环境，操作逻辑就存在差异。

因此，Vue在源码中使用createPatchFunction接收差异内容为参数，返回运行时的patch()函数

源码

function patch (oldVnode, vnode, hydrating, removeOnly) {
  if(isUndef(oldVnode)){
    createElm(vnode, [])
  }else{
    const isRealElement = isDef(oldVnode.nodeType)
    if (!isRealElement && sameVnode(oldVnode, vnode)) {
      // 给存在的节点打补丁
      patchVnode(oldVnode, vnode, [], null, null, removeOnly)
    } else {
      // 处理SSR融合逻辑
      // 或根据vnode创建新的DOM元素
    }
    
    return vnode.elem
  }
}

参数oldVnode可能传入的是真实DOM元素，也可能是不满足sameVnode()判断的VNode实例，此时Vue需要融合或替换整个DOM元素内容。

sameVnode()

sameVnode()是判断两个Vnode实例对象本身是否相似的方法，在补丁算法中被高频地使用，满足判断的VNode节点对应的DOM节点就可以被复用，但VNode节点的后代（children）仍需进行比较。

源码

function sameVnode (a, b) {
  return (
    a.key === b.key && //key相同
    a.tag === b.tag && //节点标签相同
    a.isComment === b.isComment && //是否是注释节点，要相同
    isDef(a.data) === isDef(b.data) && //是否有data属性定义，要相同
    sameInputType(a, b) //函数内容：如果tag是input，那么type也要相同
  )
}

patchVnode()

patchVnode()是深入比较两个VNode实例对象，并根据差异给DOM节点打补丁的方法

源码

function patchVnode ( oldVnode, vnode, insertedVnodeQueue, ownerArray, index, removeOnly) {
  //满足sameVnode()判断后，即可复用原有DOM节点
  const elm = vnode.elm = oldVnode.elm
  
  if (isTrue(vnode.isStatic) &&
      isTrue(oldVnode.isStatic) && //同为静态节点
      vnode.key === oldVnode.key && //key相同
      (isTrue(vnode.isCloned) || isTrue(vnode.isOnce)) //有isCloned或isOnce标记
   ) {
    //直接复用旧组件实例
    vnode.componentInstance = oldVnode.componentInstance
    return
  }
  
  const oldCh = oldVnode.children
  const ch = vnode.children
  
  /*如果这个VNode节点没有text文本时*/
  if (isUndef(vnode.text)) {
    if (isDef(oldCh) && isDef(ch)) {
      /*新老节点均有children子节点，则对子节点进行diff操作，调用updateChildren*/
      if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
    } else if (isDef(ch)) {
      /*如果老节点没有子节点而新节点存在子节点，先清空elm的文本内容，然后为当前节点加入子节点*/
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
    } else if (isDef(oldCh)) {
      /*当新节点没有子节点而老节点有子节点的时候，则移除所有ele的子节点*/
      removeVnodes(elm, oldCh, 0, oldCh.length - 1)
    } else if (isDef(oldVnode.text)) {
      /*当新老节点都无子节点的时候，只是文本的替换，因为这个逻辑中新节点text不存在，所以直接去除ele的文本*/
      nodeOps.setTextContent(elm, '')
    }
  } else if (oldVnode.text !== vnode.text) {
    /*当新老节点text不一样时，直接替换这段文本*/
    nodeOps.setTextContent(elm, vnode.text)
  }
}

patchVnode()难点在于，新老节点均存在子节点时，如何找出新老节点的子节点的差异，并将差异使用最小DOM操作应用到DOM上。这块逻辑就是Vue的虚拟DOM diff算法，由updateChildren()函数实现。

updateChildren()

源码有70行，条件分支很多，但理解后并不复杂。本文就简单说说逻辑实现：

updateChildren()接收的参数主要有3个：

• parentElm父元素
• oldCh旧子节点数组
• newCh新子节点数组

已知通过sameVnode()可以判断节点是否“相同”（当前节点相同，子节点仍需patchVnode()），那么要找出差异部分，剩下的问题就是：

比较oldCh与newCh两个数组的最小差异，即找出相同的项进行对应DOM节点移位，不相同的项进行对应DOM节点添加或删除。

问题的解法可以是：

由于Vue是以VNode的key值异同作为基准来区分节点差异的，可以取oldCh中每项的key与索引的哈希表，作为从oldCh中查找newCh每项的依据。

遍历newCh，依据哈希表来检索是否存在oldCh中，就有以下情况：

• key不存在，则是新增节点，需要在DOM上对应位置添加新节点
• key存在
  • sameVnode()为假，仍是新增节点
  • sameVnode()为真，那么节点就需要被复用，即将DOM节点从oldCh原有位置移动到newCh现在位置
• 若DOM子节点数目大于newCh子节点数目，说明DOM有多余节点，需要移除掉。

解决问题的过程如上，但算法显然有优化的空间，如DOM移除多余节点这一步，就得再遍历一遍DOM找出多余节点。Vue在用的diff算法正是优化过后的，使用双指针的解法：

1. 分别对oldCh、newCh设置头、尾双指针
2. 使用while循环，循环终止条件为oldCh、newCh任一对双指针的头指针索引大于尾指针索引
   1. oldCh中头尾节点可能是空数据，跳过
   2. sameVnode()判断oldCh与newCh头尾节点是否相同，即无需操作DOM，或是DOM节点应当从头部移动到尾部等，共2×2=4种情况
   3. 以上判断无效，则使用存在的哈希表（无哈希表则创建）查找newCh头节点
      • 未找到，则是新增节点，需要在DOM上对应位置添加新节点
      • 找到
        • sameVnode()为假，仍是新增节点
        • sameVnode()为真，那么节点就需要被复用，即将DOM节点从oldCh原有位置移动到newCh现在位置。另外，由于仍在patch()逻辑中，需对节点执行patchVnode()。
3. while循环结束后，根据双指针状态区分oldCh、newCh哪个先遍历完，补充未遍历完的后续处理
   • oldCh先结束，则newCh里还有多的节点，需要添加到DOM上
   • newCh先结束，则oldCh里还有多的节点，需要从DOM上移除

小结

patch()的主要函数和功能有：

• patch()：判断是否是初始化，需要融合SSR存在的DOM或创建新DOM。否则执行VNode补丁算法
• sameVnode()：VNode相同的判断依据
• patchVnode()：相同的Vnode可以复用当前DOM节点，仍需递归判断后代节点是否相同
• updateChildren()：判断子节点是否相同，相同则继续patchVnode()，且负责处理DOM节点顺序